Optimal Graph Learning and Nuclear Norm Maximization for Deep Cross-Domain Robust Label Propagation

1 Introduction

Deep neural networks have advanced numerous computer vision tasks [Chen et al., 2024; Huang et al., 2021; Huang et al., 2022a; Huang et al., 2022b; Huang et al., 2023a; Huang et al., 2024]. However, they typically rely on large amounts of annotated data to ensure the model's generalization ability in a target domain of interest, making the process time-consuming and resource-intensive [Wu et al., 2023b; Wu et al., 2023c]. It is intuitive to leverage a well-labeled source domain to train a model for the target domain, assuming they follow the same distributions. However, in real-life scenarios, the assumption often becomes challenging to hold due to factors such as environmental variations, differences in equipment, and human-related factors. Domain adaptation (DA), in this regard, aims to reduce manual annotation costs by improving the model's generalization ability trained on a source domain to a target domain, where the two domains could be allowed to follow different distributions [Wang et al., 2021; Wang et al., 2023b; Wang et al., 2020; Wu et al., 2024].

∗Corresponding author: Xiaochun Cao.

Existing DA approaches enhance the model's generalization ability mainly from two aspects: feature extraction and classifier design. Feature extraction typically involves designing a distribution distance [Long et al., 2015] or a network module [Long et al., 2018] to discover domain-invariant features from both the source and target domains. As DA often employs the pseudo-labeling technique for label-induced losses related to the target domain, the classifier design primarily aims to improve the quality of pseudo-labels [Wang et al., 2022; Wang and Breckon, 2020]. These two aspects are mutually reinforcing, as better domain-invariant features lead to improved pseudo-labels and vice versa. As an effective classifier, label propagation (LP) constructs a similarity graph by exploring the structural relationships among different samples. It then designs a smooth function over this similarity graph to propagate labels from the source domain to the target domain based on the assumption that close samples in feature space should have similar labels as possible [Iscen et al., 2019; Song et al., 2023].

Although LP has been applied in many shallow DA methods [Ding et al., 2018; Li et al., 2020], it has not been fully explored in the context of deep DA as the graph construction has to consider all samples globally, which may not be well-suited for the batch sampling strategy in deep neural networks. Moreover, LP is sensitive to the distribution shift problem and fails to deal with the class imbalance problem. As shown in Figure 1 (a), the two domains follow very different distributions, and LP treats the source and target domains as a union to construct a similarity graph. However, the similarity weights between sample points that are separately from the two domains become close to 0 (i.e., no weighted edges), directly resulting in inaccurate LP from the source domain to the target domain. It can be observed that the colors are faint in the upper right corner and lower left corner of the similarity graph. As shown in Figure 1 (c), the number of class heptagon is smaller than that of class circle in the source (left) and target (right) domains. For example, we predict a target sample whose ground-truth is class heptagon. Although it is closer to the heptagon sample, the LP loss is smaller than the loss formed by all circle samples. Therefore, to minimize the overall LP loss, there is a tendency to wrongly classify this sample as the class circle.

This paper proposes a deep cross-domain robust label propagation (DCDRLP) approach to address the aforementioned issues. Specifically, we address the distribution shift and class imbalance issues in LP from two perspectives: graph construction and regularization construction. As for graph construction, we introduce optimal graph learning (OGL) to optimize three graphs. Specifically, instead of treating the source and target domains as a union, we construct a cross-domain graph across the two domains, ensuring that the similarity weight between two samples from different domains is not excessively small. As illustrated in Figure 1 (b), compared to Figure 1 (a), the colors in the upper right corner and lower left corner of the similarity graph have become darker. Moreover, we also construct two domain-specific graphs for the source and target domains to respect their own structures, respectively. As illustrated in Figure 1 (b), the sample in the black dashed box may be wrongly classified to the class heptagon with only the cross-domain graph. When we consider its own structure, the other samples from the class circle will correct it based on the assumption that close samples should have similar labels.

