Partial Label Clustering

1 Introduction

Partial label learning (PLL) [Tian et al., 2023; Jia et al., 2023b; Xu et al., 2024; Jiang et al., 2024; Yang et al., 2025] is a significant weakly supervised learning framework, where each training example corresponds to a set of candidate labels, but only one of which is the ground-truth label. This form of weak supervision appears in a variety of real-world scenarios, e.g., web mining [Luo and Orabona, 2010], multimedia content analysis [Chen et al., 2018], and ecoinformatics [Liu and Dietterich, 2012]. Previous studies in PLL mainly focus on learning a multi-class classifier based on the available weak supervision [Wang et al., 2022; Jia et al., 2023c; Jia et al., 2024].

∗Corresponding author

However, in many real-world scenarios, obtaining enough training examples with candidate labels may be time and resource costly as it requires a large amount of manual annotation, while sufficient unlabeled samples are readily obtainable. Given the effectiveness of clustering methods in dealing with unlabeled samples, we believe that utilizing limited partial labeled samples and sufficient unlabeled samples for clustering is an effective solution for this scenario. However, how to effectively exploit the partial labels for clustering is still under-explored. The ambiguity of the candidate labels prevents existing constrained clustering methods [Jia et al., 2018; Jia et al., 2020a] from directly utilizing the ground-truth labels. A naive method is to adopt label disambiguation strategies [Wang et al., 2022; Jia et al., 2023c] to estimate the ground-truth labels, and then incorporate the estimated labels to constrained clustering methods. However, because of the limited effectiveness of existing methods in disambiguation, the performance improvement observed in experiments is marginal.

To address the above issue, we propose a novel method, named PLC (Partial Label Clustering), to take advantage of the available partial labels to construct a clustering model. Specifically, we first establish a weight matrix for examples based on their similarity in the feature space and perform label disambiguation based on the weight matrix to obtain label information. Then we use the label information to establish initial pairwise constraints for the examples, i.e., must-link and cannot-links and propagate the initial inaccurate pairwise constraints through the weight matrix to obtain dense and precise pairwise constraints. Moreover, these two types of constraints form an adversarial relationship which are augmented accordingly. The augmented pairwise constraints are also used to adjust the weight matrix, ultimately improving the quality of the weight matrix. Finally, we use the optimized weight matrix for spectral clustering (SC) to obtain clustering results. The entire model is formulated as a joint optimization problem and solved by alternating optimization. More importantly, we also theoretically prove that a better disambiguated label matrix can improve clustering performance.

Our contributions can be summarized as follows:

• For the first time, we propose the partial label clustering problem and leverage the information from both the feature space and the label space of labeled and unlabeled samples to address this problem.
• We theoretically prove that a better disambiguated label matrix can improve clustering performance, which indicates that utilizing label disambiguation to improve clustering performance is effective.
• Extensive experiments demonstrate that the proposed PLC method achieves superior performances than the constrained clustering, PLL and semi-supervised PLL methods.

2 RelatedWork

In this section, we briefly introduce the preliminary work and studies related to our PLC method.

Partial Label Learning. In PLL, we cannot access the ground-truth labels of training examples because the ambiguity of candidate labels poses a significant challenge. The main approach to solve this problem is to disambiguate the candidate label set. For example, some methods establish a parameter model based on the maximum likelihood criterion [Liu and Dietterich, 2012; Jin and Ghahramani, 2002] or maximum margin criterion [Nguyen and Caruana, 2008], and identify the ground-truth label through iterative optimization. [H¨ullermeier and Beringer, 2005] treats candidate labels equally and makes predictions through weighted voting based on the candidate labels of the example's neighbors. [Zhang et al., 2016a; Wang et al., 2022] construct the weighted graph of the feature space of examples for disambiguation, which utilizes the similarity of examples. [Feng and An, 2019; Jia et al., 2023c] construct the dissimilarity matrix for candidate labels to guide label disambiguation. Although the above PLL methods have achieved satisfactory outcomes, they need a large number of labeled examples for training to achieve the expected results, and perform poorly with a fewer number of labeled examples. To solve this problem, we introduce a constrained clustering model, achieving superior performance with a limited number of labeled examples and many easily available unlabeled examples.

