# Two-sample Hypothesis Testing for Inhomogeneous Random Graphs

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jul 2017.

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

- [Graphon based Clustering and Testing of Networks: Algorithms and Theory](https://mlsanity.com/paper/2110.02722/) (2021)
- [Hypothesis Testing for Equality of Latent Positions in Random Graphs](https://mlsanity.com/paper/2105.10838/) (2021)
- [Graph similarity learning for change-point detection in dynamic networks](https://mlsanity.com/paper/2203.15470/) (2022)
- [Network two-sample test for block models](https://mlsanity.com/paper/2406.06014/) (2024)
- [Differentially Describing Groups of Graphs](https://mlsanity.com/paper/2201.04064/) (2021)
- [Multivariate Analysis for Multiple Network Data via Semi-Symmetric Tensor PCA](https://mlsanity.com/paper/2202.04719/) (2022)
- [Higher-order accurate two-sample network inference and network hashing](https://mlsanity.com/paper/2208.07573/) (2022)
- [When does the mean network capture the topology of a sample of networks?](https://mlsanity.com/paper/2408.03461/) (2024)
- [Counting Cycles with AI: Counting Cycles with AI: Computationally Efficient Equivalent Forms with Applications](https://mlsanity.com/paper/2505.17964/) (2025)
- [A Sampling-based Framework for Hypothesis Testing on Large Attributed Graphs](https://mlsanity.com/paper/2403.13286/) (2024)
- [The Spectral Barycentre of a Set of Graphs with Community Structure](https://mlsanity.com/paper/2502.00038/) (2025)
- [Asymptotically perfect seeded graph matching without edge correlation (and applications to inference)](https://mlsanity.com/paper/2506.02825/) (2025)
- [Two-Sample Testing for Inhomogeneous Random Graphs in Non-Integral Lr Norms](https://mlsanity.com/paper/2609.33968/) (2026)

## Abstract (arXiv)

The study of networks leads to a wide range of high dimensional inference problems. In many practical applications, one needs to draw inference from one or few large sparse networks. The present paper studies hypothesis testing of graphs in this high-dimensional regime, where the goal is to test between two populations of inhomogeneous random graphs defined on the same set of n vertices. The size of each population m is much smaller than n, and can even be a constant as small as 1. The critical question in this context is whether the problem is solvable for small m. We answer this question from a minimax testing perspective. Let P,Q be the population adjacencies of two sparse inhomogeneous random graph models, and d be a suitably defined distance function. Given a population of m graphs from each model, we derive minimax separation rates for the problem of testing P=Q against d(P,Q)>ρ. We observe that if m is small, then the minimax separation is too large for some popular choices of d, including total variation distance between corresponding distributions. This implies that some models that are widely separated in d cannot be distinguished for small m, and hence, the testing problem is generally not solvable in these cases. We also show that if m>1, then the minimax separation is relatively small if d is the Frobenius norm or operator norm distance between P and Q. For m=1, only the latter distance provides small minimax separation. Thus, for these distances, the problem is solvable for small m. We also present near-optimal two-sample tests in both cases, where tests are adaptive with respect to sparsity level of the graphs.