Correlation clustering with a fixed number of clusters

ABSTRACT

We continue the investigation of problems concerning correlation clustering or clustering with qualitative information, which is a clustering formulation that has been studied recently [5, 7, 8, 3]. The basic setup here is that we are given as input a complete graph on n nodes (which correspond to nodes to be clustered) whose edges are labeled + (for similar pairs of items) and - (for dissimilar pairs of items). Thus we have only as input qualitative information on similarity and no quantitative distance measure between items. The quality of a clustering is measured in terms of its number of agreements, which is simply the number of edges it correctly classifies, that is the sum of number of - edges whose endpoints it places in different clusters plus the number of + edges both of whose endpoints it places within the same cluster.In this paper, we study the problem of finding clusterings that maximize the number of agreements, and the complementary minimization version where we seek clusterings that minimize the number of disagreements. We focus on the situation when the number of clusters is stipulated to be a small constant k. Our main result is that for every k, there is a polynomial time approximation scheme for both maximizing agreements and minimizing disagreements. (The problems are NP-hard for every k ≥ 2.) The main technical work is for the minimization version, as the PTAS for maximizing agreements follows along the lines of the property tester for Max k-CUT from [13].In contrast, when the number of clusters is not specified, the problem of minimizing disagreements was shown to be APX-hard [7], even though the maximization version admits a PTAS.

REFERENCES

• 1: Amit Agarwal , Moses Charikar , Konstantin Makarychev , Yury Makarychev, O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060675]
• 2: Nir Ailon , Moses Charikar , Alantha Newman, Aggregating inconsistent information: ranking and clustering, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060692]
• 3: Noga Alon , Konstantin Makarychev , Yury Makarychev , Assaf Naor, Quadratic forms on graphs, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060664]
• 4: Sanjeev Arora , Eli Berger , Guy Kindler , Muli Safra , Elad Hazan, On Non-Approximability for Quadratic Programs, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.206-215, October 23-25, 2005 [doi>10.1109/SFCS.2005.57]
• 5: Nikhil Bansal , Avrim Blum , Shuchi Chawla, Correlation Clustering, Machine Learning, v.56 n.1-3, p.89-113 [doi>10.1023/B:MACH.0000033116.57574.95]
• 6: A. Ben-Dor, R. Shamir, and Z. Yakhini. Clustering gene expression patterns. J Comp. Biol., 6:281--97, 1999.
• 7: Moses Charikar , Venkatesan Guruswami , Anthony Wirth, Clustering with qualitative information, Journal of Computer and System Sciences, v.71 n.3, p.360-383, October 2005 [doi>10.1016/j.jcss.2004.10.012]
• 8: Moses Charikar , Anthony Wirth, Maximizing Quadratic Programs: Extending Grothendieck's Inequality, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.54-60, October 17-19, 2004 [doi>10.1109/FOCS.2004.39]
• 9: W. Fernandez de la Vega , Marek Karpinski , Claire Kenyon , Yuval Rabani, Approximation schemes for clustering problems, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780550]
• 10: W. Fernandez de la Vega , Claire Kenyon, A Randomized Approximation Scheme for Metric MAX-CUT, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.468, November 08-11, 1998
• 11: E. Demaine and N. Immorlica. Correlation clustering with partial information. In Proc. of 6th APPROX, pages 1--13, 2003.
• 12: D. Emanuel and A. Fiat. Correlation clustering---minimizing disagreements on arbitrary weighted graphs. In Proc. of 11th ESA, pages 208--20, 2003.
• 13: Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998 [doi>10.1145/285055.285060]
• 14: Piotr Indyk, A Sublinear Time Approximation Scheme for Clustering in Metric Spaces, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.154, October 17-18, 1999
• 15: Subhash Khot , Guy Kindler , Elchanan Mossel , Ryan O'Donnell, Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.146-154, October 17-19, 2004 [doi>10.1109/FOCS.2004.49]
• 16: A. Nemirovski, C. Roos, and T. Terlaky. On maximization of quadratic form over intersection of ellipsoids with common center. Mathematical Programming, 86(3):463--473, 1999.
• 17: Ron Shamir , Roded Sharan , Dekel Tsur, Cluster Graph Modification Problems, Revised Papers from the 28th International Workshop on Graph-Theoretic Concepts in Computer Science, p.379-390, June 13-15, 2002
• 18: Chaitanya Swamy, Correlation Clustering: maximizing agreements via semidefinite programming, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
  G.3 PROBABILITY AND STATISTICS
      Subjects: Correlation and regression analysis

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

General Terms:
Algorithms, Theory