PaperlayerView exact revision on arXiv

Source-linked AI summary

Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs

Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, Grigory Yaroslavtsev

arXiv:1412.0681v3cs.DS

TL;DR

Correlation clustering seeks partitions that best fit noisy pairwise similarity and dissimilarity labels. The paper develops new LP rounding schemes and obtains approximation ratios that nearly or exactly match integrality gaps across several graph settings.

  • Problem

    Correlation clustering seeks a partition that fits inconsistent pairwise similarity and dissimilarity information as closely as possible; on general graphs, obtaining any constant-factor approximation is Unique-Games hard.

    Source: §1 · p. 3

  • Method

    The paper rounds the standard LP solution using carefully designed functions to set edge-rounding probabilities, with a simple O(n^2) algorithm given the LP solution.

    Source: §1.1 · p. 4, §2 · p. 7

  • Results

    2.06−ε for complete graphs nearly matches the integrality gap of 2, while complete k-partite graphs achieve 3 with a matching gap and the weighted triangle-inequality variant achieves 1.5.

    Source: §1.1 · p. 4

  • Takeaways & Limitations

    The rounding approach nearly or exactly matches the LP integrality gap in the complete-graph and complete k-partite settings.

    Source: §1.1 · p. 4

    The weighted guarantee is for instances with positive-edge weights normalized to 1 and negative weights satisfying triangle inequalities.

    Source: §1.1 · p. 4

Abstract

from arXiv · show

We give new rounding schemes for the standard linear programming relaxation of the correlation clustering problem, achieving approximation factors almost matching the integrality gaps: - For complete graphs our appoximation is $2.06 - \varepsilon$ for a fixed constant $\varepsilon$, which almost matches the previously known integrality gap of $2$. - For complete $k$-partite graphs our approximation is $3$. We also show a matching integrality gap. - For complete graphs with edge weights satisfying triangle inequalities and probability constraints, our approximation is $1.5$, and we show an integrality gap of $1.2$. Our results improve a long line of work on approximation algorithms for correlation clustering in complete graphs, previously culminating in a ratio of $2.5$ for the complete case by Ailon, Charikar and Newman (JACM'08). In the weighted complete case satisfying triangle inequalities and probability constraints, the same authors give a $2$-approximation; for the bipartite case, Ailon, Avigdor-Elgrabli, Liberty and van Zuylen give a $4$-approximation (SICOMP'12).

1 Introduction

Correlation clustering seeks a partition that best fits noisy pairwise similarity information; this paper develops LP-rounding schemes for complete and complete k-partite graphs.

1 Introduction

  • For missing-edge graphs, correlation clustering is equivalent to multicut, and constant-factor approximation is Unique-Games hard.Source: §1 · p. 3

1.1 Our Results

  • 2.06−ε on complete graphs nearly matches the integrality gap of 2, while the 3-approximation for complete k-partite graphs matches a gap of 3.Source: §1.1 · p. 4
  • A 1.5-approximation for weighted correlation clustering with triangle inequalities improves on Ailon et al.’s 2-approximation.The proof is computer assisted.Source: §1.1 · p. 4
  • The paper proves that its rounding framework nearly or exactly matches LP integrality gaps across the studied settings, and gives a lower bound within the framework when it does not.Source: §1.1 · p. 4

1.2 Our Methodology

  • The rounding scheme assigns edge-cut probabilities through functions of the LP solution, using different functions for positive and negative edges because the constraints behave asymmetrically.The paper also analyzes long positive and negative edges differently: long positive edges can be charged to the LP, while cutting long negative edges risks collateral damage.Source: §1.2 · p. 5

1.3 Other Related Work

  • Prior work reached a 2.5-approximation on complete graphs, a 4-approximation on complete bipartite graphs, and a 2-approximation for weighted graphs with triangle inequalities.Source: §1.3 · p. 5

1.4 Organization

  • The paper develops the rounding framework and its analysis, establishes integrality gaps and a framework lower bound, then presents derandomization and approximation proofs.Source: §1.4 · p. 6

2 Approximation Algorithm

The algorithm rounds an LP solution by iteratively forming clusters around pivots, with edge-type-specific probabilities determined by the LP. Its analysis bounds expected cost through per-triangle inequalities, yielding near-gap guarantees for complete graphs and a matching guarantee for complete k-partite graphs.

2 Approximation Algorithm

  • Each iteration chooses a random active pivot and independently forms a cluster using inclusion probabilities derived from LP distances and edge-type-specific rounding functions.The algorithm removes each formed cluster before the next iteration.Source: §2 · p. 6
  • 2.06−ε for complete graphs and 3 for complete k-partite graphs; the latter matches its integrality gap of 3, while the former nearly matches the gap of 2.The complete-graph guarantee uses a fixed ε with 0 < ε < 0.01.Source: §2 · p. 8

