基于影响力剪枝的图神经网络快速计算图精简  

Fast Computation Graph Simplification via Influence-based Pruning for Graph Neural Network

作　　者：顾希之 邵蓥侠 GU Xizhi;SHAO Yingxia(School of Computer Science,Beijing University of Posts and Telecommunications,Beijing 100876,China)

机构地区：[1]北京邮电大学计算机学院(国家示范性软件学院),北京100876

出　　处：《计算机科学》2023年第1期52-58,共7页Computer Science

基　　金：国家自然科学基金(62272054,U1936104,62192784)。

摘　　要：计算图精简是提升图神经网络(Graph Neural Network,GNN)模型训练速度的一种优化技术,它利用节点间存在共同邻居的特性,通过消除聚合阶段的冗余计算,来加速图神经网络模型的训练。但是,在处理大规模图数据时,已有的计算图精简技术存在计算效率低的问题,影响了计算图精简技术在大规模图神经网络中的应用。文中详细分析了当前的计算图精简技术,统计了包括搜索和重构两阶段处理的时间开销,并总结了现有方法的不足。在此基础上,提出了基于影响力剪枝的图神经网络快速计算图精简算法。该算法应用影响力模型刻画各个节点对计算图精简的贡献,并基于影响力对共同邻居的搜索空间进行剪枝,极大地提升了搜索阶段的效率。此外,详细分析了算法复杂度,从理论上证明了该技术期望的加速效果。最后,为验证所提算法的有效性,将所提算法应用到两种主流的计算图精简技术上,选取常见的图神经网络模型在多个数据集上进行测试,实验结果表明所提算法在保证一定冗余计算去除量的前提下,能够显著地提升计算图精简的效率。相比基线计算图精简技术,所提技术在PPI数据集上搜索阶段的加速效果最高提升了3.4倍,全过程最高提升了1.6倍;在Reddit数据集上搜索阶段的加速效果最高提升了5.1倍,全过程最高提升了3.2倍。Computation graph simplification is a kind of optimization technique to improve the training speed of graph neural network models.It uses the characteristics of common neighbors among nodes and speeds up the training of graph neural network models by eliminating redundant computation in the stage of aggregation.However,when dealing with large-scale graph data,the existing computation graph simplification techniques suffer from the problem of low computation efficiency,which affects the application of computation graph simplification in large-scale graph neural networks.This paper analyzes the current techniques of computation graph simplification in detail by counting the overhead of two phases including searching and reconstruction,and summarizes the shortcomings of existing techniques.On this basis,it proposes an algorithm of fast computation graph simplification via influence-based pruning for graph neural network.This algorithm applies an influence model to describe the contribution of each node to the computation graph simplification and prunes the searching space of common neighbors based on influence,which greatly improves the efficiency of the phase of searching.In addition,this paper analyzes the algorithm complexity and theoretically proves the expected acceleration effect of this technique.Finally,in order to verify the effectiveness of this novel algorithm,the algorithm is applied to two mainstream computation graph simplification technique,and common graph neural network models areselected to test on some data sets.Experimental results demonstrate that the novel algorithm can significantly improve the efficiency of the computation graph simplification on the premise of ensuring a certain amount of redundant computation reduction.Compared with the baseline of computation graph simplification,the proposed technique can speed up to 3.4 times in searching phase and speed up to 1.6 times on the whole process on PPI dataset,while it can speed up to 5.1 times in searching phase and speed up to 3.2 times on

关 键 词：图神经网络 计算图精简 共同邻居 冗余计算 剪枝 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]