pith. sign in

arxiv: 1907.00117 · v1 · pith:JJ2CZ6ZJnew · submitted 2019-06-28 · 💻 cs.DS

Min-Max Correlation Clustering via MultiCut

Saba Ahmadi , Sainyam Galhotra , Samir Khuller , Barna Saha , Roy Schwartz This is my paper

Pith reviewed 2026-05-25 12:40 UTC · model grok-4.3

classification 💻 cs.DS
keywords correlation clusteringmin-max objectiveapproximation algorithmsmulticutgraph partitioningdisagreement minimization
0
0 comments X

The pith

Min-max correlation clustering on weighted graphs admits an O(sqrt(log n * max(log |E-|, log k))) approximation via reduction to min-max multicut.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines correlation clustering on graphs with positive and negative weighted edges, shifting focus from minimizing total disagreements to minimizing the worst disagreements suffered by any one cluster. It supplies the first nontrivial approximation algorithm for this min-max version on general weighted graphs. The algorithm proceeds by establishing a matching guarantee for a min-max variant of the multicut problem and reducing the clustering task to it. A reader would care because the per-cluster guarantee prevents any single group from accumulating too many errors, a property useful when clusters must each remain reliable on their own.

Core claim

We provide the first nontrivial approximation algorithm for min-max correlation clustering achieving an O(√(log n ⋅ max{log(|E−|), log(k)}}) approximation for general weighted graphs. This is obtained via a corresponding approximation for the min-max multicut problem, with further improvements to O(r²) for graphs excluding K_{r,r} minors and a 14-approximation for complete graphs.

What carries the argument

The reduction from min-max correlation clustering to min-max multicut that transfers the approximation guarantee without extra loss.

If this is right

  • The same approximation ratio holds for the min-max multicut problem on general weighted graphs.
  • Both problems admit O(r²)-approximations on graphs that exclude K_{r,r} minors.
  • Min-max correlation clustering on complete graphs admits a 14-approximation.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The multicut reduction may extend to other per-component min-max objectives in graph partitioning tasks.
  • When the number of negative edges or the optimal number of clusters is small, the practical ratio may improve beyond the worst-case bound.

Load-bearing premise

The reduction from min-max correlation clustering to the corresponding min-max multicut problem preserves the approximation factor without introducing additional loss.

What would settle it

A concrete weighted graph instance on which the algorithm returns a clustering whose maximum per-cluster disagreement exceeds the claimed factor times the optimal min-max value.

read the original abstract

Correlation clustering is a fundamental combinatorial optimization problem arising in many contexts and applications that has been the subject of dozens of papers in the literature. In this problem we are given a general weighted graph where each edge is labeled positive or negative. The goal is to obtain a partitioning (clustering) of the vertices that minimizes disagreements - weight of negative edges trapped inside a cluster plus positive edges between different clusters. Most of the papers on this topic mainly focus on minimizing total disagreement, a global objective for this problem. In this paper, we study a cluster-wise objective function that asks to minimize the maximum number of disagreements of each cluster, which we call min-max correlation clustering. The min-max objective is a natural objective that respects the quality of every cluster. In this paper, we provide the first nontrivial approximation algorithm for this problem achieving an $\mathcal{O}(\sqrt{\log n\cdot\max\{\log(|E^-|),\log(k)\}})$ approximation for general weighted graphs, where $|E^-|$ denotes the number of negative edges and $k$ is the number of clusters in the optimum solution. To do so, we also obtain a corresponding result for multicut where we wish to find a multicut solution while trying to minimize the total weight of cut edges on every component. The results are then further improved to obtain (i) $\mathcal{O}(r^2)$-approximation for min-max correlation clustering and min-max multicut for graphs that exclude $K_{r,r}$ minors (ii) a 14-approximation for the min-max correlation clustering on complete graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The manuscript introduces the min-max correlation clustering problem (minimize the maximum per-cluster disagreements on a signed weighted graph) and claims the first nontrivial approximation algorithm, with ratio O(√(log n ⋅ max{log |E^-|, log k})) for general graphs. The algorithm is obtained by reducing the problem to an analogous min-max multicut problem (minimize the maximum cut weight per component) and solving the latter; the paper also gives an O(r²) approximation when the graph excludes K_{r,r} minors and a 14-approximation on complete graphs.

Significance. If the reduction and multicut algorithm are correct, the work supplies the first nontrivial guarantee for a natural per-cluster objective that is more equitable than the classical total-disagreement objective. The explicit link to a min-max multicut variant and the improved bounds for minor-free and complete graphs constitute a technical contribution that could influence other balanced clustering and cut problems.

major comments (1)
  1. [Abstract] Abstract: the central claim that the reduction from min-max correlation clustering to min-max multicut preserves the approximation factor without additional loss is load-bearing for the main result, yet the abstract supplies no construction or argument establishing that the factor is preserved exactly as stated.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their comments. We address the single major comment below and will revise the abstract accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that the reduction from min-max correlation clustering to min-max multicut preserves the approximation factor without additional loss is load-bearing for the main result, yet the abstract supplies no construction or argument establishing that the factor is preserved exactly as stated.

    Authors: The reduction is detailed in Section 3 of the full manuscript, where we prove that the two problems are equivalent up to the objective value: any feasible clustering for min-max correlation clustering yields a feasible multicut with identical per-component cost, and conversely any multicut solution yields a clustering with the same cost. Consequently the approximation factor is preserved exactly with no additional loss. We will revise the abstract to include a brief sentence referencing this equivalence. revision: yes

Circularity Check

0 steps flagged

No significant circularity; algorithmic construction is self-contained

full rationale

