Two-Sample Testing for Inhomogeneous Random Graphs in Non-Integral $L_r$ Norms

Soham Dan

stat.MLSep 27, 2026

Two-Sample Testing for Inhomogeneous Random Graphs in Non-Integral $L_r$ Norms

Authors: Soham Dan

Abstract

Testing whether two populations of networks share the same edge probabilities is a basic problem in network inference. How hard it is depends on the norm used to measure the difference. For the inhomogeneous Erdős--Rényi (IER) model, the optimal sample complexity is known for every integer $L_r$ norm and for $1\le r<2$ . For non-integral $r>2$ , however, the known upper and lower bounds do not match, and the lower bound was conjectured to be tight. We study this gap for two-sample testing on aligned vertices. We propose a test that runs two published statistics, of orders $2$ and $\lceil r\rceil$ , on the same data and rejects if either one rejects. Its thresholds come from Hölder interpolation, so that both statistics have the same sample cost. We prove that this test attains the conjectured rate. Combined with earlier results, this shows that for every fixed $r\ge1$ the minimax sample complexity is of order $n^{\max\{4/r-1,\,2/r\}}/ε^2$ , even when the separation changes with $n$ . In simulations with $n$ between 32 and 256, the number of graphs needed for 80% power at level $0.05$ grows with $n$ at a rate consistent with the theory. For $r=2.5$ , for example, the fitted exponent is $0.78$ , against the theoretical value $0.8$ . Interestingly, the two statistics split the work as the interpolation argument suggests: the higher-order statistic is more powerful when only a few edges change, and the $L_2$ statistic when many edges change.

Figures & tables

Norm	Known before	This note
$1\leq r<2$	$\Theta(n^{4/r-1})$	unchanged
Integer $r\geq 2$	$\Theta(n^{2/r})$	unchanged
Non-integral $r>2$	$\Omega(n^{2/r})$ and $O(n^{4/r-2/\lceil r\rceil})$	$\Theta(n^{2/r})$

Table 1: Sample complexity of two-sample testing in the aligned IER model, up to constants that depend on

r

and the target error. Every entry is divided by

\epsilon^{2}

. The last row is the gap closed in this note. Here

\Theta(\cdot)

means “of the same order as”, while

\Omega(\cdot)

and

O(\cdot)

give lower and upper bounds of that order.

Symbol	Meaning
$n$ , $m$	number of vertices; number of graphs in each group
$M$ , $N$	number of unordered edges $n(n-1)/2$ ; number of off-diagonal entries $2M$
$h_{e}=p_{e}-q_{e}$	difference of the edge probabilities of edge $e$
$\epsilon$	separation in the $L_{r}$ norm ( 1 )
$d=\lceil r\rceil$	the next integer above a non-integral $r$
$\lambda(r)$ , $A_{r}$	rate exponent $\max\{4/r-1,2/r\}$ ; rate $n^{\lambda(r)}/\epsilon^{2}$

Table 2: Main notation.

$r$	Construction	$\lambda(r)$	Power at level $0.05$	Theorem test, $1-$ error sum
1.5	dense	1.667	1.672 [1.641, 1.724]	1.663 [1.621, 1.703]
2	dense	1.000	1.003 [0.969, 1.041]	1.017 [0.963, 1.076]
2	sparse	1.000	0.981 [0.948, 1.011]	0.974 [0.911, 1.026]
2.5	sparse	0.800	0.776 [0.752, 0.804]	0.792 [0.763, 0.823]
3.5	sparse	0.571	0.552 [0.528, 0.574]	0.572 [0.539, 0.604]

Table 3: Fitted slope of

\log m^{*}

against

\log n

over

n=32,\ldots,256

, where

m^{*}

is the number of graphs per group at which the tracked quantity first reaches

0.8

(

\epsilon=0.75

). Brackets give 95% percentile intervals from 400 bootstrap samples that resample evaluation and calibration replicates within every cell. The last column tracks one minus the sum of the null rejection rate and the miss rate of the theorem test. This analysis was added after the prespecified one in Appendix C.2 .

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

$r$	$m$	Model	Rejection-rate range
2.5	300	null	[0.025, 0.060]
2.5	300	sparse	[0.390, 0.516]
2.5	1201	null	[0.031, 0.076]
2.5	1201	sparse	[1.000, 1.000]
3.5	85	null	[0.036, 0.074]
3.5	85	sparse	[0.280, 0.452]

Appendix

Table 4: Sensitivity of the oracle union to the calibration sample at

n=256

and

\epsilon=0.75

. Each range is the 2.5th–97.5th percentile over 400 bootstrap resamples of independent calibration and evaluation replicates, keeping the two statistics paired. The ranges describe variability and are not exact confidence intervals.

