Two-Sample Tests for Large Random Graphs Using Network Statistics

Abstract

We consider a two-sample hypothesis testing problem, where the distributions are defined on the space of undirected graphs, and one has access to only one observation from each model. A motivating example for this problem is comparing the friendship networks on Facebook and LinkedIn. The practical approach to such problems is to compare the networks based on certain network statistics. In this paper, we present a general principle for two-sample hypothesis testing in such scenarios without making any assumption about the network generation process. The main contribution of the paper is a general formulation of the problem based on concentration of network statistics, and consequently, a consistent two-sample test that arises as the natural solution for this problem. We also show that the proposed test is minimax optimal for certain network statistics.

To be presented in COLT 2017 (author sequence, funding details and minor typos updated in version 2)

References in corpus (3)

• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Resolving structural variability in network models and the brain
• Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization

Cited by in corpus (13)

• Two-sample Hypothesis Testing for Inhomogeneous Random Graphs
• Statistical inference for network samples using subgraph counts
• Practical methods for graph two-sample testing
• Optimal Single Sample Tests for Structured versus Unstructured Network Data
• Two-sample Test of Community Memberships of Weighted Stochastic Block Models
• Nonparametric two-sample hypothesis testing for low-rank random graphs of differing sizes
• On Two Distinct Sources of Nonidentifiability in Latent Position Random Graph Models
• On the Theoretical Properties of the Network Jackknife
• Testing Changes in Communities for the Stochastic Block Model
• Meta Two-Sample Testing: Learning Kernels for Testing with Limited Data
• Graphon based Clustering and Testing of Networks: Algorithms and Theory
• Combinatorial-Probabilistic Trade-Off: Community Properties Test in the Stochastic Block Models
• Valid Two-Sample Graph Testing via Optimal Transport Procrustes and Multiscale Graph Correlation with Applications in Connectomics