Label co-occurrence guided nonlinear disambiguation for partial multi-label learning

2.1. Partial label learning

In the field of weakly supervised learning, partial label learning (PLL)^[25-27] differs from both supervised and unsupervised learning. Its core objective is to identify a single ground-truth label for each instance from a set of candidate labels^[28]. In PLL, each candidate label set contains exactly one ground-truth label and several noisy labels. Existing PLL methods can be categorized into three strategies: label disambiguation, label transformation, and theory-driven methods.

Label disambiguation techniques primarily include mean-based methods and recognition-based methods^[29]. One type of mean-based method^[30] proposes a convex optimization approach, where predictions are obtained by averaging the model outputs over all candidate labels. Another method performs vote aggregation on the candidate label sets of neighboring samples of unseen instances^[31-33]. Recognition-based PLL methods^[34-36] treat the ground-truth label as a latent variable and infer the most probable label by constructing a parametric model. In recent years, this approach has been integrated with advanced representation learning techniques such as contrastive learning^[37] and graph neural networks^[38].

The label transformation strategy^[39,40] aims to mitigate the impact of false-positive labels on the candidate set. Theory-driven methods focus on the theoretical foundations of PLL, addressing core issues such as statistical consistency^[41-43]. Additionally, PLL research has been extended to scenarios including class imbalance, multi-view learning, online learning, high-dimensional data, and dimensionality reduction.

The essence of label disambiguation lies in extracting ground-truth label information by evaluating the credibility of candidate labels. Furthermore, PML significantly increases problem complexity, as the number of ground-truth labels in each candidate label set is unknown, whereas PLL assumes a single ground-truth label.

2.2. PML

PML addresses the scenario in which each training instance is annotated with a candidate label set that contains both ground-truth labels and irrelevant noisy labels^[7]. A naive strategy is to treat all candidate labels as correct and apply conventional MLL algorithms such as ML-KNN^[9]. However, the presence of noisy labels severely degrades the performance of such approaches. To overcome this limitation, numerous PML methods have been developed, which can be broadly categorized into two paradigms: two-stage disambiguation methods (TDM) and unified framework methods (UFM).

3.1. Learn nonlinear relationships

LRR^[54,55] addresses the subspace clustering problem by identifying the inherent subspace structures of the dataset X. The objective of LRR is to find a minimal-rank approximation of X using a suitable dictionary^[18], which can be formulated as follows:

Here, λ > 0 is a regularization parameter, E ∈ ℝ^d×n represents the reconstruction error, ||Z||_* denotes the nuclear norm, and ||E||_2,1 = Σ_j=1ⁿ(Σ_i=1^d(E_ij)²)^1/2. The matrix Z, obtained by solving Equation (2), approximates a block-diagonal form, where instances with high similarity are grouped into the same subspace, and the magnitudes of the representation coefficients for similar instances are relatively large.

The equality constraint in Equation (2) can be rewritten as E = X - XZ. Consequently, the LRR optimization problem defined in Equation (2) is equivalent to the following formulation:

Introducing an auxiliary matrix P = I - Z ∈ ℝ^n×n allows us to express ||X - XZ||_2,1 from Equation (2) as ||X - XZ||_2,1 = ||X(I - Z)||_2,1 = ||XP||_2,1 = Σ_i=1ⁿ||Xp_i|| = Σ_i=1ⁿ(p_i^TX^Tp_i)^1/2, with P = [p₁, …, p_n], where p_i ∈ ℝⁿ is the i-th column vector of P for i = 1, …, n. Therefore, the formulation in Equation (3) can be reformulated as:

After this reformulation, once the LRR formulation in Equation (2) is transformed into Equation (4), the dataset {x_i}_i=1ⁿ is represented solely through inner products (i.e., x_i^Tx_j) within the expression X^TX. This property naturally allows the incorporation of kernel methods. Specifically, the subsequent nonlinear adaptation of LRR is obtained by substituting X in Equation (2) with Ψ(X):

Within this framework, Ψ(X) = [Ψ(x₁), …, Ψ(x_n)] denotes the feature mapping, with Ψ being the transformation Ψ: ℝ^d → $$ \mathcal{F} $$. The resulting space $$ \mathcal{F} $$ is called the feature space. We define the kernel matrix K ∈ ℝ^n×n as K = Ψ(X)^TΨ(X). In addition, we define a function g(P) for P ∈ ℝ^n×n as:

