Pseudometric-Weighted Correlation Clustering via Spectral Preclustering

arXiv:2609.17403 · cs.DS · Submitted 2026-09-15 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Pseudometric-Weighted Correlation Clustering via Spectral Preclustering".

Jane: Here's the gist of the paper. Pseudometric-Weighted Correlation Clustering via Spectral Preclustering studies pseudometric-weighted correlation clustering by extending the cluster-LP framework to handle nonnegatively weighted disagreements satisfying a triangle inequality, providing a randomized polynomial-time approximation guarantee of (2 + ε)OPT.

Tom: The authors prove this by combining a spectral preclustering stage, a bounded-order relaxation, and a correlated sampling step.

Jane: Metric Preclustering via Short Random Walks The preclustering stage computes an atom partition K where the cost is O(OPT), and some optimal clustering respects every atom.

Tom: This involves computing a partition K into atoms, where the inter-atom graph G has edge weights w+(K, L) for distinct atoms.

Title and authors: Jane: So to kick things off, let's look at the title and authors of this paper, "Pseudometric-Weighted Correlation Clustering via Spectral Preclustering." It immediately signals that they are extending correlation clustering beyond the standard case.

Tom: Right, it's not just about correlation clustering anymore; they are dealing with pseudometric weights where every pair of nodes has a non-negative disagreement weight that satisfies the triangle inequality. That means we're dealing with metrics that aren't necessarily standard distances.

Lu: And this is significant because the standard analysis for correlation clustering relies on specific properties of the input metric, and they are showing how to adapt their framework when you move to these more general pseudometric settings >

Meng: So what does this mean for us in practice? Does it mean we have to change our whole pipeline just because we can't use standard distances?

Jane: Not necessarily a whole overhaul, but rather a specific extension of the cluster linear program framework. They are using spectral preclustering to handle the structure imposed by these weights before moving on to sampling.

Tom: And they are aiming for a two plus epsilon approximation guarantee, which is better than the ten over three factor we saw in previous work >

Jane: That's right, and they achieve this by carefully controlling both the total weight of admissible pairs and the weighted error in pairwise marginals during their analysis >

Lu: The spectral preclustering stage is key here because it preserves a near-optimal solution while bounding that total admissible weight by a polynomial in one over epsilon times OPT >

Meng: So they're using that structure to bound the complexity before they even get into the sampling part, which sounds like a clever way to control the search space.

Jane: Exactly; and then after that, they use correlated rounding with a randomized stopping time to sample clusters from a bounded sub-cluster relaxation >

Tom: And that's where we transition from just finding a good partition to actually constructing the final solution using that bounded sub-cluster LP >

The paper's summary: Jane: Now let's talk about the actual summary of this paper. In simple terms, they are taking the known cluster linear program approach and trying to adapt it for these more complex pseudometric weights.

Tom: They are taking the existing cluster LP framework from Cao et al., which handles unweighted correlation clustering, and extending it to handle non-uniform penalties where counting bounds aren't enough >

Lu: That's right; they point out that bounding the number of admissible pairs doesn't bound their total weight, and a small unweighted average error in pairwise marginals doesn't guarantee a small weighted objective error >

Meng: So the paper is essentially saying you need to introduce new weighted bounds specifically for both those things when dealing with these pseudometric weights >

Jane: Exactly; they then show how their spectral preclustering and sampling, combined with triangle inequality properties to charge the weighted marginal error correctly onto the admissible pairs rather than just the total input weight >

Tom: That's a powerful mechanism because it leverages the metric structure of pseudometrics to gain tighter control over errors during sampling >

Lu: The key mechanism is that they use the aggregated Ptolemy-type inequality to derive a degree-product bound and then use that to get a warm start for random walks within witness clusters >

Jane: So, this whole process is designed to ensure the final sampled solution has an objective value at most one plus epsilon times OPT >

Tom: It's basically showing that you can maintain local consistency and fixed-size identities needed for sampling while keeping the relaxation tight enough for a bounded sub-cluster LP >

The paper's improvements: Jane: So what are the specific improvements they suggest over what was there before? They are addressing the shortcomings of earlier work, especially when moving to pseudometric weights.

Tom: The main improvement is moving beyond the previous bound of ten over three for standard LP pivoting methods and giving us a two plus epsilon approximation guarantee for this weighted setting >

Lu: That means they found a way to use spectral preclustering and an aggregated Ptolemy inequality to achieve that result >

Meng: And they also introduced the idea of controlling both the total weight of admissible pairs and the weighted marginal errors separately, which is what I think we need for real-world robustness against non-uniform input weights >

Jane: So it's about making sure that our error control isn't just an approximation of what we needed, but a direct bound on what we actually need for the final objective value >

