Two-Sample Testing for Random Graphs without Vertex Correspondence

Soham Dan

stat.MLOct 5, 2026

Two-Sample Testing for Random Graphs without Vertex Correspondence

Authors: Soham Dan

Abstract

Two populations of graphs often have to be compared without any correspondence between their vertices, for instance when networks come from different communities, or when a graph generative model is evaluated against held-out graphs. We study how many graphs such an unaligned two-sample test needs, and which graph statistics can detect which differences. For an Erdős--Rényi null and a planted two-block difference that leaves every expected degree unchanged, we show that $m\asymp t^{-3}$ graphs per group are necessary and sufficient when the per-graph signal-to-noise ratio is $t<1$ . Signed triangle counts attain this rate, and the lower bound holds for every graph size. With aligned vertices $m\asymp t^{-1}$ graphs suffice, so misalignment costs a factor of order $t^{-2}$ . When the triangle signal cancels, the rate becomes $t^{-4}$ and $4$ -cycles are needed. Statistics built from trees have exactly the same expectation under both hypotheses, and tests based on finitely many of them have asymptotically no power. In the graphon limit, this class includes degree distributions and message-passing graph neural network features. For a non-constant null, a generic difference is visible at first order, and a simple motif test attains the aligned order of sample size, suggesting that misalignment is costly mainly for differences that are invisible at low orders. We also give an exactly valid test for one or two graphs per group, at a cost in power. In our simulations, the fitted exponents are close to the predicted ones, and degree-based and random-GNN evaluation metrics stay at their level in a setting where signed triangles need about $65$ graphs.

Figures & tables

Figure 1: Left: number of graphs per group at which each test reaches power

1/2

at level

0.05

, for the planted partition ( 1 ) with

n=300

and

p=1/2

. Unaligned tests (signed triangles with known

p

, excess triangle density with unknown

p

) follow the slope

-3

of Theorem 1 . Aligned tests (cross-graph statistic

Q

, top eigenvalue of the averaged adjacency matrix) follow the slope

-1

. Below the black curve, the information bound of Theorem 1 (i) rules out power

1/2

for every test. Right: the ratio of unaligned to aligned sample sizes, with a reference line proportional to

t^{-2}

Figure 2: The same degree-preserving difference

cH_{0}

added to three nulls (

n=128

): Erdős–Rényi, a regular two-block model (SBM2) and an irregular smooth graphon (SMOOTH). The plots show

m^{\ast}

against the scale

c

for the unaligned excess-triangle test and for two aligned tests, with thin curves for the prediction

2z^{2}\sigma_{0}^{2}/\Delta(c)^{2}

from the exact shift. Under the constant null the sample size of the unaligned test grows like

c^{-6}

, while under the non-constant nulls it tracks the aligned tests, whose sample size grows like

c^{-2}

. Open markers extend the grid to small

c

, and arrows mark censored values.

Figure 3: Power of two-sample tests on descriptors used to evaluate graph generative models. Descriptors are compared by a Gaussian-kernel MMD calibrated by permutation, and signed triangles by a permutation test on the mean difference (

n=200

p=0.1

200

replicates per point, horizontal line at level

0.05

). Left and middle: planted partition ( 1 ) against

\mathbb{G}(n,p)

. Right: planted-partition graphs against the same graphs after degree-preserving double-edge swaps. Tree-based descriptors (dashed) stay at the level, and the dotted curve is the normal-theory power of signed triangles.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: Sign cancellation (E11b),

n=300

p=1/2

. Left:

m^{\ast}

against

t

for signed triangles and signed

4

-cycles under the rank-one planted partition, and for

4

-cycles under the rank-two model ( 4 ), where triangles never reach power

0.5

. Right: power against

m

t=0.6

Figure 5: E11 in the sparse regime (

n=2000

, average degree

15

). The layout is as in Figure 1 .

Figure 6: E12 repeated with

n=256

. The layout is as in Figure 2 .

	Size (worst null)			Power, SBM2 null			Power, ER null
Method	$m=1$	$2$	$3$	$1$	$2$	$3$	$1$	$2$	$3$
Graph-label permutation (exact)	0.000	0.000	0.000	0.00	0.00	0.00	0.00	0.00	0.00
Welch $z$	–	0.206	0.127	–	(0.85)	(0.96)	–	(0.40)	(0.40)
Welch $t$	–	0.024	0.040	–	0.22	0.69	–	0.06	0.15
Vertex jackknife	0.010	0.009	0.014	0.21	0.58	0.89	0.00	0.02	0.04
Vertex split, $B=4$ (exact)	0.031	0.055	0.062	0.06	0.18	0.25	0.02	0.07	0.06

