# Practical methods for graph two-sample testing

arXiv: https://arxiv.org/abs/1811.12752 · HTML: https://mlsanity.com/paper/1811.12752/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Nov 2018.

## Built on by (most cited first, 7 of 7)

- [Meta Two-Sample Testing: Learning Kernels for Testing with Limited Data](https://mlsanity.com/paper/2106.07636/) (2021)
- [Graphon based Clustering and Testing of Networks: Algorithms and Theory](https://mlsanity.com/paper/2110.02722/) (2021)
- [A Unified Data Representation Learning for Non-parametric Two-sample Testing](https://mlsanity.com/paper/2412.00613/) (2024)
- [Zero-Flow Two-Sample Tests](https://mlsanity.com/paper/2607.21542/) (2026)
- [Higher-order accurate two-sample network inference and network hashing](https://mlsanity.com/paper/2208.07573/) (2022)
- [A Sampling-based Framework for Hypothesis Testing on Large Attributed Graphs](https://mlsanity.com/paper/2403.13286/) (2024)
- [Asymptotically perfect seeded graph matching without edge correlation (and applications to inference)](https://mlsanity.com/paper/2506.02825/) (2025)

## Abstract (arXiv)

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.