PaperlayerView exact revision on arXiv

Source-linked AI summary

A Label Noise Robust Algorithm for Graph Data using Neighborhood Label Distribution

Pintu Kumar, Nandyala Hemachandra

arXiv:2610.22998v1cs.LGcs.AImath.STstat.TH

TL;DR

Because GCNs rely on clean labels while real graph data can be noisy, this paper studies how corruption changes neighborhood label distributions. It introduces LENS, which screens nodes using leave-one-out neighborhood-entropy changes, and reports state-of-the-art performance with substantially less compute than existing noise-robust approaches.

  • Problem

    GCNs assume clean training labels, but real graph data is often noisy, and methods developed for independent data underperform on interconnected graphs.

    Source: §1 · p. 1

  • Method

    LENS identifies noisy nodes by measuring neighborhood-entropy changes when a node is removed, building on theoretical analysis of noise-induced NLD smoothing.

    Source: §1 · p. 2, §4.1 · p. 5

  • Results

    The authors report that LENS achieves state-of-the-art performance while using significantly less compute than existing noise-robust approaches.

    Source: §1 · p. 2, §7 · p. 10

  • Takeaways & Limitations

    The paper reports that label noise smooths NLDs, increases their entropy, and reduces graph interclass distinguishability.

    Source: §1 · p. 2, §7 · p. 10

    LENS may not work well on graphs such as Actor and Coronell that lack class-specific neighborhood structure.

    Source: §7 · p. 10

Abstract

from arXiv · show

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.

1 Introduction

The introduction frames label noise as a graph-learning problem that existing methods for independent data do not resolve, and asks how noise changes neighborhood label distributions and class distinguishability. It presents theoretical results on smoothing and entropy, and introduces LENS as an efficient noisy-node screening approach.

1 Introduction

  • Prior noise-robust methods for independent data underperform on interconnected graphs, and replacing their standard neural-network backbone with a GCN has not yielded the usual improvements.Source: §1 · p. 1
  • The study examines noise-induced changes to neighborhood patterns because local neighborhood structure helps determine how GCNs learn and aggregate information.Source: §1 · p. 1
  • The authors describe their work as a first attempt to bridge research on label-noise robustness and the role of neighborhoods in graph learning.Source: §1 · p. 2
  • The paper asks how label noise perturbs a node’s Neighborhood Label Distribution, how that understanding can identify noisy labels, and how the perturbation affects class distinguishability.Source: §1 · p. 2
  • LENS screens noisy nodes using leave-one-out neighborhood-entropy changes and is reported to outperform competing algorithms at a fraction of their computational cost.The method analyzes entropy changes when a node is computationally masked.Source: §1 · p. 2
  • Label noise smooths neighborhood label distributions and increases their entropy, while also degrading interclass distinguishability.The paper frames these effects as structural changes relevant to graph learning.Source: §1 · p. 2

2 Preliminaries

This section establishes graph, class, and label notation; describes the noise models considered; and defines neighborhood label distribution from neighboring nodes’ class counts.

2 Preliminaries

  • A graph is denoted G = (V, E), with nodes V, edges E, classes Y, ground-truth labels y_v, neighborhoods N(v), degree d_v, and noisy labels ŷ_v.Source: §2 · p. 2

2.1 Noise Models

  • The paper considers noise models commonly adopted by existing noise-robust algorithms [5, 7, 21].Source: §2.1 · p. 2

2.1.1 Symmetric Label Noise (SLN)

  • Under Symmetric Label Noise (SLN), a mislabeled sample is equally likely to receive any possible label [7].Source: §2.1.1 · p. 2

2.1.2 Pairwise Noise (PWN)

  • Under Pairwise Noise (PWN), a true label flips to a specific adjacent class with probability p, making corruption directional [7].Source: §2.1.2 · p. 2

2.1.3 Doubly stochastic noise models

  • A doubly stochastic noise-transition matrix has probabilities summing to one across both each row and each column; SLN and PWN are instances.Source: §2.1.3 · p. 3

2.2 Neighborhood Label Distribution

  • For each class, neighborhood label distribution records the fractions of a node’s neighbors belonging to each class.Source: §2.2 · p. 3

3 Impact of Label Noise on NLD

The section derives how label noise transforms a node’s neighborhood label distribution (NLD): under the analyzed noise models, smoothing moves it toward uniformity and increases entropy. The entropy-increase guarantee for general noise requires a doubly stochastic matrix applied uniformly across nodes.

3.1 Change in NLD under SLN

  • Under Symmetric Label Noise (SLN), the expected NLD is pulled toward uniformity: class-probability gaps contract and entropy increases.For SLN, the expected noisy NLD is a mixture of the initial distribution and a uniform distribution.Source: §3.1 · p. 3, §3.1.1 · pp. 3–4

