PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Universal Generalized PageRank Graph Neural Network

Eli Chien, Jianhao Peng, Pan Li, Olgica Milenkovic

arXiv:2006.07988v6cs.LGstat.ML

TL;DR

Existing GNNs struggle to balance node features and topology across homophilic and heterophilic graphs while avoiding over-smoothing. The paper introduces GPR-GNN, which learns adaptive Generalized PageRank weights, and reports robust performance across synthetic and real-world benchmarks. Theoretical results explain its filtering behavior and adaptive mitigation of over-smoothing.

  • Problem

    Existing GNNs do not universally integrate node features and graph topology across homophilic and heterophilic graphs, and deep propagation can cause feature over-smoothing.

  • Method

    GPR-GNN combines a GNN with an adaptively learned Generalized PageRank procedure whose propagation weights are trained jointly with hidden-feature parameters.

  • Results

    GPR-GNN significantly outperforms other baselines on cSBM graphs across strong homophily to strong heterophily and performs strongly on homophilic and heterophilic real-world benchmarks.

  • Takeaways & Limitations

    Adaptive GPR weights provide a graph-filtering mechanism that can accommodate diverse node-label patterns while using large-step propagation without persistent feature over-smoothing.

  • Takeaways & Limitations

    The over-smoothing guarantee is stated under assumptions including a connected graph, training nodes from every class, and suitable optimizer learning-rate decay.

Abstract

from arXiv · show

In many important graph data processing applications the acquired information includes both node features and observations of the graph topology. Graph neural networks (GNNs) are designed to exploit both sources of evidence but they do not optimally trade-off their utility and integrate them in a manner that is also universal. Here, universality refers to independence on homophily or heterophily graph assumptions. We address these issues by introducing a new Generalized PageRank (GPR) GNN architecture that adaptively learns the GPR weights so as to jointly optimize node feature and topological information extraction, regardless of the extent to which the node labels are homophilic or heterophilic. Learned GPR weights automatically adjust to the node label pattern, irrelevant on the type of initialization, and thereby guarantee excellent learning performance for label patterns that are usually hard to handle. Furthermore, they allow one to avoid feature over-smoothing, a process which renders feature information nondiscriminative, without requiring the network to be shallow. Our accompanying theoretical analysis of the GPR-GNN method is facilitated by novel synthetic benchmark datasets generated by the so-called contextual stochastic block model. We also compare the performance of our GNN architecture with that of several state-of-the-art GNNs on the problem of node-classification, using well-known benchmark homophilic and heterophilic datasets. The results demonstrate that GPR-GNN offers significant performance improvement compared to existing techniques on both synthetic and benchmark data.

1 INTRODUCTION

Existing GNNs combine node features with graph topology but are limited by homophily assumptions and feature over-smoothing. GPR-GNN learns propagation weights jointly with neural-network parameters, achieving robust performance across homophilic and heterophilic settings.

  • Motivation: Graph learning methods must jointly exploit node features and graph topology in applications such as semi-supervised node classification.These information sources can carry complementary evidence, as illustrated by social-network users and their relationships.
  • Motivation: Most existing GNN architectures are tailored to homophilic graphs, limiting their ability to learn general graph-structured data.Homophily assumes that connected nodes tend to share labels.
  • Motivation: Increasing GNN depth commonly causes feature over-smoothing, making node features nondiscriminative and encouraging shallow practical architectures.Existing models are often limited to roughly 2–4 layers despite the possibility of stacking more layers.
  • GPR-GNN: GPR-GNN learns Generalized PageRank weights together with neural-network parameters to adaptively balance node-feature and topological information.The learned weights can be positive or negative, allowing adaptation to homophilic or heterophilic label patterns.
  • GPR-GNN: GPR-GNN theoretically supports polynomial graph filtering, mitigates over-smoothing after many propagation steps, and uses informative large-step propagation.The paper reports both theoretical findings and empirical evaluation on synthetic and real-world node-classification datasets.
  • Results: On contextual stochastic block model data, GPR-GNN outperforms all baselines from strong homophily to strong heterophily and achieves state-of-the-art performance on mixed benchmark datasets.The cSBM continuously varies graph structure across the homophily–heterophily spectrum.

2 PRELIMINARIES

The paper formalizes an undirected graph through its nodes, edges, node features, and normalized adjacency matrices.

  • Graph notation: The graph is modeled as an undirected graph G = (V, E) with n nodes assigned to C ≥2 classes.The graph topology is represented by adjacency matrix A.
  • Graph notation: Node features are represented by matrix X ∈R^n×f, where f is the number of features per node.X_i: denotes row i and X_:j denotes column j.
  • Graph notation: Self-looped adjacency is normalized as ˜A_sym = ˜D^−1/2 ˜A ˜D^−1/2 using the diagonal degree matrix ˜D.The normalization defines the symmetric graph operator used later in propagation.

3 GPR-GNNS: MOTIVATION AND CONTRIBUTIONS

