Graph algorithms improve noisy label detection and correction fast
A Label Noise Robust Algorithm for Graph Data using Neighborhood Label Distribution
Machine LearningArtificial Intelligence
Summary
Labels on graph data, like tagging friends in a social network, can often be wrong, which makes understanding the graph much harder. The authors found that label mistakes blur the differences between groups in the graph, making classification less accurate. They created a new method called LENS that spots potentially wrong labels by checking how much disorder changes when each node is removed. Instead of just ignoring bad labels, LENS also tries to fix them, which helps the system learn better while running faster than past methods.
What this means in practice
- •For data science teams: Improve classification accuracy in graph-based datasets where labels may be unreliable by detecting and correcting noisy labels efficiently.
- •For social media platform engineers: Enhance friend recommendation or content tagging systems by reducing errors from mislabeled user connections and profiles using fast noise-robust methods.
Authors
Pintu Kumar, Nandyala Hemachandra
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.