Metraipolis › archive › dc_a26c536b58bf

Two-Sample Testing for Random Graphs without Vertex Correspondence — arXiv:2610.07503

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.07503
License (as archived)
CC0-1.0
Archived
2026-10-07T11:42:25.464Z
SHA-256 of the archived text
11fdb03fb31f8de8b8530d55ac1ffda58660fc4748093dabb5c24e147bfcf160
Stable URL of this page
https://metraipolis.com/documento/dc_a26c536b58bf

How to cite

Two-Sample Testing for Random Graphs without Vertex Correspondence — arXiv:2610.07503 — arXiv (en), https://arxiv.org/abs/2610.07503 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a26c536b58bf (Metraipolis archive dc_a26c536b58bf, sha256 11fdb03fb31f8de8b8530d55ac1ffda58660fc4748093dabb5c24e147bfcf160)
BibTeX
@misc{dca26c536b58bf,
  title = {Two-Sample Testing for Random Graphs without Vertex Correspondence — arXiv:2610.07503},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.07503},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a26c536b58bf; sha256 11fdb03fb31f8de8b8530d55ac1ffda58660fc4748093dabb5c24e147bfcf160},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.07503. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (stat.ML) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2610.07503 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T11:19:24.895Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).