where p_i ∈ ℝⁿ is the i-th column vector of P for i = 1, …, n. Then Equation (5) can be reformulated as:

The kernel matrix K, incorporated into g(P), plays a crucial role. It is worth noting that using a linear kernel, i.e., K = X^TX, reduces the formulation in Equation (7) to that of Equation (2), making LRR a special case of linear kernel methods. Kernel techniques facilitate the detection of complex nonlinear patterns and interactions in the dataset. This is achieved by projecting the data from the original space into a Reproducing Kernel Hilbert Space (RKHS), thereby improving the representation for the target task. With the kernel, nonlinear data structures can be effectively mapped to linearly separable subspaces in the feature space. Consequently, this allows for a comprehensive assessment of similarity between instances. Dissimilar instances, in contrast, are assigned to different subspaces with minimal cross-representation values. As a result, the learned LRR captures instance similarity, where a larger z_ij indicates a stronger affinity between x_i and x_j.

3.2. Learning label affinity matrix

In PML, exploiting inter-instance relationships can facilitate more accurate label disambiguation. For example, if similarity assessment is based solely on feature distance, instances x_i and x_j might appear similar^[56,57], yet they could belong to different classes due to the empty intersection of their label sets, i.e., S_i ∩ S_j = Ø. Therefore, incorporating candidate label information helps mitigate the influence of feature-based nearest neighbors with inconsistent labels. Additionally, when instances have overlapping labels but dissimilar features, excluding these shared labels can aid the disambiguation process.

However, the standard Jaccard similarity treats all labels equally and ignores the implicit label hierarchy commonly observed in real-world datasets. To address this limitation, we propose a weighted Jaccard distance that incorporates label weights derived from the label data itself, without requiring additional prior knowledge.

Given the label matrix Y, we calculate the weight ω_j of each label j (j = 1, 2, …, m) based on two statistical properties of the matrix. First, we consider the label frequency f_j, which is the number of instances annotated with label j and corresponds to the sum of the j-th row of Y, i.e., f_j = Σ_i=1ⁿY_j,i. We define the frequency score as:

Next, we introduce the label co-occurrence rate, which represents the proportion of other labels that co-occur with label j (i.e., labels that are simultaneously 1 with j in at least one instance). To compute this rate, we first construct the co-occurrence matrix Co ∈ ℝ^m×m, where Co_j,k = Σ_i=1ⁿY_j,i × Y_k,i denotes the number of instances in which labels j and k co-occur. We denote the co-occurrence rate as c_sc,j, and it is calculated as:

The final label weight is obtained by combining the frequency score and the co-occurrence rate using a balancing parameter η. We first compute the initial weight as initial_ω_j = η·f_sc,j + (1 - η)·c_sc,j, and then normalize these initial weights so that they sum to one, resulting in $$ \omega _j=\frac{\mathrm{initial}\_\omega _j}{\sum_{k=1}^m\mathrm{initial}\_\omega _k} $$. Here, labels with higher frequency and co-occurrence rate (i.e., more general labels) receive larger ω_j values, while specific or rare labels receive smaller ω_j values, which aligns with the implicit hierarchical structure of labels.

Using the label weights ω_j, we define the weighted Jaccard distance between label sets S_i and S_j (where S_i denotes the set of labels associated with instance i) as:

Compared with the standard Jaccard distance, the weighted variant emphasizes informative labels while suppressing the influence of rare or noisy labels.

Finally, the label affinity matrix H = [h_ij]_n×n is defined as:

where h_ij represents the likelihood that instances x_i and x_j share ground-truth labels.

Notably, the label weights ω_j and the label weight similarity sim_ω(i, j) defined in this section are further integrated with the Gaussian kernel to construct a label weight-guided fused kernel matrix K, which underpins the subsequent nonlinear LRR. The formal definition of K is:

where θ balances the feature and label similarity, and γ > 0 is the Gaussian kernel bandwidth. K is positive semi-definite, ensuring compatibility with the low-rank optimization framework. Specifically, sim_ω(i, j) quantifies label-based instance relevance and is computed as:

3.3. Predictor

Specifically, the intrinsic information present in potential label data can enhance the accuracy of subspace clustering. For instance, instances x_i and x_j may be distinct due to the absence of shared labels, i.e., S_i ∩ S_j = Ø. Consequently, the corresponding z_ij values for these instances are forced to be negligible, either zero or nearly so. Based on this rationale, we incorporate a novel term ||Z○H||₁^2[58], which integrates the potential label information, where H ∈ ℝ^n×n represents the label affinity matrix.

