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

作者：顾希之; 邵蓥侠^*

来源：计算机科学, 2023, 50(01): 52-58.

• 图神经网络
• 计算图精简
• 共同邻居
• 冗余计算
• 剪枝

计算图精简是提升图神经网络(Graph Neural Network, GNN)模型训练速度的一种优化技术，它利用节点间存在共同邻居的特性，通过消除聚合阶段的冗余计算，来加速图神经网络模型的训练。但是，在处理大规模图数据时，已有的计算图精简技术存在计算效率低的问题，影响了计算图精简技术在大规模图神经网络中的应用。文中详细分析了当前的计算图精简技术，统计了包括搜索和重构两阶段处理的时间开销，并总结了现有方法的不足。在此基础上，提出了基于影响力剪枝的图神经网络快速计算图精简算法。该算法应用影响力模型刻画各个节点对计算图精简的贡献，并基于影响力对共同邻居的搜索空间进行剪枝，极大地提升了搜索阶段的效率。此外，详细分析了算法复杂度，从理论上证明了该技术期望的加速效果。最后，为验证所提算法的有效性，将所提算法应用到两种主流的计算图精简技术上，选取常见的图神经网络模型在多个数据集上进行测试，实验结果表明所提算法在保证一定冗余计算去除量的前提下，能够显著地提升计算图精简的效率。相比基线计算图精简技术，所提技术在PPI数据集上搜索阶段的加速效果最高提升了3.4倍，全过程最高提升了1.6倍；在Reddit数据集上搜索阶段的加速效果最高提升了5.1倍，全过程最高提升了3.2倍。

• 单位
  北京邮电大学