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

Oct 5, 2026stat.ML

Two-Sample Testing via Path-based Inference

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.

Eshant English, Wei-Cheng Lai, Yanfeng Yang +3

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

Two-Sample Testing

Ask PDF

Nov 21, 2025cs.IT

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

We study the problem of learning an unknown graph via group queries on node subsets, where each query reports whether at least one edge is present among the queried nodes. In general, learning arbitrary graphs with

n

nodes and

k

edges is hard in the non-adaptive setting, requiring

Ω\big(\min\{k^2\log n,\,n^2\}\big)

tests even when a small error probability is allowed. We focus on learning Erdős--Rényi (ER) graphs

G\sim\mathrm{ER}(n,q)

in the non-adaptive setting, where the expected number of edges is

\bar{k}=q\binom{n}{2}

, and we aim to design an efficient testing--decoding scheme, namely, a non-adaptive test design together with a decoding algorithm, achieving asymptotically vanishing error probability. Prior work (Li--Fresacher--Scarlett, NeurIPS 2019) presents a testing--decoding scheme that attains an order-optimal number of tests

O(\bar{k}\log n)

but incurs

Ω(n^2)

decoding time, whereas their proposed sublinear-time algorithm incurs an extra

(\log \bar{k})(\log n)

factor in the number of tests. We extend the binary splitting approach, recently developed for non-adaptive group testing, to the ER graph learning setting, and prove that the edge set can be recovered with high probability using

O(\bar{k}\log n)

tests while attaining decoding time

O(\bar{k}^{1+δ}\log n)

for any fixed

δ>0

Hoang Ta, Jonathan Scarlett

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

O(\Bar{K}\Log N)$Inhomogeneous Random Graphs

Ask PDF

Jul 23, 2026cs.LG

Zero-Flow Two-Sample Tests

Motivated by the success of modern flow-based generative models in modeling complex data, we study two-sample testing through the lens of flow-based methods. We propose the Zero-Flow Two-Sample Test (ZF2ST), built on the zero-flow criterion, which characterizes distributional equality through a time-reversal antisymmetry of a learnable velocity field. We extend this criterion and further develop the Zero-Flow Discrepancy, an identifying discrepancy that controls the Wasserstein distance, and derive a variational representation in terms of a witness function. This representation naturally leads to a witness-based test whose power is governed by the signal-to-noise ratio (SNR), allowing direct power maximization for witness learning. ZF2ST learns the witness on one data split and performs testing on held-out samples, thereby maintaining Type-I error control and admitting a simple asymptotic null distribution. Experimentally, ZF2ST performs competitively across various synthetic and real-world benchmarks, while showing particularly strong performance in distinguishing image distributions from different sources.

Yakun Wang, Leyang Wang, Song Liu +1

University of Bristol · RIKEN AIP · University of Tokyo & RIKEN AIP

Two-Sample Testing

Ask PDF