Research map / Graph learning / Graph algorithms and clustering
Improved large-scale graph learning through ridge spectral sparsification
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 |
|---|---|---|---|
| Ridge (gamma>0) spectral sparsification via DiSRe instead of epsilon-sparsifier (ablation) | Laplacian smoothing · Amazon co-purchase graph | edges (x10^6) and squared error at sigma=10^-2: edges drop from 15 to 7.3-14.4 but error rises to 0.760-0.789 vs 0.758 at gamma=0 | Mixed |
| Increase ridge regularization gamma in DiSRe sparsifier (ablation) | Laplacian smoothing · Amazon co-purchase graph | squared error at sigma=10^-3: 0.068 to 0.072 across gamma | No clear effect |
| Use epsilon-sparsifier (DiSRe gamma=0) instead of k-neighbors sparsifier | SSL with harmonic function solution · Amazon co-purchase graph, l=346 and l=672 | SSL error: 0.314 vs 0.329 (l=346); 0.296 vs 0.311 (l=672) relative to kN k=60 | Helped |
| Increase q from 100 to 150 in DiSRe epsilon-sparsifier (ablation) | SSL with harmonic function solution · Amazon co-purchase graph, l=672 | SSL error: 0.296 to 0.310 (worse, within std) | No clear effect |
| Use kN k-neighbors sparsifier instead of DiSRe for Laplacian smoothing | Laplacian smoothing · Amazon co-purchase graph, sigma=10^-3 | squared error: 0.172 (k=60) and 0.125 (k=90) vs 0.068 for DiSRe gamma=0 | Hurt |
Closest papers by meaning
- Improved Dynamic Graph Learning through Fault-Tolerant Sparsification (ICML 2019 · similarity 0.92)
- Spectral Graph Sparsification Preserves Representation Geometry in Graph Neural Networks (NeurIPS 2026 · similarity 0.91)
- Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification (ICML 2025 · similarity 0.89)
- Structure-Aware Spectral Sparsification via Uniform Edge Sampling (NeurIPS 2025 · similarity 0.88)
- Graph Sparsification via Mixture of Graphs (ICLR 2025 · similarity 0.87)
- Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness (ICML 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.