Tom: And they also showed that their fixed horizon information argument and atom-wise coverage correction produce an explicit finite support solution of the cluster LP with value at most one plus epsilon times OPT >

Jane: So essentially, they've taken the unweighted construction and made it work explicitly for these pseudometric weights with a stronger guarantee on the final solution quality >

Conclusion: Tom: Alright, to wrap up this discussion on "Pseudometric-Weighted Correlation Clustering via Spectral Preclustering." The core idea is that you use spectral preclustering and correlated sampling to build an explicit feasible cluster linear program with value at most one plus epsilon times OPT >

Jane: And the main takeaway is that they achieved a randomized polynomial time algorithm with probability at least one minus one over n, giving us the two plus epsilon approximation guarantee >

Lu: From my side, I think it's a very solid result because they managed to handle the complexity of pseudometricity by carefully bounding both weights and marginal errors separately >

Meng: For me, the most important part is that we have a concrete construction for the cluster LP solution, which moves this from theory to something that can be actually deployed >

Tom: So we're looking at a paper that gives us a robust way to handle correlation clustering even when your input weights are tricky, and it's something we should definitely keep an eye on >

Jane: That sounds like the right way to end this deep dive into this work. Thanks for joining us.

Chenglin Fan, Dahoon Lee, Euiwoong Lee

Seoul National University · New York University · University of Michigan

cs.DS

Submitted: 2026-09-15

Updated: 2026-11-09

Comments: 37 pages, 2 figures, in submission

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 77/100

The gist: Pseudometric-Weighted Correlation Clustering via Spectral Preclustering studies pseudometric-weighted correlation clustering by extending the cluster-LP framework to handle nonnegatively weighted…

Key concepts

Pseudometric Weights
These are non-negative weights assigned to every pair of data points representing their disagreement or distance. Crucially, these weights must satisfy the triangle inequality, meaning the path between any two points is no longer longer than the direct distance, which imposes a specific geometric structure on the input data.
Spectral Preclustering
This initial stage partitions the data into atoms based on graph properties derived from metric inequalities. It computes a partition where every optimal clustering respects this atom structure. This step helps reduce the problem size and provides a warm start for subsequent sampling stages by bounding inter-atom costs.
Correlated Sampling
This technique samples clusters using a randomized stopping-time method that accounts for the correlation between sampled items. The analysis shows that the triangle inequality ensures the weighted error in pairwise marginals is charged to admissible pairs, leading to tighter control over the sampling error and enabling an explicit feasible solution.
Cluster-LP Construction
The final step constructs an explicit Cluster Linear Program (LP) solution supported on a polynomial number of clusters. This is achieved by solving a bounded sub-cluster LP that maintains local consistency. The resulting cost provides a value at most (1 + ε)OPT, which is the optimal integral clustering cost.

Terminology

Summary

Pseudometric-Weighted Correlation Clustering via Spectral Preclustering studies pseudometric-weighted correlation clustering by extending the cluster-LP framework to handle nonnegatively weighted disagreements satisfying a triangle inequality, providing a randomized polynomial-time approximation guarantee of (2 + ε)OPT. p. 0

Where the paper says it

Pseudometric-Weighted Correlation Clustering via Spectral Preclustering Chenglin Fan∗ Dahoon Lee† Euiwoong Lee‡ Abstract We study pseudometric-weighted correlation clustering, where every pair of vertices carries a nonnegative disagreement weight and the weights satisfy the triangle inequality. For every fixed ε > 0, we give a randomized polynomial-time (2 + ε)-approximation, improving the previously best known factor of 10/3.

The authors prove this by combining a spectral preclustering stage, a bounded-order relaxation, and a correlated sampling step. p. 2
Where the paper says it

Correlated sampling with weighted error control. We solve a weighted bounded sub-cluster LP with local moments of order r = poly(1/ε).

Metric Preclustering via Short Random Walks

The preclustering stage computes an atom partition K where the cost is O(OPT), and some optimal clustering respects every atom. This involves computing a partition K into atoms, where the inter-atom graph G has edge weights w+(K, L) for distinct atoms. p. 1

Where the paper says it

The first condition preserves a near-optimal solution; the second is the weighted substitute for a cardinality bound on admissible pairs. Consider the positive inter-atom graph G, whose edge KL has weight w +(K, L) for distinct atoms.

The metric input is the Ptolemy-type inequality which yields w(A, B) ≤ O(1)dC(A)dC(B) after aggregation over atoms and use of the cut condition. p. 2
Where the paper says it

The metric input is the Ptolemy-type inequality w(a, b)w(c, d) ≤ 2 w(a, c)w(b, d) + w(a, d)w(b, c) , which follows for metrics from the Ptolemy property of snowflaked metrics [FS11] and extends directly to pseudometrics. After aggregation over atoms and use of the cut condition, it yields w(A, B) ≤ O(1)dC(A)dC(B) volC , volC := X K⊆C dC(K).