3.1.1 Change in NLD entropy by SLN

  • For SLN, the expected NLD has entropy at least that of the original NLD.The result follows from the expected distribution’s mixture with a uniform distribution, which has maximum entropy.Source: §3.1.1 · pp. 3–4

3.2 Impact of PWN on NLD Entropy

  • Under Pairwise Noise (PWN), each class’s expected probability mass combines its original mass with mass from the preceding class, producing cyclic smoothing and increased entropy.The class-mass transformation is E[ˆlv,i] = lv,i(1 − p) + lv,i−1p.Source: §3.2 · p. 4

3.3 Change in NLD Entropy by Doubly Stochastic Noise Models

  • For any doubly stochastic noise matrix applied uniformly across nodes, the expected noisy NLD has entropy at least that of the original NLD.The entropy increase is not guaranteed when the matrix is only row-stochastic or the noise is node- or class-dependent.Source: §3.3 · p. 4
  • The section also derives a high-probability bound on the difference between expected-noisy-NLD entropy and realized-noisy-NLD entropy.The setup assumes independent corruption of nodes using a common row-stochastic transition matrix.Source: §3.3 · p. 4

4 LENS: Leave-one-out Entropy Node Screening

LENS uses leave-one-out changes in neighborhood entropy to screen noisy nodes, then evaluates noise reduction and false positives. Its workflow uses pseudo-labels for test and validation nodes when computing NLD entropy.

4 LENS: Leave-one-out Entropy Node Screening

  • LENS uses the theoretical link between label-noise smoothing and increased NLD entropy to screen clean nodes from corrupted ones.The screening framework is described as entropy-based and end-to-end.Source: §4 · p. 4

4.1 Identifying Noisy Nodes

  • LENS flags a node as noisy when removing it reduces neighboring NLD entropy, aggregating those local changes with Sum or Vote strategies.Both aggregation methods separate clean and noisy nodes in Figure 1.Source: §4.1 · p. 5, Figure 1 · p. 5

4.2 Change in Noise Level

  • Both LENS(Sum) and LENS(Vote) significantly decrease the noise remaining in the clean-node set Dc.Table 1 reports noise levels in Dc for both methods under Symmetric Label Noise and Pairwise Label Noise.Source: Table 1 · p. 5, §4.2 · p. 5

4.2.1 Addressing High Number of False Positives

  • Across evaluated Cora SLN noise levels, false positives have markedly lower clean local homophily than true positives and true negatives.The authors attribute this pattern to naturally heterogeneous neighborhoods at class boundaries; an added NLD-entropy threshold verifies initially flagged nodes.Source: §4.2.1 · p. 6, Figure 2 · p. 6

4.3 Pseudo Labeling

  • The workflow predicts labels for test and validation nodes, uses them to compute NLD entropy for screening, and trains a GCN on clean nodes.The pseudo-labels are generated by a GCN trained on Dtrain and are used only to calculate NLD.Source: Figure 3 · p. 6, §4.3 · p. 6

5 Evaluation of LENS for Node Classification on Noisy Labeled Graph

LENS is evaluated against noise-robust baselines across datasets, noise conditions, and GNN backbones. The results report strong classification performance, low end-to-end runtime, and benefits from relabeling at high noise levels.

5.1 Setup and Datasets

  • The evaluation uses SLN and PWN on Cora, Citeseer, and Amazon Photo, with two single-hidden-layer GCN models and comparisons to noise-robust baselines.Experiments were repeated five times, reporting mean and standard deviation; the listed baselines include Coteaching+, NRGNN, RTGNN, and DeGLIF.Source: §5.1 · p. 7

5.2 Performance of LENS on Node Classification in Presence of Label Noise

  • LENS(vote) achieved the best overall rank at 2.13 across 27 benchmark instances, with significant mean-accuracy gains over DeGLIF and TSS.The gains were +0.67% over DeGLIF (p = 0.0206) and +2.54% over TSS (p = 0.000037).Source: §5.2 · pp. 7–8, Table 2 · p. 7

5.3 Computational Time Comparison

  • 0.25 seconds was LENS’s end-to-end runtime on Cora, more than 12 times faster than the second-fastest approach.The comparison covers the full pipeline from noisy graph input to final prediction; Table 3 reports execution times on Cora using an RTX 4090.Source: §5.3 · p. 8, Table 3 · p. 8

5.4 Relabeling Function

  • On Cora, relabeling produced comparable results at low noise and significantly improved accuracy at high noise.Identified noisy nodes are assigned a new label using predictions from a GCN trained on the clean-node set, then merged with that set.Source: §5.4 · p. 8, Table 4 · p. 8

5.5 Sensitivity Analysis of Thresholds τs and τv

  • Threshold sensitivity tests found no settings that consistently outperformed τs = 0 and τv = 0.5.For Vote, neighbor entropy reductions concentrate near 0 or 1; for Sum, most clean nodes have entropy-difference sums below 0.Source: §5.5 · p. 9

