acceptodds
Under review as a conference paper at ICLR 2027

Universal 2.030-Rounding for Multilayer Correlation Clustering with Probability Weights

Abstract

Multilayer correlation clustering seeks one partition for conflicting preferences across layers. For probability weights, where joining and separating each pair have costs summing to one, we establish universal -rounding. Specifically, any explicit feasible rational cluster-LP cover can be rounded deterministically to one partition costing at most times the cover's fractional cost for all probability-weight vectors simultaneously, including those not supplied to the algorithm. We achieve this through a single auxiliary objective and potential, conditional variance bounds, and computer-assisted verification using an exact rational certificate. Consequently, combining this rounding with scalar fractional optimization and averaging yields a randomized -approximation for each fixed objective, , with a factor independent of the number of layers. Together with a two-vertex lower bound, the rounding theorem places the worst-layer cluster-relaxation gap in .

Primary area:
optimization
Keywords:
multilayer correlation clustering, probability weights, approximation algorithms, computer-assisted proofs.

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_v345OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies multilayer correlation clustering with probability weights, where joining and separating each pair on each layer have costs summing to one. The main result is a deterministic rounding procedure for the cluster LP: given any feasible fractional cover, it outputs a single partition whose cost is at most 2.030 times the fractional cost for every probability-weight vector simultaneously, including weight vectors not given to the algorithm. Combined with an existing fractional solver and an averaging scheme, this yields a randomized (2.030+ε)(2.030+\varepsilon)-approximation for each fixed ℓp\ell_p objective, with no dependence on the number of layers. The key local inequality is proved by computer-assisted exact rational verification, and the paper also shows that the integrality gap of the worst-layer cluster relaxation lies in [2,2.030][2,2.030]. The contribution is primarily theoretical, without an empirical evaluation on real-world datasets.

Critical strengths

S1. Improved theoretical guarantees. For probability-weighted multilayer correlation clustering, the paper improves the best known factor for fixed ℓp\ell_p objectives from 4 (Miyauchi et al., 2026), or 3.3865+ε3.3865+\varepsilon by combining existing results, to 2.030+ε2.030+\varepsilon. The factor of 2.030 is particularly interesting given the lower bound of 2 that the paper proves for the integrality gap of the worst-layer relaxation.

S2. Interesting theoretical approach. The universal rounding formulation is a valuable contribution, providing simultaneous guarantees for all probability-weighted objectives. This separates rounding from the construction of the fractional cover, so a single procedure serves every ℓp\ell_p objective. The combination of an auxiliary objective, potential-based rounding, and conditional variance analysis provides an interesting approach to handling conflicting preferences across multiple layers.

Critical weaknesses

W1. Lack of empirical evaluation. Although the theoretical improvement is significant, the paper does not provide an empirical comparison with existing methods. In particular, Miyauchi et al. (2026) evaluate their algorithms on real-world datasets, including the probability-constrained setting, considering both solution quality and computational efficiency. Given that the proposed method improves upon their theoretical guarantees, I would have expected a comparison in terms of effectiveness and running time. This is especially relevant because the proposed approach appears computationally demanding, and a better worst-case guarantee does not necessarily translate into better practical performance. While I acknowledge that the contribution is primarily theoretical, even a small-scale empirical evaluation would help clarify the practical significance of the proposed improvement.

W2. Limited intuition behind the technical construction. Although the theoretical analysis is detailed, the motivation behind several key design choices is not sufficiently explained. In particular, the candidate distribution (Table 2), the variance functions (Table 3), and constants such as λ=39/4\lambda=39/4 and the 4/54/5 cutoff are introduced without much discussion of how they were selected or which properties are essential to the analysis. The paper describes its contribution as an adaptation of existing cluster-LP rounding techniques to a universal auxiliary objective, but as a non-specialist I found it difficult to understand why these specific adaptations are the right ones, and how much of the novelty lies in the construction versus the parameter search. Providing more intuition about these choices would help clarify the novelty and significance of the contribution.

