Two-Sample Tests for Inhomogeneous Random Graphs in $L_r$ norm: Optimality and Asymptotics

In this paper, we study the two-sample problem for inhomogeneous Erd\H{o}s-R\'enyi (IER), random graph models, in the $L_r$ norm, in the high-dimensional regime where the number of samples is smaller or comparable to the size of the graphs. Given two symmetric matrices $P, Q \in [0, 1]^{n \times n}$ (with zeros on the diagonals), the two-sample problem for IER graphs (with respect to the $L_r$ norm $||\cdot||_r$) is to test the hypothesis $H_0: P=Q$ versus $H_1: ||P-Q||_r \geq \varepsilon$, given a sample of $m$ graphs from the respective distributions. In this paper, we obtain the optimal sample complexity for testing in the $L_r$-norm, for all integers $r \geq 1$. We also derive the asymptotic distribution of the optimal tests under $H_0$ and develop a method for consistently estimating their variances, for all integers $r \geq 1$. This allows us to efficiently implement the optimal tests with precise asymptotic levels and establish their asymptotic consistency. We validate our theoretical results by numerical experiments for various natural IER models.