Testing Cluster Structure of Graphs
Open Access
- 3 June 2026
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 22 (3) , 1-32
Abstract
We study the problem of recognizing the spectral cluster structure of a graph in the framework of property testing in the bounded degree model. A graph is defined to be \((k,\phi_{\textrm{in}},\phi_{\textrm{out}})\) - 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 \(\phi_{\textrm{in}}\) and the (outer) conductance of each part is at most \(\phi_{\textrm{out}}\) . Our main result is a sublinear algorithm with the running time \(\widetilde{O}_{d,k}(\sqrt{n}\cdot\mathrm{poly}(\phi,1/\varepsilon))\) that takes as input an \( n \) -vertex graph with maximum degree bounded by \( d \) , parameters \( k \) , \(\phi\) , \(\varepsilon\) , and with probability at least \(\frac{2}{3}\) , accepts the graph if it is \((k,\phi,O_{d,k}(\varepsilon^{4}\phi^{2}))\) -clusterable, and rejects the graph if it is \(\varepsilon\) -far from \((k,\phi^{*},\psi^{*})\) -clusterable for \(\phi^{*}=O_{d,k}(\frac{\phi^{2}\varepsilon^{4}}{\log n})\) and any \(\psi^{*}\geq 0\) . By the lower bound of \(\Omega(\sqrt{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.
Keywords
Funding Information
- Centre for Discrete Mathematics and its Applications
- Engineering and Physical Sciences Research Council (EP/J021814/1)
- ERC (307696)
- National Natural Science Foundation of China (62272431)
This publication has 35 references indexed in Scilit:
- Spectral concentration and greedy k-clusteringComputational Geometry, 2019
- Finding cycles and trees in sublinear timeRandom Structures & Algorithms, 2012
- Testing Expansion in Bounded-Degree GraphsCombinatorics, Probability and Computing, 2010
- Testing the expansion of a graphInformation and Computation, 2010
- Graph clusteringComputer Science Review, 2007
- Property Testing in Bounded Degree GraphsAlgorithmica, 2002
- Normalized cuts and image segmentationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2000
- Approximate counting, uniform generation and rapidly mixing Markov chainsInformation and Computation, 1989
- Eigenvalues and expandersCombinatorica, 1986
- λ1, Isoperimetric inequalities for graphs, and superconcentratorsJournal of Combinatorial Theory, Series B, 1985