As for regularization construction, inspired by [Cui et al., 2020], we introduce the nuclear norm maximization (NNM) into LP, to enhance the class diversity of prediction results, effectively addressing the class imbalance problem. However, as optimizing the LP model with NNM is nontrivial, we propose an efficient optimization algorithm. Finally, we incorporate the proposed LP into a deep neural network by supervising the classifier layer with the cross-entropy loss. Moreover, we utilize both features and labels to conduct OGL and generate three discriminative graphs. Then, inspired by the graph embedding (GE) technique, we construct three GE losses for the network to learn locally discriminative and domaininvariant features. Specifically, we enable two samples to close if they are close in feature space from the same class, where the two samples come from the same domain or two different domains. The main contributions of this paper are summarized as follows:

• We introduce OGL and NNM into LP so that it is robust to the problems of distribution shift and class imbalance. Moreover, we devise an efficient algorithm to solve the corresponding optimization problem.
• We incorporate the proposed LP into a deep neural network to generate reliable pseudo-labels. Moreover, we construct three GE losses with OGL to learn locally discriminative and domain-invariant features.
• We validate the effectiveness of our proposed approach on three cross-domain benchmark datasets, and it could outperform existing state-of-the-art methods.

2 RelatedWork

Existing DA approaches typically adopt the following strategies to bridge the gap between the source and target domains: statistical distribution distance metrics [Zhu et al., 2021], optimal transport [Damodaran et al., 2018], adversarial learning [Long et al., 2018], self-training based on pseudolabels [Zou et al., 2019; Liu et al., 2021], feature disentanglement [Bousmalis et al., 2016], batch normalization [Chang et al., 2019], and data augmentation [Li et al., 2021b], among others. However, since DA assumes that target domain data can participate in the training process, many methods based on the aforementioned strategies utilize pseudo-labels of the target domain to enhance feature discriminability.

As discussed above, the pseudo-labeling technique has been widely applied in DA, making the quality of pseudolabels crucial for DA performance. Existing methods mainly address this issue from three aspects: 1) using a certain threshold criterion to select more reliable pseudolabels [Wang and Breckon, 2020]; 2) designing label-induced losses to make them less sensitive to the quality of pseudolabels [Pan et al., 2019; Pei et al., 2018; Ding et al., 2018; Wang et al., 2022; Zhu et al., 2021; Wang et al., 2023c]; 3) devising classifiers capable of generating more reliable pseudo-labels [Wang and Breckon, 2020; Liang et al., 2019; Wang et al., 2022].

Considering the effectiveness of LP, recent work utilizes LP to generate pseudo-labels for DA [Ding et al., 2018; Li et al., 2019; Zhang et al., 2020; Li et al., 2020; Luo et al., 2020; Wang et al., 2022; Wang et al., 2023a]. However, they usually utilize the most basic form of LP and apply LP to a shallow DA model. In contrast, this paper proposes a novel LP robust to the problems of distribution shift and class imbalance. Moreover, inspired by [Iscen et al., 2019], we incorporate the proposed LP into a deep DA model.

ℒce CE loss

category ��

3 Proposed Approach

In DA, there exist a labeled source domain Ds := {X s ∈ Rm×n s ,Y s ∈ RC×n s } and an unlabeled target domain Dt := {X t ∈ Rm×n t } with two different distributions. 'm' is the feature dimension, 'n s ' and 'n t ' are the sample numbers of source and target domains, and 'C' is the category number. We aim to utilize labels of the source to realize label prediction for the target as accurately as possible. The whole pipeline of our proposed DCDRLP is briefly depicted in Figure 2.

3.1 Label Propagation

As existing DA approaches usually utilize the pseudolabeling technique to optimize some label-induced losses related to the target domain, it is crucial to devise a promising classifier for more reliable pseudo-labels. As an effective classifier, LP could propagate labels of the source domain to the target domain by representing the structural relationships among different samples as a similarity graph and devising a smooth function over the graph based on the assumption that close samples in feature space should have similar labels. We formulate LP as the following model,

where Y s is the ground-truth and ¯Y s , ¯Y t are prediction results. wij ∈ W denotes the similarity weight between i-th and j-th samples in feature space, and wij is large when they are close in feature space. Optimizing model (1) enables two sample labels with large similarity weight close, and the model has a closed-form solution involving an inverse matrix [Iscen et al.,

2019]. Next, we will address the sensitivity of LP to distribution shift and class imbalance issues, proposing corresponding solutions from the perspectives of graph construction and regularization construction.

3.2 Optimal Graph Learning

