acceptodds
Under review as a conference paper at ICLR 2027

GDP: Relation-Preserving Constrained Clustering from Graded Pairwise Supervision

Abstract

Pairwise constrained clustering typically uses binary supervision, while graded relations may reflect weak evidence, mixed membership, or coarser-resolution agreement. The same intermediate grade can imply different cluster structures, while relational orderings may appear on different numerical scales. Preserving graded relations and forming explicit cluster assignments are distinct but coordinated tasks. We introduce Graded DualPair (GDP), separating these roles across Local and Global representations, coordinating their pairwise relations while using relative grade ordering for direct Global supervision. GDP-Hier extends this principle across prescribed hierarchy resolutions. Our theory analyzes the relation–partition design and establishes sufficient conditions for multi-resolution hierarchy recovery. Across diverse benchmarks, GDP achieves consistently strong and frequently leading clustering performance and remains robust to targeted grade recalibration, while GDP-Hier yields strong multi-resolution clustering with cross-level coherence.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
constrained clustering, deep clustering, semi-supervised clustering, pairwise constraints, graded pairwise supervision, hierarchical clustering

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_RjJkOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the constrained clustering problem under continuous pairwise relationship supervision. The authors propose Graded DualPair (GDP), which learns graded relationships through Local representation learning, forms cluster partitions through Global representations and fixed simplex prototypes, and coordinates the two via relationship ranking and Local–Global consistency. Furthermore, the authors extend the GDP-Hier framework to multiple pre-specified levels, learning multi-resolution partitions by combining same-cluster relationships across levels. Experiments show that the method performs relatively stably under various supervision semantics and score rescalings, and achieves good clustering accuracy and cross-level consistency.

Critical strengths
  1. The paper points out that identical intermediate relationship scores may represent uncertain evidence, mixed membership, or coarse-level consistency, thereby reasonably distinguishing the two objectives of relationship preservation and cluster partitioning.
  2. The Local–Global division of labor combined with ranking supervision preserves continuous relationship information while forming explicit clusters, reducing the limitation of directly interpreting raw scores as same-cluster probabilities.
  3. The paper evaluates multiple supervision semantics, score rescalings, and hierarchy scales, and validates the main components through ablation and mechanism analyses. The accuracy and cross-level consistency results of GDP-Hier on complex hierarchies are particularly convincing.
Critical weaknesses
  1. Why are the Local and Global networks set up sequentially? Would the resulting features have sequential dependencies? If a parallel design were used, what impact would it have on the results?
  2. Furthermore, Local fits the raw scores via Equation (3), while Equation (7) requires the Global same-cluster relationships to be close to the Local values. Therefore, even though Global's direct supervision adopts ranking, the raw scores still indirectly constrain the cluster assignment.
  3. The layers of GDP-Hier are trained jointly by combining relationships, but there is no explicit guarantee that a fine-grained cluster can belong to only one coarse-grained cluster, so the output may still violate the nesting relationship. In addition, the recovery conclusion of Theorem 5.4 relies on conditions such as assignment concentration, constraint connectivity, and sufficiently small error, and does not guarantee that the training process reaches these conditions. It is suggested to further analyze the sources of hierarchical conflicts and explore explicit nesting constraints.
  4. In the experimental results, how is the supervision information between sample pairs obtained?
Questions for authors

Please see weaknesses.

6 comments
AuthorsOpenReview ↗

Response 1/4: Weakness 1

We appreciate your time and effort in evaluating our work and your positive assessment of the motivation for distinguishing graded-relation preservation from explicit cluster formation, the Local–Global division of labor with ranking supervision, and our evaluation across supervision semantics, score rescalings, and hierarchy scales.

Below, we address all four of the concerns point by point.


W1. Sequential versus parallel Local–Global architecture

"Why are the Local and Global networks set up sequentially? Would the resulting features have sequential dependencies? If a parallel design were used, what impact would it have on the results?"

[Response]