Constrained Clustering. As an important type of semisupervised learning method, constrained clustering utilizes some supervision information to enhance clustering performance. Pairwise constraint is a kind of weak supervision, which represents whether two training samples belonging to the same class, i.e., must-links and cannot-links. Several methods have been proposed to exploit pairwise constraints in constrained clustering, for example, [Zhang et al., 2016b] performs low dimensional embedding of pairwise constraints through non-negative matrix factorization, [Jia et al., 2021] exploits the dissimilarity between pairwise constraints to improve the performance of constrained clustering, [Jia et al., 2023a] stacks the pairwise constraint matrix and affinity matrix into a 3-D tensor, and promotes the construction of the affinity matrix through global low-rank constraints. In addition, pairwise constraint propagation (PCP) methods [Lu and Ip, 2010; Jia et al., 2020b] are proposed to address the sparsity problem of pairwise constraints. However, how to effectively exploit the partial labels to construct a constrained clustering model is still under-explored.

3 The ProposedMethod

In this section, we propose the details of PLC, including weight matrix construction, label disambiguation, and pairwise constraint propagation. Afterwards, we integrate them into a unified optimization objective and solve it through alternating optimization.

3.1 Notations

Denote X = [x1, x2, ..., xn]⊤ ∈ Rn×d as the feature matrix, where n and d represent the number of examples and the dimension of features. Y = [y1 , y2 , ..., yn ]⊤ ∈ {0, 1}n×q represents the partial label matrix, where q is the number of classes and yij = 1 means that the j-th label is one of the candidate labels of the sample xi. Specifically, we only have the candidate labels for training examples, and for test examples, the set of candidate labels consists of all labels, i.e., ytest = 1q for all test examples xtest, where 1q is an all ones vector. Given a training set Dtrain and a test set Dtest, the goal of PLC is to construct a weight matrix W ∈ Rn×n representing the similarity of the examples for the dataset D = Dtrain ∪ Dtest. For any example xi in D, we construct the k-nearest neighbors of xi, i.e E = {(xi, xj)|xj ∈ KNN(xi), i ̸= j}.

3.2 ConstructingWeight Matrix

Given a dataset D and its corresponding neighbor set E, our objective is to derive a weight matrix W = (wij)n×n that adequately represents the similarities among the examples. This has been proven to be effective in PLL and SC [Zhang and Yu, 2015; Kang et al., 2018]. Considering that higher weights should be assigned to examples with higher similarity, the weight matrix W can be constructed by solving the following linear least square problem:

where 1n ∈ Rn is an all ones vector and 0n×n ∈ Rn×n is an all zeros matrix. Moreover, N ∈ {0, 1}n×n is defined as: nij = 1, if (xi, xj) ∈ E and nij = 0 otherwise, which indicates that wij ≥ 0 (∀(xi, xj) ∈ E) and wij = 0 (∀(xi, xj) /∈ E). The first constraint W⊤1n = 1n normalizes the weight matrix W and the second constraint 0n×n ≤ W ≤ N ensures the non-negativity of the weight matrix W, while simultaneously ensuring that the weight matrix has values only for the k-nearest neighbors. By solving Eq. (1), we can obtain a weight matrix 1 containing the similarities of examples in the feature space.

1 Strictly, when applied to clustering, the matrix W should be symmetric. To simplify the model, we ignore symmetry and will subsequently apply symmetry processing toW, i.e., (W+W⊤)/2.

3.3 Label Disambiguation

Denote F = [f 1 , f 2 , ..., f n ]⊤ ∈ Rn×q as the label confidence matrix, where fij represents the probability of the j-th label being the ground-truth label of sample xi. We initialize the label confidence matrix as follows: Fij = 1/ ∑j yij if yij = 1, otherwise Fij = 0. The similarity relationships of examples in the feature space should be consistent in the label space, i.e., if two samples are similar in the feature space, they are more likely to share the same ground-truth label. We leverage the weight matrix W to disambiguate the label confidence matrix F, which can be obtained by solving the following problem:

where 1q ∈ Rq is an all ones vector and 0n×q ∈ Rn×q is an all zeros matrix. After the label disambiguation process, we select the class with the highest label confidence of example xi as the pseudo-label y∗ i = argmaxj∈Y f ij .

3.4 Pairwise Constraint Propagation

Based on the pseudo-labels obtained from label disambiguation, we denote the set of must-links (MLs) as M and the set of cannot-links (CLs) as C. If two examples xi and xj have the same pseudo-label, i.e., y∗ i = y∗ j , then (xi, xj) ∈M, otherwise (xi, xj) ∈ C. Then the indicator matrices of the MLs and CLs can be defined as:

