acceptodds
Under review as a conference paper at ICLR 2027

HAPPIER CONSTRAINED CLUSTERING: EXPLOITING PAIRWISE HINTS

Abstract

Constrained clustering incorporates domain knowledge through pairwise must-link and cannot-link constraints and can substantially improve unsupervised clustering. However, these constraints turn the assignment step of k-means into a combinatorial problem and, when treated only as feasibility conditions, leave much of their geometric information unexploited. We introduce HAPPIER, a weighted hard-constrained k-means framework that quantifies the geometric agreement between feasible assignments and their centers and uses this information to guide point weighting and solution selection. We establish that the fixed-center assignment relaxation is integral for two clusters under mere feasibility of the constraints, and for more than two clusters under acyclic constraint graphs. Consequently, each assignment step admits a globally optimal binary solution obtainable through linear programming, yielding a direct and tractable algorithm. Extensive experiments across diverse datasets, constraint budgets, and noise regimes demonstrate that HAPPIER robustly and consistently outperforms competitive constrained clustering methods in recovering the ground-truth cluster structure. These results confirm the value of exploiting the geometric information encoded by pairwise constraints to improve clustering quality.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Constrained Clustering, Semi-Supervised Clustering, k-Means

Reviews

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

This paper proposes HAPPIER, a weighted hard-constrained kk-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 K>2K>2, 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
  1. The framework is clearly formulated, and the main LP integrality results are sound under the stated structural assumptions.

  2. Using geometric agreement to select among constraint-feasible solutions is an interesting idea.

  3. The experiments cover diverse datasets and repeated constraint draws and initializations, with substantial improvements in several scarce and imbalanced settings.

Critical weaknesses
  1. 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.

  2. The current ablation does not isolate the benefits of reweighting, unhappy-count selection, and additional parameter search. Comparisons under equal computational budgets are needed.

  3. 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
  1. 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 K=2K=2 with unit weights and two must-link groups

A={−1,0,1},B={−2,2},A=\{-1,0,1\}, \qquad B=\{-2,2\},

with a cannot-link constraint between the groups. Initialize the centroids at c1=2c_1=2 and c2=0c_2=0. The two feasible assignments have costs

J(A→1,B→2)=22,J(A→2,B→1)=18.J(A\to 1,B\to 2)=22, \qquad J(A\to 2,B\to 1)=18.

Thus, the second assignment is the unique optimum. Both groups have mean zero, so the subsequent centroid update yields c1=c2=0c_1=c_2=0.

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

S1={−1,1},S2={−2,2}.S_1=\{-1,1\}, \qquad S_2=\{-2,2\}.

Both class centroids are zero. Every point is therefore happy according to the current definition, giving Hgt=1H^{\mathrm{gt}}=1. Nevertheless, no threshold separates these two classes.

  1. Do the gains persist under equal computational budgets, including multiple restarts of the unweighted method?

  2. Using the same candidate solutions, how does unhappy-count selection compare with selection by the unweighted kk-means objective?

4 comments
AuthorsOpenReview ↗

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>2K>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.

Thank you for the reply. The revised proof appears correct now. I will maintain my score.

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.

Reviewer_MUCpOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes HAPPIER, a constrained k-means framework using pairwise must-link and cannot-link constraints. It merges must-link components and formulates constrained assignments as a linear program, with exact integer solutions guaranteed under specific graph conditions. The method further introduces unhappy-count to measure assignments inconsistent with nearest-centroid geometry, and uses constraint-aware weighting and parameter search to select partitions with lower unhappy-count. Experiments on 20 benchmark datasets under different constraint budgets report improved clustering performance over existing methods.

Critical strengths
  1. Interesting geometry-guided solution selection. The use of unhappy-count as a label-free criterion for selecting among constraint-satisfying partitions is an intuitive and interesting idea. The constraint-aware weighting mechanism provides a simple way to explore alternative clustering solutions.
  2. Theoretically grounded optimization framework. The paper establishes conditions under which the fixed-center assignment problem admits exact binary solutions through linear programming. The resulting framework is straightforward, with encouraging empirical results across 20 benchmark datasets.