We thank the reviewer for this constructive question, which provides an opportunity to demonstrate the architectural flexibility of GDP. Our central contribution lies in separating graded-relation preservation from explicit partition formation and effectively coordinating the two, a methodological principle that does not depend on a particular sequential network topology.

  • Sequential Local–Global architecture. In the original GDP, the Local–Global division of labor takes concrete form in a sequential architecture, with Global directly reusing the relation-preserving representations learned by Local for explicit partition formation (Eq. (4)).

  • Feature dependency in the sequential architecture. In the original GDP, Global features are computed from Local features, as specified by zjglob=fϕglob(zjloc)z_j^{\mathrm{glob}}=f_{\phi_{\mathrm{glob}}}(z_j^{\mathrm{loc}}) (Eq. (4)). The resulting feature dependency follows from this computation path, which we further examine through a parallel architecture below.

  • Requested analysis of parallel Local–Global architecture. Following your suggestion, we conducted an additional ParallelGDP experiment to directly assess the impact of parallel design.

    1. Model and protocol. ParallelGDP uses a shared 500–500 backbone with separate Local (2000D) and Global (D) heads; Global reads shared features rather than Local features. LGRC and all other GDP losses, weights, and schedules are retained (LGRC every epoch; detached Local targets). We evaluate 7 datasets × 3 supervision types × 5 runs, using 5k constraints without autoencoder pretraining.

    2. Results. Test ACC/NMI/ARI (%, five-run means). GDP references are from original Table 12.

      CIFAR100-20CIFAR10FMNISTImageNet10MNISTReutersSTL10
      Binary
      GDP (Ours)71.3/67.0/56.294.9/89.3/89.379.1/70.9/64.695.9/90.4/91.195.8/89.6/90.995.2/81.9/88.289.5/80.7/79.0
      ParallelGDP (w/ LGRC)72.6/68.0/57.794.8/89.2/89.180.4/71.3/65.495.7/90.1/91.095.6/89.0/90.395.5/82.7/88.889.5/80.7/78.9
      ParallelGDP (w/o LGRC)25.9/26.2/12.549.5/35.9/28.351.0/36.7/30.149.5/38.7/31.585.7/79.2/77.794.6/81.7/87.449.6/34.8/29.6
      Difficulty
      GDP (Ours)63.2/60.8/47.495.0/89.3/89.581.2/71.6/65.995.7/90.2/90.694.7/87.4/88.793.5/78.0/85.589.1/80.2/78.0
      ParallelGDP (w/ LGRC)64.8/61.3/48.595.0/89.2/89.479.4/71.4/65.095.7/90.3/90.694.4/87.1/88.193.8/78.4/85.689.2/80.1/78.1
      ParallelGDP (w/o LGRC)12.9/6.9/2.428.5/17.8/11.325.6/10.9/7.237.5/25.6/22.425.0/10.9/6.866.1/39.7/41.327.9/13.8/8.4
      Mix
      GDP (Ours)65.0/59.1/46.794.9/89.2/89.477.2/69.3/62.895.9/90.5/91.293.3/84.8/86.094.8/81.1/87.889.5/80.6/79.0
      ParallelGDP (w/ LGRC)65.0/60.8/44.294.9/89.1/89.277.1/69.2/63.096.2/91.0/91.393.2/84.5/85.794.7/80.6/87.289.7/80.7/79.2
      ParallelGDP (w/o LGRC)16.2/10.4/4.049.6/43.0/33.732.9/20.0/13.637.5/27.7/18.334.3/22.3/15.283.1/63.3/65.938.4/26.9/17.9
    3. Comparison. With LGRC retained, ParallelGDP achieves performance broadly comparable to sequential GDP across the evaluated settings, demonstrating the architectural flexibility of our Local–Global coordination framework.

    4. Complementary LGRC ablation. We evaluate ParallelGDP without LGRC to examine relation transfer under parallel feature processing. Retaining LGRC improves mean ACC/NMI/ARI in all 21 settings. On CIFAR100-20/Binary, the no-LGRC model achieves 66.3% Local K-means ACC but only 25.9% Global-assignment ACC. These findings complement our response to Weakness 2 (see below), extending the evidence for LGRC's benefits to parallel feature processing.

Together, these results directly address sequential design, feature dependency, and parallelization. We will incorporate the new results into the revised manuscript.

AuthorsOpenReview ↗

Response 2/4: Weakness 2

W2. Raw graded scores still indirectly influence Global assignments

"Furthermore, Local fits the raw scores via Equation (3), while Equation (7) requires the Global same-cluster relationships to be close to the Local values. Therefore, even though Global's direct supervision adopts ranking, the raw scores still indirectly constrain the cluster assignment."

[Response]

