Research map / Graph learning / GNN architectures
Scalable Topology-Preserving Graph Coarsening: Concepts and Algorithms
Xiang Wu, Rong-Hua Li, Xunkai Li, Kangfei Zhao, Hongchao Qin, Guoren Wang
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 |
|---|---|---|---|
| replace clique-enumeration elementary collapse (GEC) with strong/edge collapse and neighborhood coning | graph coarsening · DBLP runtime, c=0.1 | running time (s): 100.417 -> 6.371 | Improved |
| replace GEC with STPGC | graph coarsening · ogbn-arXiv runtime, c=0.1 | running time (s): 2474.5 -> 286.3 | Improved |
| replace GEC with STPGC | graph coarsening · cit-Patent scalability | runtime: up to 37x | Improved |
| use STPGC instead of GEC | GCN on coarsened graph · Cora, c=0.1 | accuracy: 80.8 -> 82.5 | Improved |
| use STPGC instead of GEC | GCN on coarsened graph · ogbn-arXiv, c=0.1 | accuracy: 65.1 -> 63.2 | Hurt |
| use STPGC instead of GEC | GCN on coarsened graph · five datasets average | accuracy: +1.73% | Improved |
| preserve topology instead of spectral/spatial coarsening | STPGC and GEC · node classification | accuracy | Improved |
| increase degree threshold theta1 (ablation) | STPGC · Cora, ogbn-arXiv | accuracy and runtime | Mixed |
| partition graph before collapse (as in GEC) | GEC · Betti number preservation | 1-Betti number | Hurt |
| apply STPGC to link prediction at c=0.5 | GCN link prediction · Cora | AUC: 88.41 -> 89.62 | Improved |
| add 20% random edges before coarsening (ablation) | STPGC · Cora, c=0.5 | accuracy: 81.7 vs 78.0 (deletion vs addition) | Hurt |
| delete random edges before coarsening (ablation) | STPGC · Cora | accuracy | No clear effect |
Closest papers by meaning
- Graph Coarsening with Message-Passing Guarantees (NeurIPS 2024 · similarity 0.89)
- Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness (ICML 2024 · similarity 0.88)
- Graph Coarsening via Supervised Granular-Ball for Scalable Graph Neural Network Training (AAAI 2025 · similarity 0.88)
- A Topology-aware Graph Coarsening Framework for Continual Graph Learning (NeurIPS 2024 · similarity 0.87)
- GC4NC: A Benchmark Framework for Graph Condensation on Node Classification with New Insights (NeurIPS 2025 · similarity 0.87)
- Bonsai: Gradient-free Graph Condensation for Node Classification (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.
