Diffusion Improves Graph Learning

By Johannes Klicpera, Stefan Weißenberger, Stephan Günnemann. Neural Information Processing Systems, 2019

890 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Cognitive Neuroscience, Information Systems

View Paper: https://www.semanticscholar.org/paper/2a6d160b529272964ce1a6707adf52f3d6ba4861

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

In Cognitive Neuroscience

In Information Systems

Citations in the corpus

Graph Contrastive Learning with Adaptive Augmentation (2020, methodology): “dges respectively, without explicit data augmentation. Moreover, to supplement the input graph with more global information, MVGRL [16] proposes to augment the input graph via graph diffusion kernels [24]. Then, it constructs graph views by uniformly sampling subgraphs and learns to contrast node re”
Language-Agnostic Representation Learning of Source Code from Structure and Context (2021, background): “…GNNs have achieved state-of-the-art performance across a variety of tasks, such as node classiﬁcation (Kipf & Welling, 2017; Hamilton et al., 2017; Klicpera et al., 2019a), link prediction (Zhang & Chen, 2018; Schlichtkrull et al., 2018), graph clustering (Defferrard et al., 2016; Ying et al.,…”
GRAND: Graph Neural Diffusion (2021, methodology): “Choosing different spatial discretisation amounts to graph rewiring, a technique recently used to improve the performance of GNNs (Klicpera et al., 2019; Alon & Yahav, 2021).”
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.”
Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning (2020, methodology): “(4)) while GDC [32] and PowerGNN [48] used variants of ζ gpr ( u | v ) .”
How Powerful are Spectral Graph Neural Networks (2022, methodology): “Theoretically, it still has the same time complexity O(Kmd) as APPNP and GPRGNN, where K is the degree of the polynomial, m is the number of edges in the graph, and d is the number of node feature dimensions, while BernNet’s time complexity is O(K2md).”
Adaptive Universal Generalized PageRank Graph Neural Network (2020, background): “In contrast, recent GNN models that utilize Personalized PageRanks (PPR) with fixed weights (Wu et al., 2019; Klicpera et al., 2018; 2019) inevitably act as low-pass filters.”
How to Find Your Friendly Neighborhood: Graph Attention Design with Self-Supervision (2022, background): “Graph structure learning is an approach to learn the underlying graph structure while jointly learning downstream tasks (Jiang et al., 2019; Franceschi et al., 2019; Klicpera et al., 2019; Stretcu et al., 2019; Zheng et al., 2020).”
From Canonical Correlation Analysis to Self-supervised Graph Neural Networks (2021, background): “MVGRL [15] generalizes CMC [40] to graph-structured data by introducing graph diffusion [23] to create another view for a graph.”
Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning (2021, methodology): “Some recent works try to improve GNNs in different directions, such as simplifying the computational complexity [37], [38], training with adversarial scheme [39], applying to large-scale graphs [40], [41], [42], and introducing novel operators [8], [43].”
Understanding over-squashing and bottlenecks on graphs via curvature (2021, methodology): “The property that the new Cheeger constant is directly controlled by the old one stems from the fact that a random-walk approach like in Klicpera et al. (2019) is meant to act more relevantly on intra-community edges rather than inter-community edges because it prioritizes short diffusion distance…”
BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation (2021, methodology): “P kx, we obtain the polynomial filtering operation for the heat kernal based GNN such as GDC [15] and GraphHeat [34].”
Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings (2020, methodology): “In addition, for citation network datasets, we include other GNN variants (i.e., GCN [27], GAT [48], GraphSage [17], APPNP [28], H-GCN [19] and GDC [29]) as baselines.”
Graph Self-Supervised Learning: A Survey (2021, methodology): “modifying edges, or other alternative ways like subgraph sampling and graph diffusion [76], which provides limited diversity and uncertain invariance when generating multiple graph views.”
Graph Neural Networks in Recommender Systems: A Survey (2020, background): “In addition, some recent graph diffusion-based works [73, 74, 108] decouple the operations of aggregation and update and embrace a larger reception field with a larger aggregation step.”
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).”
SIGN: Scalable Inception Graph Neural Networks (2020, methodology): “On the smaller transductive datasets, we compare to the well established methods GCN Kipf and Welling (2017), GAT Velickovic et al. (2018), JK Xu et al. (2018), GIN Xu et al. (2019), ARMA Bianchi et al. (2019b), and the current state-of-the-art DIGL Klicpera et al. (2019).”