Indeed, raw scores indirectly influence Global assignments. This is an intentional and beneficial part of our design, supported by both ablation and semantic-alignment evidence. We first clarify the motivation behind this design, and then provide direct evidence of its benefits:

  • 1. Complementary rather than conflicting roles of ranking and raw scores.

    Ranking constrains only the relative ordering of Global relations, without imposing fixed numerical gaps between relation scores (Sec. 4.2, Eq. (5), lines 181–189). Meanwhile, Local learns relation values directly from raw grades (Eqs. (2)–(3)), which LGRC transfers to Global (Eq. (7)). Theorem 5.2 formally establishes their complementarity in relation space: under increasing Ranking pressure, the combined objective converges to the order-consistent relations closest to the Local values, preserving them exactly when already order-consistent (Sec. 5, lines 270–279; Appendix A.3).

  • 2. Empirical evidence for the benefits of retaining both ranking and raw scores.

    1. Ablation evidence.

      1. Ranking is more effective under the tested grade recalibrations. Table 3 compares GDP with Global BCE. Ranking gives the clearer advantage under Difficulty and recalibrated Mix, whereas direct Global BCE remains competitive when Mix grades retain their native overlap interpretation.

      2. Local-to-Global relation transfer provides additional benefits. Removing LGRC reduces ACC/NMI/ARI in all 49 originally reported dataset–condition cases (Appendix D.6, lines 2373–2375) and all 21 new ParallelGDP settings (W1, see above), supporting the benefits of transferring Local's raw-grade-informed relations to Global under both sequential and parallel architectures.

    2. Preservation of graded semantics.

      1. Figure 13: Under both Difficulty and Mix, the supplied grades exhibit positive Spearman correlations with the learned Local and Global relation scores across all seven datasets, showing that Global relations retain the ordering information in graded supervision (Appendix D.6, lines 2480–2483; Fig. 13).
      2. Table 24: We further evaluate whether Global assignments preserve the source-specific semantics of graded supervision. Under Difficulty, source decisiveness is positively correlated with Global relation decisiveness (Spearman ρ = 0.448–0.726). Under Mix, mixture ambiguity is positively correlated with Global assignment entropy (ρ = 0.194–0.527). Both correlations are positive across all seven datasets, showing that Global assignments remain sensitive to both the strength of relational evidence and the ambiguity of mixed membership (Appendix D.6, Table 24 and lines 2514–2522).

Thus, the indirect influence of raw scores is a deliberate and beneficial part of our design: retaining both ranking and raw-score-informed Local relations improves clustering performance while preserving the semantics of graded supervision.

AuthorsOpenReview ↗

Response 3/4: Weakness 3-4

W3. Cross-level nesting and theoretical recovery guarantee

Concern A: Explicit nesting and cross-level hierarchy conflicts.

"... do not explicitly guarantee that each fine-grained cluster belongs to only one coarse-grained cluster, potentially resulting in nesting violations. Further analysis ... and exploration of explicit nesting constraints are suggested."

Concern B: Theoretical recovery guarantee and practical conditions.

The recovery guarantee in Theorem 5.4 relies on conditions such as assignment concentration, constraint connectivity, and sufficiently small error, without guaranteeing that these conditions are satisfied during actual training.

[Response]

We address both concerns through analyses already included in the paper: explicit nesting post-processing, cross-level conflict analysis, sufficient recovery conditions, and controlled empirical validation.

  • 1. Concern A: Nesting and hierarchy conflicts.

    1. Design rationale. GDP-Hier aims to balance levelwise clustering accuracy and cross-level coherence through joint multi-resolution learning, rather than enforcing strict nesting by construction (Secs. 4.4 and 7).

    2. Requested evaluation of explicit nesting. The original Appendix D.5 (Table 20) evaluates agglomerative post-processing of input features and baseline embeddings, yielding zero HVR by construction. GDP-Hier achieves higher Mean ACC than the strongest nested reference on three of five datasets, including T200 (47.3% vs. 41.0%); the reverse holds for Aircraft and T608. Thus, perfect structural nesting alone does not guarantee better semantic hierarchy recovery.

    3. Requested hierarchy conflict analysis. The original Table 18 localizes T608's hierarchy violations: parent-to-leaf reaches 12.8 ± 1.1%, compared with 3.9 ± 1.1% and 2.7 ± 0.7% at the two coarser transitions (Appendix D.5). GDP-Hier achieves the lowest HVR on four of five real hierarchical benchmarks among native constrained methods (Sec. 6.2, Table 2).

    Thus, the original results demonstrate GDP-Hier's strong balance of levelwise accuracy and cross-level coherence among native constrained methods, while identifying the remaining hierarchy conflicts.

  • 2. Concern B: Recovery theory and practical relevance.

    1. Theoretical guarantee. Theorem 5.4 establishes sufficient conditions for exact hierarchy recovery (Sec. 5). The guarantee applies when these conditions hold; it does not assert that training necessarily attains them.

    2. Empirical validation. Our Synthetic-Hier experiments examine the practical relevance of these recovery conditions through two complementary analyses. The E95 diagnostic shows that more favorable theory-related error levels are associated with better hierarchy recovery, while a matched breakpoint-gap intervention demonstrates that weakening a key recovery factor degrades recovery performance (Sec. 6.2, Fig. 4).

    Thus, theory establishes sufficient recovery conditions, while empirical validation demonstrates their practical relevance.