This leads to a degree-product bound and a warm start for random walks within witness clusters. p. 0
Where the paper says it

Our spectral preclustering preserves a near-optimal solution while bounding the total admissible weight by poly(1/ε)OPT, where OPT is the optimal clustering cost. An aggregated Ptolemy-type inequality yields a degree-product bound and a warm start for random walks within witness clusters, allowing the construction to use walks of constant length.

Correlated Sampling with Weighted Error Control

The sampling stage uses a randomized-stopping-time variant of the Raghavendra–Tan correlated-rounding method to sample one cluster. The analysis shows that the triangle inequality charges the weighted pairwise marginal error to admissible pairs rather than to the total input weight. p. 0

Where the paper says it

We sample clusters from a bounded sub-cluster relaxation using correlated rounding with a randomized stopping time. An entropy bound and the triangle inequality charge the weighted marginal error to the admissible pairs rather than to the total input weight.

This results in a bound where every selected atom other than the seed atom is admissible to it, and wuv ≤ wua + wav charges the pairwise error to admissible pairs incident to a. p. 3
Where the paper says it

For a fixed vertex, Pinsker’s inequality and the chain rule for conditional mutual information bound the residual correlation averaged over the stopping time. Conditioning on the first seed a also gives the weighted charging: every selected atom other than the seed atom is admissible to it, and wuv ≤ wua + wav charges the pairwise error to admissible pairs incident to a.

The final solution has polynomial support and value at most (1 + ε)OPT with high probability. p. 3
Where the paper says it

A separate concentration bound controls the sampled objective. The final solution has polynomial support and value at most (1 + O(ε))OPT with high probability; rescaling the accuracy parameter gives theorem 1.

p. 3
Where the paper says it

A separate concentration bound controls the sampled objective. The final solution has polynomial support and value at most (1 + O(ε))OPT with high probability; rescaling the accuracy parameter gives theorem 1.

Constructing the Cluster-LP Solution

The construction culminates in an explicit feasible cluster-LP solution supported on polynomially many clusters, with value at most (1 + ε)OPT. This is achieved by solving a bounded sub-cluster LP where the relaxation keeps local consistency and fixed-size identities needed for sampling. p. 2

Where the paper says it

We solve a weighted bounded sub-cluster LP with local moments of order r = poly(1/ε). It keeps the local consistency and fixed-size identities needed for sampling, but does not use the auxiliary cardinality restriction that relates cluster size to the number of admissible neighbors in the unweighted construction.

The objective value of this solution is shown to be at most (1 + ε)OPT. p. 1
Where the paper says it

2 (Cluster-LP construction for pseudometric weights). For every fixed ε > 0, there is a randomized polynomial-time algorithm that, given a pseudometric-weighted correlation clustering instance, returns, with probability at least 1−1/n, an explicit feasible cluster-LP solution z supported on polynomially many sets, with objective value at most (1 + ε)OPT.

Final Construction and Complexity

The complete construction runs in polynomial time, with probability at least 1 − 1/(2n), returning an explicit feasible cluster-LP solution of value at most (1 + 5ε)OPT. The running time is n poly(1/ε), which is polynomial for fixed ε. p. 0

Where the paper says it

Pseudometric-Weighted Correlation Clustering via Spectral Preclustering Chenglin Fan∗ Dahoon Lee† Euiwoong Lee‡ Abstract We study pseudometric-weighted correlation clustering, where every pair of vertices carries a nonnegative disagreement weight and the weights satisfy the triangle inequality. For every fixed ε > 0, we give a randomized polynomial-time (2 + ε)-approximation, improving the previously best known factor of 10/3.

The final approximation factor of (2 + ε/2)Lw(z) is shown to be less than or equal to 2 + ε. p. 0
Where the paper says it

Pseudometric-Weighted Correlation Clustering via Spectral Preclustering Chenglin Fan∗ Dahoon Lee† Euiwoong Lee‡ Abstract We study pseudometric-weighted correlation clustering, where every pair of vertices carries a nonnegative disagreement weight and the weights satisfy the triangle inequality. For every fixed ε > 0, we give a randomized polynomial-time (2 + ε)-approximation, improving the previously best known factor of 10/3.

Discussion on Pseudometricity

Pseudometricity enters the proof in two places, where the aggregated triangle and Ptolemy inequalities give a preclustering certificate whose total admissible weight is Oε(OPT). The triangle inequality is used a second time in the sampling analysis to charge weighted pairwise marginal error to that admissible mass. p. 0

Where the paper says it

We sample clusters from a bounded sub-cluster relaxation using correlated rounding with a randomized stopping time. An entropy bound and the triangle inequality charge the weighted marginal error to the admissible pairs rather than to the total input weight.

