- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies multi-class classification from unlabeled instances, incompletely revealed same-class relations, and an aggregate class prior. The authors propose PRIME, which explicitly models the revealed same-class pairs through a class-independent one-sided reveal process rather than treating unrevealed pairs as negative relations. The method combines an incomplete-similarity likelihood with a permutation-invariant class-prior regularizer. The paper provides theoretical results on relation recovery, classification recovery up to permutation, finite-sample generalization, and reveal-rate normalization. Experiments on five image classification benchmarks show substantial improvements over an observation-naive Hard-Neg baseline, particularly under sparse relation supervision.
Critical strengths
-
The paper makes a clear and important modeling distinction between an unrevealed same-class relation and an observed different-class relation. The proposed incomplete-similarity likelihood is well aligned with the assumed one-sided observation process, avoiding the potentially severe bias introduced by treating all unrevealed pairs as negatives.
-
The proposed formulation is technically clean and supported by a relatively complete theoretical analysis, including relation recovery, classification recovery up to permutation, finite-sample generalization, and reveal-rate-aware regularization. This gives the method a stronger theoretical foundation than a purely empirical weak-supervision approach.
Critical weaknesses
-
The practical significance of the proposed supervision setting is not sufficiently established. All experiments construct incomplete same-class relations synthetically from fully labeled image classification datasets, and the evaluation is limited to MNIST, FashionMNIST, KMNIST, CIFAR10, and STL10. The paper does not demonstrate a real application in which unlabeled instances, incompletely revealed positive relations, a known class prior, and a known number of classes naturally coexist. This makes it difficult to assess whether the proposed problem formulation addresses a broadly relevant learning scenario or mainly a carefully constructed synthetic setting.
-
The experimental baselines do not fully establish the advantage of PRIME over closely related weak-supervision approaches. The largest improvements are obtained over Hard-Neg, which treats every unrevealed pair as a negative relation and is therefore explicitly misspecified under the paper’s own data-generating assumption. While KCL, DCC, and unsupervised contrastive clustering are also included, the paper does not provide convincing comparisons with adapted methods from similar-pair learning, positive-unlabeled learning, or other closely related weak-supervision formulations. Consequently, it is unclear how much of the improvement reflects a genuinely stronger learning approach versus correcting an intentionally mismatched objective.
Questions for authors
-
Can the authors provide concrete real-world applications or datasets in which this supervision setting naturally arises, i.e., where only a subset of same-class relations is observed while instance labels are unavailable but the class prior and the number of classes are known? A real-data experiment would substantially strengthen the practical motivation of the work.
-
Can the authors provide comparisons with adapted methods from similar-pair learning or positive-unlabeled learning that operate under comparable information assumptions? In particular, it would be useful to determine whether PRIME still provides a clear advantage beyond the deliberately misspecified Hard-Neg baseline.
5 comments
Response to Comment 2:
We appreciate the reviewer's constructive feedback and suggestion to strengthen the comparison with related weakly supervised learning methods. To the best of our knowledge, existing methods do not directly address the exact combination of unlabeled instances, incompletely revealed same-class relations, and an aggregate class prior for multi-class classification. We therefore adapt two closely related methods to the available supervision setting.
Existing similarity-and-unlabeled (SU) learning methods, such as "Classification from Pairwise Similarity and Unlabeled Data" (Bao et al., ICML 2018), derive supervised-risk rewriting for binary classification. This risk rewriting cannot be directly applied to the multi-class setting considered here. To provide a comparable PU learning baseline, we adapt the non-negative risk estimator from "Positive-Unlabeled Learning with Non-Negative Risk Estimator" (Kiryo et al., NeurIPS 2017) to pairwise same-class relation prediction.
Specifically, Pair-nnPU treats revealed same-class pairs as positive examples and randomly sampled instance pairs as unlabeled examples. Using the classifier-induced similarity , the adapted risk is
where P and U denote the revealed same-class pair distribution and the unlabeled pair distribution, respectively. The coefficient a denotes the same-class pair prior, equal to the sum of squared class proportions under independent instance sampling.
We further incorporate the same permutation-invariant class-prior regularizer as PRIME:
Here, b denotes the prior-regularization coefficient, which is set to the same value as in PRIME.
Importantly, Pair-nnPU does not treat unrevealed relations as different-class observations. It also shares the same classifier architecture, pairwise similarity function, and prior regularizer with PRIME, while optimizing a different relational objective. This allows us to examine the effectiveness of the proposed incomplete-similarity likelihood beyond the benefit of correctly handling unrevealed relations.
We additionally include DSBC (ML-only), adapted from "Toward Balance Deep Semisupervised Clustering" (Duan et al., IEEE TNNLS 2025). This method retains its original clustering framework and uses only the revealed same-class relations as must-link constraints, without introducing cannot-link supervision.
As reported in Table 1, PRIME achieves higher mean ACC-Hungarian than Pair-nnPU in 9 of the 10 evaluated settings across five datasets and two reveal rates. On CIFAR10, PRIME achieves 81.22% and 89.33% at reveal rates of 0.2 and 0.5, respectively, compared with 79.70% and 86.02% for Pair-nnPU. The improvements are more pronounced on STL10, where PRIME achieves 89.08% and 98.50%, compared with 69.53% and 68.09% for Pair-nnPU. PRIME also outperforms DSBC (ML-only) across all evaluated settings.
These comparisons show that appropriately handling unrevealed relations is important, while the proposed incomplete-similarity likelihood provides additional empirical benefits over pairwise PU risk estimation under comparable supervision. Thus, PRIME's improvements extend beyond the observation-naive Hard-Neg baseline.
The additional baseline descriptions and experimental results are presented in Sections 5.1–5.2 and Table 1 of the revised manuscript.
Response to Author Rebuttal
Thank you for the detailed rebuttal and additional experiments. I appreciate the authors' efforts to address my concerns, particularly the inclusion of Pair-nnPU and the new evaluations on DanishFungi24 and DeepFashion. These additions strengthen the empirical evaluation and partially address my original concerns.
However, my main concern regarding the practical significance of the proposed learning setting remains. Although DanishFungi24 provides naturally observed positive relations, the experiments still rely on predefined classes and class priors derived from ground-truth annotations. It remains unclear how commonly this particular combination of supervision would arise in practice, or what advantages it offers over alternative supervision strategies.
Moreover, while the proposed likelihood is technically well motivated and the theoretical analysis is sound, I find the overall methodological novelty and broader implications somewhat limited. The additional experiments demonstrate improvements under the considered settings, but do not fully resolve my concerns about the significance and general applicability of the contribution.
Overall, I acknowledge the improvements made during the rebuttal, but I remain insufficiently convinced that the contribution meets the acceptance threshold for ICLR.
We thank the reviewer for the careful assessment and constructive feedback. We appreciate the recognition of the key distinction between unrevealed and genuinely different-class relations, as well as the technical formulation and theoretical foundations of PRIME.
We understand the concerns regarding the practical relevance of the proposed supervision setting and the need for stronger comparisons with closely related weak-supervision approaches. To address these issues, we have extended our evaluation to real-world image datasets, including naturally observed same-class relations in DanishFungi24, and introduced adapted baselines under comparable supervision assumptions. We provide detailed responses and supporting results below.
Response to Comment 1:
We appreciate the reviewer's valuable suggestion regarding the practical motivation of our work. The use of pairwise similarity as an alternative to explicit class labels has been explored in previous similarity-and-unlabeled (SU) learning studies, including "Classification from Pairwise Similarity and Unlabeled Data" (Bao et al., ICML 2018) and "Learning from Noisy Pairwise Similarity and Unlabeled Data" (Wu et al., JMLR 2022).
For example, in privacy-sensitive settings, individuals may be unwilling to disclose their opinions but willing to indicate whether they share the same opinion with another individual. Such feedback provides same-class relations without revealing explicit class labels. When only a subset of these relations is collected, the remaining relations are unobserved, which motivates the incomplete-similarity setting considered in our work.
To further evaluate PRIME on real-world data, we have added experiments on DanishFungi24 and DeepFashion In-shop. In DanishFungi24, multiple photographs from the same observation record naturally provide same-species relations, while relations between different observations remain unknown. We construct a 10-species task with 7,500 training images and 5,791 observed same-class pairs.
For DeepFashion In-shop, we consider a 16-category classification task and construct same-class relations from category annotations, with an average revealed degree of 50. In both datasets, the number of classes is predefined, and aggregate class priors are computed from training annotations without using instance-level labels as classification targets.
As reported in Table A.8, PRIME achieves 86.93% ACC-Hungarian and 0.7660 NMI on DanishFungi24, and 95.93% ACC-Hungarian and 0.9257 NMI on DeepFashion In-shop. These results demonstrate the effectiveness of PRIME on real-world image data with incomplete same-class supervision, covering both naturally observed relations in DanishFungi24 and controlled relational supervision in DeepFashion.
The experimental details and results are provided in Appendix A.7 and Table A.8 of the revised manuscript.