PaperlayerView exact revision on arXiv

Source-linked AI summary

PaSta: Noisy Node Classification with Partial Label Learning

Yujing Liu, Yixin Liu, Yu Zheng, Yue Tan, Alan Wee-Chung Liew, Shirui Pan

arXiv:2608.25365v1cs.LG

TL;DR

Noisy node classification suffers when one-hot supervision overfits corrupted labels and makes label refinement unreliable. PASTA constructs consensus partial labels with multiple annotators, learns from them in label and representation spaces, and iteratively refines supervision. Across noisy settings, it reports an average classification improvement of 1.1% over the strongest competitor.

Abstract

from arXiv · show

Noisy node classification problem is a fundamental yet challenging task for real-world graph-related web services, where node labels are often corrupted or unreliable due to weak supervision or automatic annotation. However, existing methods typically train models based on one-hot labels, which not only makes models susceptible to overfitting on noisy labels, but also leads to error accumulation after pseudo-label-guided enhancement. In this paper, we propose a novel Partial label-based Self-training framework (PaSta for short) that leverages partial label learning technique to overcome the limitations of existing methods. Specifically, PaSta first trains multiple annotators to comprehensively capture the class distribution of nodes and aggregates their predictions to construct high-quality partial labels. Subsequently, we design a partial label-based classification model with two well-crafted loss functions to guide the model learning at both label and representation spaces. To further enhance the robustness against noisy labels, we introduce a self-training strategy where the labels refined by partial label learning are then used to further optimize the annotators in a closed-loop iterative manner. Extensive experiments on five datasets demonstrate that, compared with existing state-of-the-art methods, PaSta achieves an average improvement of 1.1% in classification performance under various noise settings.

I. INTRODUCTION

Noisy node classification is challenged by erroneous labels and one-hot supervision, which can drive overconfident fitting and unreliable label correction. PASTA addresses these issues by constructing consensus partial labels, learning in label and representation spaces, and iteratively refining annotators and labels.

  • Erroneous labels arise in real-world graph data from manual annotation errors and delayed information updates, undermining node classification.Source: §I · p. 1
  • One-hot supervision makes classifiers sensitive to noise by forcing high-confidence predictions for a single category, which can fit incorrect labels.Source: §I · p. 1
  • Partial label learning represents each sample with multiple candidate labels, preserving uncertainty and enabling correct-boundary learning when the true label is included.Source: §I · pp. 1–2
  • Applying partial labels to pseudo-labels and refined labels preserves uncertainty and reduces risks from faulty one-hot label correction.Source: §I · p. 2
  • PASTA generates partial labels with a self-supervised ensemble annotation module and exploits them through dual-space losses plus iterative self-training.Source: §I · p. 2

B. Noisy Node Classification

Noisy node classification concerns predicting node classes from graphs when only a small labeled subset is available and some labels are erroneous. PASTA combines self-supervised ensemble annotation with dual-space partial label learning to improve label quality and classifier robustness.

1) Self-Supervised Feature Extractors:

PASTA pre-trains multiple feature extractors with different self-supervised graph learning strategies to create diverse representation spaces for ensemble annotation. Because this training does not rely on ground-truth labels, the extractors are not influenced by noisy labels.

2) Supervised Predictors:

PASTA trains lightweight supervised predictors on annotator representations, progressively refining their training set with enhanced labels. Their complementary predictions are aggregated into consensus partial labels that retain richer class-distribution information.

B. Dual-Space Partial Label Learning

PaSta trains a node classifier with consensus partial labels using complementary losses in label and representation spaces. This preserves vote-derived uncertainty while avoiding one-hot overconfidence.

Classification Model

  • PaSta uses a two-layer GCN classifier to demonstrate the framework without interference from complex architectures.The classifier can alternatively be replaced by Graph-SAGE or GAT.Source: 1) Classification Model · p. 5

Vote-Aggregated Cross-Entropy Loss

  • Consensus partial labels encode class-distribution information from annotator voting rather than only one-hot or binary supervision.This distributional information motivates the Vote-aggregated Cross-Entropy loss.Source: 2) Vote-Aggregated Cross-Entropy… · p. 5