The fixed-horizon information argument and the atom-wise coverage correction then produce an explicit finite-support solution of the cluster LP. p. 0
Where the paper says it

An entropy bound and the triangle inequality charge the weighted marginal error to the admissible pairs rather than to the total input weight. Repeated sampling and atom-wise coverage corrections produce an explicit feasible cluster-LP solution supported on polynomially many clusters, with value at most (1 + ε)OPT.

The final factor-2 rounding uses only nonnegativity of the pair weights, so any improvement below 2 would therefore have to use additional structure at the rounding stage or replace this rounding step. p. 1
Where the paper says it

2 is the optimal integral clustering cost, not the fractional LP optimum. The cluster-based factor-2 rounding applies to nonnegative pair weights; lemma 2.

The 10/3 limitation for standard-LP pivoting does not apply to the cluster-LP relaxation used here. p. 0
Where the paper says it

Let OPT denote the minimum disagreement cost of a clustering. Fan, Lee, and Lee [FLL25] obtained a 10/3-approximation for this model and showed that this factor is tight within the standard-LP pivoting framework they analyze.

References

[AAB+26] Fateme Abbasi, Hyung-Chan An, Jaroslaw Byrka, Changyeol Lee, and Yongho Shin. Approximating (weighted) chromatic correlation clustering via cluster LP. p. 3

Where the paper says it

Cluster LPs have also been used for chromatic correlation clustering: Abbasi et al. [AAB+26] give a (2 + ε)- approximation, including a weighted model in which edge weights satisfy probability constraints.

In Approximation, Randomization, and Combinatorial Optimization. p. 0
Where the paper says it

Pseudometric-Weighted Correlation Clustering via Spectral Preclustering Chenglin Fan∗ Dahoon Lee† Euiwoong Lee‡ Abstract We study pseudometric-weighted correlation clustering, where every pair of vertices carries a nonnegative disagreement weight and the weights satisfy the triangle inequality. For every fixed ε > 0, we give a randomized polynomial-time (2 + ε)-approximation, improving the previously best known factor of 10/3.

Algorithms and Techniques, APPROX 2026, and RANDOM 2026, Boston University

[ACN08] Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: Ranking and clustering. p. 0

Where the paper says it

After rescaling ε, factor-2 rounding gives the stated approximation guarantee. 1 Introduction Correlation clustering asks for a partition that agrees with pairwise similarity and dissimilarity information.

J. ACM

[BBC04] Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. p. 0

Where the paper says it

Pseudometric-Weighted Correlation Clustering via Spectral Preclustering Chenglin Fan∗ Dahoon Lee† Euiwoong Lee‡ Abstract We study pseudometric-weighted correlation clustering, where every pair of vertices carries a nonnegative disagreement weight and the weights satisfy the triangle inequality. For every fixed ε > 0, we give a randomized polynomial-time (2 + ε)-approximation, improving the previously best known factor of 10/3.

Mach. Learn., 56(1-3):89–113, 2004

[CCL+24] Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman, and Lukas Vogl. Understanding the cluster linear program for correlation clustering. p. 0

Where the paper says it

For every fixed ε > 0, we give a randomized polynomial-time (2 + ε)-approximation, improving the previously best known factor of 10/3. Our algorithm extends the cluster-LP framework for unweighted correlation clustering to pseudometric weights.

In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024

[CCL+25] Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, David Rasmussen Lolck, Alantha Newman, Mikkel Thorup, Lukas Vogl, Shuyi Yan, and Hanwen Zhang. Solving the correlation cluster LP in sublinear time. p. 0

Where the paper says it

For every fixed ε > 0, we give a randomized polynomial-time (2 + ε)-approximation, improving the previously best known factor of 10/3. Our algorithm extends the cluster-LP framework for unweighted correlation clustering to pseudometric weights.

In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025

[CGW05] Moses Charikar, Venkatesan Guruswami, and Anthony Wirth. Clustering with qualitative information. p. 0

Where the paper says it

After rescaling ε, factor-2 rounding gives the stated approximation guarantee. 1 Introduction Correlation clustering asks for a partition that agrees with pairwise similarity and dissimilarity information.

J. Comput. Syst. Sci., 71(3):360–383, 2005

[CLLN23] Vincent Cohen-Addad, Euiwoong Lee, Shi Li, and Alantha Newman. Handling correlated rounding error via preclustering: A 1. p. 1

Where the paper says it

Preclustering must bound the total weight of admissible pairs, and the sampling argument must bound weighted pairwise marginal error. Metric preclustering via short random walks.

73-approximation for correlation clustering. p. 0
Where the paper says it

Pseudometric-Weighted Correlation Clustering via Spectral Preclustering Chenglin Fan∗ Dahoon Lee† Euiwoong Lee‡ Abstract We study pseudometric-weighted correlation clustering, where every pair of vertices carries a nonnegative disagreement weight and the weights satisfy the triangle inequality. For every fixed ε > 0, we give a randomized polynomial-time (2 + ε)-approximation, improving the previously best known factor of 10/3.

