Proceedings

Survey on Graph Neural Network Acceleration: An Algorithmic Perspective

Video #1 Video #2 Download BibTeX Cite

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence. Survey Track. Pages 5521-5529.

https://doi.org/10.24963/ijcai.2022/772

Abstract

Graph neural networks (GNNs) have been a hot spot of recent research and are widely utilized in diverse applications. However, with the use of huger data and deeper models, an urgent demand is unsurprisingly made to accelerate GNNs for more efficient execution. In this paper, we provide a comprehensive survey on acceleration methods for GNNs from an algorithmic perspective. We first present a new taxonomy to classify existing acceleration methods into five categories. Based on the classification, we systematically discuss these methods and highlight their correlations. Next, we provide comparisons from aspects of the efficiency and characteristics of these methods. Finally, we suggest some promising prospects for future research.

  1. [Abadal et al., 2021] Sergi Abadal, Akshay Jain, Robert Guirado, and et al. Computing graph neural networks: A survey from algorithms to accelerators. ACM Computing Surveys (CSUR), 54(9):1-38, 2021.
  2. [Arka et al., 2021] Aqeeb Iqbal Arka, Biresh Kumar Joardar, Janardhan Rao Doppa, and et al. Dare: Droplayer-aware manycore reram architecture for training graph neural net- works. In ICCAD, pages 1-9, 2021.
  3. [Bahri et al., 2021] Mehdi Bahri, Gaétan Bahl, and Stefanos Zafeiriou. Binary graph neural networks. In CVPR, pages 9492-9501, 2021.
  4. [Battaglia et al., 2018] Peter W Battaglia, Jessica B Ham- rick, Victor Bapst, and et al. Relational inductive bi- ases, deep learning, and graph networks. arXiv preprint arXiv:1806.01261, 2018.
  5. [Bojchevski et al., 2020] Aleksandar Bojchevski, Johannes Klicpera, Bryan Perozzi, and et al. Scaling graph neural networks with approximate pagerank. In SIGKDD, pages 2464-2473, 2020.
  6. [Boyd et al., 2011] Stephen Boyd, Neal Parikh, and Eric Chu. Distributed optimization and statistical learning via the alternating direction method of multipliers. Now Pub- lishers Inc, 2011.
  7. [Buluc ¸et al., 2016] Aydın Buluc ¸, Henning Meyerhenke, Ilya Safro, and et al. Recent advances in graph partitioning. Algorithm engineering, pages 117-158, 2016.
  8. [Chen et al., 2018a] Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In ICML, pages 941-949, 2018.
  9. [Chen et al., 2018b] Jie Chen, Tengfei Ma, and Cao Xiao. Fastgcn: Fast learning with graph convolutional networks via importance sampling. In ICLR, 2018.
  10. [Chen et al., 2021] Tianlong Chen, Yongduo Sui, Xuxi Chen, and et al. A unified lottery ticket hypothesis for graph neural networks. In ICML, pages 1695-1706, 2021.
  11. [Cheng et al., 2017] Yu Cheng, Duo Wang, Pan Zhou, and Tao Zhang. A survey of model compression and ac- celeration for deep neural networks. arXiv preprint arXiv:1710.09282, 2017.
  12. [Chiang et al., 2019] Wei-Lin Chiang, Xuanqing Liu, Si Si, and et al. Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks. In SIGKDD, pages 257-266, 2019.
  13. [Eppstein et al., 1997] David Eppstein, Zvi Galil, Giuseppe F Italiano, and Amnon Nissenzweig. Spar- sification-a technique for speeding up dynamic graph algorithms. JACM, 44(5):669-696, 1997.
  14. [Fey and Lenssen, 2019] Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geomet- ric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
  15. [Hamilton et al., 2017] William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurIPS, pages 1025-1035, 2017.
  16. [Han et al., 2021] Li Han, Yan Mingyu, Lü Zhengyang, Li Wenming, Ye Xiaochun, Fan Dongrui, and Tang Zhimin. Survey on graph neural network acceleration ar- chitectures. Journal of Computer Research and Develop- ment, 58(6):1204, 2021.
  17. [He et al., 2020] Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang. Lightgcn: Simplifying and powering graph convolution network for recommendation. In SIGIR, pages 639-648, 2020.
  18. [Hinton et al., 2015] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in a neural network. arXiv preprint arXiv:1503.02531, 2015.
  19. [Hu et al., 2020a] Weihua Hu, Matthias Fey, Marinka Zit- nik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00687, 2020.
  20. [Hu et al., 2020b] Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. Heterogeneous graph transformer. In WWW, pages 2704-2710, 2020.
  21. [Huang et al., 2018] Wenbing Huang, Tong Zhang, Yu Rong, and et al. Adaptive sampling towards fast graph representation learning. Advances in Neural Information Processing Systems, 31:4558-4567, 2018.
  22. [Karypis and Kumar, 1998] George Karypis and Vipin Ku- mar. A fast and high quality multilevel scheme for parti- tioning irregular graphs. SIAM Journal on scientific Com- puting, 20(1):359-392, 1998.
  23. [Kipf and Welling, 2017] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
  24. [Lamb et al., 2020] Luís C. Lamb, Artur S. d'Avila Garcez, Marco Gori, Marcelo O. R. Prates, Pedro H. C. Avelar, and Moshe Y. Vardi. Graph neural networks meet neural- symbolic computing: A survey and perspective. In IJCAI, pages 4877-4884, 2020.
  25. [Li et al., 2020] Jiayu Li, Tianyun Zhang, Hao Tian, Sheng- min Jin, Makan Fardad, and Reza Zafarani. Sgcn: A graph sparsifier based on graph convolutional networks. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pages 275-287. Springer, 2020.
  26. [Li et al., 2021] Dongyue Li, Tao Yang, Lun Du, and et al. Adaptivegcn: Efficient gcn through adaptively sparsifying graphs. In CIKM, pages 3206-3210, 2021.
  27. [Lin et al., 2020] Zhiqi Lin, Cheng Li, Youshan Miao, and et al. Pagraph: Scaling gnn training on large graphs via computation-aware caching. In SoCC, pages 401-415, 2020.
  28. [Liu et al., 2021a] Tianfeng Liu, Yangrui Chen, Dan Li, and et al. Bgl: Gpu-efficient gnn training by optimiz- ing graph data i/o and preprocessing. arXiv preprint arXiv:2112.08541, 2021.
  29. [Liu et al., 2021b] Xin Liu, Mingyu Yan, Lei Deng, and et al. Sampling methods for efficient training of graph convolu- tional networks: A survey. IEEE/CAA Journal of Auto- matica Sinica, 9(2):205-234, 2021.
  30. [Liu et al., 2021c] Xin Liu, Mingyu Yan, Shuhan Song, and et al. Gnnsampler: Bridging the gap between sam- pling algorithms of gnn and hardware. arXiv preprint arXiv:2108.11571, 2021.
  31. [Mao et al., 2021] Kelong Mao, Jieming Zhu, Xi Xiao, Biao Lu, Zhaowei Wang, and Xiuqiang He. Ultragcn: Ultra simplification of graph convolutional networks for recom- mendation. In CIKM, pages 1253-1262, 2021.
  32. [Md et al., 2021] Vasimuddin Md, Sanchit Misra, Guixiang Ma, and et al. Distgnn: Scalable distributed training for large-scale graph neural networks. arXiv preprint arXiv:2104.06700, 2021.
  33. [Pope et al., 2019] Phillip E Pope, Soheil Kolouri, Moham- mad Rostami, Charles E Martin, and Heiko Hoffmann. Ex- plainability methods for graph convolutional neural net- works. In CVPR, pages 10772-10781, 2019.
  34. [Rong et al., 2020] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph con- volutional networks on node classification. In ICLR, 2020.
  35. [Scarselli et al., 2008] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008.
  36. [Srinivasa et al., 2020] Rakshith S Srinivasa, Cao Xiao, Lu- cas Glass, and et al. Fast graph attention networks us- ing effective resistance based graph sparsification. arXiv preprint arXiv:2006.08796, 2020.
  37. [Tailor et al., 2021] Shyam Anil Tailor, Javier Fernández- Marqués, and Nicholas Donald Lane. Degree-quant: Quantization-aware training for graph neural networks. In ICLR, 2021.
  38. [Veličković et al., 2018] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. ICLR, 2018.
  39. [Wang et al., 2019a] Minjie Wang, Da Zheng, Zihao Ye, and et al. Deep graph library: A graph-centric, highly- performant package for graph neural networks. arXiv preprint arXiv:1909.01315, 2019.
  40. [Wang et al., 2019b] Xiang Wang, Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng Chua. Neural graph col- laborative filtering. In SIGIR, pages 165-174, 2019.
  41. [Wang et al., 2021a] Junfu Wang, Yunhong Wang, Zhen Yang, and et al. Bi-gcn: Binary graph convolutional net- work. In CVPR, pages 1561-1570, 2021.
  42. [Wang et al., 2021b] Shoujin Wang, Liang Hu, Yan Wang, and et al. Graph learning based recommender systems: A review. In IJCAI, pages 4644-4652, 2021. IJCAI
  43. [Wu et al., 2019] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In ICML, pages 6861-6871, 2019.
  44. [Wu et al., 2020] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE TNNLS, 32(1):4-24, 2020.
  45. [Xu et al., 2019] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural net- works? In ICLR, 2019.
  46. [Yan et al., 2019] Mingyu Yan, Xing Hu, Shuangchen Li, Abanti Basak, Han Li, Xin Ma, Itir Akgun, Yujing Feng, Peng Gu, Lei Deng, et al. Alleviating irregularity in graph analytics acceleration: A hardware/software co-design ap- proach. In Proceedings of the 52nd Annual IEEE/ACM In- ternational Symposium on Microarchitecture, pages 615- 628, 2019.
  47. [Yan et al., 2020a] Bencheng Yan, Chaokun Wang, Gaoyang Guo, and Yunkai Lou. Tinygnn: Learning efficient graph neural networks. In SIGKDD, pages 1848-1856, 2020.
  48. [Yan et al., 2020b] Mingyu Yan, Zhaodong Chen, Lei Deng, Xiaochun Ye, Zhimin Zhang, Dongrui Fan, and Yuan Xie. Characterizing and understanding gcns on gpu. IEEE Computer Architecture Letters, 19(1):22-25, 2020.
  49. [Yan et al., 2020c] Mingyu Yan, Lei Deng, Xing Hu, and et al. Hygcn: A gcn accelerator with hybrid architec- ture. In 2020 IEEE International Symposium on High Per- formance Computer Architecture (HPCA), pages 15-29. IEEE, 2020.
  50. [Yang et al., 2020] Yiding Yang, Jiayan Qiu, Mingli Song, Dacheng Tao, and Xinchao Wang. Distilling knowledge from graph convolutional networks. In CVPR, pages 7074-7083, 2020.
  51. [Yang et al., 2021] Cheng Yang, Jiawei Liu, and Chuan Shi. Extract the knowledge of graph neural networks and go beyond it: An effective knowledge distillation framework. In WWW, pages 1227-1237, 2021.
  52. [Ying et al., 2019] Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Gener- ating explanations for graph neural networks. Advances in neural information processing systems, 32:9240, 2019.
  53. [Zeng et al., 2019] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Accu- rate, efficient and scalable graph embedding. In IPDPS, pages 462-471. IEEE, 2019.
  54. [Zeng et al., 2020] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- SAINT: Graph sampling based inductive learning method. In ICLR, 2020.
  55. [Zhang et al., 2019] Chuxu Zhang, Dongjin Song, Chao Huang, and et al. Heterogeneous graph neural network. In SIGKDD, pages 793-803, 2019.
  56. [Zhang et al., 2020] Ziwei Zhang, Peng Cui, and Wenwu Zhu. Deep learning on graphs: A survey. IEEE TKDE, 2020.
  57. [Zhang et al., 2021] Ziwei Zhang, Xin Wang, and Wenwu Zhu. Automated machine learning on graphs: A survey. In IJCAI, pages 4704-4712, 2021. IJCAI
  58. [Zhao et al., 2021] Tong Zhao, Yozen Liu, Leonardo Neves, and et al. Data augmentation for graph neural networks. In AAAI, pages 11015-11023, 2021.
  59. [Zheng et al., 2020a] Cheng Zheng, Bo Zong, Wei Cheng, and et al. Robust graph representation learning via neu- ral sparsification. In ICML, pages 11458-11468, 2020.
  60. [Zheng et al., 2020b] Da Zheng, Chao Ma, Minjie Wang, and et al. Distdgl: distributed graph neural network train- ing for billion-scale graphs. In 2020 IEEE/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3), pages 36-44, 2020.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards