- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper proposes HAPPIER, a weighted hard-constrained -means framework that alternates between assignment optimization and centroid updates. After contracting must-link groups, the assignment LP is integral for feasible two-cluster instances and, for , when the reduced cannot-link graph is a forest. The method selects point weights using an ``unhappy-count'' criterion, measuring disagreement between assignments and nearest-center geometry. Experiments report substantial ARI improvements on several benchmarks.
Critical strengths
-
The framework is clearly formulated, and the main LP integrality results are sound under the stated structural assumptions.
-
Using geometric agreement to select among constraint-feasible solutions is an interesting idea.
-
The experiments cover diverse datasets and repeated constraint draws and initializations, with substantial improvements in several scarce and imbalanced settings.
Critical weaknesses
-
The novelty of the optimization framework is limited. In my opinion, forest integrality follows from existing results, and closer competing methods, particularly PCCC, are not evaluated.
-
The current ablation does not isolate the benefits of reweighting, unhappy-count selection, and additional parameter search. Comparisons under equal computational budgets are needed.
-
I am not conviced for some proofs of the paper. E.g., the strict-cescent argument of Theorem 3, and some others (See Q1).
Questions for authors
- Some issues in the Lemmas, Definitions, and proofs, as follows.
1.1 The strict-descent argument in Theorem~3 is incorrect.
The proof asserts that an assignment change necessarily produces a strict objective decrease under deterministic tie-breaking. This assertion does not hold when multiple assignments have the same cost.
Consider with unit weights and two must-link groups
with a cannot-link constraint between the groups. Initialize the centroids at and . The two feasible assignments have costs
Thus, the second assignment is the unique optimum. Both groups have mean zero, so the subsequent centroid update yields .
1.2 Minor: Corollary 1 correctly refers to an optimal extreme point. However, Algorithm 1 only specifies solving the LP with deterministic tie-breaking, without explicitly requiring an extreme-point solution.
1.3 Empty-cluster handling is missing from the pseudocode. Although the text describes a possible repair, the pseudocode directly computes every centroid using a weighted-mean formula. This formula is undefined when the corresponding cluster is empty.
1.4 It seems that the stated implication from happiness to linear separability fails under the current definition. The current definition counts a point as happy when its assigned centroid is one of several equally near centroids. Under this tie-permitting definition, happiness does not imply linear separability.
Consider the one-dimensional ground-truth classes
Both class centroids are zero. Every point is therefore happy according to the current definition, giving . Nevertheless, no threshold separates these two classes.
-
Do the gains persist under equal computational budgets, including multiple restarts of the unweighted method?
-
Using the same candidate solutions, how does unhappy-count selection compare with selection by the unweighted -means objective?
4 comments
Thank you for the reply. The revised proof appears correct now. I will maintain my score.
Follow-up
Thanks for providing feedback and acknowledging our proper revision.
We would like to thank you again for the issues you raised, especially the theoretical gaps and W2. For W2, the revised version now isolates the benefits of re-weighting, unhappy-count selection, and additional parameter search, and also provides comparisons under equal computational budgets (or additional/better initialization).
Overall, we believe that our rebuttal, and revised manuscript, fully and thoroughly address all concerns raised. We therefore kindly ask if you could reassess your recommendation based on the revised version.
Thank you for the detailed response, which has addressed most of my concerns. The theoretical arguments now appear to be correct following the revisions. However, I still have reservations about the overall soundness of the results. Therefore, I have decided to maintain my current rating.
Response to Reviewer
We appreciate the reviewer's careful assessment and detailed feedback.
Critical Weaknesses
1. Methodological novelty and comparison with PCCC.
Our main methodological contribution is the HAPPIER framework and its unhappy-count criterion, which exploit the geometric information in pairwise hints to guide point weighting and solution selection. The contribution therefore extends beyond the assignment solver: the added ablations demonstrate the value of this criterion also when applied to competing methods.
The integrality analysis supports this framework by establishing exactness of the LP assignment formulation for weighted pairwise-constrained clustering. It covers every feasible two-cluster instance without an acyclicity assumption, and acyclic reduced constraint graphs for K>2. Appendix C explains why the latter condition is mild and addressable in the studied settings. These results permit exact LP updates where PCCC uses a mixed-integer formulation.
We have added PCCC and its repositioning variant, PCCC-R, to the experimental comparisons, together with a direct LP-versus-MILP runtime comparison and ablations separating the effects of weighting, perturbations, and unhappy-count selection. These additions clarify both the relationship to this close competitor and the distinct contributions of the proposed framework.
2. Ablation studies and computational budgets.
We added ablations separating the effects of weight tuning, additional/better random initializations, and unhappy-count selection, including comparisons with approximately matched numbers of optimization runs and unhappy-count versus MSSC selection over identical candidate pools. We also examined varying levels of ground-truth happiness. These experiments clarify the sources of HAPPIER's ARI gains and the regimes in which geometry-guided selection is most effective.
3. Theoretical correctness.
We thank the reviewer for carefully examining the theoretical arguments. We revised the convergence proof and algorithm pseudocode to address the issues raised, including objective ties, extreme-point selection, and empty-cluster handling. We also corrected the statement relating dataset happiness to linear separability. We address each point below.
Questions for Authors
Q1. Issues in the lemmas, definitions, and proofs.
1.1. Strict descent in Theorem 3.
We thank the reviewer for identifying this issue in the strict-descent argument. We have revised the proof to establish that the objective is non-increasing, with strict decrease at every iteration until the stopping criterion is met. The revised argument guarantees finite termination and block-optimality of the returned solution, while correctly accounting for objective ties.
1.2. Extreme-point requirement.
We agree and have updated Algorithm 1 to explicitly require an optimal extreme-point solution of the assignment LP, ensuring binary assignments under the stated integrality conditions.
1.3. Empty-cluster handling.
We have updated Algorithm 1 to explicitly include empty-cluster repair before centroid updates and clarified its feasibility and non-increasing objective property in the convergence proof.
1.4. Happiness and linear separability.
We thank the reviewer for identifying this subtlety. Since our definition considers ties as happy, we have qualified the statement: In the absence of distance ties, dataset happiness implies linear separability, but the converse need not hold.
Q2–Q3. Computational budgets and solution selection.
As detailed in our response to Weakness 2, we have added matched-budget experiments comparing weight-tuned HAPPIER against additional random initializations of HAPPIER(0,0) and competing methods. We also compare unhappy-count and unweighted MSSC selection over identical candidate pools. These results help distinguish the effects of weight tuning and additional search, and provide further evidence that unhappy count can better guide ground-truth recovery under sufficient pairwise supervision.