- 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 -approximation for each fixed 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 . 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 objectives from 4 (Miyauchi et al., 2026), or by combining existing results, to . 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 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 and the 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
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.
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.
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.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 K. 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/10 makes Miyauchi split in either order, whereas ours joins. Pivot restarts cannot change this supplied-cover example.
Section 4.3 separates candidate geometry, ρ,λ scoring, and proof weights. The 4/5 cutoff excludes distant additions. Any positive λ gives complementarity; 39/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.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).