Navigating Complexity: Toward Lossless Graph Condensation via Expanding Window Matching

What came before

SFGC introduced structure-free graph condensation via short-segment training-trajectory meta-matching against offline expert trajectories, improving on GCond's short-range online gradient matching. GEOM diagnoses a specific remaining failure of SFGC-style trajectory matching on large graphs: performance saturates as the condensation ratio grows and never reaches the original graph's accuracy.

The problem

GEOM traces the saturation to the composition of the supervision signal: visualizing gradient norms by node "difficulty" (homophily-based), it finds difficult (low-homophily) nodes dominate the expert trajectory's gradient, biasing the condensed graph toward difficult-node patterns and away from the easy, representative nodes that actually carry most of the class signal; separately, prior trajectory matching only samples a narrow, fixed range of expert checkpoints, wasting most of the trajectory.

The idea

Fix the supervision at its source with two changes: (1) train expert trajectories with curriculum learning (easy-to-difficult node ordering by a homophily-based difficulty score) so trajectories carry a better mix of easy/difficult supervision, and (2) match against an expanding window of expert checkpoints (growing from an early, narrow range to a wide one over the course of condensation) instead of a fixed or sliding window, using ~10x more checkpoints than prior trajectory matching; a theoretical accumulated-error decomposition (initialization error + matching error, following Du et al. 2023) justifies why both changes reduce the training/evaluation-time distribution gap.

How it works

Buffer phase: train GNN experts on the full graph with a curriculum scheduler (nodes ranked by a neighborhood-label-entropy difficulty score, easy nodes introduced first via a pacing function) and save checkpoints $\{\theta_t^*\}$. Condensation phase: sample a checkpoint pair within an expanding matching range $\mathcal{R}$ (bounded by growing thresholds $U,U'$), initialize a student GNN$_\mathcal{S}$ at $\theta_t^*$, unroll $q$ training steps on the structure-free condensed data $\mathcal{S}=(\widetilde{ \mathbf{X}},\mathbf{I},\widetilde{\mathbf{Y}})$ with a learnable learning rate, and minimize a trajectory meta-matching loss $\mathcal{L}_M$ (same form as SFGC) plus a Knowledge-Embedding-Extractor term $\mathcal{L}_E=\mathrm{KL}(f(\theta_T^*;\mathcal{S})\,\|\,\widetilde{\mathcal{Y}})$ that KL-distills soft labels $\widetilde{\mathcal{Y}}$ from late-trajectory expert checkpoints into the condensed data, backpropagating both terms through the $q$-step unroll to update $\widetilde{\mathbf{X}}$ and $\widetilde{\mathcal{Y}}$.

Evidence

Table 1 (GCN condensation/evaluation, node classification, 10 repeats): state-of-the-art in 18/19 settings; reports the first "lossless" graph condensation results — ogbn-arxiv r=5% reaches 71.4% vs. 71.4% whole dataset (exact match, where GCond ran out of memory at this ratio); Cora r=2.6% reaches 83.6% vs. 81.2% whole (exceeding the original graph); Citeseer r=1.8% reaches 74.3% vs. 71.7% whole. Table 2 (cross-architecture, MLP/GAT/APPNP/Cheby/GCN/SAGE/SGC): lossless in 20/35 architecture x dataset x ratio cells. Key ablation (Table 3): expanding-window matching beats two fixed-window variants and a sliding-window variant on both Cora and Citeseer, with or without curriculum learning (CL); CL alone gives smaller gains than expanding-window alone, but the combination is best (e.g. Cora 80.8->83.6 sliding-w/o-CL to expanding-with-CL); a separate ablation (Fig. 4) shows the KEE soft-label term gives further gains especially once the trajectory-matching loss plateaus.

Limitations

Explicitly stated: GEOM still requires deriving expert trajectories in advance, adding non-trivial upfront GNN-training cost that the paper does not offset (future work is to improve this efficiency). Also observed: it is not lossless everywhere (1/19 cases in Table 1 is not state-of-the-art, and only 20/35 cross-architecture cells are lossless); the curriculum-learning difficulty measure is specific to homophily-based node classification and does not obviously transfer to graph-level classification; GCond itself runs out of memory at ogbn-arxiv r=5%, so GEOM's "lossless" claim there has no GCond comparison point at that ratio.