Questions for authors

Q1. Could the authors provide an empirical comparison with Miyauchi et al. (2026), particularly regarding clustering objective values and computational efficiency? Even a small-scale evaluation would help clarify whether the improved approximation guarantee translates into practical benefits.

Q2. Could the authors elaborate on how the candidate distribution, variance functions, and numerical constants were derived? In particular, which elements are essential for achieving the 2.030 guarantee, and how do they differ from existing cluster-LP rounding techniques?

Q3. Scope and future directions (not affecting my assessment). Miyauchi et al. (2026) also study the general multilayer problem without the probability constraint, obtaining an O(L log n)-approximation. The paper restricts attention to probability weights and does not discuss this general case. Could parts of the approach, in particular the common-cover construction, whose factor does not depend on the number of layers, help remove the dependence on L in the general setting? Similarly, could the approach extend to intermediate settings such as global weight bounds [n1]?

[n1] Correlation Clustering with Global Weight Bounds. ECML-PKDD 2021.

2 comments
AuthorsOpenReview ↗

Response to reviewer eW6a

The requested comparison is now in Table 4 (p. 10), using exact worst-layer integer OPT on all 150 instances: 120 synthetic and 30 subsets of one public two-layer sparrow network, with 6, 8, or 10 vertices.

MethodMean cost/OPTTheoretical factor
Ours1.0322.030
Metric-LP Miyauchi, 20 attempts1.0334
Same-cover Miyauchi, 20 attempts1.0264
Mean-layer aggregation, 20 attempts1.1034L

We test that guarantee separately in Appendix E.5 (p. 38): freeze the restarted outputs, then construct layers maximizing their cover-relative excess. Five of 150 violate 2.0302.030; ours satisfy the bound throughout.

Appendix E.6 (p. 39) also executes averaging and rounding on 18 pre-specified conflicting-layer inputs. It uses an exponential exact oracle. This checks the workflow, while retaining the baseline's better mean quality.

W2 / Q2: Design intuition and parameter selection.

Equation (4) sets the universal target KK. The support budget can exceed it, so we add pivot candidates with a complementary budget. Each family pays for a cluster by its own budget decrease. The minimum of the total budgets is at most the target and pays selected clusters when budgets switch (Section 3).

Our shared threshold couples neighbor inclusions without layer signs; Garcia-Soriano and Schohn use sign-dependent, conditionally independent additions. Section 1's two-vertex example at distance 3/103/10 makes Miyauchi split in either order, whereas ours joins. Pivot restarts cannot change this supplied-cover example.

Section 4.3 separates candidate geometry, ρ,λ\rho,\lambda scoring, and proof weights. The 4/54/5 cutoff excludes distant additions. Any positive λ\lambda gives complementarity; 39/439/4 also permits the local pivot bound. With modes positive and candidates fixed, changing mode probabilities or variance functions leaves the deterministic output unchanged, although the certificate may fail. The covariance example explains compensation. Joint search and rationalization produced the unchanged constants; exact verification proves sufficiency.

Q3: Unrestricted weights and global weight bounds.

Appendix F (p. 40) gives a supplied-cover extension under Mandaglio et al.'s global weight condition. Normalization makes each nonzero layer's fractional and integral costs the same positive multiple of probability-layer costs, so the same partition retains factor 2.0302.030 in every layer and every monotone norm.

For unrestricted pair weights, varying pair totals obstruct Equation (4)'s common auxiliary target; removing layer-count dependence remains open (Section 7).

I thank the authors for the detailed response and the revisions.

W2 is mostly addressed by improving the presentation of the paper, but my major concern, W1, still remains. I appreciate the new comparison (Table 4) and the authors' transparency about its limits. However, it confirms my concern about practical significance. In Table 4, the proposed method does not improve solution quality over restarted Miyauchi rounding: its mean cost/OPT (1.032) is on par with metric-LP Miyauchi (1.033) and slightly worse than same-cover Miyauchi (1.026), which also attains a lower maximum ratio (1.286 vs. 1.308). At the same time, its rounding is about seven times slower (1.779 ms vs. 0.259 and 0.275 ms, excluding LP solution). Moreover, these instances are very small (n ≤ 10), far from the real-world datasets used by Miyauchi et al. (2026). Overall, the improved worst-case guarantee does not translate into practical benefits in the reported experiments, while incurring a higher computational cost.

