AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (4.4 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Robust Correlation Clustering Problem with Locally Bounded Disagreements

Institute of Mathematics, Hebei University of Technology, Tianjin 300401, China
School of Mathematics and Statistics, Shandong Normal University, Jinan 250358, China
College of Statistics and Data Science, Beijing University of Technology, Beijing 100124, China
Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing 100124, China
Show Author Information

Abstract

Min-max disagreements are an important generalization of the correlation clustering problem (CorCP). It can be defined as follows. Given a marked complete graph G=(V,E), each edge in the graph is marked by a positive label " +" or a negative label " -" based on the similarity of the connected vertices. The goal is to find a clustering 𝒞 of vertices V, so as to minimize the number of disagreements at the vertex with the most disagreements. Here, the disagreements are the positive cut edges and the negative non-cut edges produced by clustering 𝒞. This paper considers two robust min-max disagreements: min-max disagreements with outliers and min-max disagreements with penalties. Given parameter δ∈(0,1/14), we first provide a threshold-based iterative clustering algorithm based on LP-rounding technique, which is a (1/δ,7/(1-14⁢δ))-bi-criteria approximation algorithm for both the min-max disagreements with outliers and the min-max disagreements with outliers on one-sided complete bipartite graphs. Next, we verify that the above algorithm can achieve an approximation ratio of 21 for min-max disagreements with penalties when we set parameter δ=1/21.

Keywords

approximation algorithmmin-max disagreementsoutlierspenaltiesLP-rounding

References

[1]
J. P. Hou, A. Emad, G. J. Puleo, J. Ma, and O. Milenkovic, A new correlation clustering method for cancer mutation analysis, Bioinformatics, vol. 32, no. 24, pp. 3717–3728, 2016.
Crossref Google Scholar
[2]
J. Jafarov, S. Kalhan, K. Makarychev, and Y. Makarychev, Correlation clustering with asymmetric classification errors, in Proc. 37th Int. Conf. Machine Learning, Virtual, 2020, pp. 4641–4650.
Google Scholar
[3]
S. Kim, C. D. Yoo, S. Nowozin, and P. Kohli, Image segmentation using higher-order correlation clustering, IEEE Trans. Pattern Anal. Mach. Intell., vol. 36, no. 9, pp. 1761–1774, 2014.
Crossref Google Scholar
[4]
P. Li, G. J. Puleo, and O. Milenkovic, Motif and hypergraph correlation clustering, IEEE Trans. Inf. Theory, vol. 66, no. 5, pp. 3065–3078, 2019.
Crossref Google Scholar
[5]
A. Ukkonen, Crowdsourced correlation clustering with relative distance comparisons, in Proc. 2017 IEEE Int. Conf. Data Mining (ICDM), New Orleans, LA, USA, 2017, pp. 1117–1122.
Crossref Google Scholar
[6]
N. Veldt, D. F. Gleich, and A. Wirth, A correlation clustering framework for community detection, in Proc. 2018 World Wide Web Conf., Lyon, France, 2018, pp. 439–448.
Crossref Google Scholar
[7]
N. Bansal, A. Blum, and S. Chawla, Correlation clustering, Mach. Learn., vol. 56, pp. 89–113, 2004.
Crossref Google Scholar
[8]
N. Ailon, N. Avigdor-Elgrabli, E. Liberty, and A. V. Zuylen, Improved approximation algorithms for bipartite correlation clustering, SIAM J. Comput., vol. 41, no. 5, pp. 1110–1121, 2012.
Crossref Google Scholar
[9]
N. Ailon, M. Charikar, and A. Newman, Aggregating inconsistent information, J. ACM, vol. 55, no. 5, pp. 1–27, 2008.
Crossref Google Scholar
[10]
M. Bressan, N. Cesa-Bianchi, A. Paudice, and F. Vitale, Correlation clustering with adaptive similarity queries, in Proc. 33rd Int. Conf. Neural Information Processing Systems, Vancouver, Canada, 2019, pp. 12531–12540.
Google Scholar
[11]
M. Charikar, V. Guruswami, and A. Wirth, Clustering with qualitative information, J. Comput. Syst. Sci., vol. 71, no. 3, pp. 360–383, 2005.
Crossref Google Scholar
[12]
J. H. Lange, A. Karrenbauer, and B. Andres, Partial optimality and fast lower bounds for weighted correlation clustering, in Proc. 35th Int. Conf. Machine Learning (ICML), Stockholm, Sweden, 2018, pp. 2892–2901.
Google Scholar
[13]
E. Thiel, M. H. Chehreghani, and D. Dubhashi, A non-convex optimization approach to correlation clustering, Proc. AAAI Conf. Artif. Intell., vol. 33, no. 1, pp. 5159–5166, 2019.
Crossref Google Scholar
[14]
S. Chawla, K. Makarychev, T. Schramm, and G. Yaroslavtsev, Near optimal LP rounding algorithm for correlation clustering on complete and complete k-partite graphs, in Proc. Forty-Seventh Annual ACM Symp. on Theory of Computing, Portland, OR, USA, 2015, pp. 219–228.
Crossref Google Scholar
[15]
G. J. Puleo and O. Milenkovic, Correlation clustering and biclustering with locally bounded errors, IEEE Trans. Inf. Theory, vol. 64, no. 6, pp. 4105–4119, 2018.
Crossref Google Scholar
[16]
M. Charikar, N. Gupta, and R. Schwartz, Local guarantees in graph cuts and clustering, in Proc. 19th Int. Conf. Integer Programming and Combinatorial Optimization, Waterloo, Canada, 2017, pp. 136–147.
Crossref Google Scholar
[17]
, R. Krishnaswamy, and N. Rajaraman, Robust correlation clustering, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019), D. Achlioptas and L. A. Végh, eds. Dagstuhl, Germany: Schloss Dagstuhl, 2019, pp. 33:1–33:18.
[18]
M. H. Chehreghani, Hierarchical correlation clustering and tree preserving embedding, arXiv preprint arXiv: 2002.07756, 2020.
Google Scholar
[19]
D. Vainstein, V. Chatziafratis, G. Citovsky, A. Rajagopalan, M. Mahdian, and Y. Azar, Hierarchical clustering via sketches and hierarchical correlation clustering, arXiv preprint arXiv: 2101.10639, 2021.
Google Scholar
[20]
K. Makarychev, Y. Makarychev, and A. Vijayaraghavan, Correlation clustering with noisy partial information, in Proc. 28th Conf. Learn. Theory (COLT), Paris, France, 2015, pp. 1321–1342.
Google Scholar
[21]
C. Mathieu and W. Schudy, Correlation clustering with noisy input, in Proc. 2010 Annu. ACM-SIAM Symp. on Discrete Algorithms (SODA), Austin, TX, USA, 2010, pp. 712–728.
Crossref Google Scholar
[22]
I. Giotis and V. Guruswami, Correlation clustering with a fixed number of clusters, in Proc. Seventeenth Annu. ACM-SIAM Symp. on Discrete Algorithm (SODA), Miami, FL, USA, 2006, pp. 1167–1176.
Crossref Google Scholar
[23]
A. Aboud and Y. Rabani, Correlation clustering with penalties and approximating the reordering buffer management problem, Doctor dissertation, Computer Sicence Department, Technion, Haifa, Israel, 2008.
Tsinghua Science and Technology
Volume 29 Issue 1,
February 2024
Pages 66-75
DOI: 10.26599/TST.2023.9010027
Cite this article:
Ji S, Li M, Liang M, et al. Robust Correlation Clustering Problem with Locally Bounded Disagreements. Tsinghua Science and Technology, 2024, 29(1): 66-75. https://doi.org/10.26599/TST.2023.9010027

339

Views

23

Downloads

0

Crossref

0

Web of Science

0

Scopus

0

CSCD

Altmetrics
Received: 30 March 2022
Revised: 05 January 2023
Accepted: 06 March 2023
Published: 21 August 2023
© The author(s) 2024.

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).
Return