Critical weaknesses
  1. Insufficient validation of geometry-guided solution selection. While the unhappy-count criterion is intuitively motivated, the experiments do not adequately distinguish whether the gains of HAPPIER(α, β) arise from constraint-aware weighting, the larger pool of candidate partitions generated by grid search, or the unhappy-count selection criterion itself. It remains unclear whether alternative criteria (e.g., MSSC) applied to the same candidates, or additional random restarts without weight tuning, would yield comparable gains. Moreover, although the paper acknowledges that reducing unhappy-count may hinder ground-truth recovery when the true partition is geometrically misaligned, it does not systematically quantify how performance changes as this mismatch increases.
  2. Incomplete experimental comparison and reproducibility. The paper identifies PCCC as another alternating method that optimizes constrained assignments through integer programming, yet omits it from the experimental comparisons. More importantly, the specific (α, β) search grid and selection protocol are not reported, and no code is provided, making the main results difficult to reproduce. A brief end-to-end runtime comparison would also be useful, given the additional parameter search.

Minor presentation note: Several figures & tables use excessively small fonts, making the results difficult to read. A clearer layout is strongly recommended.

Questions for authors
  1. Could the authors distinguish the contributions of constraint-aware weighting, candidate search, and unhappy-count-based selection? For example, comparing unhappy-count with MSSC on the same candidate pool, and using additional random restarts of HAPPIER(0,0) under a matched search budget, would help identify what drives the gains. Could the authors also provide a controlled experiment varying ground-truth happiness and comparing the relative performance of the methods? This would help characterize the method's applicability boundaries, without requiring it to perform well under every geometric condition.
  2. Since the Related Work presents PCCC as another alternating approach to constrained assignment optimization, could the authors include a comparison with PCCC under a consistent experimental protocol? This would help clarify the relative advantages of HAPPIER.
  3. Could the authors provide the exact (α, β) search grid, clarify how parameters are selected across datasets and experimental runs, and specify the LP solver configuration? Providing the code or sufficient implementation details, along with evidence of performance stability under different search configurations, would help substantiate the reported results.
3 comments
AuthorsOpenReview ↗

Response to Reviewer

We thank the reviewer for these helpful suggestions and questions.

Critical Weaknesses

1. Validation of geometry-guided solution selection.

We added ablation experiments addressing each concern: (1) equal-budget comparisons isolating the benefits of weight tuning from additional random initializations; (2) unhappy-count versus MSSC selection over identical candidate pools; and (3) experiments across varying ground-truth happiness levels. These additions clarify the sources of HAPPIER's ARI gains and the regimes in which geometry-guided solution selection is most effective.

2. Experimental comparison and reproducibility.

We agree that a direct comparison with PCCC was warranted and thank the reviewer for pointing out this omission. We have now included both PCCC and PCCC-R under a consistent evaluation protocol. We have also released our code, documented the exact (α,β)(\alpha,\beta) grid, selection protocol, and LP solver configuration, and added end-to-end wall-clock and CPU-time measurements in the Appendix.

Presentation

We also revised the figures and tables to improve font sizes and readability.

Questions for Authors

1. Contributions of weighting, candidate search, and selection.

As detailed in our response to Weakness 1, we have added all three requested ablations, clarifying the respective contributions of weighting, candidate search, and unhappy-count selection, as well as the regimes in which they are most effective.

2. Comparison with PCCC.

As noted in our response to Weakness 2, we now compare against both PCCC and PCCC-R under a consistent experimental protocol.

3. Implementation details and search configurations.

As detailed in our response to Weakness 2, we have expanded the implementation details for all evaluated methods, including HAPPIER's exact (α,β)(\alpha,\beta) grid, per-initialization tuning and selection procedure, and LP solver settings. We have also released our code. The equal-budget comparisons discussed under Weakness 1 further assess the benefits of weight tuning relative to additional search, helping establish that the observed gains are not merely a consequence of a larger search budget.