5.6 Experiments on Additional Datasets

  • On Roman Empire and Amazon Ratings, LENS outperformed evaluated methods, matched comparable performance on PubMed, and surpassed all but NRGNN on DBLP.For DBLP, LENS’s accuracy is upper-bounded by clean-data GCN performance, while NRGNN’s roughly 4% advantage over GCN persists across noise levels.Source: §5.6 · p. 9, Table 5 · p. 9

5.7 Experiments using other GNN architectures

  • LENS performed well with GAT and GraphSAGE backbones as well as GCN.The Cora evaluation replaced both LENS models with either GAT or GraphSAGE.Source: §5.7 · p. 9

6 Impact of Label Noise on Interclass Distinguishability

The section relates node-level neighborhood label distributions to a graph-level measure of interclass distinguishability. Under the stated balanced-graph and doubly stochastic conditions, symmetric label noise reduces that distinguishability.

Theorem 5

  • Under symmetric label noise, interclass distinguishability does not increase for a balanced clean K-class graph whose Class NLD matrix is doubly stochastic.The theorem defines interclass distinguishability as the entropy of normalized singular values and states InterClass(C̃) ≤ InterClass(C).Source: §6 · p. 10

Interpretation

  • The class-level decrease parallels node-level smoothing: noisy labels push individual NLDs toward uniformity, blending class patterns.The Class NLD matrix is formed by averaging node NLD vectors within each class and stacking the resulting vectors as columns.Source: §6 · p. 10

Proof outline

  • The proof attributes the decrease to down-scaling all but the highest singular value, followed by entropy comparison of the normalized singular values.The derivation invokes majorization and Schur concavity of entropy.Source: §6 · p. 10

7 Limitations and Conclusions

LENS has difficulty identifying noisy nodes in heterogeneous regions and may not work well on graphs lacking class-specific neighborhood structure. The paper concludes that label noise smooths NLDs, increases their entropy, reduces interclass distinguishability, and that LENS achieves state-of-the-art performance with less compute than compared approaches.

Limitations and Conclusions

  • Noisy nodes in heterogeneous regions are difficult for LENS to identify, and it may not work well on graphs with “Bad Heterophily,” such as Actor and Coronell.The paper characterizes these graphs as lacking class-specific neighborhood structure.Source: §7 · p. 10
  • The paper reports that label noise smooths NLDs, increases their entropy, reduces interclass distinguishability, and that LENS achieves state-of-the-art performance with less compute.The stated conclusions concern graph data and comparisons with existing noise-robust approaches.Source: §7 · p. 10

A.1 Proof of Theorem 1 and related Corollaries

The appendix proof derives expected neighborhood class mass under symmetric label noise by separating retained labels from labels that move into a class. It then relates expected counts to the initial neighborhood label distribution.

Proof of Theorem 1

  • The proof models the noisy count for a class as the sum of retained members and incoming members, represented by independent binomial variables.Retained members were originally in the class and remain there; incoming members came from other classes and are corrupted into it.Source: §A.1 · p. 13
  • The expected noisy class count combines the retained-count and influx expectations, then uses the initial class proportion as the count divided by neighborhood size.The passage identifies the initial proportion as l_j = c_j/d.Source: §A.1 · p. 13
  • For a specific class, the expected noisy probability mass is obtained by multiplying the initial distribution vector by the noise transition matrix.The theorem states this expected-mass result for a node in a K-class setting under symmetric label noise.Source: §A.1 · p. 13

A.2 Proof of Theorem 2

Under Pairwise Noise, each class’s expected neighborhood-label mass combines retained labels with labels flipping in from the preceding class. This convex-combination form implies that expected NLD entropy does not decrease.

A.2 Proof of Theorem 2

  • Expected class-i NLD mass under Pairwise Noise is lv,i(1 − p) + lv,i−1p.The preceding class wraps cyclically, so class 1 receives label flips from class K.Source: §A.2 · p. 14
  • The expected class-j count combines retained neighbors and an influx from the preceding class, with each count modeled binomially.The retention probability is 1 − p and the influx probability is p; the class indices follow the cyclic condition c0 ≡ cK.Source: §A.2 · p. 14
  • Because the expected NLD is a convex combination of the original distribution and its cyclic shift, strict entropy concavity gives H(E[ˆlv]) ≥ H(lv).The cyclic shift preserves entropy because it only permutes the class probabilities.Source: §A.2 · p. 14

A.3 Proof of Theorem 3

For doubly stochastic noise, the expected NLD entropy is nondecreasing, but this property need not hold when the noise assumptions are relaxed. The finite-degree analysis also bounds when entropy increase is guaranteed with high probability.

