Research map / Graph learning / GNN architectures
Mitigating Label Noise on Graphs via Topological Sample Selection
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Topological Sample Selection (TSS), an easy-to-hard curriculum that uses a graph-topology measure (Class-conditional Betweenness Centrality) to select clean nodes for GNN training under label noise.
Problem
Learning GNNs from noisily labeled graphs: standard i.i.d. sample selection fails on graphs because nodes near class boundaries are informative but hard to separate from mislabeled nodes, and no topology-aware selection measure exists.
Approach
Defines Class-conditional Betweenness Centrality (CBC), a random-walk (personalized PageRank) betweenness measure counting traversals between node pairs of different (noisy) classes, to rank nodes by proximity to class boundaries; TSS then runs an easy-to-hard curriculum, first selecting confident nodes far from boundaries and then near-boundary nodes.
Key results
- On CORA under 40% symmetric noise, TSS reaches 82.58±0.92 accuracy versus 81.82 for Me-Momentum and 80.86 for cross-entropy.
- TSS achieves best accuracy in all nine synthetic settings across Cora, CiteSeer and PubMed (e.g., 86.69 on PubMed at 30% symmetric).
- On large graphs with 50% instance-dependent noise, TSS reaches 59.33 on WikiCS, 64.46 on Facebook, 86.04 on Physics and 66.30 on DBLP, the best in each column.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use TSS instead of the strongest listed baseline | Noisy-label GNN node classification · Cora; CiteSeer; PubMed, selected symmetric, pairflip, and instance-dependent noise settings | accuracy: 85.02±0.12 vs 83.76±0.25; 85.26±0.30 vs 84.09±0.48; 84.70±0.04 vs 83.14±0.25; 75.86±0.31 vs 75.41±1.04; 77.25±0.44 vs 76 | Helped |
| Use TSS instead of the strongest listed baseline | Noisy-label GNN node classification · WikiCS, Facebook, Physics, and DBLP, instance-dependent noise at 30% and 50% | accuracy: 76.35±0.06 vs 75.28±0.56; 59.33±0.46 vs 58.93±1.12; 77.58±1.81 vs 77.14±2.35; 64.46±1.75 vs 62.46±3.47; 92.64±0.82 vs 90 | Helped |
| Replace CBC with feature-based difficulty measurement (ablation) | TSS · CiteSeer and PubMed, symmetric noise 30% | accuracy: CiteSeer: 74.35±0.86 vs 75.86±0.31; PubMed: 84.11±0.76 vs 86.69±0.32 | Hurt |
| Replace CBC with neighborhood-based difficulty measurement (ablation) | TSS · CiteSeer and PubMed, symmetric noise 30% | accuracy: CiteSeer: 74.54±0.36 vs 75.86±0.31; PubMed: 84.15±0.88 vs 86.69±0.32 | Hurt |
| Use the easy-to-hard schedule instead of one-time confident-node extraction (ablation) | TSS · Cora and CiteSeer noisy-label experiments | accuracy | Helped |
| Vary the pacing function (ablation) | TSS · Various datasets, 20% symmetric noise | accuracy | No clear effect |
| Vary initial pace parameter λ₀ (ablation) | TSS · Cora and PubMed | accuracy | Mixed |
| Change the GNN backbone among GCN, GAT, ARMA, and APPNP (ablation) | TSS · Cora and CiteSeer, symmetric and pairflip noise | accuracy | No clear effect |
Surprising findings
- Co-teaching+ and MentorNet, which work well on i.i.d. data, do not show superior performance on graph data, per the authors.
- RCL performs below plain cross-entropy in many settings (e.g., 63.40 vs 75.14 on Cora at 50% symmetric).
Limitations
- Theoretical bound relies on a hinge-loss linear hypothesis class and an approximate local-independence assumption, so it does not directly certify GNN training.
- CBC is computed with noisy labels over class pairs and relies on a PPR random-walk approximation rather than exact shortest-path betweenness.
Experimental setup
Datasets: Cora CiteSeer PubMed WikiCS Facebook Physics DBLP
Benchmarks: Cora CiteSeer PubMed WikiCS Facebook Physics DBLP
Metrics: classification accuracy
Baselines: Cross-Entropy Co-teaching+ Me-Momentum MentorNet CLNode RCL LPM CP NRGNN PI-GNN RT-GNN RS-GNN
Builds on: Co-teaching+ curriculum learning memorization effect Personalized PageRank
Closest papers by meaning
- NoisyGL: A Comprehensive Benchmark for Graph Neural Networks under Label Noise (NeurIPS 2024 · similarity 0.88)
- Robust Node Classification on Graph Data with Graph and Label Noise (AAAI 2024 · similarity 0.87)
- Label-free Node Classification on Graphs with Large Language Models (LLMs) (ICLR 2024 · similarity 0.87)
- Structural-Entropy-Based Sample Selection for Efficient and Effective Learning (ICLR 2025 · similarity 0.87)
- Topology-Aware Dynamic Reweighting for Distribution Shifts on Graph (ICML 2025 · similarity 0.86)
- TopoGCL: Topological Graph Contrastive Learning (AAAI 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.