In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023

[CLN22] Vincent Cohen-Addad, Euiwoong Lee, and Alantha Newman. Correlation clustering with sherali-adams. p. 0

Where the paper says it

Pseudometric-Weighted Correlation Clustering via Spectral Preclustering Chenglin Fan∗ Dahoon Lee† Euiwoong Lee‡ Abstract We study pseudometric-weighted correlation clustering, where every pair of vertices carries a nonnegative disagreement weight and the weights satisfy the triangle inequality. For every fixed ε > 0, we give a randomized polynomial-time (2 + ε)-approximation, improving the previously best known factor of 10/3.

In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022

[CMSY15] Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, and Grigory Yaroslavtsev. Near optimal LP rounding algorithm for correlationclustering on complete and complete k-partite graphs. p. 9

Where the paper says it

The complete argument, including these cases, is given in section A. 3 A regular near-optimal clustering We next refine C ⋆ only by splitting along unions of atoms.

In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015

[DEFI06] Erik D. Demaine, Dotan Emanuel, Amos Fiat, and Nicole Immorlica. Correlation clustering in general weighted graphs. p. 0

Where the paper says it

Pseudometric-Weighted Correlation Clustering via Spectral Preclustering Chenglin Fan∗ Dahoon Lee† Euiwoong Lee‡ Abstract We study pseudometric-weighted correlation clustering, where every pair of vertices carries a nonnegative disagreement weight and the weights satisfy the triangle inequality. For every fixed ε > 0, we give a randomized polynomial-time (2 + ε)-approximation, improving the previously best known factor of 10/3.

Theor. Comput. Sci., 361(2-3):172–187, 2006

[FLL25] Chenglin Fan, Dahoon Lee, and Euiwoong Lee. Improved approximation algorithms for chromatic and pseudometric-weighted correlation clustering. p. 3

Where the paper says it

Cluster LPs have also been used for chromatic correlation clustering: Abbasi et al. [AAB+26] give a (2 + ε)- approximation, including a weighted model in which edge weights satisfy probability constraints.

In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2025, NeurIPS 2025

[FS11] Thomas Foertsch and Viktor Schroeder. Hyperbolicity, CAT(-1)-spaces and the ptolemy inequality. p. 0

Where the paper says it

Our spectral preclustering preserves a near-optimal solution while bounding the total admissible weight by poly(1/ε)OPT, where OPT is the optimal clustering cost. An aggregated Ptolemy-type inequality yields a degree-product bound and a warm start for random walks within witness clusters, allowing the construction to use walks of constant length.

Mathematische Annalen, 350:339–356, 2011

[GS26] David Garc´ıa-Soriano and Antoine Schohn. Approximate dual separation for the cluster LP: a 1. p. 3

Where the paper says it

Related developments. Subsequent work has accelerated the unweighted cluster-LP construction [CCL+25] and obtained approximate dual separation and improved rounding [GS26].

387 approximation for correlation clustering. p. 0
Where the paper says it

Pseudometric-Weighted Correlation Clustering via Spectral Preclustering Chenglin Fan∗ Dahoon Lee† Euiwoong Lee‡ Abstract We study pseudometric-weighted correlation clustering, where every pair of vertices carries a nonnegative disagreement weight and the weights satisfy the triangle inequality. For every fixed ε > 0, we give a randomized polynomial-time (2 + ε)-approximation, improving the previously best known factor of 10/3.

CoRR, abs/2607.27829, 2026

[RT12] Prasad Raghavendra and Ning Tan. Approximating csps with global cardinality constraints using SDP hierarchies. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

--- Page 1 ---

Pseudometric-Weighted Correlation Clustering via Spectral Preclustering Chenglin Fan Dahoon Lee Euiwoong Lee Abstract We study pseudometric-weighted correlation clustering, where every pair of vertices carries a nonnegative disagreement weight and the weights satisfy the triangle inequality. For every fixed ε > 0, we give a randomized polynomial-time (2 + ε)-approximation, improving the previously best known factor of 10/3. p. 0

Where the paper says it

Pseudometric-Weighted Correlation Clustering via Spectral Preclustering Chenglin Fan∗ Dahoon Lee† Euiwoong Lee‡ Abstract We study pseudometric-weighted correlation clustering, where every pair of vertices carries a nonnegative disagreement weight and the weights satisfy the triangle inequality. For every fixed ε > 0, we give a randomized polynomial-time (2 + ε)-approximation, improving the previously best known factor of 10/3.

The weighted setting requires controlling both the total weight of admissible pairs and the weighted error in pairwise marginals. p. 0
Where the paper says it

