Correlation clustering is perhaps the most natural formulation of clustering. Given @math objects and a pairwise similarity measure, the goal is to cluster the objects so that, to the best possible extent, similar objects are put in the same cluster and dissimilar objects are put in different clusters. Despite its theoretical appeal, the practical relevance of correlation clustering still remains largely unexplored, mainly due to the fact that correlation clustering requires the @math pairwise similarities as input. In this paper we initiate the investigation into algorithms for correlation clustering. In we are given the identifier of a single object and we want to return the cluster to which it belongs in some globally consistent near-optimal clustering, using a small number of similarity queries. Local algorithms for correlation clustering open the door to algorithms, which are particularly useful when the similarity between items is costly to compute, as it is often the case in many practical application domains. They also imply @math distributed and streaming clustering algorithms, @math constant-time estimators and testers for cluster edit distance, and @math property-preserving parallel reconstruction algorithms for clusterability. Specifically, we devise a local clustering algorithm attaining a @math -approximation in time @math independently of the dataset size. An explicit approximate clustering for all objects can be produced in time @math (which is provably optimal). We also provide a fully additive @math -approximation with local query complexity @math and time complexity @math . The latter yields the fastest polynomial-time approximation scheme for correlation clustering known to date.
Testing and estimating clusterability. Our methods can also be used for quickly testing clusterability of a given input graph @math , which is related to the task of estimating the , i.e., the minimum number of edge label swaps (from +'' to --'' and viceversa) needed to transform @math into a cluster graph. Note that this corresponds to the optimal cost of correlation clustering for the given input @math . Clusterability is a hereditary graph property (closed under removal and renaming of vertices), hence it can be tested with one-sided error using a constant number of queries by the powerful result of Alon and Shapira @cite_14 . Combined with the work of Fischer and Newman @cite_7 , this also yields estimators for cluster edit distance that run in time independent of the graph size. Unfortunately, the query complexity of the algorithm given by these results would be a tower exponential of height @math , where @math is the approximation parameter.
@cite_14 @cite_7
1985538939 2007704435
The problem of characterizing all the testable graph properties is considered by many to be the most important open problem in the area of property testing. Our main result in this paper is a solution of an important special case of this general problem: Call a property tester oblivious if its decisions are independent of the size of the input graph. We show that a graph property @math has an oblivious one-sided error tester if and only if @math is semihereditary. We stress that any “natural” property that can be tested (either with one-sided or with two-sided error) can be tested by an oblivious tester. In particular, all the testers studied thus far in the literature were oblivious. Our main result can thus be considered as a precise characterization of the natural graph properties, which are testable with one-sided error. One of the main technical contributions of this paper is in showing that any hereditary graph property can be tested with one-sided error. This general result contains as a special case all the previous results about testing graph properties with one-sided error. More importantly, as a special case of our main result, we infer that some of the most well-studied graph properties, both in graph theory and computer science, are testable with one-sided error. Some of these properties are the well-known graph properties of being perfect, chordal, interval, comparability, permutation, and more. None of these properties was previously known to be testable. Tolerant testing is an emerging topic in the field of property testing, which was defined in [M. Parnas, D. Ron, and R. Rubinfeld, J. Comput. System Sci., 72 (2006), pp. 1012-1042] and has recently become a very active topic of research. In the general setting, there exist properties that are testable but are not tolerantly testable [E. Fischer and L. Fortnow, Proceedings of the @math th IEEE Conference on Computational Complexity, 2005, pp. 135-140]. On the other hand, we show here that in the setting of the dense graph model, all testable properties are not only tolerantly testable (which was already implicitly proved in [N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy, Combinatorica, 20 (2000), pp. 451-476] and [O. Goldreich and L. Trevisan, Random Structures Algorithms, 23 (2003), pp. 23-57]), but also admit a constant query size algorithm that estimates the distance from the property up to any fixed additive constant. In the course of the proof we develop a framework for extending Szemeredi's regularity lemma, both as a prerequisite for formulating what kind of information about the input graph will provide us with the correct estimation, and as the means for efficiently gathering this information. In particular, we construct a probabilistic algorithm that finds the parameters of a regular partition of an input graph using a constant number of queries, and an algorithm to find a regular partition of a graph using a @math circuit. This, in some ways, strengthens the results of [N. Alon, R. A. Duke, H. Lefmann, V. Rodl, and R. Yuster, J. Algorithms, 16 (1994), pp. 80-109].