Thus, the paper directly addresses both concerns: explicit-nesting evaluation and conflict analysis, alongside sufficient recovery conditions and empirical validation of their practical relevance.


W4. Provenance of pairwise supervision

"… how is the supervision information between sample pairs obtained?"

[Response]

Sec. 6.1 and Appendix C.3 document five supervision sources: binary constraints and four graded forms capturing instance difficulty, mixed membership, human judgments, and hierarchical semantics.

  1. Binary: Same-class/different-class supervision derived from ground-truth labels (Appendix C.3, lines 1223–1226).

  2. Difficulty: Classifier-derived predictive distributions capture instance easiness and induce graded pairwise relationships (lines 1228–1241).

  3. Mix: Soft membership vectors from mixed samples provide graded pairwise relationships through their inner products (lines 1254–1265).

  4. Human-derived: CIFAR10H grades derive from aggregated human class distributions (Appendix C.3, lines 1267–1272). We additionally evaluate FMNIST-H as a second human-annotated dataset (see our response to Reviewer r5XW, Q2).

  5. Hierarchy-induced: Pairwise grades reflect the deepest semantic resolution of each sample pair (lines 1274–1283).

The appendices provide all technical details, including pairwise-grade construction (Appendix C.3), constraint sampling, experimental protocols, grade calibration settings, and numerical transformations (Appendices C.4 and D.4). The supplementary materials provide the complete source code, experimental resources, and reproduction instructions.

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

This paper proposes Graded DualPair (GDP) for clustering with graded pairwise supervision. It separates relation preservation from partition formation through coordinated Local and Global representations, combining relation fitting, ranking supervision, and prototype calibration. GDP-Hier extends the framework to multiple hierarchy resolutions. The paper provides supporting theoretical analysis and extensive experiments showing strong clustering performance, robustness to grade recalibration, and improved cross-level consistency.

Critical strengths
  1. The separation of relation learning and partition formation is well motivated. It addresses the mismatch between intermediate relation grades and discrete cluster membership, with theoretical analysis clarifying the design.

  2. The empirical evaluation is extensive, covering different supervision semantics, image and text datasets, recalibration tests, and component ablations. These results provide substantial evidence for the framework’s effectiveness.

Critical weaknesses

The representation dimensions are not fully matched across methods. GDP learns Local relations in a 2,000-dimensional space, while key baselines use 10–20-dimensional embeddings for flat clustering. Without a dimension-matched comparison, the contribution of Local–Global coordination is harder to isolate.

Questions for authors
  1. Does GDP retain its advantage when ProbPair uses the same Local representation dimension and a comparable reconstruction setup?

  2. What explains the T608 leaf-accuracy degradation relative to input-feature K-means? Does this accuracy–coherence tradeoff persist across constraint budgets?

2 comments
AuthorsOpenReview ↗

Response 1/2: Weakness 1 & Question 1

We appreciate your time and effort in evaluating our work, as well as your positive assessment of the motivation behind the Local–Global separation, the theoretical analysis supporting our design, and the extensive empirical evaluation across different supervision semantics and datasets.

Below, we address your remaining concerns point by point.


W1. Representation dimension fairness

"The representation dimensions are not fully matched across methods. GDP learns Local relations in a 2,000-dimensional space, while key baselines use 10–20-dimensional embeddings for flat clustering. Without a dimension-matched comparison, the contribution of Local–Global coordination is harder to isolate."

