Learn Layer-wise Connections in Graph Neural Networks

Lanning Wei, Huan Zhao, Zhiqiang HearXiv 2021 · arXiv

Introduction

Deep Graph Neural Networks (GNNs) often suffer from "over-smoothing," where node representations become indistinguishable as network depth increases. While manual architectural solutions like skip connections (ResNet) or feature concatenation (DenseNet) have been proposed, their effectiveness varies significantly across different graph datasets. The Learn Layer-wise Connections (LLC) framework addresses this by using Neural Architecture Search (NAS) to automatically design data-specific information flow between layers.

Methodology: The LLC Framework

The LLC framework treats GNN connectivity as a searchable optimization problem. The model's architecture is represented as a Directed Acyclic Graph (DAG) comprising a pre-processing block, multiple GNN blocks, and a post-processing block.

The LLC search space: (a) shows the 4-layer backbone where each node can connect to any predecessor; (b) details the internal structure of a GNN block with a learned fusion function.

Search Space and Optimization

Each block in the DAG can receive input from any preceding block. For every potential connection, the framework learns to choose between an IDENTITY operation (active connection) or a ZERO operation (no connection). When multiple inputs are selected, they are merged using a learned fusion function, such as SUM, MEAN, MAX, CONCAT, LSTM, or ATTENTION.

To make this search efficient, LLC employs a differentiable search algorithm using Gumbel-Softmax relaxation. This allows the architecture to be optimized via standard gradient descent alongside network weights in a bi-level optimization process.

Experimental Evaluation

The researchers evaluated LLC on five diverse benchmarks: citation networks (Cora, PubMed, DBLP), a co-purchase network (Amazon Computer), and a co-authorship network (Physics). Preliminary studies using GraphGym on 14 datasets confirmed that no single manual architecture (like ResNet or JKNet) consistently outperforms others, justifying the need for automated search.

Key Insights and Results

LLC consistently achieved state-of-the-art performance, outperforming standard stacking and manual skip-connection baselines. For instance, on the Cora dataset with a GAT backbone, LLC reached an accuracy of 0.8777, surpassing the best manual baseline (JKNet) at 0.8655.

Diverse Architectures for Diverse Data

A primary finding was that optimal architectures are highly dataset-dependent. For example, the searched architecture for Cora exhibits a complex multi-branch structure, whereas other datasets might favor denser connectivity.

An example of a searched architecture for GraphSAGE on the Cora dataset, illustrating the non-trivial connectivity patterns discovered by LLC.

Mitigating Over-smoothing

By analyzing the Metric for Smoothness (MAD index), the authors demonstrated that LLC maintains higher feature diversity than standard stacked GNNs. The framework effectively "rescues" deep models by allowing deeper layers to access "sharper" information from shallower blocks or the original input features. This is supported by the observation that the input block is frequently selected by subsequent layers.

Conclusion and Future Work

LLC demonstrates that learning layer-wise connections is a powerful way to enhance GNN capacity and robustness to depth. Future research will focus on simultaneously searching for internal aggregation operators (e.g., GCN vs. GAT) and exploring the theoretical links between graph properties, such as homophily, and the resulting optimal architectures.

Summary updated

Abstract

In recent years, Graph Neural Networks (GNNs) have shown superior performance on diverse applications on real-world datasets. To improve the model capacity and alleviate the over-smoothing problem, several methods proposed to incorporate the intermediate layers by layer-wise connections. However, due to the highly diverse graph types, the performance of existing methods vary on diverse graphs, leading to a need for data-specific layer-wise connection methods. To address this problem, we propose a novel framework LLC (Learn Layer-wise Connections) based on neural architecture search (NAS) to learn adaptive connections among intermediate layers in GNNs. LLC contains one novel search space which consists of 3 types of blocks and learnable connections, and one differentiable search algorithm to enable the efficient search process. Extensive experiments on five real-world datasets are conducted, and the results show that the searched layer-wise connections can not only improve the performance but also alleviate the over-smoothing problem.
BibTeX
@misc{wei2021learn,
  author = {Lanning Wei and Huan Zhao and Zhiqiang He},
  title = {{Learn Layer-wise Connections in Graph Neural Networks}},
  year = {2021},
  eprint = {2112.13585},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2112.13585},
}
Figure