A.3 Proof of Theorem 3

  • For any doubly stochastic noise matrix, the expected NLD entropy satisfies H(E[ˆlv]) ≥ H(lv).The proof represents the matrix as a convex combination of permutation matrices, whose action preserves entropy.Source: §A.3 · pp. 14–15

A.4 Counterexamples for Remark 1

  • The entropy-increase property is not universal: a non-doubly-stochastic matrix or node-dependent noise can decrease NLD entropy.A uniform three-class NLD becomes [1/2, 1/3, 1/6] under the row-stochastic example, with lower entropy; node-dependent doubly stochastic matrices can also concentrate [0.9, 0.1] into [1, 0].Source: §A.4 · p. 15

A.5 Proof for Theorem 4

  • Theorem 4 considers initial NLD lv and noisy-graph NLD ˆlv for node v of degree dv in a K-class setting; under independent corruption with common row-stochastic Q, a result holds with probability at least 1 − δ.Source: §A.5 · p. 15

Step 2: Continuity of Shannon entropy

  • The entropy gap narrows as node degree increases, while more classes enlarge the gap for small-degree nodes.The analysis states that H(ˆlv) > H(lv) with probability 1 − δ when ΔV ≥ error; for high-entropy NLDs, this condition holds only for very high-degree nodes.Source: Step 2: Continuity of Shannon entropy · p. 16

B Impact of label noise on Interclass distinguishability

The section uses entropy of normalized singular values as a proxy for interclass distinguishability. Under symmetric label noise and the stated balanced, clean, doubly stochastic conditions, the expected Class NLD’s distinguishability decreases.

B Impact of label noise on Interclass distinguishability

  • The Class NLD stacks each class’s average NLD as a column, and entropy of its normalized singular values serves as a continuous distinguishability proxy.The proxy measures whether the class-pattern matrix is full-rank and distinguishable or collapsing toward rank 1.Source: B Impact of label noise on Interclass… · p. 17
  • Under symmetric label noise, InterClass(˜C) ≤ InterClass(C) for the balanced, clean graph whose Class NLD matrix is doubly stochastic.InterClass is defined as entropy of the normalized singular values.Source: B Impact of label noise on Interclass… · p. 17

Step 1: The Matrix Transformation

  • The expected noisy Class NLD is formed by transforming the original matrix with the symmetric-noise transition matrix, yielding ˜C = α²C + (1 − α²)U.Here U is the uniform matrix and α is the contraction factor.Source: Step 1: The Matrix Transformation · p. 17

Step 2: The singular value decay

  • The dominant singular value stays at 1, while every secondary singular value is scaled by α².The derivation separates the uniform component from structural variation before calculating the noisy matrix’s singular values.Source: Step 2: The singular value decay · pp. 18–19

Step 3: Normalization and Skew

Step 4: The Entropy Drop

  • The proof establishes majorization by showing that partial sums of ˜s are at least those of s, so entropy drops.The stated comparison follows from the contraction factor being less than 1 and the dominant singular value and tail sum being positive.Source: Step 4: The Entropy Drop · p. 19

C Comparison with Simple Neighborhood-Based Heuristics

LENS is compared with neighborhood-label heuristics on homophilic and heterophilic graphs, and the section relates its approach to prior graph label-noise methods. The reported comparisons favor LENS more clearly at higher noise on Roman Empire.

C Comparison with Simple Neighborhood-Based Heuristics

  • The evaluation compares LENS variants with one- and two-hop label-agreement or majority heuristics on Cora and Roman Empire under SLN and PWN.Cora is homophilic and Roman Empire heterophilic; the node-classification results are identified as Table 7.Source: C Comparison with Simple… · p. 20
  • On Roman Empire, LENS (Vote) reaches 67.4% versus Nbr_rarity’s 65.0% at 50% SLN, and LENS (Sum) reaches 62.2% versus 54.4% at 40% PWN.On Cora, LENS and neighbor’s-neighbor heuristics are comparable at low noise, while LENS generally has higher accuracy as noise increases.Source: C Comparison with Simple… · p. 20
  • LENS considers the full neighborhood label distribution, retaining class proportions that majority-based heuristics discard, especially relevant to heterophilic graphs at higher noise.Different classes can share the same most frequent neighboring label while differing in the remaining label proportions.Source: C Comparison with Simple… · pp. 20–21

D Related Works

  • Prior approaches include loss correction, pseudo-labeling, and co-training strategies for noisy graph labels.The cited examples are D-GNN [40], NRGNN, and Coteaching+ [37].Source: D Related Works · p. 21
  • Other related methods use graph consistency, contrastive learning, curriculum selection, or leave-one-out influence; DeGLIF [7] relabels nodes using validation-loss changes.The section also describes RTGNN, CP, RNCGLN, PIGNN, CGNN, CRGNN, and TSS.Source: D Related Works · p. 21
Loading 2610.22998v1…