Research map / Graph learning / Graph algorithms and clustering
Navigating Complexity: Toward Lossless Graph Condensation via Expanding Window Matching
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes GEOM, a graph condensation method that uses curriculum-trained expert trajectories and expanding window matching (plus a knowledge embedding extractor loss) to approach lossless condensation of graphs.
Problem
Existing graph condensation methods, especially trajectory matching, fail to replicate the original graph's GNN performance on some datasets, because they provide biased and restricted supervision from the original graph.
Approach
Train expert trajectories with curriculum learning over easy-to-difficult nodes to expose more diverse supervision, then match the condensed graph against an expanding window of expert trajectory stages starting from the initial stage, with an added knowledge embedding extractor loss.
Key results
- GEOM achieves state-of-the-art in 18 of 19 node-classification settings, with improvements up to 2.8% according to the authors.
- On Cora at 2.60% ratio, GEOM reaches 82.9 average accuracy across architectures vs. 80.3 for SFGC and 75.9 for GCond; on Citeseer 74.2 vs 71.5.
- Lossless performance (condensed graph matches or beats whole-dataset accuracy) in 20 of 35 architecture-dataset combinations.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GEOM instead of SFGC | Graph condensation · Citeseer (r = 1.80%) | average accuracy: 71.5 -> 74.2 | Helped |
| Use GEOM instead of SFGC | Graph condensation · Cora (r = 2.60%) | average accuracy: 80.3 -> 82.9 | Helped |
| Use GEOM instead of SFGC | Graph condensation · Ogbn-arxiv (r = 0.25%) | average accuracy: 64.3 -> 66.8 | Helped |
| Use GEOM instead of SFGC | Graph condensation · Ogbn-arxiv (r = 5.00%) | average accuracy: 68.5 -> 69.6 | Helped |
| Use GEOM instead of SFGC | Graph condensation · Flickr (r = 0.50%) | average accuracy: 45.0 -> 46.0 | Helped |
| Use GEOM instead of SFGC | Graph condensation · Reddit (r = 0.10%) | average accuracy: 88.2 -> 89.2 | Helped |
| Use GEOM instead of SFGC | Graph condensation · Reddit (r = 5.00%) | average accuracy: 90.4 -> 92.6 | Helped |
| Use expanding-window matching instead of Fixed1 matching (ablation) | GEOM · Cora | accuracy: 82.3 -> 82.9 | Helped |
| Use expanding-window matching instead of Fixed2 matching (ablation) | GEOM · Cora | accuracy: 81.8 -> 82.9 | Helped |
| Use expanding-window matching instead of sliding-window matching (ablation) | GEOM · Cora | accuracy: 80.8 -> 82.9 | Helped |
| Add curriculum learning in the buffer phase (ablation) | GEOM with expanding-window matching · Cora | accuracy: 82.9 -> 83.6 | Helped |
| Add curriculum learning in the buffer phase (ablation) | GEOM with expanding-window matching · Citeseer | accuracy: 73.2 -> 74.3 | Helped |
Surprising findings
- Curriculum learning does not obviously improve final performance; its main role is to yield trajectories with more diverse information.
- Omitting early trajectory information leads to suboptimal results, so the expanding window always starts at 0.
Limitations
- Relies on pre-computing expert trajectories, adding offline computational cost for training expert GNNs.
- Lossless performance is not achieved in all architecture-dataset combinations (20 of 35).
Experimental setup
Datasets: Cora Citeseer Ogbn-arxiv Flickr Reddit
Benchmarks: Cora Citeseer Ogbn-arxiv Flickr Reddit
Metrics: node classification accuracy standard deviation Silhouette Coefficient Davies-Bouldin Index Calinski-Harabasz Index
Baselines: Random Herding K-Center DC-Graph GCond GCond-X SFGC
Builds on: SFGC GCond DC-Graph CLNode
Closest papers by meaning
- Adapting Precomputed Features for Efficient Graph Condensation (ICML 2025 · similarity 0.90)
- Bi-Directional Multi-Scale Graph Dataset Condensation via Information Bottleneck (AAAI 2025 · similarity 0.90)
- Bonsai: Gradient-free Graph Condensation for Node Classification (ICLR 2025 · similarity 0.89)
- Towards Pre-trained Graph Condensation via Optimal Transport (NeurIPS 2025 · similarity 0.89)
- GC-Bench: An Open and Unified Benchmark for Graph Condensation (NeurIPS 2024 · similarity 0.88)
- GC4NC: A Benchmark Framework for Graph Condensation on Node Classification with New Insights (NeurIPS 2025 · similarity 0.88)
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.