I acknowledge that the contribution is primarily theoretical, and I did not expect an extensive experimental evaluation. However, as noted in my review, even a small-scale evaluation should help clarify whether the improved guarantee yields practical benefits. The reported comparison does not show such benefits, and the paper does not clarify in which settings they could be expected. For this reason, I maintain my original assessment of this paper.

Reviewer_eW6aOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper gives a randomized 2.03-factor approximation for Multilayer Correlation Clustering with probability weights. The problem consists of finding a partition of objects (that is, vertices of a multilayer graph) which minimizes the cost of disagreements over L layers. The cost depends on whether a vertex pair is contained in a common cluster or not and is based on weights summing to one (reflecting probabilities). The problem is well-known in the single-layer case and many recent results gave improved approximation factors. The multilayer version has recently been introduced and an approximation factor of 4 and 3.3865 have been shown. The paper achieves a factor of 2.03 essentially by rounding a given LP-based fractional cluster cover, a strategy that has been used previously in the literature to achieve approximation algorithms. The result is poorly presented and I could not follow the proofs and techniques. It is overly technical and does not provide good intuition and explanation of the underlying ideas (one key lemma is a purely computer-assisted calculation). I believe a reader who does not already know the problem and the details of the existing techniques cannot really understand much of this paper.

Critical strengths

The paper gives an improved approximation factor for a relevant problem.

Critical weaknesses

The results are not well presented and seem to be very technical and based on choosing very specific numbers. I could not verify the correctness and I could also not identify any interesting new algorithmic high-level ideas. It seems like the paper is merely tweaking existing techniques to obtain some improvement.

Questions for authors

What is the key idea underlying your improvement? Are there any insights which could be applied to other problems?

2 comments
AuthorsOpenReview ↗

Response to reviewer eW6a

Q1 / novelty: What is the key idea behind the improvement? 

One partition must work for every probability-weighted layer. Maximizing excess over those weights gives one target Db(C)≤KD_b(C)\le K (Section 3). 

The support-family total can be K+Δ>KK+\Delta > K. We construct a pivot family with total K−λΔK-\lambda\Delta, so 

min⁡K+Δ,K−λΔ≤K(λ>0).\min\\{K+\Delta,K-\lambda\Delta\\}\le K\qquad(\lambda > 0).

 Each family provides a cluster paid for by its own budget decrease. Choosing the cluster for the smaller total makes that minimum a decreasing potential, including when the smaller budget changes. Summing proves the guarantee. This is the construction before tuning constants.

 The pivot family shares a threshold without layer signs, changing joint inclusion probabilities. We build on Cao et al. and Garcia-Soriano and Schohn's budget/variance framework. The two-vertex example (Section 1) shows why restarting Miyauchi's rule alone cannot ensure universal 2.0302.030.

 Numerical parameters: What motivates the specific choices?

 Section 4.3 (pp. 7-8) separates three roles: radii, intervals, and the cutoff define candidates; ρ,λ\rho,\lambda define scores; mode probabilities and variance functions support the existence proof. With listed modes positive and candidate sets fixed, changing proof weights leaves the deterministic output unchanged, although its certificate may fail.

 Any positive λ\lambda gives budget complementarity. Choosing 39/439/4 additionally makes the pivot inequality feasible with the listed candidates and variance weights. Threshold mixing controls joint inclusion near 1/21/2; the 4/54/5 cutoff excludes distant set members. Section 4.2's covariance −1/4-1/4 example explains how variance compensation helps.

 The unchanged rational values are fixed across inputs and layer counts. The supplementary parameter-selection note records their joint numerical search and rationalization. Exact full-domain verification certifies joint sufficiency.

 Correctness: How can the proof be checked?

 The revised proof separates hand-checkable reductions from one computer-assisted lemma.

 Equation (4) makes the universal guarantee equivalent to Db(C)≤KD_b(C)\le K. Section 3 exhibits the support-budget limitation explicitly: E(11/25)=3953/7500>103/200=k(11/25)E(11/25)=3953/7500 > 103/200=k(11/25). Complementary budget totals nevertheless have minimum at most the target. The support average (7) supplies a candidate for EE; the variance identity (10) and Lemma 5 supply one for BB. Equation (6) then pays each chosen cluster through the potential decrease, including when budgets switch. Summing proves Theorem 1.

 Only Lemma 5 is computer-assisted. Affineness reduces triple membership to two endpoints; positive-denominator clearing gives polynomials; nonpositive coefficients certify entire tetrahedra. Exact subdivision coverage and boundary checks establish the continuous domain (Section 4.4; Appendix C.1, pp. 15-17).

 Both main theorems inherit that dependence. Appendix C.2 separates finite implementation checks from the continuous proof. The separate symbolic calculation verifies 19 selected polynomials.

 Presentation: How has the exposition changed? 