Thank you for the response and revisions. I appreciate the additional ablation studies, comparisons with PCCC, and clarification of the parameter search and implementation details. These additions provide useful evidence and help alleviate the concerns raised in my original review. I will take them into account in my further assessment and the upcoming reviewer–AC discussion.

AuthorsOpenReview ↗

Thanks for the feedback and reconsideration

Thanks for the feedback and reconsideration.

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

The paper studies weighted k-means (MSSC) clustering under hard pairwise constraints (must-link / cannot-link), requiring all constraints to be strictly satisfied with K fixed. The core theoretical contribution is that the fixed-center assignment subproblem's LP relaxation has integral extreme points in two cases: for K=2 the cannot-link graph is necessarily bipartite; for K>2, if the reduced cannot-link graph is acyclic, integrality follows from the tree-coloring result of Delle Donne and Marenco 2016, yielding a globally optimal binary assignment in polynomial time via LP.

Critical strengths
  1. The LP exactness theorem for the fixed-center assignment subproblem is a contribution. Theorem 1 (K=2) and Theorem 2 (K>2 with acyclic reduced cannot-link graph) give checkable graph conditions, and Corollary 1 (p.6) guarantees that "a globally optimal binary assignment can be obtained in polynomial time through linear programming".
  2. Unhappy-count is a conceptually valuable diagnostic lens. Definitions 1–3 (p.3) operationalize the tension between constraint satisfaction and geometric adaptation as a computable quantity.
Critical weaknesses
  1. The literature coverage is insufficient to support the paper's novelty claims — a positioning-level flaw. The paper states that "Comprehensive overviews ... are available in three recent reviews (González-Almagro et al., 2025; Yin et al., 2024; Bagirov et al., 2020)" (p.2), and the reference list contains only three works from the last three years — González-Almagro et al. (2025), Yin et al. (2024), and Baumann & Hochbaum (2025) — with nothing from 2026.
  2. Beyond the integrality theorem, the methodological increment is thin, and the (α, β) tuning procedure is under-justified and partly circular.
  3. The theoretical guarantees are far narrower than the paper's framing suggests, and their boundary is never stress-tested. The paper runs no experiment at a hint budget where cycles occur, does not measure how often acyclicity holds as a function of budget, and does not analyze behavior when the condition fails. Given that exactness is the primary technical contribution, the absence of a stress test at the boundary of its own assumption is a material gap.
  4. The empirical validation is insufficient in baseline and scenario coverage to support the strongest claims. The comparison set omits the exact/global methods the paper itself cites as the alternative paradigm (Xia 2009; Piccialli et al. 2022) even on small datasets where they are applicable, so the claim of "globally optimal binary assignments" is never compared against a global optimum on instances where both are computable — the natural sanity check for an exactness claim. The soft-constraint baselines are older (2004–2007), and the hard baselines are two methods.
Questions for authors
  1. The literature coverage is insufficient to support the paper's novelty claims — a positioning-level flaw. The paper states that "Comprehensive overviews ... are available in three recent reviews (González-Almagro et al., 2025; Yin et al., 2024; Bagirov et al., 2020)" (p.2), and the reference list contains only three works from the last three years — González-Almagro et al. (2025), Yin et al. (2024), and Baumann & Hochbaum (2025) — with nothing from 2026.
  2. Beyond the integrality theorem, the methodological increment is thin, and the (α, β) tuning procedure is under-justified and partly circular.
  3. The theoretical guarantees are far narrower than the paper's framing suggests, and their boundary is never stress-tested. The paper runs no experiment at a hint budget where cycles occur, does not measure how often acyclicity holds as a function of budget, and does not analyze behavior when the condition fails. Given that exactness is the primary technical contribution, the absence of a stress test at the boundary of its own assumption is a material gap.
  4. The empirical validation is insufficient in baseline and scenario coverage to support the strongest claims. The comparison set omits the exact/global methods the paper itself cites as the alternative paradigm (Xia 2009; Piccialli et al. 2022) even on small datasets where they are applicable, so the claim of "globally optimal binary assignments" is never compared against a global optimum on instances where both are computable — the natural sanity check for an exactness claim. The soft-constraint baselines are older (2004–2007), and the hard baselines are two methods.
