About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
AISTATS 2023
Conference paper
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.