Two-Sample Testing for Inhomogeneous Random Graphs in Non-Integral Lr Norms
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 Lr norm and for 1≤ 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 ⌈ r⌉, 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≥1 the minimax sample complexity is of order nmax{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 L2 statistic when many edges change.
Related
- Two-Sample Testing for Random Graphs without Vertex Correspondence
- Spectrum of Directed Inhomogeneous Random Graphs
- Higher-Order Fluctuations of the Log-Partition Function for Ising Models on Inhomogeneous Random Graphs
- Inhomogeneous random graphs: how heavy tails reshape connectivity
- Perron-Wright asymptotics and critical component processes for regular inhomogeneous random graphs
BibTeX
@misc{dan2026twosample,
title = {{Two-Sample Testing for Inhomogeneous Random Graphs in Non-Integral $L_r$ Norms}},
author = {Soham Dan},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.33968},
eprint = {2609.33968},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33968},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Two-Sample Testing for Inhomogeneous Random Graphs in Non-Integral L_r Norms
AU - Soham Dan
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2609.33968
UR - https://arxiv.org/abs/2609.33968
AB - 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≤ 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 ⌈ r⌉, 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≥1 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.
ER -