Breaking the Size Wall with Small Synthetic Graphs

Graph neural networks (GNNs), models that update each node by repeatedly combining messages from its neighbors, are often trained on small graphs and then run on much larger ones. When the graphs grow, accuracy frequently collapses. GraphUniverse calls this the "size wall." It is a synthetic benchmark that samples families of graphs sharing the same community semantics, and on it standard message-passing networks fail on graphs larger than those seen in training, while graph transformers do not. The obvious fixes are expensive. One is to train on large graphs, which makes synthetic data generation and training cost grow with graph size. The other is to switch to attention over all node pairs, which costs more at deployment.

This proposal argues that the size wall is not really about size. A message-passing network with $L$ layers only ever sees each node's $L$-hop neighborhood, the set of nodes within $L$ edges of it. We hypothesize that the wall appears when deployment graphs contain local neighborhoods unlike any in training: hubs with higher degree, larger 2-hop sets, different clustering. Small training graphs simply cannot contain such neighborhoods unless they are generated on purpose. If that is right, one could tune a cheap generator so that its small graphs reproduce the neighborhood statistics of the target graph. A model trained this way should cross the wall at a fraction of the generation and training cost of size-matched data. The same account also predicts where the wall should appear, which makes it straightforward to refute.

Core Claim

For an $L$-layer message-passing network, the out-of-size accuracy drop is governed by the mismatch between training and deployment distributions of label-free rooted-neighborhood statistics. Raw node count matters only because it caps those statistics. Concretely, let $s(v)$ be a short vector computed around node $v$ without labels: its degree, the degrees of its neighbors, its 2-hop neighborhood size up to hop $L$, and its local clustering. We choose the parameters $\theta$ of a degree-corrected stochastic block model (a random graph generator where nodes belong to communities and each node has its own degree propensity) to solve

$$\theta^\star = \arg\min_\theta \; D\big(P_{\text{target}}(s),\, P_{\theta,n}(s)\big),$$

where $P_{\text{target}}$ is the distribution of $s$ over the unlabeled deployment graph, $P_{\theta,n}$ is its distribution over generated graphs with $n$ nodes, and $D$ is a sliced Wasserstein distance. The target statistics need no labels, so they can be computed on the deployment graph in one linear-time pass.

The claim yields a sharp prediction. A graph with $n$ nodes cannot contain an $L$-hop neighborhood larger than $n$. So the minimum training size that avoids the wall should track the upper quantiles of the target's $L$-hop neighborhood size. That quantity grows with depth $L$ and with how heavy the degree tail is, and only indirectly with target size. If adding layers does not move the wall, or if statistic-matched small graphs fail where size-matched graphs succeed, the claim is wrong.

The claim also resolves a tension in the file. GraphWorld, a large sweep of synthetic graphs for benchmarking GNNs, found graph size negligible for node classification. But its tasks train and test on the same graph, so neighborhood statistics never shift. Under our account it should see no size effect. The partitioning models GAP and PR-GPT transfer from 1,000- or 5,000-node graphs to graphs with 20,000 to 1,000,000 nodes. They use shallow or simplified propagation, which is consistent with small-$L$ neighborhoods that small graphs can already cover.

Relation to Prior Work

Three groups of papers bear on this, in different roles. The first group motivates the problem. GraphUniverse documents the size wall and the non-monotonic effect of homophily, the tendency of linked nodes to share a class. It uses its hierarchical generator strictly for evaluation. We reuse that generator as a training-data engine and add a matching step that it does not have.

The second group supplies the cost argument. GraphUniverse reports about 1.3 seconds per 1,000-node graph on a consumer CPU, and GraphWorld reports generating and benchmarking millions of graphs for under \$120. Generation itself is cheap. Training cost on large graphs, and attention cost at deployment, are what grow. Outside graphs, TDScaling shows that steering synthetic data toward diversity beats piling up quantity for code agents, and DISCO shows 75,000 filtered examples beating more than a million unfiltered ones. Our approach is the graph analogue of both. Instead of generic diversity, we target the coverage of exactly the statistics the model can see.

The third group is the closest competing approach, and it constrains the design. MCond condenses a large graph into a small synthetic one plus a learned mapping for unseen nodes, using bi-level gradient matching. GCondenser benchmarks such condensation methods, finds structure-free condensates often suffice, and finds trajectory matching slow and eigenbasis matching out of time on ogbn-arxiv. Both distill a specific observed graph through expensive optimization and never test transfer to differently shaped graphs. We optimize a handful of generator parameters against label-free statistics in closed form. Our target is a different, larger graph.

Research Program

The work has three parts.

The first part is diagnostic. On GraphUniverse families, we train GCN, GraphSAGE, GATv2 (Graph Attention Networks), and GIN at depths $L \in \{1,2,3,4\}$ on graphs of size $n_{\text{train}}$. We test at sizes up to 50 times larger. We regress the accuracy drop on the training-to-deployment discrepancy in $s$ and, separately, on the size ratio. If the claim holds, the discrepancy should explain most of the variance and size should add little. The predicted wall location, where the upper quantile of $L$-hop neighborhood size exceeds $n_{\text{train}}$, should shift with $L$.

