# Testing Cluster Structure of Graphs

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Apr 2015.

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

- [A Tighter Analysis of Spectral Clustering, and Beyond](https://mlsanity.com/paper/2208.01724/) (2022)
- [Efficient and Local Parallel Random Walks](https://mlsanity.com/paper/2112.00655/) (2021)
- [Sublinear-Time Clustering Oracle for Signed Graphs](https://mlsanity.com/paper/2206.13813/) (2022)
- [Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation](https://mlsanity.com/paper/2212.00642/) (2022)
- [A Differentially Private Clustering Algorithm for Well-Clustered Graphs](https://mlsanity.com/paper/2403.14332/) (2024)
- [Structure-Aware Spectral Sparsification via Uniform Edge Sampling](https://mlsanity.com/paper/2510.12669/) (2025)
- [A Sublinear-Time Spectral Clustering Oracle with Improved Preprocessing Time](https://mlsanity.com/paper/2310.17878/) (2023)

## Abstract (arXiv)

We study the problem of recognizing the cluster structure of a graph in the framework of property testing in the bounded degree model. Given a parameter varepsilon, a d-bounded degree graph is defined to be (k, φ)-clusterable, if it can be partitioned into no more than k parts, such that the (inner) conductance of the induced subgraph on each part is at least φ and the (outer) conductance of each part is at most cd,kvarepsilon4φ2, where cd,k depends only on d,k. Our main result is a sublinear algorithm with the running time widetildeO(√n·poly(φ,k,1/varepsilon)) that takes as input a graph with maximum degree bounded by d, parameters k, φ, varepsilon, and with probability at least frac23, accepts the graph if it is (k,φ)-clusterable and rejects the graph if it is varepsilon-far from (k, φ^*)-clusterable for φ^* = c'd,kfracφ2 varepsilon4log n, where c'd,k depends only on d,k. By the lower bound of Omega(√n) on the number of queries needed for testing graph expansion, which corresponds to k=1 in our problem, our algorithm is asymptotically optimal up to polylogarithmic factors.