Learning Hierarchical Cluster Structure of Graphs in Sublinear Time

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.