Testing graph cluster structure has been a central object of study in property testing since the foundational work of Goldreich and Ron [STOC'96] on expansion testing, i.e. the problem of distinguishing between a single cluster (an expander) and a graph that is far from a single cluster. More generally, a $(k, ε)$-clusterable graph $G$ is a graph whose vertex set admits a partition into $k$ induced expanders, each with outer conductance bounded by $ε$. A recent line of work initiated by Czumaj, Peng and Sohler [STOC'15] has shown how to test whether a graph is close to $(k, ε)$-clusterable, and to locally determine which cluster a given vertex belongs to with misclassification rate $\approx ε$, but no sublinear time algorithms for learning the structure of inter-cluster connections are known. As a simple example, can one locally distinguish between the `cluster graph' forming a line and a clique? In this paper, we consider the problem of testing the hierarchical cluster structure of $(k, ε)$-clusterable graphs in sublinear time. Our measure of hierarchical clusterability is the well-established Dasgupta cost, and our main result is an algorithm that approximates Dasgupta cost of a $(k, ε)$-clusterable graph in sublinear time, using a small number of randomly chosen seed vertices for which cluster labels are known. Our main result is an $O(\sqrt{\log k})$ approximation to Dasgupta cost of $G$ in $\approx n^{1/2+O(ε)}$ time using $\approx n^{1/3}$ seeds, effectively giving a sublinear time simulation of the algorithm of Charikar and Chatziafratis [SODA'17] on clusterable graphs. To the best of our knowledge, ours is the first result on approximating the hierarchical clustering properties of such graphs in sublinear time.

One natural question in the area of sublinear time algorithms asks whether we can distinguish between graphs with max-cut value at least 1-ε from graphs with max-cut value at most 1/2+ε in the adjacency list model where we can make degree queries and neighbor queries. Chiplunkar, Kapralov, Khanna, Mousavifar, and Peres (FOCS' 18) showed that in graphs of bounded degree, one cannot hope for a factor 1/2+ε approximation to the max-cut value in time n^{1/2+o(ε)}. Recently, Peng and Yoshida (SODA '23) obtained o(n) time algorithms which can distinguish expanders with max-cut value at least 1-ε from expanders with small max-cut value (their running time is n^{1/2+O(ε)}). In this paper, going beyond the results of Peng-Yoshida, we develop sublinear time algorithms for this problem on clusterable graphs (which is a graph class with a good community structure). Our algorithms run in ≈ n^{0.5001+ O(ε)} time. A natural extension of Peng-Yoshida approach does not seem to work for clusterable graphs. Indeed, their random walk based technique tracks the 𝓁₂ length of random walk vectors and they exploit the difference in the length of these vectors to tell apart expanders with large cut value from expanders with small cut-value. Such approaches fail to be reliable when graph has loosely connected clusters. Taking inspiration from [Ashish Chiplunkar et al., 2018], we exploit the more refined geometry of spectra of clusterable graphs which leads to our sublinear time implementation. We prove a novel spectral lemma which shows that in a spectral expander 2 - λ_{n-1} ≥ Ω(λ₂). This lemma is leveraged to show that there is a suitable difference between spectra of clusterable graphs with large cut value and spectra of clusterable graphs with small cut value. We use this gap to obtain our sublinear time implementation. To do this, we obtain a nuanced understanding of the eigenvector structure of clusterable graphs and in particular, we show that the eigenvectors of the normalized Laplacian of a clusterable graph, corresponding to eigenvalues which are close to 2 have a small infinity norm.

Learning graph cluster structure using few queries is a classical question in property testing, with the fundamental special case, namely expansion testing, considered in the seminal work of Goldreich and Ron[STOC'96]. The most recent results in this line of work design clustering oracles for (k, ε)-clusterable graphs, which are graphs that can be partitioned into k induced expanders with outer conductance bounded by ε ≪ 1. These oracles, given a graph whose vertex set can be partitioned into a disjoint union of k clusters (i.e., good expanders) with outer conductances bounded by ε ≪ 1, provide query access to an O(ε log k)- approximation to this ground truth clustering in time ≈ 2poly(k/ε)n1/2+O(ε) per query. Motivated by the rising interest in learning hierarchical structures in large networks, in this paper we introduce (k, γ)-hierarchically clusterable graphs, a natural hierarchical analog of classical (k, ε)-clusterable graphs; intuitively, these are graphs that exhibit pronounced hierarchical structure. We give a hierarchical clustering oracle for this model, i.e. a small space data structure that provides query access to a good hierarchical clustering at cost ≈ poly(k) · n1/2+O(γ) per query; notably, the dependence on k is polynomial, in contrast to best known flat clustering oracles. The result relies on several structural properties of hierarchically clusterable graphs that we hope will be of independent interest in sublinear time spectral graph algorithms.