NodeMixup: Tackling Under-Reaching for Graph Neural Networks

Weigang Lu, Ziyu Guan, Wei Zhao, Yaming Yang, Long Jin

Abstract

Graph Neural Networks (GNNs) have become mainstream methods for solving the semi-supervised node classification problem. However, due to the uneven location distribution of labeled nodes in the graph, labeled nodes are only accessible to a small portion of unlabeled nodes, leading to the under-reaching issue. In this study, we firstly reveal under-reaching by conducting an empirical investigation on various well-known graphs. Then, we demonstrate that under-reaching results in unsatisfactory distribution alignment between labeled and unlabeled nodes through systematic experimental analysis, significantly degrading GNNs' performance. To tackle under-reaching for GNNs, we propose an architecture-agnostic method dubbed NodeMixup. The fundamental idea is to (1) increase the reachability of labeled nodes by labeled-unlabeled pairs mixup, (2) leverage graph structures via fusing the neighbor connections of intra-class node pairs to improve performance gains of mixup, and (3) use neighbor label distribution similarity incorporating node degrees to determine sampling weights for node mixup. Extensive experiments demonstrate the efficacy of NodeMixup in assisting GNNs in handling under-reaching.

Introduction

In semi-supervised node classification, models typically rely on a small set of labeled nodes to propagate information across a vast graph of unlabeled data. Most popular GNNs are "shallow" (typically 2 layers) to avoid issues like over-smoothing—where node features become indistinguishable—or over-squashing, where information from distant nodes is lost during message passing. However, this shallow architecture introduces a critical bottleneck: under-reaching.

Under-reaching occurs because labeled nodes are often clustered in specific regions of a graph. Consequently, many unlabeled nodes—particularly those with low connectivity—are topologically distant from any labeled data. Because a standard 2-layer GNN can only aggregate information from its two-hop neighborhood, these distant nodes never receive supervision signals during training, leading to poor generalization.

The Under-Reaching Phenomenon

Empirical investigations reveal a strong connection between node degree and reachability. As shown in the figure below, there is a clear trend across multiple datasets: low-degree nodes are statistically much further away from labeled nodes (measured by average shortest path) than high-degree nodes.

Average shortest path (Avg. SP) to labeled nodes vs. node degree across four datasets, illustrating that low-degree nodes are statistically further from labeled data.

This distance creates a "distribution misalignment" where the model learns representations for labeled areas that fail to generalize to the rest of the graph. The authors found a clear positive correlation between a node's reachability to labeled data and the model's ability to classify it correctly, as evidenced by Pearson correlation analysis across various GNN backbones.

Pearson correlation between reachability and classification accuracy across various GNN architectures, demonstrating the impact of under-reaching on performance.

The NodeMixup Framework

To address this, the authors propose NodeMixup, an architecture-agnostic data augmentation framework that breaks the constraints of physical graph edges by creating "virtual" training examples through interpolation. Its core components include:

  1. Cross-set Pairing: Unlike traditional Mixup which blends labeled nodes, NodeMixup pairs labeled nodes with pseudo-labeled unlabeled nodes. This directly forces the model to "reach" into the unlabeled regions of the graph.
  2. Topology Fusing:
    • Intra-class Mixup: When mixing nodes of the same class, the method fuses their neighbor connections (adjacency rows/columns). This encourages the model to learn that these nodes share similar topological roles.
  3. Inter-class Mixup: When mixing nodes of different classes, the model uses an identity matrix to block message passing, helping the model learn sharper decision boundaries without introducing topological noise.
  4. NLD-aware Sampling: Instead of random pairing, NodeMixup uses Neighborhood Label Distribution (NLD) similarity. It calculates how similar the predicted labels of a node's neighbors are to another node's neighbors. It specifically assigns higher sampling weights to low-degree nodes, ensuring the most isolated nodes benefit most from the augmentation.

Experimental Results

NodeMixup was evaluated as a "plug-and-play" addition to several backbones, including GCN, GAT, APPNP, and GraphSAGE, across standard benchmarks and large-scale datasets like ogbn-arxiv.

  • Consistent Performance Gains: NodeMixup outperformed original GNNs and other state-of-the-art methods like GraphMix and ReNode. For instance, on the PubMed dataset with a GCN backbone, accuracy improved from 77.91% to 81.16%.
  • Scalability: On the challenging ogbn-arxiv dataset, NodeMixup helped a standard GCN (71.74%) outperform deeper architectures like GCNII (72.74%) by reaching 73.46% accuracy.
  • Ablation Studies: Results confirmed that "Labeled-Unlabeled" (LU) pairing is significantly more effective than traditional "Labeled-Labeled" (LL) pairing for mitigating under-reaching.

Conclusion

NodeMixup effectively bridges the information gap in shallow GNNs by manufacturing reachability through intelligent node interpolation. By prioritizing low-degree nodes and leveraging neighborhood topology, it ensures that supervision signals reach the most isolated parts of the graph, leading to more robust and accurate node classification.

Summary updated

Abstract

Graph Neural Networks (GNNs) have become mainstream methods for solving the semi-supervised node classification problem. However, due to the uneven location distribution of labeled nodes in the graph, labeled nodes are only accessible to a small portion of unlabeled nodes, leading to the \emph{under-reaching} issue. In this study, we firstly reveal under-reaching by conducting an empirical investigation on various well-known graphs. Then, we demonstrate that under-reaching results in unsatisfactory distribution alignment between labeled and unlabeled nodes through systematic experimental analysis, significantly degrading GNNs' performance. To tackle under-reaching for GNNs, we propose an architecture-agnostic method dubbed NodeMixup. The fundamental idea is to (1) increase the reachability of labeled nodes by labeled-unlabeled pairs mixup, (2) leverage graph structures via fusing the neighbor connections of intra-class node pairs to improve performance gains of mixup, and (3) use neighbor label distribution similarity incorporating node degrees to determine sampling weights for node mixup. Extensive experiments demonstrate the efficacy of NodeMixup in assisting GNNs in handling under-reaching. The source code is available at \url{https://github.com/WeigangLu/NodeMixup}.
BibTeX
@inproceedings{lu2024nodemixup,
  author = {Weigang Lu and Ziyu Guan and Wei Zhao and Yaming Yang and Long Jin},
  title = {{NodeMixup: Tackling Under-Reaching for Graph Neural Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i13.29328},
}
Figure