Hypothesis Testing for Random Graphs with Community Structure

Graphs are significant mathematical objects. They naturally appear in many completely different tasks starting from social networks analysis, citation analysis, and ending with protein-protein interactions and brain connectomes analysis. Analysis of random graphs has been an active area of research: there are works on community detection problem, the theory of graph limits, determining the number of communities in the graph, determining the graph model. A significant part of studied problems can be rephrased in the sense of hypothesis testing problem for one graph. However, the hypothesis testing problem in the multiple-graph setting have not got so much attention and still is not well studied. We focus on the problem of testing between two samples of random graphs with a general low-rank structure including graphs with community structures defined on the same set of vertices: we decide whether these graphs are equally distributed or not. In this work, we introduce two bootstrap approaches dealing with the general low-rank structured graphs, and the asymptotic test dealing with the graphs came from Stochastic Block Model. We provide the asymptotic test with theoretical justification. We validate the testing procedures qualities in a series of experiments with simulated data. In experiments with EEG and brain connectomes data, we obtain results that are more reliable than the results obtained by the existing hypothesis testing methods. Moreover, the results on brain connectomes data are competitive with machine learning methods results.