[Response]

We appreciate the chance to explain our dimension-matching setup. Our original design maintains a shared backbone architecture and matches the dimensionality of the representations used for final clustering. Specifically:

  1. Shared backbone architecture. GDP and the autoencoder-based baselines use the same 500–500–2000 encoder backbone, with identical layer structure and hidden dimensions across these shared layers (Appendix C.5, lines 1428–1435).

  2. Matched final clustering dimensions. (a) GDP uses a D-dimensional Global representation to determine cluster assignments, while (b) baselines perform clustering on the D-dimensional final embedding. Thus, the representations used for final clustering are dimension-matched across the methods (Appendix C.5, lines 1431–1435).

Thus, our original experimental design prioritizes backbone consistency and matched final clustering dimensions. To further address your concern about Local dimensionality, we conduct the requested matched-dimension experiment below.


Q1. Dimension-matched ProbPair comparison

"Does GDP retain its advantage when ProbPair uses the same Local representation dimension and a comparable reconstruction setup?"

[Response]

Yes. GDP also retains its advantage when ProbPair's embedding dimension is increased to match GDP's Local representation. As requested, we increased ProbPair's final embedding dimension to 2000, retaining its original 500–500–2000 encoder backbone and pairwise objective, with a mirrored 2000–2000–500–500 decoder. Both methods use MSE reconstruction with the same weight (λ=0.02). We evaluated it without autoencoder pretraining, using 5k constraints across 7 datasets and 3 supervision types, with 5 independent runs per setting. The resulting test ACC/NMI/ARI (%) are compared with GDP's original Table 12 results below:

CIFAR100-20CIFAR10FMNISTImageNet10MNISTReutersSTL10
Binary
ProbPair (2000 D)34.1/38.2/20.694.8/89.1/89.175.8/66.6/59.596.1/90.9/91.692.7/83.7/84.894.8/80.9/87.889.4/80.3/78.7
GDP (Ours)71.3/67.0/56.294.9/89.3/89.379.1/70.9/64.695.9/90.4/91.195.8/89.6/90.995.2/81.9/88.289.5/80.7/79.0
Difficulty
ProbPair (2000 D)60.3/59.2/38.494.1/88.0/87.674.8/68.3/58.691.7/85.7/81.089.8/80.6/78.486.4/69.3/72.784.0/77.8/64.5
GDP (Ours)63.2/60.8/47.495.0/89.3/89.581.2/71.6/65.995.7/90.2/90.694.7/87.4/88.793.5/78.0/85.589.1/80.2/78.0
Mix
ProbPair (2000 D)66.6/61.8/50.494.8/88.9/89.173.5/65.6/57.296.1/90.8/91.790.4/79.8/80.493.7/77.8/84.989.4/80.3/78.9
GDP (Ours)65.0/59.1/46.794.9/89.2/89.477.2/69.3/62.895.9/90.5/91.293.3/84.8/86.094.8/81.1/87.889.5/80.6/79.0

The dimension-matched results confirm that GDP's advantage persists across the majority of settings:

  1. Overall performance. GDP outperforms 2000D ProbPair in 18 out of 21 dataset–supervision settings across all three metrics, including all seven Difficulty settings. While some performance gaps in both directions are small, GDP achieves substantially larger improvements in several settings, particularly on CIFAR100-20 under Binary supervision.

  2. Impact of increasing the embedding dimension. A higher embedding dimension does not necessarily improve ProbPair's performance. On CIFAR100-20 under Binary supervision, increasing its embedding dimension from 20 to 2000 reduces ACC from 62.8% (original ProbPair, Table 12) to 34.1%, whereas GDP achieves 71.3% under the same experimental setting.

These results directly address the dimensionality concern: GDP's advantage persists across most evaluated settings after matching ProbPair's final embedding dimension to GDP's 2000D Local representation. We will incorporate this dimension-matched comparison into the revised manuscript.

AuthorsOpenReview ↗

Response 2/2: Question 2 & Overall Conclusion

Q2. T608 leaf accuracy and the accuracy–coherence trade-off

"What explains the T608 leaf-accuracy degradation relative to input-feature K-means? Does this accuracy-coherence tradeoff persist across constraint budgets?"

[Response]