As discussed, LP constructs the similarity graph W on the union of the source domain and target domain. As such, the similarity weights connecting the two domains are close to 0 when they follow very different distributions. To this end, we construct one cross-domain and two domain-specific graphs separately. We define the construction of these two types of graphs as the following optimization processes,

where z is the learned feature vector from G or 'Fc'. To simplify the notation, n, z, and y are for a specific domain, while n⋆ , x⋆ , and y⋆ are for the other different domain.

The first term of the two models enables two close samples in feature space with similar labels to have large similarity weights. The second term avoids a trivial solution where only the nearest data point can be the neighbor of zi with a similarity weight of 1. Notably, α1 and α2 could be determined by the number of nearest neighbors k [Nie et al., 2014].

We optimize model (2) between source and target domains to obtain two graphs W st and W ts , and denote their average graph as Wcro = (W st +W ts⊤)/2. Then, we construct our cross-domain graph as W cro = [0,Wcro ;Wcro⊤, 0]. Moreover, we optimize model (3) on source and target domains to obtain our domain-specific graphs W ss and W tt , respectively. Notably, we only utilize features to conduct OGL for LP, while both features and labels are adopted for graph embedding losses, which will be introduced later.

3.3 Deep Cross-Domain Robust Label Propagation

Given the data features of the source and target domains, we obtain three similarity graphs through the aforementioned OGL. Then, we utilize these graphs to enable LP to be robust to distribution shift. Additionally, inspired by [Cui et al., 2020], we further introduce a nuclear norm maximization loss into LP to enhance its robustness to class imbalance issue. The formal definition is expressed in the following model,

Optimizing the first term enables two samples close in feature space from different domains to have similar labels. Optimizing the second term makes two samples close in feature space from the target domain have similar labels. Optimizing the third term will increase the class diversity of predictions. Intuitively, the first term aims to propagate labels from source to target. In contrast, the second term utilizes the structure of the target domain itself to correct some label propagation errors in the first term. Moreover, we introduce a non-negative constraint, a normalization constraint, and a constraint that predicted source labels should be equal to the ground-truth. δ and σ are the hyper-parameters that balance the corresponding terms' relative importance.

Different from LP, 1) We split LP into two parts with two types of graphs so that it is robust to distribution shift; 2) We introduce a constraint of nuclear norm maximization to deal with the class imbalance problem; 3) We introduce nonnegative and normalization constraints to ensure the probability meaning of predicted labels; 4) We solve the corresponding optimization problem with an efficient algorithm.

Although LP has been applied to many shallow DA methods, it has not been fully explored in deep DA as the graph construction requires all samples globally, which is unsuited for batch sampling strategy in deep neural networks. Inspired by [Iscen et al., 2019], we utilize the predictions of the target domain by model (4) to supervise the classifier layer in a deep neural network with the cross-entropy loss, enabling it to obtain better pseudo-labels from model (4).

3.4 Graph Embedding

Besides an effective classifier, existing DA methods also focus on designing a feature extractor to obtain discriminative and domain-invariant features. Graph embedding (GE), as an effective feature learning technique, aims to incorporate the similarity graph constructed in the original feature space into a dimensionality reduction framework, preserving the local manifold structure in the original feature space [Zheng et al., 2011; Cai et al., 2011]. Inspired by this, we conduct OGL in the feature space extracted by G, using ground-truth labels from the source domain and pseudo-labels from the target domain. This results in three similarity graphs with discriminative structures. Subsequently, the three graphs are applied into the feature space extracted by 'Fc', yielding the following three graph embedding losses,

where the first two losses aim to prompt sample features from the same domain close if they are close in feature space of G and have similar labels. The third loss aims to prompt sample features from two domains to close if they are close in feature space G and have similar labels. As such, we could learn locally discriminative and domain-invariant features by minimizing the above losses for better DA effects.

After introducing the various modules above, we obtain the overall loss function for the proposed model as below,

where Lce is the cross-entropy loss, Lge is the loss for locally discriminative and domain-invariant feature learning. Moreover, α, β, and λ are the hyper-parameters that balance different losses' importance.

4 Experiments

