Source-linked AI summary
Diffusion Improves Graph Learning
Johannes Gasteiger, Stefan Weißenberger, Stephan Günnemann
TL;DR
GNNs usually rely on one-hop message passing, motivating a method that captures broader graph structure without losing spatial locality. GDC uses sparsified generalized graph diffusion, connects spatial and spectral views, and consistently improves diverse graph models across supervised and unsupervised tasks. Its main scope boundary is the assumption of homophily, with concerns for complex-edge and link-prediction settings.
Problem
GNN message passing uses direct neighbors, while spectral models capture broader structure but do not generalize to previously unseen graphs.
Method
GDC replaces ordinary adjacency with a sparsified generalized graph-diffusion graph and can be used with GNNs or other graph-based models.
Results
GDC consistently improves accuracy across a wide range of models on supervised and unsupervised tasks and various homophilic datasets.
Takeaways & Limitations
GDC provides a spatially localized graph convolution that combines strengths of spatial and spectral methods and can be applied in a plug-and-play manner.
Takeaways & Limitations
GDC assumes homophily and may perform poorly with complex edges or graph reconstruction tasks such as link prediction.
Abstract
from arXiv · showhide
Graph convolution is the core of most Graph Neural Networks (GNNs) and usually approximated by message passing between direct (one-hop) neighbors. In this work, we remove the restriction of using only the direct neighbors by introducing a powerful, yet spatially localized graph convolution: Graph diffusion convolution (GDC). GDC leverages generalized graph diffusion, examples of which are the heat kernel and personalized PageRank. It alleviates the problem of noisy and often arbitrarily defined edges in real graphs. We show that GDC is closely related to spectral-based models and thus combines the strengths of both spatial (message passing) and spectral methods. We demonstrate that replacing message passing with graph diffusion convolution consistently leads to significant performance improvements across a wide range of models on both supervised and unsupervised tasks and a variety of datasets. Furthermore, GDC is not limited to GNNs but can trivially be combined with any graph-based model or algorithm (e.g. spectral clustering) without requiring any changes to the latter or affecting its computational complexity. Our implementation is available online.
1 Introduction
GNNs predominantly use one-hop message passing, while spectral models capture broader graph structure but often generalize poorly. GDC extends message passing with localized graph diffusion to combine these strengths.
- GNNs typically aggregate messages from direct neighbors to form node embeddings layer by layer.
- Spectral models capture more complex graph properties but are routinely outperformed by message-passing models and do not generalize to unseen graphs.
- GDC aggregates information from larger neighborhoods constructed by sparsifying generalized graph diffusion.
- GDC is spatially localized, scalable, compatible with message passing, and applicable to unseen graphs.
- The paper proposes GDC, analyzes its spectral properties, and evaluates variants across supervised and unsupervised graph learning.
2 Generalized graph diffusion
Generalized graph diffusion combines transition matrices with weighting coefficients to aggregate information across multiple graph distances. PPR, the heat kernel, and standard GCN convolution arise as specific choices within this framework.
- Generalized graph diffusion is defined using a transition matrix T and weighting coefficients θ_k, with convergence requiring conditions on their values and T’s eigenvalues.
- For undirected graphs, transition matrices include random-walk and symmetric forms, with optional weighted self-loops implementing a lazy random walk.
- Personalized PageRank and the heat kernel are popular graph-diffusion special cases using random-walk transitions.
- The standard GCN convolution corresponds to one-step diffusion with θ_1 = 1, θ_k = 0 for k ≠ 1, and a symmetric transition matrix with unit self-loops.
- PPR and heat-kernel coefficients have closed-form series solutions and outperform coefficients learned through label propagation and node-embedding models in the investigated experiments.
3 Graph diffusion convolution
GDC replaces the adjacency matrix with a sparsified generalized diffusion graph, using diffusion to smooth noisy neighborhoods while preserving spatial locality. Its main scope is homophilic graphs, with limitations for heterophily, complex edges, and link prediction.
- GDC replaces the adjacency matrix A with a sparsified generalized diffusion matrix and applies the existing model to the resulting weighted directed graph.
- Graph diffusion smooths neighborhoods as a denoising filter, addressing noise in real-graph features and edges.
- Sparsification truncates localized diffusion values using top-k or thresholding, while fast PPR and heat-kernel approximations give GDC linear runtime O(N).
- GDC assumes homophily, and extending it to heterophily may require negative edge weights.
- The authors suspect weaker performance on complex-edge settings and graph reconstruction tasks; preliminary experiments found no link-prediction improvement.
4 Spectral analysis of GDC
GDC admits a spectral interpretation as a polynomial graph filter while retaining spatial localization and avoiding key limitations of spectral-based models. Its diffusion and sparsification steps primarily produce low-pass behavior, preserving useful spectral structure while suppressing noise and undesired interactions.
- GDC is a spatial method that can be interpreted as a graph convolution and analyzed in the graph spectral domain.
- Graph diffusion as a polynomial filter: Generalized graph diffusion corresponds directly to a polynomial spectral filter after exchanging the Laplacian L with the transition matrix T.
- Spectral properties of GDC: GDC’s four stages are transition-matrix calculation, diffusion summation, sparsification, and transition-matrix calculation on the sparsified graph.
- Spectral properties of GDC: Heat-kernel and PPR diffusions act as low-pass filters, amplifying low eigenvalues linked to large-scale structure and suppressing high eigenvalues linked to detail and noise.
- Spectral properties of GDC: Typical sparsification thresholds empirically have almost no effect on eigenvalues, with changes concentrated mainly at the highest and lowest eigenvalues.
- Unlike spectral-based models, GDC avoids expensive eigendecomposition, preserves locality, and can generalize across graphs using shared coefficients.
5 Related work
Graph diffusion and random walks have established roles in classical graph learning, while GNN research distinguishes spectral and spatial approaches. Prior work has explored extended-neighborhood aggregation and diffusion-based propagation through several specialized methods.
- Graph diffusion and random walks have been studied for clustering, semi-supervised classification, and recommendation systems.
- GNNs are generally classified into spectral-based models using graph-Laplacian eigendecomposition and spatial-based models using local graph structure.
- Prior methods used personalized PageRank, k-hop random walks, heat kernels, and maximal-entropy random walks for extended-neighborhood aggregation or node propagation.
6 Experimental results
Across supervised and unsupervised experiments, GDC improved graph-model accuracy while remaining effective with sparse, localized diffusions. Results also identify practical choices for transition matrices, coefficients, sparsification, label rates, and node distance.
- Semi-supervised node classification: GDC consistently and significantly improved semi-supervised node-classification accuracy across diverse models and datasets, including models that otherwise broke down.It surpassed or matched previous state of the art on all investigated datasets.
- Clustering: GDC consistently and significantly improved clustering accuracy across models and datasets, with spectral clustering gaining up to 30 percentage points.The improvement occurred even though spectral clustering’s eigenvectors are not affected by the diffusion step itself.
- Scope and limitations: The experiments focused on transductive node-level prediction; graph-classification results were promising but less consistent, and no improvement was found for inductive PPI.For example, GCN on DD improved by 2.5 percentage points.
- Sparsification: Sparsification improved prediction performance at an optimal degree, while GDC surpassed the original graph at roughly the same average degree across datasets.At constant accuracy, GDC is expected to reduce average degree on larger graphs.
- Transition matrix: The symmetric transition matrix Tsym performed best across datasets; GCN accuracy was largely insensitive to self-loops, whereas GAT performed better with them.The comparison found the symmetric transition matrix generally outperformed the random-walk transition matrix Trw.
- Weighting coefficients: PPR and heat-kernel coefficients were effective, with optimal α ∈[0.05, 0.2] and t ∈[1, 10]; trained coefficients often collapsed to minimal neighborhoods.Even with hand-tuned regularization, PPR and heat-kernel coefficients outperformed learned coefficients.
- Label rate and node distance: GDC’s improvement increased as labels became sparser and was larger for nodes farther from the training set.GDC still improved performance at 60 labels per class, corresponding to a 17 % label rate; its broader range helps nodes distant from training data.
7 Conclusion
The conclusion presents GDC as a sparsified graph-diffusion method that extends message passing while remaining spatially localized and applicable beyond GNNs. It connects graph diffusion to spectral models and reports broad empirical gains with limited tuning.
- GDC uses sparsified generalized graph diffusion as a more powerful, spatially localized extension of message passing.
- GDC is closely connected to spectral-based models through an equivalent polynomial-filter representation and spectral analysis.
- GDC can enhance graph-based models beyond GNNs while preserving the strengths of spectral methods without their stated weaknesses.
- Experiments report consistent accuracy improvements across diverse models, supervised and unsupervised tasks, and homophilic datasets with little hyperparameter tuning.
- The conclusion identifies unexplored extensions involving graph classification, regression, alternative diffusion coefficients, random walks, and operators beyond transition-matrix powers.
B Experiments
The experiments use fixed dataset splits, repeated randomized evaluation, controlled preprocessing settings, and bootstrap confidence intervals across implementations and graph variants.
- Hyperparameters are optimized on development sets, while held-out test sets are used only once for final evaluation.Development sets contain 1500 nodes, or 5000 for COAUTHOR CS; training uses 20 nodes per class.
- Accuracy is evaluated over 100 random splits, whereas clustering results are averaged over 20 randomly initialized runs.
- Confidence intervals are estimated by bootstrapping results from 100 or 20 runs with 1000 samples.
- Experiments use PyTorch and PyTorch Geometric for node classification and DGI, with NumPy, SciPy, graph-tool, gensim, and scikit-learn elsewhere.
- All experiments select the largest connected component and evaluate PPR, heat-kernel, top-k, and threshold-based preprocessing over specified hyperparameter ranges.
B.1 Datasets
The appendix includes a dataset-statistics table for the datasets used in the study.
- Table 1 reports statistics for the study’s datasets.
- The dataset statistics are presented in tabular form.
- The appendix identifies dataset characteristics through a dedicated statistics table.
B.2 Results
The results section compares GDC with APPNP and reports accuracy tables across several datasets, alongside spectral and sparsification analyses. Figures examine how sparsification changes accuracy and eigenvalues.
- APPNP results are included as a state-of-the-art comparison for semi-supervised node classification because it uses graph diffusion internally.
- Accuracy results are tabulated for CORA, CITESEER, PUBMED, COAUTHOR CS, AMZ COMP, and AMZ PHOTO with bootstrap-estimated 95% confidence levels.
- Sparsification primarily affects the Laplacian’s lowest and highest eigenvalues, while GDC can surpass original accuracy at comparable graph degree.
B.3 Hyperparameters
This section lists the hyperparameters selected for the evaluated models and algorithms using grid and random search.
- Hyperparameters for GCN and GAT were obtained through grid and random search.
- The same grid-and-random-search procedure was used for JK, GIN, ARMA, and APPNP.
- Hyperparameters for DCSBM, spectral clustering, DeepWalk, and DGI were also obtained through grid and random search.