3 comments
AuthorsOpenReview ↗

Response to Reviewer

We thank the reviewer for their careful evaluation and constructive feedback.

1. Literature coverage.

We appreciate the reviewer’s reference to the most recent 2026 systematic survey, now included in our literature review to provide more comprehensive and up-to-date coverage of the field.

2. Methodological contribution and weight tuning.

Our main methodological contribution is HAPPIER: using the geometric agreement between assignments and centers to exploit pairwise hints beyond constraint satisfaction. For each candidate clustering, unhappy count is computed directly from its assignments and unweighted centroids. We select (α,β)(\alpha,\beta) by minimizing this count, breaking ties by unweighted MSSC. Neither ground-truth labels beyond the supplied hints nor ARI are used in tuning.

The empirical claim is improved ground-truth recovery, evaluated by ARI, rather than merely a reduction in the criterion used for selection. We have clarified the tuning procedure and added ablations with approximately matched numbers of optimization runs, separating the benefits of weight tuning, additional/better initializations, and unhappy-count selection. These provide empirical justification for the proposed mechanism.

The LP exactness result supports this framework by enabling exact assignment updates without integer restrictions in the stated settings, whereas PCCC uses a MILP formulation.

3. Scope and practical relevance of the integrality guarantees.

The two-cluster result is of independent interest: for K=2K=2, feasibility alone guarantees LP exactness, without any acyclicity assumption. We also note another reviewer’s comment that this can be done in linear time by simple comparisons. For K>2K>2, the acyclicity requirement is mild and can be accommodated in the studied settings, enabling exact LP updates in place of the MILP updates used by PCCC.

The practical scope of the acyclicity condition is examined in Appendix C through both classical random-graph bounds and finite-sample experiments across increasing hint budgets. These complementary analyses show that cycles are rare under the sparse random-supervision regimes considered in our experiments.

Importantly, unlike ground-truth happiness, acyclicity can be checked directly from the supplied constraints, so the applicability of the integrality guarantee can be determined in advance.

The condition also accommodates practical alternatives to unrestricted random sampling. When queried pairs can be selected, guided sampling can preserve acyclicity by construction, accounting for must-link contraction. When hints are supplied in advance and some relaxation is acceptable, retaining a spanning forest removes the minimum number of reduced cannot-link edges needed to obtain acyclicity. This provides a further option in applications that permit relaxing some pairwise constraints, as common in soft-constraint approaches. Appendix C details these constructions and their scope.

4. Experimental comparisons and interpretation of exactness.

We have expanded the comparison to include the recent PCCC method and its repositioning variant, PCCC-R (Baumann and Hochbaum, 2025), alongside additional ablations that clarify the contributions of weighting, perturbations, and unhappy-count selection.

The claim of “globally optimal binary assignments” concerns the assignment subproblem with fixed centers, rather than global minimization over both assignments and centers. PCCC solves this assignment subproblem through MILP and therefore provides the direct comparison for our exact LP updates. Globally exact MSSC methods address the full clustering problem, which is a different computational task.

Our empirical focus is ground-truth recovery from pairwise hints. As the experiments demonstrate, lower MSSC need not imply higher ARI; exploiting this distinction through hint-aware weighting and solution selection is central to our contribution. The soft-constraint baselines provide reference comparisons for relaxing hint satisfaction, while the main evaluation concerns hard-constrained methods. The expanded comparisons and ablations assess both recovery performance and the mechanisms responsible for the observed gains.

Reviewer_fssbOpenReview ↗

The author has made some modifications to the questions, but currently there is only one article in the related work and comparative algorithm section for 2025 in recent years. I will maintain the original score.

The author has made some modifications to the questions, but currently there is only one article in the related work and comparative algorithm section for 2025 in recent years. I will maintain the original score.

AuthorsOpenReview ↗

Answer to reply: on the rejection due to related work criticism

Thanks for providing feedback.

We believe our rebuttal and revised manuscript fully and thoroughly answer the arguments you provided for the reject recommendation.

