Predict then Propagate: Graph Neural Networks meet Personalized PageRank
By Johannes Klicpera, Aleksandar Bojchevski, Stephan Günnemann. 2018
2,108 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, Information Retrieval & Search, Graph Learning
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Stephan Günnemann
- Jure Leskovec
- William L. Hamilton
- Xiangnan He
- Marinka Zitnik
- Philip S. Yu
- Shirui Pan
- Michael M. Bronstein
In Statistical and Nonlinear Physics
- Stephan Günnemann
- Matthias Fey
- Jure Leskovec
- Michael M. Bronstein
- William L. Hamilton
- Xiyuan Wang
- Muhan Zhang
- Pan Li
In Information Retrieval & Search
- Stephan Günnemann
- Daniel Zügner
- Matthias Fey
- William L. Hamilton
- Muhan Zhang
- Hao Zhu
- Pan Li
- Xiyuan Wang
In Graph Learning
- Stephan Günnemann
- William L. Hamilton
- Jure Leskovec
- Matthias Fey
- Marinka Zitnik
- Michael M. Bronstein
- Aleksandar Bojchevski
- Pan Li
Citations in the corpus
- Directional Message Passing for Molecular Graphs (2020, background): “General GNNs have been largely inspired by their application to molecular graphs and have started to achieve breakthrough performance in various tasks at around the same time the molecular variants did (Kipf & Welling, 2017; Klicpera et al., 2019; Zambaldi et al., 2019).”
- Fast Graph Representation Learning with PyTorch Geometric (2019, methodology): “…(Hamilton et al., 2017), the attention-based operators GAT (Veličković et al., 2018) and AGNN (Thekumparampil et al., 2018), the Graph Isomorphism Network (GIN) from Xu et al. (2019), and the Approximate Personalized Propagation of Neural Predictions (APPNP) operator (Klicpera et al., 2019).”
- Masked Label Prediction: Unified Massage Passing Model for Semi-Supervised Classification (2020, methodology): “where β can be the gated function like Equation 5 or a predefined hyper-parameters like APPNP [Klicpera et al., 2018].”
- Lifelong Graph Learning (2020, positive): “Regardless of the nonlinear function, existing methods propagate neighbor features as ÂX, where X = [x1, · · · ,xn], meaning they can only propagate information element-wisely, as features in the next layer are weighted average of the current features [20, 22, 42, 58].”
- Pitfalls of Graph Neural Network Evaluation (2018, methodology): “If we were interested in comparing one model versus the rest, we could perform pairwise t-tests, as done in Klicpera et al. [2019]. Since we are interested in comparing all the models to each other, we consider the relative accuracy of each model instead.”
- Adversarial Attacks on Neural Networks for Graph Data (2018, methodology): “, 2006], the last years have seen a tremendous interest in methods for deep learning on graphs [Bojchevski and Günnemann, 2018; Monti et al., 2017; Cai et al., 2018; Klicpera et al., 2019].”
- Simple and Deep Graph Convolutional Networks (2020, methodology): “(Klicpera et al., 2019a) also proposes APPNP, which with an approximation derived by a truncated power iteration.”
- Simple Spectral Graph Convolution (2021, methodology): “…baselines, We include three state-of-the-art shallow models: GCN (Kipf & Welling, 2016), GAT (Veliˇckovi´c et al., 2017), FastGCN (Chen et al., 2018), APPNP (Klicpera et al., 2019a), Mixhop (Abu-El-Haija et al., 2019), SGC (Wu et al., 2019), DGI (Velickovic et al., 2019) and GIN (Xu et al., 2018a).”
- Graph Representation Learning (2020, background): “[2019] and Klicpera et al. [2019] found that convolutions based on à achieved the best empirical performance.”
- Graph Random Neural Networks for Semi-Supervised Learning on Graphs (2020, background): “• Eight graph convolutions: GCN [20], GAT [35], APPNP [21], Graph U-Net [12], SGC [39], MixHop [1], GMNN [31] and GrpahNAS [13].”
- Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods (2021, neutral): “• APPNP: MLP hidden dimension ∈ { 16 , 32 , 64 , 128 , 256 } , learning rate ∈ { .”
- Revisiting Heterophily For Graph Neural Networks (2022, methodology): “We compare these approaches with several baselines and SOTA GNN models: MLP with 2 layers (MLP-2), GAT [41], APPNP [20], GPRGNN [8], H2GCN [46], MixHop [1], GCN+JK [19, 43, 26], GAT+JK [41, 43, 26], FAGCN [4], GraphSAGE [15], Geom-GCN [36] and BernNet [16].”
- Open Graph Benchmark: Datasets for Machine Learning on Graphs (2020, background): “, what mini-batch training methods can induce the best regularization effect, and how to allow mini-batch training for advanced GNNs that rely on large receptive-field sizes (Xu et al., 2018; Klicpera et al., 2019; Li et al., 2019), since the current mini-batch methods are rather limited by the numb”
- Combining Label Propagation and Simple Models Out-performs Graph Neural Networks (2020, background): “For comparable GNN models to our framework (in terms of simplicity or style), we use GCN, SGC, and APPNP.”
- BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation (2021, methodology): “APPNP [14] utilizes Personalized PageRank (PPR) to set the filter weights.”
- Is Homophily a Necessity for Graph Neural Networks? (2021, background): “Since then, numerous GNN variants, which follow specific forms of feature transformation (linear layers) and aggregation have been proposed [34, 13, 11, 19].”