Our analysis and new experiments address both questions:

  • Extremely sparse same-leaf supervision is a plausible contributor to T608's leaf-accuracy gap.

    1. Limited leaf-level supervision. Under uniform pair sampling, same-leaf positive pairs account for only 0.2% of all possible T608 pairs (rounded; Appendix C.3, Table 4), yielding approximately 8 such constraints in expectation out of 5k. This limits the leaf-level guidance available to GDP-Hier, whereas unsupervised input-feature K-means does not depend on these constraints, helping explain the observed leaf-accuracy gap.

    2. Supporting evidence from the T200 subset. T200 is a 200-leaf subset of T608, preserving the inherited semantic hierarchy, with the same-leaf positive proportion reaching 0.5% (Table 4). On T200, GDP-Hier achieves 52.9% Leaf ACC, outperforming input-feature K-means (46.7%), consistent with this interpretation (Table 2; Appendix D.5, Table 19).

  • Yes, the observed leaf-accuracy/coherence pattern persists across constraint budgets. We conducted additional T608 experiments with 1k/2k constraints. Together with the original 5k results and input-feature K-means reference, the following table compares Mean ACC, Leaf ACC, and HVR (five-run means, %):

    MethodConstraintsMean ACC ↑Leaf ACC ↑HVR ↓
    Input-feature K-means–27.734.126.7
    GDP-Hier1k28.017.410.7
    GDP-Hier2k29.024.45.1
    GDP-Hier5k29.124.76.5

Across all three budgets, GDP-Hier maintains higher Mean ACC and substantially lower HVR than input-feature K-means, while its Leaf ACC remains lower but improves from 17.4% to 24.7% as the constraint budget increases. Together, these findings support our sparse-supervision explanation and confirm the observed cross-budget pattern, addressing both parts of the question.


Overall Conclusion

We hope our responses resolve your remaining concerns:

  • W1/Q1: Representation dimensionality. Our original design maintains a shared encoder backbone and matched final clustering dimensions, while the new 2000D ProbPair comparison shows GDP's advantage persists in 18/21 settings.
  • Q2: T608 accuracy and coherence. Sparse same-leaf supervision plausibly contributes to the leaf-accuracy gap. New 1k/2k results show consistently higher Mean ACC and lower HVR than input-feature K-means across budgets, alongside improving Leaf ACC.

We will incorporate the new 2000D ProbPair comparison and T608 constraint-budget results, together with their experimental details, into the revised manuscript.

We hope these clarifications and new results further strengthen your positive view and support a more favorable assessment, and we remain happy to address any further questions :-)

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

This paper studies constrained clustering with graded pairwise supervision, where intermediate relation grades need not represent calibrated probabilities of two samples belonging to the same cluster. The main observation is that preserving graded relational information and forming a discrete partition are related but distinct objectives.

The paper proposes Graded DualPair (GDP), which separates these roles between Local and Global representations. The Local representation directly learns graded pairwise relations. The Global representation produces soft assignments over fixed simplex prototypes and is supervised primarily through relative grade ordering rather than direct fitting to the numerical grades. Local–Global Relation Consistency transfers relation information from the Local representation to the Global branch, while assignment-adaptive prototype calibration and marginal entropy support partition formation. GDP-Hier extends the framework to prescribed multi-resolution hierarchies using resolution-specific Global heads and a composite hierarchy relation.

The paper provides theoretical analysis of the relation–partition design and sufficient conditions for hierarchy recovery. Empirically, GDP is evaluated across multiple flat clustering benchmarks under binary, difficulty-based, mixed-membership, and human-derived graded supervision. GDP-Hier is evaluated on multi-resolution hierarchy benchmarks. The experiments include grade-recalibration tests, multiple constraint budgets, component ablations, synthetic theory-aligned experiments, initialization studies, hyperparameter analyses, and hierarchy-coherence evaluation.

Critical strengths
  1. The paper identifies a meaningful distinction between relation preservation and partition formation and turns it into a coherent method. Intermediate pairwise grades can represent different phenomena and therefore need not be calibrated flat co-membership probabilities. GDP addresses this by preserving graded relations in a Local representation while using relative grade ordering and prototype-based assignments to form the Global partition. I find this separation conceptually well motivated and more general than directly interpreting every intermediate grade as a soft same-cluster target.

  2. The empirical and theoretical validation is unusually comprehensive. The paper evaluates multiple supervision semantics, datasets, constraint budgets, initialization regimes, and numerical grade recalibrations, and extends the analysis to multi-resolution hierarchy recovery. Component ablations support the importance of Local–Global coordination, ranking-based Global supervision, and prototype calibration, while the synthetic hierarchy experiments directly examine quantities appearing in the theoretical recovery condition. This breadth makes the empirical conclusions substantially more convincing.

