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

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 largest logit. We demonstrate that it is possible to infer hidden graph structural information from the dataset using these logits. We introduce the key notion of label non-uniformity, which is derived from the Wasserstein distance between the softmax distribution of the logits and the uniform distribution. We demonstrate that nodes with small label non-uniformity are harder to classify correctly. We theoretically analyze how the label non-uniformity varies across the graph, which provides insights into boosting the model performance: increasing training samples with high non-uniformity or dropping edges to reduce the maximal cut size of the node set of small non-uniformity. These mechanisms can be easily added to a base GNN model. Experimental results demonstrate that our approach improves the performance of many benchmark base models.

Introduction

Graph Neural Networks (GNNs) have become the standard for node classification tasks, leveraging "message passing" to aggregate information from neighboring nodes. This mechanism is highly effective for nodes situated within dense clusters of the same class. However, it poses a significant challenge at class boundaries. Nodes located between different classes receive conflicting signals, and the inherent smoothing effect of message passing can blur class distinctions, making these boundary nodes difficult to classify accurately.

The fundamental difficulty lies in the fact that class boundaries are typically unknown a priori. This research explores whether a model's own output logits can serve as structural probes to identify these boundaries and improve overall classification performance.

Methods: Label Non-Uniformity and wGNN

The authors introduce the concept of label non-uniformity ($w(v)$), a metric that quantifies a model's confidence by calculating the Wasserstein distance between a node's softmax probability distribution and a uniform distribution. A high $w(v)$ indicates the model is confident in a specific label, while a low $w(v)$ suggests uncertainty, often signifying that the node resides near a class boundary.

Based on this metric, two plug-and-play algorithms are proposed to enhance any base GNN model (e.g., GCN, GAT):

  1. Supplementing Training (Algorithm 1): The model identifies test nodes with the highest label non-uniformity—those with the most "certain" predictions—and incorporates them into the training set with their predicted labels. This refined self-training approach leverages high-confidence predictions to provide more supervision.
  2. Edge Dropping (Algorithm 2): The model identifies nodes with the lowest non-uniformity, which are likely boundary nodes. It then constructs a subgraph of these nodes and randomly drops edges within it. This creates a structural "bottleneck" that prevents noisy, cross-boundary information from propagating during message passing.
Conceptual illustration of boundary nodes and the creation of structural bottlenecks via edge dropping.

Experimental Results

The proposed "wGNN" approach was evaluated across a diverse set of benchmarks, including citation networks (Cora, Citeseer, Pubmed), co-purchase/co-authorship graphs (Amazon Photo, MS Academic), and specialized heterophilic graphs (Airport, Disease, Texas, Chameleon).

The wGNN variants consistently outperformed their base models in all 42 experimental configurations. For instance, on the Cora dataset, a standard GCN's accuracy improved from 80.65% to 83.12%. The improvements were particularly notable on heterophilic graphs, such as the Texas dataset, where GCN accuracy rose from 54.60% to 58.11%. Statistical analysis confirmed that these gains were significant (p-value < 0.05) in 88% of the cases.

Sensitivity analysis showing the impact of the percentage of selected nodes on classification accuracy.

The performance of the method is sensitive to the hyperparameters $\eta_1$ and $\eta_2$, which determine the fraction of nodes selected for training supplementation and edge dropping, respectively. As shown in the sensitivity analysis above, there is typically an optimal range for these parameters that maximizes accuracy before diminishing returns or noise introduction occurs.

Discussion and Conclusion

The core insight of this work is that model "uncertainty" (low label non-uniformity) is not merely a failure of the classifier but a reflection of the underlying graph geometry. By using logits as structural probes, the wGNN framework effectively identifies and mitigates the "smoothing paradox"—where message passing, while beneficial for homophilic clusters, degrades performance at boundaries.

While the method is model-agnostic and provides consistent boosts, it does introduce additional computational overhead due to the multi-pass training process and requires careful hyperparameter tuning. Future research may focus on single-pass implementations and improving the robustness of the non-uniformity metric when the initial base model performance is low.

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 largest logit. We demonstrate that it is possible to infer hidden graph structural information from the dataset using these logits. We introduce the key notion of label non-uniformity, which is derived from the Wasserstein distance between the softmax distribution of the logits and the uniform distribution. We demonstrate that nodes with small label non-uniformity are harder to classify correctly. We theoretically analyze how the label non-uniformity varies across the graph, which provides insights into boosting the model performance: increasing training samples with high non-uniformity or dropping edges to reduce the maximal cut size of the node set of small non-uniformity. These mechanisms can be easily added to a base GNN model. Experimental results demonstrate that our approach improves the performance of many benchmark base models.
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