Our algorithm extends the cluster-LP framework for unweighted correlation clustering to pseudometric weights. The weighted setting requires controlling both the total weight of admissible pairs and the weighted error in pairwise marginals.

Our spectral preclustering preserves a near-optimal solution while bounding the total admissible weight by poly(1/ε)OPT, where OPT is the optimal clustering cost. p. 0
Where the paper says it

The weighted setting requires controlling both the total weight of admissible pairs and the weighted error in pairwise marginals. Our spectral preclustering preserves a near-optimal solution while bounding the total admissible weight by poly(1/ε)OPT, where OPT is the optimal clustering cost.

An aggregated Ptolemy-type inequality yields a degree-product bound and a warm start for random walks within witness clusters, allowing the construction to use walks of constant length. p. 0
Where the paper says it

Our spectral preclustering preserves a near-optimal solution while bounding the total admissible weight by poly(1/ε)OPT, where OPT is the optimal clustering cost. An aggregated Ptolemy-type inequality yields a degree-product bound and a warm start for random walks within witness clusters, allowing the construction to use walks of constant length.

We sample clusters from a bounded sub-cluster relaxation using correlated rounding with a randomized stopping time. p. 0
Where the paper says it

An aggregated Ptolemy-type inequality yields a degree-product bound and a warm start for random walks within witness clusters, allowing the construction to use walks of constant length. We sample clusters from a bounded sub-cluster relaxation using correlated rounding with a randomized stopping time.

An entropy bound and the triangle inequality charge the weighted marginal error to the admissible pairs rather than to the total input weight. p. 0
Where the paper says it

We sample clusters from a bounded sub-cluster relaxation using correlated rounding with a randomized stopping time. An entropy bound and the triangle inequality charge the weighted marginal error to the admissible pairs rather than to the total input weight.

Repeated sampling and atom-wise coverage corrections produce an explicit feasible cluster-LP solution supported on polynomially many clusters, with value at most (1 + ε)OPT. p. 0
Where the paper says it

An entropy bound and the triangle inequality charge the weighted marginal error to the admissible pairs rather than to the total input weight. Repeated sampling and atom-wise coverage corrections produce an explicit feasible cluster-LP solution supported on polynomially many clusters, with value at most (1 + ε)OPT.

p. 0
Where the paper says it

An entropy bound and the triangle inequality charge the weighted marginal error to the admissible pairs rather than to the total input weight. Repeated sampling and atom-wise coverage corrections produce an explicit feasible cluster-LP solution supported on polynomially many clusters, with value at most (1 + ε)OPT.

After rescaling ε, factor-2 rounding gives the stated approximation guarantee. p. 0
Where the paper says it

Repeated sampling and atom-wise coverage corrections produce an explicit feasible cluster-LP solution supported on polynomially many clusters, with value at most (1 + ε)OPT. After rescaling ε, factor-2 rounding gives the stated approximation guarantee.

--- Page 2 ---

The cluster-LP approach Cao et al. [CCL+24] introduced the cluster LP, with one variable for each possible cluster, and gave a polynomial-time construction for the unweighted problem. p. 1

Where the paper says it

The cluster-LP approach. [CCL+24] introduced the cluster LP, with one variable for each possible cluster, and gave a polynomial-time construction for the unweighted problem.

For every fixed ε > 0, their algorithm returns an explicit feasible solution of value at most (1 + ε)OPT, where the benchmark is the optimal integral clustering rather than the fractional LP optimum. p. 1
Where the paper says it

[CCL+24] introduced the cluster LP, with one variable for each possible cluster, and gave a polynomial-time construction for the unweighted problem. For every fixed ε > 0, their algorithm returns an explicit feasible solution of value at most (1 + ε)OPT, where the benchmark is the optimal integral clustering rather than the fractional LP optimum.

We ask whether the same construction can be carried out for pseudometric weights. p. 1
Where the paper says it

For every fixed ε > 0, their algorithm returns an explicit feasible solution of value at most (1 + ε)OPT, where the benchmark is the optimal integral clustering rather than the fractional LP optimum. We ask whether the same construction can be carried out for pseudometric weights.

With nonuniform penalties, the counting bounds used in the unweighted analysis are not enough. p. 1
Where the paper says it

We ask whether the same construction can be carried out for pseudometric weights. With nonuniform penalties, the counting bounds used in the unweighted analysis are not enough.

Bounding the number of admissible pairs does not bound their total weight, and a small unweighted average error in pairwise marginals need not give a small weighted objective error. p. 1
Where the paper says it

With nonuniform penalties, the counting bounds used in the unweighted analysis are not enough. Bounding the number of admissible pairs does not bound their total weight, and a small unweighted average error in pairwise marginals need not give a small weighted objective error.

