Partial Label Learning with Dissimilarity Propagation guided Candidate Label Shrinkage
Authors: Yuheng Jia
Fuchao Yang
Yongqiang Dong
Venue: NeurIPS 2023 poster (2023)
Keywords: partial label learning
dissimilarity propagation
candidate label shrinkage
TL;DR: We propose a novel model to handle the partial label learning problem based on dissimilarity propagation.

Abstract: In partial label learning (PLL), each sample is associated with a group of candidate labels, among which only one label is correct. The key of PLL is to disambiguate the candidate label set to find the ground-truth label. To this end, we first construct a constrained regression model to capture the confidence of the candidate labels, and multiply the label confidence matrix by its transpose to build a second-order similarity matrix, whose elements indicate the pairwise similarity relationships of samples globally. Then we develop a semantic dissimilarity matrix by considering the complement of the intersection of the candidate label set, and further propagate the initial dissimilarity relationships to the whole data set by leveraging the local geometric structure of samples. The similarity and dissimilarity matrices form an adversarial relationship, which is further utilized to shrink the solution space of the label confidence matrix and promote the dissimilarity matrix. We finally extend the proposed model to a kernel version to exploit the non-linear structure of samples and solve the proposed model by the inexact augmented Lagrange multiplier method. By exploiting the adversarial prior, the proposed method can significantly outperform
state-of-the-art PLL algorithms when evaluated on 10 artificial and 7 real-world partial label data sets. We also prove the effectiveness of our method with some theoretical guarantees. The code is publicly available at https://github.com/Yangfc-ML/DPCLS.

Partial Label Learning with Dissimilarity Propagation guided Candidate Label Shrinkage
Yuheng Jial.3, Fuchao Yang', Yonggiang Dong
School of Computer Science and Engineering, Southeast University, Nanjing 210096, China 2 College of Software Engineering. Southeast University Nanjing 210096, China
Key Laboratory of New Generation Artificial Intelligence Technology and Its Interdisciplinary Applications (Southeast University), Ministry of Education, China
yhjia@ seu.edu.cn, yangfo@ vangfo@seu.edu.cor seu.edu.cn, dongyq @ seu.edu.cn
Abstract
In partial label learning (PLL), each sample is associated with group of candidate labels, among which only one label correct. The key of PLL. disambiguate the candidate label set to find the ground-truth label. To this end, we first construct constrained regression model capture the confidence the candidate labels, and multiply the label confidence matrix by its transpose to build second-order similarity matrix, whose elements indicate the pairwise similarity relationships samples globally. Then we develop semantic dissimilarity matrix by considering intersection of the candidate label set, and further propagate the initial dissimilarity relationships to the whole data set by leveraging the local geometric structure of samples. The similarity and dissimilarity matrices form adversarial relationship, which is further utilized to shrink the solution space of the label confidence matrix and promote the dissimilarity matrix. We finally extend the proposed model kernel version exploit the non-linear structure samples and solve the proposed model by the inexact augmented Lagrange multiplier method. By exploiting the adversarial prior, the proposed method significantly outperform state-of-the-art PLL algorithms when evaluated on 10 artificial and 7 real-world partial label data sets. We also prove the effectiveness of our method with some theoretical guarantees. The code is publicly available at https:/ //g:://iitii hggggtttbb.... wwwaanfff///CCCCCC
the complement
Introduction
Partial label learning (PLL) [14, 15, 17] is an emerging weakly supervised learning framework. In PLL, each sample is associated with set of candidate labels, among which only one is the ground- truth label. Different from conventional supervised learning, PLL avoids precisely annotating label on each sample, which greatly reduces the labeling cost. Accordingly, PLL has been applied to many real-world scenarios such as automatic image annotation [1, 20], web mining [9], and ecoinformatics [8].
Formally speaking, let X Rd be the d-dimensional feature space and (1, 9} be the label space with & labels. Given the partial label training set D ( 5;) 1 < < m), where x, E X a d-dimensional feature vector represent the i-th sample and S S y the associated candidate label set, among which only one label is correct. PL. aims to induce a multi-class classifier f X' + from D. which very challenging as the ground truth label of sample concealed in the candidate label set.
*Corresponding author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

