Two-sample hypothesis testing for inhomogeneous random graphs

DOI10.1214/19-AOS1884MaRDI QIDQ126111zbMATH OpenOpenAlexFDO

Authors Debarghya Ghoshdastidar, Maurilio Gutzeit, Alexandra Carpentier, Ulrike von Luxburg, Maurilio Gutzeit, Alexandra Carpentier, Ulrike Von Luxburg

Publication date 4 July 2017

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.00833, https://projecteuclid.org/euclid.aos/1597370670

zbMATH Keywords

minimax testingtwo-sample testinhomogeneous Erdős-Rényi model

Mathematics Subject Classification ID

Hypothesis testing in multivariate analysis (62H15) Random graphs (graph-theoretic aspects) (05C80) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20) Minimax procedures in statistical decision theory (62C20)

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)>ho$. 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.

Recommendations

• A nonparametric two-sample hypothesis testing problem for random graphs
• Two-sample Testing in High Dimensions
• On some graph-based two-sample tests for high dimension, low sample size data
• Testing for high-dimensional geometry in random graphs
• A global homogeneity test for high-dimensional linear regression

Cites work

• scientific article; zbMATH DE number 5968943 (Why is no real title available?)
• scientific article; zbMATH DE number 889593 (Why is no real title available?)
• A goodness-of-fit test for stochastic block models
• A kernel two-sample test
• A nonparametric two-sample hypothesis testing problem for random graphs
• A two-sample test for high-dimensional data with applications to gene-set testing
• Community detection in dense random networks
• Community detection in sparse random networks
• Concentration and regularization of random graphs
• Detecting positive correlations in a multivariate sample
• Detection and feature selection in sparse mixture models
• Graph kernels
• Higher criticism for detecting sparse heterogeneous mixtures.
• Higher criticism for large-scale inference, especially for rare and weak effects
• Hypotheses testing on infinite random graphs
• Hypothesis testing for automated community detection in networks
• Hypothesis testing for high-dimensional sparse binary regression
• Hypothesis testing for network data in functional neuroimaging
• Large networks and graph limits
• Non-asymptotic minimax rates of testing in signal detection
• Nonparametric goodness-of-fit testing under Gaussian models
• On signal detection and confidence sets for low rank inference problems
• On the spread of viruses on the Internet
• Optimal algorithms for testing closeness of discrete distributions
• Optimal detection of sparse principal components in high dimension
• Oracle inequalities for network models and sparse graphon estimation
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Some hypothesis tests for the covariance matrix when the dimension is large compared to the sample size
• Spectra of edge-independent random graphs
• Statistical mechanics of complex networks
• Testing Ising models
• Testing for high-dimensional geometry in random graphs
• The phase transition in inhomogeneous random graphs
• Two-Sample Test of High Dimensional Means Under Dependence
• User-friendly tail bounds for sums of random matrices
• Weisfeiler-Lehman graph kernels

Cited in

(17)

• Hypotheses testing on infinite random graphs
• Random geometric graph: some recent developments and perspectives
• Combinatorial inference for graphical models
• Two-sample test of stochastic block models
• A nonparametric two-sample hypothesis testing problem for random graphs
• A General Asymptotic Framework for Distribution-Free Graph-Based Two-Sample Tests
• A Spectral-Based Framework for Hypothesis Testing in Populations of Networks
• Hypothesis testing for populations of networks
• Testing for Equivalence of Network Distribution Using Subgraph Counts
• A comparative power analysis of the maximum degree and size invariants for random graph inference
• Degree-based goodness-of-fit tests for heterogeneous random graph models: independent and exchangeable cases
• Tuning-free heterogeneous inference in massive networks
• Two-sample test of stochastic block models via the maximum sampling entry-wise deviation
• Sharp local minimax rates for goodness-of-fit testing in multivariate binomial and Poisson families and in multinomials
• statGraph
• Hypothesis testing for equality of latent positions in random graphs
• Statistical inference on attributed random graphs: fusion of graph features and content

This page was built for publication: Two-sample hypothesis testing for inhomogeneous random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q126111)