Two-Sample Tests for Inhomogeneous Random Graphs in Lr norm: Optimality and Asymptotics
Abstract
In this paper we study the two-sample problem for inhomogeneous Erdős-Rényi (IER) random graph models in the Lr 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 ∈ [0, 1]n×n (with zeros on the diagonals), the two-sample problem for IER graphs (with respect to the Lr norm || · ||r) is to test the hypothesis H0 : P = Q versus H1 : ||P - Q||r ≥ ε, given a sample of m graphs from the respective distributions. In this paper, we obtain the optimal sample complexity for testing in the Lr norm, for all integers r ≥ 1. We also derive the asymptotic distribution of the optimal tests under H0 and develop a method for consistently estimating their variances. This allows us to efficiently implement the optimal tests with precise asymptotic level and establish their asymptotic consistency. We validate our theoretical results by numerical experiments for various natural IER models.