We therefore need weighted bounds both for the admissible pairs and for the marginal errors produced by the sampling step. p. 1
Where the paper says it

Nor is an additive error proportional to the total input weight useful, since the latter can be arbitrarily larger than OPT. We therefore need weighted bounds both for the admissible pairs and for the marginal errors produced by the sampling step.

--- Page 3 ---

Our results are as follows. Theorem 1.1 (Main approximation theorem). p. 1

Where the paper says it

1 Our results Our main result is the following approximation guarantee. 1 (Main approximation theorem).

For every fixed ε > 0, there is a randomized polynomial-time algorithm for pseudometric-weighted correlation clustering that, with probability at least 1 − 1/n, returns a clustering of cost at most (2 + ε)OPT. p. 1
Where the paper says it

1 (Main approximation theorem). For every fixed ε > 0, there is a randomized polynomial-time algorithm for pseudometric-weighted correlation clustering that, with probability at least 1 − 1/n, returns a clustering of cost at most (2 + ε)OPT.

We obtain this guarantee by extending the cluster-LP construction of Cao et al. p. 1
Where the paper says it

For every fixed ε > 0, there is a randomized polynomial-time algorithm for pseudometric-weighted correlation clustering that, with probability at least 1 − 1/n, returns a clustering of cost at most (2 + ε)OPT. We obtain this guarantee by extending the cluster-LP construction of Cao et al.

[CCL+24] to pseudometric weights. p. 1
Where the paper says it

We obtain this guarantee by extending the cluster-LP construction of Cao et al. [CCL+24] to pseudometric weights.

Theorem 1.2 (Cluster-LP construction for pseudometric weights)

For every fixed ε > 0, there is a randomized polynomial-time algorithm that, given a pseudometric-weighted correlation clustering instance, returns, with probability at least 1−1/n, an explicit feasible cluster-LP solution z supported on polynomially many sets, with objective value at most (1 + ε)OPT. The benchmark in theorem 1. p. 1

Where the paper says it

For every fixed ε > 0, there is a randomized polynomial-time algorithm that, given a pseudometric-weighted correlation clustering instance, returns, with probability at least 1−1/n, an explicit feasible cluster-LP solution z supported on polynomially many sets, with objective value at most (1 + ε)OPT. The benchmark in theorem 1.

2 is the optimal integral clustering cost, not the fractional LP optimum. p. 1
Where the paper says it

The benchmark in theorem 1. 2 is the optimal integral clustering cost, not the fractional LP optimum.

Technical Overview

The construction follows the same three stages as in the unweighted case: preclustering, a boundedorder relaxation, and sampling. The weighted analysis changes the estimates used in the first and third stages. p. 1

Where the paper says it

2 Technical overview The construction follows the same three stages as in the unweighted case: preclustering, a boundedorder relaxation, and sampling. The weighted analysis changes the estimates used in the first and third stages.

Preclustering must bound the total weight of admissible pairs, and the sampling argument must bound weighted pairwise marginal error. p. 1
Where the paper says it

The weighted analysis changes the estimates used in the first and third stages. Preclustering must bound the total weight of admissible pairs, and the sampling argument must bound weighted pairwise marginal error.

The first condition preserves a near-optimal solution; the second is the weighted substitute for a cardinality bound on admissible pairs. The metric input is the Ptolemy-type inequality which yields w(A, B) ≤ O(1)dC(A)dC(B). p. 2

Where the paper says it

The metric input is the Ptolemy-type inequality w(a, b)w(c, d) ≤ 2 w(a, c)w(b, d) + w(a, d)w(b, c) , which follows for metrics from the Ptolemy property of snowflaked metrics [FS11] and extends directly to pseudometrics. After aggregation over atoms and use of the cut condition, it yields w(A, B) ≤ O(1)dC(A)dC(B) volC , volC := X K⊆C dC(K).

After aggregation over atoms and use of the cut condition, it yields w(A, B) ≤ O(1)dC(A)dC(B), and the cut condition also gives constant conductance for G[C]. p. 2
Where the paper says it

After aggregation over atoms and use of the cut condition, it yields w(A, B) ≤ O(1)dC(A)dC(B) volC , volC := X K⊆C dC(K). The cut condition also gives constant conductance for G[C].

This leads to a warm start bound where PC(A, B) ≤ O(1)πC(B). p. 2
Where the paper says it

The displayed bound implies PC(A, B) ≤ O(1)πC(B) for distinct atoms A, B ⊆ C. Thus, after one non-lazy step, the walk has a constant warm start even when the starting atom has very small stationary mass.

The entropy bound and the triangle inequality charge the weighted marginal error to the admissible pairs rather than to the total input weight. Repeated sampling and atom-wise coverage corrections produce an explicit feasible cluster-LP solution supported on polynomially many clusters, with value at most (1 + ε)OPT. The final solution has polynomial support and value at most (1 + ε)OPT with high probability.

