Do Condensed Graphs Survive Deployment Shift?

Graph condensation shrinks a huge training graph into a tiny synthetic one, sometimes a few hundred nodes, so that a graph neural network (a model that updates each node by aggregating its neighbors' features) can be trained cheaply on the small graph instead. The synthetic graph is tuned to imitate one specific real graph, the one used for training. Deployed models, however, run on real graphs that drift over time. Edges go missing, new nodes arrive with different degree patterns, and the graph grows. This is the synthetic-to-real gap familiar from robotics and LiDAR, where a model trained on a clean simulator breaks on noisy sensors. Here the "simulator" is the condensed graph and the "real world" is the shifted deployment graph. Nobody has measured how large this gap is for condensation, and it could decide which condensation designs are worth keeping.

The question also settles a live disagreement. A benchmark study found that condensed graphs with no edges at all work about as well as condensed graphs with learned structure. Another line of work argues that structure must be preserved faithfully. We conjecture that both are right in their own setting. Edges look optional only because every test so far is in-distribution. Under structural shift at deployment, edge-free condensation should degrade most. We further propose a cheap repair: match the synthetic graph against a family of corrupted views of the real graph instead of the single clean one, at a cost that grows linearly with the number of edges.

Core Claim

Our claim has two parts, each falsifiable. The first is a measurement claim. When a model trained on a condensed graph is evaluated on a structurally shifted real graph, the ranking of condensation methods changes. Structure-free variants lose the most. Spectrally faithful ones lose the least. The shift can be temporal, can come from degree-biased edge loss or node subsampling, or can mean moving to a different citation domain.

The second is a method claim. Corruption-marginalized condensation averages or worst-cases a distribution-matching objective over corrupted views of the real graph. It closes most of the resulting robustness gap while keeping the speed of the fast, moment-matching condensers. We expect random corruption to supply most of the gain and a learned adversarial corruption to add a smaller increment. Both parts are tested separately, so a null result on the method still leaves a useful benchmark finding.

Where This Sits in Prior Work

The motivating evidence comes from the condensation literature itself. Graph Condensation for Graph Neural Networks (GCOND) learns synthetic node features and an edge-generating network by matching training gradients against the real graph. It retains 95.3% of Reddit accuracy with 154 nodes, and its edge-free variant GCOND-X is already competitive. GCondenser: Benchmarking Graph Condensation standardizes gradient, distribution and trajectory matching and reports that edges are often optional. It also finds that distribution matching gives the best accuracy-per-compute and that spectral methods run out of time on ogbn-arxiv.

Does Graph Distillation See Like Vision Dataset Counterpart? (SGDD) points the other way. Feature-driven condensation distorts the graph's spectral profile, which it measures as Laplacian energy distribution. SGDD fixes this with graphon-based structure plus optimal-transport alignment, and gains up to 11.3% across architectures. All three papers evaluate on the same distribution the synthetic graph was fit to. Our contribution is to move their evaluation off-distribution, not to propose a fourth matching loss for the in-distribution case.

The method borrows from two sim-to-real papers. Adversarially Masking Synthetic to Mimic Real (ASM) learns, through a differentiable relaxation of discrete choices called Gumbel-Softmax, which points to drop from clean synthetic LiDAR scans. The drops are chosen so the scans resemble real sensor dropout. This raises SynLiDAR→SemKITTI mIoU from 15.2% to 22.8%, and ASM reports that random dropping does not reach this. We reuse its learned-mask idea, but apply it to edges of the real graph during condensation rather than to points.

EdgeMask-DG* adversarially masks edges to find domain-invariant structure. It reaches 78.0% worst-case accuracy on Cora OOD and 73.81 average F1 across ACMv9, DBLPv7 and Citationv1. Its k-NN and spectral-clustering enrichment is cubic in node count, so it does not scale. We keep its adversarial masking but drop the enrichment. The mask then costs one pass over the edge list.

Two papers constrain the design. Simple Graph Condensation (SimGC) matches per-hop feature means and variances from a linear propagation model. It is 6–10× faster than GCOND and reaches 67.0% on ogbn-products at a 0.08% reduction rate. Its smoothness regularizer assumes neighbors share labels, so we remove that term and keep its moment-matching backbone as our base objective. GraphUniverse shows that standard message-passing networks hit a "size wall" when test graphs are larger than training graphs. Condensation creates exactly this setting, with a model trained on hundreds of nodes and deployed on hundreds of thousands. That makes size shift a required axis of our evaluation.

Research Program

We build three things.

1. A shift benchmark for condensation. Each method condenses the training portion of a real graph. We then train standard architectures on the synthetic graph: a graph convolutional network (GCN), GraphSAGE, the attention-based GAT and the more expressive GIN. Each trained model is evaluated on the test portion under five shift protocols, applied only at test time:

  1. the native temporal split of ogbn-arxiv, where test papers come from later years;
  2. uniform edge removal at rates from 10% to 50%;
  3. degree-biased edge removal, where high-degree nodes lose edges preferentially, mimicking incomplete crawls;
  4. induced-subgraph size shift, evaluating on subgraphs much larger or smaller than the condensed graph;
  5. cross-domain transfer, condensing on one of ACMv9, DBLPv7 or Citationv1 and testing on another with a shared label space.

Datasets are Cora, Citeseer, Flickr, Reddit, ogbn-arxiv and ogbn-products, all from Open Graph Benchmark and the condensation papers above.

2. Corruption-marginalized condensation. Let $S_k(X, A)$ denote the class-conditional mean and standard deviation of $k$-hop propagated features on a graph with features $X$ and adjacency $A$, the same statistics SimGC matches. Let $X', A'$ be the synthetic features and adjacency. The objective is

$$ \min_{X',A'} \; \max_{\phi} \; \mathbb{E}_{m \sim q_\phi} \sum_{k=0}^{K} D\big(S_k(X, A \odot m),\, S_k(X', A')\big) \quad \text{s.t. } \mathbb{E}[\lVert 1-m \rVert_1] \le \rho |E|. $$

Here $m$ is a binary edge mask, and $q_\phi$ is a mask distribution produced by a small network. That network reads cheap per-edge signals: endpoint degrees, feature cosine similarity, and edge age where timestamps exist. $D$ is a squared moment distance, $\rho$ is the corruption budget, and $|E|$ is the number of real edges.

Each mask requires one sparse propagation of the real graph, so $M$ sampled masks cost $M$ times SimGC's precomputation. That is linear in edges, with no nested training loop and no eigendecomposition. There are two variants. In the first, $q_\phi$ is fixed to uniform dropout (no max step). In the second, $\phi$ is trained adversarially with the Gumbel-Softmax relaxation. We also run each variant with the synthetic adjacency $A'$ forced to the identity, which isolates whether robustness requires synthetic structure.

3. A diagnostic. For every condensed graph we record the spectral distance to the real graph, measured as SGDD's Laplacian-energy optimal-transport distance. We then test whether that distance predicts robustness under shift better than in-distribution accuracy does. This speaks directly to the "edges are optional" dispute.

Baselines

Full-graph reference. The naive reference is training directly on the full real graph with a scalable sampler, then applying the same test-time shifts. On ogbn-products in-distribution, GraphSAINT reaches 79.08% test accuracy and GraphSAGE 78.50% (Open Graph Benchmark). This upper reference tells us how much of any shift-induced loss comes from condensation rather than from the shift itself.

Existing condensers. We run GCOND, GCOND-X, the distribution-matching method GCDM, SimGC and SGDD through the GCondenser code paths and validator protocol. Condensation ratios are identical, and each method gets the same per-dataset hyperparameter search budget and the same GPU-hour cap. SimGC is the strongest competitor on the speed–accuracy frontier, and its reported 67.0% on ogbn-products at 0.08% is the in-distribution number our method must stay within about one point of. SGDD is the strongest competitor on structural fidelity. If it already holds up under shift, our method is unnecessary; where SGDD times out, we report that as a finding. No reported result on Lacuna was found for any condensation method under structural or temporal deployment shift, so these numbers will be produced here.

Scalability-focused non-condensation methods. These are Fixed Aggregation Features (FAFs) from Fixed Aggregation Features Can Rival GNNs, which feed fixed multi-hop mean, max and standard-deviation features to an ordinary multilayer perceptron (MLP), and FIT-GNN from FIT-GNN, which coarsens the graph for fast inference. Both are run on the full training graph with their own recommended settings. FAFs are compared at matched preprocessing time.

Domain generalization reference. On the citation domains, we compare against EdgeMask-DG*'s reported 73.81 average F1. We also rerun it where memory allows, noting where its cubic precomputation fails.

What counts as winning. The method wins if, averaged over shift protocols, it recovers at least half of the gap between the best existing condenser and the full-graph reference. It must do so at condensation cost within 2× of SimGC and with in-distribution accuracy no more than one point below it.

Key ablations. Uniform-dropout versus adversarial masks isolate the adversarial ingredient. Identity versus learned synthetic adjacency isolates the role of structure.

Why not just…?

Why not just condense a DropEdge-augmented real graph? This is the most serious threat, and we have built it in as the uniform-mask variant. ASM and EdgeMask-DG* both report that static random corruption underperforms learned masking, but in LiDAR and small citation graphs respectively, not in condensation. If uniform masks match adversarial ones across protocols, we will report that the fix is simply "condense under random edge dropout" and drop the adversarial component. Degree-biased removal is the protocol most likely to separate the two, because a learned mask can concentrate corruption where uniform dropout does not.

Why not just use Fixed Aggregation Features and skip condensation? FAFs rival GNNs in-distribution (44.59% versus 44.26% for GCN on Squirrel), and they need no bilevel optimization. However, their features are computed on the clean training graph, so edge loss at test time shifts every aggregated statistic the MLP depends on. They also fail on long-range tasks such as Roman-Empire. The benchmark measures FAFs under the same shifts. If they are as robust as our method at lower cost, that is a real negative result for condensation, and we will state it. Condensation would then remain justified only where a small shareable training set is itself needed, for example in architecture search.

Why not just keep structure-free condensation, since edges are optional? That conclusion rests entirely on in-distribution evaluation. SGDD's 11.3% cross-architecture gap suggests it is fragile, but not specifically under deployment shift. The identity-adjacency ablation, run under every shift protocol, answers this directly. If structure-free variants stay within noise of structured ones under 50% edge removal and on temporal ogbn-arxiv, then our central conjecture is wrong.

Why not just coarsen instead of condensing? FIT-GNN accelerates inference on the real graph but does not produce a small training set. Its partitions are fixed by the clean training topology. We include it to check whether its robustness under shift comes for free, and we treat it as complementary rather than as a replacement.

Decisive Checks

Three results decide the proposal.

The first is the ranking reversal. If structure-free condensers lose significantly more accuracy than SGDD-style condensers under degree-biased edge removal and on the temporal split of ogbn-arxiv and Reddit, measured over five seeds and four architectures, the measurement claim holds. If the ranking is unchanged, the "edges are optional" finding generalizes, and we report that.

The second is whether spectral distance to the real graph predicts drop under shift. We test this by rank correlation across all condensed graphs. The comparison point is whether it predicts better than in-distribution accuracy does.

The third checks the method along three axes. On ogbn-products and ogbn-arxiv, corruption-marginalized condensation should recover a meaningful share of the shift gap at under 2× SimGC's condensation time. On the ACMv9/DBLPv7/Citationv1 transfer, it should be competitive with EdgeMask-DG*'s 73.81 F1 while training on a synthetic graph under 1% of the source size. Its advantage over uniform dropout should appear specifically under non-uniform corruption.

The size-shift protocol additionally tests whether condensation pushes standard message-passing networks into the size wall that GraphUniverse identified. If it does, graph transformers trained on the same condensed graphs should hold up better. That would be a second, independent reason for condensation benchmarks to report off-distribution results.