Dual-Space Objective

Vote-Aggregated Cross-Entropy Loss

  • VaCE assigns greater update strength to categories receiving more annotator votes, providing fine-grained supervision and avoiding one-hot overconfidence.It is designed as an improvement over conventional cross-entropy.Source: 2) Vote-Aggregated Cross-Entropy… · p. 5

3) Partial label Similarity (PaSim) Loss:

PaSim exploits semantic information in non-target consensus labels by aligning node similarities in partial-label and representation spaces. It complements VaCE within PaSta’s overall objective.

Motivation

  • Unlike conventional partial labels, PaSta’s non-target consensus labels can encode semantic information such as proximity to classification boundaries.This information is used to improve model generalization.Source: 3) Partial label Similarity (PaSim) Loss · p. 5

PaSim Loss

Similarity Construction

  • PaSta computes partial-label and embedding similarity matrices to transfer semantic affinity from label space into representation space.The matrices are formed from pairwise similarities.Source: 3) Partial label Similarity (PaSim) Loss · p. 5

Combined Objective

  • The overall objective combines VaCE and PaSim, whose complementary constraints improve robustness and discriminability.The two losses operate in label and representation spaces, respectively.Source: 3) Partial label Similarity (PaSim) Loss · p. 5

C. Iterative Self-Training Framework

PaSta jointly refines its annotation and partial-label learning modules through iterative self-training. The closed loop addresses the risk that noisy original labels produce inaccurate partial labels.

Motivation

  • Sequentially running annotation and partial-label learning can propagate low-quality original labels into inaccurate partial labels and weaker classifier training.This motivates joint closed-loop optimization.Source: C. Iterative Self-Training Framework · p. 5

Closed-Loop Optimization

  • Each self-training iteration uses annotated partial labels to update partial-label learning, then uses classifier predictions to refine the annotators.The process is bootstrapping and closed-loop.Source: C. Iterative Self-Training Framework · p. 5
  • After τ iterations, both modules are progressively refined and mutually enhanced, producing better partial labels and classification results.The passage characterizes this as the outcome of iterative refinement.Source: C. Iterative Self-Training Framework · p. 6

Label Enhancement

  • Label enhancement bridges classifier predictions back to annotator training through noisy-label filtering and pseudo-label expansion.The training set S begins as the original labeled node set V_L.Source: C. Iterative Self-Training Framework · p. 6

Noisy Label Filtering

  • Noisy-label filtering removes nodes whose losses exceed a class-specific threshold, treating them as unlabeled in subsequent training.The threshold selects the top r% highest-loss values within each class.Source: 1) Noisy Label Filtering · p. 6

2) Pseudo-Label Expansion:

PaSta expands supervision by assigning pseudo-labels to high-confidence unlabeled nodes after filtering noisy labels. The method’s scalability is constrained by quadratic time and space in the number of nodes.

Pseudo-Label Expansion

  • After noisy-label filtering, PaSta assigns pseudo-labels to unlabeled nodes using predicted classes and confidence scores.These predictions come from the classification model.Source: 2) Pseudo-Label Expansion · p. 6
  • The method adds pseudo-labels to the top α highest-confidence nodes in each class to enrich annotator supervision.α is a hyperparameter.Source: 2) Pseudo-Label Expansion · p. 6
  • The refined training set provides cleaner and more informative supervision for subsequent annotator training, improving annotation quality and classifier performance.This occurs after the two-step label-enhancement process.Source: 2) Pseudo-Label Expansion · p. 6

Complexity Analysis

  • O(τ · t · n^2d) is PaSta’s overall time complexity across τ self-training iterations.The dominant factors are graph convolution and similarity computation; n is the number of nodes.Source: D. Complexity Analysis · p. 6
  • O(n^2 + t · d^2) is PaSta’s total space complexity, dominated by dense similarity matrices and multiple GCN annotators.The quadratic term arises from pairwise semantic-affinity storage.Source: D. Complexity Analysis · p. 6