2.1 Analysis

  • If every vertex triple satisfies ALG(uvw) ≤ αLP(uvw), the expected total clustering cost is at most α times the LP value.The analysis charges violated constraints at each step to the LP volume removed at that step.Source: §2.1 · p. 9

2.2 Triple-Based Analysis

  • The triple-based analysis checks edge-type patterns and reduces the guarantee to tight triangle inequalities and specified corner cases.The complete-graph and complete k-partite analyses account for which triangle types can occur in each graph class.Source: §2.2 · p. 10

3 Choosing the Rounding Functions

The section derives bounds on the rounding functions from difficult triangle configurations, then selects functions that satisfy those constraints and are tractable to analyze.

3 Choosing the Rounding Functions

  • The authors choose f−(x) = x as an easy-to-analyze candidate that satisfies the (+,−,−) triangle constraint for α = 2.06.They then bound f+ using a (+,+,−) triangle with lengths (x,x,2x).Source: §3 · pp. 11–12
  • The analysis bounds f+ from below using (+,+,−) triangles and from above using (+,+,+) triangles, restricting its feasible choices.The lower bound is necessary for approximating (+,+,−) triangles well, while a large f+ affects the (+,+,+) ratio.Source: §3 · p. 12
  • For α = 2.06, the selected functions satisfy the derived constraints when a = 0.19 and b = 0.5095.The parameters were chosen computationally within the analytic bounds to minimize α.Source: §3 · p. 12

4 Pictorial Proofs

The pictorial proof plots the difference between the scaled LP and algorithm costs for tight triangle cases; positivity of the plotted polynomials establishes the theorem. An analytical proof is also supplied in the appendix.

4 Pictorial Proofs

  • For tight triangles, plots of 2.06·LP(uvw)−ALG(uvw) are positive over the possible LP weights, proving Theorem 2.The displayed cases include (+,+,+), (+,+,−), and (+,−,−) triangles.Source: §4 · p. 13, Figure 1 · p. 13, Figure 2 · p. 13
  • The appendix proves positivity for every case by using partial derivatives and root bounds in two cases, and positive-term factorizations in the other two.The paper describes this as the analytical proof of Theorem 2.Source: §4 · p. 13

5 Lower Bounds

The section establishes integrality-gap lower bounds for bipartite and weighted complete-graph cases, and limits how far the paper’s rounding-function framework can improve its approximation ratios.

5.1 Integrality Gap for Bipartite Graphs

  • For every constant δ > 0, a bipartite correlation-clustering instance has integrality gap 3 − δ; a feasible LP solution costs |E|/3, and optimum costs at least (1 − 2/d)|E|.Source: §5.1 · pp. 14–15

5.2 Integrality Gap for Complete Graphs with Triangle Inequalities

  • 6/5−δ is an integrality gap for complete graphs with triangle inequalities.The proof lower-bounds the optimum clustering cost for the constructed weight function.Source: §5.2 · pp. 15–16

5.3 Lower Bound of 2.025 for the Complete Case

  • 2.025 is a lower bound on the approximation ratio achievable by rounding functions satisfying the paper’s conditions for complete graphs.At α = 2.025, x = 0.48 forces f+(x) into (0.836, 0.987), conflicting with the upper bound below 0.833.Source: §5.3 · pp. 16–17

5.4 Lower bound of 1.5 for Weighted Triangle Inequalities

  • 1.5 is a lower bound on the approximation ratio for any monotone rounding function in the weighted triangle-inequality case.The proof rules out a better ratio by analyzing the function’s behavior around a discontinuity.Source: §5.4 · pp. 17–18

6 Weighted Case

The paper extends its rounding approach to weighted correlation clustering and gives a black-box reduction from weighted to unweighted instances. Under triangle inequalities, it obtains a deterministic 1.5-approximation.

6 Weighted Case

  • 2.06 is obtained for weighted correlation clustering by modifying the rounding rule to choose positive-edge rounding with probability λ+_uv.The analysis expresses the weighted cost as a convex combination of unweighted expressions.Source: §6 · p. 18
  • A black-box reduction transfers any α-approximation for unweighted complete graphs to an α-approximation for weighted complete graphs.It replaces each vertex with many copies, samples edges according to weights, and randomly maps original vertices back to clusters.Source: §6 · pp. 18–19

6.1 Weights Satisfying the Triangle Inequality

  • 1.5 is achieved by a deterministic polynomial-time algorithm for weighted complete graphs whose negative weights satisfy triangle inequalities.The paper reports a 2-approximation by Ailon, Charikar, and Newman for this setting.Source: §6.1 · p. 19

7 Derandomization

