Two-sample Hypothesis Testing for Inhomogeneous Random Graphs

Debarghya Ghoshdastidar (Universität Tübingen)
Wednesday, October 25, 2017 - 10:00am
WIAS, Erhard-Schmidt-Saal, Mohrenstraße 39, 10117 Berlin

In this talk, we consider the problem of testing between two populations of inhomogeneous random graphs defined on the same set of vertices. We are particularly interested in the high-dimensional setting where the population size is potentially much smaller than the graph size, and may even be constant. It is known that this setting cannot be tackled if the separation between two models is quantified in terms of total variation distance.
Hence, we study two-sample testing problems where the separation between models is quantified by the Frobenius or operator norms of the difference between the population adjacency matrices. We derive upper and lower bounds for the minimax separation rate for these problems. Interestingly, the proposed near-optimal tests are uniformly consistent in both the “large graph, small sample” and “small graph, large sample” regimes.
This is a joint work with Maurilio Gutzeit, Alexandra Carpentier and Ulrike von Luxburg.