Graph Neural Networks (GNN) is an emerging field for learning on
non-Euclidean data. Recently, there has been increased interest in designing
GNN that scales to large graphs. Most existing methods use "graph sampling" or
"layer-wise sampling" techniques to reduce training time. However, these
methods still suffer from degrading performance and scalability problems when
applying to graphs with billions of edges. This paper presents GBP, a scalable
GNN that utilizes a localized bidirectional propagation process from both the
feature vectors and the training/testing nodes. Theoretical analysis shows that
GBP is the first method that achieves sub-linear time complexity for both the
precomputation and the training phases. An extensive empirical study
demonstrates that GBP achieves state-of-the-art performance with significantly
less training/testing time. Most notably, GBP can deliver superior performance
on a graph with over 60 million nodes and 1.8 billion edges in less than half
an hour on a single machine. The codes of GBP can be found at
this https URL .

本文介绍了一种名为 GBP 的可扩展的 GNN，使用本地化的双向传播过程来实现高效的训练与测试，理论分析表明其是第一种在预计算和训练阶段都实现了次线性时间复杂度的方法，并在大规模图上取得了最先进的性能。