We found no missing literature significant enough to warrant rejection, and would appreciate if you could constructively provide any such missing citation.

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

This paper studies hard-constrained k-means with must-link (ML) and cannot-link (CL) constraints. It runs block coordinate descent: ML groups are collapsed to single representatives, then the method alternates between (i) an assignment step solved as an LP and (ii) a weighted centroid update. The paper proves the assignment LP is integral in two cases: for K = 2 whenever the constraints are feasible (the CL graph is then bipartite), and for K > 2 when the reduced CL graph is a forest. It also proves finite convergence to a block-optimal point. The main empirical idea is the unhappy-count: the number of points not assigned to their nearest center. This is a label-free selection signal.

Critical strengths
  1. Separating dataset "happiness" from separability explains when constraint satisfaction alone fails to move the geometry, and when the MSSC objective is a poor proxy for recovery.
  2. Collapsing MLs with union-find and using an integral LP gives an assignment step that is exactly optimal, with no greedy or rounding heuristics. This fixes a known failure of COP-KMeans and the feasibility-pump step of BCK-Means.
  3. With 20 datasets, 2 hint budgets, 100 runs per cell, and per-seed analyses, I'd say the experiment appear quite thorough. However, I have some reservations about this (see weaknesses).
  4. Some gains are striking: Nursery ARI 0.47 vs at most 0.10 for others; Mushroom 0.69 vs at most 0.32.
  5. The parameter-free HAPPIER(0, 0) is already competitive or better than the hard-constraint baselines, and the selection rule uses no labels.
Critical weaknesses
  1. The showcase may be cherry-picked, and baselines are missing. Section 4.3 uses two hand-built 100/400 subsets chosen to be "happy". It is unclear how they were selected or whether other subsets behave the same way. PCCC (Baumann & Hochbaum, 2025) is discussed but not compared, and there are no exact or global baselines on small instances to show how close HAPPIER gets to the true constrained optimum.
  2. The largest dataset has N~13k, and no runtimes are reported for the LP step or for the grid search. One LP solve per iteration, times the number of grid points, times restarts, could be expensive. The claim in the conclusion needs timing results or should be dropped.
  3. The comparison seems a bit unfair. HAPPIER picks the best of a grid of runs by unhappy-count. Every baseline runs a single fixed configuration. The soft-constraint methods' penalty weights do not appear to have been tuned. Neither the grid nor the size of the selection budget is reported. A fair test would give each baseline the same number of runs and the same unhappy-count selection rule (over restarts or penalty weights). Without that, part of the gain could come from model selection rather than from the method.
  4. Theorem 1 says that with K = 2 and feasible constraints, each connected component of the CL graph has exactly two valid 2-colorings. The LP is not needed: comparing two costs per component solves it in linear time. Theorem 2 is a direct application of a known tree-coloring polytope result, and for a forest a simple dynamic program also solves the assignment exactly. Theorem 3 is the standard Lloyd finite-convergence argument. The paper should present these as straightforward observations rather than a core contribution, or compare the LP against these direct solvers.
Questions for authors

See weaknesses.

1 comment
AuthorsOpenReview ↗

Response to Reviewer

Thanks for the thoughtful comments and suggestions.

1. Subset selection and comparison with PCCC.

To address concerns about subset selection, each experiment in the imbalanced setting now includes five independently and randomly sampled subsets from the full dataset, respecting the prescribed class proportions (imbalance ratio). We report mean ARI over 1,000 runs: 2 datasets (BBC and PBMC) × 5 random subsets × 10 hint draws × 10 initializations. Importantly, we observe that ground-truth happiness tends to emerge naturally in the scarce-data regime (N=DN=D), with nearly all randomly sampled subsets of BBC and PBMC satisfying this condition. Thus, the original examples were not exceptional or cherry-picked, and the previously observed performance gains remain consistent across independent random subsets.

Thanks for pointing out the missing state-of-the-art method PCCC. We now discuss PCCC more fully in the background section and compare it with HAPPIER in all experiments. This comparison highlights both the computational efficiency of HAPPIER’s assignment step and the benefit of geometry-guided solution selection.

