acceptodds
Under review as a conference paper at ICLR 2027

Learning Multi-Class Classifiers from Incompletely Revealed Same-Class Relations

Abstract

We study multi-class classification from unlabeled instances, revealed same-class pairs, and an aggregate class prior, without instance-level class labels. The supervision consists of revealed same-class pairs, where each pair indicates that its two instances belong to the same class. We propose PRIME (Prior-Regularized Incomplete-Similarity Multi-Class Estimation), which constructs training pairs by sampling unlabeled instances and models the probability that a pair is revealed through the same-class similarity induced by the latent classifier under a class-independent one-sided reveal process. A permutation-invariant class-prior regularizer matches the predicted class marginal to the class prior up to permutation and constrains marginal latent-class usage. We prove that, when the ground-truth same-class relation is realizable by the induced pairwise function class, every population minimizer recovers that relation almost surely. When the latent output dimension equals the number of ground-truth classes, relation recovery determines the classifier up to a global class permutation. We further derive a uniform finite-sample generalization bound and establish permutation invariance and marginal-collapse exclusion. Experiments on five image benchmarks show that PRIME improves instance-level classification and pairwise relation recovery over observation-naive training, with larger gains when fewer same-class relations are revealed.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Weakly supervised learning, incomplete pairwise supervision, multi-class classification, class-prior regularization

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_yPUkOpenReview ↗
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
  1. 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.

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

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

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

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.

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 qf(x,x′)=f(x)Tf(x′)q_f(x,x')=f(x)^T f(x'), the adapted risk is

RnnPU=aEP[l+(qf)]+max(0,EU[l−(qf)]−aEP[l−(qf)])R_{nnPU}=aE_P[l_+(q_f)]+max(0,E_U[l_-(q_f)]-aE_P[l_-(q_f)])

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:

LPair−nnPU=RnnPU+bLpriorL_{Pair-nnPU}=R_{nnPU}+bL_{prior}

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.

Reviewer_yPUkOpenReview ↗

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.

Reviewer_5gyDOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
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 models the observation of same-class pairs through a one-sided reveal process and optimizes an incomplete-similarity likelihood. A permutation-invariant class-prior regularizer is introduced to constrain the predicted class distribution without requiring predefined class correspondences. The paper establishes population-level relation and classification recovery guarantees, together with a finite-sample generalization bound. Experiments on five image benchmarks demonstrate promising results, particularly under sparse relational supervision.

Critical strengths
  1. The distinction between unrevealed and genuinely negative relations is important for learning from incomplete pairwise supervision. The proposed one-sided observation model provides a principled way to address this ambiguity.

  2. The paper establishes population-level relation recovery, classification recovery up to permutation, and a finite-sample generalization bound. These results provide useful theoretical support for the proposed learning objective.

  3. Promising empirical performance. PRIME achieves strong results across five image benchmarks, particularly under low reveal rates. The evaluation of both instance-level classification and pairwise relation recovery provides complementary evidence of its effectiveness.

Critical weaknesses
  1. Insufficient comparisons with closely related learning approaches. The experiments mainly compare PRIME with an observation-naive baseline and several clustering methods. While these comparisons are useful, they do not fully establish its advantages over existing positive-unlabeled or pairwise weak-supervision approaches adapted to the same observation setting.

  2. The method assumes that same-class relations are revealed independently with a class-independent probability and that the aggregate class prior is available. These assumptions may not hold in realistic applications where relation availability depends on class identity or instance characteristics.

  3. Limited evidence of robustness under challenging class distributions. Although the main experiments show strong performance, the additional class-imbalance results indicate substantial sensitivity to the target prior and class distribution. This raises questions about the method's reliability beyond the relatively controlled benchmark settings.