By combining the above components, LCND is defined as follows:

where α is a regularization parameter that controls the strength of the weak supervision constraint. Specifically, after obtaining the optimal projection matrix W through training, the predicted label vector for an unseen test sample x_t is generated as y_t = Wx_t. The final label set is then determined by applying a threshold or by selecting the labels with the highest confidence scores.

3.4. Solving the optimization problem

Introducing auxiliary variables J, U, and V allows us to restructure the objective function in Equation (14) as follows:

The augmented lagrange multiplier (ALM) method^[59] is then employed to handle the following augmented Lagrangian function:

where Y₁, Y₂, Y₃, and Y₄ are all N × N matrices in ℝ^N×N and serve as the Lagrange multipliers. Additionally, μ > 0 is a penalty parameter.

The optimization problem in Equation (11) can be solved iteratively by alternating minimization over the following subproblems:

(1) Optimize W while holding other parameters constant: With V, J, Z, U, and P fixed, the update equation for W is obtained by differentiating Equation (17):

This corresponds to a standard linear regression problem, whose solution can be determined as follows:

(2) Optimize V while holding other parameters constant: The task of updating V can be treated as a standard linear regression problem, and its solution can be expressed as:

(3) Optimize J while holding other parameters constant: With W, V, Z, U, and P fixed, the optimization of Equation (16) with respect to J reduces to the following problem:

The objective in Equation (20) can be equivalently written as:

Optimizing the objective function in Equation (21) involves performing singular value decomposition (SVD) on the matrix Z + Y₂/μ, followed by applying soft thresholding to the resulting singular values.

(4) Optimize Z while holding other parameters constant: This is an ordinary least squares regression problem. Its solution is:

(5) Next, update U with the other variables fixed:

Therefore, U can be updated using Equation (24):

where the function $$ \Psi _{\frac{\alpha \mathrm{H}}{\mu_k}} $$(X) is defined as the element-wise product of max(|X| - $$ \frac{\alpha}{\mu_k} $$H, 0) and sgn(X), the sign function of X. Here, the update of U corresponds to a soft-thresholding operation.

(6) Update P with the other variables fixed: The optimization problem for updating P_k+1 is formulated as follows:

where C_k+1 = I - Z_k+1 + Y_1,k/μ_k. Note that solving the problem in Equation (25) is nontrivial, as the objective function is convex but nonsmooth. Let c_i (respectively, p_i) denote the i-th column vector of C (respectively, P), and set the scalar τ = μ_k/λ. Then (μ_k/2)||P - C||_F² can be rewritten as μ_k((τ/2)Σ_i=1ⁿ||p_i - c_i||²). Normalizing the objective function by λ, the problem stated in Equation (25) can be reformulated as:

The problem can be decomposed into n independent subproblems, each taking the following form:

Lemma 1: Let τ > 0 be a scalar, b ∈ ℝ^q a constant vector (q is a positive integer), and S = diag({s_i}_1≤i≤q) ∈ ℝ^q×q a diagonal matrix whose diagonal entries s_i are positive and sorted in descending order. Then the optimal solution p^* to the following problem:

is given by

Here, S^-1 = diag({s_i^-1}_1≤i≤q) is the inverse of S, and the positive scalar δ satisfies:

In particular, when ||S^-1b|| > 1/τ, Equation (30) (with respect to δ) has a unique positive solution, which can be found via the bisection method as described in^[20]. The proof of Lemma 1 is provided in the Supplementary Materials. Leveraging Lemma 1, we obtain the following theorem.

Theorem 1: For τ > 0, the optimal solution p_i^* to the problem in Equation (27) can be expressed as:

where $$ \mathbf{\tilde{b}} $$_u = G_K^Tc_i ∈ $$ \mathbb{R}^{r_K} $$, and G_K ∈ $$ \mathbb{R}^{n\times r_K} $$ consists of the first r_K columns of G. The vector $$ \hat{\mathbf{p}} $$ is defined as

Here, δ is a positive scalar satisfying:

Specifically, if the norm ||[1/σ₁, …, 1/$$ \sigma _{r_K} $$]^T○$$ \tilde{\mathbf{b}} $$_u|| exceeds 1/τ, then Equation (33) (with respect to δ) has a unique positive solution, which can be obtained using the bisection method as previously described^[20]. The verification of Lemma 1 is detailed in the Supplementary Materials.