Evaluation

  • PaSta is evaluated on five real-world graph datasets spanning citation, collaboration, and product co-purchase networks.The datasets are Cora, Citeseer, DBLP, Computers, and Photo.Source: 1) Datasets · p. 6

2) Comparison Methods:

PASTA is evaluated against classical, self-supervised, and noisy-node-classification methods across five graph datasets under multiple noise settings. It consistently performs best, with gains attributed to its losses, multi-annotator labels, and iterative self-training.

Comparison Methods

  • The comparison includes GCN and GAT, self-supervised methods DGI, GCA, and SUGRL, and noisy-node-classification methods JoCoR, NRGNN, MTS-GNN, and BO-NNC.These methods span traditional supervised, label-efficient self-supervised, and noise-robust approaches.Source: 2) Comparison Methods · p. 6

Result Analysis

  • PASTA achieves the best performance across four evaluated datasets, improving by 1.1% over BO-NNC and 12.7% over GCN on average.The evaluation uses classification accuracy under different noise levels; Photo results are provided separately in the appendix.Source: B. Result Analysis · p. 7
  • PASTA improves over DGI by 8.3% under uniform noise and 8.5% under pair noise on average across all datasets.DGI is identified as the strongest among the compared semi-supervised and self-supervised methods.Source: B. Result Analysis · p. 7

Ablation Study

  • Using all three components improves performance by 4.2% over versions with any two components, while adding both losses yields a 1.7% average gain.Self-training produces a further 9.6% average improvement over methods without it.Source: C. Ablation Study · p. 8
  • Multi-annotator consensus labels improve accuracy by 7.5%, 6.9%, and 6.1% over labels generated individually by DGI, GCA, and SUGRL, respectively.The results support exploiting complementary predictions from diverse annotators.Source: C. Ablation Study · p. 8

D. Parameter Sensitivity Analysis

PASTA benefits from iterative optimization: early rounds substantially improve performance, which increases with τ before stabilizing beyond approximately three iterations. Consensus partial labels also preserve multiple candidate categories, avoiding information loss from one-hot pseudo-labels.

Parameter Sensitivity Analysis

  • The sensitivity analysis varies the number of iterative optimization rounds τ from 0 through 5.The loss-balance parameter λ is analyzed separately in the appendix.Source: D. Parameter Sensitivity Analysis · p. 8
  • Initial iterations substantially improve performance over the non-iterative setting by refining annotators with more reliable supervision.The resulting partial labels support more robust classifier training.Source: D. Parameter Sensitivity Analysis · p. 8
  • Performance improves as τ increases and stabilizes when τ exceeds 3, indicating convergence after approximately three iterations.The annotators and classifier mutually enhance each other during self-training.Source: D. Parameter Sensitivity Analysis · p. 8

Consensus Partial Label Visualization

  • Consensus partial labels retain multiple candidate categories, whereas aggregated one-hot pseudo-labels can assign incorrect classes even when an annotator predicts correctly.Retaining multiple candidates preserves accurate information and provides more reliable supervision.Source: E. Consensus Partial Label Visualization · pp. 8–9, §VI · p. 9

APPENDIX

On Photo, PASTA achieves the best classification performance under varying noise rates and is not sensitive to λ across the tested values.

Photo classification results

  • 2.27% and 2.57% improvements over BO-NNC under uniform and pair noise, respectively, make PASTA the best-performing method on Photo.The comparison is reported across different noise rates in Table III.Source: Classification Results of Photo Dataset · p. 10
  • Table III reports classification accuracy (%) for all methods under different noise rates on Photo, with best results shown in bold.Source: Table III · p. 10

Sensitivity analysis

  • λ is tested at 0.01, 0.1, 1, 10, and 100 to assess sensitivity to the Lpasim loss weight.The analysis uses Figure 6 to evaluate this hyperparameter.Source: Sensitivity to λ · p. 10, Figure 6 · p. 10
  • PASTA is reported as insensitive to λ because Lpasim and Lvace have inherently aligned optimization objectives.Source: Sensitivity to λ · p. 10

Related papers

Loading 2608.25365v1…