GPR-GNN addresses heterophily and over-smoothing by learning propagation weights that form an adaptive polynomial graph filter over hidden node features.

  • Generalized PageRank: Generalized PageRank assigns learnable weights γ_k to propagation steps and aggregates the resulting representations for graph clustering or feature propagation.Specific choices recover methods such as Personalized PageRank and other PageRank variants.
  • Generalized PageRank: Truncating GPR at order K makes it equivalent to a polynomial graph filter, whose learned weights determine the filter.Larger K can better approximate the underlying optimal graph filter and supports large-step propagation.
  • Homophily versus heterophily: Homophily measures the tendency of neighboring nodes to share labels, with H(G) approaching 1 for strong homophily and 0 for strong heterophily.The paper uses this distinction to analyze learned propagation behavior across graph types.
  • Over-smoothing: Standard graph convolution repeatedly propagates and transforms node features, but deep propagation can converge to representations determined mainly by node degrees.This convergence removes discriminative information from node features.
  • GPR-GNN architecture: GPR-GNN first extracts hidden features with a neural network and then propagates them through GPR with weights learned end-to-end.The weights adapt each propagation step to the node-label pattern and reveal the learned polynomial graph filter.
  • Related models: APPNP and SGC are special cases of GPR-GNN with fixed propagation-weight choices, while GCN-like alternatives aggregate layer outputs or use Chebyshev polynomial filtering.The compared architectures differ in whether propagation weights and nonlinear transformations are learned flexibly.

4 THEORETICAL PROPERTIES OF GPR-GNNS

Theoretical analysis characterizes GPR-GNN as an adaptive polynomial graph filter and explains how signed weights address heterophily while learned magnitudes reduce over-smoothing.

  • Graph filtering: The GPR component corresponds spectrally to a polynomial graph filter applied to the normalized adjacency eigenvalues.Its response is determined by the polynomial formed from the propagation weights.
  • Graph filtering: Nonnegative normalized GPR weights produce a low-pass filter, whereas sufficiently long weights γ_k = (−α)^k can produce a high-pass filter.The result assumes a connected graph for the stated theorem.
  • Heterophily: Adaptive negative weights allow GPR-GNN to pass relevant high-frequency components that fixed-weight APPNP and SGC suppress.This provides the theoretical explanation for performance on heterophilic graphs.
  • Over-smoothing: When large-step propagation causes over-smoothing, gradient updates drive the corresponding |γ_k| toward zero under suitable SGD learning-rate decay.Reducing these weights removes the dominance of over-smoothed representations in the final output.

5 RESULTS FOR NEW CSBM SYNTHETIC AND REAL-WORLD DATASETS

Experiments on cSBM and real-world benchmarks evaluate GPR-GNN across homophilic and heterophilic settings, with varying feature–topology informativeness and data splits. GPR-GNN is robust across these conditions, while learned weights reflect graph-label structure and can escape over-smoothing.

  • cSBM results: GPR-GNN significantly outperforms all baselines on cSBM whenever φ < 0, while baseline GNNs can underperform MLP when graph information is weak.The cSBM experiments span φ ∈ {−1, −0.75, −0.5, ..., 1} under sparse and dense splitting.
  • Initialization robustness: Random GPR-weight initialization causes only slight performance drops under dense splitting, while remaining strongly superior to baselines on strongly heterophilic graphs.The initialization bias is described as irrelevant when dense splitting provides sufficiently rich label information.
  • Real-world benchmark results: GPR-GNN outperforms tested methods overall on real-world benchmarks, achieving state-of-the-art performance on homophilic datasets and significant gains on heterophilic datasets.The benchmarks include five homophilic and five heterophilic datasets, evaluated using mean accuracy with 95% confidence intervals.
  • Learned-weight interpretation: Learned GPR weights are positive on homophilic datasets but can be negative or zig-zag shaped on heterophilic datasets, indicating different propagation patterns.Actor emphasizes γ0 and node features, whereas Squirrel exhibits a zig-zag pattern associated with more informative topology.
  • Efficiency: GPR-GNN has running time similar to APPNP because learning K+1 additional weights adds computations dominated by the neural-network module.The experiments use K = 10, with K ≤ 20 typically reported for the method.

6 CONCLUSIONS

The paper introduces GPR-GNN to address GNN weaknesses on heterophilic graphs and with many propagation steps, combining adaptive GPR with GNNs. Theory and experiments support reduced over-smoothing, broad label-pattern handling, benchmark gains, and interpretability.

  • GPR-GNN combines adaptive generalized PageRank with GNNs to address limited heterophily generalization and shallow practical architectures.
  • Theoretical analysis shows that GPR-GNN mitigates feature over-smoothing and works across diverse node label patterns.
  • The contextual stochastic block model provides synthetic benchmarks spanning homophilic and heterophilic node-label patterns.
  • Experiments on real-world benchmark datasets show clear performance gains over state-of-the-art methods.
  • GPR-GNN has interpretability properties that the paper identifies as independently valuable.

A.1 DETAILED DISCUSSION ON PREVENTING OVER-SMOOTHING.

