Two-sample Hypothesis Testing for Inhomogeneous Random Graphs

Abstract

The study of networks leads to a wide range of high dimensional inference problems. In many practical applications, one needs to draw inference from one or few large sparse networks. The present paper studies hypothesis testing of graphs in this high-dimensional regime, where the goal is to test between two populations of inhomogeneous random graphs defined on the same set of $n$ vertices. The size of each population $m$ is much smaller than $n$, and can even be a constant as small as 1. The critical question in this context is whether the problem is solvable for small $m$. We answer this question from a minimax testing perspective. Let $P,Q$ be the population adjacencies of two sparse inhomogeneous random graph models, and $d$ be a suitably defined distance function. Given a population of $m$ graphs from each model, we derive minimax separation rates for the problem of testing $P=Q$ against $d(P,Q)>\rho$. We observe that if $m$ is small, then the minimax separation is too large for some popular choices of $d$, including total variation distance between corresponding distributions. This implies that some models that are widely separated in $d$ cannot be distinguished for small $m$, and hence, the testing problem is generally not solvable in these cases. We also show that if $m>1$, then the minimax separation is relatively small if $d$ is the Frobenius norm or operator norm distance between $P$ and $Q$. For $m=1$, only the latter distance provides small minimax separation. Thus, for these distances, the problem is solvable for small $m$. We also present near-optimal two-sample tests in both cases, where tests are adaptive with respect to sparsity level of the graphs.

arXiv commentTo appear in the Annals of Statistics. This 54-page version includes the supplementary material (appendix to the main paper)

References in corpus (18)

• Statistical mechanics of complex networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Higher criticism for detecting sparse heterogeneous mixtures
• User-friendly tail bounds for sums of random matrices
• A two-sample test for high-dimensional data with applications to gene-set testing
• The phase transition in inhomogeneous random graphs
• Optimal detection of sparse principal components in high dimension
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges
• Higher Criticism for Large-Scale Inference, Especially for Rare and Weak Effects
• A goodness-of-fit test for stochastic block models
• Testing Network Structure Using Relations Between Small Subgraph Probabilities
• Hypothesis testing for high-dimensional sparse binary regression
• Two-Sample Tests for Large Random Graphs Using Network Statistics
• Practical methods for graph two-sample testing
• Adaptivity and Computation-Statistics Tradeoffs for Kernel and Distance based High Dimensional Two Sample Testing
• Detecting positive correlations in a multivariate sample
• Optimal Single Sample Tests for Structured versus Unstructured Network Data

Cited by in corpus (4)

• Network Recovery from Unlabeled Noisy Samples
• Correcting a Nonparametric Two-sample Graph Hypothesis Test for Graphs with Different Numbers of Vertices with Applications to Connectomics
• Localized geometry detection in scale-free random graphs
• Valid Two-Sample Graph Testing via Optimal Transport Procrustes and Multiscale Graph Correlation with Applications in Connectomics