Scalable Graph Neural Networks via Bidirectional Propagation
  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
https://github.com/chennnM/GBP .