Appendix

Table 1: Calibration of the two-sample excess-triangle test with

m\leq 3

graphs per group (

n=128

, two-sided level

0.05

). Size is the largest rejection rate under the three nulls ER

(1/2)

, SBM2 and SMOOTH (1000 replicates, Monte Carlo s.e.

0.007

0.05

). Power is under

W+H_{0}

(500 replicates). Parentheses mark tests whose size in that cell exceeds

0.064

. Figure 7 shows all

n\in\{64,128\}

and

m\leq 10

Figure 7: Size (left two columns, on a square-root axis with a grey band at

0.05\pm 2

Monte Carlo s.e.) and power under

W+H_{0}

(right two columns) of the calibration methods, for the three nulls (rows),

n\in\{64,128\}

and

m\in\{1,2,3,5,10\}

. Open markers in the power panels flag methods whose size in that cell exceeds

0.064

	ER		SMOOTH		rank-one		Size
Descriptor	$H_{A}$	$H_{O}$	$H_{A}$	$H_{O}$	$H_{A}$	$H_{O}$	max
Degree histogram (MMD)	$>256$	$>256$	$>256$	$>256$	$>256$	$>256$	0.070
Random GIN (MMD)	$>256$	$>256$	44.3	$>256$	25.7	$>256$	0.085
Clustering histogram (MMD)	28.0	38.7	$\leq 8$	191	$\leq 8$	$>256$	0.080
Graphlet counts (MMD)	$>256$	$>256$	176	$>256$	124	$>256$	0.085
Laplacian spectrum (MMD)	14.5	13.5	11.7	16.7	8.9	25.8	0.090

Appendix

Table 2: E15: graphs per group needed for power

0.5

(

m^{\ast}

, interpolated on

m\in\{8,\dots,256\}

, with

{\leq}8

when reached at

m=8

and

{>}256

when not reached), and the largest rejection rate under the three nulls (

m\in\{8,64\}

200

replicates each).

Descriptor	deg	wl1	wl2	deg	wl1	wl2	max
	D&D			ENZYMES			Size
Degree histogram (MMD)	$>64$	$>64$	$>64$	$>64$	$>64$	$>64$	0.058
Random GIN, sum (MMD)	$>64$	$>64$	$>64$	$>64$	$>64$	$>64$	0.062
Random GIN, mean (MMD)	$>64$	$>64$	$>64$	$>64$	$>64$	$>64$	0.063
Clustering histogram (MMD)	$\leq 4$	$\leq 4$	$>64$	20.4	22.4	$>64$	0.058
Graphlet counts (MMD)	17.2	17.6	$>64$	15.1	20.0	$>64$	0.060

Appendix

Table 3: E16: graphs per group needed for power

0.5

(

m^{\ast}

, interpolated on

m\in\{4,\dots,64\}

, with

{\leq}4

when reached at

m=4

and

{>}64

when not reached) for the three kinds of rewiring, the largest rejection rate without rewiring (

m\in\{8,64\}

1200

replicates each), and the share of triangles removed.

Figure 8: Top (E15): rejection rates against

m

for the degree-preserving differences

H_{A}

, aligned with the degree profile of the null, and

H_{O}

, orthogonal to its eigenfunctions, under SMOOTH and the rank-one null (

n=200

\delta=0.07

). Bottom (E16): D&D and ENZYMES graphs against copies with

5\%

of their edges rewired by unrestricted swaps (deg) or by swaps between vertices of equal degree (wl1). Dashed curves are tree statistics, and the grey band is

0.05\pm 2

Monte Carlo s.e.

Explore similar work

Two-Sample Testing for Inhomogeneous Random Graphs in Non-Integral $L_r$ Norms
Sep 27, 2026Soham DanInhomogeneous Random Graphs Two-Sample Testing
Auditing Bayesian Graph Alignment: Diagnostic Comparisons and Reference Failure
Sep 19, 2026Melika Gorgi, Kourosh MirsohiConditional Independence Diagnosis
Center for Complex Biological Systems University of California, Irvine Irvine, CA 92697, USA · Department of Computer Science University of California, Irvine Irvine, CA 92697, USA
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

Sep 27, 2026, stat.MLJ/K move · Enter open · S save

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

Soham Dan

Inhomogeneous Random Graphs Two-Sample Testing Optimal Sample Complexity Integral Probability Neural Network Inference

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Two-Sample Testing for Inhomogeneous Random Graphs in Non-Integral LrL_rLr​ Norms

Auditing Bayesian Graph Alignment: Diagnostic Comparisons and Reference Failure

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

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