The second part builds the matching generator. We fit $\theta$ (degree exponent, average degree, community count, and a hub-injection parameter that places a few high-propensity nodes) by derivative-free search, because each evaluation is a seconds-long CPU sample. We do this under explicit budgets measured in total generated edges and GPU training minutes. Homophily is label-dependent and unobservable at deployment, so we do not match it. Instead we randomize it over a range and report separately whether homophily shift remains a residual failure.

The third part transfers the idea to real graphs. On Reddit and Flickr inductive node classification, we train on small subgraphs of the training graph. These subgraphs are chosen by weighted sampling so that their neighborhood statistics match those of the full deployment graph. We then run the trained model on the full graph.

Baselines

The naive reference point is training on GraphUniverse graphs of the same small size $n_{\text{train}}$, with family parameters drawn uniformly ("domain randomization"), and no matching. It sets the floor and shows the wall. It gets the same edge budget, model sizes, and hyperparameter search budget (the same number of trials per method) as every other condition.

The strongest data-side competitor is size-matched synthetic training: generate graphs as large as the deployment graph from the same family. This is what one would do if size were the cause, and it is the upper bound on what data alone can buy. We run it at equal accuracy-targets and report the cost it needs, in generated edges and training GPU-minutes. Beating it means matching its out-of-size accuracy within one standard deviation over five seeds at a substantially lower cost. We aim for at least a fivefold reduction in training edges. If it is strictly more accurate at equal cost, our claim fails.

The strongest architecture-side competitor is GPS, the graph transformer that GraphUniverse reports as size-invariant. It is trained on the naive small graphs with the same tuning budget. We compare accuracy and deployment cost per node. The file gives no per-size accuracy numbers for GPS or the MPNNs, so we report our own reproduction (no reported result found on Lacuna for size-wall accuracy values).

On real graphs, the strongest existing method is MCond. It reports 91.53% inductive accuracy on Reddit against a 94.00% full-graph baseline, with a 121.5× inference speedup. We also include the random-subgraph and K-Center baselines it was compared against. We compare against MCond's published number and, where feasible, a rerun under our protocol. We also record condensation wall-clock time, because MCond's bi-level optimization is its main cost. Beating it means reaching at least 91.53% on Reddit with lower total offline compute.

The key ablation isolates the matching ingredient. It keeps the generator, size, and budget fixed and replaces matched $\theta$ with random $\theta$ that has the same mean degree. A second ablation matches only the degree histogram, without 2-hop statistics, to test whether the depth-dependent statistics matter.

Why not just…?

Why not just switch to a graph transformer? This is a real threat on accuracy, since GraphUniverse reports that GPS holds up across sizes. The question here is different: whether the cheaper and more widely deployed message-passing models can be fixed by data alone. Our experiments report accuracy against deployment cost on graphs up to Reddit scale. If GPS matches accuracy at comparable deployment cost, we will say the data-side fix is unnecessary for that regime.

Why not just train on bigger synthetic graphs? Generation is cheap, so this could plausibly work as well. That is why it is our main baseline rather than a straw man. The proposal is worth pursuing only if matched small graphs reach the same accuracy for less training compute, or if the depth sweep shows that size-matched data succeeds because it covers neighborhood statistics. The regression in the diagnostic phase settles which account is right.

Why not just randomize generator parameters widely? Broad randomization is the cheap version of diversity scaling. TDScaling suggests that diversity helps, but undirected diversity wastes budget on neighborhoods the target never contains. More importantly, small graphs cannot contain large $L$-hop neighborhoods no matter how their parameters are randomized. The random-$\theta$ ablation measures exactly this gap.

Why not just use graph condensation or random subsampling? MCond already shows that random sampling and K-Center fracture neighborhoods and degrade inductive accuracy. Condensation, however, needs bi-level optimization and is tied to one observed graph. GCondenser documents the cost of the stronger variants and never tests transfer under structural shift. Our Reddit and Flickr comparison measures accuracy and offline compute directly against both.

Why not just change the aggregator or normalization? Mean aggregation or degree normalization may blunt hub effects without new data. We include mean-aggregating GraphSAGE and degree-normalized GCN as backbones. If they remove the wall on naive small graphs, the problem is architectural and our method becomes unnecessary for them.

Proposed Experiments and Decisive Checks

The primary testbed is GraphUniverse inductive node classification. We train at sizes of 200 to 2,000 nodes and test at 2,000 to 100,000 nodes. We cross this with degree-exponent and homophily shifts, and also use the GraphUniverse families mapped from MolHIV, AQSOL, IMDB-MULTI, NCI1 and ZINC, where the authors report rank correlations above 0.8 with real-world model rankings. The secondary testbed is Reddit and Flickr inductive node classification, with Pubmed as a smaller check. Metrics are test accuracy as a function of the size ratio, the area under that curve, generated edges and GPU-minutes to reach a fixed accuracy, and deployment latency per node. Everything is averaged over five seeds.

The first decisive check is the depth-shift test. If the wall's onset does not move when $L$ increases from 1 to 4, in line with the predicted $L$-hop neighborhood quantile, the mechanism is wrong. The second check holds size fixed and varies the hub-injection parameter, then holds statistics fixed and varies size. Accuracy should follow the statistics, not the size. The third check is the cost frontier: matched small-graph training must sit on or above the size-matched curve at a lower cost. If size-matched training dominates everywhere, we will report that the size wall is better solved by scale, and the cheap-generation account fails.