The first page now gives the two-vertex restart obstruction. Section 3 (pp. 4-5) explains the target KK, a concrete support-budget overshoot, complementary candidate families, and their minimum-total potential before fixing λ\lambda. Section 4.2 explains covariance compensation through a three-vertex example; Sections 4.3-4.4 then explain parameter roles and exact verification. 

This provides a reading route from the requirement to the construction and its proof. Lemma reference names are corrected, the variance table is in the main text, and setup instructions are in the supplementary README. The main text remains 10 pages. Section 6 distinguishes ordinary-instance performance, constructed universal stress, and executed averaging on conflicting layers. 

Q2: Which insights could apply to other problems? 

Two principles can transfer. Maximizing rounding excess over independently varying pair weights can expose one auxiliary objective and an explicit target for simultaneous guarantees. If each candidate family admits a cluster paid for by its own budget decrease, and the minimum of their total budgets is at most the target, that minimum can serve as one potential even when the smaller total changes. 

Appendix F (p. 40) provides a concrete supplied-cover extension under Mandaglio et al.'s global weight condition. Each nonzero layer cost becomes a positive multiple of a probability-layer cost, so the same partition retains factor 2.0302.030 simultaneously in all such layers.

I checked the response of the authors. I acknowledge that they tried to improve the presentation. The result might be nice from a theoretical point of view but it seems limited in practice. I raise my score to weak reject, but given that the paper is still very technical and mostly based on tweaking existing ideas, I do not think this is enough for acceptance.

Reviewer_VnDvOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The authors propose a deterministic rounding algorithm that converts an explicit feasible rational cluster-LP cover into one partition satisfying a 2.0302.030 bound against every probability-weight objective simultaneously. Combining this result with a norm-specific fractional-cover construction yields a randomized (2.030+ε)(2.030+\varepsilon)-approximation for each fixed ℓp\ell_p objective.

Critical strengths
  • The paper provides a meaningful theoretical improvement for general multilayer objectives. Table 1 compares the proposed (2.030+ε)(2.030+\varepsilon) guarantee with the previously obtainable 3.3865+ε3.3865+\varepsilon bound, with no dependence of the approximation factor on the number of layers.

  • The universal rounding guarantee controls one realized partition across all probability-weighted objectives relative to the supplied cover. This addresses an important limitation of separate layerwise expectation bounds.

  • The auxiliary-objective reformulation and two-budget potential provide a coherent framework. The paper also separates universal rounding from norm-specific optimization and documents the scope and reproduction procedure of its computer-assisted proof.

