Abstract
We propose a novel solution to addressing a long-standing dilemma in the representation learning of graph neural networks (GNNs): how to effectively capture and represent useful information embedded in long-distance nodes to improve the performance of nodes with low homophily without leading to performance degradation in nodes with high homophily. This dilemma limits the generalization capability of existing GNNs. Intuitively, interactions with distant nodes introduce more noise for a node than those with close neighbors. However, in most existing works, messages being passed among nodes are mingled together, which is inefficient from a communication perspective. Our solution is based on a novel, simple, yet effective aggregation scheme, resulting in a ladder-style GNN architecture, namely LADDER-GNN. Specifically, we separate messages from different hops, assign different dimensions for them, and then concatenate them to obtain node representations. Such disentangled representations facilitate improving the information-to-noise ratio of messages passed from different hops. To explore an effective hop-dimension relationship, we develop a conditionally progressive neural architecture search strategy. Based on the searching results, we further propose an efficient approximate hop-dimension relation function to facilitate the rapid configuration of the proposed LADDER-GNN. We verify the proposed LADDER-GNN on seven diverse semi-supervised node classification datasets. Experimental results show that our solution achieves better performance than most existing GNNs. We further analyze our aggregation scheme with two commonly used GNN architectures, and the results corroborate that our scheme outperforms existing schemes in classifying low homophily nodes by a large margin.
The GNN Dilemma: Under-reaching vs. Over-smoothing
Graph Neural Networks (GNNs) have become the standard for modeling graph-structured data. However, they face a persistent challenge: the trade-off between capturing distant context and maintaining signal purity. In high-homophily graphs, nearby neighbors share labels, making local aggregation effective. In low-homophily graphs, critical information often resides further away.
Standard GNNs aggregate messages from neighbors and "mingle" them together. This leads to two primary issues:
- Under-reaching: Limiting the search to 1-2 hops misses distant context.
- Over-smoothing: Deepening the network to reach distant nodes introduces noise that washes out local features, making node embeddings indistinguishable.
A Communication-Centric Solution
The researchers frame GNN message passing as a multi-source communication problem. The target node acts as a "receiver," while neighbors at various distances (hops) are "transmitters." In traditional GNNs, clean local signals are mixed with noisy distant signals, much like trying to listen to a high-fidelity speaker and a static-filled radio at the same volume.
LADDER-GNN addresses this by treating each hop as a separate channel with its own "bandwidth" or embedding dimension. By allocating more dimensions to reliable nearby neighbors and fewer to distant, noisier ones, the model performs a form of "lossy compression" that naturally filters out noise while preserving structural signals.
The LADDER-GNN Architecture
The architecture is built on three key pillars:
- Disentangled Representations: Instead of summing messages, LADDER-GNN aggregates information within each hop independently and then concatenates them. This prevents distant noise from polluting local features.
- Hop-Aware Dimension Allocation: Embedding sizes shrink as distance from the target node increases, creating a "ladder" shape.
- Progressive Neural Architecture Search (NAS): A search strategy identifies the optimal dimensions for each hop.
To reduce the computational cost of NAS, the authors discovered that optimal dimensions typically follow an exponentially decreasing function. They provide an "Approx" shortcut—a simple formula that yields near-optimal results without the expensive search.
Key Results and Insights
Evaluated across seven benchmarks, including citation networks (Cora, Citeseer) and large-scale datasets (OGB-Arxiv, OGB-Products), LADDER-GNN demonstrated significant improvements:
- Performance Boost: It enhanced standard GCN and GAT models by up to 4.7%.
- Low-Homophily Excellence: It significantly outperformed existing GNNs on nodes where neighbors are dissimilar, proving its ability to extract signal from noise.
- State-of-the-Art: LADDER-GNN achieved top-tier results on OGB leaderboards, surpassing complex models like JKNet and DeepGCN.
Conclusion
LADDER-GNN offers a theoretically grounded and practically efficient solution to the over-smoothing problem. By treating dimensionality as a filter and disentangling hop-wise information, it allows GNNs to "climb the ladder" to distant nodes without losing their footing in local context.
Summary updated