Source-linked AI summary
Predict then Propagate: Graph Neural Networks meet Personalized PageRank
Johannes Gasteiger, Aleksandar Bojchevski, Stephan Günnemann
TL;DR
Graph message-passing methods struggle to use large neighborhoods because propagation range is limited and deeper aggregation can oversmooth representations. The paper derives personalized PageRank propagation, yielding PPNP and APPNP, which decouple neural prediction from propagation. Across multiple graphs, the models outperform several state-of-the-art methods while remaining efficient and parameter-light.
Problem
Graph message-passing methods use only a few propagation steps, making their effective classification neighborhoods difficult to extend without oversmoothing or increasing network depth and parameters.
Method
The paper derives personalized PageRank propagation and uses it to build PPNP and its fast approximation APPNP, separating neural predictions from graph propagation.
Results
PPNP and APPNP significantly outperform state-of-the-art baselines across all evaluated datasets, while using fewer parameters and less training time than most competing models.
Takeaways & Limitations
The approach provides a large, adjustable neighborhood for node classification and can be combined with arbitrary neural prediction networks without adding propagation parameters.
Takeaways & Limitations
The paper identifies the need for faster or incremental personalized PageRank approximations and more sophisticated propagation schemes as future work.
Abstract
from arXiv · showhide
Neural message passing algorithms for semi-supervised classification on graphs have recently achieved great success. However, for classifying a node these methods only consider nodes that are a few propagation steps away and the size of this utilized neighborhood is hard to extend. In this paper, we use the relationship between graph convolutional networks (GCN) and PageRank to derive an improved propagation scheme based on personalized PageRank. We utilize this propagation procedure to construct a simple model, personalized propagation of neural predictions (PPNP), and its fast approximation, APPNP. Our model's training time is on par or faster and its number of parameters on par or lower than previous models. It leverages a large, adjustable neighborhood for classification and can be easily combined with any neural network. We show that this model outperforms several recently proposed methods for semi-supervised classification in the most thorough study done so far for GCN-like models. Our implementation is available online.
1 INTRODUCTION
Existing graph message-passing methods use limited neighborhoods, while enlarging them can cause oversmoothing and worsen the trade-off between neighborhood range and network depth. The paper addresses this with personalized PageRank propagation, separating prediction from propagation and achieving strong efficiency and accuracy results.
- Message-passing methods use limited neighborhoods, although larger neighborhoods would help nodes in peripheral or sparsely labelled regions.
- Increasing propagation depth is difficult because excessive neighborhood aggregation causes oversmoothing and loss of local focus.
- Personalized PageRank adds teleportation to the root node, balancing locality against information from a large neighborhood and permitting infinitely many propagation steps without oversmoothing.
- Separating prediction from propagation enables larger propagation ranges without changing the neural network and allows combination with any prediction method.
- The model achieves state-of-the-art results with fewer parameters, less training time than most competitors, and computational complexity linear in the number of edges.
2 GRAPH CONVOLUTIONAL NETWORKS AND THEIR LIMITED RANGE
GCN propagation is tied to a shallow, layer-based neighborhood and can converge toward a graph-wide distribution that forgets the root node. The paper motivates personalized PageRank as a way to retain root-specific locality while extending propagation.
- GCN depth couples neighborhood size to neural-network depth, while additional layers can cause oversmoothing and increase learnable parameters.
- The model is illustrated as generating node predictions from features first, then propagating them with an adaptation of personalized PageRank.
- As propagation depth grows, GCN influence follows a random-walk distribution that can converge to a graph-wide stationary distribution independent of the root node.
3 PERSONALIZED PROPAGATION OF NEURAL PREDICTIONS
PPNP generates node-level neural predictions independently, then propagates them with personalized PageRank; APPNP approximates this propagation efficiently while preserving adjustable locality and long-range influence.
- Personalized PageRank: Personalized PageRank uses a teleport vector to preserve each root node’s local neighborhood in the limiting distribution.The teleport probability α controls how quickly influence decreases with distance from the root.
- PPNP: PPNP generates predictions from node features and propagates them through a fully personalized PageRank scheme.The neural network operates independently on each node’s features, producing prediction matrix H before propagation.
- PPNP: Separating prediction from propagation makes neural-network depth independent of propagation range and permits combining the scheme with other prediction methods.The approach can use effectively infinitely many neighborhood aggregation layers without adding message-passing layers.
- Efficiency and range: Direct computation of the fully personalized PageRank matrix would create a dense matrix with O(n^2) training and inference complexity.APPNP addresses this computational issue through approximate propagation rather than explicit matrix construction.
- APPNP: APPNP approximates topic-sensitive PageRank with power iteration, retaining graph sparsity without constructing an n×n matrix.The prediction matrix H serves as both the starting vector and teleport set, while K controls the number of iterations.
- Efficiency and range: The propagation scheme requires no additional trainable parameters, allowing far-reaching propagation with few parameters.This contrasts with GCN-style propagation, where additional steps typically require additional layers and parameters.
4 RELATED WORK
Related approaches extend message passing with skip connections, co-training, normalization, or architectural changes, but the paper positions decoupled propagation as a simpler way to increase range and avoid oversmoothing.
- Extended message passing: Skip connections and aggregation schemes improve message-passing training and neighborhood range, but the resulting models still use limited propagation depth.The cited approaches remain constrained by the low number of message-passing layers used.
- Training strategies: Combining message passing with co-training or self-training can improve results, but each additional step requires a full training cycle and increases training time.The paper notes that these improvements are comparable to results from other semi-supervised classification models.
- Oversmoothing: Residual connections with batch normalization address oversmoothing, whereas this paper uses decoupled prediction and propagation without ad-hoc techniques or extra hyperparameters.The decoupled design also increases propagation range without introducing additional layers.
5 EXPERIMENTAL SETUP
The experiments use harmonized, statistically rigorous evaluation across four text-classification graphs, with matched model capacity and controlled hyperparameter procedures.
- Evaluation protocol: The evaluation addresses sensitivity to data splits and initialization through a carefully designed protocol, since message-passing results can vary substantially across setups.The paper identifies single splits, unclear validation/test separation, and dataset-specific tuning as sources of experimental bias.
- Evaluation protocol: Confidence intervals are calculated by bootstrapping and main claims are tested with paired t-tests to assess statistical robustness.The authors describe this as their most rigorous study of GCN-like models.
- Datasets: The benchmark contains four text-classification graphs: three citation graphs and one coauthorship graph, all using bag-of-words abstract features.The evaluated graphs use their largest connected components.
- Reported results: Table 2 reports average accuracy with uncertainties at the 95% confidence level calculated by bootstrapping.Its caption states that PPNP and APPNP significantly outperform the compared models on all datasets under the rigorous setup.
- Reported results: Accuracy distributions vary across data splits and initializations, demonstrating why rigorous evaluation is important for model comparison.PPNP, APPNP, and GAT typically have lower variance than other methods.
- Datasets: The datasets have average shortest path lengths between 5 and 10, so a regular two-layer GCN cannot cover each entire graph.Shortest path length is reported as SP in the dataset statistics.
- Baselines: The comparison includes GCN, N-GCN, GAT, bootstrapped feature propagation, and jumping knowledge networks, including an unoptimized vanilla GCN reference.Hyperparameters for all models are listed in the appendix.
- Model configuration: PPNP uses a neural network structurally similar to GCN with the same parameter count, while APPNP uses α = 0.1 and K = 10 power iterations.The MICROSOFT ACADEMIC graph uses α = 0.2.
6 RESULTS
PPNP and APPNP achieve strong, statistically significant accuracy across datasets while supporting broad propagation ranges and competitive training efficiency. Their advantages are especially pronounced with sparse labels and distant training nodes, and APPNP remains stable across propagation steps and teleport probabilities.
- Overall accuracy: Both models significantly outperform state-of-the-art baselines on all datasets under a rigorous evaluation protocol.The result is statistically significant at p < 0.05 using a paired t-test.
- Overall accuracy: PPNP, APPNP, and GAT typically show lower accuracy variance across random initializations and data splits.The distributions demonstrate sensitivity differences between methods and the importance of statistically rigorous evaluation.
- Training time: APPNP is around 25 % slower than GCN per epoch but scales similarly with graph size and is significantly faster than GAT.Exact PPNP is limited to moderately sized graphs, whereas APPNP scales to large data.
- Training set size: PPNP and APPNP gain a larger advantage as the number of labeled nodes per class decreases, especially for nodes farther from training nodes.Their higher propagation range allows information to travel farther in sparsely labeled settings.
- Propagation steps: With α = 0, accuracy breaks down as propagation steps increase, whereas APPNP with α = 0.1 improves and stabilizes toward exact PPNP.K = 10 is sufficient to effectively approximate exact PPNP in the reported experiments.
- Teleport probability: Teleport probabilities around α ∈ [0.05, 0.2] generally perform best, although the optimum varies across datasets.Higher α also improves convergence speed, so it should be adjusted to the graph structure.
7 CONCLUSION
The paper introduces PPNP and APPNP, which use personalized PageRank to decouple prediction from propagation and support large, adjustable neighborhoods. APPNP’s propagation converges to exact PPNP, while the approach is reported as efficient and strong across multiple graphs.
- PPNP and APPNP derive graph propagation from personalized PageRank by relating GCN propagation to PageRank.PPNP is the exact model, while APPNP provides a fast approximation.
- Decoupling prediction and propagation lets the model extend its effective range without adding propagation-dependent neural-network parameters.The propagation scheme can be paired with neural networks that generate predictions from node features.
- The model uses a large, adjustable neighborhood controlled by the teleport probability α and is reported to be computationally efficient.The conclusion states that the method outperforms several state-of-the-art methods on multiple graphs.
- APPNP’s finite-step propagation converges to exact PPNP as the number of propagation steps tends to infinity.The convergence follows from the resulting geometric series under the stated normalization and α conditions.
C EXPERIMENTAL DETAILS
The experiments use sampled citation and coauthorship graphs with fixed training and early-stopping sets, common optimization settings, and model-specific architectures and regularization. Evaluation uncertainty is estimated through 1000-sample bootstrapping at a 95% confidence level.
- Sampling procedure: Figure 7 illustrates sampling from visible and test sets, with 1500 sampled citation-graph nodes and 5000 MICROSOFT ACADEMIC nodes in the visible set.Each experiment uses 20 training nodes per class and 500 early-stopping nodes.
- Training procedure: The early-stopping procedure uses patience p = 100 and a maximum of n = 10 000 epochs, selecting the highest early-stopping accuracy and breaking ties by loss.
- Uncertainty estimation: Uncertainties and confidence intervals use a 95% confidence level calculated by bootstrapping with 1000 samples.
- Optimization: All models use Adam with learning rate l = 0.01 and cross-entropy loss, while feature rows are L1 normalized.Weights are initialized according to Glorot and Bengio (2010).
- Model settings: Vanilla GCN uses two layers with h = 16, whereas optimized GCN uses h = 64 with adjacency dropout d = 0.5 and λ = 0.02.
- Model settings: N-GCN uses R = 4 heads, walks up to K −1 = 4 steps, and effectively RKh = 320 hidden units, five times the units of GCN, GAT, and PPNP.
E F1 SCORE
PPNP achieves the highest average macro F1 score on every investigated dataset. The supplied materials also identify confidence-interval reporting and an out-of-memory result in the efficiency analysis.
- PPNP achieves the highest average macro F1 score on all datasets investigated.The table caption states that uncertainties represent the 95% confidence level calculated by bootstrapping.
- The F1-score table reports uncertainties at the 95% confidence level calculated by bootstrapping.
- The efficiency analysis records an out-of-memory result on PUBMED and MS ACADEMIC.
- Figure 8 reports that deeper APPNP neural networks do not improve validation accuracy.The caption attributes this observation probably to simple bag-of-words features and the small training set size.
H TRAINING SET SIZE
The supplied figure captions report accuracy as a function of training set size for CITESEER, PUBMED, and MICROSOFT ACADEMIC. They identify the datasets and metric but do not state the plotted outcomes.
- Figure 9 plots accuracy for different training set sizes on CITESEER.
- Figure 10 plots accuracy for different training set sizes on PUBMED.
- Figure 11 plots accuracy for different training set sizes on MICROSOFT ACADEMIC.
I ACCURACY DEPENDING ON DISTANCE FROM TRAINING NODES
APPNP’s accuracy improvement over GCN increases with distance from training nodes on CORA-ML and is examined across multiple graphs, with graph-specific y-axis scales.
- On CORA-ML, APPNP’s average accuracy improvement over GCN increases with hop distance from the training nodes.The figure reports improvement in percentage points and also gives the average number of nodes at each distance.
- Across different graphs, the figures report APPNP’s average accuracy improvement over GCN by hop distance from training nodes.The average node count at each distance is calculated over multiple dataset splits.
- The y-axis uses a different scale for each graph, so improvement magnitudes should be compared within graphs rather than directly across them.