Critical weaknesses
  • Practical scalability remains unclear. Appendix B reports O(n5s)O(n^5s) rational operations for explicit rounding, where ss is the cover support size, while the complete algorithm requires repeated fractional optimization.
  • Appendices G.3–G.5 provide useful reproducibility details, but the presentation is overly focused on code modules and revision-specific information. Low-level setup and import details could be moved to the supplementary README.
  • Appendix G.5 provides implementation consistency checks, but not comparative clustering results.
Questions for authors

see weaknesses.

  • Could the authors compare clustering quality and runtime with the multilayer method of Miyauchi et al. and a layer-aggregation baseline, using the same objectives?
2 comments
AuthorsOpenReview ↗

Response to reviewer VnDv

W1: Practical scalability and repeated fractional optimization.

Practical scalability remains open. We have made the costs explicit and separated a full averaging demonstration from supplied-cover rounding profiles.

With ss cover supports, rounding takes O(n5s)O(n^5s) rational operations. Averaging TT responses gives at most ∑jσj\sum_j\sigma_j supports, where σj\sigma_j is the support count of response jj. For maximum layer cost, T=O(1+mlog⁡(2L)/η2)T=O(1+m\log(2L)/\eta^2), with m=(n2)m=\binom n2. Scalar solves, layer-cost evaluation, and encoding costs are additional (Appendices A.2/B.2). The approximation factor, rather than runtime, is independent of LL.

Appendix E.6 (p. 39) executes scalar optimization, averaging, and rounding on 18 fixed conflicting-layer inputs with 4–6 vertices. One pass uses 624,960 scalar responses; mean total times at n=4,5,6n=4,5,6 are 94.3394.33, 498.97498.97, and 2886.192886.19 ms. An independent checker replays every decision. This demonstration uses an exponential partition-enumeration oracle.

Appendix E.4 separately profiles 36 supplied covers. At n=60n=60, rounding time increases from 69.3569.35 ms with six supports to 2762.272762.27 ms with 30. These profiles exclude cover construction.

W2: Code and setup details in the submitted Appendices G.3-G.5.

We moved setup commands, file maps, and import details to the supplementary README. The reorganized Appendix C.1 (pp. 15-17) presents the mathematical verification of Lemma 5: reduction to endpoint polynomials, coefficient signs over entire tetrahedra, subdivision coverage, and boundary values. Appendix C.2 (p. 17) separates this continuous-domain argument from finite implementation checks.

We also corrected automatic references that displayed lemmas as theorems. The mathematical proof remains in the manuscript; reproduction commands are in the supplement. The six appendix topics separate rounding, fractional optimization, exact verification, analytic bounds, experiments, and weight extensions.

W3 / question: Comparison with Miyauchi and layer aggregation.

Table 4 (p. 10) directly compares maximum-layer disagreement against exact integer OPT on all 150 instances: 120 synthetic and 30 subsets of one public two-layer sparrow network, with 6, 8, or 10 vertices. Baselines include 20 pivot attempts. Our mean-layer LP + pivot control differs from Aggregate-Pr.

For ours, metric-LP Miyauchi, same-cover Miyauchi, and aggregation, mean cost/OPT is 1.0321.032, 1.0331.033, 1.0261.026, and 1.1031.103.

Our theoretical advantage is universal factor 2.0302.030 versus four. Section 1's two-vertex example shows why restarting the fixed Miyauchi rule alone cannot ensure it. Appendix E.5 (p. 38) tests this separately: five of 150 fixed restarted outputs violate 2.0302.030 on constructed layers relative to their cover; ours satisfy it throughout. Appendices E.1-E.3 retain the original end-to-end timings and full protocols.

Thank you for your response and revisions. I appreciate the paper's theoretical contributions, but the presentation still needs significant improvement. I will therefore maintain my current score. To give a few examples, please highlight the changes from the original submission to the revised submission; specify whether each algorithm is deterministic or randomized and include its running-time guarantee in the comparison table; and clarify how the motivating applications give rise to the objective, as well as how the sparrow-network experiments relate to these applications.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response to all reviewers