Critical weaknesses
  1. There is a concerning between-experiment-family reproducibility discrepancy in one of the ablation settings. The paper explicitly reports that, for CIFAR100-20 Mix with 5k constraints and no autoencoder pretraining, two independently executed experiment families under the claimed same nominal configuration produce GDP test ACC values of approximately 65.0% and 59.8%, both with standard deviation around 2.2%. The authors state that their audit found no discrepancy in data construction, aggregation, or nominal configuration and that the available evidence does not identify a causal explanation. I appreciate the transparency, but a roughly five-point unexplained shift is substantial relative to many of the comparative margins in the paper. This raises a question about unaccounted experimental variability and how confidently individual ablation differences should be interpreted.
Questions for authors
  1. Clarification on experimental variability: The appendix reports an unexplained difference between two independently executed experiment families for GDP on CIFAR100-20 Mix with 5k constraints and no pretraining: approximately 65.0 ± 2.2% versus 59.8 ± 2.2% ACC despite the same nominal configuration. Could the authors provide further diagnostics for this discrepancy? In particular, do independently repeated experiment families show similar between-family variability on other datasets/settings, and does this variability change any conclusions from the component ablations? A convincing explanation or additional repeated-family evidence would materially affect my confidence in the ablation results.
  2. Naturally occurring graded supervision: CIFAR10H is useful evidence beyond the controlled Difficulty/Mix constructions, but it covers a single dataset and several methods are closely grouped. Could the authors clarify which experimental evidence they view as supporting the general claim that GDP handles naturally occurring graded relations with heterogeneous semantics or calibration, beyond the synthetic constructions? If additional natural graded-constraint experiments are available, these would materially strengthen the paper.
2 comments
AuthorsOpenReview ↗

Response 1/2: Weakness 1 & Question 1

We sincerely thank you for the time and effort devoted to evaluating our work, and for your positive assessment of GDP's conceptual motivation, theoretical analysis, and comprehensive empirical evaluation.

Below, we address your remaining concerns point by point.


W1/Q1. Between-family experimental variability

"... two independently executed experiment families ... produce GDP test ACC values of approximately 65.0% and 59.8% ... Could the authors provide further diagnostics ... and does this variability change any conclusions from the component ablations?"

[Response]

We thank you for recognizing our transparency in reporting this discrepancy. We faithfully reported both independent results and explicitly discussed the difference in Appendix D.6. Our additional independent replication and systematic audit provide further evidence on the reported discrepancy, while the original within-family ablations continue to support our main component findings.

  1. Additional independent replication under the same setting. Under the same nominal CIFAR100-20 Mix setting (5k constraints, no pretraining), three independent five-run experiment families yielded the following test ACC results (%):

    ExperimentFive individual runsMean ± Std
    Main experiment (Table 12)65.03, 62.01, 64.59, 64.87, 68.2764.95±2.23
    Ablation experiment (Table 21)60.92, 56.27, 62.18, 59.08, 60.3459.76±2.25
    New independent replication62.10, 64.57, 64.60, 64.85, 62.0463.63±1.43

    The new five-run replication yields 63.63 ± 1.43% test ACC, between the two originally reported means, providing additional evidence for assessing the observed between-family difference.

  2. Our audit finds the discrepancy to be isolated among the examined settings. We examined data construction, Mix supervision generation, result aggregation, and experimental configurations, finding no inconsistency in these checks. The variation occurs across independently executed families involving stochastic constraint sampling and optimization. No similar discrepancies were found in other comparable settings.

  3. The broader experimental conclusions remain supported. Across the other 20 matched dataset–supervision settings in Tables 12 and 21 (Binary, Difficulty at b=0.5, and Mix identity), the median ACC difference is only 0.15 percentage points, calculated from unrounded results (14/20 below 0.5 points). Importantly, the original within-family ablations provide consistent evidence for our main component findings: removing LGRC reduces all three metrics in all 49 reported settings, while removing the vertex term does so in 47/49 settings (Appendix D.6, Table 21).

  4. Reproduction resources provided with the original submission. Our supplementary materials provide the source code, experimental configurations, and reproduction instructions for independent verification of the reported results.

