Source-linked AI summary
Scaling Graph Neural Networks with Approximate PageRank
Aleksandar Bojchevski, Johannes Gasteiger, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberczki, Michal Lukasik, Stephan Günnemann
TL;DR
Large-scale GNNs remain difficult to train because recursive message passing creates costly neighborhood expansion. PPRGo replaces repeated propagation with pre-computed sparse approximate personalized PageRank, achieving high performance on a 12.4-million-node graph in under two minutes while supporting distributed execution.
Problem
Recursive message passing creates expensive neighborhood expansion, while large-graph benchmarks and distributed scalability evaluations remain limited.
Method
PPRGo decouples feature transformation from propagation and uses pre-computed sparse approximate personalized PageRank for multi-hop information diffusion.
Results
12.4M nodes, 173M edges, and 2.8M node features comprise MAG-Scholar, where PPRGo achieves high performance in under 2 minutes on one machine and is more efficient than multi-hop models when distributed.
Takeaways & Limitations
PPRGo provides a scalable approach for semi-supervised node classification on million-node graphs in single-machine and distributed environments.
Takeaways & Limitations
Direct power-iteration-based propagation remains prohibitively expensive for large graphs, and graphs beyond a certain size may not fit in memory.
Abstract
from arXiv · showhide
Graph neural networks (GNNs) have emerged as a powerful approach for solving many network mining tasks. However, learning on large graphs remains a challenge - many recently proposed scalable GNN approaches rely on an expensive message-passing procedure to propagate information through the graph. We present the PPRGo model which utilizes an efficient approximation of information diffusion in GNNs resulting in significant speed gains while maintaining state-of-the-art prediction performance. In addition to being faster, PPRGo is inherently scalable, and can be trivially parallelized for large datasets like those found in industry settings. We demonstrate that PPRGo outperforms baselines in both distributed and single-machine training environments on a number of commonly used academic graphs. To better analyze the scalability of large-scale graph learning methods, we introduce a novel benchmark graph with 12.4 million nodes, 173 million edges, and 2.8 million node features. We show that training PPRGo from scratch and predicting labels for all nodes in this graph takes under 2 minutes on a single machine, far outpacing other baselines on the same graph. We discuss the practical application of PPRGo to solve large-scale node classification problems at Google.
1 INTRODUCTION
Large-scale GNN learning is constrained by recursive message passing, neighborhood expansion, and limited benchmark coverage. PPRGo addresses these issues with approximate personalized PageRank, enabling scalable single-machine and distributed learning.
- Motivation: Few large benchmark datasets support scalability evaluation, while many studies focus primarily on single-machine settings.Most demonstrated graphs contain fewer than 250K nodes, apart from a small number of exceptions.
- Motivation: Recursive message passing causes neighborhood expansion and expensive information propagation as GNN depth increases.Each node requires information from neighbors whose own representations require further expansion.
- Motivation: Existing scalable GNN methods commonly sample graph structure but still incur steep runtime–accuracy trade-offs from multi-hop message passing.Sampling may also require computing importance scores before reducing retrieved data.
- Approach: PPRGo uses approximate personalized PageRank to preserve multi-hop influence without repeated power iteration or prohibitive message passing.The approach exploits localized PageRank vectors that can be sparsely approximated and pre-computed in distributed fashion.
- Contributions: 12.4M nodes, 173M edges, and 2.8M node features define the MAG-Scholar benchmark introduced for large-scale graph learning.The benchmark is presented alongside PPRGo’s scalability evaluation.
2 BACKGROUND
The background separates feature transformation from graph propagation and motivates approximate personalized PageRank as a scalable alternative. Sparse localization and distributed push operations make PageRank-based propagation practical, whereas dense propagation and repeated power iteration are costly.
- GNNs and Message-Passing: Message-passing GNNs transform and aggregate neighbor information recursively, but deeper models require exponentially more nodes and may suffer from over-smoothing.Large distributed graphs also incur expensive remote calls when gathering neighborhoods.
- GNNs and Message-Passing: PPNP decouples node-wise neural feature transformation from personalized-PageRank propagation.The neural network generates local representations, while propagation smooths them according to graph structure.
- GNNs and Message-Passing: Dense propagation matrices are inefficient, and repeated power iterations during every gradient update become prohibitively expensive on large graphs.Very large sparse graphs may also exceed memory capacity.
- Personalized PageRank: Personalized PageRank incorporates multi-hop neighborhood information without explicit message passing, with influence decaying across layers.The relevant PageRank formulation can be approximated using scalable algorithms.
- Personalized PageRank: Forward and backward search approximate PageRank through graph traversal, while Andersen et al.’s push method offers scalability, guarantees, and distributed implementability.The resulting vectors can have few nonzero entries.
- Personalized PageRank: Localized probability mass permits truncating small PageRank values and representing the propagation matrix sparsely.The sparse approximation can be renormalized to approximate the symmetric propagation matrix.
3 THE PPRGO MODEL
PPRGo decouples feature transformation from propagation and uses sparse, top-k approximate personalized PageRank to generate predictions. Pre-computation enables efficient batched training and inference while exposing a scalability–performance trade-off through its approximation parameters.
- Model Design: PPRGo combines independently computed node representations with sparse approximate personalized-PageRank propagation.Its design follows from decoupling feature transformation and propagation.
- Prediction: For each node, predictions aggregate representations from its top-k PageRank-ranked neighbors using their approximate PageRank weights.The model maps node attributes to local representations before aggregation.
- Scalability: The approximation threshold ε and neighbor count k provide explicit controls over the scalability–performance trade-off.Increasing k includes more neighbors, while ε controls the residual norm.
- Approximation: PPRGo’s PageRank approximation uses sparse vectors initialized with a target node and residual mass, then applies distributed push operations.The algorithm takes a graph, teleport probability, target node, and maximum residual as inputs.
- Scalability: Pre-computing the sparse propagation matrix reduces training and inference prediction cost to O(k), where k ≪ N.A batch of b nodes requires features from at most b·k nodes.
- Approximation: The teleport probability α controls whether propagation emphasizes immediate or extended multi-hop neighborhoods.Values near 1 favor local neighborhoods, while smaller values increase extended-neighborhood influence.
4 SCALABILITY
PPRGo targets industry-scale graph classification by combining distributed computation with efficient inference strategies. Its approach precomputes approximate PageRank vectors for training, uses limited power iteration during inference, and exploits homophily to reduce neural-network predictions.
- 4.1 Node Classification in the Real World: Web-scale graphs can contain hundreds of billions of nodes and edges, with frequent changes and rapidly stale labels.Fast training and especially fast inference are desirable because inference is performed more frequently in real-world settings.
- 4.2 Distributed Training: PPRGo trains in two distributed stages: precomputing approximate personalized PageRank vectors, then optimizing model parameters with stochastic gradient descent.Both stages are implemented using distributed computing techniques.
- 4.2 Distributed Training: PageRank vectors for every node can be computed in parallel, allowing the preprocessing implementation to scale to graphs with billions of nodes.The number of iterations required for a target approximation accuracy can be determined in advance, enabling runtime estimation.
- 4.3 Efficient Inference: During inference, PPRGo can replace one-time PageRank-vector computation with power iteration because the vectors are used only once.Only 1-3 power-iteration steps are needed before accuracy improvements level off.
- 4.3 Efficient Inference: Homophily lets PPRGo predict logits for only a small random fraction of nodes while nearly matching full-prediction performance.The resulting label-propagation approach can use 10 % or 1 % of logits and reduce runtime below a graph-agnostic model without sacrificing accuracy.
5 EXPERIMENTS
The experiments evaluate PPRGo’s accuracy–scalability trade-offs, distributed speed, and single-machine resource use across academic and large graph datasets. PPRGo maintains comparable predictive performance while offering substantially faster runtimes and scaling to MAG-Scholar-C.
- Scalability vs. Accuracy Trade-off: Smaller approximation 𝜖 and larger top-k neighborhoods consistently improve performance, while increasing computational cost.In the academic setting, runtime increases from 6 minutes at 𝜖=0.1, k=2 to 12 minutes at 𝜖=0.001, k=256; sparse-label settings are more sensitive to these choices.
- Scalability vs. Accuracy Trade-off: Top-k performance plateaus around k=32 because a few nodes capture most personalized PageRank mass on average.The result supports approximating localized PageRank vectors with sparse top-k representations.
- Distributed Training: PPRGo is considerably faster than the 2-hop GNN baseline in distributed training, and its speedup advantage grows with additional workers.The models have around 61% accuracy, but PPRGo also requires fewer steps to converge; FastGCN offers no significant scalability advantage over the baseline in this IO-dominated setting.
- Distributed Training: PPRGo’s relative speed deteriorates more slowly as k increases than the 2- and 3-hop GNNs in distributed training.FastGCN again matches the 2-hop GNN in the reported comparison.
- Runtime and Memory on a Single Machine: On MAG-Scholar-C, PPRGo trained from scratch and predicted all test nodes in under 2 minutes, whereas Cluster-GCN and SGC did not finish within 24 hours.On Reddit, PPRGo completed in under 20 seconds and used less memory than the compared methods, while APPNP ran out of memory.
- Efficient Inference: Reducing inferred nodes by a factor of 10 lowers accuracy by around 0.6 percentage points while reducing inference time by 50%.PPRGo achieved 68.7% accuracy with a single power-iteration step, without calculating the PPR vectors.
6 CONCLUSION
PPRGo scales GNN node classification to million-node graphs without expensive message passing, while trading scalability and performance through intuitive hyperparameters. On MAG-Scholar, it achieves high performance in under 2 minutes on one machine and scales efficiently in distributed settings.
- PPRGo scales semi-supervised node classification to graphs with millions of nodes without relying on expensive message passing.
- 12.4M nodes, 173M edges, and 2.8M node features define the MAG-Scholar benchmark used to evaluate large-scale GNN scalability.
- Fewer inferred logits require more power iteration steps to stabilize accuracy, increasing propagation time.
- Under 2 minutes covers preprocessing, training, and inference for PPRGo on MAG-Scholar using a single machine.
- PPRGo demonstrates distributed scalability and greater efficiency than multi-hop models beyond the single-machine setting.
A.1 Parallel Efficiency
The experiments measure how effectively models use additional distributed workers through parallel efficiency. PPRGo achieves the best parallel efficiency among the evaluated models.
- The distributed experiments evaluate parallel efficiency across different models on MAG-Scholar-F.
- Parallel efficiency measures how well a model utilizes additional distributed workers.It is evaluated using the number of steps per second achieved with t workers relative to one worker.
- PPRGo achieves the best parallel efficiency among the evaluated models.
A.2 MAG-Scholar Graph Construction
MAG-Scholar is constructed from the Microsoft Academic Graph as a citation graph with paper-abstract features and ground-truth field-of-study labels.
- MAG-Scholar represents papers as nodes and citations or references as graph edges.
- Each paper is represented by bag-of-words features extracted from its abstract.
- The graph retains words appearing in at least 5 abstracts during feature preprocessing.
A.3 Experimental Details
The experiments use fixed PPRGo settings across datasets, with a Reddit-specific teleport parameter, a two-layer feed-forward network, and standardized graph preprocessing.
- The teleport parameter is α=0.25 for all datasets except Reddit, where α=0.5 is used.
- The feed-forward neural network has two layers, including a single hidden layer of size 32.
- Training uses dropout 0.1, weight decay 10^-4, 200 epochs, learning rate 0.005, Adam, and batch size 512.
- Graphs are restricted to their largest connected component and standardized as undirected and unweighted.
- Overall runtime excludes dataset loading time because it is the same for all models.
A.4 Further Implementational Details
The distributed implementation approximates personalized PageRank with fixed iterations and prunes nodes whose residual scores fall below a threshold.
- Distributed computation uses a fixed number of push-flow iterations rather than iterating until convergence.
- Nodes with residual scores below a specified threshold are dropped during each distributed iteration.
- Single-machine experiments implement the algorithm in Python with Numba acceleration and no parallelization.
A.5 Applicability and Limitations
PPRGo assumes homophily and compresses message passing into a single step, limiting its theoretical expressiveness relative to GNNs.
- Compressing message passing into a single step prevents PPRGo from performing arbitrary message-passing schemes like GNNs.
- PPRGo has less theoretical expressiveness than GNNs, despite showing the same or better practical accuracy.
- Its arbitrary fθ realization supports use with images, audio, and text models such as CNNs, LSTMs, and Transformers.