Pick $k$ vertices of a large graph at random and count the edges among them. Repeat many times and you get a histogram, the graph's induced edge-count profile. This one-dimensional object is what the Erdős–McKay line of extremal graph theory studies. That work asks how many distinct values the histogram must hit when the graph has no large clique or independent set. It is also a cheap, permutation-free summary that a statistician can compute on a graph with millions of nodes.
We propose to make this profile into a calibrated hypothesis test. The test statistic is the one-dimensional Wasserstein distance, meaning the area between two cumulative distribution functions. It compares a graph's sampled profile to the profile predicted by a fitted random-graph model (goodness of fit), or to another graph's profile (two-sample). The work has three parts. We derive the correct null limit, which is non-Gaussian and changes rate when the reference model is Erdős–Rényi. We give finite-sample validity guarantees with explicit, small constants. We then check whether the resulting test beats simpler histogram, kernel, and bootstrap tests on standard graph benchmarks.
Core Claim
The profile $\mu_{G,k}$ is the law of $e(G[S])$, the edge count of the subgraph induced on a uniformly random $k$-subset $S$. It lives on the ordered integers $\{0,\dots,\binom{k}{2}\}$. The natural distance on it is
$$T = \sqrt{M}\,\sum_{t=0}^{\binom{k}{2}-1} \big|\hat F_M(t) - F_\nu(t)\big|,$$
where $\hat F_M$ is the empirical cumulative distribution function (CDF) from $M$ sampled subsets and $F_\nu$ is the CDF of the reference profile $\nu$. We make three claims.
First, under the null the limit of $T$ is a sum of absolute values of a correlated Gaussian vector, not a normal. This is the degenerate case where transport CLTs lose their linear term.
Second, the statistic has two noise sources: subset sampling at rate $M^{-1/2}$, and the graph's own randomness given the model. When the model is a non-constant graphon, the graph-level term is driven by the vertices' hidden positions and scales as $n^{-1/2}$. When the model is Erdős–Rényi with estimated density, that first-order term vanishes and the graph-level fluctuation drops to order $n^{-1}$. A test calibrated for one regime is miscalibrated in the other.
Third, because the problem is one-dimensional with at most $\binom{k}{2}+1$ support points, the finite-sample error of the limit can be bounded with explicit constants small enough to matter at $k\in\{3,4,5\}$ and $M$ in the thousands. This is the regime where generic Hoeffding-style thresholds are loose.
Where This Sits
Transport inference (the core mechanism). The method comes from the transport-inference literature. Central limit theorems for empirical transportation cost in general dimension and Central limit theorems for general transportation costs linearize the cost through unique dual potentials when $P\neq Q$. They also show that this linearization collapses when $P=Q$, which is exactly the goodness-of-fit null.
Central limit theorems for semi-discrete Wasserstein distances handles finitely supported measures and obtains a supremum-of-Gaussian limit through Hadamard differentiability. Our setting is fully discrete and one-dimensional, so the limit takes an explicit form. Our samples, however, are not i.i.d. draws from a fixed measure: the measure itself comes from a random graph, which none of these papers treat.
Entropic and sliced approaches (Statistical bounds for entropic optimal transport, Limit theorems for entropic optimal transport maps and Sinkhorn divergence, Distributional Convergence of the Sliced Wasserstein Process) regularize or project to reach parametric rates. We need neither, because the profile is already one-dimensional. Those works motivate the degenerate-null problem but do not supply our limit.
Graph statistics (the closest competitors, and the application). A Few Moments Please: Scalable Graphon Learning via Moment Matching fits graphons by matching subgraph counts instead of solving Gromov–Wasserstein alignments. It bounds cut distance but gives no distributional theory. We reuse its fitted graphons as the null models $\nu$ to be tested. Efficient graphlet kernels for large graph comparison samples $k$-vertex graphlets with an $L_1$ deviation bound whose sample size is independent of $n$. That is the closest existing guarantee, and its unoptimized concentration constants are what we aim to beat. Subgraph Matching via Partial Optimal Transport and A Fused Gromov-Wasserstein Approach to Subgraph Contrastive Learning use transport between graphs for matching and representation learning. They offer no inference, and we deliberately avoid their non-convex alignment.
Extremal theory (a structural constraint). The extremal results tell us when the profile cannot collapse onto a few values. Induced subgraphs with distinct sizes shows that a graph with density bounded away from 0 and 1 has at least $10^{-7}k$ distinct $k$-vertex edge counts. Induced subgraphs of prescribed size forces $n^\delta$ distinct edge counts in graphs without logarithmic homogeneous sets. Both papers state that their constants are not optimized, and $10^{-7}$ is useless as a quantitative non-degeneracy input.
We therefore do not build on those constants. We prove the weaker, directly needed fact: an explicit lower bound on the variance of $e(G[S])$, computable from degree and codegree statistics of $G$. This quantity plays the role that connected support plays in the semi-discrete CLT. Where it is small the test is underpowered, and we report that honestly rather than hiding it.
Constant-factor refinement (a constraint on the proofs). Constant-factor optimization shapes the finite-sample part. Learning with Square Loss: Localization through Offset Rademacher Complexity and Minimax Regret on Patterns Using Kullback-Leibler Divergence Covering show that replacing generic chaining with problem-specific structure yields usable explicit constants (the latter reports $c=38$ for all $n$). We take that stance rather than their specific techniques. Our finite-sample bound will state every constant numerically.
Research Program
Asymptotic theory. We write $\hat F_M(t)-F_\nu(t)$ as the sum of two parts. The first is the subset-sampling error given $G$, which is an empirical-CDF process with multinomial covariance on $\binom{k}{2}+1$ points. The second is the gap between $G$'s true profile and the model profile. That gap is a vector of subgraph-density U-statistics, and its Hoeffding decomposition sets its rate.
For a non-constant graphon, the first-order projection is non-zero, and we obtain
$$T \Rightarrow \sum_t |Z_t|, \qquad Z = Z^{\text{sub}} + \sqrt{\lambda}\,Z^{\text{graph}},$$
where $\lambda=\lim M/n$, $Z^{\text{sub}}$ is the Gaussian limit of the subset-sampling process, and $Z^{\text{graph}}$ is the Gaussian limit of the first-order U-statistic projection. Both covariances will be given in closed form.
For Erdős–Rényi with estimated density, the first-order projection vanishes. The graph term then enters at the $n^{-1}$ scale, as a weighted sum of centered chi-squares, and the relevant ratio becomes $M/n^2$. We will derive plug-in estimators for all covariances and quantify how estimating $\nu$ from $G$ shifts the null. That shift is the fitted-model effect a naive test ignores.
Finite-sample validity. For the subset-sampling term we will bound the Kolmogorov distance between the law of $T$ and its limit by an explicit constant times $(\binom{k}{2}+1)^{a}/\sqrt{M}$. The exponent $a$ comes from a multivariate Gaussian approximation in fixed dimension, combined with the 1-Lipschitz property of $z\mapsto\sum_t|z_t|$ in $\ell_1$.
The deliverable is a table-free, closed-form sample-size rule: the smallest $M$ for which the nominal level is guaranteed within a stated slack. We will compare this rule, at matched precision, to the sample size implied by the Hoeffding-type $L_1$ argument of the graphlet-kernel paper. We will also compare it to the DKW route, which bounds $W_1$ by $\binom{k}{2}$ times the sup-norm CDF error. That route is the obvious generic bound and loses roughly a factor of the support width.
Software. We will release a sampler with exact CDF bookkeeping, the covariance plug-ins, and quantile computation for $\sum_t|Z_t|$ by Monte Carlo on the Gaussian vector. The last step is cheap because the dimension is at most 11 for $k=5$.
Baselines
Naive reference: an edge-density z-test. This compares only the mean of the profile, which is the graph's edge density, to the model's. It is the do-nothing reference because many graph goodness-of-fit checks stop at density. Any profile-based test must at least match its power on density shifts. It must also clearly beat it on alternatives that preserve density, such as planted communities at fixed average degree or graphs with an inserted homogeneous set.
Chi-square test on the same edge-count histogram. This is the strongest simple competitor because it uses exactly our sampled data. It will receive the same $M$, the same $k$, and the same plug-in covariance treatment of graph-level noise, so that only the statistic differs. We count it as beaten if $W_1$ has higher power on alternatives that move mass between neighboring edge counts at matched level. We expect it to win on alternatives that flip mass between distant counts. We will report both outcomes rather than claim uniform dominance.
Sampled graphlet-frequency test with Hoeffding thresholds. This is the strongest existing method with a finite-sample guarantee. It uses the $L_1$ deviation on the full graphlet spectrum from Efficient graphlet kernels for large graph comparison, which reports that about 10,000 sampled graphlets gave stable representations. That paper reports no test power or type-I error, so there is no reported result found on Lacuna for its power as a hypothesis test.
We will run it, and its MMD version with the graphlet kernel, with identical sample budgets and a permutation-calibrated threshold in the two-sample setting. We beat it if our guaranteed-valid test reaches the same power with fewer samples, or more power at equal samples. The sample-size ratio implied by the two finite-sample rules is reported separately.
Parametric bootstrap from the fitted model. This baseline refits MomentNet graphons on resampled graphs, as in A Few Moments Please: Scalable Graphon Learning via Moment Matching. It is given 200 refits, with wall-clock time reported. It is the most serious threat to the calibration contribution, discussed below.
Ablations. Two ablations isolate our ingredients. The first replaces the degenerate limit with the Gaussian linearization appropriate for $P\neq Q$ in the del Barrio line. The second drops the graph-level term $Z^{\text{graph}}$ and treats the $M$ subsets as the only noise. If neither ablation distorts type-I error, our main theoretical ingredient is unnecessary.
Why not just…?
Why not just run a chi-square test on the histogram? It is a legitimate competitor and part of the experiments. Its weakness is that it ignores the ordering of edge counts. A structural change that nudges mass by one or two edges spreads across many cells, each with little signal. Its null also suffers the same two-source noise problem, so it does not avoid our theory. If chi-square matches $W_1$ in power across the alternative families, the contribution shrinks to the calibration theory, and we will say so.
Why not just bootstrap? Bootstrap calibration of transport distances is delicate exactly at the degenerate null that the del Barrio line identifies. Resampling subsets alone, given $G$, also misses the graph-level variance. A parametric bootstrap from a fitted graphon avoids both problems in principle and is a real threat. The comparison will settle whether it is calibrated as well as our limit, and at what cost: each replicate requires refitting a neural graphon. Our limit instead gives a finite-sample guarantee the bootstrap cannot.
Why not just use a graph kernel two-sample test? Kernel tests on graphlet or Weisfeiler–Lehman features need pairwise Gram matrices. TUDataset: A collection of benchmark datasets for learning with graphs notes that such kernels struggle to scale to larger collections. More importantly, they compare collections of graphs. Our main use case is goodness of fit of a single large graph against a model, where there is no second sample to permute. In the two-sample setting we run them directly as a baseline.
Why not just compare Gromov–Wasserstein distances between graphs? Alignment is non-convex. Subgraph Matching via Partial Optimal Transport needs sliding windows and pruning to fit in memory on large graphs, and it yields no null distribution. It answers a matching question, not a testing one.
Proposed Experiments
Synthetic calibration. We will use the 13 synthetic graphon types from the MomentNet benchmark. On that suite, MomentNet is reported to outperform SIGL in 9 of 13 types; that is an estimation result and no testing numbers are reported. We sample graphs with $n$ from $10^3$ to $10^5$, $k\in\{3,4,5\}$, and $M$ from $10^3$ to $10^5$. We measure empirical type-I error at $\alpha=0.05$ over 1,000 replicates in both the Erdős–Rényi and non-constant regimes.
The decisive check is the regime switch. The Gaussian-linearization ablation should over- or under-reject in the Erdős–Rényi case as $M/n^2$ varies, while our limit stays near 0.05. If the switch is not visible, the second claim is wrong.
Power. We test against density-preserving alternatives: a planted clique or independent set of size $n^{c}$, a two-block community structure at fixed average degree, and degree-heterogeneous perturbations. The planted homogeneous sets mirror the Erdős–Hajnal picture of structure forced by forbidden patterns. For each alternative we report power against effect size for all baselines at matched $M$.
Constants. We report the ratio of our guaranteed sample size to the empirically needed sample size, and the same ratio for the Hoeffding and DKW rules. Success means our ratio is within a small single-digit factor while the generic rules are an order of magnitude or more above it.
Real graphs. For two-sample tests we use class splits of D&D, REDDIT-B, IMDB-B, and AIDS from TUDataset. There, detection of known class differences at small $M$ is the target. For single-graph goodness of fit we fit MomentNet graphons to Deezer and LastFM and test the fit, reporting whether rejection is driven by the profile's tails, which indicate homogeneous structure, or by its center.
The project fails in a useful, publishable way if any of three things happens: the chi-square test dominates on power, the parametric bootstrap matches calibration at acceptable cost, or the variance lower bound is too small on real graphs for any profile test to have power.
References
- Central limit theorems for empirical transportation cost in general dimension
- Central limit theorems for general transportation costs
- Central limit theorems for semi-discrete Wasserstein distances
- Statistical bounds for entropic optimal transport: sample complexity and the central limit theorem
- Limit theorems for entropic optimal transport maps and Sinkhorn divergence
- Distributional Convergence of the Sliced Wasserstein Process
- A Few Moments Please: Scalable Graphon Learning via Moment Matching
- Efficient graphlet kernels for large graph comparison
- Subgraph Matching via Partial Optimal Transport
- A Fused Gromov-Wasserstein Approach to Subgraph Contrastive Learning
- Induced subgraphs with distinct sizes
- Induced subgraphs of prescribed size
- Learning with Square Loss: Localization through Offset Rademacher Complexity
- Minimax Regret on Patterns Using Kullback-Leibler Divergence Covering
- TUDataset: A collection of benchmark datasets for learning with graphs