Predict then Propagate: Graph Neural Networks meet Personalized PageRank
Johannes Gasteiger, Aleksandar Bojchevski、Stephan Günnemann Technical University of Munich, Germany
Abstract
Neural message passing algorithms for semi-supervised classification on graphs have recently achieved great success. However, for classifying a node these methods only consider nodes that are a few propagation steps away and the size of this utilized neighborhood is hard to extend. In this paper, we use the relationship between graph convolutional networks (GCN) and PageRank to derive an improved propagation scheme based on personalized PageRank. We utilize this propagation procedure to construct a simple model, personalized propagation of neural predictions (PPNP), and its fast approximation, APPNP. Our model’s training time is on par or faster and its number of parameters on par or lower than previous models. It leverages a large, adjustable neighborhood for classification and can be easily combined with any neural network. We show that this model outperforms several recently proposed methods for semi-supervised classification in the most thorough study done so far for GCN-like models. Our implementation is available online. 111https://www.kdd.in.tum.de/ppnp
中文速览
图神经网络在半监督节点分类任务中表现出色，但现有的消息传递方法（如图卷积网络GCN）存在一个根本缺陷：随着传播层数增加，节点表示会过度平滑，导致每个节点的"个性"消失，因此实际上只能利用极小范围的邻域信息。本文揭示了GCN与PageRank之间的内在联系，并以此为基础，提出了一种基于个性化PageRank（Personalized PageRank）的新传播方案——PPNP及其快速近似版本APPNP：核心思路是将神经网络生成预测与图上的信息传播彻底分离，先用神经网络独立处理每个节点的特征得到初步预测，再通过带"回传"概率的个性化PageRank迭代扩散这些预测，从而在保留局部邻域信息的同时，可以灵活地聚合任意大范围的图结构信息。实验结果表明，APPNP在多个基准数据集上的半监督分类精度超过了此前的主流方法，同时参数量更少、训练速度更快，计算复杂度仅与边数成线性关系。这项工作的意义在于从根本上解耦了"用多深的网络"和"看多大范围邻居"这两个原本相互绑定的问题，为图学习模型的设计提供了更灵活、更高效的新思路。
原文 arXiv:1810.05997;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1810.05997v6