Two-Sample Testing for Random Graphs without Vertex Correspondence

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 masymp t⁻³ 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 masymp t⁻¹ graphs suffice, so misalignment costs a factor of order t⁻². When the triangle signal cancels, the rate becomes t⁻⁴ 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.

Two-Sample Testing for Inhomogeneous Random Graphs in Non-Integral L_r Norms
Soham Dan
arXiv27 Sep 2026PreprintCC BY 4.0Full textStatisticsarXiv
Joint Independence Testing for Latent Position Random Graphs
Xiaoyi Wen, Zoltan Szabo
arXiv25 Oct 2026PreprintarXiv licenceFull textStatisticsarXiv
Walk/Zeta correspondence for quantum walks on path graphs: a pre-geometric structure implied by a generalized reflection principle
Jiro Akahori, Riki Kitano, Norio Konno +1
arXiv4 Oct 2026PreprintarXiv licenceFull textMathematical physics ProbabilityarXiv
Data-Matrix-Based Overall Goodness-of-Fit Testing for Confirmatory Factor Analysis: In-Sample Prediction Error for Observed Variables
Young Ze Kim, Gyeongcheol Cho, Hanjoe Kim
PsyArXiv6 Oct 2026PreprintAll rights reservedFull textStatisticsOSF
OLS Testing with Predictors Scaled to Have Unit Sample Variance, and Similar Results for a Robust Regression Estimator
David J. Olive, Sanjuka Johana Lemonge
Axioms1 Oct 2026Peer-reviewedCC BY 4.0StatisticsCrossref

Cite

BibTeX RIS

BibTeX

@misc{dan2026twosample,
  title = {{Two-Sample Testing for Random Graphs without Vertex Correspondence}},
  author = {Soham Dan},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.07503},
  eprint = {2610.07503},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.07503},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Two-Sample Testing for Random Graphs without Vertex Correspondence
AU  - Soham Dan
PY  - 2026
DA  - 2026/10/05
PB  - arXiv
DO  - 10.48550/arxiv.2610.07503
UR  - https://arxiv.org/abs/2610.07503
AB  - 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 masymp 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 masymp 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.
ER  -

Abstract

Related

Cite