Together, the additional independent replication, systematic audit, and extensive within-family ablations provide further evidence on the reported variability and reinforce our main experimental conclusions, with the original supplementary materials supporting independent verification.

AuthorsOpenReview ↗

Response 2/2: Question 2 & Overall Conclusion

Q2. Naturally occurring graded supervision

"... which experimental evidence ... supports the general claim that GDP handles naturally occurring graded relations with heterogeneous semantics or calibration ... CIFAR10H ... covers a single dataset and several methods are closely grouped ... If additional natural graded-constraint experiments are available, these would materially strengthen the paper."

[Response]

We thank you for this constructive suggestion. We would respectfully like to draw your attention to the additional experiments on naturally sourced graded supervision already included in the paper, beyond CIFAR10H and the synthetic Difficulty/Mix settings. We also further strengthen this evidence with new human-annotated experiments.

  1. Existing evidence from naturally grounded graded relations. Beyond CIFAR10H and the synthetic Difficulty/Mix settings, our paper already evaluates benchmarks (CIFAR100-HIER, RCV1-HIER, Aircraft, T200, and T608) whose graded supervision captures inherent semantic relationships among classes, grounded in the datasets' native taxonomies or the established WordNet ontology (Appendix C.3). These results demonstrate our method's effectiveness under diverse naturally sourced graded supervision (Table 2; Appendix D.5).

  2. New evidence of clearer performance separation under fewer constraints. Without autoencoder pretraining, GDP's test ACC lead over the strongest competing mean increases from 0.30 percentage points at 5k constraints (94.0% vs. 93.7%, WPP; Table 16) to 1.44 points in our additional 1k-constraint evaluation (see below) (89.04% vs. 87.60%, ECI-PP).

  3. Additional experiments with human-derived supervision. Following your suggestion that further experiments could strengthen the paper, we identified and evaluated an additional human-annotated dataset, FMNIST-H (Ishida et al., ICLR 2023). We use a fixed, class-stratified 8k/2k train/test split of the original 10k FMNIST test images, with the same input representation as our FMNIST experiments and original class labels for evaluation. As in CIFAR10H, we sample training pairs and compute their grades as inner products of human class-vote distributions. We evaluate all eight methods on CIFAR10H and FMNIST-H using 1k constraints, without autoencoder pretraining. The following table reports test ACC/NMI/ARI (%, five-run means):

    MethodCIFAR10HFMNIST-H
    VanillaDCC54.15/54.90/40.7659.44/60.69/45.90
    VolMaxDCC73.09/69.03/58.9458.25/56.71/42.65
    CIDEC67.37/69.32/57.1258.09/57.31/41.45
    SpherePair87.27/79.05/75.3759.90/57.61/43.93
    ProbPair84.29/75.44/70.4361.46/60.90/46.83
    WPP80.53/71.69/64.4962.49/60.90/47.10
    ECI-PP87.60/82.50/78.0664.02/62.84/49.26
    GDP (Ours)89.04/84.16/80.7567.00/65.47/51.80

    GDP achieves the highest mean ACC/NMI/ARI on both human-derived datasets, demonstrating its effectiveness under naturally sourced graded supervision. We will include these new results in the revised manuscript.

Together, we (1) highlight existing evidence for natural graded supervision, (2) demonstrate clearer performance separation with fewer constraints, and (3) strengthen human-derived validation with FMNIST-H.


Overall Conclusion

We hope our responses resolve your remaining concerns:

  • W1/Q1: Between-family experimental variability. Additional independent replication and systematic auditing provide further evidence on the reported variability, while extensive within-family ablations continue to support our main component conclusions.
  • Q2: Naturally occurring graded supervision. We highlight existing evidence beyond CIFAR10H and synthetic settings, demonstrate clearer separation with fewer constraints, and provide new FMNIST-H experiments confirming GDP's advantage.

We will incorporate the new replication and human-derived experiments (1k CIFAR10H and FMNIST-H), together with their protocols, into the revised manuscript, while making the existing taxonomy-grounded evidence more visible.

We hope these clarifications and new results further strengthen your positive view and support a more favorable assessment, and we remain happy to address any further questions :-)

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.