Adaptive Graph Diffusion Networks

Chuxiong Sun, Jie Hu, Hongming Gu, Jinpeng Chen, Mingchuan Yang

Abstract

Graph Neural Networks (GNNs) have received much attention in the graph deep learning domain. However, recent research empirically and theoretically shows that deep GNNs suffer from over-fitting and over-smoothing problems. The usual solutions either cannot solve extensive runtime of deep GNNs or restrict graph convolution in the same feature space. We propose the Adaptive Graph Diffusion Networks (AGDNs) which perform multi-layer generalized graph diffusion in different feature spaces with moderate complexity and runtime. Standard graph diffusion methods combine large and dense powers of the transition matrix with predefined weighting coefficients. Instead, AGDNs combine smaller multi-hop node representations with learnable and generalized weighting coefficients. We propose two scalable mechanisms of weighting coefficients to capture multi-hop information: Hop-wise Attention (HA) and Hop-wise Convolution (HC). We evaluate AGDNs on diverse, challenging Open Graph Benchmark (OGB) datasets with semi-supervised node classification and link prediction tasks. AGDNs achieve top-1 performance on the ogbn-arxiv, ogbn-proteins and ogbl-ddi datasets and top-3 performance on the ogbl-citation2 dataset. On Tesla V100 GPU cards, AGDNs outperform Reversible GNNs (RevGNNs) with 13% complexity and 1% training runtime on the ogbn-proteins dataset.

Introduction: The Depth Dilemma in GNNs

Graph Neural Networks (GNNs) are the standard for data structured as networks, such as social media, protein interactions, or citation webs. However, they face a significant "Goldilocks" problem regarding depth. Shallow GNNs often fail to capture long-range relationships between distant nodes, while deep GNNs frequently suffer from over-smoothing, where node representations become nearly identical after multiple rounds of message passing, and over-fitting due to redundant feature transformations.

Existing solutions often force a trade-off. "Decoupled" GNNs are fast but lack the capacity to learn complex hierarchies because they restrict graph operations to a single feature space. Conversely, massive models like Reversible GNNs (RevGNNs) can scale deep but are computationally expensive and slow to train. Adaptive Graph Diffusion Networks (AGDNs) offer a middle ground: a model that is deep, adaptive, and highly efficient.

Methodology: Adaptive Graph Diffusion

The core innovation of AGDNs lies in how the model aggregates information from multiple "hops" (distances) away in the graph without the typical computational bloat.

The architecture of an AGDN layer, illustrating the flow from input $H^{(l-1)}$ to output $H^{(l)}$ through multi-hop diffusion and learnable weighting.

Implicit Diffusion and Pseudo-symmetric Adjacency

Instead of pre-calculating massive, dense matrices representing multi-hop connections—which is memory-intensive—AGDNs calculate multi-hop representations iteratively. This "right-to-left" matrix multiplication keeps the memory footprint small. Furthermore, the authors propose a Pseudo-symmetric Adjacency normalization technique that balances the importance of a node's incoming and outgoing connections, improving training stability.

Learnable Weighting Mechanisms

Standard diffusion methods use fixed, predefined weights for different hops. AGDNs replace these with two learnable mechanisms to capture multi-hop information dynamically:

  1. Hop-wise Attention (HA): This allows the model to learn, for each individual node, which neighborhood distance is most important.
  2. Hop-wise Convolution (HC): This treats different hops as a sequence and applies a learnable filter across them, allowing different feature channels to prioritize different distances.
Illustration of the Hop-wise Attention (HA) and Hop-wise Convolution (HC) mechanisms and their corresponding parameter tensors.

Mathematically, the HC mechanism is equivalent to learning a polynomial filter in the spectral domain, allowing the model to approximate a wide variety of graph filters without the heavy computation of traditional spectral GNNs.

Experimental Evaluation

The researchers evaluated AGDNs using the Open Graph Benchmark (OGB), covering node classification (ogbn-arxiv, ogbn-proteins, ogbn-products) and link prediction (ogbl-ppa, ogbl-ddi, ogbl-citation2).

Key Results

AGDNs demonstrated state-of-the-art performance and remarkable efficiency:

  • Leaderboard Dominance: Achieved Top-1 performance on ogbn-arxiv, ogbn-proteins, and ogbl-ddi at the time of submission.
  • Efficiency vs. RevGNNs: On the ogbn-proteins dataset, AGDNs outperformed RevGNNs while using only 13% of the complexity and 1% of the training runtime.
  • Speed vs. SEAL: For link prediction on ogbl-citation2, AGDNs achieved comparable results to the SEAL model but were 500x faster during inference.
  • Mitigating Over-smoothing: Ablation studies showed that the HA/HC mechanisms effectively prevent node features from washing out, even as network depth increases.

Conclusion

Adaptive Graph Diffusion Networks provide a scalable and efficient framework for deep graph learning. By utilizing implicit diffusion and learnable weighting mechanisms like Hop-wise Attention and Convolution, AGDNs overcome the traditional barriers of over-smoothing and high computational cost. Future work may involve optimizing neighbor sampling for even deeper architectures and further refining memory scaling for massive-scale graphs.

Summary updated

Abstract

Graph Neural Networks (GNNs) have received much attention in the graph deep learning domain. However, recent research empirically and theoretically shows that deep GNNs suffer from over-fitting and over-smoothing problems. The usual solutions either cannot solve extensive runtime of deep GNNs or restrict graph convolution in the same feature space. We propose the Adaptive Graph Diffusion Networks (AGDNs) which perform multi-layer generalized graph diffusion in different feature spaces with moderate complexity and runtime. Standard graph diffusion methods combine large and dense powers of the transition matrix with predefined weighting coefficients. Instead, AGDNs combine smaller multi-hop node representations with learnable and generalized weighting coefficients. We propose two scalable mechanisms of weighting coefficients to capture multi-hop information: Hop-wise Attention (HA) and Hop-wise Convolution (HC). We evaluate AGDNs on diverse, challenging Open Graph Benchmark (OGB) datasets with semi-supervised node classification and link prediction tasks. Until the date of submission (Aug 26, 2022), AGDNs achieve top-1 performance on the ogbn-arxiv, ogbn-proteins and ogbl-ddi datasets and top-3 performance on the ogbl-citation2 dataset. On the similar Tesla V100 GPU cards, AGDNs outperform Reversible GNNs (RevGNNs) with 13% complexity and 1% training runtime of RevGNNs on the ogbn-proteins dataset. AGDNs also achieve comparable performance to SEAL with 36% training and 0.2% inference runtime of SEAL on the ogbl-citation2 dataset.
BibTeX
@misc{sun2020adaptive,
  author = {Chuxiong Sun and Jie Hu and Hongming Gu and Jinpeng Chen and Mingchuan Yang},
  title = {{Adaptive Graph Diffusion Networks}},
  year = {2020},
  eprint = {2012.15024},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2012.15024},
}
Figure