Relational Graph Neural Network Design via Progressive Neural Architecture Search

Ailing Zeng, Minhao Liu, Zhiwei Liu, Ruiyuan Gao, Jing Qin, Qiang Xu

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.

Introduction

Graph Neural Networks (GNNs) have revolutionized representation learning on graphs by aggregating information from local neighborhoods. However, they face a persistent challenge: balancing the need for long-range context with the risk of over-smoothing. Standard GNNs often suffer from "under-reaching" when limited to a few hops, failing to capture global structure. Conversely, increasing depth to reach distant nodes often leads to "over-smoothing," where node representations become indistinguishable.

This paper identifies message mingling—the practice of summing or averaging messages from all neighbors into a single vector—as the primary culprit. From a communication perspective, this is like trying to listen to a clear whisper nearby while someone else is shouting nonsense from across the room; the "clean" local signal gets drowned out by "noisy" distant signals.

The LADDER-GNN Framework

To address this, the authors introduce LADDER-GNN, which treats message passing as a multi-source communication problem. Instead of mixing all incoming signals, LADDER-GNN disentangles messages based on their hop distance.

Comparison of information aggregation schemes from a communication perspective.

As shown in the figure above, the core innovation is the "ladder" structure. By assigning different dimensions (channel capacities) to different hops—typically more for closer, more reliable neighbors and fewer for distant, noisier ones—the model can effectively filter information. This disentangled representation allows the network to preserve high-fidelity local features while still benefiting from distant context.

The implementation of LADDER-GNN follows a structured workflow involving in-hop aggregation, dimension search, and final concatenation.

The LADDER-GNN workflow: from aggregation to final embedding.

To optimize the "ladder" shape (the specific dimensionality for each hop), the authors employ a Reinforcement Learning-based Progressive Neural Architecture Search (NAS). The NAS results consistently showed that the most accurate models allocated the most dimensions to Hop-1 and Hop-2, with dimensions dropping off sharply for higher hops. Recognizing the computational cost of NAS, they also derive an Approximate Hop-Dimension Function—an exponential decay formula that approximates the optimal search results, providing a fast and effective configuration for practical use.

Experimental Evaluation

LADDER-GNN was evaluated across seven diverse datasets, including citation networks (Cora, Citeseer, Pubmed), large-scale benchmarks (OGB-Arxiv, OGB-Products), and heterogeneous graphs. Key findings include:

  • Accuracy Boost: LADDER-GNN consistently outperformed state-of-the-art models, boosting standard GCN and GAT performance by up to 4.7%.
  • Superiority in Low Homophily: The model excels in graphs where nodes are dissimilar to their neighbors (low homophily), as it can selectively leverage relevant distant information without being overwhelmed by local noise.
  • Efficiency: The approximate configuration achieved performance parity with the full NAS-searched models, demonstrating the practical utility of the derived hop-dimension relationship.

Conclusion

LADDER-GNN offers a scalable and effective solution to the over-smoothing problem in GNNs. By treating aggregation as a communication task and disentangling hop-specific information, it enables deeper architectures that maintain high representational power. Future work includes exploring joint optimization of graph topology and architecture, as well as scaling to massive, web-scale graphs.

Summary updated

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.
BibTeX
@misc{zeng2021relational,
  author = {Ailing Zeng and Minhao Liu and Zhiwei Liu and Ruiyuan Gao and Jing Qin and Qiang Xu},
  title = {{Relational Graph Neural Network Design via Progressive Neural Architecture Search}},
  year = {2021},
  eprint = {2105.14490},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2105.14490},
}
Figure