Research map / Learning theory and algorithms / Clustering
Spectrally Approximating Large Graphs with Smaller Graphs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Coarsen the graph by randomized edge contraction with a heavy-edge potential | Graph Laplacian · General graphs satisfying the stated eigenvalue condition | principal eigenvalue approximation | Helped |
| Use lifted coarse eigenvectors without refinement | Spectral clustering · Bounded-degree graphs with a sufficiently large cluster eigengap | k-means objective error | Helped |
| Use heavy-edge contraction on graphs with small degree variation | REC · Graph spectral approximation | RSS constants | Helped |
| Increase the dimensionality reduction ratio | REC · Graph spectral approximation | RSS constants | Hurt |
| Apply a few local power-iteration smoothing steps after lifting | Coarsened spectral clustering · MNIST digits 0–4, 12-nearest-neighbor graph | relative k-means error | Helped |
| Use coarsening on eigenspaces without a sufficiently large eigenvalue gap | Lifted principal eigenspaces · Stochastic block model graphs | eigenspace alignment | Hurt |
Closest papers by meaning
- Taxonomy of reduction matrices for Graph Coarsening (NeurIPS 2025 · similarity 0.90)
- Pass-Efficient Algorithms for Graph Spectral Clustering (Student Abstract) (AAAI 2024 · similarity 0.90)
- Structure-Aware Spectral Sparsification via Uniform Edge Sampling (NeurIPS 2025 · similarity 0.89)
- UGC: Universal Graph Coarsening (NeurIPS 2024 · similarity 0.87)
- Dynamic Spectral Clustering with Provable Approximation Guarantee (ICML 2024 · similarity 0.87)
- Generating Graphs via Spectral Diffusion (ICLR 2025 · 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.