Hypothesis testing for graphs: Fundamental limits and practical methods
Date:
Thursday, February 14, 2019 09:00 - 10:00
Speaker:
Debarghya Ghoshdastidar (University of Tübingen)
Location:
Mondi Seminar Room 2, Central Building
Series:
Mathematics and CS Seminar
Host:
Christoph Lampert
Contact:
GUGGENBICHLER Teresa
Two-sample hypothesis testing for graphs is the statistical problem of testing whether two given populations of graphs are similar or significantly different. It is an important tool in many scientific disciplines including bioinformatics, neuroscience and social science. For instance, testing between brain networks of Alzheimer patients and healthy individuals reveal the neurological effects of Alzheimer's disease. The graph testing problem is quite challenging as one often needs to draw inference from one or few samples of large graphs.
In this talk, we provide insights into the fundamental challenges of the problem from a statistical (minimax) perspective. We show that some standard formulations of the testing problem are unsolvable if we observe only few samples. On the positive side, we present two problem formulations that are solvable even when we observe only one or two graphs from each population. We also present new statistical tests based on asymptotics of large random graphs, and demonstrate the use of these methods in testing real networks.