MLs and CLs essentially represent the relationships between sample classes, i.e., the similarity relationship and the dissimilarity relationship respectively. However, the initial similarity and dissimilarity relationships are imprecise. To address this issue, we propagate the similarity matrix S ∈ Rn×n and the dissimilarity matrix D ∈ Rn×n through the weight matrix W constructed in the feature space, i.e., if two samples are similar in the feature space, their similarity and dissimilarity codings should also be similar. Moreover, the similarity matrix S and the dissimilarity matrix D naturally form an adversarial relationship, i.e., if two samples have high (low) similarity, their dissimilarity should be low (high). Combining propagation and adversarial relationship together, we have the following objective:

where ⊙ represents the elementwise product and || · ||1 refers to the l1 norm, i.e., ||D⊙ S||1 = ∑ij DijSij. L ∈ Rn×n is the Laplacian matrix of weight matrix W, i.e., L = A - W, where A is a diagonal matrix with the i-th diagonal element

Algorithm 1 Pseudo-code of PLC

Input:

• D : the partial label training dataset {(xi,Yi)|1 ≤ i ≤ n}.
• k : the number of nearest neighbors.
• l : the number of clusters.
• α, β, γ : the hyper-parameters in Eq.(5) and Eq.(10).
• x∗ : the unseen test example for prediction.

Output:

• C : the clusters {C1,C2, ...,Cl}.
• 1: Construct partial label dataset of all samples D′ = D ⋃{(x∗ ,Y∗i )|Y∗i = 1q} ;
• 2: Initialize the weight matrixWby solving Eq. (1);
• 3: Initialize the label confidence matrix F by solving Eq. (2);
• 4: Initialize pairwise constraints according to Eq. (3);
• 5: Initialize the similarity matrix S and dissimilarity matrix D by solving Eq. (4);
• 6: repeat
• 7: for j = 1 to n do
• 8: Update the vector ˆwj ∈ Rk by solving Eq. (7);
• 9: end for
• 10: Update the label confidence matrix F by solving Eq. (8) or iteratively solving the subproblems as Eq. (9);
• 11: Update the matrix S and D by solving Eq. (10) with KKT conditions;
• 12: until convergence or maximum number of iterations being reached.
• 13: Perform SC on W to obtain the final clustering results C.
• 14: return the final clustering results C = {C1,C2, ...,Cl}.

Aii = ∑nj=1 Wij . α, β ≥ 0 are two hype-parameters to balance different terms. Through Eq. (4), we can enhance the accuracy and density of information in S and D by incorporating adversarial and propagation terms.

3.5 Overall Model

Combining the optimization problems mentioned above, the final optimization objective of our proposed PLC model can be summarized as follows:

3.6 Alternating Optimization

Since the optimization objective Eq. (5) consists of multiple linear and quadratic equations and has multiple optimization variables, it is difficult to optimize directly. In this subsection, we solve this problem through alternating optimization methods, i.e., alternately optimizing one variable and fixing the other variables until convergence or reaching the predetermined maximum iterations.

Update W With fixed F, S and D, the subproblem of variable W can be formulated as:

Eq. (6) can be separated column-wisely and we can optimize the j-th column vector W·j while fixing other column vectors. For the vector W·j, only k non-negative elements located in the neighborhood of the sample xj need to be updated. We can simplify the optimization vector W·j as ˆwj ∈ Rk . Denote thematrixO fj = [f j -f Nj(1) , f j -f Nj(2) , ..., f j -f Nj(k) ]⊤ ∈ Rk×q and the matrix O xj = [xj -xNj (1), xj -xNj (2), ..., xj - xNj(k)]⊤ ∈ Rk×d , where Nj(·) represents the k nearest neighbors of the sample xj. The subproblem of Eq. (6) can be reformulated as:

where G xj = O xj (O xj )⊤ ∈ Rk×k , G fj = O fj (O fj )⊤ ∈ Rk×k are two Gram matrices for feature vector xj and label confidence vector f j respectively. H·j = [H1j,H2j, ...,Hkj]⊤ ∈ Rk×1 , where Hij =∥ D·Nj(i) - D·j ∥22 represents the difference in dissimilarity encoding between the sample xj and the neighboring sample xi. K·j = [K1j,K2j, ...,Kkj]⊤ ∈ Rk×1 , whereKij =∥ S·Nj(i)-S·j ∥22 represents the difference in similarity encoding between the sample xj and the neighboring sample xi. Obviously, Eq. (7) is a standard Quadratic Programming (QP) problem and it can be efficiently solved by any QP tools.

