Research map / Graph learning / Graph algorithms and clustering
Graph Reduction with Spectral and Cut Guarantees
Andreas Loukas
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 |
|---|---|---|---|
| use local variation (neighborhood) contraction sets instead of heavy edge matching | coarsening · yeast (reduction 70%, k=10) | mean relative eigenvalue error: 3.390 -> 0.406 | Improved |
| use local variation (neighborhood) contraction sets instead of heavy edge matching | coarsening · minnesota (reduction 70%, k=10) | mean relative eigenvalue error: 9.299 -> 1.866 | Improved |
| use local variation (edges) instead of neighborhoods | coarsening · bunny (reduction 70%, k=10) | mean relative eigenvalue error: 0.323 -> 0.081 | Improved |
| use local variation (neighborhoods) instead of edges | coarsening · yeast (reduction 30%, k=10) | mean relative eigenvalue error: 0.123 -> 0.003 | Improved |
| use local variation (neighborhoods) instead of Kron reduction | coarsening · yeast (reduction 70%, k=10) | mean relative eigenvalue error: 1.865 -> 0.406 | Improved |
| use local variation (edges) instead of Kron reduction | coarsening · bunny (reduction 70%, k=40) | mean relative eigenvalue error: 1.192 -> 0.098 | Improved |
| use Kron reduction instead of heavy edge matching | coarsening · yeast (reduction 30%, k=10) | mean relative eigenvalue error: 0.343 -> 0.054 at 30%; 0.921 -> 1.321 at 50% | Mixed |
| increase reduction ratio from 30% to 70% | local variation (neighborhoods) · minnesota, k=10 | mean relative eigenvalue error: 0.078 -> 1.866 | Hurt |
| increase subspace size k from 10 to 40 | local variation (neighborhoods) · yeast (reduction 30%) | mean relative eigenvalue error: 0.003 -> 0.023 | Hurt |
| use local variation methods versus the best state-of-the-art coarsening at maximum reduction | local variation · four graphs, 70% reduction | mean relative eigenvalue error: 3.9x better (2.6x including Kron) | Improved |
| use algebraic distance instead of heavy edge matching | coarsening · airfoil (reduction 70%, k=10) | mean relative eigenvalue error: 4.744 -> 5.544 | Hurt |
Closest papers by meaning
- Taxonomy of reduction matrices for Graph Coarsening (NeurIPS 2025 · similarity 0.92)
- Spectral Graph Sparsification Preserves Representation Geometry in Graph Neural Networks (NeurIPS 2026 · similarity 0.89)
- Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification (ICML 2025 · similarity 0.87)
- Spectral Graph Pruning Against Over-Squashing and Over-Smoothing (NeurIPS 2024 · similarity 0.87)
- Graph Coarsening with Message-Passing Guarantees (NeurIPS 2024 · similarity 0.87)
- Structure-Aware Spectral Sparsification via Uniform Edge Sampling (NeurIPS 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.
