Research map / Graph learning / Graph algorithms and clustering
Optimal Graph Clustering without Edge Density Signals
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.
Derives the instance-wise optimal clustering error rate for the Popularity-Adjusted Block Model (PABM) and shows that cluster recovery is possible without edge-density signal when intra- and inter-cluster popularity coefficients differ.
Problem
Characterizing the information-theoretic limits of graph clustering under the popularity-adjusted block model, which has vertex-specific intra- and inter-cluster popularity parameters, and whether recovery is possible when edge densities are equal.
Approach
Derives matching lower and upper bounds on the optimal misclassification rate for PABM via per-vertex Chernoff divergences; shows that per-vertex popularity differences alone make clustering possible even when p=q, and that PABM's expected adjacency rank lies between k and k^2, motivating k^2-eigenvector spectral methods.
Key results
- On synthetic homogeneous PABM with p=q (xi=1) and c large enough, pabm and osc recover clusters while sbm and dcbm variants fail (n=900, k=3, rho=0.05).
- On real data, pabm reaches 0.99 accuracy on liveJournal-top2 and 0.88 on mnist versus 0.44 for sbm and 0.54 for dcbm on mnist.
- The optimal error rate is non-monotone in the inter-cluster edge ratio xi: accuracy first decreases then increases as xi grows when c=0.8.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PABM instead of the strongest baseline | PABM spectral clustering · politicalBlogs | accuracy: 0.95 -> 0.91 | Hurt |
| Use PABM instead of the strongest baseline | PABM spectral clustering · liveJournal-top2 | accuracy: 0.99 -> 0.99 | No clear effect |
| Use PABM instead of the strongest baseline | PABM spectral clustering · citeseer | accuracy: 0.58 -> 0.45 | Hurt |
| Use PABM instead of the strongest baseline | PABM spectral clustering · cora | accuracy: 0.47 -> 0.47 | No clear effect |
| Use PABM instead of the strongest baseline | PABM spectral clustering · mnist | accuracy: 0.79 -> 0.88 | Helped |
| Use PABM instead of the strongest baseline | PABM spectral clustering · fashionmnist | accuracy: 0.60 -> 0.63 | Helped |
| Use PABM instead of the strongest baseline | PABM spectral clustering · cifar10 | accuracy: 0.71 -> 0.74 | Helped |
| Increase the embedding dimension from d=3 to d=6 (ablation) | PABM and OSC spectral clustering on synthetic homogeneous PABM · Synthetic homogeneous PABM | accuracy | Helped |
| Increase the embedding dimension beyond d=6 (ablation) | PABM and OSC spectral clustering on synthetic homogeneous PABM · Synthetic homogeneous PABM | accuracy | No clear effect |
| Increase the embedding dimension (ablation) | SBM and DCBM spectral clustering on synthetic homogeneous PABM · Synthetic homogeneous PABM | accuracy | No clear effect |
| Use PABM- and OSC-specific spectral methods rather than SBM/DCBM variants when c is sufficiently large and ξ=1 | Spectral clustering on synthetic homogeneous PABM · Synthetic homogeneous PABM with ξ=1 | accuracy | Helped |
| Increase ξ from 0 to 1 | PABM and OSC spectral clustering · Synthetic homogeneous PABM with c=0.8 | accuracy | Mixed |
Surprising findings
- Cluster recovery is possible in PABM even when intra- and inter-cluster expected edge densities are equal (p=q), unlike SBM and DCBM.
- The optimal error rate is not monotonically increasing in the number of inter-cluster edges.
Limitations
- Closed-form optimal rate derived only for k=2 equal-size clusters and a restricted homogeneous family (uniform lambda^in with lambda^out=1) in the proposition.
- Assumes Chernoff information grows unboundedly (omega(1)); the constant-error case is only sketched.
- Achievability proof for the MLE is more technical and the practical algorithms (OSC, subspace clustering) lack theoretical analysis.
Experimental setup
Datasets: politicalBlogs liveJournal-top2 citeseer cora mnist fashionmnist cifar10
Benchmarks: politicalBlogs liveJournal-top2 citeseer cora mnist fashionmnist cifar10
Metrics: accuracy misclassification rate
Baselines: sbm spectral clustering dcbm spectral clustering sklearn spectral clustering tcsc gspc
Builds on: stochastic block model degree-corrected block model popularity adjusted block model Chernoff-Hellinger divergence
Closest papers by meaning
- Structure-Aware Spectral Sparsification via Uniform Edge Sampling (NeurIPS 2025 · similarity 0.90)
- Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model (ICML 2025 · similarity 0.90)
- Pass-Efficient Algorithms for Graph Spectral Clustering (Student Abstract) (AAAI 2024 · similarity 0.89)
- A Differentially Private Clustering Algorithm for Well-Clustered Graphs (ICLR 2024 · similarity 0.88)
- Dynamic Correlation Clustering in Sublinear Update Time (ICML 2024 · similarity 0.88)
- On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models (NeurIPS 2024 · similarity 0.87)
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.