Questions for authors
  1. (Most likely to change my score) Could the authors provide comparisons with stronger weakly supervised or positive-unlabeled pairwise learning approaches adapted to the same supervision setting? In particular, how much of PRIME's advantage comes from correctly modeling the one-sided reveal process rather than from the specific proposed objective and prior regularization? Such comparisons would substantially strengthen the empirical contribution. It can also address my concern: "The experiments are not sufficient to support theoretical innovation."

  2. The method assumes a class-independent reveal probability ρ\rho. How would PRIME behave if the reveal probability depended on the class or instance characteristics? Could the authors provide an analysis or experiment under nonuniform reveal mechanisms?

  3. The proposed framework requires an aggregate class prior, which may be difficult to obtain accurately in practice. How sensitive is PRIME to prior estimation errors, particularly under class imbalance? Could the authors clarify the performance degradation observed in the long-tailed setting and the role of the prior regularizer?

  4. The theoretical recovery guarantees rely on realizability of the ground-truth same-class relation and matching the latent output dimension to the true number of classes. How restrictive are these conditions in practical settings, and what behavior should be expected under model misspecification or an incorrect number of latent classes?

  5. In the sparse-relation experiments, the incomplete-similarity likelihood already achieves strong performance without prior regularization. Could the authors further clarify when the permutation-invariant prior term becomes essential, beyond providing improvements at the lowest relation budgets?

3 comments

We thank the reviewer for the thoughtful evaluation and constructive suggestions. We appreciate the recognition of PRIME's principled treatment of incomplete same-class relations, its theoretical recovery guarantees, and its promising performance under sparse relational supervision.

We also appreciate the concerns regarding comparisons with related weakly supervised methods, the assumptions on the reveal mechanism and class prior, robustness to class imbalance and model misspecification, and the role of prior regularization. To address these concerns, we have strengthened the empirical comparisons and conducted additional experiments and analyses, as detailed below.

Response to Comment 1:

We appreciate the reviewer's careful assessment of the empirical evaluation and the suggestion to include stronger comparisons. To better distinguish the contributions of the incomplete-similarity likelihood and prior regularization, we have added two weakly supervised baselines: Pair-nnPU and DSBC (ML-only).

Existing similarity-and-unlabeled (SU) learning methods, such as "Classification from Pairwise Similarity and Unlabeled Data" (Bao et al., ICML 2018), derive a supervised-risk rewriting for binary classification, which is not directly applicable to our multi-class setting.