The paper derandomizes its rounding algorithm by fixing probabilities deterministically while preserving the approximation guarantee. Coordinate-wise convexity of the potential supports the rounding step.

7 Derandomization

  • A polynomial-time deterministic algorithm achieves approximation ratio α whenever the rounding functions satisfy Lemma 4’s conditions.The returned cost is at most α times the LP value.Source: §7 · p. 20
  • The algorithm sets each rounding probability to 0 or 1 by greedily choosing the value that maximizes the potential with other variables fixed.The potential is convex in each probability variable.Source: §7 · p. 20
  • After fixing the probabilities, the algorithm selects a pivot with nonnegative expected LP-minus-cost difference and assigns vertices deterministically.This bounds the violated constraints at each step by α times the LP volume removed, hence the total cost by αLP.Source: §7 · p. 20

8 Analysis of the k-partite case

The proof reduces the 3-approximation claim to checking each possible triangle type in a complete k-partite graph. Its case analysis verifies ALG(uvw) ≤ 3·LP(uvw) across those types.

8 Analysis of the k-partite case

  • ALG(uvw) ≤ 3·LP(uvw) is established for every triangle type possible in a complete k-partite graph.The proof reduces the claim to triangle-level bounds and concludes the case analysis with the approximation guarantee.Source: §8 · pp. 20, 23
  • The proof distinguishes seven triangle types, including configurations with one neutral edge, while triangles entirely within one partition have no cost contribution.For the seven types, the edge signs and partition memberships determine which case analysis applies.Source: §8 · p. 20
  • For (+,−,∅) triangles, the analysis checks piecewise cases and shows that 3·LP ≥ ALG.The argument uses edge-length regimes and triangle-inequality constraints; when c < 2/3, it gives separate bounds for three cases.Source: §8 · pp. 21–23
  • For (+,+,−) triangles, the case analysis verifies the 3·LP ≥ ALG bound across the considered edge-length regimes.The proof divides cases according to whether a, b, and c are below or above the 1/3 and 2/3 thresholds.Source: §8 · p. 22
  • For (+,−,−) triangles, the examined cases likewise establish 3·LP ≥ ALG.The calculations handle both a < 1/3 and the remaining regime for c < 2/3, then treat c ≥ 2/3 separately.Source: §8 · p. 22

A Analysis of the Complete Case

The complete-graph analysis uses α = 2.06 for its triangle-wise bounds. Because these bounds are not completely tight, the resulting approximation is 2.06 − ε.

A Analysis of the Complete Case

  • 2.06 − ε is achieved for complete graphs because the α = 2.06 triangle-wise analysis is not completely tight.The section checks α·LP(uvw) − ALG(uvw) ≥ 0 for possible triangle edge types and lengths.Source: A Analysis of the Complete Case · p. 25

A.1 (−, −, −) Triangles

This section establishes LP-versus-rounding cost bounds for triangles across four sign patterns, including a case-based proof that C(+,+,+) ≥ 0 when x + y = z.

(−,−,−) triangles

  • For (−,−,−) triangles, setting f−(x)=x gives LP ≥ALG for all x,y,z∈[0,1].The difference LP−ALG is a sum of nonnegative terms.Source: §A.1 · p. 25

(+,−,−) triangles

  • For (+,−,−) triangles, f+(x)≤2x on [0,1] ensures 2·LP ≥ALG; the paper’s chosen f+ satisfies this condition.The bound holds with f−(x)=x.Source: §A.2 · p. 26

(+,+,−) triangles

  • For (+,+,−) triangles, C(+,+,−)(x,y,z) ≥0 for all x,y,z∈[0,1], and the most expensive cases in [a,b] occur with equal positive-edge lengths or at a boundary.The analysis reduces candidate minima to equal positive-edge lengths or boundary cases before establishing nonnegativity.Source: §A.3 · p. 28

(+,+,+) triangles

  • For (+,+,+) triangles, C(+,+,+)(x,y,z) ≥0 throughout [0,1]^3, with results covering edges in [a,b] and cases with one edge below a.The proof establishes nonnegativity for triangles whose edge lengths all lie in [a,b] and for triangles with one edge below a and the other two in [a,b].Source: §A.4 · pp. 30–31

A.1 (−, −, −) Triangles

  • For z > b, f+(z) = 1 makes C(+,+,+) decrease as z decreases, so the worst case is z = b.This case is then covered by the remaining cases.Source: §A.4 · p. 31
  • When x, y < a, the proof applies the triangle inequality and f+(z) < 2z to show the resulting quantity is positive.Source: §A.4 · p. 31
  • For a < x ≤ y with z ≤ b, Lemma 35 applies; for x < a ≤ y with z ≤ b, Lemma 36 applies.Source: §A.4 · p. 31
Loading 1412.0681v3…