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.
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:
- Hop-wise Attention (HA): This allows the model to learn, for each individual node, which neighborhood distance is most important.
- 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.
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, andogbl-ddiat the time of submission. - Efficiency vs. RevGNNs: On the
ogbn-proteinsdataset, 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