Network In Graph Neural Network

Xiang Song, Runjie Ma, Jiahang Li, Muhan Zhang, David Paul WipfarXiv 2021 · arXiv

Introduction

Scaling Graph Neural Networks (GNNs) typically involves either increasing the hidden dimension (width) or adding more message-passing layers (depth). However, both strategies face significant limitations. Increasing width leads to rapid parameter growth and overfitting, while increasing depth often results in over-smoothing, where node features become indistinguishable due to repeated aggregation. Network In Graph Neural Network (NGNN) is a model-agnostic methodology designed to enhance GNN capacity by incorporating non-linear feedforward layers within each GNN layer, allowing for deeper models without these typical pitfalls.

The Challenges of Scaling GNNs

Traditional scaling methods often encounter a point of diminishing returns due to three primary factors:

  1. Overfitting: Wider layers can easily memorize training data, failing to generalize to unseen nodes.
  2. Over-smoothing: Each additional GNN layer expands the receptive field. While this captures more context, the aggregation process eventually causes node representations to converge, losing local information.
  3. Computational Inefficiency: Parameter counts grow quadratically with the hidden dimension size, making wide models computationally expensive for marginal accuracy gains.
Figure 2: Parameter size increases exponentially with hidden dimension size, highlighting the inefficiency of simply widening GNN layers.

Methodology: Network In Graph Neural Network

Inspired by the "Network In Network" (NIN) architecture from computer vision, NGNN increases depth within each layer rather than adding more inter-layer message-passing steps.

In a standard GNN layer, neighbor features are aggregated and then passed through a single linear transformation. In contrast, an NGNN layer takes the aggregated output and processes it through a multi-layer perceptron (MLP) with one or more non-linear feedforward layers before proceeding to the next GNN layer. This allows for more complex feature transformations at each hop without expanding the receptive field, effectively mitigating over-smoothing. NGNN is model-agnostic and can be integrated into architectures like GCN, GraphSage, GAT, and SEAL.

Experimental Setup

The effectiveness of NGNN was evaluated on large-scale datasets from the Open Graph Benchmark (OGB) and the Reddit dataset:

  • Node Classification: ogbn-products, ogbn-arxiv, ogbn-proteins, and reddit.
  • Link Prediction: ogbl-collab, ogbl-ppa, and ogbl-ddi.

These benchmarks represent diverse real-world graphs, including citation networks and protein-protein interaction maps, featuring millions of nodes and edges.

Results and Analysis

NGNN consistently outperforms baseline GNNs across various metrics, demonstrating superior efficiency and robustness.

Robustness to Structural Noise

A key finding is NGNN's enhanced stability against graph perturbations. When random "noise edges" are added to the graph, NGNN-equipped models maintain higher accuracy compared to vanilla GNNs. This suggests that the intra-layer non-linearity helps the model better filter out irrelevant structural information.

Figure 3: NGNN-GraphSage variants demonstrate significantly better robustness to noisy edges compared to the baseline GraphSage model.

Efficiency and Performance

  • Accuracy Boost: On ogbn-products, NGNN improved GraphSage's test accuracy by 1.6%.
  • State-of-the-Art Results: NGNN reached the top of the ogbl-ppa and ogbl-ddi leaderboards. For ogbl-ppa, it improved the SEAL model's hits@100 score by 7.08%.
  • Parameter Efficiency: On ogbn-proteins, NGNN combined with GAT achieved second place while using 5.8x fewer parameters than the top-performing "RevGNN-Wide" model. This proves that non-linear complexity is often more valuable than raw dimensionality.
  • Training Overhead: The performance gains come at a low cost; for instance, adding NGNN to GraphSage on ogbn-products only increased training time by 3.1%.

Conclusion

NGNN provides a simple yet powerful way to increase GNN capacity. By focusing on intra-layer depth, it avoids the pitfalls of over-smoothing and parameter explosion. While adding too many internal layers (e.g., 4 or more) can eventually lead to overfitting, the optimal configuration of 1 or 2 MLPs per layer offers a significant performance boost. Future research may explore NGNN's utility in broader graph tasks beyond classification and link prediction.

Summary updated

Abstract

Graph Neural Networks (GNNs) have shown success in learning from graph structured data containing node/edge feature information, with application to social networks, recommendation, fraud detection and knowledge graph reasoning. In this regard, various strategies have been proposed in the past to improve the expressiveness of GNNs. For example, one straightforward option is to simply increase the parameter size by either expanding the hid-den dimension or increasing the number of GNN layers. However, wider hidden layers can easily lead to overfitting, and incrementally adding more GNN layers can potentially result in over-smoothing.In this paper, we present a model-agnostic methodology, namely Network In Graph Neural Network (NGNN ), that allows arbitrary GNN models to increase their model capacity by making the model deeper. However, instead of adding or widening GNN layers, NGNN deepens a GNN model by inserting non-linear feedforward neural network layer(s) within each GNN layer. An analysis of NGNN as applied to a GraphSage base GNN on ogbn-products data demonstrate that it can keep the model stable against either node feature or graph structure perturbations. Furthermore, wide-ranging evaluation results on both node classification and link prediction tasks show that NGNN works reliably across diverse GNN architectures.For instance, it improves the test accuracy of GraphSage on the ogbn-products by 1.6% and improves the hits@100 score of SEAL on ogbl-ppa by 7.08% and the hits@20 score of GraphSage+Edge-Attr on ogbl-ppi by 6.22%. And at the time of this submission, it achieved two first places on the OGB link prediction leaderboard.
BibTeX
@misc{song2021network,
  author = {Xiang Song and Runjie Ma and Jiahang Li and Muhan Zhang and David Paul Wipf},
  title = {{Network In Graph Neural Network}},
  year = {2021},
  eprint = {2111.11638},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2111.11638},
}
Figure