GPR‑GNN: Adaptive Universal Generalized PageRank Graph Neural Network for Over‑Smoothing and Generalization

Guest Speaker: Eli Chien (UIUC Research Assistant) – organized by DataFunTalk.

Introduction: The talk introduces the paper "Adaptive Universal Generalized PageRank Graph Neural Network (GPR‑GNN)" presented at ICLR 2021. Graph Neural Networks (GNNs) have achieved great success on tasks such as node classification, graph classification, and link prediction, with applications ranging from disease‑gene association to recommendation systems.

The presentation first outlines the logical framework of GNNs and highlights two fundamental shortcomings: limited universality across heterogeneous graphs and the over‑smoothing problem.

1. GNN Logical Framework and Defects

Typical GNNs stack graph‑specific layers (e.g., GCN). Each layer propagates node features to neighbors, applies linear and non‑linear transformations, and the final layer uses softmax for label prediction. Two major defects arise from this stacking:

Universality: Most GNNs perform well only on homophilic graphs (nodes tend to connect to same‑label nodes). A truly universal GNN should work equally well on heterophilic graphs.

Over‑Smoothing: Stacking many layers leads to feature collapse; after many layers the node representations become indistinguishable, which limits practical GNN depth to 2‑4 layers.

2. GPR‑GNN Mechanism and Theoretical Analysis

To address the two defects, the GPR‑GNN model is proposed. It first extracts initial node features (e.g., via an MLP), then propagates these features on the graph for K steps, and finally linearly combines the outputs of all propagation steps using learnable GPR parameters (denoted ~). These parameters are interpretable and can mitigate over‑fitting.

The model can be viewed as a generalized PageRank (GPR) process: starting from an initial probability distribution, the distribution is propagated K times, producing hidden‑layer outputs that are linearly combined to obtain the final prediction.

From a graph signal processing perspective, GPR corresponds to a polynomial graph filter. If all GPR parameters are non‑negative, the filter behaves as a low‑pass filter; alternating signs enable high‑pass behavior, providing the ability to model both homophilic (low‑frequency) and heterophilic (high‑frequency) graphs. Hence, achieving universality requires some parameters to be negative.

3. Experimental Validation

3.1 Generalization Verification – Synthetic cSBM graphs with controllable homophily/heterophily were used. GPR‑GNN achieved the best symmetric performance across the spectrum, while models like GCN, GAT, and APPNP performed well on homophilic graphs but poorly on heterophilic ones.

3.2 Interpretability Verification – On both synthetic and real datasets, GPR parameters were examined. For homophilic graphs, parameters were non‑negative (low‑pass); for heterophilic graphs, negative values appeared (high‑pass), matching theoretical predictions.

3.3 Over‑Smoothing Avoidance – Experiments initialized GPR parameters with only the last layer active, causing severe over‑smoothing at epoch 0 (≈50% accuracy). During training, earlier‑layer parameters grew while the last‑layer weight decreased, leading to accuracy ≈98.8%, demonstrating that GPR‑GNN can overcome over‑smoothing.

Additional experiments on ten real‑world datasets (five homophilic, five heterophilic) confirmed GPR‑GNN’s superior performance.

4. Summary and Future Directions

GPR‑GNN offers three key advantages: universality across graph types, avoidance of over‑smoothing and over‑fitting, and interpretable parameters.

Potential future work includes:

Replacing the simple MLP feature extractor with more powerful models.

Designing more sophisticated polynomial graph filters.

Extending GPR concepts to graph representation learning.

Improving existing GNNs, especially those based on personalized PageRank, using GPR ideas.

Thank you for attending the talk.

Please like, share, and give a three‑click boost at the end of the article.