We compare our proposed DCDRLP with 16 state-of-theart DA methods, including 3 LP-based shallow DA methods: DTLC [Li et al., 2020], CRLP [Wang et al., 2022], RMMD [Wang et al., 2023a], and 13 deep DA methods: CDAN [Long et al., 2018], BSP [Chen et al., 2019], BNM [Cui et al., 2020], DSAN [Zhu et al., 2021], ATM [Li et al., 2021a], TSA [Li et al., 2021b], GDCAN [Li et al., 2022], DMP [Luo et al., 2022], DALN [Chen et al., 2022], SDAT [Rangwani et al., 2022], DRDA [Huang et al., 2023b], MEDM [Wu et al., 2023a], MetaReg [Li et al., 2023]. Besides, we adopt the variant of the highest results from their papers. As shallow DA methods fail to deal with large-scale datasets, we do not record their results on VisDA-2017.

4.1 Datasets

We conduct comprehensive experiments on three crossdomain image classification datasets. Office-31 consists of 31 categories shared from three distinct domains: Amazon

(A), Dslr (D), and Webcam (W), and they have 2,817, 498, and 795 images, respectively. Office-Home includes 65 categories shared from four different domains: Art (A), Clipart (C), Product (P) and Real-World (R). The four domains have 2,427, 4,365, 4,439, and 4,357 images. VisDA-2017 is a large-scale synthetic-to-real dataset which have 12 shared categories. The synthetic domain and real domain have 152,397 and 55,388 images, respectively. Following [Li et al., 2021b], we utilize one domain as the source domain and another as the target domain to construct 4, 12, and 1 DA tasks for the three datasets, respectively. Notably, the easy tasks of D→W and W→D in Office-31 are not included as most existing DA methods obtain nearly 100% accuracy results. Moreover, in VisDA-2017, we regard the synthetic as the source domain and the real as the target domain.

4.2 Implementation Details

We use ResNet-50 as the backbone network for Office-31 and Office-Home, while ResNet-101 is for VisDA-2017. Moreover, we use a mini-batch SGD optimizer with a momentum of 0.9 and a weight decay of 0.001. We set the batch size for the source and target domains to 32, with a learning rate of 0.01. The entire network training process spans 10 epochs, each comprising 500 iterations. For comparison results, we set hyper-parameters of α as 0.5. As for k, the numbers of nearest neighbors for both cross-domain graph and domainspecific graph are set as 10. For a fair comparison, we adopt 20 nearest neighbors for the graph construction of standard LP in the ablation study. As for β, λ, δ, and σ, we select the optimal values for each DA task through trials.

4.3 Results

We record the accuracy results on the three datatsets in Tables 1, 2, 3. The best average results are in bold font, and the second-best ones are underlined. From these tables, we can observe that our proposed approach outperforms all compared methods on average. The average results of our proposed approach are 87.0%, 73.6%, and 85.6%, which have

0.8%, 1.0%, and 1.3% improvements over the best baselines TSA, DALN, and SDAT/MetaReg, respectively. Furthermore, we can observe a greater improvement on OfficeHome than on Office-31, attributed to the larger distribution shift within Office-Home. The most significant enhancement is obtained on VisDA-2017, as there exists a severe class imbalance issue, and we report accuracy results for each class. On the one hand, shallow DA methods also use LP to obtain reliable pseudo-labels. Still, they do not consider LP sensitive to the distribution shift problem and fail to deal with the class imbalance problem. Additionally, most of them suffer from the limitation of handling large-scale datasets. On the other hand, deep DA methods enhance the quality of pseudo-labels or promote discriminative feature learning through different strategies. However, they do not take advantage of LP in label prediction. In contrast, our proposed approach applies LP to a deep DA model and addresses the distribution shift and class imbalance problems in LP. As a result, the proposed approach could produce more reliable pseudo-labels and learn more effective discriminative features for better DA effects.

4.4 Empirical Analysis

To validate the effectiveness of our proposed approach, we conduct ablation experiments on various key components of the model, visualize the feature distributions, and perform sensitivity analysis on some key hyper-parameters.

Ablation Study. We select four relatively challenging DA tasks on Office-Home and test the model's performance with the following variations. w/o OGL means that the graph construction strategy in our model is kept consistent with LP; w/o NNM indicates that we do not consider nuclear norm maximization; w/o LP indicates that we do not use the proposed LP to supervise the classifier layer in the network; w/o GE s , GE t refers to removing the domain-specific graph embedding losses, while w/o GE cro refers to removing the cross-domain graph embedding loss. We keep all parameters consistent across these variations to ensure a fair comparison.

