Two-Sample Testing for Random Graphs without Vertex Correspondence

Excerpt

arXiv:2610.07503v1 Announce Type: cross 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\H{o}s--R\'enyi null and a planted two-block difference that leaves every expected