$r$	Construction	Finite crossings	Slope	Bootstrap interval
1.5	dense	4/4	1.679	[1.590, 1.774]
2	dense	4/4	0.945	[0.846, 1.036]
2	sparse	4/4	1.014	[0.930, 1.104]
2.5	sparse	4/4	1.066	withheld
3.5	sparse	3/4	censored	withheld

Appendix

Table 5: Prespecified analysis: slope of

\log m^{*}

against

\log n

over

n=32,64,128,256

, where

m^{*}

is the number of graphs at which the power of the theorem test reaches

0.8

(

\epsilon=0.75

). A slope or interval is withheld when a crossing is censored.

$r$	$m$	Method	Rejections	Interval
2.5	172	Union	431/1000	[0.401, 0.462]
2.5	172	Union, $L_{2}$ statistic	230/1000	[0.205, 0.257]
2.5	172	Union, $L_{3}$ statistic	293/1000	[0.266, 0.322]
2.5	172	Direct $L_{2}$	382/1000	[0.352, 0.413]
2.5	172	Direct ceiling	424/1000	[0.394, 0.455]
3.5	57	Union	507/1000	[0.476, 0.538]

Appendix

Table 6: Null rejection rates at the sample sizes of the support study (

n=128

P=Q=1/2

\epsilon=0.75

). All methods in a row block use the same observations. Intervals are pointwise 95% Wilson intervals.

$r$	Method	Cells	Observed range	Undefined/total
1.5	$L_{2}$	32	0.034–0.062	0/20000
1.5	union	32	0.034–0.062	0/20000
2	$L_{2}$	41	0.034–0.066	0/24500
2	union	41	0.034–0.066	0/24500
2.5	$L_{2}$	41	0.032–0.080	0/24500
2.5	$L_{3}$	41	0.034–0.068	1/24500

Appendix

Table 7: Null rejection rates of the practical normal calibration at nominal level

0.05

, over all null cells of the main and structured studies. Rates are computed among the defined decisions, and the last column counts undefined decisions among all replicate evaluations.

Explore similar work

Two-Sample Testing via Path-based Inference
Oct 5, 2026Eshant English, Wei-Cheng Lai, Yanfeng Yang +3Two-Sample Testing
The University of Tokyo, Tokyo, Japan · Hasso Plattner Institute for Digital Engineering, Germany · Institute of Statistical Mathematics, Japan +3
A Fast Binary Splitting Approach for Non-Adaptive Learning of Erdős--Rényi Graphs
Nov 21, 2025Hoang Ta, Jonathan ScarlettO(\Bar{K}\Log N)$Inhomogeneous Random Graphs
Department of Computer Science, School of Computing, National University of Singapore (NUS), Singapore 117417 · Department of Computer Science, Hanoi University of Science and Technology, Vietnam · Department of Computer Science, Department of Mathematics, and Institute of Data Science, NUS, Singapore 117417
Zero-Flow Two-Sample Tests
Jul 23, 2026Yakun Wang, Leyang Wang, Song Liu +1Two-Sample Testing
University of Bristol · RIKEN AIP · University of Tokyo & RIKEN AIP

Oct 5, 2026, stat.MLJ/K move · Enter open · S save

Two-Sample Testing via Path-based Inference

Eshant English, Wei-Cheng Lai, Yanfeng Yang, Kenji Fukumizu+2

The University of Tokyo, Tokyo, Japan · Hasso Plattner Institute for Digital Engineering, Germany · Institute of Statistical Mathematics, Japan+3

Two-Sample Testing

Open paper AskPDF arXiv

Modern deep generative models are primarily studied for their ability to generate realistic samples, yet the generative dynamics they learn can also serve as objects of statistical inference. We develop this idea for two-sample testing, the problem of deciding whether the same distribution generated two finite datasets. Using stochastic interpolants, we connect both distributions to a shared Gaussian bottleneck, so that each half of the resulting path is a Gaussian channel acting on a single population. We prove that the null hypothesis holds if and only if the population denoiser, or equivalently, the velocity fields of the two halves, coincide at any single noise level, which amounts to a reflection symmetry of the path about the bottleneck. Deviations from this symmetry yield a continuum of two-sample witnesses, which we estimate via held-out regression risks on learned denoisers and velocities and aggregate along the path; under an information-theoretic weighting, the aggregated discrepancy equals the Jeffreys divergence between the noise-smoothed distributions. Calibrating the resulting statistics by permutation yields tests that are valid in finite samples for any trained networks and consistent when the fields are learned accurately. On a synthetic benchmark and three image benchmarks, the proposed tests improve power over the strongest baseline by up to 33 percentage points at an equal total sample budget, with the best choice of regression representation and path weighting depending on the data modality. These results show that generative paths provide a principled representation for statistical testing, extending stochastic-interpolant models beyond generation.

Abstract

Explore similar work

Two-Sample Testing via Path-based Inference

A Fast Binary Splitting Approach for Non-Adaptive Learning of Erdős--Rényi Graphs

Zero-Flow Two-Sample Tests