From Table 4, we observe that removing or replacing key components in our proposed model leads to a certain performance decrease. The performance degradation with the variants of w/o OGL (2.4%) and w/o NNM (4.1%) reflects that OGL and NNM could make LP robust to distribution difference and class imbalance, respectively. The performance drop with the variant of w/o LP (4.1%) indicates that leveraging the advantage of our proposed LP in label prediction could enhance the performance of deep DA models. The performance decline with the variants of w/o GE s , GE t (0.4%) and w/o GE cro (1.2%) validates that GE losses could prompt locally discriminative and domain-invariant features for better DA effects. By observing the impact of the abovementioned components on our model, we can verify the significance of our proposed LP with OGL and NNM.

To further validate the effectiveness of NNM in terms of class imbalance issue, we directly use features extracted by the backbone on VisDA-2017 as inputs for LP, LP with OGL, and LP with OGL and NNM. As shown in Figure 3, VisDA2017 exhibits a severe class imbalance problem in the target domain. It can be observed that the sample number predicted as the majority class using LP (i.e., Figure 3(a)) is much higher than the ground-truth. In contrast, the sample number predicted as the minority class is much smaller than the ground-truth. This leads to poor results for the minority classes, degrading the average accuracy for all classes accordingly. As graph construction with OGL is robust to distribution shift, including source domain samples into the target domain will somewhat mitigate the class imbalance problem.

From Figure 3(b), it can be observed that the sample numbers assigned to the minority classes increase, and the accuracy results of the minority classes begin to rise. When we further introduce NNM, the sample numbers of minority classes and the accuracy results further increase. Additionally, we observe that, although "truck" is a majority class, it is relatively smaller than "car". As there are similarities between these two categories, many samples belonging to the "truck" are misclassified as "car". Correspondingly, both Figure 3(b) and Figure 3(c) show significant improvements in the sample number and accuracy result on the class "truck".

Feature Visualization. We visualize the distribution of features extracted by our model on Office-Home. As shown in Figure 4, the good alignment of different color dots indicates better domain-invariant features. Moreover, better discriminative features are suggested when different sub-clusters are clustered more compactly. Our model's feature distribution exhibits better discriminative and domain-invariant characteristics than the source-only model (a model directly trained on the source for the target). Since our proposed LP can generate more reliable pseudo-labels, it facilitates the graph embedding process to extract more accurately locally discriminative and domain-invariant features.

Hyper-Parameter Sensitivity. We conduct sensitivity analysis on the crucial parameters of the proposed model. As shown in Figure 5(a), we conduct convergence analysis on our model and observe that the model achieves convergence at a relatively fast rate with increasing iterations. In Figure 5(b), α represents the impact of the proposed LP on the network's performance, and this curve shows a trend of first increasing and then decreasing, confirming the effectiveness of our proposed LP. In Figure 5(c), β demonstrates the significance of locally discriminative and domain-invariant feature learning, showing a trend of first increasing and then decreasing. In Figure 5(d), λ characterizes the importance between cross-domain GE and domain-specific GE. The former emphasizes learning domain-invariant features, while the latter focuses on preserving domain-specific structures. In addition, a larger λ will place more emphasis on domain-specific GE, and vice versa for cross-domain GE. It can be observed that better results are achieved when λ has a smaller value, indicating that cross-domain GE has a greater impact on model performance than domain-specific GE. Moreover, it can be observed that the proposed model is not particularly sensitive to these three parameters and can achieve good performance within a relatively wide range.

5 Conclusion

This paper proposes a novel classifier for DA, where we introduce OGL and NNM to be robust to distribution shift and class imbalance problems. Moreover, we incorporate the proposed classifier and GE losses into a deep neural network to obtain reliable pseudo-labels and learn locally discriminative and domain-invariant features for better DA effects. Extensive experiments on multiple cross-domain benchmarks could verify the effectiveness of our proposed approach.

(a) P→C

(b) R→P

Acknowledgments

This work was supported by the National Natural Science Foundation of China (No.62306343, No.62025604, No.62301621), the Shenzhen Science and Technology Program (No.KQTD20221101093559018), and the Shenzhen Science and Technology Program (No.20231121172359002).

Contribution Statement

We state that Wei Wang, Hanyang Li, and Ke Shi made equal contributions to this work.