Where the gains come from

The total admissible-pair weight is poly(1/ε)OPT, which is controlled by Rε = max (1, α, 128α / (2α ε / t0 + 1))OPT. This bound ensures that w(Eadm) ≤ RεOPT and Rε = poly(1/ε). p. 1

Where the paper says it

Starting from an atom-respecting optimum, we obtain a regular near-optimal witness and a computable set Eadm such that every inter-atom pair co-clustered by the witness is admissible and w(Eadm) ≤ poly(1/ε)OPT. The first condition preserves a near-optimal solution; the second is the weighted substitute for a cardinality bound on admissible pairs.

The choice of r:= 2 + ln 2 R squared / ε squared is made to ensure the correlation error proved below is at most εOPT/y∅. p. 3
Where the paper says it

Writing yuv for the aggregate pair moment and y∅ for the total cluster mass, the sampled cluster C satisfies X uv∈( V 2 ) wuv P[u, v ∈ C] − yuv y∅ ≤ O w(Eadm) y∅ √ r . Our choice of r makes the right-hand side at most εOPT/y∅ .

This choice ensures that the correlation error proved below is at most εOPT/y∅. p. 3
Where the paper says it

Writing yuv for the aggregate pair moment and y∅ for the total cluster mass, the sampled cluster C satisfies X uv∈( V 2 ) wuv P[u, v ∈ C] − yuv y∅ ≤ O w(Eadm) y∅ √ r . Our choice of r makes the right-hand side at most εOPT/y∅ .

The Bounded Sub-Cluster LP

The bounded sub-cluster LP is formulated with variables y s S and constraints that ensure local consistency, and its optimum value is at most (1 + ε)OPT. The final objective value of the sampled cluster satisfies E[cost(C)] ≤ (1 + 2ε)OPT/y∅. p. 3

Where the paper says it

A separate concentration bound controls the sampled objective. The final solution has polynomial support and value at most (1 + O(ε))OPT with high probability; rescaling the accuracy parameter gives theorem 1.

This is achieved by combining the local consistency and admissibility constraints with the sampling results. p. 2
Where the paper says it

We solve a weighted bounded sub-cluster LP with local moments of order r = poly(1/ε). It keeps the local consistency and fixed-size identities needed for sampling, but does not use the auxiliary cardinality restriction that relates cluster size to the number of admissible neighbors in the unweighted construction.

The final cost-failure probability is at most 1/(4n). p. 6
Where the paper says it

For L > 0, Markov’s inequality shows that a single rounding has probability at least η/(2 + η) of having cost at most (2 + η)L. Repeating independently O(η −1 log n) times and returning the cheapest clustering makes the failure probability an arbitrarily small inverse polynomial in n.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Precision in clustering with pseudometric weights: The system can now solve correlation clustering problems where pair disagreements are defined by a metric that satisfies the triangle inequality, improving upon previous bounds of 10/3 for standard LP pivoting methods.

  2. Enhanced feasibility guarantee for fractional solutions: The algorithm can return an explicit feasible cluster LP solution with a value at most (1 + epsilon)OPT, which is the optimal integral clustering cost benchmark, rather than just the fractional LP optimum.

  3. Improved approximation ratio through spectral preclustering: By using spectral preclustering and an aggregated Ptolemy-type inequality, the system achieves a (2 + epsilon) OPT approximation guarantee with high probability, exceeding previous best known factors of 10/3.

  4. Robustness to input weight variations: The analysis shows that the weighted marginal error is charged to admissible pairs rather than the total input weight, allowing for tighter control over errors even when weights are non-uniform.

  5. Polynomial time solution construction: The complete construction runs in polynomial time for fixed epsilon, enabling practical application of these sophisticated clustering techniques on large datasets with high success probability (at least 1 - 1/(2n)).

Abstract

We study pseudometric-weighted correlation clustering, in which pairs have arbitrary positive or negative labels and nonnegative disagreement weights satisfying the triangle inequality. For every fixed epsilon>0, we give a randomized polynomial-time (2+ epsilon) -approximation, improving the previous factor of 10/3. The algorithm constructs an explicit feasible solution to the cluster LP with polynomial support and value at most (1+ epsilon) OPT, where OPT is the minimum integral clustering cost. Our main contribution is a weighted preclustering construction that witnesses a near-optimal clustering while bounding the total weight of admissible edges by poly(1/epsilon) OPT. We obtain admissibility certificates from random walks, where the factor-two Ptolemy's inequality for pseudometrics reduces the required length of walks from O(n) to a constant. We then bound the rounding error separately at each vertex and use the triangle inequality to control its weighted cost. Sampling and coverage corrections produce an exactly feasible solution, and the factor-two rounding completes the approximation algorithm.

Sources

Related papers