Practical methods for graph two-sample testing
This work addresses a challenging problem in applied research fields like statistics and machine learning, where graph testing is crucial but often limited by few replicates, though it is incremental in improving practical methods.
The paper tackled the problem of two-sample testing for large graphs, where inference is drawn from few replicates, by evaluating existing theoretical methods and proposing two new tests based on asymptotic distributions. The result showed that the new tests are computationally less expensive and, in some cases, more reliable than existing methods.
Hypothesis testing for graphs has been an important tool in applied research fields for more than two decades, and still remains a challenging problem as one often needs to draw inference from few replicates of large graphs. Recent studies in statistics and learning theory have provided some theoretical insights about such high-dimensional graph testing problems, but the practicality of the developed theoretical methods remains an open question. In this paper, we consider the problem of two-sample testing of large graphs. We demonstrate the practical merits and limitations of existing theoretical tests and their bootstrapped variants. We also propose two new tests based on asymptotic distributions. We show that these tests are computationally less expensive and, in some cases, more reliable than the existing methods.