A Label Noise Robust Algorithm for Graph Data using Neighborhood Label Distribution
Abstract
Graph Convolutional Networks (GCNs) have demonstrated exceptional performance on graph-structured data. However, their success heavily relies on the availability of clean labels, an assumption that often fails in real-world scenarios. The learnability of GCNs is intrinsically linked to the neighborhood structure of nodes, making it critical to understand how this structure changes in the presence of label noise. In this work, we investigate how the neighborhood label distribution of a node changes under label noise. We mathematically derive that label noise smooths this distribution, which inherently increases its entropy and severely decreases interclass distinguishability. To address this challenge, we propose Leave-one-out Entropy Node Screening (LENS), an end-to-end framework that identifies noisy nodes by measuring the reduction in neighborhood entropy when a specific node is removed. LENS further incorporates a relabeling mechanism to recover and preserve valuable feature information instead of entirely discarding the identified noisy nodes. Crucially, the end-to-end computational overhead of LENS is remarkably low. Extensive evaluations demonstrate that our algorithm achieves state-of-the-art node classification accuracy while executing an order of magnitude faster than existing noise-robust approaches.
Related
- Estimation of the Label-Noise Transition Matrix with Performance Guarantees via Selective Classification
- Robust Direct Preference Optimization under Preference Label-Flip Attacks
- When is early stopping beneficial under label noise? A phase diagram for kernel gradient flow
- Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithm
- The AECM Algorithm for Deterministic Maximum Likelihood Direction Finding in the Presence of Gaussian Mixture Noise
BibTeX
@misc{kumar2026label,
title = {{A Label Noise Robust Algorithm for Graph Data using Neighborhood Label Distribution}},
author = {Pintu Kumar and Nandyala Hemachandra},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.22998},
eprint = {2610.22998},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.22998},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Label Noise Robust Algorithm for Graph Data using Neighborhood Label Distribution
AU - Pintu Kumar
AU - Nandyala Hemachandra
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.22998
UR - https://arxiv.org/abs/2610.22998
AB - Graph Convolutional Networks (GCNs) have demonstrated exceptional performance on graph-structured data. However, their success heavily relies on the availability of clean labels, an assumption that often fails in real-world scenarios. The learnability of GCNs is intrinsically linked to the neighborhood structure of nodes, making it critical to understand how this structure changes in the presence of label noise. In this work, we investigate how the neighborhood label distribution of a node changes under label noise. We mathematically derive that label noise smooths this distribution, which inherently increases its entropy and severely decreases interclass distinguishability. To address this challenge, we propose Leave-one-out Entropy Node Screening (LENS), an end-to-end framework that identifies noisy nodes by measuring the reduction in neighborhood entropy when a specific node is removed. LENS further incorporates a relabeling mechanism to recover and preserve valuable feature information instead of entirely discarding the identified noisy nodes. Crucially, the end-to-end computational overhead of LENS is remarkably low. Extensive evaluations demonstrate that our algorithm achieves state-of-the-art node classification accuracy while executing an order of magnitude faster than existing noise-robust approaches.
ER -