Update F With fixed W, S and D, the subproblem of variable F is the same as Eq. (2). Note that ∑(xi,xj)∈E wij = 1, we can define T = WW⊤ +In×nW⊤1n×nW-2W, where In×n is an n-order identity matrix and 1n×n is an matrix of all ones. The Eq. (2) can be rewritten as:

This is also a QP problem, which can be solved by any QP tools. However, this QP problem contains nq variables and n(q + 1) constraints, which leads to excessive computational overhead when nq is large. According to [Zhang et al., 2016a], we can update the label confidence vector f j while fixing other vectors:

Eq. (9) is one of the subproblems for updating F with q variables and q + 1 constraints and it can be efficiently solved. Update S and D With fixed W and F, variable S and D can be updated simultaneously by solving Eq. (4). To handle the equality constraint efficiently, Eq. (4) is approximated as:

where P represents the position of PCs, and Pij = 1 if (xi, xj) ∈ M∪ C, otherwise Pij = 0. Eq. (10) is convex to S (or D) when D (or S) is fixed. We can introduce the Lagrange multiplier matrices ΦS ∈ Rn×n and ΦD ∈ Rn×n to deal with the non-negative constraint and the Lagrangian function is expressed as:

according to the Karush-Kuhn-Tucker (KKT) conditions, we have S ⊙ ΦS = 0 and D ⊙ ΦD = 0. Let ∂L/∂Sij = 0 and ∂L/∂Dij = 0, the updating formula are shown as follows:

After alternating optimization, we obtain a weight matrix that can fully represent the similarity relationship of the samples. Finally, we apply SC on the weight matrix W to get the final clustering results.

The overall pseudo-code of our PLC method is summarized in Algorithm 1 and the computational complexity analysis of Algorithm 1 can be found in Appendix C.

4 Theoretical Analysis

Theorem 1. Denote F ∈ [0, 1]n×q and W ∈ [0, 1]n×n as the label confidence matrix and the weight matrix to be optimized. Let FG and WG be the ground-truth label matrix and the optimal weight matrix under the ground-truth labels. We assume that WG is constructed on the premise that the ground-truth labels of neighboring examples are the same. Let λ be the smallest eigenvalue of F⊤GFG and ||∆W||F be the average distance of each corresponding position between

The proof can be found in Appendix B. From Theorem 1, we find that a smaller difference between F and FG can reduce the upper bound of ||∆W||F , indicating that better disambiguation results help achieve a better weight matrix, thereby improving clustering performance.In summary, we prove that, under some general assumptions, a better disambiguated label matrix improves clustering performance.

5 Experiments

5.1 Experimental Setup

Datasets To conduct a comprehensive evaluation of our proposed method, we compare our PLC method with other methods on both controlled UCI datasets and real-world datasets. The characteristics of controlled UCI datasets and real-world datasets can be found in Appendix D. Following the widelyused partial label data generation protocol [Cour et al., 2011], we generate the artificial partial label datasets under the controlling parameter r which controls the number of falsepositive labels. For each example, we randomly select r other labels as false-positive labels.

Compared Methods To demonstrate the effectiveness of our PLC method, we compare it with two baseline clustering methods, three state-of-the-art constrained clustering methods, five well-established PLL methods, and two semisupervised PLL methods. (1) Baseline clustering method: KMeans [Macqueen, 1967] and SC [Ng et al., 2001]. (2) Constrained clustering methods: SSC-TLRR [Jia et al., 2023a], DP-GLPCA [Jia et al., 2021] and SSSC [Jia et al., 2018]. (3) PLL methods: PL-KNN [Cour et al., 2009], PL-SVM [Nguyen and Caruana, 2008], DPCLS [Jia et al., 2023c], AGGD [Wang et al., 2022] and IPAL [Zhang and Yu, 2015]. (4) Semi-supervised PLL methods: SSPL [Wang et al., 2019]

and PARM [Wang and Zhang, 2020]. Each compared method is implemented with the default hyper-parameter setup suggested in the respective literature. Parameters for our PLC method are set as α, β ∈ {0.01, 0.1, 1}, γ = 10 and k ∈ {10, 15, 20, 25, 30, 40}.