We thank the reviewers. Our contribution is deterministic universal 2.0302.030 rounding: one partition satisfies every probability-weighted layer relative to a supplied rational cluster cover, including layers not given to the algorithm. Norm-specific cover construction then gives a randomized (2.030+ε)(2.030+\varepsilon)-approximation for each fixed ℓp\ell_p objective, improving the general multilayer bound 3.3865+ε3.3865+\varepsilon independently of layer count. For p=1p=1, a stronger existing single-layer result applies (Table 1).

The main theorems, rounding rules, and constants are unchanged. The revision explains the construction and proof, adds comparisons, and states implementation limits. All page references are to the revised manuscript.

1. The idea before the constants. Maximizing excess over all probability weights gives one target Db(C)≤KD_b(C)\le K. A support-family total can exceed it: write that total as K+ΔK+\Delta. The pivot family has complementary total K−λΔK-\lambda\Delta, so their minimum is at most KK for every λ>0\lambda > 0.

Each family supplies a cluster paid for by its own budget decrease. Choosing a cluster for the smaller total makes that minimum a decreasing potential, even when the smaller budget changes. Summing proves the simultaneous guarantee (Section 3, pp. 4–5). Shared thresholds without layer signs change joint inclusion probabilities; this is the construction that the numerical certificate supports. It builds on Cao et al.'s budgets/covariances and Garcia-Soriano and Schohn's weighted variances and exact verification.

The two-vertex example on p. 1 shows why restarting Miyauchi's fixed rule alone cannot ensure 2.0302.030: both pivot orders separate, with cost/cover 10/310/3, while ours joins at zero cost. The supplied cover is not optimal for that layer; this illustrates a rounding obstruction, not approximation hardness. The gap [2,2.030][2,2.030] concerns the worst-layer relaxation.

2. What the computer-assisted proof certifies. Equation (4) identifies the universal target, Equations (5)–(7) pay clusters through the potential, and the variance identity (10) plus Lemma 5 certify the pivot family. Only Lemma 5 is computer-assisted, and both main theorems inherit that dependence.

Appendix C.1 (pp. 15–17) verifies polynomial signs over entire tetrahedra, exact subdivision coverage, and boundary values. Appendix C.2 distinguishes this continuous-domain proof from finite checks. The separate symbolic calculation covers 19 selected polynomials, not a second full-domain proof. Section 4.3 explains the constants' roles; exact verification establishes joint sufficiency.

3. What the experiments show. Table 4 (p. 10) compares exact worst-layer integer OPT on 150 instances: 120 synthetic and 30 subsets of one public two-layer sparrow network, with 6, 8, or 10 vertices. Mean cost/OPT and theoretical factor are:

MethodMean cost/OPTTheoretical factor
Ours1.0322.030
Metric-LP Miyauchi, 20 attempts1.0334
Same-cover Miyauchi, 20 attempts1.0264
Mean-layer aggregation, 20 attempts1.1034L

Appendix E.5 (p. 38) tests universality separately: freeze outputs, then construct layers maximizing cover-relative excess. Five of 150 restarted outputs violate 2.0302.030; ours satisfy it throughout. These are post-hoc supplied-cover tests.

Appendix E.6 (p. 39) executes scalar optimization, averaging, and rounding on 18 pre-specified conflicting-layer inputs. It uses an exponential exact oracle; the cited polynomial-time solver remains unimplemented. Its five baseline universal violations are separate from E.5, and neither method violates the bound on the original input layers. Neither this demonstration nor the 36 supplied-cover profiles establishes scalability.

4. Costs, scope, and reading route. Rounding uses O(n5s)O(n^5s) rational operations for ss cover supports, in addition to cover construction, scalar solves, and encoding costs. The approximation factor is independent of layer count; runtime is not. Appendix F (p. 40) extends the supplied-cover guarantee under a global weight condition; a full algorithm with unequal layer scales remains open.

The 10-page main text now gives the target and potential before numerical choices, followed by the covariance example, parameter roles, and verification. Setup commands and file maps are in the supplementary README; the mathematical verification remains in the manuscript.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.