计算机科学 ›› 2023, Vol. 50 ›› Issue (1): 52-58.doi: 10.11896/jsjkx.220900032
顾希之, 邵蓥侠
GU Xizhi, SHAO Yingxia
摘要： 计算图精简是提升图神经网络(Graph Neural Network,GNN)模型训练速度的一种优化技术,它利用节点间存在共同邻居的特性,通过消除聚合阶段的冗余计算,来加速图神经网络模型的训练。但是,在处理大规模图数据时,已有的计算图精简技术存在计算效率低的问题,影响了计算图精简技术在大规模图神经网络中的应用。文中详细分析了当前的计算图精简技术,统计了包括搜索和重构两阶段处理的时间开销,并总结了现有方法的不足。在此基础上,提出了基于影响力剪枝的图神经网络快速计算图精简算法。该算法应用影响力模型刻画各个节点对计算图精简的贡献,并基于影响力对共同邻居的搜索空间进行剪枝,极大地提升了搜索阶段的效率。此外,详细分析了算法复杂度,从理论上证明了该技术期望的加速效果。最后,为验证所提算法的有效性,将所提算法应用到两种主流的计算图精简技术上,选取常见的图神经网络模型在多个数据集上进行测试,实验结果表明所提算法在保证一定冗余计算去除量的前提下,能够显著地提升计算图精简的效率。相比基线计算图精简技术,所提技术在PPI数据集上搜索阶段的加速效果最高提升了3.4倍,全过程最高提升了1.6倍;在Reddit数据集上搜索阶段的加速效果最高提升了5.1倍,全过程最高提升了3.2倍。
中图分类号:
| [1]GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826. [2]KIPF T N,WELLING M.Semi-supervised classification withgraph convolutional networks[J].arXiv:1609.02907,2016. [3]VELIČKOVIĆ P,CUCURULL G,CASANOVA A,et al.Graph attention networks[J].arXiv:1710.10903,2017. [4]XU K,HU W,LESKOVEC J,et al.How powerful are graph neural networks?[J].arXiv:1810.00826,2018. [5]HAMILTON W,YING Z,LESKOVEC J.Inductive representation learning on large graphs[C]//Advances in Neural Information Processing Systems.2017:1025-1035. [6]CHEN J,MA T,XIAO C.Fastgcn:fast learning with graph convolutional networks via importance sampling[J].arXiv:1801.10247,2018. [7]ZOU D,HU Z,WANG Y,et al.Layer-dependent importance sampling for training deep and large graph convolutional networks[C]//Advances in Neural Information Processing Systems.2019:11249-11259. [8]ZENG H,ZHOU H,SRIVASTAVA A,et al.Graphsaint:Graph sampling based inductive learning method[J].arXiv:1907.04931,2019. [9]CHIANG W L,LIU X,SI S,et al.Cluster-gcn:An efficient algorithm for training deep and large graph convolutional networks[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.2019:257-266. [10]WU F,SOUZA A,ZHANG T,et al.Simplifying graph convolutional networks[C]//International Conference on Machine Learning.PMLR,2019:6861-6871. [11]BOJCHEVSKI A,KLICPERA J,PEROZZI B,et al.Scalinggraph neural networks with approximate pagerank[C]//Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.2020:2464-2473. [12]ZHU R,ZHAO K,YANG H,et al.Aligraph:a comprehensive graph neural network platform[J].arXiv:1902.08730,2019. [13]CHEN X,WANG Y,XIE X,et al.Rubik:A hierarchical architecture for efficient graph neural network training[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2021,41(4):936-949. [14]JIA Z,LIN S,YING R,et al.Redundancy-free computation for graph neural networks[C]//Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.2020:997-1005. [15]ZENG H,PRASANNA V.GraphACT:Accelerating GCN training on CPU-FPGA heterogeneous platforms[C]//Proceedings of the 2020 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays.2020:255-265. [16]FEY M,LENSSEN J E.Fast graph representation learning with PyTorch Geometric[J].arXiv:1903.02428,2019. |
| [1] | 郝敬宇, 文静轩, 刘华锋, 景丽萍, 于剑. 结合全局信息的深度图解耦协同过滤 Deep Disentangled Collaborative Filtering with Graph Global Information 计算机科学, 2023, 50(1): 41-51. https://doi.org/10.11896/jsjkx.220900255 |
| [2] | 蒲金垚, 卜令梅, 卢永美, 叶子铭, 陈黎, 于中华. 利用异构图神经网络实现情绪-原因对的有效抽取 Utilizing Heterogeneous Graph Neural Network to Extract Emotion-Cause Pairs Effectively 计算机科学, 2023, 50(1): 205-212. https://doi.org/10.11896/jsjkx.211100265 |
| [3] | 周芳泉, 成卫青. 基于全局增强图神经网络的序列推荐 Sequence Recommendation Based on Global Enhanced Graph Neural Network 计算机科学, 2022, 49(9): 55-63. https://doi.org/10.11896/jsjkx.210700085 |
| [4] | 闫佳丹, 贾彩燕. 基于双图神经网络信息融合的文本分类方法 Text Classification Method Based on Information Fusion of Dual-graph Neural Network 计算机科学, 2022, 49(8): 230-236. https://doi.org/10.11896/jsjkx.210600042 |
| [5] | 齐秀秀, 王佳昊, 李文雄, 周帆. 基于概率元学习的矩阵补全预测融合算法 Fusion Algorithm for Matrix Completion Prediction Based on Probabilistic Meta-learning 计算机科学, 2022, 49(7): 18-24. https://doi.org/10.11896/jsjkx.210600126 |
| [6] | 杨炳新, 郭艳蓉, 郝世杰, 洪日昌. 基于数据增广和模型集成策略的图神经网络在抑郁症识别上的应用 Application of Graph Neural Network Based on Data Augmentation and Model Ensemble in Depression Recognition 计算机科学, 2022, 49(7): 57-63. https://doi.org/10.11896/jsjkx.210800070 |
| [7] | 熊中敏, 舒贵文, 郭怀宇. 融合用户偏好的图神经网络推荐模型 Graph Neural Network Recommendation Model Integrating User Preferences 计算机科学, 2022, 49(6): 165-171. https://doi.org/10.11896/jsjkx.210400276 |
| [8] | 邓朝阳, 仲国强, 王栋. 基于注意力门控图神经网络的文本分类 Text Classification Based on Attention Gated Graph Neural Network 计算机科学, 2022, 49(6): 326-334. https://doi.org/10.11896/jsjkx.210400218 |
| [9] | 余皑欣, 冯秀芳, 孙静宇. 结合物品相似性的社交信任推荐算法 Social Trust Recommendation Algorithm Combining Item Similarity 计算机科学, 2022, 49(5): 144-151. https://doi.org/10.11896/jsjkx.210300217 |
| [10] | 李勇, 吴京鹏, 张钟颖, 张强. 融合快速注意力机制的节点无特征网络链路预测算法 Link Prediction for Node Featureless Networks Based on Faster Attention Mechanism 计算机科学, 2022, 49(4): 43-48. https://doi.org/10.11896/jsjkx.210800276 |
| [11] | 曹合心, 赵亮, 李雪峰. 图神经网络在Text-to-SQL解析中的技术研究 Technical Research of Graph Neural Network for Text-to-SQL Parsing 计算机科学, 2022, 49(4): 110-115. https://doi.org/10.11896/jsjkx.210200173 |
| [12] | 苗旭鹏, 周跃, 邵蓥侠, 崔斌. GSO:基于图神经网络的深度学习计算图子图替换优化框架 GSO:A GNN-based Deep Learning Computation Graph Substitutions Optimization Framework 计算机科学, 2022, 49(3): 86-91. https://doi.org/10.11896/jsjkx.210700199 |
| [13] | 杨旭华, 金鑫, 陶进, 毛剑飞. 基于图神经网络和依存句法分析的文本分类 Text Classification Based on Graph Neural Networks and Dependency Parsing 计算机科学, 2022, 49(12): 293-300. https://doi.org/10.11896/jsjkx.220300195 |
| [14] | 孙开伟, 刘松, 杜雨露. 基于属性图注意力网络的电影推荐模型 Movie Recommendation Model Based on Attribute Graph Attention Network 计算机科学, 2022, 49(11A): 211100106-8. https://doi.org/10.11896/jsjkx.211100106 |
| [15] | 李宝珍, 张晋, 王宝录, 余平. 融合多层次视觉信息的人物交互动作识别 Human-Object Interaction Recognition Integrating Multi-level Visual Features 计算机科学, 2022, 49(11A): 220700012-8. https://doi.org/10.11896/jsjkx.220700012 |
|
||
首页