Implementation Details For constrained clustering methods, we randomly sample the partial label examples based on the proportion ρ ∈ {0.05, 0.10, 0.15, 0.20, 0.30, 0.40} and the remaining samples are used as test data. For PLL and semi-supervised PLL methods, we randomly sample the partial label examples based on the proportion ρ ∈ {0.01, 0.02, 0.05, 0.10}. For each experiment, we implemented 10 times with random partitions and reported the average performance with the standard deviation. We used ACC and NMI as evaluation metrics. For detailed information, please refer to Appendix A.

5.2 Experimental Results

Comparison with Constrained Clustering Methods

Fig. 1 illustrates the ACCs and the NMIs of our PLC method compared to constrained clustering methods under different proportions of partial label training examples on synthetic UCI datasets. According to these figures, our PLC method ranks first in 88.9% (64/72) cases. Table 1 reports the ACCs of our PLC method compared to constrained clustering methods under different proportions of partial label training examples on real-world datasets. Our PLC method ranks first in 100% (24/24) cases. Moreover, we can find that constrained clustering methods perform poorly in some cases, and there is a decline in performance despite an increase in the proportion of partial labeled samples, indicating that constrained clustering methods are difficult to handle the ambiguous labels. In contrast, our PLC method performs better in most cases, indicating that the PLC method can effectively utilize the partial label samples to predict the unlabeled samples.

Comparison with PLL & Semi-supervised PLL Methods Table 2 reports the ACCs of our PLC method compared to PLL and semi-supervised PLL methods under different proportions of partial label training examples on real-world datasets. Our PLC method achieves superior performance against PL-KNN, PL-SVM, IPAL, PARM in 100% (16/16) cases, against SSPL in 93.75% (15/16) cases, and against AGGD and DPCLS in 87.5% (14/16) cases. We can find that our PLC method performs better in the case of fewer partial labeled samples than PLL methods and semi-supervised PLL methods, indicating that our PLC method is helpful in addressing the issue of insufficient partial labels.

More experimental results can be found in Appendix E. We also conduct a significance analysis to prove that our PLC method is significantly superior to the comparing methods. The results can be found in Appendix E.4.

5.3 Further Analysis

Ablation Study. In Table 3, we conduct an ablation study on Lost and MSRCv2 datasets with different proportion ρ ∈ {0.05, 0.10, 0.15, 0.20, 0.30, 0.40} to check the necessity of the terms involved in our method. Specifically, PLC-CW represents the PLC version that only utilizes sample features to construct a weight matrix and perform the SC, PLC-LD represents the PLC version that utilizes sample features and disambiguated partial labels to construct a weight matrix and perform SC, and PLC-SD represents the PLC version that utilizes pairwise constraint propagation to densify the initial pairwise constraint and perform SC. The results in Table 3 indicate that label disambiguation and pairwise constraint propagation are helpful in improving classification accuracy, and taking both into account is the best choice.

Parameter Sensitivity Fig. 2 reports the performance of our PLC method under different parameter configurations on datasets Lost and MSRCv2. According to Fig. 2, the performance of our PLC method is relative stable in the different settings of α and β (Fig. 2(a) and Fig. 2(b)). We can directly fix α, β = 0.1 in practice. In addition, the accuracy curves in Fig. 2(c) indicate that our PLC is relative sensitive to the parameter k. In practice, we find that setting a smaller k ∈ {10, 15} for small-scale datasets and a larger k ∈ {20, 30, 40} for large-scale datasets can improve the performance of our PLC method.

6 Conclusion

In this paper, we proposed a novel method named PLC. For the first time, we explore whether partial labels can help improve the performance of clustering methods. Specifically, we first construct a weight matrix based on the relationships in the feature space and disambiguate the candidate labels to estimate the ground-truth label. Then we establish the must-link constraint and the cannot-link constraint based on the disambiguation results. Finally, we propagate the initial pairwise constraints and form an adversarial relationship between these two constraints to improve clustering performance. Moreover, we theoretically prove that a better disambiguated label matrix improves clustering performance, confirming that using label disambiguation to enhance clustering performance is effective. Our PLC method achieves superior performance compared to conventional constrained clustering, PLL and semi-supervised PLL methods on both three synthetic datasets and four real-world datasets.

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China under Grants U24A20322 and in part by the Big Data Computing Center of Southeast University.