Research map / Graph learning / Graph algorithms and clustering
Local Graph Clustering with Noisy Labels
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 local graph clustering with noisy node labels by reweighting edges (weight epsilon on cross-label edges) and running l2-norm flow diffusion, with theory on a local random model and experiments on six attributed graphs.
Problem
Local graph clustering from a seed node is usually based only on graph structure; the paper asks how noisy binary node labels (cluster membership proxies from attributes) can be exploited locally, without processing the whole graph, to improve recovery of a target cluster.
Approach
Build a weighted graph where edges between nodes with equal noisy labels keep weight 1 and cross-label edges get small weight epsilon, then run l2-norm flow diffusion on it; theory shows this beats diffusion on the original graph under label accuracy above 1/2 in a local random model.
Key results
- Across six attributed graphs, LFD averages 62.5 F1 in the no-ground-truth setting versus 50.6 for single-seed FD and 55.9 for multi-seed FD, a 9.3% average relative improvement over the best baseline.
- With ground-truth samples, LFD improves F1 by up to 13% over other methods (Coauthor Physics with 25 positive and negative nodes).
- On synthetic SBM data, LFD outperforms FD even at label accuracy 0.7 where labels alone reach F1 about 0.2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use label-based edge weights with flow diffusion instead of the strongest reported baseline | Local graph clustering · Coauthor CS (no ground-truth labels) | F1: 50.5 -> 63.1; +12.6 | Helped |
| Use label-based edge weights with flow diffusion instead of the strongest reported baseline | Local graph clustering · Coauthor Physics (no ground-truth labels) | F1: 62.8 -> 72.9; +10.1 | Helped |
| Use label-based edge weights with flow diffusion instead of the strongest reported baseline | Local graph clustering · Amazon Photo (no ground-truth labels) | F1: 62.6 -> 66.8; +4.2 | Helped |
| Use label-based edge weights with flow diffusion instead of the strongest reported baseline | Local graph clustering · Amazon Computers (no ground-truth labels) | F1: 58.2 -> 60.4; +2.2 | Helped |
| Use label-based edge weights with flow diffusion instead of the strongest reported baseline | Local graph clustering · Cora (no ground-truth labels) | F1: 55.4 -> 56.5; +1.1 | Helped |
| Use label-based edge weights with flow diffusion instead of the strongest reported baseline | Local graph clustering · Pubmed (no ground-truth labels) | F1: 53.9 -> 55.3; +1.4 | Helped |
| Increase label accuracy and use the resulting labels for label-weighted diffusion | LFD · Synthetic stochastic block model | F1 | Helped |
| Use noisy labels with label-weighted diffusion rather than diffusion on the original graph | Local clustering on synthetic data · Synthetic stochastic block model; a0=a1=0.7 | F1 | Helped |
| Use a weak classifier's predictions as noisy labels for diffusion | Local graph clustering · Real-world attributed graphs | F1: up to 13% | Helped |
| Set the cross-label edge weight epsilon within [10^{-2},10^{-1}] | LFD · Different datasets with varying cluster sizes and label accuracy | F1 | No clear effect |
| Use additional positive seed nodes | Flow diffusion · Cora | F1 | Hurt |
Surprising findings
- Even very noisy labels (weak classifier with F1 around 40%) improve diffusion, and the classifier can be simple logistic regression.
- Adding more ground-truth seed nodes can increase mass leakage and reduce accuracy on Cora, which the learned classifier mitigates by down-weighting cross-label edges.
Limitations
- Theoretical guarantees rely on a random local model with strong density assumptions (p, q scaling with log k) and on a single seed node and epsilon=0.
- Empirical gains are reported with the F1 metric against ground-truth communities of graph datasets treated as clusters; the classifier relies on node attributes being informative.
Experimental setup
Datasets: Amazon Photo Coauthor CS Coauthor Physics Amazon Computers Cora Pubmed synthetic stochastic block model
Benchmarks: Amazon Photo Coauthor CS Coauthor Physics Amazon Computers Cora Pubmed synthetic SBM
Metrics: F1 score
Baselines: Flow Diffusion (FD) Weighted Flow Diffusion (WFD) PageRank (PR) Labels alone Logistic Regression classifier
Builds on: l2-norm flow diffusion weighted flow diffusion approximate personalized PageRank local random model
Closest papers by meaning
- Weighted Flow Diffusion for Local Graph Clustering with Node Attributes: an Algorithm and Statistical Guarantees (ICML 2023 · similarity 0.93)
- Efficient Testing for Correlation Clustering: Improved Algorithms and Optimal Bounds (ICLR 2026 · similarity 0.89)
- THESAURUS: Contrastive Graph Clustering by Swapping Fused Gromov-Wasserstein Couplings (AAAI 2025 · similarity 0.87)
- NoisyGL: A Comprehensive Benchmark for Graph Neural Networks under Label Noise (NeurIPS 2024 · similarity 0.87)
- DGCLUSTER: A Neural Framework for Attributed Graph Clustering via Modularity Maximization (AAAI 2024 · similarity 0.87)
- Optimal Graph Clustering without Edge Density Signals (NeurIPS 2025 · 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.