Leveraging Label Non-Uniformity for Node Classification in Graph Neural Networks

Feng Ji, See Hian Lee, Hanyang Meng, Kai Zhao, Jielong Yang, Wee Peng Tay

Introduction

In node classification tasks, Graph Neural Networks (GNNs) rely heavily on "message passing" to aggregate information from a node's neighbors. While highly effective in homophilic graphs—where connected nodes tend to share the same label—this mechanism falters at class boundaries. Nodes situated between different classes receive mixed signals, and the inherent smoothing effect of message passing blurs their features, making accurate classification difficult.

Because the true labels of all nodes are unknown, identifying these hidden structural boundaries is a significant challenge. This paper asks a compelling question: Can we infer a graph's hidden boundaries using only the output of a base GNN, and leverage that insight to improve model performance? The authors answer affirmatively by introducing label non-uniformity, a novel metric that powers two plug-and-play algorithms to enhance standard GNNs.

The Core Concept: Label Non-Uniformity

The foundation of the authors' approach is the label non-uniformity metric, denoted as $w(v)$.

When a GNN processes a node, it produces raw scores (logits) that a softmax layer converts into a probability distribution across classes. Label non-uniformity measures the Wasserstein distance between this predicted distribution and a perfectly uniform distribution.

  • High Non-Uniformity: Indicates high model confidence. The node is likely situated safely within a distinct class region.
  • Low Non-Uniformity: Indicates uncertainty. The model is receiving mixed signals, suggesting the node lies near a class boundary.

By treating model uncertainty not just as a failure of prediction, but as a structural probe, the authors map the graph's topology. Low confidence effectively points to the edges where one class ends and another begins.

Two Plug-and-Play Algorithms

Using the $w(v)$ metric, the authors propose a wrapper framework (dubbed wGNN) that can be applied to any base GNN (such as GCN or GAT). It consists of two distinct strategies:

  1. Supplementing Training Data (Self-Training): The model identifies test nodes with the highest label non-uniformity (the "sure bets"). It then adds these nodes to the training set, using their predicted labels as ground truth to reinforce the model's learning.
  2. Strategic Edge Dropping: The model identifies nodes with the lowest non-uniformity (the "boundary candidates") and strategically removes edges among them. Theoretically grounded in the Cheeger constant, reducing the "cut size" near boundaries creates a graph bottleneck. This prevents the blurring effect of message passing across class borders, allowing the model to learn more distinct embeddings.

Key Results and Heterophilic Success

The wGNN approach was evaluated across a diverse set of benchmark datasets, including citation networks (Cora, Citeseer, Pubmed), co-purchase graphs (Amazon Photo, CS), specialized networks (Airport, Disease), and heterophilic graphs (Texas, Chameleon).

  • Consistent Gains: wGNN improved performance in 88% of the experimental comparisons (37 out of 42) with statistical significance ($p < 0.05$).
  • Rescuing Deep Models: Deep GNNs often suffer from severe over-smoothing. In a test using a deep GAT base model, applying the non-uniformity wrapper improved accuracy by approximately 15%.
  • Heterophilic Performance: Edge dropping is traditionally used to prevent over-smoothing in homophilic graphs. However, the authors demonstrate its efficacy in heterophily. By dropping edges near boundaries, the algorithm severs "noisy" edges connecting different classes. On the Texas dataset, wGNN pushed the performance of an ACM-GCN base model from 88.38% to 90.27%.

Limitations and Future Work

While highly effective, the wGNN framework has a few limitations:

  • Base Model Dependency: Because the method relies on initial logits, an exceptionally poor base model will produce a noisy non-uniformity metric, potentially propagating errors during the self-training phase.
  • Hyperparameter Sensitivity: The approach introduces three new hyperparameters ($\eta_0, \eta_1, \eta_2$) controlling the fraction of nodes and edges manipulated. Finding the optimal configuration requires grid search and additional computational overhead.

Looking forward, the authors suggest exploring how label non-uniformity correlates with deeper geometric properties of graphs, such as hyperbolicity or Ricci curvature, opening new avenues for understanding graph topology through the lens of model uncertainty.

Summary updated

Abstract

In node classification using graph neural networks (GNNs), a typical model generates logits for different class labels at each node. A softmax layer often outputs a label prediction based on the la...
BibTeX
@inproceedings{ji2023leveraging,
  author = {Feng Ji and See Hian Lee and Hanyang Meng and Kai Zhao and Jielong Yang and Wee Peng Tay},
  title = {{Leveraging Label Non-Uniformity for Node Classification in Graph Neural Networks}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=HfUWnPeLLH},
}
Figure