Graph Condensation for Graph Neural Networks

What came before

Prior graph-size reduction was graph sparsification (drop edges to preserve pairwise distances/cuts/eigenvalues) and graph coarsening (group nodes into super-nodes), neither of which is optimized for downstream GNN accuracy and neither of which reduces node attributes. Dataset distillation (DD) and dataset condensation (DC, gradient matching) had solved the analogous problem for images but assume independent, Euclidean samples.

The problem

Image-style condensation cannot be applied to graphs because nodes are interdependent through edges (message passing couples every node to its neighborhood), so there is no notion of condensing "one sample" independently of the rest of the graph; the paper also observes that the discrete adjacency matrix has O(N'^2) parameters if learned freely, which overfits as the condensed graph grows.

The idea

Treat graph condensation as the same gradient-matching bi-level problem as image DC (match per-step GNN parameter gradients between condensed and real data across random initializations), but resolve the graph-specific coupling by parameterizing the condensed adjacency matrix as a function of the condensed node features (an MLP over pairs of feature vectors) instead of a free parameter, so structure and features are optimized jointly but structure never needs its own O(N'^2) parameter block.

How it works

Optimizes condensed features $\mathbf{X}'$ and an MLP $g_\Phi$ that outputs $\mathbf{A}'=g_\Phi(\mathbf{X}')$ (symmetrized sigmoid of an MLP over concatenated node-feature pairs); condensed labels $\mathbf{Y}'$ are fixed to match the real class distribution and never learned. In the loop: a GNN (SGC used for the condensation objective, GCN for evaluation) is initialized from a distribution $P_{\theta_0}$, trained for one step at a time on both the condensed graph and a class-wise sampled batch of real nodes (with sampled neighbors), and $\mathbf{X}'$/$\Phi$ are updated to minimize the cosine-distance gradient-matching loss $\sum_t D(\nabla_\theta \mathcal{L}(\mathrm{GNN}_{\theta_t}(\mathbf{A}',\mathbf{X}'),\mathbf{Y}'), \nabla_\theta \mathcal{L}(\mathrm{GNN}_{\theta_t}(\mathbf{A},\mathbf{X}),\mathbf{Y}))$, summed per class to ease optimization. $\mathbf{X}'$ and $\Phi$ are updated in alternating blocks of epochs rather than jointly. After training, small edge weights in $\mathbf{A}'$ are thresholded away to sparsify storage. A "graphless" variant, GCond-x, fixes $\mathbf{A}'=\mathbf{I}$ and only learns $\mathbf{X}'$.

Evidence

Table 2 (GCN evaluator, hard labels, node classification, 10 repeats): on Cora at r=1.3% GCond reaches 79.8% vs. 81.2% whole-dataset accuracy; on Reddit at r=0.1% GCond reaches 89.6% vs. 93.9% whole (the abstract's headline 95.3%-of-original number); on Flickr at r=1% GCond reaches 47.1% vs. 47.1% whole (matches exactly); the largest gap is ogbn-arxiv at r=0.05%, 61.3% vs. 71.4% whole. GCond beats random, herding, k-center and graph-coarsening baselines by a large margin at the smallest ratios (Obs 1). Table 3/4 show cross-architecture transfer (APPNP/Cheby/GCN/GraphSAGE/SGC/MLP/GAT) with no more than a few points of drop. Table 5 reports storage: Reddit condenses from 435.5MB/153,932 nodes to 0.4MB/153 nodes. Key ablation: GCond-x (features only, identity adjacency) matches GCond within a point or two on 11 of 15 dataset/ratio combinations, showing that most of the gradient-matching signal is absorbed into node features even when no explicit structure is learned; explicit structure mainly helps cross-architecture generalization and interpretability rather than raw accuracy.

Limitations

The gap to whole-dataset accuracy grows on the largest, most heterophilous graph tested (ogbn-arxiv); node labels are fixed rather than learned/relabeled; only single-label transductive/inductive node classification is addressed, with graph-level classification and multi-label settings left as future work (stated in the conclusion); jointly optimizing features and structure is unstable enough to require an alternating-block schedule rather than joint gradient descent; and the learned structure is sometimes uninterpretable (a near star-graph on Reddit), suggesting the structure channel can degenerate to a trivial solution the accuracy metric cannot detect.