The paper's central contribution is a reduction from min-max correlation clustering to a min-max multicut problem followed by an approximation algorithm achieving the stated O(√(log n ⋅ max{log |E−|, log k})) bound. No equations or steps reduce a claimed prediction or result to a fitted parameter or self-citation by construction. The reduction is presented as factor-preserving via standard graph partitioning techniques, with no self-definitional loops, renamed empirical patterns, or load-bearing self-citations that would force the result. The derivation relies on external combinatorial primitives and is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

No free parameters, invented entities, or nonstandard axioms are introduced in the abstract; the work rests on standard assumptions of weighted graph problems and the existence of an optimum clustering with k clusters.

axioms (1)
  • domain assumption Existence of an optimal clustering with a finite number k of clusters
    Implicit in the problem statement and approximation guarantee that references k.

pith-pipeline@v0.9.0 · 5824 in / 1079 out tokens · 42694 ms · 2026-05-25T12:40:14.202298+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

  1. [1]

    Ahmadi, S

    S. Ahmadi, S. Khuller, and B. Saha. Min-max correlation cl ustering via multicut. In A. Lodi and V. Nagarajan, editors, Integer Programming and Combinatorial Optimization, pages 13–26, Cham, 2019. Springer International Publishi ng

    work page 2019

  2. [2]

    Ailon, N

    N. Ailon, N. Avigdor-Elgrabli, E. Liberty, and A. Van Zuyl en. Improved approxi- mation algorithms for bipartite correlation clustering. SIAM Journal on Comput- ing, 41(5):1110–1121, 2012

    work page 2012

  3. [3]

    Ailon, M

    N. Ailon, M. Charikar, and A. Newman. Aggregating inconsi stent information: ranking and clustering. Journal of the ACM (JACM) , 55(5):23, 2008

    work page 2008

  4. [4]

    Bansal, A

    N. Bansal, A. Blum, and S. Chawla. Correlation clustering . Machine Learning , 56(1-3):89–113, 2004

    work page 2004

  5. [5]

    Bansal, U

    N. Bansal, U. Feige, R. Krauthgamer, K. Makarychev, V. Nag arajan, S. Naor, and R. Schwartz. Min-max graph partitioning and small set expan sion. SIAM Journal on Computing , 43(2):872–904, 2014

    work page 2014

  6. [6]

    Charikar, N

    M. Charikar, N. Gupta, and R. Schwartz. Local guarantees i n graph cuts and clustering. In International Conference on Integer Programming and Combi natorial Optimization, pages 136–147. Springer, 2017

    work page 2017

  7. [7]

    Charikar, V

    M. Charikar, V. Guruswami, and A. Wirth. Clustering with q ualitative informa- tion. In Foundations of Computer Science, 2003. Proceedings. 44th A nnual IEEE Symposium on , pages 524–533. IEEE, 2003

    work page 2003

  8. [8]

    Chawla, K

    S. Chawla, K. Makarychev, T. Schramm, and G. Yaroslavtsev . Near optimal lp rounding algorithm for correlationclustering on complete and complete k-partite graphs. In Proceedings of the forty-seventh annual ACM symposium on Th eory of computing, pages 219–228. ACM, 2015

    work page 2015

  9. [9]

    Cheng and G

    Y. Cheng and G. M. Church. Biclustering of expression data . In Ismb, volume 8, pages 93–103, 2000

    work page 2000

  10. [10]

    Chlamtac, K

    E. Chlamtac, K. Makarychev, and Y. Makarychev. How to pla y unique games using embeddings. In Foundations of Computer Science, 2006. FOCS’06. 47th Annua l IEEE Symposium on , pages 687–696. IEEE, 2006

    work page 2006

  11. [11]

    E. D. Demaine, D. Emanuel, A. Fiat, and N. Immorlica. Corr elation clustering in general weighted graphs. Theoretical Computer Science , 361(2-3):172–187, 2006

    work page 2006

  12. [12]

    S. Kim, S. Nowozin, P. Kohli, and C. D. Yoo. Higher-order c orrelation clustering for image segmentation. In J. Shawe-Taylor, R. S. Zemel, P. L . Bartlett, F. Pereira, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 24, pages 1530–1538. Curran Associates, Inc., 2011

    work page 2011

  13. [13]

    Kirillov, E

    A. Kirillov, E. Levinkov, B. Andres, B. Savchynskyy, and C. Rother. Instancecut: From edges to instances with multicut. In Computer Vision and Pattern Recogni- tion (CVPR), 2017 IEEE Conference on , pages 7322–7331. IEEE, 2017

    work page 2017

  14. [14]

    Kriegel, P

    H.-P. Kriegel, P. Kr¨ oger, and A. Zimek. Clustering high-dimensional data: A survey on subspace clustering, pattern-based clustering, and cor relation clustering. ACM Transactions on Knowledge Discovery from Data (TKDD) , 3(1):1, 2009

    work page 2009

  15. [15]

    Puleo and O

    G. Puleo and O. Milenkovic. Correlation clustering and b iclustering with locally bounded errors. In International Conference on Machine Learning , pages 869–877, 2016

    work page 2016

  16. [16]

    Svitkina and ´E

    Z. Svitkina and ´E. Tardos. Min-max multiway cut. In Approximation, Randomiza- tion, and Combinatorial Optimization. Algorithms and Tech niques, pages 207–218. Springer, 2004

    work page 2004

  17. [17]

    Symeonidis, A

    P. Symeonidis, A. Nanopoulos, A. Papadopoulos, and Y. Ma nolopoulos. Nearest- biclusters collaborative filtering with constant values. I n International Workshop on Knowledge Discovery on the Web , pages 36–55. Springer, 2006

    work page 2006