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

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.