PCCC’s MILP accommodates cycles in the cannot-link graph. When this graph is acyclic after must-link contraction, the distinction at the assignment step boils down to MILP versus LP. For fixed centers and the same assignment costs and constraints, HAPPIER’s LP attains the same global assignment optimum as PCCC’s full MILP, while benefiting from the tractability and scalability of an LP formulation.

The approaches also differ in how they select solutions. HAPPIER uses the HAPPY measure to guide point weighting and solution selection, and our experiments test whether it provides a better proxy for agreement with the ground truth than the clustering objective. Since a global MSSC minimizer need not attain the highest ARI, we evaluate ground-truth recovery directly and consider a global objective-gap comparison beyond the scope and goals of our work.

2. Runtime reporting.

We agree that runtime reporting was an important omission. We have now added detailed wall-clock and CPU-time measurements in the Appendix, covering both LP assignments and the full weight-tuning procedure.

3. Fairness and implementation details.

These are indeed valid concerns. We added equal-budget comparisons in the Appendix, clarified that the soft-constraint penalty weights were already tuned (but incorrectly reported), and expanded the implementation details for all methods, including HAPPIER's exact weight grid and selection budget.

4. Theoretical guarantees and methodological contribution.

Our main methodological contribution is the HAPPY framework: exploiting the geometric information in pairwise hints through unhappy-count-guided weighting and solution selection to improve ground-truth recovery.

Theorems 1–3 provide supporting guarantees for this framework. The integrality analysis explicitly draws on known graph structure and coloring results, while the convergence proof uses standard descent principles, with ties and empty clusters handled explicitly. Their role is to justify the proposed formulation and algorithm rigorously, rather than introduce new general graph-coloring or convergence principles.

The two-cluster and forest cases also admit the direct algorithms described by the reviewer. These are compatible alternatives for implementing the assignment step; we do not claim that LP is the fastest possible solver for these structures. Nevertheless, identifying when integer restrictions can be removed is relevant to constrained clustering, where the very recent PCCC framework uses MILP assignment updates.

We have added comparisons with PCCC and PCCC-R and ablations separating weighting, additional search, and unhappy-count selection. In particular, the gains from applying unhappy-count selection to competing methods demonstrate that the methodological contribution extends beyond the chosen assignment solver.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Revisions

We first thank the reviewers for their careful evaluation and thoughtful feedback, which led to a more comprehensive analysis of our approach and improved the paper.

We summarize the main revisions below and address specific comments in our replies to the individual reviewers.

1. Strengthening the experimental comparison. To address the reviewers’ concerns, we added experiments that include PCCC, provide a fairer comparison across methods, evaluate HAPPIER against additional alternatives, and compare the unhappy-count metric with the MSSC objective. The results demonstrate HAPPIER's advantages and identify the regimes in which these advantages are most pronounced.

2. What drives the gains. The new experiments also provide insights into what drives HAPPIER’s performance gains by separating the effects of individual components and identifying their contributions across different settings.

3. Avoiding suboptimal local solutions. To make the benchmark as consistent as possible across methods, we also tested a common center-perturbation heuristic applied after convergence to escape suboptimal local solutions. We tested both unhappy-count and MSSC as criteria for selecting the resulting solutions. The results further support the value of unhappy-count as a label-free solution-selection criterion beyond HAPPIER.

4. Replacing the 20 Newsgroups experiment. While preparing the rebuttal, we identified label leakage in the 20 Newsgroups experiment. After correcting the issue, we found that the dataset no longer met the joint requirement of scarcity (N=DN=D) and happiness for this setting. We therefore replaced it with a comparable text dataset (BBC).

5. Other revisions. We tightened and clarified the writing throughout the paper in response to the reviewers’ comments and suggestions. We also updated some numerical results, and the appendix now contains a substantially more comprehensive numerical analysis.

We believe these additions substantially strengthen the paper, further establishing HAPPIER as an effective framework for constrained clustering and highlighting the broader value of the unhappy-count metric as a label-free criterion for guiding and selecting clustering solutions, with potential applications across a wide range of domains.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.