KDD 2021 | 时间复杂度接近最优的通用图传播算法

神经网络应用中的节点分类问题等。但是，现有工作普遍只着眼于某一特定的邻近度指标，而缺乏一种通用的算法以同时支持绝大多数节点邻近度指标的高效计算。本篇论文将多种节点邻近度指标归纳为一种通用的计算范式，针对该通用范式提出了一种可以高效计算绝大多数节点邻近度指标的算法AGP。通过严格的理论分析，我们证明了AGP算法可以在近似最优的时间复杂度下完成所有符合该通用范式的邻近度指标的计算，例如Personalized PageRank、Heat Kernel PageRank、transition probability、Katz、图神经网络中的特征传播过程等。

我们以社区发现和图神经网络应用中的节点分类场景为例，借助大量的实验证明了AGP算法的有效性。特别地，在以GNN为基础的节点分类问题中，AGP成功将多种GNN模型的支持数据大小扩展到了目前最大的公开数据集 Papers100M ，AGP可以在半小时内单机单卡完成Papers100M上的训练过程。

https://dl.acm.org/doi/abs/10.1145/3447548.3467243