We therefore adapt the non-negative PU risk estimator from "Positive-Unlabeled Learning with Non-Negative Risk Estimator" (Kiryo et al., NeurIPS 2017) to pairwise same-class relation prediction. Specifically, revealed same-class pairs serve as positive examples, while randomly sampled instance pairs serve as unlabeled examples. Using the classifier-induced similarity qf=f(x)Tf(x′)q_f=f(x)^T f(x'), the adapted risk is RnnPU=aEP[l+(qf)]+max(0,EU[l−(qf)]−aEP[l−(qf)])R_{nnPU}=a E_P[l_+(q_f)]+max(0,E_U[l_-(q_f)]-a E_P[l_-(q_f)])

Here, P and U denote the revealed same-class pair distribution and the unlabeled pair distribution, respectively. The coefficient a is 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:

LnnPU=RnnPU+bLpriorL_{nnPU}=R_{nnPU}+b L_{prior}

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 shares the same classifier architecture, pairwise similarity function, and prior regularizer with PRIME, while optimizing a different relational objective. This comparison therefore helps isolate the contribution of the proposed incomplete-similarity likelihood beyond the general benefit of correctly handling unlabeled relations.

We additionally include DSBC (ML-only), adapted from "Toward Balance Deep Semisupervised Clustering" (Duan et al., IEEE TNNLS 2025). This baseline retains its original clustering framework and uses only the revealed same-class relations as must-link constraints, without introducing cannot-link supervision.

As shown in Table 1 of the revised manuscript, PRIME achieves higher mean ACC-Hungarian than Pair-nnPU in 9 of the 10 evaluated settings across five datasets and two reveal rates. On STL10, PRIME achieves 89.08% and 98.50% at reveal rates of 0.2 and 0.5, respectively, compared with 69.53% and 68.09% for Pair-nnPU. PRIME also outperforms DSBC (ML-only) across all evaluated settings.

To further examine the contribution of prior regularization, we conducted additional ablation experiments. Figure 4 shows that the incomplete-similarity likelihood alone can achieve strong recovery under sparse relational supervision. Under feature-dependent revealing (Table A.5), adding prior regularization improves ACC-Hungarian from 39.42% to 89.71% on FashionMNIST and from 19.60% to 81.74% on CIFAR-10. The corresponding average numbers of active clusters increase from 4.33 and 2.33 to 10, respectively.

These results illustrate the practical contribution of prior regularization to class recovery and latent-class utilization under the evaluated conditions. Since Figure 4 and Table A.5 examine different experimental settings, their results reflect different finite-sample conditions rather than a universal requirement for prior regularization.

Together, these comparisons show that PRIME's improvements extend beyond correctly handling unrevealed relations. They provide additional empirical evidence for the effectiveness of the proposed incomplete-similarity likelihood, while the ablation results clarify the complementary role of prior regularization.

The additional baselines and comparisons are presented in Sections 5.1–5.2 and Table 1, while the prior-ablation results are reported in Figure 4 and Table A.5 of the revised manuscript.

Response to Comment 2:

We appreciate the reviewer's constructive suggestion to examine the class-independent reveal assumption. To address this concern, we have conducted additional experiments on FashionMNIST and CIFAR-10 under nonuniform reveal mechanisms, using three random seeds and matched clean settings.

We consider two nonuniform reveal mechanisms. Under class-dependent revealing, the classes are divided into two equally sized groups with reveal probabilities of 0.05 and 0.35, respectively, maintaining an average reveal rate of approximately 0.2. Under feature-dependent revealing, same-class pairs with higher feature similarity are more likely to be observed. In both settings, PRIME retains its original training objective with a single reveal rate of 0.2, without explicitly modeling the nonuniform observation probabilities.

As reported in Table A.4 of the revised manuscript, PRIME maintains performance close to the clean setting under feature-dependent revealing, with ACC-Hungarian changes of -0.19 and +0.59 percentage points on FashionMNIST and CIFAR-10, respectively. In contrast, class-dependent revealing leads to decreases of 18.51 and 12.62 percentage points on the two datasets.

These results indicate that PRIME is relatively robust to the tested feature-dependent reveal mechanism, even without explicitly accounting for variations in observation probabilities. However, substantial class-dependent differences in reveal probabilities can noticeably reduce classification performance. This identifies an important limitation of the current observation model, whose theoretical guarantees rely on class-independent revealing.

The experimental protocols and results are provided in Appendix A.6 and Table A.4 of the revised manuscript.


Response to Comment 3:

We thank the reviewer for highlighting the importance of reliable aggregate class-prior information, particularly under class imbalance. To further investigate this issue, we revisited the long-tailed MNIST experiment (imbalance factor 10, reveal rate 0.2) and evaluated different prior settings using the permutation-invariant regularizer defined in Eq. (2). All results are reported as mean ± standard deviation over three random seeds.

During this examination, we identified and corrected an inconsistency between the prior regularizer used in the original long-tailed experiment and its definition in Eq. (2). We have updated the corresponding results in Table A.2.

Without prior regularization, PRIME achieves 69.95 ± 0.48% ACC-Hungarian with seven active clusters. Using the empirical long-tailed prior substantially improves performance to 97.69 ± 0.06% and recovers all ten active clusters.

We further examine sensitivity to prior misspecification. When the empirical prior is perturbed with α = 0.2, ACC-Hungarian decreases to 87.30 ± 8.36%, while replacing it with a uniform prior yields 70.43 ± 0.34%.

These results demonstrate that accurate aggregate prior information can substantially improve both classification accuracy and latent-class utilization under class imbalance. At the same time, deviations from the true class distribution can reduce recovery performance, with the perturbed prior also exhibiting greater variability across runs. Thus, while prior regularization can be highly beneficial, its effectiveness depends on the accuracy of the supplied aggregate prior.

We have updated Table A.2 and the corresponding discussion in Appendix A.7 to clarify the effects of prior misspecification and class imbalance.

Response to Comment 4:

We appreciate the reviewer's thoughtful question regarding the assumptions underlying our recovery guarantees. The realizability and correct-cardinality assumptions provide sufficient conditions for exact population recovery. In practice, the number of classes may be specified by the application, while realizability depends on whether the classifier can adequately represent the underlying same-class relations.

To investigate class-cardinality misspecification, we conducted additional experiments on FashionMNIST with Ktrue=10K_{true}=10 and KmodelK_{model} set to 8, 10, and 12.

As reported in Table A.7, PRIME achieves ACC-Hungarian of 70.96 ± 5.31%, 89.97 ± 0.59%, and 87.25 ± 1.61%, respectively. Underestimating the number of classes prevents exact recovery of all distinct classes, whereas moderate overestimation retains relatively high accuracy, although some classes may be split across additional output coordinates.

We also compare PRIME with and without prior regularization under these settings. Without the prior term, ACC-Hungarian reaches only 33.15%, 33.05%, and 42.72%, respectively. Adding prior regularization substantially improves classification performance and increases the average number of active clusters to 8, 10, and 12, respectively.

For each value of KmodelK_{model}, we use a uniform prior matching the model output dimension. Thus, these experiments jointly examine class-cardinality misspecification and the corresponding prior specification, rather than isolating the effect of class cardinality alone.

Regarding realizability, when the true same-class relation cannot be exactly represented by the classifier-induced similarity, the learning objective can still seek an approximation within the model class. However, the exact population recovery guarantee no longer applies in this case.

These additional experiments characterize PRIME's empirical behavior when the assumed number of classes differs from the underlying data distribution. The corresponding results and experimental details are provided in Table A.7 and Appendix A.7 of the revised manuscript.

Response to Comment 5:

We appreciate the reviewer's insightful observation regarding the role of prior regularization. As established in Theorem 2, the incomplete-similarity likelihood is sufficient for population recovery under the stated assumptions, even when λπ=0\lambda_\pi=0. This is consistent with Figure 4, where PRIME achieves strong classification performance without prior regularization under sparse relational supervision.

The prior regularizer plays an additional role during finite-sample optimization by encouraging the predicted class marginal to match the given class prior up to permutation. This can be particularly beneficial when predictions concentrate on only a few latent classes.

To further investigate this effect, we conducted additional ablation experiments comparing PRIME with and without prior regularization. As reported in Table A.5, under feature-dependent revealing, adding prior regularization improves ACC-Hungarian from 39.42% to 89.71% on FashionMNIST and from 19.60% to 81.74% on CIFAR-10. The corresponding average numbers of active clusters increase from 4.33 and 2.33 to 10, respectively.

Together, Figure 4 and Table A.5 illustrate the complementary roles of the two objective terms. The incomplete-similarity likelihood can recover effective classifiers without prior regularization, while the prior term can substantially improve class allocation and classification performance under certain finite-sample training conditions.

These additional results and the corresponding experimental details are provided in Appendix A.6 and Table A.5 of the revised manuscript.

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

This paper investigates multi-class classification from unlabeled instances, incompletely revealed same-class relations, and aggregate class-prior information. The authors propose PRIME, which models the probability of observing a same-class relation through a one-sided reveal process and optimizes an incomplete-similarity likelihood based on classifier-induced pairwise similarities. A permutation-invariant class-prior regularizer is further introduced to encourage appropriate latent-class usage without requiring predefined class identities. The paper provides theoretical analyses of population-level relation recovery, classification identifiability up to permutation, finite-sample generalization, and reveal-rate normalization.

Critical strengths
  1. The paper addresses a meaningful weakly supervised learning problem with a clearly defined observation mechanism. Unlike conventional pairwise classification methods that directly treat observed relations as similarity labels, PRIME explicitly distinguishes unrevealed relations from different-class relations. This formulation appropriately captures the uncertainty associated with incomplete same-class supervision and provides a principled foundation for the proposed likelihood objective.

  2. The theoretical analysis provides useful support for the proposed learning framework. Proposition 1 and Corollary 1 establish the recovery of latent same-class relations and instance-level classifiers up to a global permutation under realizability assumptions. The paper further provides a finite-sample generalization bound and investigates permutation invariance, marginal-collapse exclusion, and reveal-rate normalization, contributing to the theoretical understanding of incomplete relational supervision.

  3. The experiments provide encouraging evidence of the method's effectiveness under different supervision levels. The evaluation covers five image benchmarks and considers instance-level classification, clustering quality, and pairwise relation recovery. In particular, Table 1 shows substantial improvements over Hard-Neg at low reveal rates, while Figure 4 investigates extremely sparse relation supervision. The supplementary experiments on class-prior perturbations and reveal-rate misspecification further enrich the empirical analysis.

Critical weaknesses
  1. Section 3.1 assumes that every same-class relation is independently revealed with a constant probability ρ\rho, while different-class relations are never revealed. However, real-world relational annotations may exhibit class-dependent observation probabilities, instance-dependent selection biases, or incorrectly revealed relations. Although Appendix A.7 examines misspecification of the overall reveal rate, these experiments do not address violations of the underlying class-independent and one-sided observation assumptions. The authors should consider class-dependent reveal probabilities, feature-dependent reveal mechanisms, and a controlled proportion of incorrectly revealed pairs to evaluate whether PRIME remains effective when the observation process deviates from its theoretical formulation.

  2. The compared baselines are relatively outdated, which may limit the strength of the empirical evaluation. It is recommended to include more recent competitive methods published within the last three years to better demonstrate the effectiveness of the proposed approach against current state-of-the-art techniques.

  3. Theorem 1 establishes a generalization bound for an empirical risk averaged over all unordered instance pairs, whereas the implementation optimizes the objective through sampled mini-batches and employs importance-corrected stratified sampling in the sparse-relation experiments. In particular, Figure 4 reports strong classification performance even at an average revealed degree of only 0.5, where many training instances may have no directly observed same-class neighbors. The current theoretical analysis does not explicitly characterize how the finite number and connectivity of revealed relations affect instance-level recovery. It would strengthen the paper to provide a sample-complexity analysis incorporating the revealed relation budget or, alternatively, controlled experiments varying the number of instances and revealed relations independently to clarify the conditions under which sparse supervision remains sufficient.

Questions for authors

Please carefully checking the weaknesses.

3 comments

We thank the reviewer for the careful evaluation and constructive feedback. We appreciate the recognition of the importance of distinguishing unrevealed relations from different-class relations, the theoretical analysis supporting PRIME, and the encouraging empirical results under incomplete supervision.

We also appreciate the concerns regarding the realism of the reveal mechanism, the competitiveness of the baselines, and the relationship between our theoretical analysis and sparse mini-batch training. To address these issues, we have conducted additional robustness experiments, introduced stronger baselines, and further investigated sparse relational supervision. We provide detailed responses below.

Response to Comment 1:

Thank you for this suggestion. We have added experiments on FashionMNIST and CIFAR-10 to evaluate PRIME under class-dependent revealing, feature-dependent revealing, and incorrectly revealed relations, using three random seeds and matched clean settings.

For class-dependent revealing, we assign reveal probabilities of 0.05 and 0.35 to two groups of classes, maintaining an average reveal rate of approximately 0.2. Compared with the clean setting, ACC-Hungarian decreases by 18.51 and 12.62 percentage points on FashionMNIST and CIFAR-10, respectively.

Under feature-dependent revealing, performance remains close to the clean setting, with ACC-Hungarian changes of -0.19 and +0.59 percentage points, respectively. When approximately 5% of observed relations are incorrectly revealed in the sampling distribution, ACC-Hungarian decreases by only 2.08 and 2.03 percentage points, respectively.

These results show that PRIME remains effective under the tested feature-dependent and mildly noisy reveal mechanisms, while substantial class-dependent observation bias can noticeably reduce recovery performance. Although our theoretical guarantees rely on the assumed observation model, these additional experiments clarify the empirical behavior and limitations of PRIME when the reveal mechanism is misspecified. The results are reported in Table~A.4 of the revised manuscript.

Response to Comment 2:

We appreciate the reviewer's suggestion to strengthen the empirical evaluation with more recent and competitive baselines. 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 weakly supervised approaches to our supervision setting.

Specifically, we have added Pair-nnPU, adapted from Positive-Unlabeled Learning with Non-Negative Risk Estimator'' (Kiryo et al., NeurIPS 2017), and DSBC (ML-only), adapted from the more recent Toward Balance Deep Semisupervised Clustering'' (Duan et al., IEEE TNNLS 2025). The former provides a pairwise PU-learning comparison under matched supervision, while the latter introduces a recent deep constrained clustering baseline.

For Pair-nnPU, revealed same-class pairs serve as positive examples, while randomly sampled instance pairs serve as unlabeled examples. We use the classifier-induced similarity qf(x,x′)=f(x)⊤f(x′)q_f(x,x')=f(x)^\top f(x') and adapt the non-negative PU risk with the same-class pair prior α=∑k=1Kπk2\alpha=\sum_{k=1}^{K}\pi_k^2. Pair-nnPU uses the same classifier architecture, pairwise similarity function, and permutation-invariant class-prior regularizer as PRIME. Thus, the comparison controls these components while evaluating different relational objectives. Importantly, unrevealed pairs are not treated as known different-class relations.

For DSBC (ML-only), we retain its original clustering framework and provide only the revealed same-class relations as must-link constraints. We do not introduce cannot-link constraints or infer different-class relations from unrevealed pairs. This adaptation allows DSBC to operate under the available relational supervision without providing additional pairwise labels.

As shown in Table~1 of the revised manuscript, PRIME achieves higher mean ACC-Hungarian than Pair-nnPU in 9 of the 10 evaluated settings across five datasets and two reveal rates. The improvements are particularly pronounced on STL10, where PRIME achieves 89.08% and 98.50% at ρ=0.2\rho=0.2 and ρ=0.5\rho=0.5, respectively, compared with 69.53% and 68.09% for Pair-nnPU. PRIME also outperforms DSBC (ML-only) across all evaluated settings.

These comparisons extend the empirical evaluation beyond the observation-naive Hard-Neg baseline. In particular, the comparison with Pair-nnPU provides evidence for the effectiveness of the proposed incomplete-similarity likelihood relative to an adapted pairwise PU objective under matched classifier architecture and prior regularization. The DSBC comparison further evaluates PRIME against a recent constrained clustering approach.

The additional baseline descriptions and results are presented in Sections5.1--5.2 and Table1 of the revised manuscript.

Response to Comment 3:

We appreciate the reviewer's careful observation regarding the relationship between Theorem 1 and sparse mini-batch training.

Theorem 1 establishes a generalization bound for the complete-pair empirical risk. In the sparse-relation experiments, we employ importance-corrected stratified sampling over revealed and unrevealed pairs. Conditional on the training instances UU and the observed relation set S+S^+, the mini-batch estimator satisfies EB[LISbatch∣U,S+]=RIS,nfullE_{B}[L_{IS}^{batch}|U,S^+]=R_{IS,n}^{full} Thus, the mini-batch loss is an unbiased estimator of the complete-pair empirical objective. However, Theorem 1 does not directly characterize finite-step optimization or instance-level recovery under a fixed number of revealed relations.

To further investigate sparse supervision, we conducted additional experiments on FashionMNIST, independently varying the number of training instances (n=10,000n=10{,}000 or 30,00030{,}000) and the number of revealed relations (M=5,000M=5{,}000 or 15,00015{,}000).

At a fixed budget of M=5,000M=5{,}000, increasing nn from 10,00010{,}000 to 30,00030{,}000 changes the average revealed degree from 11 to 0.3330.333, while test ACC-Hungarian increases from 85.56% to 86.43%. In the latter setting, 71.68% of training instances have no revealed neighbors, yet these instances achieve 87.23% training ACC-Hungarian under a shared Hungarian alignment. Increasing MM to 15,00015{,}000 at n=30,000n=30{,}000 further improves test ACC-Hungarian to 88.56%.

These results indicate that PRIME can learn an effective instance-level classifier even when the observed relation graph is highly sparse. The shared feature-based classifier allows information from revealed relations to generalize to instances without directly observed neighbors. Together with Theorem 1, these experiments provide a broader understanding of PRIME under incomplete and sparse relational supervision.

We have clarified the relationship between the theoretical and empirical objectives in Section 4.2, provided the sampling details in Appendix A.6, and reported the additional results in Section 5.2 and Table A.6.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.