Source-linked AI summary
Scalable Graph Neural Networks via Bidirectional Propagation
Ming Chen, Zhewei Wei, Bolin Ding, Yaliang Li, Ye Yuan, Xiaoyong Du, Ji-Rong Wen
TL;DR
Existing scalable GNN methods struggle to combine large-graph scalability with reliable performance, especially on billion-edge graphs. GBP uses localized bidirectional propagation from feature vectors and training/testing nodes, achieving sub-linear complexity and strong empirical performance, including billion-edge execution on one machine.
Problem
Existing graph- and layer-wise sampling methods reduce training time but still face performance and scalability problems on graphs with billions of edges.
Method
GBP performs localized bidirectional propagation from feature vectors and training/testing nodes to produce representations that can be trained with mini-batches.
Results
GBP achieves sub-linear complexity for precomputation, training, and inference while improving efficiency and performance across real-world graphs, including billion-edge networks on a single machine.
Takeaways & Limitations
GBP provides a scalable GNN that extends empirical evaluation to billion-edge networks while retaining strong performance and lower running time than existing methods.
Takeaways & Limitations
The reverse-push approximation can be biased, and estimating representations through random walks from every training node is infeasible for fully supervised training on large graphs.
Abstract
from arXiv · showhide
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 .
1 Introduction
GNN scalability is limited by full-batch memory demands, rapidly expanding neighborhoods, and existing methods’ inability to provide reliable billion-edge performance. GBP addresses these problems through localized bidirectional propagation and reports sub-linear complexity with strong empirical scalability.
- Full-batch GCN stores every node representation in GPU memory, limiting scalability, while mini-batch neighborhoods can grow exponentially with depth.
- Existing scalable GNN methods reduce training time through layer-wise sampling, graph sampling, or related propagation strategies.
- Existing methods remain linear in the number of edges, can perform poorly on semi-supervised tasks, and lack reliable performance on billion-scale graphs.
- GBP propagates locally from both feature vectors and training/testing nodes, producing unbiased representations and enabling mini-batch training after propagation.
- GBP achieves sub-linear theoretical complexity and consistently improves performance and scalability across semi-supervised and fully supervised datasets.
- GBP achieves superior results on a graph with over 1.8 billion edges in less than 2,000 seconds on a moderate machine.
2 Theoretical analysis of existing methods
The analysis characterizes the time costs of vanilla GCNs and scalable alternatives, showing how propagation, feature transformation, sampling, and storage determine their scalability. Existing approaches reduce some costs but retain unfavorable layer, edge, inference, or memory dependencies.
- Vanilla GCN propagation costs O(LmF), while feature transformation costs O(LnF 2) across training and inference.
- Scalable GNN methods approximate full neighbor propagation to enable mini-batch training, and Table 1 summarizes their training and inference complexities.
- GraphSAGE has per-epoch complexity O(nsL n F 2), which grows exponentially with the number of layers and is not scalable on large graphs.
- Layer-wise sampling limits expansion with fixed samples across layers, but its training complexity remains linear in m because sampled neighborhoods usually exceed the average degree.
- Graph sampling can achieve sub-linear per-epoch feature propagation, but GraphSAINT still requires full inference with O(LmF + LnF 2) complexity.
- PPRGo requires O(m/ε) precomputation and O(n/ε) storage for its PPR matrix, making it infeasible on billion-scale graphs.
3 Bidirectional Propagation Method
GBP approximates Generalized PageRank through localized bidirectional propagation from training/testing nodes and feature vectors, combining Monte-Carlo and Reverse Push propagation. The resulting estimator is unbiased while exploiting sparsity to reduce computation and support mini-batch training.
- Generalized PageRank: GBP precomputes Generalized PageRank propagation and then applies a multi-layer neural network with mini-batch training.A two-layer model predicts with Y = SoftMax(σ(PW1)W2).
- Bidirectional Propagation: Monte-Carlo propagation samples random walks from training/testing nodes to estimate transition probabilities with sparse matrices.The estimator is unbiased, but using many walks from every training node can be infeasible for fully supervised large-graph training.
- Bidirectional Propagation: Reverse Push propagation deterministically transfers feature-vector residues exceeding rmax to sparse reserve matrices across propagation levels.Maintaining only residue entries above the threshold avoids scanning every matrix entry.
- Estimator Construction: GBP combines Monte-Carlo and Reverse Push propagation to form an unbiased estimator of each propagation matrix and the Generalized PageRank matrix.The sparse matrices reduce estimator variance and make multiplication cost depend on their nonzero entries.
- Complexity Analysis: The bidirectional algorithm has time contributions from Monte-Carlo propagation and Reverse Push propagation, with the latter controlled by feature dimension, average degree, and rmax.The analysis assumes D^-rX is column-normalized and bounds the algorithm through Lemma 1.
- Practical Considerations: Efficiency and accuracy can be traded off by adjusting the push threshold rmax and the number of random walks nr, while the resulting propagation supports parallel execution and mini-batch construction.Random walks across nodes and Reverse Push across features can run in parallel after which mini-batches are constructed from P.
4 Experiments
Experiments evaluate GBP across transductive, inductive, and billion-scale settings, showing strong accuracy and substantial runtime advantages over scalable GNN baselines. GBP also converges faster than sampling-based methods and achieves an F1-score of 0.79 on Friendster in less than half an hour.
- Datasets and evaluation: The experiments cover seven graph datasets spanning citation, protein-interaction, customer-interaction, co-purchasing, and social-network settings.The evaluation includes transductive learning on small and billion-scale graphs and inductive learning on medium to large graphs.
- Transductive learning on small graphs: GBP outperforms APPNP across Cora, Citeseer, and Pubmed in semi-supervised transductive node classification.The study uses fixed train/validation/test splits and reports mean accuracy over ten runs.
- Inductive learning on medium to large graphs: GBP achieves comparable performance to GraphSAINT on PPI, Yelp, and Amazon with 5-10x less running time.Running time includes precomputation and training; SGC and LADIES are faster but less accurate than GraphSAINT and GBP.
- Convergence: GBP and SGC converge much faster than LADIES and GraphSAINT in the 4-layer-model experiments.The comparison excludes data loading, preprocessing, validation evaluation, and model saving time.
5 Conclusion
GBP uses localized bidirectional propagation to achieve sub-linear complexity for precomputation, training, and inference. Experiments report improved efficiency and performance, including scaling to billion-edge networks on one machine.
- GBP is a scalable GNN based on localized bidirectional propagation.
- GBP achieves sub-linear time complexity for precomputation, training, and inference.
- GBP improves efficiency and performance over state-of-the-art methods in experiments.
- GBP scales to billion-edge networks on a single machine.
Broader Impact
The paper presents GBP as a general technical and theoretical contribution for scaling GNNs on large graphs. It identifies possible scalability applications while leaving other impacts for future work.
- GBP addresses the challenge of scaling GNNs on large graphs.
- The authors characterize GBP as a general technical and theoretical contribution without foreseeable specific impacts.
- Applications in bioinformatics, computer vision, and natural language processing may improve the scalability of existing GNN models.
- Exploration of other potential impacts is left for future work.
A Proofs
The proof invokes a Chernoff bound for bounded independent and identically distributed random variables. The lemma relates their bounded range and mean to a probabilistic bound used in the analysis.
- The proof requires a Chernoff bound for bounded i.i.d. random variables.
- The variables have common mean µ and lie in the interval [0, r].
- The variables are indexed by i from 1 through n_r.
A.1 Proof of Lemma 1
The proof bounds GBP’s bidirectional propagation cost by analyzing Monte Carlo propagation, reverse push propagation, and their combination. These phase-wise bounds yield the stated overall time-complexity bound.
- A.1 Proof of Lemma 1: Algorithm 1 consists of Monte Carlo propagation, reverse push propagation, and a combination phase.
- A.1 Proof of Lemma 1: The combination phase has cost bounded by O(L^2|V_t|n_rF).
- A.1 Proof of Lemma 1: Monte Carlo propagation generates n_r random walks of length L for each training/testing node, with cost O(L|V_t|n_r).
- A.1 Proof of Lemma 1: The reverse push phase bounds residue mass to limit the number of nodes receiving substantial pushes.
- A.1 Proof of Lemma 1: Summing the three phase costs gives the overall time-complexity bound for Algorithm 1.
A.2 Proof of Lemma 2
The proof establishes Lemma 2 by induction over push operations, considering separate cases for intermediate and final propagation stages. The induction concludes that the stated invariant holds.
- The proof initializes Q(t) and R(t) to zero for all stages, with R(0) set to D−rX.
- For a push on node u and feature k with |R(t)(u, k)| > rmax, the proof analyzes two propagation cases.
- When t ≤ ℓ−1, the residue at stage t is decremented and the next-stage residue is incremented.
- When t = ℓ, the residue is transferred into Q(ℓ), preserving the invariant at the final stage.
- The induction therefore holds, completing the proof of the lemma.
A.3 Proof of Theorem 1
The theorem proof bounds the reverse-propagation procedure using residue thresholds, random-walk concentration, and a union bound. It derives a sub-linear complexity bound and relates the resulting inference behavior to GBP's advantage over sampling-based methods.
- P is identified as the Generalized PageRank matrix, satisfying P = PL.
- The proof uses a union bound to ensure the desired accuracy with probability at least 1 − 1/nL.
- Lemma 2 provides an unbiased estimator for T(ℓ), while Chernoff bounds control its estimation error with high probability.
- With L = 4 in experiments, the stated complexity is bounded using ε, d, |Vt|, and log(nL), rather than the full edge count m.
- After reverse propagation terminates, every residue entry is bounded by rmax, enabling an upper bound on Tℓ(s, k).
- GBP, SGC, and PPRGo have a significant inference-time advantage over LADIES and GraphSAINT on the entire test graph.
B.2 Additional details in experimental setup
The section provides a table of URLs for the baseline code implementations.
- Table 7 lists URLs for the baseline codes.