For a detailed update procedure, please refer to Algorithm 1. The detailed update process for parameter P is presented in Algorithm 2.

Algorithm 1.

Algorithm 2.

4.1. Datasets

We select three real-world datasets, namely music_emotion, music_style^[44], and mirflickr^[60]. As shown in Table 1, these datasets represent real-world PML instances, where candidate labels are obtained from online users and subsequently verified to establish ground-truth labels. In addition, we consider six synthetic datasets derived from multi-label benchmarks: Bibtex^[61], Birds^[62], Emotions^[63], Image^[9], Medical^[64], and Scene^[8]. To evaluate the robustness of our approach under different levels of label noise, we introduce a parameter r ∈ {1, 2, 3} that controls the number of false positive labels added to the candidate label set of each instance^[16]. By applying these three noise settings to each of the six original multi-label datasets, we construct 6 × 3 = 18 synthetic PML datasets with varying noise intensities. In addition to these synthetic datasets, we also use the three real-world datasets for validation. All comparative experiments are therefore conducted across 21 benchmark datasets. The detailed characteristics of these datasets are summarized in Table 2.

4.2. Experimental setup

4.3. Performance comparison

The experimental work presented herein was conducted on a computing platform equipped with an octa-core processor (each core running at 2.0 GHz) and 16.0 GB of RAM. The software used for these experiments is MATLAB version R2016a.

The detailed experimental results are presented in Tables 3-6. In these tables, bold text indicates that the corresponding algorithm achieved the best performance among all compared methods. Compared with the competing methods, LCND achieves superior performance in most experimental settings. PLAIN outperforms LCND in only one case, namely on the Birds dataset with respect to ranking loss.

To verify the effectiveness of LCND in real-world scenarios, we conducted experiments on the music_emotion, music_style, and mirflickr datasets. Among the eight compared algorithms, PAMB outperforms LCND in terms of Hamming loss on the real-world PML dataset because it adopts a binary decomposition strategy, which can improve the overall proportion of correctly predicted labels on a small portion of the data. However, its performance degrades noticeably on other datasets due to limited robustness to label noise. According to global statistical results for the Hamming loss metric, the overall performance of PAMB is inferior to that of LCND. In the remaining experimental settings, LCND consistently achieves the best or near-best results.

Additionally, this study employs the Friedman test^[68] to evaluate the comparative efficacy of the methods under review and to determine whether there is a statistically significant difference in their generalization capabilities. Let k be the number of methods being compared and N the total number of datasets used. Let r_i^j denote the rank of the j-th method on the i-th dataset. For the Friedman test, the mean rank of each method is computed as R_j = $$ \frac{1}{N} $$Σ_i=1^Nr_i^j (1 ≤ j ≤ k). Assuming the null hypothesis that the generalization performance of all evaluated methods is equivalent, the Friedman statistic F_F is defined and follows an F-distribution with k-1 and (k-1)(N-1) degrees of freedom:

where,

Table 7 summarizes the Friedman statistics F_F and the critical values for the six evaluation criteria (number of compared algorithms k = 9, number of datasets N = 21). Based on Table 7, the null hypothesis that there is no significant performance difference among the compared methods can be rejected at the 0.05 significance level.

In addition, we apply the Bonferroni-Dunn test^[68] to further investigate the performance differences among the eight compared algorithms. LCND serves as the benchmark method, and its average rank difference relative to the other methods is measured by the critical difference (CD). We consider the performance difference between LCND and another method to be significant if their mean rank difference exceeds the CD threshold (in this study, CD is set to 2.302, with k = 9 algorithms and N = 21 datasets). The CD analysis for each metric is shown in Figure 1. In this figure, the average ranks of the seven methods are plotted, with the best (i.e., smallest) ranks placed on the far right. A bold line connects LCND to a compared method if their average rank difference falls within the CD range.

Figure 1. LCND compared with eight algorithms using Bonferroni-Dunn test. If not linked on CD diagram, performance differs significantly (CD = 2.302, 0.05 significance). LCND: Label co-occurrence guided nonlinear disambiguation for partial multi-label learning; CD: critical difference.

From Figure 1, we can observe that:

• LCND achieves the best average ranking across all evaluation metrics. As shown in Figure 1, LCND consistently occupies the rightmost position in the CD diagram for all six metrics, including Hamming loss, Ranking loss, One error, Coverage, Average precision, and microF1. This indicates that LCND outperforms the seven competing algorithms in both error-based and accuracy-based evaluations, demonstrating strong robustness and generalizability.

