# Two-Sample Testing for Random Graphs without Vertex Correspondence

arXiv: https://arxiv.org/abs/2610.07503 · HTML: https://mlsanity.com/paper/2610.07503/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 68 references that are in the map.
- First posted on arXiv 5 Oct 2026.

## Builds on (most cited first, 14 of 14)

- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [Lov'asz Meets Weisfeiler and Leman](https://mlsanity.com/paper/1802.08876/) (2018)
- [Two-sample Testing Using Deep Learning](https://mlsanity.com/paper/1910.06239/) (2019)
- [Optimal hypothesis testing for stochastic block models with growing degrees](https://mlsanity.com/paper/1705.05305/) (2017)
- [Low-degree lower bounds via almost orthonormal bases](https://mlsanity.com/paper/2509.09353/) (2025)
- [Graphon based Clustering and Testing of Networks: Algorithms and Theory](https://mlsanity.com/paper/2110.02722/) (2021)
- [Testing Network Structure Using Relations Between Small Subgraph Probabilities](https://mlsanity.com/paper/1704.06742/) (2017)
- [Hypothesis testing for populations of networks](https://mlsanity.com/paper/1911.03783/) (2019)
- [Detecting Arbitrary Planted Subgraphs in Random Graphs](https://mlsanity.com/paper/2503.19069/) (2025)
- [PolyGraph Discrepancy: a classifier-based metric for graph generation](https://mlsanity.com/paper/2510.06122/) (2025)
- [Multivariate Inference of Network Moments by Subsampling](https://mlsanity.com/paper/2409.01599/) (2024)
- [Vertex misalignment and changepoint localization in network time series](https://mlsanity.com/paper/2604.20072/) (2026)
- [Sharp Low-Degree Thresholds for Planted-vs-Planted Testing](https://mlsanity.com/paper/2606.05266/) (2026)

## Abstract (arXiv)

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 ErdHos--R'enyi 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.