学术讲座

大数据管理与分析方法研究北京市重点实验室（BDAI）研究生沙龙由中国人民大学高瓴人工智能智能学院与信息学院联合定期举行。本周BDAI重点实验室研讨会由信息学院博士生王涵之介绍自己的研究工作。欢迎同学们积极参与研讨！

报告人：王涵之，博士三年级

时间：2021年11月24日12:30-13:30

标题：Approximate Graph Propagation (通用图传播算法AGP)

摘要: Efficient computation of node proximity queries is of fundamental importance in various graph mining and learning tasks. In particular, several recent works leverage fast node proximity computation to improve the scalability of Graph Neural Networks (GNN). However, prior studies on proximity computation and GNN feature propagation are on a case-by-case basis, with each paper focusing on a particular proximity measure.

In this talk, I will introduce a unified randomized algorithm, AGP, which computes various proximity queries and GNN feature propagation with near-optimal time complexity, including transition probabilities, Personalized PageRank, heat kernel PageRank, Katz, SGC, GDC, and APPNP. The effectiveness of AGP is demonstrated in two concrete applications: local clustering with heat kernel PageRank and node classification with GNNs. The results show that AGP can significantly improve various existing GNN models' scalability without sacrificing prediction accuracy. Most notably, AGP extends the scalability of GNN to a billion-edge graph Papers100M, which is the largest publicly available GNN dataset so far.

(节点邻近度的高效计算在众多图挖掘和表示学习问题中都有着广泛的应用，例如社区发现、图神经网络应用中的节点分类问题等。但是，现有工作普遍只着眼于某一特定的邻近度指标，而缺乏一种通用算法以同时支持绝大多数节点邻近度指标的高效计算。本次报告将提供一种通用的图传播范式以归纳多种节点邻近度指标，并针对该通用范式提出一种可以高效计算绝大多数节点邻近度指标的算法AGP。AGP算法可以在近似最优的时间复杂度下完成所有符合该通用范式的邻近度指标的计算，例如Personalized PageRank (PPR)、Heat Kernel PageRank、transition probability、Katz、图神经网络中的特征传播过程等。此外，本次报告将以社区发现和图神经网络应用中的节点分类场景为例，借助大量的实验结果证明AGP算法的有效性。特别地，在以GNN为基础的节点分类问题中，AGP成功将多种GNN模型的支持数据大小扩展到了目前最大的公开数据集Papers100M，AGP可以在半小时内单机单卡完成Papers100M上的训练过程。)

欢迎同学们积极参会！