Robust Clustering Oracle and Local Reconstructor of Cluster Structure of Graphs

We develop sublinear time algorithms for analyzing the cluster structure of graphs with noisy partial information. A graph G with maximum degree at most d is called (k, φin, φout)-clusterable, if it can be partitioned into at most k parts, such that each part has inner conductance at least φin and outer conductance at most φout, where d is assumed to be constant. A graph G is called to be an ∊-perturbation of a (k,φin, φout)-clusterable graph if there is partition of G with at most k parts (called clusters), such that one can insert/delete at most ϵdn intra-cluster edges to make it a (k,φin,φout)-clusterable graph. We are given query access to the adjacency list of such a graph. We show that one can construct in time a robust clustering oracle for a bounded-degree graph G that is an ∊-perturbation of a -clusterable graph. Using such an oracle, a typical clustering query (e.g., IsOutlier(s), SameCluster(s, t)) can be answered in time and the answers are consistent with a partition of G in which all but vertices belong to a good cluster, i.e., a set with inner conductance at least , and outer conductance . We also develop a local reconstruction algorithm that takes as input a graph as above, and on any query vertex v, outputs all its neighbors in the reconstructed graph G’, which is guaranteed to be -clusterable (with slightly boosting degree bound). The number of edges changed is at most . Furthermore, the algorithm runs in time (per query) and can answer consistently with the same G′ for any sequence of queries it gets.