Scalable Graph Neural Networks via Bidirectional Propagation

Abstract

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 .

arXiv commentNeurIPS 2020

References in corpus (18)

• Inductive Representation Learning on Large Graphs
• Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks
• Simplifying Graph Convolutional Networks
• Representation Learning on Graphs with Jumping Knowledge Networks
• DropEdge: Towards Deep Graph Convolutional Networks on Node Classification
• DeepInf: Social Influence Prediction with Deep Learning
• FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling
• Scaling Graph Neural Networks with Approximate PageRank
• MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing
• Attention-based Graph Neural Network for Semi-supervised Learning
• PairNorm: Tackling Oversmoothing in GNNs
• Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks
• Multi-Label Image Recognition with Graph Convolutional Networks
• Efficient Estimation of Heat Kernel PageRank for Local Clustering
• Graph Star Net for Generalized Multi-Task Learning
• Heterogeneous Network Representation Learning: A Unified Framework with Survey and Benchmark
• Optimizing Generalized PageRank Methods for Seed-Expansion Community Detection
• Fast Bidirectional Probability Estimation in Markov Models

Cited by in corpus (9)

• Graph Attention Multi-Layer Perceptron
• PaSca: a Graph Neural Architecture Search System under the Scalable Paradigm
• Approximate Graph Propagation
• Model Degradation Hinders Deep Graph Neural Networks
• RPT: Toward Transferable Model on Heterogeneous Researcher Data via Pre-Training
• Edge-based Local Push for Personalized PageRank
• Boosting Multitask Learning on Graphs through Higher-Order Task Affinities
• Fast and Effective GNN Training through Sequences of Random Path Graphs
• Scalable Deep Graph Clustering with Random-walk based Self-supervised Learning