Research map / Graph learning / GNN architectures
Bi-Directional Multi-Scale Graph Dataset Condensation via Information Bottleneck
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 BiMSGC, a bi-directional multi-scale graph dataset condensation framework that starts from an information-bottleneck-selected meso-scale graph and then condenses to smaller and larger scales via eigenbasis matching with an SCIB objective.
Problem
Condensing sparse graphs into multiple scales simultaneously is costly, and existing large-to-small and small-to-large paradigms suffer scaling-down degradation and scaling-up collapse at different scales.
Approach
Start multi-scale condensation at an information-bottleneck-estimated meso-scale subgraph and propagate outward in both directions (pruning to smaller scales, expanding to larger ones) with a subgraph condensation information bottleneck objective combined with eigenbasis matching.
Key results
- On Citeseer at 0.5% reduction, BiMSGC reaches 73.7 accuracy versus 68.1 for the best baseline GDEM.
- On Reddit at 0.05% reduction, BiMSGC reaches 93.3 accuracy versus 83.6 for GDEM, close to the whole-dataset 93.9.
- The paper reports 20.85x speedup over baselines on Citeseer.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use BiMSGC instead of the strongest listed baseline | GCN node classification · Cora, reduction 0.50% | accuracy: 68.7$_{\pm 3.6}$ -> 78.2$_{\pm 1.3}$ | Helped |
| Use BiMSGC instead of the strongest listed baseline | GCN node classification · Citeseer, reduction 0.50% | accuracy: 68.1$_{\pm 2.5}$ -> 73.7$_{\pm 0.9}$ | Helped |
| Use BiMSGC instead of the strongest listed baseline | GCN node classification · Ogbn-Arxiv, reduction 0.05% | accuracy: 61.0$_{\pm 1.9}$ -> 62.7$_{\pm 0.4}$ | Helped |
| Use BiMSGC instead of the strongest listed baseline | GCN node classification · Flickr, reduction 0.10% | accuracy: 46.2$_{\pm 2.1}$ -> 50.3$_{\pm 0.5}$ | Helped |
| Use BiMSGC instead of the strongest listed baseline | GCN node classification · Reddit, reduction 0.05% | accuracy: 83.6$_{\pm 0.9}$ -> 93.3$_{\pm 0.7}$ | Helped |
| Add information bottleneck (IB) optimization to multi-scale condensation (ablation) | BiMSGC on Citeseer · Citeseer, multiple target reduction scales | accuracy consistency across scales | Helped |
| Increase the initial meso-scale (ablation) | BiMSGC · All evaluated scales | average node-classification accuracy: less than 0.5% | No clear effect |
Surprising findings
- At some reduction rates BiMSGC exceeds the performance of training on the original full dataset (e.g., Cora 80.9 vs. whole dataset 80.9 and Citeseer 73.6 vs. 71.1).
Limitations
- Meso-scale must be selected by pre-setting several candidate scales and comparing them, a preliminary estimate rather than a principled optimum.
- Several baselines run out of memory on Reddit, so comparisons there are incomplete.
- Many key derivations and hyperparameter details are deferred or unclear in the text.
Experimental setup
Datasets: Cora Citeseer Ogbn-Arxiv Flickr Reddit
Benchmarks: Cora Citeseer Ogbn-Arxiv Flickr Reddit
Metrics: node classification accuracy
Baselines: GCond SFGC SGDD EXGC GC-SNTK GCDM GDEM GEOM
Builds on: GDEM GCond VIB GMI MINE
Closest papers by meaning
- Bonsai: Gradient-free Graph Condensation for Node Classification (ICLR 2025 · similarity 0.90)
- Navigating Complexity: Toward Lossless Graph Condensation via Expanding Window Matching (ICML 2024 · similarity 0.90)
- GC4NC: A Benchmark Framework for Graph Condensation on Node Classification with New Insights (NeurIPS 2025 · similarity 0.88)
- GC-Bench: An Open and Unified Benchmark for Graph Condensation (NeurIPS 2024 · similarity 0.88)
- Towards Pre-trained Graph Condensation via Optimal Transport (NeurIPS 2025 · similarity 0.87)
- Adapting Precomputed Features for Efficient Graph Condensation (ICML 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.