Abstract
Correlation Clustering is an elegant model that captures fundamental graph cut problems such as Min \(\,s-t\,\) Cut, Multiway Cut, and Multicut, extensively studied in combinatorial optimization. Here, we are given a graph with edges labeled \(+\) or − and the goal is to produce a clustering that agrees with the labels as much as possible: \(+\) edges within clusters and − edges across clusters. The classical approach towards Correlation Clustering (and other graph cut problems) is to optimize a global objective. We depart from this and study local objectives: minimizing the maximum number of disagreements for edges incident on a single node, and the analogous max min agreements objective. This naturally gives rise to a family of basic min-max graph cut problems. A prototypical representative is Min Max \(s-t\) Cut: find an \(s-t\) cut minimizing the largest number of cut edges incident on any node. We present the following results: (1) an \(O(\sqrt{n})\)-approximation for the problem of minimizing the maximum total weight of disagreement edges incident on any node (thus providing the first known approximation for the above family of min-max graph cut problems), (2) a remarkably simple 7-approximation for minimizing local disagreements in complete graphs (improving upon the previous best known approximation of 48), and (3) a -approximation for maximizing the minimum total weight of agreement edges incident on any node, hence improving upon the
-approximation that follows from the study of approximate pure Nash equilibria in cut and party affiliation games.
M. Charikar and N. Gupta—Supported by NSF grants CCF-1617577, CCF-1302518 and a Simons Investigator Award.
R. Schwartz—Supported by ISF grant 1336/16.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
\(\delta (S)\) denotes the collection of edges crossing the cut \((S,\overline{S})\).
- 2.
Theorem 1 can be easily adapted to apply also for Min Max \(s-t\) Cut, Min Max Multiway Cut, and Min Max Multicut, resulting in a gap of
.
- 3.
The convexity of f is used only to show that relaxation (1) can be solved, and it is not required in the rounding process.
- 4.
Note that \( E^+_{\text {heavy}}\subseteq E^+_0\subseteq E^+_{\text {bad}}\) and \(E^-_{\text {heavy}}\subseteq E^-_{\text {bad}}\).
References
Ailon, N., Avigdor-Elgrabli, N., Liberty, E., van Zuylen, A.: Improved approximation algorithms for bipartite correlation clustering. SIAM J. Comput. 41(5), 1110–1121 (2012)
Ailon, N., Charikar, M., Newman, A.: Aggregating inconsistent information: ranking and clustering. J. ACM (JACM) 55(5), 23 (2008)
Amit, N.: The bicluster graph editing problem. Ph.D. thesis, Tel Aviv University (2004)
Balcan, M.F., Blum, A., Mansour, Y.: Improved equilibria via public service advertising. In: SODA 2009, pp. 728–737 (2009)
Bansal, N., Blum, A., Chawla, S.: Correlation clustering. Mach. Learn. 56(1–3), 89–113 (2004)
Bansal, N., Feige, U., Krauthgamer, R., Makarychev, K., Nagarajan, V., Naor, J., Schwartz, R.: Min-max graph partitioning and small set expansion. SIAM J. Comput. 43(2), 872–904 (2014)
Ben-Dor, A., Shamir, R., Yakhini, Z.: Clustering gene expression patterns. J. Comput. Biol. 6(3–4), 281–297 (1999)
Bhalgat, A., Chakraborty, T., Khanna, S.: Approximating pure nash equilibrium in cut, party affiliation, and satisfiability games. In: EC 2010, pp. 73–82 (2010)
Charikar, M., Guruswami, V., Wirth, A.: Clustering with qualitative information. In: FOCS 2003, pp. 524–533 (2003)
Chawla, S., Makarychev, K., Schramm, T., Yaroslavtsev, G.: Near optimal LP rounding algorithm for correlationclustering on complete and complete k-partite graphs. In: STOC 2015, pp. 219–228 (2015)
Cheng, Y., Church, G.M.: Biclustering of expression data. In: Ismb, vol. 8, pp. 93–103 (2000)
Christodoulou, G., Mirrokni, V.S., Sidiropoulos, A.: Convergence and approximation in potential games. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 349–360. Springer, Heidelberg (2006). doi:10.1007/11672142_28
Demaine, E.D., Emanuel, D., Fiat, A., Immorlica, N.: Correlation clustering in general weighted graphs. Theor. Comput. Sci. 361(2), 172–187 (2006)
Fabrikant, A., Papadimitriou, C., Talwar, K.: The complexity of pure Nash equilibria. In: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, pp. 604–612. ACM (2004)
Filkov, V., Skiena, S.: Integrating microarray data by consensus clustering. Int. J. Artif. Intell. Tools 13(04), 863–880 (2004)
Garg, N., Vazirani, V.V., Yannakakis, M.: Approximate max-flow min-(multi) cut theorems and their applications. In: STOC 1993, pp. 698–707 (1993)
Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: How easy is local search? J. Comput. Syst. Sci. 37(1), 79–100 (1988)
Kriegel, H.P., Kröger, P., Zimek, A.: Clustering high-dimensional data: a survey on subspace clustering, pattern-based clustering, and correlation clustering. ACM Trans. Knowl. Discov. Data (TKDD) 3(1), 1 (2009)
Monderer, D., Shapley, L.S.: Potential games. Games Econ. Behav. 14(1), 124–143 (1996)
Puleo, G., Milenkovic, O.: Correlation clustering and biclustering with locally bounded errors. In: Proceedings of the 33rd International Conference on Machine Learning, pp. 869–877 (2016)
Schäffer, A.A., Yannakakis, M.: Simple local search problems that are hard to solve. SIAM J. Comput. 20(1), 56–87 (1991)
Svitkina, Z., Tardos, É.: Min-max multiway cut. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) APPROX/RANDOM -2004. LNCS, vol. 3122, pp. 207–218. Springer, Heidelberg (2004). doi:10.1007/978-3-540-27821-4_19
Swamy, C.: Correlation clustering: maximizing agreements via semidefinite programming. In: SODA 2004, pp. 526–527 (2004)
Symeonidis, P., Nanopoulos, A., Papadopoulos, A., Manolopoulos, Y.: Nearest-biclusters collaborative filtering with constant values. In: Nasraoui, O., Spiliopoulou, M., Srivastava, J., Mobasher, B., Masand, B. (eds.) WebKDD 2006. LNCS, vol. 4811, pp. 36–55. Springer, Heidelberg (2007). doi:10.1007/978-3-540-77485-3_3
Van Gael, J., Zhu, X.: Correlation clustering for crosslingual link detection. In: IJCAI, pp. 1744–1749 (2007)
Wirth, A.: Correlation clustering. In: Sammut, C., Webb, G. (eds.) Encyclopedia of Machine Learning, pp. 227–231. Springer, Heidelberg (2010)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Charikar, M., Gupta, N., Schwartz, R. (2017). Local Guarantees in Graph Cuts and Clustering. In: Eisenbrand, F., Koenemann, J. (eds) Integer Programming and Combinatorial Optimization. IPCO 2017. Lecture Notes in Computer Science(), vol 10328. Springer, Cham. https://doi.org/10.1007/978-3-319-59250-3_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-59250-3_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-59249-7
Online ISBN: 978-3-319-59250-3
eBook Packages: Computer ScienceComputer Science (R0)