@incollection{icml2020_1119,
abstract = {Hypothesis testing of random networks is an emerging area of modern research, especially in the high-dimensional regime, where the number of samples is smaller or comparable to the size of the graph. In this paper we consider the goodness-of-fit testing problem for large inhomogeneous random (IER) graphs, where given a (known) reference symmetric matrix \textdollar Q \textbackslash in [0, 1]\^{}\lbrace n \textbackslash times n\rbrace \textdollar and \textdollar m\textdollar independent samples from an IER graph given by an unknown symmetric matrix \textdollar P \textbackslash in [0, 1]\^{}\lbrace n \textbackslash times n\rbrace \textdollar , the goal is to test the hypothesis \textdollar P=Q\textdollar versus \textdollar \vert \vert P-Q\vert \vert \textbackslash geq \textbackslash varepsilon\textdollar , where \textdollar \vert \vert \textbackslash cdot\vert \vert \textdollar is some specified norm on symmetric matrices. Building on recent related work on two-sample testing for IER graphs, we derive the optimal minimax sample complexities for the goodness-of-fit problem in various natural norms, such as the Frobenius norm and the operator norm. We also propose practical implementations of natural test statistics, using their asymptotic distributions and through the parametric bootstrap. We compare the performances of the different tests in simulations, and show that the proposed tests outperform the baseline tests across various natural random graphs models.},
author = {Dan, Soham and Bhattacharya, Bhaswar B.},
booktitle = {Proceedings of Machine Learning and Systems 2020},
pages = {1810--1819},
title = {Goodness-of-Fit Tests for Inhomogeneous Random Graphs},
year = {2020}
}