大规模图神经网络系统综述
作者:
作者简介:

赵港(1997-),女,硕士,主要研究领域为分布式系统.
王千阁(1994-),男,博士生,主要研究领域为分布式图计算.
姚烽(1995-),男,博士生,主要研究领域为分布式图计算.
张岩峰(1982-),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为大数据处理和分布式系统.
于戈 (1962-),男,博士,教授,博士生导师,CCF会士,主要研究领域为数据库和分布式系统.

通讯作者:

张岩峰,zhangyf@mail.neu.edu.cn

基金项目:

国家重点研发计划 (2018YFB1003400); 国家自然科学基金(61672141, 62072082); 中央高校基本科研业务费(N181605017, N181604016)


Survey on Large-scale Graph Neural Network Systems
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [59]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    图神经网络(GNN)是一类基于深度学习的处理图域信息的方法, 它通过将图广播操作和深度学习算法结合, 可以让图的结构信息和顶点属性信息都参与到学习中, 在顶点分类、图分类、链接预测等应用中表现出良好的效果和可解释性, 已成为一种广泛应用的图分析方法. 然而现有主流的深度学习框架(如TensorFlow、PyTorch等)没有为图神经网络计算提供高效的存储支持和图上的消息传递支持, 这限制了图神经网络算法在大规模图数据上的应用. 目前已有诸多工作针对图结构的数据特点和图神经网络的计算特点, 探索了大规模图神经网络系统的设计和实现方案. 首先对图神经网络的发展进行简要概述, 总结了设计图神经网络系统需要面对的挑战; 随后对目前图神经网络系统的工作进行介绍, 从系统架构、编程模型、消息传递优化、图分区策略、通信优化等多个方面对系统进行分析; 最后使用部分已开源的图神经网络系统进行实验评估, 从精确度、性能、扩展性等多个方面验证这些系统的有效性.

    Abstract:

    Graph neural network (GNN) is used to process graph structure data based on deep learning techniques. It combines graph propagation operations with deep learning algorithms to fully utilize graph structure information and vertex features in the learning process. GNNs have been widely used in a range of applications, such as node classification, graph classification, and link prediction, showing promised effectiveness and interpretability. However, the existing deep learning frameworks (such as TensorFlow and PyTorch) do not provide efficient storage support and message passing support for GNN’s training, which limits its usage on large-scale graph data. At present, a number of large-scale GNN systems have been designed by considering the data characteristics of graph structure and the computational characteristics of GNNs. This study first briefly reviews the GNNs, and summarizes the challenges that need to be faced in designing GNN systems. Then, the existing work on GNN training systems is reviewed, and these systems are analyzed from multiple aspects such as system architecture, programming model, message passing optimization, graph partitioning strategy and communication optimization. Finally, several open source GNN systems are chosen for experimental evaluation to compare these systems in terms of accuracy, efficiency, and scalability.

    参考文献
    [1] Redmon J, Divvala S, Girshick R, Farhadi A. You only look once: Unified, real-time object detection. In: Proc. of the 2016 IEEE Conf. on Computer Vision and Pattern Recognition. Las Vegas: IEEE, 2016. 779–788. [doi: 10.1109/CVPR.2016.91]
    [2] Ren SQ, He KM, Girshick R, Sun J. Faster R-CNN: Towards real-time object detection with region proposal networks. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2017, 39(6): 1137–1149. [doi: 10.1109/TPAMI.2016.2577031
    [3] Luong MT, Pham H, Manning CD. Effective approaches to attention-based neural machine translation. In: Proc. of the 2015 Conf. on Empirical Methods in Natural Language Processing. Lisbon: Association for Computational Linguistics, 2015. 1412–1421. [doi: 10.18653/v1/D15-1166]
    [4] Wu YH, Schuster M, Chen ZF, et al. Google’s neural machine translation system: Bridging the gap between human and machine translation. arXiv: 1609.08144, 2016.
    [5] Hinton G, Deng L, Yu D, Dahl GE, Mohamed AR, Jaitly N, Senior A, Vanhoucke V, Nguyen P, Sainath TN, Kingsbury B. Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups. IEEE Signal Processing Magazine, 2012, 29(6): 82–97. [doi: 10.1109/MSP.2012.2205597
    [6] Sanchez-Gonzalez A, Heess N, Springenberg JT, Merel J, Riedmiller M, Hadsell R, Battaglia P. Graph networks as learnable physics engines for inference and control. In: Proc. of the 35th Int’l Conf. on Machine Learning. Stockholm: PMLR, 2018. 4470–4479.
    [7] Battaglia PW, Pascanu R, Lai M, Rezende DJ, Kavukcuoglu K. Interaction networks for learning about objects, relations and physics. In: Proc. of the 30th Int’l Conf. on Neural Information Processing Systems. Barcelona: NIPS, 2016. 4509–4517. [doi: 10.5555/3157382.3157601]
    [8] Hamilton WL, Ying R, Leskovec J. Representation learning on graphs: Methods and applications. IEEE Data Engineering Bulletin, 2017, 40(1): 52–74
    [9] Brandes U, Gaertler M, Wagner D. Experiments on graph clustering algorithms. In: Proc. of the 11th European Symp. on Algorithms. Budapest: Springer, 2003. 568–579. [doi: 10.1007/978-3-540-39658-1_52]
    [10] Fout A, Byrd J, Shariat B, Ben-Hur A. Protein interface prediction using graph convolutional networks. In: Proc. of the 31st Int’l Conf. on Neural Information Processing Systems. Long Beach: NIPS, 2017. 6533–6542. [doi: 10.5555/3295222.3295399]
    [11] Jeong C, Jang S, Park E, Choi S. A context-aware citation recommendation model with BERT and graph convolutional networks. Scientometrics, 2020, 124(3): 1907–1922. [doi: 10.1007/s11192-020-03561-y
    [12] Ribeiro LFR, Saverese PHP, Figueiredo DR. struc2vec: Learning node representations from structural identity. In: Proc. of the 23rd ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. Halifax: ACM, 2017. 385–394. [doi: 10.1145/3097983.3098061]
    [13] Kipf TN, Welling M. Semi-supervised classification with graph convolutional networks. In: Proc. of the 5th Int’l Conf. on Learning Representations. Toulon: OpenReview.net, 2017.
    [14] Chen J, Ma TF, Xiao C. FastGCN: Fast learning with graph convolutional networks via importance sampling. In: Proc. of the 6th Int’l Conf. on Learning Representations. Vancouver: OpenReview.net, 2018.
    [15] Huang X, Li JD, Hu X. Accelerated attributed network embedding. In: Proc. of the 2017 SIAM Int’l Conf. on Data Mining. Houston: SIAM, 2017. 633–641. [doi: 10.1137/1.9781611974973.71]
    [16] Hamilton WL, Ying R, Leskovec J. Inductive representation learning on large graphs. In: Proc. of the 31st Int’l Conf. on Neural Information Processing Systems. Long Beach: NIPS, 2017. 1025–1035. [doi: 10.5555/3294771.3294869]
    [17] Wang ZQ, Tan YW, Zhang M. Graph-based recommendation on social networks. In: Proc. of the 2010 12th Int’l Asia-Pacific Web Conf. Busan: IEEE, 2010. 116–122. [doi: 10.1109/APWeb.2010.60]
    [18] Hamaguchi T, Oiwa H, Shimbo M, Matsumoto Y. Knowledge transfer for out-of-knowledge-base entities: A graph neural network approach. In: Proc. of the 26th Int’l Joint Conf. on Artificial Intelligence. Melbourne: IJCAI.org, 2017. 1802–1808. [doi: 10.24963/ijcai.2017/250]
    [19] Liben-Nowell D, Kleinberg J. The link-prediction problem for social networks. Journal of the American Society for Information Science and Technology, 2007, 58(7): 1019–1031. [doi: 10.1002/asi.20591
    [20] Abadi M, Barham P, Chen JM, et al. TensorFlow: A system for large-scale machine learning. In: Proc. of the 12th USENIX Conf. on Operating Systems Design and Implementation. Savannah: USENIX Association, 2016. 265–283. [doi: 10.5555/3026877.3026899]
    [21] PyTorch. http://pytorch.org.
    [22] Chen TQ, Li M, Li YT, Lin M, Wang NY, Wang MJ, Xiao TJ, Xu B, Zhang CY, Zhang Z. MXNet: A flexible and efficient machine learning library for heterogeneous distributed systems. arXiv: 1512.01274, 2015.
    [23] Yu D, Eversole A, Seltzer ML, Yao KS, Guenter B, Kuchaiev O, Seide F, Wang HM, Droppo J, Huang ZH, Zweig G, Rossbach CJ, Currey J. An introduction to computational networks and the computational network toolkit. In: Proc. of the 15th Annual Conf. of the Int’l Speech Communication Association. Singapore: ISCA, 2014.
    [24] Chen R, Shi JX, Chen YZ, Zang BY, Guan HB, Chen HB. PowerLyra: Differentiated graph computation and partitioning on skewed graphs. ACM Trans. on Parallel Computing, 2018, 5(3): 13. [doi: 10.1145/3298989
    [25] Gonzalez JE, Low Y, Gu HJ, Bickson D, Guestrin C. Powergraph: Distributed graph-parallel computation on natural graphs. In: Proc. of the 10th USENIX Symp. on Operating Systems Design and Implementation. Hollywood: USENIX Association, 2012. 17–30.
    [26] Low Y, Bickson D, Gonzalez J, Guestrin C, Kyrola A, Hellerstein JM. Distributed graphlab: A framework for machine learning and data mining in the cloud. Proc. of the VLDB Endowment, 2012, 5(8): 716–727. [doi: 10.14778/2212351.2212354
    [27] Malewicz G, Austern MH, Bik AJC, Dehnert JC, Horn I, Leiser N, Czajkowski GJ. Pregel: A system for large-scale graph processing. In: Proc. of the 2010 ACM SIGMOD Int’l Conf. on Management of Data. Indianapolis: ACM, 2010. 135–146. [doi: 10.1145/1807167.1807184]
    [28] Xiao WC, Xue JL, Miao YS, Li Z, Chen C, Wu M, Li W, Zhou LD. Tux2: Distributed graph computation for machine learning. In: Proc. of the 14th USENIX Conf. on Networked Systems Design and Implementation. Boston: USENIX Association, 2017. 669–682. [doi: 10.5555/3154630.3154684]
    [29] Scarselli F, Gori M, Tsoi AC, Hagenbuchner M, Monfardini G. The graph neural network model. IEEE Trans. on Neural Networks, 2009, 20(1): 61–80. [doi: 10.1109/TNN.2008.2005605
    [30] Gallicchio C, Micheli A. Graph echo state networks. In: Proc. of the 2010 Int’l Joint Conf. on Neural Networks. Barcelona: IEEE, 2010. 1–8. [doi: 10.1109/IJCNN.2010.5596796]
    [31] LeCun Y, Bengio Y. Convolutional networks for images, speech, and time series. In: Arbib MA, ed. Handbook of Brain Theory and Neural Networks. Cambridge: MIT Press, 1995.
    [32] LeCun Y, Bengio Y, Hinton G. Deep learning. Nature, 2015, 521(7553): 436–444. [doi: 10.1038/nature14539
    [33] Li RY, Wang S, Zhu FY, Huang JZ. Adaptive graph convolutional neural networks. In: Proc. 32nd AAAI Conf. on Artificial Intelligence, the 30th Innovative Applications of Artificial Intelligence, the 8th AAAI Symp. on Educational Advances in Artificial Intelligence. New Orleans: AAAI, 2018. 3546–3553.
    [34] Defferrard M, Bresson X, Vandergheynst P. Convolutional neural networks on graphs with fast localized spectral filtering. Proc. of the 30th Int’l Conf. on Neural Information Processing Systems. Barcelona: NIPS, 2016. 3844–3852. [doi: 10.5555/3157382.3157527]
    [35] Levie R, Monti F, Bresson X, Bronstein MM. Cayleynets: Graph convolutional neural networks with complex rational spectral filters. IEEE Trans. on Signal Processing, 2019, 67(1): 97–109. [doi: 10.1109/TSP.2018.2879624
    [36] Gilmer J, Schoenholz SS, Riley PF, Vinyals O, Dahl GE. Neural message passing for quantum chemistry. In: Proc. of the 34th Int’l Conf. on Machine Learning. Sydney: PMLR, 2017. 1263–1272.
    [37] Velickovic P, Cucurull G, Casanova A, Romero A, Liò P, Bengio Y. Graph attention networks. arXiv: 1710.10903, 2017.
    [38] Li YJ, Vinyals O, Dyer C, Pascanu R, Battaglia P. Learning deep generative models of graphs. arXiv: 1803.03324, 2018.
    [39] You JX, Ying R, Ren X, Hamilton W, Leskovec J. GraphRNN: Generating realistic graphs with deep auto-regressive models. In: Proc. of the 35th Int’l Conf. on Machine Learning. Stockholm: PMLR, 2018. 5708–5717.
    [40] Wu ZH, Pan SR, Long GD, Zhang CQ. Graph waveNet for deep spatial-temporal graph modeling. In: Proc. of the 28th Int’l Joint Conf. on Artificial Intelligence. Macao: IJCAI.org, 2019. 1907–1913. [DOI: 10.24963/ijcai.2019/264]
    [41] Guo SN, Lin YF, Feng N, Song C, Wan HY. Attention based spatial-temporal graph convolutional networks for traffic flow forecasting. In: Proc. of the 33rd AAAI Conf. on Artificial Intelligence, 31st Conf. on Innovative Applications of Artificial Intelligence, the 9th Symp. on Educational Advances in Artificial Intelligence. Honolulu: AAAI, 2019. 922–929. [doi: 10.1609/aaai.v33i01.3301922]
    [42] Cai HY, Zheng VW, Chang KCC. A comprehensive survey of graph embedding: Problems, techniques, and applications. IEEE Trans. on Knowledge and Data Engineering, 2018, 30(9): 1616–1637. [doi: 10.1109/TKDE.2018.2807452
    [43] Cui P, Wang X, Pei J, Zhu WW. A survey on network embedding. IEEE Trans. on Knowledge and Data Engineering, 2019, 31(5): 833–852. [doi: 10.1109/TKDE.2018.2849727
    [44] Goyal P, Ferrara E. Graph embedding techniques, applications, and performance: A survey. Knowledge-based Systems, 2018, 151: 78–94. [doi: 10.1016/j.knosys.2018.03.022
    [45] Wu ZH, Pan SR, Chen FW, Long GD, Zhang CQ, Yu PS. A comprehensive survey on graph neural networks. IEEE Trans. on Neural Networks and Learning Systems, 2021, 32(1): 4–24. [doi: 10.1109/TNNLS.2020.2978386
    [46] Zhou J, Cui GQ, Hu SD, Zhang ZY, Yang C, Liu ZY, Wang LF, Li CC, Sun MS. Graph neural networks: A review of methods and applications. arXiv: 1812.08434, 2018.
    [47] Wang MJ, Yu LF, Zheng D, Gan Q, Gai Y, Ye ZH, Li MF, Zhou JJ, Huang Q, Ma C, Huang ZY, Guo QP, Zhang H, Lin HB, Zhao JB, Li JY, Smola A, Zhang Z. Deep graph library: Towards efficient and scalable deep learning on graphs. arXiv: 1909.01315, 2019.
    [48] Fey M, Lenssen JE. Fast graph representation learning with PyTorch Geometric. arXiv: 1903.02428, 2019.
    [49] Ma LX, Yang Z, Miao YS, Xue JL, Wu M, Zhou LD, Dai YF. Neugraph: Parallel deep neural network computation on large graphs. In: Proc. of the 2019 USENIX Annual Technical Conf. Renton: USENIX Association, 2019. 443–458.
    [50] Liang SW, Wang Y, Liu C, He L, Li HW, Xu DW, Li XW. EnGN: A high-throughput and energy-efficient accelerator for large graph neural networks. IEEE Trans. on Computers, 2020. [doi: 10.1109/TC.2020.3014632
    [51] A graph system developed by Alibaba. https://github.com/alibaba/euler
    [52] Jiang JW, Xiao P, Yu LL, Cheng JF, Miao XP, Zhang ZP, Cui B. PSGraph: How Tencent trains extremely large-scale graphs with Spark? In: Proc. of the 2020 IEEE 36th Int’l Conf. on Data Engineering. Dallas: IEEE, 2020. 1549–1557. [doi: 10.1109/ICDE48307.2020.00137]
    [53] Zhu R, Zhao K, Yang HX, Lin W, Zhou C, Ai BL, Li Y, Zhou JG. Aligraph: A comprehensive graph neural network platform. Proc. of the VLDB Endowment, 2019, 12(12): 2094–2105. [doi: 10.14778/3352063.3352127
    [54] Jia ZH, Lin SN, Gao MY, Zaharia M, Aiken A. Improving the accuracy, scalability, and performance of graph neural networks with roc. In: Proc. of the Machine Learning and Systems. Austin: MLSys, 2020. 187–198.
    [55] Zhang DL, Huang X, Liu ZQ, Hu ZY, Song XZ, Ge ZB, Zhang ZQ, Wang L, Zhou J, Shuang Y, Qi Y. AGL: A scalable system for industrial-purpose graph machine learning. arXiv: 2003.02454, 2020.
    [56] https://github.com/PaddlePaddle/PGL
    [57] Zhou J, Li XL, Zhao PL, Chen CC, Li LF, Yang XX, Cui Q, Yu J, Chen X, Ding Y, Qi YA. Kunpeng: Parameter server based distributed learning systems and its applications in alibaba and ant financial. In: Proc. of the 23rd ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. Halifax: ACM, 2017. 1693–1702. [doi: 10.1145/3097983.3098029]
    [58] Sen P, Namata G, Bilgic M, Getoor L, Galligher B, Eliassi-Rad T. Collective classification in network data. AI Magazine, 2008, 29(3): 93. [doi: 10.1609/aimag.v29i3.2157
    [59] http://snap.stanford.edu/data/web-Stanford.html
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

赵港,王千阁,姚烽,张岩峰,于戈.大规模图神经网络系统综述.软件学报,2022,33(1):150-170

复制
分享
文章指标
  • 点击次数:7129
  • 下载次数: 15705
  • HTML阅读次数: 8452
  • 引用次数: 0
历史
  • 收稿日期:2020-10-13
  • 最后修改日期:2020-12-21
  • 在线发布日期: 2021-02-07
  • 出版日期: 2022-01-06
文章二维码
您是第20540962位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号