• LCND is statistically significantly superior to most baseline methods. With a CD threshold of CD = 2.302 at the 0.05 significance level, algorithms that are not connected by a horizontal bar are considered significantly different. LCND is not comparable to the majority of the competing methods (e.g., ML-KNN, PML-lc, PARTICLE, NATAL, PLAIN, PML-TF) on most metrics, confirming that its performance advantage is statistically significant.

• The performance improvement of LCND is most pronounced on ranking-oriented metrics. The gap between LCND and the competing methods is particularly large for Ranking loss and Average precision. This demonstrates that the weighted Jaccard label affinity and nonlinear kernel mapping effectively capture fine-grained label semantics, enabling LCND to better distinguish ground-truth labels from noisy candidates during label ranking.

• LCND achieves a notably better average rank than the recent transformer-based method PML-TF, especially on ranking-oriented metrics, confirming the advantage of explicit nonlinear kernel modeling over implicit deep feature extraction in PML tasks.

4.4. Ablation study

To assess the contribution of key model components, we conduct an ablation study in which we systematically remove these components to observe the resulting changes in performance. The specific configurations for this ablation analysis are outlined below:

• To validate the effectiveness of the nonlinear component P in our model, we perform an ablation analysis by removing this component and evaluating the subsequent performance changes. Specifically, we remove the module g(P) $$ \triangleq \sum_{i=1}^n\sqrt{\mathbf{p}_i^T\mathbf{Kp}_i} $$ by directly using the linear LRR formulation in Equation (2). The objective function then becomes:

We refer to this method as LCND-NOK and solve the optimization problem using the ALM method.

• To demonstrate the impact of label affinity, we remove the term α||Z○H||₁², which is a constraint in LCND, resulting in a modified method called LCND-NOH.

• To assess the combined influence of the nonlinear component and label affinity, we exclude the label affinity component from the formulation in Equation (36), yielding a variant of the method termed LCND-NOKH.

Figure 2 presents the comparative experimental results of three methods on the music_style, Birds_3, and Medical_3 datasets, where average precision is shown as one minus the average precision (i.e., 1 - Average Precision). Key observations are as follows:

Figure 2. Performance of LCND-NOH, LCND-NOK, LCND-NOKH and LCND. LCND: Label co-occurrence guided nonlinear disambiguation for partial multi-label learning.

• The LCND model outperforms the other methods on all datasets and most metrics, particularly in reducing One Error and improving 1 - Average Precision. The LCND-NOKH model, which lacks both the nonlinear component and label affinity, underperforms compared to LCND-NOK and LCND-NOH. This indicates that jointly modeling label correlations and nonlinear feature structures is essential for achieving optimal performance.

• LCND-NOK performs well on some metrics by modeling features in linear subspaces, but it does not outperform the full model. On the Medical_3 dataset, where the feature dimension is larger than the number of instances (d > n), the need to handle nonlinear problems becomes evident. These results confirm that nonlinear feature induction and label relationships improve training. Our ablation study demonstrates the superior performance and reliability of the complete model.

4.5. Comparison of different kernel functions

To validate the effectiveness and generality of different kernel functions, this section presents comparative experiments using the polynomial, Sigmoid, arctan, and Gaussian kernels on both real-world and synthetic datasets. The results are summarized in Figure 3.

Figure 3. The comparative results of different kernel functions.

As shown in Figure 3, the Gaussian kernel function significantly outperforms all other kernels across all six performance metrics. This superiority stems from the inherent mechanism of the Gaussian kernel: it embeds sample data into an infinite-dimensional RKHS via implicit feature mapping. This property theoretically enables the Gaussian kernel to approximate arbitrarily complex nonlinear decision boundaries, demonstrating exceptional versatility in addressing nonlinear classification problems.

4.6. Comparison of different label functions

To rigorously verify the effectiveness of the proposed weighted Jaccard distance, we conducted additional ablation experiments comparing three variants of label similarity metrics:
1. LCND-H: LCND using the standard Jaccard similarity (i.e., with equal label weights).
2. LCND-CH: LCND using the cosine similarity between label vectors.

The experiments were performed on three representative datasets with distinct characteristics: music_emotion, Medical_3, and Birds_2. The results are shown in Figure 4, from which we make the following observations:

