Clustering with qualitative information

By Moses Charikar, Venkatesan Guruswami, Anthony Wirth. 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., 2003

505 citations recorded by the source corpus.

We consider the problem of clustering a collection of elements based on pairwise judgments of similarity and dissimilarity. N. Bansal et al. (2002) cast the problem thus: given a graph G whose edges are labeled "+" (similar) or "-" (dissimilar), partition the vertices into clusters so that the number of pairs correctly (resp. incorrectly) classified with respect to the input labeling is maximized (resp. minimized). Complete graphs, where the classifier labels every edge, and general graphs, where some edges are not labeled, are both worth studying. We answer several questions left open by N. Bansal et al. (2002) and provide a sound overview of clustering with qualitative information. We give a factor 4 approximation for minimization on complete graphs, and a factor O(log n) approximation for general graphs. For the maximization version, a PTAS for complete graphs is shown by N. Bansal et al. (2002); we give a factor 0.7664 approximation for general graphs, noting that a PTAS is unlikely by proving APX-hardness. We also prove the APX-hardness of minimization on complete graphs.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/61d7405a3b5e3b0f843f37efc69f383178a6075b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Correlation clustering in general weighted graphs (2006, background): “[3], the paper of Swamy [26] gives a 0.”
A discriminative framework for clustering via similarity functions (2008, background): “1 Correlation Clustering can be viewed as a relaxation that allows some pairs to fail to satisfy this condition, and the algorithms of [10, 13, 33, 2] show this is sufﬁcient to cluster well if the number of pairs that fail is small.”
A Mathematical Bibliography of Signed and Gain Graphs and Allied Areas (2018, background): “Charnes and W.M. Raike 1966a One-pass algorithms for some generalized network problems. Operations Res. 14 (1966), 914–924.”
Large-Scale Deduplication with Constraints Using Dedupalog (2009, methodology): “For example, it is believed that minor variations of the problem do not have constant factor approximations [15] and obtaining even an unbounded (logn factor) approximation is non-trivial [25].”
Semi-supervised graph clustering: a kernel approach (2005, result): “In contrast, recent work by Bansal et al. (2002), Charikar et al. (2003), Demaine and Immorlica (2003) in semi-supervised clustering considers inputs only in the form of constraints, and does not consider an underlying distance function between the points.”
Modularity-maximizing graph communities via mathematical programming (2007, methodology): “We use a “rounding” procedure due to Charikar et al. [5] for the problem of Correlation Clustering [1].”