APPNP avoids over-smoothing because its propagated features retain dependence on the initial features, but its label-independent low-pass filter cannot adapt to homophilic and heterophilic label assignments. GPR-GNN instead learns label-guided weights that can address both cases.

  • APPNP's asymptotic propagation retains dependence on H(0), so it does not suffer from feature over-smoothing.
  • APPNP's PPR matrix Πppr is independent of node-label information, limiting its ability to adapt its graph filter to label patterns.
  • With identical topology, homophilic labels call for low-frequency emphasis whereas heterophilic bipartite labels call for high-frequency emphasis.
  • GPR-GNN learns GPR weights guided by node labels, allowing one architecture to account for both homophilic and heterophilic cases.

A.2 DISCUSSION ON THE INSUFFICIENCY OF HOMOPHILY MEASURE H(G)

The homophily measure H(G) cannot distinguish heterophilic graphs whose topology carries different amounts of label information. Two examples both have H(G)=0, although only one separates label groups structurally.

  • Both illustrated graph cases have H(G) = 0 because nodes do not connect to nodes sharing their labels.
  • In one case, the topology cannot distinguish blue from green or orange from purple nodes, whereas the second case carries more label information.
  • Chernoff-Hellinger divergence of the empirical edge-probability matrix B is suggested as one possible alternative measure.
  • Finding alternative homophily or heterophily measures remains open because practical graph-generation processes may differ substantially from stochastic block models.

A.3 PROOF OF THEOREM 4.1

The theorem establishes contrasting spectral behavior for GPR filters: nonnegative weights produce low-pass filtering, while alternating weights can produce high-pass filtering. The proof uses the spectrum of a connected graph's normalized adjacency matrix.

  • If γ0 = 1 and some γk′ > 0 for k′ > 0, the theorem gives |gγ,K(λi)/gγ,K(λ1)| < 1 for all i ≥ 2.
  • For γk = (−α)^k with α ∈ (0, 1) and K →∞, the limiting ratio exceeds 1 for every i ≥ 2, corresponding to high-pass behavior.
  • For a connected graph, λ1 = 1 and |λi| < 1 for i ≥ 2, providing the spectral basis for the theorem.
  • A GPR filter with nonnegative coefficients is a polynomial graph filter whose lowest-frequency component becomes dominant.
  • The choice γk = (−α)^k emphasizes high-frequency components, including the boundary λ = −1 associated with bipartite graphs.

A.4 PROOF OF THEOREM 4.2

The proof formalizes over-smoothing in GPR-GNN and shows that gradient updates drive propagation weights away from the over-smoothed regime when the training set contains every class.

  • Definition and setup: The proof analyzes softmax predictions using a smooth parameter and approximates them by an argmax for sufficiently large η.The smoothed softmax converges to the argmax vector as η grows.
  • Definition and setup: Over-smoothing occurs when a dominant propagated representation makes all nodes converge to the same label.For sufficiently large propagation steps, all node representations become proportional to the same vector, up to the sign of the dominant GPR weight.
  • Theorem conclusion: Theorem A.6 concludes that GPR-GNN can always avoid over-smoothing under the stated assumptions.This conclusion applies for sufficiently large k and η and a training set containing nodes from each class.
  • Gradient behavior: When γk > 0, the gradient has the same sign as γk, so gradient descent decreases |γk| under over-smoothing.The corresponding argument for γk < 0 gives a negative gradient, again reducing the magnitude of the weight.
  • Gradient behavior: If the training set contains nodes from every class, the equality condition required for zero gradient cannot occur.The proof uses this condition to establish the strict gradient signs for both positive and negative GPR weights.

A.5 CSBM DETAILS

This section defines the contextual stochastic block model, explains the graph-theoretic ingredients used in the analysis, and documents the synthetic-data and benchmark experimental settings. The experiments include cSBM splits, real-world homophilic and heterophilic datasets, learned-weight visualizations, and an over-smoothing test.

  • cSBM construction: The cSBM augments the classical stochastic block model with Gaussian node features and two equally sized communities.Node labels are represented by ±1, and each feature vector combines a label-dependent signal with Gaussian noise.
  • cSBM construction: The cSBM graph has conditionally independent edges, while μ and λ control the information strength in node features and graph structure.The experiments vary these signal parameters within an achievable regime.
  • Experimental setup: The synthetic experiments use n = 5000 nodes, f = 2000 feature dimensions, ξ = 2.5, and ϵ = 3.25.The parameters μ and λ are varied along λ^2 + μ^2/ξ = 1 + ϵ.
  • Graph analysis: The graph analysis establishes that the normalized adjacency has a simple largest eigenvalue 1 and that all other eigenvalues satisfy 1 > λ2 ≥ ... ≥ λn with |λn| < 1.The strict bound uses connectivity and self-loops, which rule out the bipartite equality case.
  • Experimental setup: Benchmark experiments use dense and sparse cSBM splits alongside homophilic and heterophilic real-world datasets, with reported accuracy confidence intervals.The heterophilic graphs are converted to undirected form for the benchmark methods, while Geom-GCN retains directed inputs.
  • Over-smoothing evaluation: The over-smoothing experiment initializes γk = δkK and compares accuracy at Epoch 0 with the final epoch while recording the ratio of runs producing one label for all nodes.Figure 9 tracks how the GPR weights change across epochs.
Loading 2006.07988v6…