Figure 4. Performance of LCND-H, LCND-CH and LCND. LCND: Label co-occurrence guided nonlinear disambiguation for partial multi-label learning.

1. The weighted Jaccard distance consistently outperforms the standard Jaccard distance. On all three datasets, LCND achieves significantly higher average precision than LCND-H. This improvement arises because the standard Jaccard distance treats all labels equally and cannot distinguish frequent labels from rare, specific, or noisy ones. In contrast, the proposed weighting scheme adaptively enhances the contribution of informative labels while suppressing the influence of noisy or trivial labels.

2. The weighted Jaccard distance also outperforms the cosine similarity. LCND-CH yields the lowest average precision across all datasets. Cosine similarity computed directly on binary label vectors is highly sensitive to the sparsity and label noise in the candidate label sets of PML. In comparison, the weighted Jaccard distance incorporates global label statistics (i.e., label frequency and co-occurrence) and is more robust to random label noise.

These findings demonstrate that the proposed weighted Jaccard distance is a critical component for robust label disambiguation in PML. The weighting scheme effectively leverages global label statistics to mitigate the adverse effects of label noise and sparsity, achieving consistent and significant performance improvements over both the standard Jaccard distance and the cosine similarity.

4.7. Parameter analysis

Within the scope of this study, we consider four regularization parameters: α, β, γ, and λ. These parameters are selected from the interval [10^-3, 10³] using a grid search strategy. To investigate its impact, we present experimental results of the LCND classifier by adjusting one parameter at a time while keeping the other three fixed. The data in Figures 5 and 6 indicate that the overall trends of α and γ remain stable across different datasets. The λ parameter is also stable except for the extremely small value of 10^-3. The β parameter first increases and then decreases as its value increases, with the optimal parameter range consistently falling between 1 and 10 across all datasets.

Figure 5. The performance of LCND on the mirflickr dataset across a range of trade-off parameter values. LCND: Label co-occurrence guided nonlinear disambiguation for partial multi-label learning.

Figure 6. The performance of LCND on the Medical_1 dataset across a range of trade-off parameter values. LCND: Label co-occurrence guided nonlinear disambiguation for partial multi-label learning.

4.8. Computational complexity

In the context of the LCND algorithm, T_LCND denotes the total number of iterations required. It is not necessary to compute the inverse (XVV^TX^T + 2βI_d)^-1 at every iteration; thus, computing W according to Equation (18) incurs a complexity of $$ \mathcal{O} $$(n²d + mdn + md²). Similarly, the inverse of (WX)^T(WX) +μI does not need to be computed iteratively, which reduces the cost of updating V as per Equation (19) to $$ \mathcal{O} $$(n³). For updating J, a partial SVD approach can be used for singular value shrinkage, which has a time complexity of $$ \mathcal{O} $$(rn²), where r is the rank used in the partial SVD at a given iteration. Updating Z according to Equation (22) has a complexity of $$ \mathcal{O} $$(n²). The soft-thresholding operation for U, as detailed in Equation (24), also has a complexity of $$ \mathcal{O} $$(n²). During the update of P, n subproblems of the form given in Equation (27) must be solved, each with a complexity of $$ \mathcal{O} $$(r_X²) due to matrix-vector multiplications as outlined in Theorem 1, where r_X denotes the rank of X. The complexity of the bisection method [Equation (33)] is $$ \mathcal{O} $$(n·r·log($$ \mathrm{\frac{high-low}{tol}} $$)), where tol is the tolerance set to 1 × 10^-4, and “low” and “high” are the lower and upper bounds. Consequently, the overall complexity of solving LCND is $$ \mathcal{O} $$(T_LCND((d + r + m + r_X)n² + mdn + md + n³)).

We note that the label affinity matrix H constructed via the weighted Jaccard distance is highly sparse in practice. Because the candidate label sets of most instance pairs have little or no overlap, the vast majority of entries in H are either exactly zero or negligibly small. In our implementation, H can be stored in a sparse matrix format. This sparsity significantly reduces the computational cost of the element-wise product Z○H and the associated ℓ₁ penalty. Moreover, the sparse structure of H naturally encourages sparsity in the learned instance affinity matrix Z, which in turn enables the use of scalable sparse linear algebra routines and iterative solvers, thereby avoiding full n × n matrix inversions. This sparsity-driven strategy provides a practical and effective way to extend LCND to large-scale datasets while fully preserving its nonlinear modeling capability.