Two-Sample Testing of Unaligned Graphs with Latent Geometry

Two-sample tests for populations of graphs often have to work without a correspondence between the vertices of different graphs. For an Erdős–Rényi null and a planted-partition difference with signal-to-noise ratio $t$, this raises the number of graphs needed from order $t^{-1}$ to order $t^{-3}$. Real graph populations are rarely Erdős–Rényi. When the null has latent geometry, each graph carries information about the positions of its own vertices, and a test can align every graph to itself before comparing the two samples. We study when this works, for analytic graphon nulls on the torus and differences that oscillate in the latent position. For the ring null on the circle and a difference at frequency $\omega$, we show that for fixed $t$ the number of graphs per group needed is $\min\{t^{-3},e^{8\pi^2\omega^2/(nI)}/(nt)\}$ up to factors $e^{\zeta\omega^2/n}$ for every $\zeta>0$, where $I$ is the Fisher information of one edge about the angle between its endpoints. One graph per group therefore suffices below the critical frequency $\omega^\ast=(In\log n/(8\pi^2))^{1/2}$, and order $t^{-3}$ graphs are needed above it. On the $d$-dimensional torus, for separable cosine nulls, the resolvable frequencies form an ellipsoid given by the Fisher information matrix of the null, and a difference along a latent direction that the null does not encode costs order $t^{-3}$ graphs at every frequency. Statistics of bounded degree, including all fixed motif counts, need order $t^{-3}$ graphs at every frequency above their degree. In simulations the power of the self-aligned test follows its predicted curves without fitted constants, and on nulls built from Hi-C contact maps of the E. coli chromosome it follows them up to a finite-sample loss of efficiency in the angle estimates.