Research map / Graph learning / Graph algorithms and clustering
Improved Dynamic Graph Learning through Fault-Tolerant 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 |
|---|---|---|---|
| replace from-scratch spectral sparsification at each time point with fault-tolerant (FT) sparsification maintained by constant-cost per-update insertions/deletions | dynamic graph Laplacian-regularized estimation and SSL · Facebook ego-combined dynamic graph | average update time: 34.2 s to 0.3 ms (speedup > 10^5) | Helped |
| use FT spectral sparsifier instead of from-scratch sparsifier for dynamic updates | Laplacian-regularized estimation and graph SSL · Facebook ego-combined, sigma 0.1 and 0.01 | estimation/SSL error | No clear effect |
| FT sparsification keeps a somewhat larger edge count than from-scratch sparsification | spectral sparsifier size · Facebook ego-combined | # edges: 16502 vs 12978 edges (about 27% more) | Mixed |
Closest papers by meaning
- Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification (ICML 2025 · similarity 0.89)
- Spectral Graph Sparsification Preserves Representation Geometry in Graph Neural Networks (NeurIPS 2026 · similarity 0.88)
- Graph Sparsification via Mixture of Graphs (ICLR 2025 · similarity 0.86)
- Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness (ICML 2024 · similarity 0.86)
- Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition (ICML 2025 · similarity 0.85)
- Joint Graph Rewiring and Feature Denoising via Spectral Resonance (ICLR 2025 · similarity 0.85)
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.