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.

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

References in corpus (6)

• A two-sample test for high-dimensional data with applications to gene-set testing
• Higher Criticism for Large-Scale Inference, Especially for Rare and Weak Effects
• Testing Network Structure Using Relations Between Small Subgraph Probabilities
• Two-Sample Tests for Large Random Graphs Using Network Statistics
• Practical methods for graph two-sample testing
• 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