Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data

What came before

GCond (and its one-step cousin DosCond) solve graph condensation by jointly optimizing condensed features, a learned/generated adjacency matrix, and GNN parameters — a triple-level problem — using short-range (single- or few-step) online gradient matching against the real graph's GNN gradients. SFGC argues this inherits two problems from that design rather than from graphs per se.

The problem

Short-range online gradient matching only imitates a few steps of GNN training at a time ("short-sight"), so the condensed graph fails to capture the GNN's holistic, long-term learning behavior; and jointly learning node features, a graph-structure-learning module, and GNN parameters (triple-level) makes it hard to reach a jointly optimal solution and causes the condensed structure to overfit the specific GNN convolution used during condensation, hurting cross-architecture generalization.

The idea

If the graph condensation goal is really about matching long-term GNN training behavior, drop the graph structure entirely — represent the condensed data as a bare node set with identity adjacency — and let the node features implicitly absorb whatever structural information matters, learned by matching whole segments of pretrained expert training trajectories (not single gradient steps) instead of raw gradients.

How it works

Offline, trains $K$ expert GNNs on the full graph and stores their parameter snapshots $\{\theta_t^{*,i}\}_{t=1}^T$ as trajectories. Online, samples a trajectory and a start step $t_0$, initializes a student GNN$_\mathcal{S}$ at $\theta_{t_0}^{*,i}$, trains it for $q$ steps on the condensed graph-free data $\mathcal{S}=(\widetilde{\mathbf{X}},\mathbf{I},\widetilde{\mathbf{Y}})$ (identity adjacency, fixed hard labels), and minimizes a meta-matching loss $\mathcal{L}_{\text{meta-tt}}=\|\widetilde{\theta}_{t_0+q}-\theta_{t_0+p}^{*,i}\|^2 / \|\widetilde{\theta}_{t_0}-\theta_{t_0+p}^{*,i}\|^2$ that aligns the student's endpoint after $q$ steps to the expert's endpoint after $p$ steps, backpropagating through the $q$-step training to update $\widetilde{\mathbf{X}}$. Because a condensed-graph-free candidate cannot be scored without training a GNN on it, a graph neural tangent kernel (GNTK) ridge-regression "graph neural feature score" gives a closed-form validation error (a KIP-style criterion adapted to GNTK) used to pick the best candidate across the meta-matching trajectory without extra iterative training.

Evidence

Table 1 (GCN condensation and evaluation, hard labels, node classification, 10 repeats): SFGC wins 13 of 15 dataset x ratio combinations against GCond, GCond-X, DC-Graph, coreset and coarsening baselines; on Cora r=2.6% SFGC reaches 81.7% vs. 81.2% whole-dataset (exceeding the original graph); on ogbn-arxiv r=0.05% SFGC reaches 65.5% vs. GCond's 61.3% (whole 71.4%), the largest margin over GCond in the table. Table 2 (cross-architecture transfer to MLP/GAT/APPNP/Cheby/GCN/SAGE/SGC): SFGC's average score beats GCond and GCond-X on both Citeseer (71.5 vs. 69.0/70.2) and Cora (80.3 vs. 78.4/75.7), including on GAT and MLP where GCond loses much more accuracy (e.g. GCond's GAT drops to 55.4/66.2 on Citeseer/Cora vs. SFGC's 72.1/80.8) — attributed directly to identity-structure data having nothing for any specific convolution operator to overfit. Key ablation (Fig. 3): five variants that add back a learned structure (discrete kNN with k=1/2/5, continuous cosine-similarity structure, a GCond-style parameterized structure module) all underperform the structure-free SFGC across three transductive datasets and nine ratios, and the parameterized-structure variant "almost fails" under the meta-matching objective. Efficiency (Appendix E.1): the GNTK-based score takes 0.015s vs. 0.845s for iterative-training evaluation on Flickr (r=0.1%), and 0.042s vs. 4.264s on ogbn-arxiv (r=0.05%).

Limitations

Only node-level condensation of a single graph is addressed; the conclusion explicitly leaves graph-level condensation (condensing a set of many graphs, DosCond/SFGC's counterpart problem) to future work. The offline expert-trajectory pretraining is an added upfront cost not folded into the reported per-step efficiency numbers. Results are reported only with GCN as the trajectory-generating architecture (cross-architecture generalization is evaluated only at test time, not for experts of other architectures). The parameterized-structure ablation "almost fails," suggesting the meta-matching objective is specifically tuned to the identity-structure case and may not transfer cleanly to methods that still want some structure.