The key to solving PLL is label disambiguation, i.e., identifying the ground-truth label of a sample from its candidate label set. For example, [6. 12] considered the ground -rrth label as a latent variable and identified it through an iterative refining procedure. [3] narrowed the candidate label set through a sparsity- -hased self-training procedure. Some works [19, 22, 23] leveraged the similarity relationship of samples in the feature space to disambiguation, i.e., samples are similar to each other in the feature space are likely to share the same ground-truth label. Recently, some researches exploited the label space to achieve label disambiguation [2, 7, 13J. For example. SDIM [2] first built a pairwise dissimilarity matrix through the candidate label sets, and then maximized the difference of the label confidence between two samples if their pairwise dissimilarity between them is large according to the constructed dissimilarity matrix. However, the dissimilarity matrix constructed by SDIM is predefined and relatively sparse, which depresses its effectiveness.
Realizing the effectiveness of the dissimilarity relationship in PLJ., we propose a novel PL.L method named DPCLS (partial label learning with Dissimilarity Propagation guided Candidate Label Shrink- age). Specifically, we first construct a semantic dissimilarity matrix by considering the complement of the intersection of the candidate label set, i..., if two samples do not share any common candidate labels, they must belong to different classes, and their semantic dissimilarity is large. The above constructed dissimilarity relationships are still sparse and fixed, we therefore propose to propagate the initial dissimilarity relationships to the whole data set by leveraging the local geometric structure of samples, i.e., if two samples are similar to each other in feature space, they are expected to share the similar dissimilarity codings. Second, to include the enhanced semantic dissimilarity matrix in design second-order similarity matrix by multiplying the label confidence matrix with its transpose. Under the ideal condition, the enhanced semantic dissimilarity matrix and the similarity matrix naturally form adversarial relationship, i.e., larger (resp. smaller) dissimilarity between two samples means a smaller (resp. larger) similarity between them. By exploiting this adversarial prior, the enhanced dissimilarity matrix can shrink the solution space of the label confidence matrix, and meanwhile, the similarity matrix induced from the label confidence matrix also contributes to build better dissimilarity matrix. We theoretically confirm the above statement under some general conditions. Furthermore, we extend our method to kernel version to model the non- non-linear structure of samples. The proposed model is finally formulated as a constrained regression problem with adversarial learning and graph regularization, which is optimized by inexact augmented Lagrange multiplier (IALM). Extensive experiments on artificial and real-world partial label data sets demonstrate the effectiveness of the proposed PLL method.
label disambiguation,
2 The Proposed Method
Basic Model
Let X [21, T2.-... ................................ ]m T E mxd denote the feature matrix, where m and d represent the number of samples and the dimension of features. Y = [y), '..... .ym] E {0, 1Jmxq represents the partial label matrix, where g is the number of classes. Moreover, Dij = 1 indicates that the j-th label is one of the candidate labels of the sample 24. Note that in the candidate label set, only one label correct.
To fulfill PLI. we first build the following constrained regression model
min F
|XW
Fl1;
A I
F1, 1m, 0mxq FY
where F E Rm is the label confidence matrix with F,, representing the probability of the j-th label being the ground-truth label for the i-th sample. W E Rdxx is the coefficient matrix that maps the feature matrix to the label confidence matrix F. To avoid over-fitting, we impose the widely-used squared Frobenius norm on W as the regularization term, which is introduced by X > O. 1, E RR.9 and 1m, E Rd are two all ones vectors, mmx; E Rmxx is an all zeroes matrix. The first constraint F1,- = 1m normalizes the label confidence vector for all samples. The second constraint Omxo S F < Y means each element of F is no less than O, and no more than the corresponding element of Y. which implies the ground-truth label of each sample must reside in the candidate label set and the label confidence of the non candidate labels must be O. We initialize the label confidence matrix as F, 1/E, Σ, Vij if yıy=1, otherwise F ey O.
By minimizing Eq. (1), we construct a linear regression model that maps the feature space to the label confidence F. We assume that the mapping from the features to the ground- -ruth label may
2

---

be easier, while that to the false-positive label residing in the candidate label set is relatively harder. Accordingly, optimizing Eq. (1) will help disambiguate the candidate labels and produce preliminary label confidence matrix by exploring the useful information in the feature space.
Dissimilarity Propagation guided Candidate Label Shrinkage To further exploit the valuable information in the label space, we first use candidate labels to construct a dissimilarity matrix Du E mm i.e.,
1. v.y =0 Doy
0, otherwise.
If V.V = 0, the i-th sample z; and the j-th sample zy do not share any common candidate labels, which means they must belong to the different classes. Otherwise, I; and 2, have chance to belong to the same class. Therefore, Du indicates the semantic dissimilarity of samples. We then multiply the label confidence matrix with its transpose to create a similarity matrix termed as FFT, whose (i,j)-th element indicates the similarity between and zj. As the semantic dissimilarity matrix Do and similarity matrix FF form an adversarial relationship. i.c., a larger (resp. smaller) element in Do implies a smaller (resp. larger) clement in FF", we use this adversarial prior to shrink the solution space of F by:
min Do @ FF
where ( denotes the element-wiss product of two matrices and || || represents the I norm (i.e., the sum of absolute values of all elements in matrix). Minimizing Eq. (3) ensues that the positive elements of Do and FF will lie in the different locations. Unfortunately, directly minimizing Eq. (3) cannot help produce a better label confidence matrix F, because Do is inferred from the candidate label set, and the (i, j)th element of Do is positive only when yeu) = 0, while F is upper bounded by Y. the jith element of FF is positive only when you * 0. That is the locations of the positive elements of Dn and FF are complementary.
To solve this problem, we propose to promote the initial dissimilarity matrix Do to produce a denser dissimilarity matrix D E TR by novel dissimilarity propagation method. Specifically, leverage the local geometric structure of samples to enhance Do- Note that each column of D (e.g.. a.,) can represent the dissimilarity relationships between a sample (e.g.. x;)) and the other samples. If two samples I; and 2, are close to each other in the feature space, their dissimilarity relationships (D. and D should also be similar. To capture the feature similarity, we build local geometric matrix S E R.xx using a radial basis function (RBF) kernel:
exp(- - =,) E
S.
(4)
0, otherwise,
where j E N; indicates that v, is k-nearest neighbor of z;, and a is hyyer-parameter controlling the bandwidth of the RBF kernel. Based on S, the dissimilarity propagation guided candidate label shrinkage module becomes
D OF > S. D. 1.,
(S)
S.L. 0mxm SD 1mxm: Diy = Dosj. if Doy 1.
The second term makes the highly similar samples in the feature samples share the similar dissimilarity codings. Moreover, Dij Doij if Doij = means the reliable semantic relationship should be retained in D. In order to make D a well-defined dissimilarity matrix, each element in D should lie in the range of [0,1]. J. Note that in Eq. (5), both and D are optimization variables. By minimizing Eq. (5), the enhanced semantic dissimilarity matrix will shrink the solution space of F and at the same time F will also help promote the quality of D by the adversarial term.
Model Formulation
Taking all the above considerations into account, the proposed model finally becomes:
min |XW~ - F + A || a D FF + (Tr((DDD))) W.F.D
(6)
s.t. F1, = 1m, 0m x < F < Y, 0mxm <DS 1mxm, D.y = Dus, if Doy 1,
where L mmm = Ds S is a graph Laplacian matrix, and Ds mpmxm is a diagonal matrix Σ Sig. Tr(:) returns the trace of a matrix. a, 3 > 0 are
with the i-th diagonal element Dsa- two hyper-parameters to balance different terms. By solving Eq. (6), the semantic dissimilarity is enhanced by a dissimilarity propagation process, and further utilized to shrink the solution space of the label confidence matrix by a novel adversarial prior.
3

---

3 Optimization and Setting
We adopt IALM to solve the problem in Eq. (6). To simplify Eq. (6), we introduce an auxiliary
matrix A D mmmx and equivalently rewrite it as
|XW- Fll. W + A O FF (TT(DDDD))
min W.F.D.A
S.L. F1, mm 0mxe 1 F S Y.D A, mm S S 1mxm Au = Doaj ; if Dos =1 1.
The solution of Eq. (7) can be obtained by solving the following augmented Lagrange equation:
[XW- F 1/ + FF + +TTT(DD" ( D A + 2/ | All
min W.F.D.A
2
s.t. FI,- Lm, Omxg S F 0mxm I A 1mxm A., Duxy, Dosy 1,
(8)
where 4 E " is the Lagrange multiplier matrix, 2 0 penalty parameter, and (:-)) returns the inner product of two matrices. We can optimize Eq. (8) by solving the following subproblems alternatively and iteratively.
W subproblem is formulated
min XW F
Kernel Extension
The linear mapping in Eq. (9) may fail to model the nonlinear relationship. Therefore, we extend the above model to a kernel-based non-linear version. Let 6(-) IR R denote the feature transformation that maps the origin feature space X to higher dimensional Hilbert space ((X). According to the Representer Theorem, W can be expressed as a linear combination of the input features, i.e., W = HH where H E R mmxx stores the combination weights. Then, we have (X) = KH, where
(xX (X) mm the kernel matrix and each element Kij- = K((,, J.)) Finally, the nonlinear version is represented as:
min KH +
KH),,,
(10)
where b E Rd is the bias term. When the first derivatives of H and b reach O, Eq. (10) is solved, i.e.
H K Amxxm 1m
1m 1
1 1F 1 H²K 1m).
(11)
m
where I E Rm denotes an identity matrix. In the experiments, we use the RBF kernel as the kernel function, i.e., K(z,, =
2/112/0 2), for our method and the compared ones.
2) F subproblem is written as
min F - PI -PI
A FF
(12)
S.L. F1, 1m, Omxa F
where P
KH 1 E R is the output matrix the model. Eq. (12) can be formulated as a standard quadratic programming (QP) problem, and solved by any QP tools. The detailed derivation process can be found in Section A of the supplementary file.
D subproblem represented
4
min (Tr
D
(13)
/
Eq. (13) reaches the minimum when its first-order derivative with respect D vanishes, leading to
D (nA- (28L + plmxm))
(14)
A subproblem is expressed as
min a
A O FF
+ #
D A +
(15)
s.t. 0 0mxm
A 5 1mxm: Aij Dou. if Dos 1.
Eq. (15) can solved weieel, i.e.,
(DD + oFF
A T
Ti To
(16)

---

Algorithm The Pseudo Code of the Proposed Method
Input: D: the partial label training set; X, ct k: the parameters of model; 3: unseen test sample
Output: y: the predicted lahel for sample
1: Construct the dissimilarity matrix Du according to Eq. (2) and the kernel matrix K [IC(2s,, 22 mm
2: Initialize D A + 0mxm: 14 10-4
while not converged do
4: Update H and b by Eq.(11) (11)
5: Update F by solving Eq. (12)
6: Update D by Eq. (14)
Update A by Eq. (16)
8: Update 4, by Eq. (17)
9: Check the convergence condition ||D - All < 10-8
10: end while
Return the predicted label I according to Eq. (18).
where T, Ti To are three thresholding operators in elementwise, i.e., T(Ciy) 1, Dosj (Ca) == min(1, Ciy). (C,) == max(0) (0, Ciy).
Finally, the Lagrangian multiplier matrix and are updated by
+ T + PDD A)
(17)
min((.1pp pmas),
where Mmux 1mmx=10000 10 a predefined upper bound for μ.. Model Prediction Given unseen test example u. our method predicts its label by
9 arg Σ Hx,(G, be.
(18)
The overall pseudo code of our method summarized in Algorithm 1, where it stops when [D Al 10-8, where || -1.00 denotes the infinity norm of matrix.
Hyper-parameter Settings of Our Method
Parameter À is used control the model complexity. A too large (resp. small) value of À will lead to under-fitting (resp. over-fitting). Therefore, we set A=0.55 for our method. Parameters a and / are used control the importance of the adversarial term and dissimilarity propagation term respectively, According to a number experiments, we fix 3 = 0.001 and select from (0.001, 0.01]. Parameter k controls the number of k-nearest neighbors. Following the previous works [16, 22], set k=10. Computational Complexity Analysis
The computational complexity of Algorithm 1 mainly determined by steps 4-7. Specifically, steps 4 and 6 involve the inversion of m x m matrices with the complexity of (mm)). Step 5 solves a QP problem, leading to the complexity of O(m2q Step 7 can efficiently solved by linear thresh- olding operations with the complexity of O(m²), Therefore, the overall computational complexity of Algorithm in each iteration O(2m² + m² + m²q²). More analysis about computational complexity can be found in Section A of the supplementary file.
4 Theoretical Analysis
where FG E _ and N E max are ground-truth label matrix and false-positive label matrix respec- fively. Let H = W N represent the family of functions for DPCLS, where the linear function (W.N) N) H. Suppose the complexity of W and the sparsity of N are upper bounded by e and e2 respectively, Le., [| f S 6 and [|N]] S 62. The Rademacher complexity of DPCLS with square
Theorem 1. The square loss function E of DPCLS can be rewritten as | XWI
loss & upper bounded as follow
Rs(E o H) 2V2q(vmmqe + +2)
(19)
Lemma 1. [11] Denote H be a family of functions and S = {#1, Z2, Im is set of fixed samples. Loss function is upper bounded by θ 2 0, then for any 8 > O. with probability at least 1 8, for all h H we have
(2/0)
C(h) S (s(h) Re o H) + 30
(20)
2m
5

---

where ((h) and (h) are generalization error and empirical error to h respectively.
The detailed proof of Theorem 1 given in the Section B of the supplementary file. According to Lemma and Theorem 1, we have
((N) (s(h) 2V2g( / muqei c2)
(2/
+ 3
(21)
m
2m
The Rademacher complexity is bounded by the sum of the complexity of classifier W and the sparsity of false-positive label matrix N. When the number of false-positive labels is small, which leads to better generalization performance. Moreover, more training samples (a larger m) will also promote the generalization performance.
Theorem 2. Denote F E {0, (0.1)mxo and D E {0, 1m the partial label matrix and the to be optimized semantic dissimilarity matrix. Let FG and D be the ground-truth label matrix and the ground-truth dissimilarity matrix. Suppose the smallest eigenvalue of D and L are > and XL be the average distance of each sample between FG F F) and A
respectively (Ap 2 0, AL 2 0). Let ||
|
and F (i.e., A
F be the average distance of each corresponding
position between D and D (i.e.,
m
D
D
Then we have
A
q
D D-
D 1|
2/
| |
\Bvm
(22)
Ap F S
FF - -FFFa
1
|L
Anm
The proof can be found in Section B of the supplementary file. From Theorem 2, we can find that the number of samples increases, the upper bound of Aelly decreases, which indicates that more training samples will push the partial label matrix to be close to the ground -round-truth one and achieve better PLL performance. Moreover, a smaller error between D and D implies a smaller upper bound of AF|| which indicates better dissimilarity matrix can help achieve better label
matrix. Similarly, a larger number of training samples will reduce the distance between D and D, and a smaller error between F and FG implies a smaller upper bound of ÂD suggesting better dissimilarity matrix. As summary, we prove that, under some general assumptions, a better dissimilarity matrix will help produce a better label matrix, and vice versa. Therefore, the rationality of the proposed adversarial prior is theoretically proved.
5 Experiment and Analysis
To demonstrate the effectiveness of the proposed model, we compared DPCLS with eight shallow PLL algorithms, which were configured by the suggested parameters in the literature, i.e., CLPL [1]. PL-SVM [12], PL-KNN [5], PL-DA [18], IPAL [22], AGGD [16], PL-CLA [13], SDIM [2]. Those methods were evaluated on 10 synthetic data sets and 7 real-world data sets, whose details can be found in Section C of the supplementary file. Three deep learning PLI methods RC [4], PRODEN [10], and CAVL [21] were also evaluated as comparison on the real-world data sets. Ten runs of 50%%50%% random train/test splits were performed on each data set, and the average classification accuracy and the standard deviation were recorded.
5.1 Performance on Synthetic Data Sets
Following the widely-used partial label data generation protocol [1], 10 synthetic data sets were used to generate artificial partial label data sets. Specifically, three parameters r,p, control the generation process, i.e., p controls the proportion of partial label examples, controls the number of calse-positive labels, and c controls the probability of a specific false- sise-posiivee label co-occurs with the ground-truth label.
Fig. I illustrates the classification accuracy of six data sets (Glass, Steel, Ecoli, Yeast, Optdigits and Usps) as the co-occurring probability varies from 0. to 0.7 with step-size 0.1 (p=1,-=1) In general, the proposed model clearly exceeds the compared methods with different e, and achieves the highest accuracy in 33 out of 36 cases. Moreover, increases, it is more difficult to distinguish the

---

OPCLS 1o
CLPL 4 PL-SVM
-
PL-KNN
PL-DA
-. IPAL
AGGD O PL-CLA IN A..... SDIM
Clace Bcatce Accuncy
Cas
645
35 d70 200000 pew36ll of coading
000-94912 pwb.Adi di Loppinglaad laod
100 1 (O3dd caapiiggaa
(a) Glass (p=1, 1=1)
Steel (p=1, r=1)
Ecoli (p= r=1)
Casiitation AccumUT
Cassiiation
6.8
Jre-areaving peruablly altee eaplongaae
drn-araanin prisaallyy thete raupliggaann)
(d) Yeast (==1,==))
(e) Optdigits (p=1, r=1)
(f) Usps (p=1, r=1)
Figure I: The classification accuracy of each algorithm as e increases from 0.1 to 0.7 with p=1, r=1.
Table 1: Classification accuracy (mean=std) of each comparing algorithm on four synthetic data sets as r increases from 3 to 6. e/o indicates whether the accuracy of DPCLS is statistically superior/inferior
to the compared algorithm according to the pairwise t-test at 0.05 significance level.
Data
DPCLS
CLPL
PL-SVM
PL-KNN
PL-DA
IPAL
AGGD
PL-CLA
SDIM
912+-008
+023
6664.003e
.655..025
782++0020
7793+.018
898 998++
8807
.177-.0/7
:019
.594-.034
.5774.057
768+.002
.7724.017
8855+.011
891--.015
Isolet
002
.535=.015
.543:1.070
6.18
.711:.016e
7790
8554
8845
84911.01+
.858
.525: .200
.452..0624
.645.1.020
.7331.020
.7761.011
.24:1.015e
.22.1.018
800:1.040
.7801.037
.262:1.04e
.24...033
347:1.01
.715:1.04
.764:.054
.735:1.055
.7441.044e
.77611.049
74311.01
.1961.052e
.216...33e
28871.02e
.6651..654
.730::065
.67311.066
.692.L.067
Orl
.73
.7041.032
.1581.029
.1891.027
.24:1.040
.5941.045
677:1.067
.0711.09
.22:1.056.
.669 .042
.6601
.1142.024
.1591.025
2189
$36.2.047
.646_.073
.545.1.500
.5561.053
.062+0007
.058+.007
006
.011
0024+.004
060+=009
056=.010
.055+-008+
047++0006
.057+.007
055+-007
055++009
.054-0009
.053+-000 007
.045+0005
Amazon
.055+.009
.050+-007
045+
.020+-005
.02+-0005
0050+0099
047++008
0044+-009
.037+-007
048+-009
.0424-007
.029
.020+-003+
044++009
.043-0008
337 -007
0007
,208
6.03+
.1154.017
.178:
2.82
.33==0009
.291 2009
.305+.000+
3261:
.009
.190
.1214.028
.170:10033
.282:.010
.325=
.284:1.01
.300
Bookmark
323 009
0010
11691.09
.11.1..25
.1891.051
.278:1.009
.319-000
.27:110100
.2981.001
.2211.009
2400=.10+
.1481.013+
.1031..29+ .186:1.043
.270...000 000..
.27611.00e
.295.1.007
dalse-positive label and the ground-truth label, and PLL becomes harder. Accordingly, the accuracies of all the PI.. algorithms decrease, but the performance advantage of the proposed method over the compared ones becomes more salient such as on Glass and Ecoli, which proves that our method is skilled in more challenging PLL tasks.
Table reports the classification accuracies of diffferent algorithms as r varies from 3 to 6 on four data sets (Isolet, Orl, Amazon, Bookmark) with more than 20 classes. Our method ranks first in 11 out of 12 cases, and ranks second in the remaining case. The improvements brought by our method are significant. For example, on Isolet with r = 6, our method improves the classification accuracy of the best comparison from 0.824 to 0.858. According to the pairwise t-test, our method significantly surpasses the compared ones in 103 out of 128 cases. Moreover, different methods have different characteristics and may fit different data sets. For example, CLPI. performs satisfactorily on Orl and Amazon, but badly on Isolet and Bookmark; AGGD is good at Bookmark, but not at Orl.
7

---

Table 2: Classification accuracy (meanzstd) of each algorithm real-world partial label data sets. e/o indicates whether the accuracy of DPCLS is statistically superior/iferroo to the compared algorithm according to the pairwise t-test at 0.05 significance level. "S" and "D" indicate shallow and deep PLL
methods respectively.
Type
Method
FG.NET
FG-NET3
FG-NETS
Lost
MSRCv2
BirdSong
Malagacy
Soccer Player
Yahoo! News
DPCLS
.07:2.009
A362.017
.862.011
.770:.024
.5572.014
.751.0099
.6762.004
.532:.002
626=.003 003
CLPL
.5811.09*
.1600006
.53811017e
1.51.
.3711.010
610:1012+
1.66
5441.004 .97=.002
PL-SVM
0524:010
357=002+
511::022+
.7882.078
.310=000+
682=.023
.644.001+
.5000002+
5462t000+
PL-KNN
038.1.05
022
.33.1.019
.3341.021
.3911.023
-573..007
007
.493 002.
.38
s
PL-DA
0422.004
.166=.050.
255+2.070
.3092000
A16=.022+
660
013+
6666
008+
.95==003+
394:
IPAL
0524:006
347=0015.
.102:006
.100.020
.24=2.24e
.722=.000
.211=:17+
.530+0005
618
07511.010
.4231.016
.6681.018
1.24
.593.
050w
.527
616:1.004
PL-CLA
0044.011
424+.020
511+:015+
0662002
470=.016+
.722=0012+
655+
.525=.003
606:t.00e
SDIM .073.1.09
.23
.66.1.019
.36.1.023
.4751.016
.724
.6431.007
.524_.003
.6071..044
RC
07211.009
0022
488
1881.0200
7226
.4461.099
.715 .09.
007
.664
004e
1.321.004
620
D
PRODEN
0711+0009
A13==016
.67=.025.
.7122.032
430=.019+
.7042001++
66542017
.528=000
.03:
CAVI. .071 071.1.006
.655 0200
488.1.021
L.700
.444 .013
.695 1.17 .68.1.039
.510 .04
.628 .014
Table 3: Win/tie/loss counts on the classification performance of DPCLS against each comparing algorithm on all data sets. D-PLL indicates the summary of deep learning PLL methods RC,
PRODEN and CAVL. (I), (II) indicate the summaries on synthetic data sets and on real-world data
sets respectively. "Total" denotes the summary on all the data sets.
CLPL
PL-SVM
PL-KNN
PL-DA
IPAL
AGGD
PL-CLA
SDIM
D-PLL
(1)
44/870
51/1/0
52/070
47/5/0
46/6/0
23/29/0
38/14/0
30/22/0
(1I)
8/1/0
9/0/0
9/0/0
9/0/0
8/1/0
7/2/0
7/2/0
7/2/0
21/6/0
Total
52/9/0
60/1/0
61/0/0
56/5/0
54/7/0
30/31/0
45/16/0
37/24/0
21/6/0
Different from them, the proposed method produces excellent performance on all the evaluated data sets, suggesting its robustness to different data sets.
Table 3 (row (I)) reports win/tie/loss counts between DPCLS and eight comparing algorithms on the synthetic data sets according to the pairwise t-test at the significance level of 0.05, where we can find that DPCLS statistically outperforms other algorithms in 79.6% cases (331 out of 416) and none of the algorithms can beat DPCLS significantly.
5.2 Performance on Real-world Data Sets
Real-world data sets were collected from various tasks and domains. As the average size of the candidate label set of FG-NET is large, which will cause low classification accuracy on the test set. Following [2. 16] we employed the mean absolute error (MAE) to further calculate two extra evaluation indicators MAE3 and MAE5 on FG-NET, i.c., the test examples are considered to be correctly classified if the difference between the predicted age and the ground-truth age is no more than 3/5 years.
Table 2 demonstrates the classification accuracies of different methods on the real-world data sets. It is obvious that our method ranks first in all cases when compared with shallow PLL algorithms. Moreover, according to the pairwise t-test, our method statistically outperforms PL-SVM, PL-KNN and PL-DA on all real-world data sets and statistically surpasses AGGD, PL-CLA and SDIM on six data sets except FG-NET. Furthermore, compared with the best comparisons, our method improves the classification accuracy from 0.494 to 0.557 on MSRCv2 and from 0.747 to 0.770 on Lost.
We also compare the classification accuracies of our method with three deep learning PLL methods RC, PRODEN, CAVL on the real-world data sets. Our method ranks first on six the data sets except Yahoo! News. Specifically, according to the pairwise t-test, our method statistically outperforms RC, PRODEN and CAVL on three real-world data sets (Lost, MSRCv2 and BirdSong). Furthermore, compared with the best comparisons of deep leraning PLL methods, our method improves the classification accuracy from 0.446 to 0.557 on MSRCv2 and from 0.715 to 0.751 on BirdSong. Therefore, we can conclude that our method shows competitive performance compared with the deep learning PLL methods.
8

---

Table 4: Ablation study of our method on the real-world partial label data sets.
FG-NET
Lost
MSRCv2
BirdSong
Malagasy
Soccer Player Yahoo! News
DPCLS
0077=0009
.770:.024
.5571.014
.7512.009
.6761.004
.532:.0002
.626=.003
DPCLS-LM
.0671.009e
652=.023
.3971.009
.5772.012+
.5871.014
.492:.002+
.44:..004
DPCLS-KE
008:1.009
-701=023+
.388:.014e
.595=.014e
.6744.009
.95=..02e
.63.1.004e
DPCLS-DP
.073=.010
667=-027
.4661.018*
.721:.014
.6122.011
.534+.00*
.6041.004e
(a) Ideal FF
(b) Original FF"
(c) FF DPCLS
(d) Ideal D
Original Do
(f) D by DPCLS
Figure 2: Visual comparison of the similarity matrix and the semantic dissimilarity matrix on data set Ecoli (r=1, r=1, e=.88). (a), (d) Ideal similarity matrix and semantic dissimilarity matrix; (b), (e) Initial similarity matrix FF and semantic dissimilarity matrix Do: (c), (f) The similarity matrix FF and the dissimilarity matrix D produced by DPCLS. The brighter color indicates larger value.
Table 3 (row (II) presents the win/tie/loss counts of the proposed method against the compared ones on real-world data sets according to the pairwise t-test at significance level of 0.05. On all the real-world data sets, DPCLS achieves significantly superior performance in 85.9% cases, and gets comparable performance in the remaining cases against the comparing algorithms. Taking both the synthetic data sets and real-world data sets into account, our method accomplishes significantly better performance in 80.8% cases, which indicates the excellent classification ability of our method.
5.3 Further Analysis
Visualization Fig. 2 visually compares the ideal, the original and the enhanced similarity matrix and semantic dissimilarity matrices on data set Ecoli r=1, <0..). Compared with the ideal similarity matrix, the value of each element in the original similarity matrix FFT is relatively small with many incorrect connections. Compared with the ideal dissimilarity matrix, the original dissimilarity matrix Do is relatively sparse, and many positive elements missed in Do- On the contrary, the similarity matrix and the dissimilarity matrix produced by DPCLS become denser, which are quite close to the ideal ones. Especially, when checking the areas highlighted by the red rectangle boxes, DPCLS can effectively recover the similarity relationship between samples in FFT, and many positive elements missed by D, have been recovered by method. The visual comparison illustrates that our method can produce much higher-qu qualltyy similarity and dissimilarity matrices, which is useful to find a high-quality label confidence matrix F and promote the performance of PLL.
Ablation Study In Table 4, we conduct an ablation study on the real-world data sets to check the necessity of the involved terms of our method. Specifically, DPCLS-LM denotes DPCLS without Dissimilarity Propagation and Kernel Extension, and DPCLS-KE and DPCLS-DP indicate DPCLS without Kernel Extension and without Dissimilarity Propagation respectively. From Table can find that both the kernel extension and the dissimilarity propagation are helpful in improving classification accuracy and taking both of them into account the best choice.
Conclusion
In this paper, we have presented novel PLL method. Specifically, we first construct similarity matrix based on the multiplication of the label confidence matrix and its transpose. Then, we develop a dissimilarity matrix by exploiting the label space, and further utilize the local geometric structure of the samples to enhance the dissimilarity matrix, i.e., propagating the initial semantic dissimilarity relationships to the whole data set. The similarity and dissimilarity matrices form an adversarial relation, and the proposed model takes advantage of this novel adversarial prior to shrink the solution space of the label confidence matrix, which contributes to find the correct label in the candidate label set. Extensive experiments and comparisons on artificial and real-world partial label data sets have validated the effectiveness of our approach.

---

Acknowledgments
This work was supported in part by the National Natural Science Foundation of China under Grant 62106044 and 62072100, in part by the Natural Science Foundation of Jiangsu Province under Grant BK20210221, and in part by the ZhiShan Youth Scholar Program from Southeast University under Grant 2242022R40015.
References
[1] Timothée Cour, Benjamin Sapp, and Ben Taskar. Learning from partial labels. Journal of Machine Learning Research, 12:1501-1536, 2011.
[2] Lei Feng and Bo An. Partial label learning by semantic difference maximization. In International Joint Conference Artificial Intelligence, pages 2294-2300, 2019.
[3] Lei Feng and Bo An. Partial label learning with self-guided retraining, In AAAI Conference on Artificial Intelligence, pages 3542 3229,, 2019.
[4] Lei Feng, Jiaqi Lv, Bo Han, Miao Xu, Gang Niu, Xin Geng, Bo An, and Masashi Sugiyama. Provably consistent partial-label learning. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, 2020.
[5] Eyke Hüllermeier and Jürgen Beringer. Learning from ambiguously labeled examples. Intelli- gent Data Analysis, 10(5):119-44) 439, 2006.
[6] Rong and Zoubin Ghahramani. Learning with multiple labels. Advances in Neural Information Processing Systems 15, pages 897-904, 2002.
[7] Changchun Li, Ximing Li, and Jihong Ouyang. Learning with noisy partial labels by simul- taneously leveraging global and local consistencies. In ACM International Conference on Information and Knowledge Management, pages 725-734, 2020.
[8] Li-Ping Liu and Thomas G. Dietterich. A conditional multinomial mixture model for superset label learning. In Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems, pages 557-565, 2012.
[9] Jie Luo and Francesco Orabona. Learning from candidate labeling sets. In Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems, pages 1504-1512, 2010.
[10] Jiaqi Lv, Miao Xu, Lei Feng, Gang Niu, Xin Geng, and Masashi Sugiyama. Progressive identification of true labels for partial-label learning. In International Conference Machine Learning, volume 119, pages 6500-65 1510, 2020.
[11] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, Foundations of Machine Learning. The MIT Press, 2nd edition, 2018.
[12] Nam Nguyen and Rich Caruana. Classification with partial labels. In ACM SIGKDD Interna- lional Conference Knowledge Discovery and Data Mining, pages 551-559, 2008
[13] Peng Ni, Suyun Zhao, Zhi-Gang Dai, Hong Chen, and Cui-Ping Li. Partial label learning via disambiguation. J. Comput. Sci. Technol., 36(3):590-606 2021.
[14] Cai-Zhi Tang and Min-Ling Zhang, Confidence-rated discriminative partial label leamiin. In Satinder Singh and Shaul Markovitch, editors, AAAI Conference Artificial Intelligence, pages 2611-2617, 2017.
[15] Yingjie Tian, Xiaotong Yu, and Saiji Fu. Partial label learning: Taxonomy, analysis and outlook. Neural Nenworks, 161:708-734, 2023.
[16] Deng-Bao Wang, Min-Ling Zhang, and Li Li. Adaptive graph guided disambiguation for partial label learning. IEEE Trans. Pattern Anal. Mach. Intell., 44(12))8796-881 2022.
10

---

[17] Haobo Wang, Ruixuan Xiao, Yixuan Li, Lei Feng, Gang Niu, Gang Chen, and Junbo Zhao. Pico: Contrastive label disambiguation for partial label learning. International Conference on Learning Representations, 2022.
[18] Wei Wang and Min-Ling Zhang. Partial label learning with discrimination augmentation. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1920-1928, 2022.
[19] Ning Xu, Jiaqi Lv, and Xin Geng. Partial label learning via label enhancement. In AAAI Conference Artificial Intelligence, pages 5557-5564, 2019.
[20] Zinan Zeng, Shijie Xiao, Kui Jia, Tsung-Han Han Chan, Shenghua Gao, Dong Xu, and Yi Ma. Learning by associating ambiguously labeled images. In IEEE Conference on Computer Vision and Pattern Recognition, pages 708-715, 2013.
[21] Fei Zhang, Lei Feng, Bo Han, Tongliang Liu, Gang Niu, Tao Qin, and Masashi Sugiyama. Exploiting class activation value for partial-label learning. In International Conference on Learning Representations, 2022.
[22] Min-Ling Zhang and Fei Yu. Solving the partial label learning problem: An instance- based approach. In International Joint Conference Artificial Intelligence, pages
2015.
[23] Min-Ling Zhang, Bin-Bin Zhou, and Xu-Ying Ying Liu. Partial label learning via feature-aware disambiguation. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1335-1344, 2016.


Reviews:
[{"review_id": "TSny5KsCvb", "reviewer": "Reviewer_sPwu", "summary": "The manuscript delineates an innovative method, termed as DPCLS, which is designed for partial label learning. In addressing the issue  - namely label disambiguation - the DPCLS method exhibits an amalgamation of similarity relationship and dissimilarity relationship in an adversarial manner that endows the method with superior performance in comparison to baseline methods. \n\nThe manuscript manifests commendable quality through its comprehensive and well-crafted approach toward partial label learning. The clarity is evident in the lucid and well-structured exposition of the proposed methodology. The originality lies in the adversarial learning of similarity and dissimilarity relationships, addressing the challenges posed in partial label learning. The paper's significance is underscored by its superior performance over baseline methods, along with its potential to inspire future research in this domain.", "questions": "Please find my comments on weaknesses.", "limitations": "Please find my comments on weaknesses.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. The DPCLS method's novelty is encapsulated in its adversarial learning manner of similarity and dissimilarity relationships, effectively addressing the unique challenges in partial label learning.\n\nS2. The paper employs a sound theoretical approach with clear and well-structured explanations of the methodology and its components.\n\nS3. The evaluation is comprehensive, with comparisons to baseline methods providing a compelling demonstration of the superior performance of the DPCLS method.", "weaknesses": "W1.  Although the paper provides a comprehensive explanation of the methodology, further technical insights regarding the implementation and specific algorithms within the DPCLS method would be beneficial. For example, does the order of Steps. 4-9 have an influence on the final performance? The auxiliary matrix $A$ needs more clarification, which is not easy to follow.\n\nW2.  The paper falls short in providing a detailed analysis of the limitations of the proposed approach, a factor that could be significant for future research and practical applications.\n\nW3.  Too many hyper-parameters in a method would somewhat degrade its quality.\n\nW4.  A more detailed exposition of existing methods related to this work, including their characteristics and potential biases or weaknesses, would enrich the manuscript.\n\nW5.  A clear motivation about real-world applications or potential application scenarios, would strengthen the practical significance.\n\nW6.  Some claims in Section 4 Theoretical Analysis need more clarifications, e.g., the number of training samples, and dissimilarity matrix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Thank you for your time and effort in reviewing our paper.**\n\n---\n\n**W1: Steps of Algorithm 1 and explanation of the auxiliary matrix $A$**\n\n**Answer to W1:**\n* **The effect of the different orders:**\nSteps 4-9 in **Algorithm 1** solve four subproblems, and the order of them will not affect the final performance empirically, as with different orders the algorithm stops only when it is converged [1, 2]. To validate this statement, we reversed the order of steps 4-7 and conducted experiments on data sets Lost, Ecoli ($e$=0.8) and Steel ($e$=0.8). The experimental results are shown in the following **Table RA1**, where we find the order of steps 4-9 will not affect the experimental results. \n* **Clarification on $A$**:\nThe variable $D$ in the initial problem (Eq. (6)) has many constraints ($\\mathbf{0}\\_{m\\times m} \\leq D \\leq \\mathbf{1}\\_{m\\times m}, D_{i j}=D\\_{0 i j}, \\text{if} D\\_{0 i j}=1$), making the $D$ subproblem very difficult to solve. To simplify the optimization, we introduce an auxiliary matrix $A$ and let $A=D$, and transfer some of the constraints on $D$ to the variable $A$. Then the initial problem in Eq. (6) equivalently becomes the problem in Eq. (7). Accordingly, the original subproblem regarding $D$ becomes two subproblems regarding $D$ (in Eq. (13)) and $A$ (in Eq. (15)), which are both easy to solve. More details can be found in the code, which has already been submitted to the appendix.\n\nAs suggested, we will provide more detailed explanations about the technical insights of **Algorithm 1**.\n\n---\n\n**Table RA1:  Origin order and reverse order classification accuracy**\n| Data set | Origin order | Reverse order|\n|:----:|:----:|:----:|\n| Lost | .770$\\pm$.024 | .770$\\pm$.024 |\n| Ecoli (e=0.8) |.832$\\pm$.014|.832$\\pm$.014|\n| Steel (e=0.8) |.638$\\pm$.022|.638$\\pm$.022|\n\n---\n\n**W2:  The paper falls short in providing a detailed analysis of the limitations of the proposed approach, a factor that could be significant for future research and practical applications.**\n\n**Answer to W2:** \\\nWe agree with the reviewer that every work has some limitations. For our work, one of the major limitations is the computation issue on large-scale data sets. Although in **Section A** of the **supplementary file** (Eq. (5)), we have made the solving of the QP problem regarding the $F$-subproblem more scalable. In our work, the sizes of the dissimilarity and similarity matrices are both $m\\times m$ with $m$ the number of the training samples, making the construction and the associated computation regarding them not scalable to the extreme large-scale data sets. In practice, we can remedy this issue by handling the data sets through mini-batches or an anchor graph. Nevertheless, the heavy computation burden on large-scale data sets is still a limitation of our work. In the final version of our paper, we will discuss this limitation in the **Conclusion** section.\n\n---\n\n**W3. Too many hyper-parameters in a method would somewhat degrade its quality.**\n\n**Answer to W3:** \\\nIn the second last paragraph of **Section 3**, we have discussed how to set the hyper-parameters of our method. Specifically, our method has 4 hyper-parameters $\\alpha$, $\\beta$, $\\gamma$ and $k$, **three of which are fixed ($\\lambda, k, \\beta$), and $\\alpha$ is selected from {0.001, 0.01}**. As a comparison, the compared methods like SDIM [3] have two hyper-parameters, where one is selected from {0.001, 0.005, ..., 0.5} and the other one is selected from {0.00001, 0.00005, 0.0001, ..., 0.1}. Therefore, our method does not need complex parameter tuning and can achieve better classification performance. Moreover, as shown in **Fig. S1** of the **supplementary file**, the performance of our method is robust to the hyper-parameters, making it quite easy to use in practice. \n\n---\n\n**W4: A more detailed exposition of existing methods related to this work, including their characteristics and potential biases or weaknesses, would enrich the manuscript.**\n\n**Answer to W4:** \\\nThank you for your suggestion. Please find the detailed **Related Work** in the **Global Response**. In the final version, we will add the detailed related works and discuss their characteristics.\n\n---\n\n**W5: A clear motivation about real-world applications or potential application scenarios, would strengthen the practical significance.**\n\n**Answer to W5:** \\\nThe research on PLL is initially motivated by several real-world problems. For example, in video face recognition, several persons may appear on a single frame with captions indicating their names. In this case, one person is annotated by several names as the candidate labels and only one name is the correct label for this person [4]. Please refer to **Fig. R1** of the **Global Response (PDF)** for more detailed real-world applications.  \\\nIn fact, some data sets used in the experiments were collected from real-world scenarios, such as the data set Birdsong from the bird song classification task, FG-NET from the facial age estimation task, and Lost from the automatic face naming from videos. \\\nIn the final version, we will show more real-world PLL applications to strengthen the practical significance. \n\n---\n\n**W6: Some claims in Section 4 Theoretical Analysis need more clarifications, e.g., the number of training samples, and dissimilarity matrix.**\n\n**Answer to W6:** \\\nThank you for your suggestion. $m$ denotes the number of training samples, and $D$ is the dissimilarity matrix. We will add detailed explanation for each variable in **Section 4** of the final version.\n\n---\n\n[1] 2021-TPAMI-Partial Multi-Label Learning with Noisy Label Identification \\\n[2] 2023-Tcyber-Prior Knowledge Regularized Self-Representation Model for Partial Multilabel Learning \\\n[3] 2019-IJCAI-Partial Label Learning by Semantic Difference Maximization \\\n[4] 2017-TKDE-Disambiguation-Free Partial Label Learning"}, {"review_id": "qdXTWEiiw0", "reviewer": "Reviewer_ysvn", "summary": "The paper proposes a new method for partial label learning called Dissimilarity Propagation guided Candidate Label Shrinkage（DPCLS）. The method captures the confidence of candidate labels by constructing a constrained regression model and uses the product of the label confidence matrix and its transpose to build a second-order similarity matrix. Additionally, the method constructs a semantic dissimilarity matrix by considering the complement of the intersection of candidate label sets and propagating the initial dissimilarity relationships throughout the entire dataset using the local geometric structure of the samples. The adversarial relationship between the similarity and dissimilarity matrices is further utilized to narrow down the solution space of the label confidence matrix and facilitate the construction of the dissimilarity matrix. The method is evaluated on artificial datasets and real-world partial label datasets, demonstrating superior performance compared to existing partial label learning algorithms.", "questions": "See the above.", "limitations": "See the above.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper introduces a unique combination of dissimilarity propagation and guided candidate label shrinkage for PLL, offering a fresh perspective on the problem.\n2. The authors present a detailed framework, including the construction of similarity and dissimilarity matrices, leveraging local geometric structures, and extension to a kernel version, providing a comprehensive solution for PLL.\n3. The proposed method is extensively evaluated on multiple artificial and real-world datasets, demonstrating its effectiveness and outperforming existing algorithms.", "weaknesses": "1. The structure and logic of the paper need further improvement. I recommend that the authors provide a clearer background and motivation in the introduction, enumerate the contributions of the paper, and provide an overview of the overall framework of the paper.\n2. In the setting of hyperparameters of the method, the authors do not provide a specific method or principle for parameter selection. For parameters λ, α, β, and k, the authors only mention fixed values or ranges without explaining how to choose these parameters to obtain optimal performance. It is recommended that the authors provide guidance or experimental results regarding hyperparameter selection.\n3. The paper has a limited number of references and lacks a comprehensive review of the latest research in the relevant field. I recommend that the authors conduct a more thorough literature search on the relevant field and provide more background and explanations of related studies in the introduction and related work sections.\n4. The proposed model involves constructing similarity and dissimilarity matrices and solving the problem using the augmented Lagrange multiplier method, which may result in higher computational complexity compared to simpler approaches. It is recommended to perform complexity analysis on the algorithm.\n5. In the conclusion section, the authors can further discuss the limitations of the proposed method and directions for future improvements to enhance the completeness of the conclusion. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Thank you for your time and effort in reviewing our paper.**\n\n---\n\n**W1: The structure and logic of the paper need improvement.**\n\n**Answer to W1:** \n\nThank you for your suggestion. In the final version, we will improve the introduction to make the logic clearer. Specifically, the **Background (Related Work)** and **Motivation** of our work are presented in the **Global Response**. The enumerated contributions and the overall framework of this paper are summarized as follows.  \n\n**Contribution and Novelty** of our work\n* We propagate the initial sparse semantic dissimilarity relationships to the whole data set, obtaining a dense and information-rich dissimilarity matrix. \n* We form an adversarial relationship between the enhanced dissimilarity matrix and the second-order similarity matrix constructed by the label confidence matrix, which helps shrink the solution space of the label confidence matrix. \n* The proposed model is extended to a kernel version to fit the non-linear structure of the samples and solved efficiently by an IALM-based algorithm. \n* We give some theoretical analyses and guarantees on the effectiveness of the proposed model.\n* Extensive experiments on real-world and synthetic data sets demonstrate the effectiveness of our model.\n\n**Framework** of our paper:  \\\nSection 1 briefly introduces PLL, motivation and the contributions of our work. Section 2 presents the proposed model, and Section 3 shows the optimization algorithm. Section 4 illustrates the theoretical analysis of the model. Section 5 reports the experiments and the associated analyses. Finally, section 6 concludes the paper.\n\n---\n\n**W2: Setting of hyperparameters.**\n\n**Answer to W2:** \\\n**First**, determining the best hyper-parameters is a challenging task for almost all machine learning models. However, as shown in the last second paragraph of **Section 3**, most of our hyper-parameters are fixed, suggesting the robustness of our model. \\\n**Second**, we determine the hyper-parameters based on the following principles. $k$ controls the number of k-nearest neighbors, and $\\lambda$ controls the model complexity. As they are commonly used parameters in many related methods [1, 2], we directly followed the settings of the related works and set $k=10, \\lambda=0.05$. $\\alpha$ and $\\beta$ introduce the adversarial term and the dissimilarity propagation term, and we set their values according to many experiments. In **Section D** of the **supplementary file**, we experimentally show their influence on the proposed model, and therefore fixed $\\beta$ = 0.001 and selected $\\alpha$ from {0.001, 0.01}.  \\\n**Finally**, if all hyper-parameters are carefully tuned, our algorithm can be further improved. Even with these fixed hyper-parameters, our model still statistically outperforms others in 85.9% cases (85 out of 99) on the real-world data sets.\n\n---\n\n**W3: Limited number of references and lacks a comprehensive review of the latest works**\n\n**Answer to W3:** \\\nAs suggested, we will enhance the references in the final version. Please refer to the **Global Response** for the comprehensive review of the related works.\n\n---\n\n**W4: Complexity analysis.**\n\n**Answer to W4:** \n* Actually, we have already analyzed the computational complexity of our algorithm and compared it with other PLL methods in **Table S1** of the **supplementary file**. For your convenience, we paste **Table S1** here. DPCLS solves a QP problem with the computational complexity of $\\mathcal{O}(m^3q^3)$, which is the same as many SOTA PLL methods like AGGD [2], SDIM [4], and PL-CLA [3]. \n* We also compared the actual running time of DPCLS with other baselines in **Table RA2**, where DPCLS is only slightly slower than the baselines but with a significant accuracy improvement. More analyses can be found in the supplementary file.\n\n---\n\n**Table S1: Computational complexity comparison between the linear regression based PLL methods.**\n|    |AGGD|PL-CLA|SDIM|DPCLS|\n|:----:|:----:|:----:|:----:|:----:|\n|Computational complexity|$\\mathcal{O}(m^3+mk^{3}+m^3q^3)$|$\\mathcal{O}(m^3+m^3q^3)$ |$\\mathcal{O}(m^3+m^3q^3)$|$\\mathcal{O}(2m^3+m^{2}+m^3q^3)$|\n\n---\n\n**Table RA2: Accuracy Vs. Time cost**\n|Data set|Type|AGGD|PL-CLA|SDIM|DPCLS|\n|----|----|----|----|----|----|\n|Glass $r=1, \\epsilon=0.8$|Accuracy|.491$\\pm$.063|.458$\\pm$.073|.508$\\pm$.073|.560$\\pm$.051|\n| |Time|2.63s|2.13s|2.25s|2.65s|\n|Ecoli $r=1, \\epsilon=0.8$|Accuracy|.801$\\pm$.033|.803$\\pm$.031|.801$\\pm$.028|.833$\\pm$.014|\n| |Time|3.34s|2.88s|2.88s|3.56s|\n|Lost| Accuracy | .702$\\pm$.024 |.696$\\pm$.021|.736$\\pm$.023|.770$\\pm$.024|\n| |Time|12.22s| 5.80s| 7.26s|22.03s|\n\n---\n\n**W5: Discuss the limitations of the proposed work**\n\n**Answer to weakness5:** \\\nWe agree with the reviewer that every work has some limitations. For our work, one of the major limitations is the computation issue on large-scale data sets. Although in **Section A** of the **supplementary file** (Eq. (5)), we have made the solving of the QP problem regarding the $F$-subproblem more scalable. In our work, the sizes of the dissimilarity and similarity matrices are both $m\\times m$ with $m$ the number of the training samples, making the construction and the associated computation regarding them not scalable to the extreme large-scale data sets. In practice, we can remedy this issue by handling the data sets through mini-batches or an anchor graph. Nevertheless, the heavy computation burden on large-scale data sets is still a limitation of our work. In the final version of our paper, we will discuss this limitation in the **Conclusion** section.\n\n---\n\n[1] 2018-IJCAI-Leveraging Latent Label Distributions for Partial Label Learning \\\n[2] 2022-TPAMI-Adaptive Graph Guided Disambiguation for Partial Label Learning \\\n[3] 2021-JCST-Partial Label Learning via Conditional-Label-Aware Disambiguation \\\n[4] 2019-IJCAI-Partial Label Learning by Semantic Difference Maximization\n"}, {"review_id": "8sShwfniVk", "reviewer": "Reviewer_vgJ9", "summary": "This paper constructs a second-order similarity matrix and a semantic dissimilarity matrix. The similarity matrix is obtained by leveraging the confidence obtained from the underlying model, while the semantic dissimilarity matrix is determined based on the label candidate set and the distribution of samples in the feature space. An objective function is formulated using the adversarial relationship between the similarity matrix and the dissimilarity matrix. Additionally, the paper proposes a version of the algorithm to handle nonlinear problems by mapping the original feature space to a high-dimensional reproducing kernel Hilbert space (RKHS). Finally, the proposed method is compared with several state-of-the-art PLL algorithms and validated on ten  synthetic datasets and seven real-world datasets.", "questions": "1.\tWhat was the motivation behind the author's paper? What problems in PLL did it solve?\n2.\tIf the relationship between two samples is characterized by both low confidence and low dissimilarity, can the loss term based on adversarial priors handle this situation?\n", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1.\tAn adversarial relationship is constructed for label disambiguation, and in addition, two versions are proposed: linear separable and non-linear separable.\n2.\tSolid theoretical analysis and ample amount of work.\n", "weaknesses": "1.\tThe research motivation of the paper is not clearly stated.\n2.\tThe paper mainly focuses on describing the proposed method, without summarizing and extracting issues from existing PLL research.\n3.\tThe principle behind the construction of the loss term based on adversarial priors is not explained.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Thank you for your time and effort in reviewing our paper.**\n\n---\n\n**W1: The research motivation of the paper is not clearly stated.** \n\n**W2: The paper mainly focuses on describing the proposed method, without summarizing and extracting issues from existing PLL research.**\n\n**Answer to W1 and W2:** \\\nThank you for your valuable comments and suggestions. Please refer to the **Global Response** for the detailed review of the **Related Work** and the summarizing of their issues in the **Motivation**.  In the final version, we will improve the related works and motivation in the introduction.\n\n---\n\n**W3: The principle behind the construction of the loss term based on adversarial priors is not explained.**\n\n**Answer to W3:** \\\nThe dissimilarity matrix $D$ represents the dissimilarities between samples, i.e., if the value of $D(i,j)$ is large, the sample $x_i$ is highly dissimilar to the sample $x_j$. While the similarity matrix $FF^T$ represents the similarities between samples, i.e., if the $(i,j)$-th element of $FF^T$ is large, $x_i$ is highly similar to $x_j$. Therefore, an adversarial relationship naturally exists between $D$ and $FF^T$. We, accordingly, formulate this adversarial relationship as \\\n $\\mathop{\\min}\\limits_{D, F}\\|\\|D\\odot F F^T\\|\\|\\_{1}=\\mathop{\\min}\\limits_{D, F}\\sum_{i, j=1}^{m}|D_{ij} \\cdot (FF^T)_{ij}|.$ \\\nBy minimizing the above equation, the adversarial relationship is captured and the solution space of the label confidence matrix $F$ is shrunk to achieve better label disambiguation. Besides, the quality of the dissimilarity matrix $D$ can also be enhanced. In the final version of the paper, we will explain the principle behind the adversarial prior clearer in the second paragraph of **Section 2**. \n\n\n---\n\n**Q1: What was the motivation behind the author's paper? What problems in PLL did it solve?** \n\n**Answer to Q1:** \\\nPlease refer to **Global Response** for the detailed motivation of our paper and the disadvantages of the exiting PLL methods. Here we summarize the motivation of our work simply. Exploiting the information in the label space is important to label disambiguation in PLL. The current methods leverage this information by constructing a semantic dissimilarity matrix [1, 2] like SDIM [1] and PANGOLIN [2]. However, the dissimilarity matrices constructed by them are very sparse (See the **Fig 2 (e)** of the paper, the initial dissimilarity matrix is sparse). Therefore, we propose to enhance the initial dissimilarity matrix by using the geometric structure between samples in the feature space. Moreover, the dissimilarity matrix and the similarity matrix constructed by the label confidence matrix form an adversarial relationship. We use this adversarial relationship to further enhance the dissimilarity matrix and more importantly, shrink the solution space of the label confidence matrix to achieve better label disambiguation. Our model can achieve superior performance than the comparing algorithms (experiments show that our algorithm achieves significantly superior performance on real-world data sets and synthetic data sets in 79.6% cases) and obtain a better dissimilarity matrix (See the **Fig 2 (f)** of the paper, the dissimilarity matrix produced by DPCLS become denser, which is quite close to the ideal one in **Fig 2 (d)**). Besides, we also theoretically prove the effectiveness of the adversarial term in **Section 4** of the paper.\n\n---\n\n**Q2: If the relationship between two samples is characterized by both low confidence and low dissimilarity, can the loss term based on adversarial priors handle this situation?**\n \n**Answer to Q2:** \\\nYes, our adversarial term can handle the situation when low confidence and low dissimilarity occur at the same time. Specifically, the loss of the adversarial term can be written as\\\n$\\mathop{\\min}\\limits_{D, F}\\|\\|D\\odot F F^\\mathsf{T}\\|\\|\\_{1}=\\mathop{\\min}\\limits_{D, F}\\sum_{i, j=1}^{m}|D_{ij} \\cdot (FF^T)_{ij}|$. \\\nWhen the confidence between $x_i$ and $x_j$ is low and the dissimilarity between $x_i$ and $x_j$ is also small, the values of both $ FF^T (i,j)$ and $D(i,j)$ are small. Accordingly, the value of the above objective function is also small. Therefore, the proposed adversarial loss can accept this uncertainty case (both low confidence and low dissimilarity).  \\\nOn the contrary, our adversarial term does not allow two samples to have both high confidence and high dissimilarity which will lead to a large objective function value. Therefore, the proposed adversarial term adopts a conservative strategy. The reason is that PLL is a weakly supervised problem, with insufficient supervision, we should allow some uncertainty cases exist (both low label confidence and low dissimilarity). Extensive experiments have demonstrated the effectiveness of the adopted adversarial strategy. And we also theoretically prove its effectiveness in **Section 4** of this paper.\n\n---\n\n[1] 2019-IJCAI-Partial Label Learning by Semantic Difference Maximization \\\n[2] 2020-CIKE-Learning with Noisy Partial Labels by Simultaneously Leveraging Global and Local Consistencies\n"}, {"review_id": "hVxt2knjo4", "reviewer": "Reviewer_9Zpk", "summary": "This paper proposes a new approach to partial label learning, called DPCLS, which learns the similarity and dissimilarity matrices to improve labeling accuracy in an adversarial relationship. The proposed method is compared to several existing methods on a variety of datasets, and the results demonstrate its superior performance in most cases. The paper also includes theoretical proof of the rationality of the proposed adversarial prior and a visualization of the enhanced similarity and dissimilarity matrices on a real-world dataset.", "questions": "1. In Fig.1 (c), compared with the co-occurring probability of 0.7, it confused me that the proposed method seems to get a better performance in the co-occurring probability of 0.8.\n\n2. The datasets adopted in the paper are simple and small-scale which is hardly convincing, and the moderately sized datasets are suggested to adopt to validate the effectiveness of the proposed method. For example, CIFAR-100.\n\n3. I am confused about the reported comparison results in Table 2: for the comparison method CAVL, there is a big performance drop between the reported experimental results and the CAVL paper. And can you compare the proposed method with the representative PLL method PiCO?\n\n4. For hyper-parameters sensitivity, the author should provide the variance in the figure.\n\n5. The motivation of the paper should be further explained in detail.\n", "limitations": "Please refer to the weakness and limitations", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper introduces a new partial-label learning method called DPCLS, which leverages similarity and dissimilarity matrices an adversarial relationship to effectively tackle the challenges associated with partial-label learning.\n\n2. A theoretical proof of the rationality of the proposed adversarial prior is included to further validate the proposed method’s effectiveness.\n\n3. Extensive experiments conducted on both real-world and artificial partial label datasets showcase the efficacy of the proposed method.\n", "weaknesses": "The paper focus on an interesting partial label learning problem and has several issues that can be improved: the datasets adopted in this paper are small-scale and the motivation of this paper should be explained in detail.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Thank you for your time and effort in reviewing our paper.**\n\n---\n\n**W1: Small-scale data sets and motivation of this paper**\n\n**Answer to W1**\n* **Motivation**: Thank you for your valuable comments and suggestions. Please refer to **Global Response** for the detailed **Motivation** of our work, and in the final version, we will improve the introduction to better describe the motivation of our work.\n* **Data sets**: To the best of our knowledge, _the largest real-world partial label data sets_ are Soccer Player (17472 samples and 279 dimensions) and Yahoo! News (22991 samples and 163 dimensions), which were both evaluated in our paper. Moreover, some recent partial label learning works adopt some larger-scale synthetic data sets. Therefore, in this rebuttal, we further evaluated our work on CIFAR-100 (60000 samples and 1024 dimensions). Please refer to **Q2** for the detailed experimental results on CIFAR-100.\n\n---\n\n**Q1: In Fig.1 (c), compared with the co-occurring probability of 0.7, it confused me that the proposed method seems to get a better performance in the co-occurring probability of 0.8.**\n\n**Answer to Q1:** \\\nThanks for your careful reading. Ecoli is a small-scale data set with 336 samples. Due to the influence of the random factors in producing the partial labels, the classification accuracy may fluctuate with the increase of the co-occurring probability ($\\epsilon$). But, the overall trend is clear that as the co-occurring probability increases, the classification accuracy will decrease. Note that a similar phenomenon also occurs in the original papers of LALO [1], SURE [2] and AGGD [3].\n\n---\n\n**Q2: Data sets.**\n\n**Answer to Q2:** \\\nBased on your suggestion, we conducted experiments on the CIFAR-100 data set (50000 training samples and 10000 testing samples). As CIFAR-100 is not a partial label data set, following the settings of the recent works [4, 5], we randomly flipped some negative labels to constitute the candidate labels with the probability $q$ ($q$ was set to 10%, 20%, and 30%). Then, we compare our method with two state-of-the-art deep learning based PLL algorithms: PICO[4] and CAVL[5]. As CIFAR-100 is an image data set, to get a good classification on it, we need some reasonable feature representation. Therefore, we use PICO to extract the features of CIFAR-100 and reduce the dimensions of it from 1024 to 128. Then, we apply the learned representation to our model. The comparison is shown in the following **Table RA3**, where we can see that our DPCLS still achieves better performance than SOTA PLL methods on CIFAR-100. To be specific, as $q$ increases, more false positive labels exist in the candidate label sets, and PLL becomes harder. Accordingly, the accuracies of the PLL algorithms decrease rapidly, but the performance advantage of our method becomes more salient, which proves that our method is skilled in more challenging PLL tasks. \n\n---\n\n**Table RA3: Classification accuracy (mean$\\pm$std) on CIFAR-100.**\n|Data set |CIFAR-100 $q=10$%|CIFAR-100 $q=20$%|CIFAR-100 $q=30$%|\n|:----:|:----:|:----:|:----:|\n|DPCLS|**70.07**|**64.60**|**34.23**|\n|PICO|68.60|62.50|27.55|\n|CAVL|58.80|21.83|12.27|\n\n---\n\n**Q3: Experiment results of CAVL and compared with PICO.**\n\n**Answer to Q3:** \n* **CAVL**: In the original CAVL[5] paper, **ten-fold cross-validation** was used on the real-world data sets, which consisted of 90% samples for training and 10% samples for testing. In our paper, **ten runs of 50%/50% random train/test splits** were performed on each data set, which consisted of 50% samples for training and 50% samples for testing. Different experimental settings result in different classification accuracy. \n* **PICO**: PICO [4] is designed for image classification (it involves data augmentation for images, such as image rotation, image resize, etc.), and cannot be directly evaluated on real-world data sets (the commonly used real-world PLL data sets are non-image data sets). In order to apply PICO on non-image data sets, the encoder of PICO is changed from ResNet to a multi-layer perceptron that is suitable for real-world data sets, and the image augmentation  (like image rotation, image resize, etc.) is changed to randomly mask 20% of the features as part of the augmented data. The experimental results are shown in **Table R1** of **Global Response (PDF)**. Compared with PICO, DPCLS achieves higher classification accuracy on the real-world data sets in 5/6 cases. \n\n---\n\n**Q4: For hyper-parameters sensitivity, the author should provide the variance in the figure.**\n\n**Answer to Q4:** \\\nThank you for your suggestion, we added **standard deviation** in the **Global Response (PDF) Table R2, Table R3 and Fig. R2 (c) and (d)**.  And we will add them to the **supplementary file** in the final version.\n\n---\n**Q5: The motivation of the paper should be further explained in detail.**\n\n**Answer to Q5:** \\\n**Motivation**: Please refer to **Global Response** for detailed **Motivation**, and in the final version, we will improve the introduction to better describe the motivation of our work.\n\n---\n\n[1] 2018-IJCAI-Leveraging Latent Label Distributions for Partial Label Learning \\\n[2] 2019-AAAI-Partial Label Learning with Self-Guided Retraining \\\n[3] 2022-TPAMI-Adaptive Graph Guided Disambiguation for Partial Label Learning \\\n[4] 2022-ICLR-PICO: Contrastive Label Disambiguation for Partial Label Learning \\\n[5] 2022-ICLR-Exploiting Class Activation Value for Partial-Label Learning\n"}, {"review_id": "E8Hj1KGBRA", "reviewer": "Reviewer_6Rie", "summary": "In this submission, authors propose a novel partial label learning method named DPCLS by realizing the effectiveness of the dissimilarity relationship. They develop a semantic similarity and dissimilarity matrix which form an adversarial relationship, which is further utilized to shrink the solution space of the label confdence matrix and promote the dissimilarity matrix.", "questions": "1. The submission does propose a partial label learning approach, but the motivation for proposing it is unclear. Why similarity and dissimilarity matrix? From this pespective, the novelty is very limited.\n2. Why $l_1$ norm in Eq.(3)? Some comparative experiments?\n3. The hyper-parameter $\\sigma$ in Eq.(4) is not given.\n4. According to Figure S1(a) and Figure S1(b) in supplementary material, the smaller the value of $\\alpha$, the better the performance (with some $\\beta$). Thus, it is suggested to do further ablation studies where $\\lambda$, $\\alpha$, $\\beta$ in Eq.(6) are respectively set to zeros.\n5. As shown in Algorithm 1, the proposed approach works in an iterative manner, so the convergence analysis should be conducted? How many rounds the approach will converge?\n6. As shown in Table 1, the traditional baseline CLPL achieves relative superior performance while the newest baselines only achieves relative general performance? Data sets matters?", "limitations": "Limitations are not discussed in the current version.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. Partial label learning is an interesting topic.\n2. A novel partial label learning approach is proposed.\n3. Experiments validate the effectiveness of the proposed approach.", "weaknesses": "1. The motivation is unclear and the novelty might be limited.\n2. The technical details of proposed approach can be further discussed.\n3. More experiments can be conducted to validate the effectiveness of the proposed approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Thank you for your time and effort in reviewing our paper.**\n\n---\n\n**W1: The motivation is unclear and the novelty might be limited.**\n\n**Answer to W1:** \n* **Motivation**: please refer to the **Global Response** for the **Motivation** of our work, and in the final version, we will improve the introduction to better describe the motivation of our work.\n* **Novelty**: The main novelties of our work are summarized in the response to **W1** of **Reviewer ysvn**. \n\n---\n\n**W2: Discuss the technical details of the proposed approach.**\n\n**Answer to W2:** \\\nPlease refer to **Q2**.\n\n--- \n\n**W3: More experiments.**\n\nFollowing your suggestion, we compared our method with an additional SOTA PLL method PICO [1] on the real-world data sets in **Table R1** of the **Global Response (PDF)**. PICO is designed for image classification (it involves data augmentation for images, such as image rotation, image resize, etc.), and cannot be directly evaluated on the real-world data sets (as the commonly used real-world PLL data sets are non-image data sets). To use PICO on non-image data sets, the encoder of it is changed from ResNet to a multi-layer Perceptron, and the image augmentation is changed to randomly mask 20% of the features as part of the augmented data. Compared with PICO, DPCLS achieves better performance in 5/6 cases.\n\n---\n\n**Q1: Motivation of our paper.**\n\n**Answer to Q1:** \\\nPlease refer to **W1 Motivation**.\n\n---\n\n**Q2: Why $l_1$ norm in Eq.(3)?**\n\n**Answer to Q2:**\\\nWe use the $\\ell_1$ norm mainly because of its excellent computational property. Specifically, as both the values of the dissimilarity matrix $D$ and similarity matrix $FF^T$ are limited to [0,1], the seemingly non-smooth $\\ell_1$ norm can be written as the trace of some multiplicated matrices ($\\|\\|D\\odot F F^\\mathsf{T}\\|\\|\\_1=trace(F^TDF)$), making the associated optimization regarding $D$ and $F$ feasible. The well-known alternative like the Frobenius norm will lead to a fourth-order optimization problem, which is quite difficult to optimize. Another alternative is the $\\ell_0$ norm, which is both non-convex and non-smooth. Therefore, we selected the $\\ell_1$ norm . Besides, minimizing the $\\ell_1$ norm fits the requirement of the adversarial prior, i.e., a larger element in $D$ indicates a smaller element in the corresponding position of $FF^T$ and vice versa. \n\n---\n\n**Q3: The hyper-parameter $\\sigma$ in Eq.(4) is not given.**\n\n**Answer to Q3:** \\\nThank you for the reminder. Following LALO [1], hyper-parameter $\\sigma$ is determined by **$\\sigma$=$\\sum_{i=1}^{m}||x_i-x_{i k}||_2/m$**, where $x_{ik}$ denotes the $k$-th nearest neighbor of $x_i$. The setting of $\\sigma$ is included in the code file. But as suggested, we will illustrate it in the last second paragraph of **Section 3**.\n\n---\n\n**Q4: Further ablation studies.**\n\n**Answer to Q4:** \\\nIn **Fig. S1 (a) and (b)**, the brighter color indicates a larger value. It can be observed that when $\\alpha$ ($\\beta$) decreases, the classification accuracy of DPCLS drops. To better present the experimental results, we convert the image into a table format, please refer to **Table R2 and Table R3** in the **Global Response (PDF)**, which show that when $\\alpha=0.01, \\beta=0.001$, DPCLS achieves the best performance on data sets Lost and MSRCv2. \n\nIn the following **Table RA4**, we show the performance of our model with $\\alpha=0$, $\\beta=0$ and $\\lambda=0$, respectively (Actually, the **Table 4** of our paper has shown the case of $\\alpha=\\beta=0$, which is denoted as DPCLS-DP.). The results in **Table RA4** prove the effectiveness of each term of our method. (Note that the experimental results of DPCLS $\\alpha=0$ and DPCLS $\\beta=0$ are the same, mainly because when $\\alpha=0$, the enhanced dissimilarity matrix will not affect the label confidence. And since the initial dissimilarity matrix and the similarity matrix are complementary, i.e., they are both constructed by the candidate label set, when $\\beta=0$, the dissimilarity matrix will also not affect the label confidence matrix. For more details please refer to line 98 of our paper.)\n\n**Table RA4: Ablation study**\n|Data set |FG-NET| Lost |MSRCv2|BirdSong|Malagasy|\n|:----:|:----:|:----:|:----:|:----:|:----:|\n|DPCLS|.077$\\pm$.009|.770$\\pm$.024|.557$\\pm$.014|.751$\\pm$.009|.676$\\pm$.004|\n|DPCLS $\\lambda=0$|.047$\\pm$.011|.267$\\pm$.088|.110$\\pm$.039|.393$\\pm$.110|.245$\\pm$0.11| \n|DPCLS $\\alpha=0$|.073$\\pm$.010|.687$\\pm$.027|.466$\\pm$.018|.721$\\pm$.014|.612$\\pm$.011|\n|DPCLS $\\beta=0$|.073$\\pm$.010|.687$\\pm$.027|.466$\\pm$.018|.721$\\pm$.014|.612$\\pm$.011|\n\n---\n\n**Q5: Convergence analysis of DPCLS.**\n\n**Answer to Q5:** \\\nOur algorithm solves the optimization problem in Eq. (7) of the paper with four blocks of variables, however, to the best of our knowledge, there is no general convergence proof for the IALM algorithm with more than two blocks of variables [2]. Fortunately, since each subproblem can be solved efficiently, our algorithm empirically converges well. The empirical curves can be found in the **Fig. R2** of the **Global Response (PDF)**. It is shown that our method converges within about 60 iterations.\n\n---\n\n**Q6: Why CLPL achieves relatively superior performance.**\n\n**Answer to Q6:** \\\nAccording to **Table 1**, CLPL achieves relatively good performance on Orl and Amazon data sets, but its performance was not as good as the newest algorithms on other data sets (See **Figure 1** and **Table 2** of the paper). Therefore, we think the observation in **Table 1** is due to the characteristics of the data sets. We will analyze this observation in **Section 5** of the final version.\n\n---\n\n[1] 2022-ICLR-PICO: Contrastive Label Disambiguation for Partial Label Learning \\\n[2] 2011-Foundations and Trends in Machine learning-Distributed optimization and statistical learning via the alternating direction method of multipliers. \n"}]

Author rebuttal:
Thanks to all the reviewers and the area chair for handling our paper and the valuable comments and suggestions to improve its quality. In the initial comments, we received 4 positive recommendations (1 Accept, 1 Weak Accept, 2 Borderline Accept) and 1 negative recommendation (1 Borderline Reject). In this **"Global Response"**, we will respond to two common questions posed by several reviewers, i.e., **"Related Work"** and **"Motivation"** of our work.

---

**To reviewers sPwu, ysvn and vgJ9**

**Related Work:**\
Partial label learning (PLL) [1, 2, 3] is an emerging weakly supervised learning framework. In PLL, each sample is associated with a set of candidate labels, among which only one is the ground-truth label. The key to solve the PLL problem is label disambiguation, i.e., identifying the ground-truth label of a sample from its candidate label set. We roughly divide the existing label disambiguation strategies into three categories. 

The first kind of methods [4, 5, 6, 7] leverages the similarity relationship of samples in the feature space to achieve label disambiguation. For example, [4] makes predictions by weighted voting on neighboring instances. [5] used graph regularization to disambiguate the candidate labels, i.e., if two samples are similar in features, they are likely to share the same ground-truth label. [6] adopted an adaptive graph structure to estimate label confidence, and the label with the highest confidence is regarded as the ground-truth label. [7] proposed discrimination augmentation for PLL by using the class prototypes. However, when the neighboring relationships and class prototypes of samples are inaccurate, the performance of this kind of methods will be degraded. 

The second kind of methods [8, 9, 10] uses the output of the model to guide label disambiguation. For example, [8] narrowed the candidate label set through a sparsity-based self-training procedure. [9] and [10] disambiguate the candidate label sets by the outputs of the deep neural network itself. However, the model output may be inaccurate (especially in the early stages of model training), which will result in performance degradation. 

The third kind of methods [11, 12] uses the information of the label space to achieve disambiguation. Especially, the information of the non-candidate labels that accurately indicates a sample does not belong to that set of labels is exploited. For example, SDIM [11] first proposed to use the dissimilarity relationship of samples in the label space (if two samples do not share any common candidate labels, they must belong to the different classes), and then maximized the label confidence between dissimilar samples to achieve label disambiguation. [12] guided the disambiguation by using the dissimilarity matrix and the class prototypes simultaneously, i.e., maximize the label confidence between dissimilar samples and reduce the label confidence of those with large distances from the class prototypes. Although these methods use the information of the label space, the constructed semantic dissimilarity matrix is sparse and predefined, which limits its applicability.

---

**To reviewers ysvn, vgJ9, 9Zpk and 6Rie**

**Motivation:**\
Like SDIM [11], our method belongs to the third category. The core idea of SDIM [11] is to use the constructed semantic dissimilarity matrix $D$ to guide label disambiguation. However, the dissimilarity matrix $D$ in SDIM is sparse and predefined. Especially with a larger candidate label set, $D$ will become extremely sparse, limiting the model performance. To solve this problem, we aim to construct a denser and information-rich dissimilarity matrix to help label disambiguation. Specifically, we propose to enhance the initial dissimilarity relationships to the whole data set by the local geometric structure of samples in the feature space, i.e., If two samples $x_i$ and $x_j$ are close to each other in the feature space, their dissimilarity relationships should also be similar. When the enhanced dissimilarity matrix is obtained, another problem is how to apply it to label disambiguation. As $D\in\mathbb{R}^{m \times m}$ indicates the pairwise dissimilarity relationships among samples, we further use the label confidence matrix $F$ multiplied by its transpose to construct a second-order similarity matrix $FF^T\in\mathbb{R}^{m \times m}$ among samples. The dissimilarity matrix $D$ and the similarity matrix $FF^T$ naturally form an adversarial relationship, i.e., a larger (resp. smaller) element in $D$ implies a smaller (resp. larger) element in $FF^T$. We formulate this adversarial prior as an $\ell_1$ norm minimization problem. By optimizing it, the enhanced dissimilarity matrix $D$ can shrink the solution space of the label confidence matrix $F$ to achieve label disambiguation, and meanwhile, the similarity matrix induced from the label confidence matrix also contributes to build a better dissimilarity matrix. Theoretical analysis in **Section 4** and empirical evaluation in **Section 5** demonstrate the effectiveness of the above approach.

---

[1] 2023-NN-Partial label learning: Taxonomy, analysis and outlook \
[2] 2022-ICLR-PICO: Contrastive Label Disambiguation for PLL \
[3] 2022-ICLR-Exploiting Class Activation Value for PLL \
[4] 2012-Intelligent Data Analysis-Learning from ambiguously labeled examples\
[5] 2018-IJCAI-Leveraging Latent Label Distributions for PLL \
[6] 2022-TPAMI-Adaptive Graph Guided Disambiguation for PLL  \
[7] 2022-KDD-Partial Label Learning with Discrimination Augmentation \
[8] 2019-AAAI-Partial Label Learning with Self-Guided Retraining \
[9] 2020-ICML-Progressive Identification of True Labels for PLL  \
[10] 2021-ICML-Leveraged Weighted Loss for Partial Label Learning \
[11] 2019-IJCAI-Partial Label Learning by Semantic Difference Maximization \
[12] 2020-CIKE-Learning with Noisy Partial Labels by Simultaneously Leveraging Global and Local Consistencies


Meta-review: The paper presents a dissimilarity propagation guided label shrinkage approach for partial label learning. The reviewers generally agreed that the proposed method makes a solid contribution to the addressed problem through rigorous theoretical analysis and extensive empirical study. There also exist several concerns in the reviews regarding motivation of study, usefulness of algorithm and completeness of literature survey as well. The authors managed to address some of these in their responses. After discussions, the reviewers reached a consensus that this is an interesting and technically sound paper where strengths outweigh weaknesses. We thus recommend that the paper can be accepted if space available in the program.
Decision: Accept (poster)