# Testing Network Structure Using Relations Between Small Subgraph Probabilities

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Apr 2017.

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

- [Testing network correlation efficiently via counting trees](https://mlsanity.com/paper/2110.11816/) (2021)
- [Sharp detection boundaries on testing dense subhypergraph](https://mlsanity.com/paper/2101.04584/) (2021)
- [Higher-order accurate two-sample network inference and network hashing](https://mlsanity.com/paper/2208.07573/) (2022)
- [Optimal community detection in dense bipartite graphs](https://mlsanity.com/paper/2505.18372/) (2025)
- [Two-Sample Testing for Random Graphs without Vertex Correspondence](https://mlsanity.com/paper/2610.07503/) (2026)

## Abstract (arXiv)

We study the problem of testing for structure in networks using relations between the observed frequencies of small subgraphs. We consider the statistics beginalign* T3 & =(edge frequency)3 - triangle frequency T2 & =3(edge frequency)2(1-edge frequency) - V-shape frequency endalign* and prove a central limit theorem for (T2, T3) under an ErdHos-R'enyi null model. We then analyze the power of the associated chi2 test statistic under a general class of alternative models. In particular, when the alternative is a k-community stochastic block model, with k unknown, the power of the test approaches one. Moreover, the signal-to-noise ratio required is strictly weaker than that required for community detection. We also study the relation with other statistics over three-node subgraphs, and analyze the error under two natural algorithms for sampling small subgraphs. Together, our results show how global structural characteristics of networks can be inferred from local subgraph frequencies, without requiring the global community structure to be explicitly estimated.