Two-sample hypothesis testing for inhomogeneous random graphs

DOI10.1214/19-AOS1884MaRDI QIDQ126111zbMATH OpenOpenAlexFDO

Authors Debarghya Ghoshdastidar, 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

inhomogeneous Erdős-Rényi modelminimax testingtwo-sample test

Mathematics Subject Classification ID

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

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.

Review text

Testing random graphs is challenging problem especially in large dimensions (chemical compounds graphs, brain networks of several patients analysis, and other). This paper focuses on the drawing inference from large sparse networks and consider the graphs on a common vertex set sampled from an inhomogeneous Erdös-Rényi model [\textit{B. Bollobàs} et al., Random Struct. Algorithms 31, No. 1, 3--122 (2007; Zbl 1123.05083)]. The latter model is considered in the case when no structural assumption on the population adjacency matrix is assumed.

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

• 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
• scientific article; zbMATH DE number 5968943 (Why is no real title available?)
• scientific article; zbMATH DE number 889593 (Why is no real title available?)
• 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 for high-dimensional geometry in random graphs
• Testing Ising models
• 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

(31)

• A nonparametric two-sample hypothesis testing problem for random graphs
• statGraph
• Tuning-free heterogeneous inference in massive networks
• Combinatorial inference for graphical models
• Sharp local minimax rates for goodness-of-fit testing in multivariate binomial and Poisson families and in multinomials
• Statistical inference on attributed random graphs: fusion of graph features and content
• Hypotheses testing on infinite random graphs
• Testing for Equivalence of Network Distribution Using Subgraph Counts
• Degree-based goodness-of-fit tests for heterogeneous random graph models: independent and exchangeable cases
• A General Asymptotic Framework for Distribution-Free Graph-Based Two-Sample Tests
• A comparative power analysis of the maximum degree and size invariants for random graph inference
• Hypothesis testing for populations of networks
• A Spectral-Based Framework for Hypothesis Testing in Populations of Networks
• Random geometric graph: some recent developments and perspectives
• Two-sample test of stochastic block models
• Hypothesis testing for equality of latent positions in random graphs
• Two-sample test of stochastic block models via the maximum sampling entry-wise deviation
• Likelihood Ratio Tests in Random Graph Models with Increasing Dimensions
• The spectral barycentre of a set of graphs with community structure
• Local goodness-of-fit testing for Hölder-continuous densities: minimax rates
• Optimal Network Pairwise Comparison
• Two-sample test for stochastic block models via the largest singular value
• Higher-Order Accurate Two-Sample Network Inference and Network Hashing
• Nonparametric two-sample hypothesis testing for low-rank random graphs of differing sizes
• A Bootstrap-based Method for Testing Similarity of Matched Networks
• An overview of asymptotic normality in stochastic blockmodels: cluster analysis and inference
• Forest Expression of Networks and their Applications
• Detection and estimation of vertexwise latent position shifts across networks
• Localized geometry detection in scale-free random graphs
• Multivariate Analysis for Multiple Network Data via Semi-Symmetric Tensor PCA
• Network-valued random vectors and their statistical foundations: a comparison of inferential techniques and testing frameworks under heterogeneity

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)