# SIDE: Self-supervised Intermediate Domain Exploration for Source-free Domain
Adaptation

Jiamei Liu, Han Sun*, Yizhen Jia,
Nanjing University of Aeronautics and Astronautics
Nanjing
{jiamei, sunhan<EMAIL_ADDRESS>
&Jie Qin,
Nanjing University of Aeronautics and Astronautics
Nanjing
<EMAIL_ADDRESS>
Huiyu Zhou,
University of Leicester
Englend
<EMAIL_ADDRESS>
&Ningzhong Liu,
Nanjing University of Aeronautics and Astronautics
Nanjing
<EMAIL_ADDRESS>

###### Abstract

Domain adaptation aims to alleviate the domain shift when transferring the
knowledge learned from the source domain to the target domain. Due to privacy
issues, source-free domain adaptation (SFDA), where source data is unavailable
during adaptation, has recently become very demanding yet challenging.
Existing SFDA methods focus on either self-supervised learning of target
samples or reconstruction of virtual source data. The former overlooks the
transferable knowledge in the source model, whilst the latter introduces even
more uncertainty. To address the above issues, this paper proposes self-
supervised intermediate domain exploration (SIDE) that effectively bridges the
domain gap with an intermediate domain, where samples are cyclically filtered
out in a self-supervised fashion. First, we propose cycle intermediate domain
filtering (CIDF) to cyclically select intermediate samples with similar
distributions over source and target domains. Second, with the aid of those
intermediate samples, an inter-domain gap transition (IDGT) module is
developed to mitigate possible distribution mismatches between the source and
target data. Finally, we introduce cross-view consistency learning (CVCL) to
maintain the intrinsic class discriminability whilst adapting the model to the
target domain. Extensive experiments on three popular benchmarks, i.e.
Office-31, Office-Home and VisDA-C, show that our proposed SIDE achieves
competitive performance against state-of-the-art methods.
code:https://github.com/se111/SIDE

_K_ eywords Domain adaptation $\cdot$ source-free $\cdot$ consistency learning
$\cdot$ self-supervised learning

##  1 Introduction

(a) Self-supervised learning based SFDA methods

(b) Virtual source based SFDA methods

(c) Our proposed SIDE

Figure 1: Illustration of different SFDA methods. (a) SSL based methods
usually generate pseudo-labels for target data, ignoring the large
distribution shift even if the source model well fits the source domain. (b)
Virtual source based methods synthesize source data to assist domain
adaptation, introducing additional costs and uncertainty. (c) SIDE selects
intermediate data from the target domain, gradually adapting the model to the
target domain.

In spite of remarkable successes in various applications, deep neural networks
rely on training on a large amount of labeled data. Besides, when applying the
trained model to a novel domain, the performance will drop dramatically due to
the disagreement between the distributions of the original (source) domain and
the new (target) domain, also known as domain shift. To overcome this,
unsupervised domain adaptation (UDA) has received a plethora of research
interests, aiming to transfer the knowledge learned from the labeled source
domain to the unlabeled target domain by alleviating the domain shift.
However, the source domain data, which is indispensable for the adaptation
process, may not be accessible due to data privacy or intellectual property
concerns. To circumvent this limitation, source-free domain adaptation (SFDA)
has recently emerged as a more practical setting, where only the pre-trained
source model is available without any access to the source data.

To re-adapt the model to the target domain under this challenging setting, a
number of SFDA methods have been proposed, which can be mainly divided into
the following two categories. The first line of approaches perform self-
supervised learning directly based on target samples, as shown in Fig. 1 (a).
The basic idea is to explore reliable pseudo-labels of target data to
calibrate the model [1, 2]. Nevertheless, the quality of pseudo-labels is
difficult to guarantee, as the source model is pre-trained based on source
data and thus has a limited adaptive ability on the target domain due to the
large domain gap. The second line of methods transfer the knowledge from the
virtual source domain, where virtual source data is generated by means of
synthesis [3][4] or style transfer [5][6], as illustrated in Fig. 1 (b).
However, reconstructing the source domain has two drawbacks. On the one hand,
the replacement of the virtual source data has severe uncertainty and there is
still a domain gap even if the source data can be perfectly restored. On the
other hand, the generative networks involved in source data reconstruction
unnecessarily introduce additional computational overhead.

Therefore, to effectively and efficiently tackle SFDA, we need to not only dig
out the intrinsic characteristic of the target domain, but also explicitly
reveal and eliminate the domain differences without adding new data. To
fulfill this goal, in this paper, we propose self-supervised intermediate
domain exploration (SIDE) to calibrate the model through self-supervised
consistency training with the help of cyclically explored intermediate domain
samples. Specifically, we incorporate three carefully-designed modules into
SIDE, including cycle intermediate domain filtering (CIDF), inter-domain gap
transition (IDGT), and cross-view consistency learning (CVCL). To
progressively reduce the gap between source and target domains, CIDF
cyclically discovers those target samples similar to source domain prototypes
to form the intermediate domain in a self-supervised learning manner. The
intuition behind CIDF is that the selected samples work as the bridge to make
the distribution of the source domain gradually approach that of the target
domain. Furthermore, we propose IDGT to generate augmented samples based on
target and intermediate domain samples, properly reflecting the influence of
the intermediate domain. Finally, CVCL introduces instance- and class-level
consistency losses to guarantee the consistency between two different views of
the same target sample.

It is noteworthy that our proposed SIDE shows its unique advantages over the
existing SFDA methods. 1) Compared to self-supervised methods, SIDE learns
target data representations by leveraging an intermediate domain that shares
similarities with both source and target domains. This avoids the interference
on the target distribution brought by the inaccurately assigned pseudo labels.
Besides, our proposed consistency losses further guarantee the class
discriminability, leading to improved classification accuracy. 2) In
comparison with ‘virtual’ source data based methods, SIDE does not require any
additional time-consuming generation procedures. It leverages ‘real’
intermediate data cyclically to facilitate the transition from the source
domain to the target one. In other words, we gradually increase the
adaptability of the learned target model, which is often overlooked in
previous works.

We summarize our main contributions as follows:

$\bullet$ We tackle the challenging SFDA task by a novel framework, namely
self-supervised intermediate domain exploration (SIDE), which exploits
intermediate samples cyclically to reduce the cross-domain gap and assist
self-supervised learning in the target domain.

$\bullet$ We propose three delicately-designed modules (_i.e._ , CIDF, IDGT,
and CVCL), which collaboratively facilitate a smooth adaptation from the pre-
trained source model to the target one. As a result, the domain gap is
gradually eliminated whilst learning more discriminative target features.

$\bullet$ Extensive experiments on three benchmarks demonstrate that the
proposed approach achieves state-of-the-art performance compared to both UDA
and SFDA methods.

##  2 Related Work

###  2.1 Unsupervised Domain Adaptation

Early UDA methods mitigate domain shift mainly through instance re-weighting
[7] [8][9] and feature adaptation [10] [11][12]. The former re-weights the
source data so that the source distribution can be closer to the target
distribution in a non-parametric manner, whereas the gap between two domains
is not too significant. Feature adaptation aims to discover the common feature
representations of data using metrics [13], projections [14] and subspace
alignment [15], _etc_. Benefiting from the development of deep learning,
alignment-based methods [16] [17] [18] and adversarial-based methods [19] [20]
[21] have become popular. However, due to data privacy, the classical UDA
method can not adapt to the target domain well with the absence of source
domain data.

Figure 2: The framework of the proposed SIDE. We first select the intermediate
data from the target domain by calculating the feature-level similarities
between the target samples and the prototypes, and repeat this process
throughout the training procedure cyclically. Then, the intermediate and the
target samples are trained with the mixup regularization to eliminate the
implicit gap. Finally, we optimize the feature encoder by calculating
instance- and class-level consistency losses considering different views of a
sample. Best viewed in color.

###  2.2 Source-Free Domain Adaptation

SFDA aims to adapt the source model to the unlabeled target domain data
without accessing the source data. The existing methods are mainly divided
into two categories. One is using the methods of pseudo-labels based on self-
supervised learning. Liang et al. [22] maximize mutual information and
generate pseudo labels to match the target features to the source hypothesis.
Kim et al. [23] select samples by entropy values for target model training.
However, the accumulation of noise caused by false pseudo-labels brings
negative transfer. Different from them, we use the CVCL module to explore deep
intrinsic features and corresponding category information.

Some works have attempted to recover the pseudo-source domain by generative
methods. Qiu et al. [4] generate pseudo-source domain data by additionally
training a generator. Du et al. [20] augment the typical target domain
samples. Ding et al. [24] select the pseudo-source samples based on the
feature similarity with the class prototypes, whilst ignoring that the
distribution of features learned by the target model is gradually shifted. In
this paper, we propose to cyclically choose intermediate domain samples that
enables us to push the learnt feature distribution towards the unknown target
domain distribution.

###  2.3 Self-Supervised Learning in SFDA

Since there is no human-annotated label in the target domain, self-supervised
learning (SSL) has been widely applied in SFDA. Contrastive learning is a
common paradigm in SSL with the main idea of minimizing the distance between
anchors and negative samples [25][26]. Qiu et al. [4] explore the boundary
information of the source model and align the source/target data via
contrastive learning. However, pushing away the same-class samples as negative
pairs makes the training unstable. Inspired by the approaches without using
negative samples [27] [26], we perform instance- and class-level consistency
regularization on cross-views to learn domain-invariant feature
representations.

##  3 Proposed Method

In this section, we first describe the problem setup of the source-free domain
adaptation task. Then, we elaborate our proposed method, namely self-
supervised intermediate domain exploration (SIDE) in detail, which is composed
of three modules, _i.e._ , cycle intermediate domain filter- ing (CIDF),
inter-domain gap transition (IDGT), and cross-view consistency learning
(CVCL). Specifically, CIDF obtains intermediate domain samples by calculating
the similarity between target samples and prototypes obtained from the pre-
trained source model. IGDT then augments the intermediate domain samples with
the target domain samples. Finally, the adaptation of the model to the target
domain is further strengthened by CVCL. The overall architecture of the
proposed SIDE framework is shown in Fig. 2.

###  3.1 Problem Setup

In a source-free domain adaptation task, the labeled source domain data with
$n_{s}$ labeled samples is denoted as
$D_{s}=\\{{(x_{s}^{i},y_{s}^{i})}\\}_{i=1}^{n_{s}}$, where
$x_{s}^{i}\in\mathcal{X}_{s}$,
${y}_{s}^{i}\in\mathcal{Y}_{s}\subseteq\mathbb{R}^{K}$ and $y_{s}^{i}$ is the
one-hot ground-truth label with $K$ dimensions. For brevity, unless otherwise
stated, we neglect the superscript $i$ such as denoting $x_{s}^{i}$ as
$x_{s}$. The unlabeled target domain data with $n_{t}$ samples is denoted as
$D_{t}=\\{{x_{t}^{i}}\\}_{i=1}^{n_{t}}$, where $x_{t}^{i}\in\mathcal{X}_{t}$.
The label space of the two domains is shared while the marginal distribution
is different. The source model, denoted as $f_{s}(\cdot)=h_{s}(g_{s}(\cdot))$,
consists of feature extractor $g_{s}(\cdot):\mathcal{X}_{s}\to\mathbb{R}^{D}$
and classifier $h_{s}(\cdot):\mathbb{R}^{D}\to\mathbb{R}^{K}$ where $D$ is the
feature dimension. The source model is obtained by training the source data
with the standard cross-entropy loss
$L_{s}^{ce}=-\sum_{k=1}^{K}{\widetilde{y}_{s}^{k}{\rm log}p_{s}^{k}}$, where
$p_{s}^{k}=\sigma_{k}(f_{s}(x_{s}))$ is the $k$-th element of the model’s
output after the softmax operation $\sigma_{k}(a)=\frac{{\rm
exp}(a_{k})}{\sum_{j=1}^{K}{{\rm exp}(a_{j})}}$, and $\widetilde{y}_{s}^{k}$
is the $k$-th element of the converted one-hot label with label-smoothing
[28]: $\widetilde{y}_{s}^{k}=(1-\tau)y_{s}^{k}+\tau/K$, where $\tau$ is the
smoothness coefficient ($\tau=0.1$ in our experiment). SFDA aims to predict
the labels $\\{y_{t}^{i}\\}_{i=1}^{n_{t}}$ in the target domain where
$y_{t}^{i}\in\mathcal{Y}\subseteq\mathbb{R}^{K}$ by learning a target model
$f_{t}(\cdot):\mathcal{X}_{t}\to\mathcal{Y}_{t}$ based on the source model.
Similar to the formula for the source model, the target model is defined as
$f_{t}(\cdot)=h_{t}(g_{t}(\cdot))$.

###  3.2 Cycle Intermediate Domain Filtering

In order to reduce the distribution gap between the absent source data and the
target data, we utilize intermediate domain samples which conform to the
distribution characteristics of the target data while sharing high
similarities with the source data. Classification information is hidden in the
source classifier $h_{s}(\cdot)$ [29] and the prototype of each class can be
represented by the weight vector
$W_{s}=\\{{w_{k}};{w_{k}\in\mathbb{R}^{D\times K}\\}}_{k=1}^{K}$ of
$h_{s}(\cdot)$ [30]. We cyclically select the intermediate domain samples
$\\{\mathcal{X}_{m},\mathcal{Y}_{m}\\}={\\{x_{m}^{i},y_{m}^{i}\\}_{i=1}^{n_{m}}}$
by calculating their similarities with the prototypes, where $n_{m}$ is the
number of intermediate samples:

$\mathcal{X}_{m}^{k,\mathcal{C}}=\begin{cases}x_{m^{\prime}}^{k,\mathcal{C}},m^{\prime}\in\mathop{\rm
min}\limits_{t}{D_{\rm
sim}(g_{t}(x_{t}),w_{k})},&\rm{if}\;\mathcal{C}=\mathcal{T}\\\
\mathcal{X}_{m}^{k,\mathcal{C}-1},&\rm{otherwise}\end{cases}$ (1)

where $D_{\rm sim}(\cdot,\cdot)$ represents the distance metric, for which we
use the cosine distance by default. $\mathcal{T}$ and $\mathcal{C}$ denote the
epoch value of the selected intermediate samples and the current training
epoch value, respectively. $\rm min(\cdot)$ indicates that the top-$n_{m}$
samples most similar to the prototype in each class are selected as they have
the minimum distance with $W_{s}$. As the training progresses, the gap between
the source domain represented by the intermediate domain and target domain
will gradually decrease because the distribution of the features extracted by
the target model $g_{t}(\cdot)$ gradually approaches the target domain. We
denote $E$ as the maximum epoch, and the target model $g_{t}(\cdot)$ at epoch
$\mathcal{T}$ is used to filter out the intermediate samples. $\mathcal{T}$ is
defined as

$\begin{split}{\mathcal{T}}=e\cdot\alpha E\quad
s.t.\;0<\mathcal{T}<E,\end{split}$ (2)

where $e=\\{1,2,\cdots,\lfloor\frac{1}{\alpha}\rfloor\\}$ is the number of the
cycles and $\alpha$ is the ratio falling in [0, 1].

Similar to the source data, we directly employ the cross-entropy loss with
label smoothing as follows:

$\begin{split}\begin{aligned} &L_{\rm
int}(f_{t};\mathcal{X}_{m},\mathcal{Y}_{m})=&-\gamma\mathbb{E}_{(x_{m},y_{m})\in{X_{m}\times
Y_{m}}}\sum_{k=1}^{K}{l_{m}^{k}{\rm
log}\sigma_{k}(f_{t}(x_{m}^{k,\mathcal{C}}))},\end{aligned}\end{split}$ (3)

where $l_{m}^{k}=(1-\tau)y_{m}^{k}+\tau/K$ is the smoothed $k$-th element of
the one-hot label and $y_{m}$ is the intermediate domain label corresponding
to $x_{m}^{k,\mathcal{C}}$. $\gamma$ is the hyperparameter.

###  3.3 Inter-Domain Gap Transition

In order to make full use of the intermediate samples obtained by the
progressively adapted target model, we employ mixup regularization to diffuse
the effect of the intermediate samples on the entire target domain.
Specifically, given two samples $x_{m}$, $x_{t}$ and these labels from the
intermediate domain and target domain respectively, IDGT bridges the gap by
mixing these two samples:

$\begin{split}\widehat{x}_{u}=\lambda x_{m}+(1-\lambda)x_{t},\
\widehat{q}_{u}=\lambda q_{m}+(1-\lambda)\widehat{q}_{t},\end{split}$ (4)

where $\lambda\sim Beta(\beta,\beta)$ for $\beta\in(0,\infty)$, $q_{m}$ is the
one-hot encoding of $y_{m}$ and $\widehat{q}_{t}$ is the soft label of
$x_{t}$. To produce $\widehat{q}_{t}$, we build two memory banks:
$B_{z}=[z_{t}^{1},z_{t}^{2},···,z_{t}^{n_{t}}]$ that stores all the features
and $B_{p}=[p_{t}^{1},p_{t}^{2},...,p_{t}^{n_{t}}]$ that stores the
corresponding prediction scores, where $z_{t}=g(x_{t})$ and
$p_{t}=h_{t}(g_{t}(x_{t}))$. The historic items in the memory bank are updated
corresponding to the current batch and do not require any additional
computation. We then refine the target labels via nearest-neighbor soft voting
by averaging the probabilities associated with the $r$-nearest neighbors
${\cal N}_{r}$ in the target feature space, _i.e_.
$q_{t}=\frac{1}{r}\sum_{j=1}^{r}p_{t,j}$ , where $p_{t}\in{\cal N}_{r}$. We
calculate the gap transition loss $L_{\rm gap}$ by adopting the
Kullback–Leibler (KL) divergence, which can be mathematically expressed as
follows:

$\begin{split}L_{\rm
gap}(f_{t};\widehat{x}_{u},\widehat{q}_{u})=\frac{1}{D}\sum_{d=1}^{D}{\rm
KL}(\widehat{Q}_{u,(d,:)},Q_{u,(d,:)})=\frac{1}{D}\sum_{d=1}^{D}\sum_{k=1}^{K}\sigma_{k}(\widehat{q}_{u,(d,k)}{\rm
log}(\frac{\widehat{q}_{u,(d,k)}}{f_{t}(x_{u,(d,k)})})),\end{split}$ (5)

where $\widehat{Q},Q\in\mathbb{R}^{D\times K}$ are the logits before the
softmax operation.

###  3.4 Cross-View Consistency Learning

To promote the feature representation learning in the target model and seek
the consistent and complementary information across different views of one
image, we randomly draw two augmentations $t_{s}$ and $t_{s}^{\prime}$, and
augment $x_{t}$ into two views $x^{A}_{t}=t_{s}(x_{t})$ and
$x^{B}_{t}=t_{s}^{\prime}(x_{t})$. Inspired by standard contrastive learning
methods [31], we design a momentum encoder
$g_{t^{\prime}}(\cdot):\mathcal{X}_{t}\to{\mathbb{R}}^{D}$ and a 2-layer MLP
projection head $p_{t}(\cdot):{\mathbb{R}}^{D}\to{\mathbb{R}}^{D^{\prime}}$ to
support the local instance-level and global class-level consistent alignment
where ${D^{\prime}}$ is the output feature dimension of the 2-layer MLP
projection head. The objective of this process is to minimize the following
consistency loss function $L_{\rm con}$:

$\begin{split}L_{\rm con}=L_{\rm sam}+\varepsilon L_{\rm cls},\end{split}$ (6)

where $L_{\rm sam}$ is the local sample-level consistency loss and $L_{\rm
cls}$ is the global class-level consistency loss, which are defined in the
following. $\varepsilon$ is the trade-off parameter.

####  3.4.1 Local Sample-Level Consistency

Using a learnable non-linear projection head by contrastive loss has shown
promising results for representation learning. To maximize the similarity
between the two output embedding vectors of the projection heads, the feature
embeddings obtained by encoders $z_{t}=g_{t}(x_{t})$ and
$z_{t^{\prime}}=g_{t^{\prime}}(x_{t})$ are used to optimize the model with the
following loss:

$\begin{split}L_{\rm sam}(p_{t};z_{t},z_{t^{\prime}})=D_{\rm
NMSE}(p_{t}(z_{t}^{A}),p_{t}(z_{t^{\prime}}^{B}))+D_{\rm
NMSE}(p_{t}(z_{t^{\prime}}^{A}),p_{t}(z_{t}^{B})),\end{split}$ (7)

where $D_{\rm NMSE}(a,b)=||\xi(a)-\xi(b)||_{2}^{2}$ is the MSE loss with the
$l_{2}$-normalized input. As shown above, the symmetric loss is used to
compute two losses by swapping two data augmentations.

Algorithm 1 The training procedure of the proposed SIDE.

1:Target dataset $\mathcal{X}_{t}$, well-trained source model
$f_{s}=h_{s}(g_{s}(\cdot))$, hyperparameters $e$, $\alpha$, $\gamma$,
$\varepsilon$.

2:Target model $f_{t}=h_{t}(g_{t}(\cdot))$.

3:Initialize $f_{t}$ and $g_{t^{\prime}}$ with $f_{s}$ and $g_{t}$
respectively. Initialize $p_{t}$ randomly.

4:for ep = 1 to $E$ do

5: if ep mod ($e\cdot\alpha)$ = 0 then

6: Sample the intermediate data $\mathcal{X}_{m}$ using Eq. (1).

7: Calculate $L_{\rm int}$ using Eq. (3).

8: end if

9: Generate pseudo-labels.

10: Calculate $L_{\rm gap}$, $L_{\rm sam}$ and $L_{\rm cls}$ using Eq. (5),
Eq. (7) and Eq. (9), respectively.

11: Update momentum encoder $g_{t^{\prime}}$ using Eq. (8).

12: Update encoder $g_{t}$ and projector $p_{t}$ using Eqs. (3), (5) and (6).

13:end for

14:return Target model $f_{t}=h_{t}(g_{t}(\cdot))$.

In addition, the parameters $\theta_{t^{\prime}}$ of the momentum model
$g_{t^{\prime}}$ are updated with the momentum $\omega$ and the parameters
$\theta_{t}$ of $g_{t}$ at each mini-batch step instead of back-propagation:

$\begin{split}\theta_{t^{\prime}}\leftarrow\omega\theta_{t^{\prime}}+(1-\omega)\theta_{t}.\end{split}$
(8)

####  3.4.2 Global Class-Level Consistency

Existing self-supervised consistency methods consider that the final predicted
labels of two images should be as closer as possible if they are identical.
However, these methods are limited to instance-level prediction consistency
without learning compact and discriminative classification information at the
global class-level. The prediction of mini-batch
${{P_{t}}^{A}}=h_{t}(g_{t}(x_{t}^{A}))\in\mathbb{R}^{n\times K}$ and
${P_{t^{\prime}}^{B}}=h_{t}(g_{t^{\prime}}({x_{t}^{B}}))\in\mathbb{R}^{n\times
K}$ of views A and B are obtained by the encoder $g_{t}(\cdot)$ and the
momentum encoder $g_{t^{\prime}}(\cdot)$, followed by classifier
$h_{t}(\cdot)$. The cross-view correlation matrix $\mathcal{M}$ of different
encoders is obtained with
$\mathcal{M}={{P_{t}^{A}}^{T}P_{t^{\prime}}^{B}}\in\mathbb{R}^{K\times K}$.
Inspired by [32], we calculate the contrastive clustering loss for the
predicted values of each mini-batch:

$\begin{split}\begin{aligned} L_{\rm
cls}(f_{t};\mathcal{M})=\frac{{\mathcal{L}_{1}}(\xi({\mathcal{M}}),{I_{n}})+{\mathcal{L}_{1}}(\xi(\mathcal{M}^{T}),{I_{n}})}{2K},\end{aligned}\end{split}$
(9)

where $\mathcal{L}_{1}(\cdot)$ is the $\mathcal{L}_{1}$ loss and
${{I_{n}}\in{\mathbb{R}}^{K\times K}}$ is the identity matrix. $\xi(\cdot)$
indicates the normalization function of the matrix. Given coherence
constraints on the diagonal matrix and the predicted cross-correlation matrix,
SIDE can promote intra-class compactness and inter-class separability.

Algorithm 1 demonstrates the whole training procedure of our proposed SIDE.

Methods | A→D | A$\rightarrow$W | D$\rightarrow$A | D$\rightarrow$W | W$\rightarrow$A | W$\rightarrow$D | Avg.
---|---|---|---|---|---|---|---
Source-only | 80.9 | 75.6 | 59.5 | 92.8 | 60.5 | 99.2 | 78.1
DANN[21] | 79.7 | 82.0 | 68.2 | 96.9 | 67.4 | 99.1 | 82.2
CDAN[33] | 92.9 | 94.1 | 71.0 | 98.6 | 69.3 | 100.0 | 87.7
SRDC[34] | 95.6 | 95.7 | 76.7 | 99.2 | 77.1 | 100.0 | 90.8
MCC[35] | 95.8 | 95.4 | 75.6 | 98.6 | 73.9 | 100.0 | 89.4
BDG[36] | 93.6 | 93.6 | 73.2 | 99.0 | 72.0 | 100.0 | 88.5
BNM[37] | 90.3 | 91.5 | 70.9 | 98.5 | 71.6 | 100.0 | 87.1
SHOT[38] | 94.0 | 90.1 | 74.7 | 98.4 | 74.3 | 99.9 | 88.6
BAIT[39] | 91.0 | 93.0 | 75.0 | 99.0 | 75.3 | 100.0 | 88.9
CPGA[4] | 94.4 | 94.1 | 76.0 | 98.4 | 76.6 | 99.8 | 89.9
NRC[40] | 96.0 | 90.8 | 75.3 | 99.0 | 75.0 | 100.0 | 89.4
A2Net[41] | 94.5 | 94.0 | 76.7 | 99.2 | 76.1 | 100.0 | 90.1
HCL[42] | 92.5 | 94.7 | 75.9 | 98.2 | 77.7 | 100.0 | 89.8
AAA[6] | 95.6 | 94.2 | 75.6 | 98.1 | 76.0 | 99.8 | 89.9
DIPE[43] | 96.6 | 93.1 | 75.5 | 98.4 | 77.2 | 99.6 | 90.1
SIDE | 97.1 | 97.2 | 76.5 | 99.1 | 76.9 | 100.0 | 91.1

Table 1: Classification accuracy (%) on the Office-31 dataset. ‘A→D’ means A
is the source domain and D is the target domain. The best and second-best
results are shown in bold and with underline, respectively. Same notations are
used in all tables.

##  4 Experiments

###  4.1 Datasets

We evaluate our method on three benchmark datasets. Office-31 [44] is composed
of 4,652 images from 31 categories of everyday objects. The dataset consists
of 3 subsets: Amazon (A), Webcam (W), and DSLR (D). Office-Home [45] is a
challenging medium-sized benchmark with 65 categories and a total of 15,500
images. The dataset consists of 4 domains: Art (A), Clipart (C), Product (P),
and Real-world (R). VisDA-C [46] is another challenging and large-scale
dataset with 12 categories in two domains. Its source domain contains 152k
synthetic images generated by 3D rendering while the target domain has 55k
real object images.

Methods | Reference | A$\rightarrow$ C | A$\rightarrow$ P | A$\rightarrow$ R | C$\rightarrow$ A | C$\rightarrow$ P | C$\rightarrow$ R | P$\rightarrow$ A | P$\rightarrow$ C | P$\rightarrow$ R | R$\rightarrow$ A | R$\rightarrow$ C | R$\rightarrow$ P | Avg.
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Source-only | - | 38.1 | 58.9 | 69.4 | 48.3 | 57.7 | 61.1 | 49.4 | 36.4 | 69.9 | 64.7 | 43.7 | 75.4 | 56.1
DANN[21] | PMLR’15 | 45.6 | 59.3 | 70.1 | 47.0 | 58.5 | 60.9 | 46.1 | 43.7 | 68.5 | 63.2 | 51.8 | 76.8 | 57.6
CDAN[33] | NIPS’18 | 50.7 | 70.6 | 76.0 | 57.6 | 70.0 | 70.0 | 57.4 | 50.9 | 77.3 | 70.9 | 56.7 | 81.6 | 65.8
SRDC[34] | CVPR’20 | 52.3 | 76.3 | 81.0 | 69.5 | 76.2 | 78.0 | 68.7 | 53.8 | 81.7 | 76.3 | 57.1 | 85.0 | 71.3
BDG[36] | AAAI’20 | 51.5 | 73.4 | 78.7 | 65.3 | 71.5 | 73.7 | 65.1 | 49.7 | 81.1 | 74.6 | 55.1 | 84.8 | 68.7
BNM[37] | CVPR’20 | 52.3 | 73.9 | 80.0 | 63.3 | 72.9 | 74.9 | 61.7 | 49.5 | 79.7 | 70.5 | 53.6 | 82.2 | 67.9
SHOT[38] | PMLR’20 | 57.1 | 78.1 | 81.5 | 68.0 | 78.2 | 78.1 | 67.4 | 54.9 | 82.2 | 73.3 | 58.8 | 84.3 | 71.8
BAIT[39] | arXiv’20 | 57.4 | 77.5 | 82.4 | 68.0 | 77.2 | 75.1 | 67.1 | 55.5 | 81.9 | 73.9 | 59.5 | 84.2 | 71.6
A2Net[41] | ICCV’21 | 58.4 | 79.0 | 82.4 | 67.5 | 79.3 | 78.9 | 68.0 | 56.2 | 82.9 | 74.1 | 60.5 | 85.0 | 72.8
CPGA[4] | IJCAI’21 | 59.3 | 78.1 | 79.8 | 65.4 | 75.5 | 76.4 | 65.7 | 58.0 | 81.0 | 72.0 | 64.4 | 83.3 | 71.6
NRC[40] | NIPS’21 | 57.7 | 80.3 | 82.0 | 68.1 | 79.8 | 78.6 | 65.3 | 56.4 | 83.0 | 71.0 | 58.6 | 85.6 | 72.2
AAA[6] | TPAMI’21 | 56.7 | 78.3 | 82.1 | 66.4 | 78.5 | 79.4 | 67.6 | 53.5 | 81.6 | 74.5 | 58.4 | 84.1 | 71.8
DIPE[43] | CVPR’22 | 56.5 | 79.2 | 80.7 | 70.1 | 79.8 | 78.8 | 67.9 | 55.1 | 83.5 | 74.1 | 59.3 | 84.8 | 72.5
SIDE | Ours | 56.9 | 79.7 | 82.5 | 70.1 | 79.4 | 80.0 | 68.5 | 55.2 | 84.0 | 74.3 | 60.6 | 85.2 | 73.0

Table 2: Classification accuracy (%) on the Office-Home dataset.

Methods | Reference | plane | bike | bus | cat | horse | kniffe | mcycle | person | plant | sktbrd | train | truck | Avg.
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Source-only | - | 67.9 | 11.1 | 57.7 | 70.9 | 63.3 | 8.9 | 79.1 | 21.6 | 68.1 | 16.8 | 84.6 | 9.4 | 46.6
DANN[21] | PMLR‘15 | 81.9 | 77.7 | 82.8 | 44.3 | 81.2 | 29.5 | 65.1 | 28.6 | 51.9 | 54.6 | 82.8 | 7.8 | 57.4
CDAN[33] | NIPS’18 | 85.2 | 66.9 | 83.0 | 50.8 | 84.2 | 74.9 | 88.1 | 74.5 | 83.4 | 76.0 | 81.9 | 38.0 | 73.9
SWD[47] | CVPR’19 | 90.8 | 82.5 | 81.7 | 70.5 | 91.7 | 69.5 | 86.3 | 77.5 | 87.5 | 63.6 | 85.6 | 29.2 | 76.4
MCC[35] | ECCV’20 | 88.7 | 80.3 | 80.5 | 71.5 | 90.1 | 93.2 | 85.0 | 71.6 | 89.4 | 73.8 | 85.0 | 36.9 | 78.8
CoSCA[48] | ACCV’20 | 95.7 | 87.4 | 85.7 | 73.5 | 95.3 | 72.8 | 91.5 | 84.8 | 94.6 | 87.9 | 87.9 | 36.9 | 82.9
PAL[49] | arXiv’20 | 90.9 | 50.5 | 72.3 | 82.7 | 88.3 | 88.3 | 90.3 | 79.8 | 89.7 | 79.2 | 88.1 | 39.4 | 78.3
SHOT[38] | PMLR’20 | 94.3 | 88.5 | 80.1 | 57.3 | 93.1 | 94.9 | 80.7 | 80.3 | 91.5 | 89.1 | 86.3 | 58.2 | 82.9
BAIT[39] | arXiv’20 | 93.7 | 83.2 | 84.5 | 65.0 | 92.9 | 95.4 | 88.1 | 80.8 | 90.0 | 89.0 | 84.0 | 45.3 | 82.7
A2Net[41] | ICCV’21 | 94.0 | 87.8 | 85.6 | 66.8 | 93.7 | 95.1 | 85.8 | 81.2 | 91.6 | 88.2 | 86.5 | 56.0 | 84.3
HCL[42] | NIPS’21 | 93.3 | 85.4 | 80.7 | 68.5 | 91.0 | 88.1 | 86.0 | 78.6 | 86.6 | 88.8 | 80.0 | 74.7 | 83.5
AAA[6] | TPAMI’21 | 94.4 | 85.9 | 74.9 | 60.2 | 96.0 | 93.5 | 87.8 | 80.8 | 90.2 | 92.0 | 86.6 | 68.3 | 84.2
DIPE[43] | CVPR’22 | 95.2 | 87.6 | 78.8 | 55.9 | 93.9 | 95.0 | 84.1 | 81.7 | 92.1 | 88.9 | 85.4 | 58.0 | 83.1
SIDE | Ours | 95.9 | 84.3 | 83.7 | 68.7 | 93.9 | 92.2 | 91.3 | 79.3 | 93.3 | 93.2 | 88.2 | 56.8 | 85.1

Table 3: Classification accuracy (%) on the VisDA-C dataset.

###  4.2 Compared Methods

We compare our method with different kinds of state-of-the-art methods,
including 1) source-only: ResNet [50]; 2) unsupervised domain adaptation with
source data: DANN[21], CDAN[33], SRDC[34], MCC[35], BDG[36], BNM [37],
SWD[47], CoSCA[48], and PAL[49]; 3) source-free unsupervised domain
adaptation: SHOT[38], BAIT[39], CPGA[4], NRC[40], BDT[51], A2Net[41], HCL[42],
AAA[6], and DIPE[43].

###  4.3 Implementation Details

All the experiments are conducted using the PyTorch library. For fair
comparison, we also use ResNet-50 as the backbone for the Office datasets and
ResNet-101 [50] for VisDA-C as the feature encoder. The projection head is a
2-layer MLP and the classifier follows SHOT [38] to add a bottleneck
consisting of a fully-connected layer, followed by a batch normalization
layer. We train the source model using the SGD optimizer with the learning
rate of 1e-3 for the backbone and 1e-2 for the classifier. In the adaptation
stage, we set the learning rate to 1e-3 for the backbone and 1e-2 for
projection. We set the training epoch to 100, 40 and 2 for Office, Office-Home
and VisDA, respectively. For hyperparameters, we set $\alpha$ and $e$ in Eq.
(2) as 0.3 and 2, respectively. The $\gamma$ in Eq. (3) and $\epsilon$ in Eq.
(6) are set to 0.1 and 0.01. Following [24], we adopt $n_{m}$ = 5, 5, 50 in
Eq. (1) for Office-31, Office-Home and VisDA-C, respectively. All the results
are averaged over three runs with seeds $\in$ 0, 1, 2.

Figure 3: Average accuracy of intermediate data(left) and Average accuracy on
intermediate and target data. The adaptability of the target model is closely
correlated with the screening ability of the intermediate data in the CIDF
module(right).

###  4.4 Results

Office-31. On this dataset, the transfer of task D $\rightarrow$ W and W
$\rightarrow$ D are relatively simple due to the small gap between D and W,
while there is still much room for improvement in other tasks. As shown in
Table 1, the proposed SIDE outperforms most state-of-the-art methods and the
improvement on A $\rightarrow$ D and A $\rightarrow$ W is especially obvious.
Compared to SRDC, the current best UDA method on Office-31, our proposed
method gains the improvement of 0.3%. Compared with the best result of the
previous SFDA method, SIDE improves the accuracy by 1.0%.

Office-Home. As we can see from Table 2, our method achieves the best
performance in average accuracy on this dataset, compared with the other SFDA
methods. The best or second-best results are achieved by our method in terms
of 10 out of 12 transfer tasks. The results are consistent with our
expectations that our method can also perform well on relatively large
dataset.

VisDA-C. From Table 3, we can observe that SIDE achieves the best accuracy or
second-best accuracy in terms of more than half of the categories and obtains
comparable results in the rest categories on this large-scale dataset. The
experimental results above clearly demonstrate the effectiveness of our method
in addressing the multi-scale and domain-gap challenges.

In summary, our method achieves the above promising results mainly due to the
introduction of self-supervised learning, which is beneficial for learning the
feature distribution of the target domain. In the meantime, both CIDF and IDGT
modules can effectively reduce the implicit domain gap. Different from the
methods based on pseudo source domain generation, SIDE avoids changing the
intrinsic structure of the target domain when aligning the target domain with
the pseudo-source domain.

Backbone | CIDF | IDGT | CVCL | Office-31 | Office-Home
---|---|---|---|---|---
✓ |  |  |  | 78.1 | 56.1
✓ | ✓ |  |  | 84.8 | 64.1
✓ |  |  | ✓ | 87.1 | 69.2
✓ | ✓ |  | ✓ | 87.6 | 69.4
✓ | ✓ | ✓ |  | 90.8 | 71.4
✓ | ✓ | ✓ | ✓ | 91.1 | 73.0

Table 4: Ablation study on the loss functions.

$\alpha$ | $e$ |
---|---|---
| 0.1 | 0.2 | 0.3 | 0.4 | 0.5 | 1 | 2 | 3 | 4
| 68.7 | 69.5 | 70.1 | 69.7 | 69.9 | 68.9 | 70.1 | 69.1 | 69.4

Table 5: Influence of the trade-off parameter $\alpha$ and $e$ in C → A
accuracy (%) on the Office-Home dataset.

Figure 4: Results of parameter $\gamma$(left) and $\varepsilon$(right)
sensitivity.

###  4.5 Ablation Study

Intermediate Samples Selection. To verify the effectiveness of the cyclically
selected intermediate samples, we compare non-cyclic filtering (_i.e._ the
intermediate samples are only selected once before the model training) with
cyclic filtering during the training process. As Fig. 3 shows, the experiment
shows that with cyclic filtering, the accuracy of the selected intermediate
domain samples is improved from 92.9% to 96.1% in D $\rightarrow$ A, and the
corresponding test in the target domain can also obtain accuracy improvement
of 5.4%. Similarly, except for the relatively simple domain adaptation tasks W
$\rightarrow$ D and D $\rightarrow$ W, the final adaptation outcome in the
other tasks is corresponding to the outcome on the intermediate data.

Hyperparameters. In this subsection, we evaluate the sensitivity of
hyperparameters with the tasks A $\rightarrow$ C, P $\rightarrow$ C, R
$\rightarrow$ C on Office-Home. Table 5 shows the sensitivity of performance
with $e\in$ {0.1, 0.3, 0.5, 0.7, 0.9} and $\alpha\in$ {0.005, 0.01, 0.02,
0.03, 0.04} in Eq. (2). The results show that our method is insensitive to
both parameters. Because the proposed CIDF, IGDT and CVCL alternatively
promote each other by providing positive feedback. The more optimized the
model can be during the training process, the more reliable the selection of
intermediate samples becomes. Furthermore, we evaluate $\varepsilon$ and
$\gamma$ on Office-Home, and as shown in Fig. 4, our method is not sensitive
to these hyperparameters either.

(a) Source-only

(b) SHOT

(b) SIDE

(b) Source-only

(b) SHOT

(b) SIDE

Figure 5: The t-SNE visualizations of different methods on the target domain
(Webcam) of the Office-31 task A → W. The first row shows the visualization of
category features in the target domain where the different colors denote
different categories. The second row shows the visualization of the filtered
intermediate samples (in red) and other target samples (in blue). Best viewed
in color.

Component Analysis. To investigate the effectiveness of the proposed modules
in the adaptation phase, the quantitative results of the model with different
components are shown in Table 4. 1) When only using CIDF, the performance
increases by 6.7% and 8.0% on Office-31 and Office-Home, respectively,
compared to the source-only model. The partial samples in the target domain
serve as the intermediate domain to implicitly align the distributions. 2)
Introducing CVCL alone encourages the model to learn a deeper internal
structure of the target domain, increasing the model performance
significantly. It is worth noting that IDGT cannot be used alone as it depends
on the intermediate samples from CIDF. 3) Using CIDF and CVCL at the same time
can improve the adaptability of the model but not achieve the optimal
performance. Because the intermediate sample does not play its role at this
time and the two modules lack a bridge to promote each other. 4) Combining
CIDF and IDGT, the model can better be adapted to the target domain as the
intermediate data is used as a pedal to eliminate the domain gap. This
combination ignores the learning of the internal distribution information of
the target domain in the absence of CVCL. 5) The best results can only be
achieved when combining all three modules as they reinforce each other to
improve the adaptability of the target model.

t-SNE Visualization. We show the t-SNE feature visualization on the task A → W
of target features on Office-31. In Fig. 5 (a), the feature distribution is
rather chaotic when using only the source domain model. After the adaptation
of the SIDE method, as shown in Fig. 5 (c), the features of the same category
are closely related. Its classification boundary is more discriminative and
the distribution is more compact compared with SHOT, as shown in Fig. 5 (b).
This is because the category information of the target domain has been deeply
examined by the CVCL module through self-supervised learning, without changing
the intrinsic structure of the target domain by the alignment of the two
domains.

The distribution of the intermediate samples in the target domain is also
visualized. As shown in Fig. 5 (f), the intermediate domain samples obtained
by CIDF gather in the center of a certain category feature. Compared with the
method without any adaptation strategy in Fig. 5 (d), the distance between
intermediate samples in the same class selected by SIDE is closer. The
promotion of CIDF is benefited by the CVCL module mining the semantic
information of the target domain and the IDGT module strengthening the
influence of intermediate samples through data augmentation. The method using
other adaptation strategies in Fig. 5 (e) can also enhance intra-class
compactness to a certain extent, but there is still inter-class adhesion.

##  5 Conclusion

In this paper, we propose a novel method named SIDE to tackle the task of
source-free domain adaptation via cyclically exploiting the intermediate
samples. With the help of intermediate samples, SIDE effectively bridges the
gap between the unseen source and target domains. The instance- and class-
level consistency learning across different views gradually improves the
classification capability of the target model by learning more discriminative
features. Extensive experiments on three datasets show that our proposed SIDE
outperforms other state-of-the-art methods.

## References

  * [1] Weijie Chen, Luojun Lin, Shicai Yang, Di Xie, Shiliang Pu, and Yueting Zhuang.  Self-supervised noisy label learning for source-free unsupervised domain adaptation.  In IROS, 2022.
  * [2] Shiqi Yang, Yaxing Wang, Joost van de Weijer, Luis Herranz, and Shangling Jui.  Generalized source-free domain adaptation.  In ICCV, 2021.
  * [3] Vinod K Kurmi, Venkatesh K Subramanian, and Vinay P Namboodiri.  Domain impression: A source data free domain adaptation method.  In WACV, 2021.
  * [4] Zhen Qiu, Yifan Zhang, Hongbin Lin, Shuaicheng Niu, Yanxia Liu, Qing Du, and Mingkui Tan.  Source-free domain adaptation via avatar prototype generation and adaptation.  IJCAI, 2021.
  * [5] Cian Eastwood, Ian Mason, Christopher KI Williams, and Bernhard Schölkopf.  Source-free adaptation to measurement shift via bottom-up feature restoration.  ICLR, 2022.
  * [6] Jingjing Li, Zhekai Du, Lei Zhu, Zhengming Ding, Ke Lu, and Heng Tao Shen.  Divergence-agnostic unsupervised domain adaptation by adversarial attacks.  PAMI, 2021.
  * [7] Jing Jiang and ChengXiang Zhai.  Instance weighting for domain adaptation in nlp.  In ACL, 2007.
  * [8] Rui Wang, Masao Utiyama, Lemao Liu, Kehai Chen, and Eiichiro Sumita.  Instance weighting for neural machine translation domain adaptation.  In EMNLP, 2017.
  * [9] Yi Yao and Gianfranco Doretto.  Boosting for transfer learning with multiple sources.  In CVPR, 2010.
  * [10] Raghuraman Gopalan, Ruonan Li, and Rama Chellappa.  Domain adaptation for object recognition: An unsupervised approach.  In ICCV, 2011.
  * [11] Boqing Gong, Yuan Shi, Fei Sha, and Kristen Grauman.  Geodesic flow kernel for unsupervised domain adaptation.  In CVPR, 2012.
  * [12] Baochen Sun and Kate Saenko.  Subspace distribution alignment for unsupervised domain adaptation.  In BMVC, 2015.
  * [13] Samitha Herath, Mehrtash Harandi, and Fatih Porikli.  Learning an invariant hilbert space for domain adaptation.  In CVPR, 2017.
  * [14] Si Si, Dacheng Tao, and Bo Geng.  Bregman divergence-based regularization for transfer subspace learning.  IEEE TKDE, 22(7):929–942, 2009.
  * [15] Ji Liu and Lei Zhang.  Optimal projection guided transfer hashing for image retrieval.  In AAAI, 2019.
  * [16] Weifeng Ge and Yizhou Yu.  Borrowing treasures from the wealthy: Deep transfer learning through selective joint fine-tuning.  In CVPR, 2017.
  * [17] Xu Zhang, Felix Xinnan Yu, Shih-Fu Chang, and Shengjin Wang.  Deep transfer network: Unsupervised domain adaptation.  arXiv preprint arXiv:1503.00591, 2015.
  * [18] Mingsheng Long, Yue Cao, Jianmin Wang, and Michael Jordan.  Learning transferable features with deep adaptation networks.  In ICML, 2015.
  * [19] Lei Zhang, Qingyan Duan, David Zhang, Wei Jia, and Xizhao Wang.  Advkin: Adversarial convolutional network for kinship verification.  IEEE TCYB, 51(12):5883–5896, 2020.
  * [20] Yuntao Du, Haiyang Yang, Mingcai Chen, Juan Jiang, Hongtao Luo, and Chongjun Wang.  Generation, augmentation, and alignment: A pseudo-source domain based method for source-free domain adaptation.  AAAI, 2022.
  * [21] Yaroslav Ganin and Victor Lempitsky.  Unsupervised domain adaptation by backpropagation.  In ICML, 2015.
  * [22] Jian Liang, Dapeng Hu, Yunbo Wang, Ran He, and Jiashi Feng.  Source data-absent unsupervised domain adaptation through hypothesis transfer and labeling transfer.  PAMI, 2021.
  * [23] Youngeun Kim, Donghyeon Cho, Kyeongtak Han, Priyadarshini Panda, and Sungeun Hong.  Domain adaptation without source data.  IEEE Transactions on Artificial Intelligence, 2(6):508–518, 2021\.
  * [24] Yuhe Ding, Lijun Sheng, Jian Liang, Aihua Zheng, and Ran He.  Proxymix: Proxy-based mixup training with label refinery for source-free domain adaptation.  arXiv preprint arXiv:2205.14566, 2022.
  * [25] Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He.  Improved baselines with momentum contrastive learning.  arXiv preprint arXiv:2003.04297, 2020.
  * [26] Xinlei Chen and Kaiming He.  Exploring simple siamese representation learning.  In CVPR, 2021.
  * [27] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, et al.  Bootstrap your own latent-a new approach to self-supervised learning.  NIPS, 2020.
  * [28] Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna.  Rethinking the inception architecture for computer vision.  In CVPR, 2016.
  * [29] Shoukai Xu, Haokun Li, Bohan Zhuang, Jing Liu, Jiezhang Cao, Chuangrun Liang, and Mingkui Tan.  Generative low-bitwidth data free quantization.  In ECCV, 2020.
  * [30] Kuniaki Saito, Kohei Watanabe, Yoshitaka Ushiku, and Tatsuya Harada.  Maximum classifier discrepancy for unsupervised domain adaptation.  In CVPR, 2018.
  * [31] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick.  Momentum contrast for unsupervised visual representation learning.  In CVPR, 2020.
  * [32] Zizheng Yan, Yushuang Wu, Guanbin Li, Yipeng Qin, Xiaoguang Han, and Shuguang Cui.  Multi-level consistency learning for semi-supervised domain adaptation.  IJCAI, 2022.
  * [33] Mingsheng Long, Zhangjie Cao, Jianmin Wang, and Michael I Jordan.  Conditional adversarial domain adaptation.  NIPS, 31, 2018.
  * [34] Hui Tang, Ke Chen, and Kui Jia.  Unsupervised domain adaptation via structurally regularized deep clustering.  In CVPR, 2020.
  * [35] Ying Jin, Ximei Wang, Mingsheng Long, and Jianmin Wang.  Minimum class confusion for versatile domain adaptation.  In ECCV, 2020.
  * [36] Guanglei Yang, Haifeng Xia, Mingli Ding, and Zhengming Ding.  Bi-directional generation for unsupervised domain adaptation.  In AAAI, 2020.
  * [37] Shuhao Cui, Shuhui Wang, Junbao Zhuo, Liang Li, Qingming Huang, and Qi Tian.  Towards discriminability and diversity: Batch nuclear-norm maximization under label insufficient situations.  In CVPR, 2020.
  * [38] Jian Liang, Dapeng Hu, and Jiashi Feng.  Do we really need to access the source data? source hypothesis transfer for unsupervised domain adaptation.  In ICML, 2020.
  * [39] Shiqi Yang, Yaxing Wang, Joost van de Weijer, Luis Herranz, and Shangling Jui.  Unsupervised domain adaptation without source data by casting a bait.  arXiv preprint arXiv:2010.12427, 1(2):5, 2020.
  * [40] Shiqi Yang, Joost van de Weijer, Luis Herranz, Shangling Jui, et al.  Exploiting the intrinsic neighborhood structure for source-free domain adaptation.  NIPS, 2021.
  * [41] Haifeng Xia, Handong Zhao, and Zhengming Ding.  Adaptive adversarial network for source-free domain adaptation.  In ICCV, 2021.
  * [42] Jiaxing Huang, Dayan Guan, Aoran Xiao, and Shijian Lu.  Model adaptation: Historical contrastive learning for unsupervised domain adaptation without source data.  NIPS, 2021.
  * [43] Fan Wang, Zhongyi Han, Yongshun Gong, and Yilong Yin.  Exploring domain-invariant parameters for source free domain adaptation.  In CVPR, 2022.
  * [44] Kate Saenko, Brian Kulis, Mario Fritz, and Trevor Darrell.  Adapting visual category models to new domains.  In ECCV, 2010.
  * [45] Hemanth Venkateswara, Jose Eusebio, Shayok Chakraborty, and Sethuraman Panchanathan.  Deep hashing network for unsupervised domain adaptation.  In CVPR, 2017.
  * [46] Xingchao Peng, Ben Usman, Neela Kaushik, Judy Hoffman, Dequan Wang, and Kate Saenko.  Visda: The visual domain adaptation challenge.  arXiv preprint arXiv:1710.06924, 2017.
  * [47] Chen-Yu Lee, Tanmay Batra, Mohammad Haris Baig, and Daniel Ulbricht.  Sliced wasserstein discrepancy for unsupervised domain adaptation.  In CVPR, 2019.
  * [48] Shuyang Dai, Yu Cheng, Yizhe Zhang, Zhe Gan, Jingjing Liu, and Lawrence Carin.  Contrastively smoothed class alignment for unsupervised domain adaptation.  In ACCV, 2020.
  * [49] Dapeng Hu, Jian Liang, Qibin Hou, Hanshu Yan, Yunpeng Chen, Shuicheng Yan, and Jiashi Feng.  Panda: Prototypical unsupervised domain adaptation.  arXiv preprint arXiv:2003.13274, 1, 2020.
  * [50] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In CVPR, 2016.
  * [51] Jogendra Nath Kundu, Akshay R Kulkarni, Suvaansh Bhambri, Deepesh Mehta, Shreyas Anand Kulkarni, Varun Jampani, and Venkatesh Babu Radhakrishnan.  Balancing discriminability and transferability for source-free domain adaptation.  In ICML, 2022.


$E(X_{\mathcal{C}})$, the disjointedness of the proposed edge sets follows
from the analogous statement on the vertices $V(X_{\mathcal{C}})$. To show the
union, consider arbitrary $e=\\{a,b\\}\in E(X_{\mathcal{C}})$ not either
$\\{v,v_{1}\\}$ or $\\{v_{d},w\\}$, and consider vertex $a$: if $a\in
V(\mathcal{C}_{1}^{*})$, then we must have $b\in V(\mathcal{C}_{1}^{*})$ and
$e\in E(\mathcal{C}_{1}^{*})$ by construction of $\mathcal{C}_{1}^{*}$. A
similar argument holds if we initially assume $a\in V(\mathcal{C}_{2}^{*})$ or
$a\in V(\mathcal{P}^{*})$, so every $e\in E(X_{\mathcal{C}})$ lies in
$E(\mathcal{C}_{1}^{*}),E(\mathcal{C}_{2}^{*}),E(\mathcal{P}^{*})$, or
$\\{\\{v,v_{1}\\},\\{v_{d},w\\}\\}$.

It also follows from this decomposition that any path from a vertex in
$V(\mathcal{C}_{1}^{*})$ to a vertex in $V(\mathcal{C}_{2}^{*})$ necessarily
involves all vertices of $\mathcal{P}$ at some point, in order respecting that
of $\mathcal{P}$. Specifically, let
$\tilde{\mathcal{P}}=\\{\nu_{0},\nu_{1},\nu_{2},\dots,\nu_{k}\\}$ with
$\nu_{0}\in V(\mathcal{C}_{1}^{*})$ and $\nu_{k}\in V(\mathcal{C}_{2}^{*})$ be
such a path. Certainly, we have that $v\in\tilde{\mathcal{P}}$ and is the
earliest vertex of $\mathcal{P}$ in $\tilde{\mathcal{P}}$, as any edge
traversed from $\nu_{0}\in V(\mathcal{C}_{1}^{*})$ must either be in
$E(\mathcal{C}_{1}^{*})$ or be equal to $\\{v,v_{1}\\}$. Now assume the
vertices $\\{v,v_{1},\dots,v_{i}\\}$ have appeared in $\mathcal{P}$, following
this order. Starting from an occurrence of the vertex $v_{i}$,
$\tilde{\mathcal{P}}$ pursues a sequence of edges that either immediately goes
to $v_{i-1}$ or $v_{i+1}$ (i.e. the next edge is $\\{v_{i-1},v_{i}\\}$ or
$\\{v_{i},v_{i+1}\\}$) or eventually returns to $v_{i}$ after traversing
vertices in $V(\mathcal{P}^{*})\setminus V(\mathcal{P}^{(0)})$ (returning to a
different vertex in $\mathcal{P}^{(0)}$ first would give the existence of a
barbell subgraph with shorter connecting path, a contradiction on the choice
of $\mathcal{B}$). In particular, the next new vertex of $\mathcal{P}$ that
appears in $\tilde{\mathcal{P}}$ exists, and must necessarily be $v_{i+1}$.

Figure 14: Schematic diagram illustrating this decomposition. Since
$\mathcal{P}$ is the shortest path in any barbell subgraph of
$X_{\mathcal{C}}$ and there does not exist another path $\mathcal{P}^{\prime}$
connecting vertices in $V(\mathcal{C}_{1})$ and $V(\mathcal{C}_{2})$,
$X_{\mathcal{C}}$ must possess this structure. Indeed, if the vertex sets of
$\mathcal{C}_{1}^{*}$, $\mathcal{C}_{2}^{*}$, and $\mathcal{P}^{*}$ were not
pairwise disjoint, we would raise a contradiction on either the minimality of
the length of $\mathcal{P}$ in a barbell subgraph of $X_{\mathcal{C}}$ or the
nonexistence of a second such path $\mathcal{P}^{\prime}$. From here, it
should be clear that every vertex in $\mathcal{P}$ must be visited at least
four times in any optimal swap sequence achieving a cycle in
$\mathsf{FS}(X_{\mathcal{C}},\text{Star}_{n})$.

Here, we must necessarily visit each vertex in $\mathcal{P}$ at least four
times via the swap sequence $\mathcal{S}$, which will show that
$\mathcal{S}_{\mathcal{B}}$ cannot be improved. Indeed, assume the contrary:
certainly the path $\mathcal{P}$ is crossed an even number of times (to return
to a starting vertex in $\mathcal{C}_{1}^{*}$, where we shall assume without
loss of generality $n\in V(\text{Star}_{n})$ begins its traversal), so
$\mathcal{P}$ is crossed exactly twice. But then $\mathcal{S}$ must have
completed some cycle in $\mathsf{FS}(X,\text{Star}_{n})$ strictly on the
subgraph $V(\mathcal{C}_{2}^{*})$ as we do not return there, a contradiction
on $\mathcal{S}$ as a sequence of swaps achieving the girth of
$\mathsf{FS}(X,\text{Star}_{n})$, as there exists a strictly improved sequence
of swaps that is a proper contiguous subset of the sequence of swaps given by
$\mathcal{S}$ that yields a cycle in $\mathsf{FS}(X,\text{Star}_{n})$, a
contradiction on the optimality of $\mathcal{S}$. ∎

From the discussion following Problem 4.7 concerning the graphs in
$\mathcal{G}$ and Theorem 4.15, we can deduce that any graph in $\mathcal{G}$
does not have a proper barbell subgraph, which significantly improves our
understanding of the possible graphs that lie in $\mathcal{G}$, and thus the
possible trajectories $\mathfrak{n}$ takes around a graph $X$ to achieve the
girth of $\mathsf{FS}(X,\text{Star}_{n})$.

######  Proposition 4.16.

Let $\mathcal{G}^{\prime}$ include the set of graphs $\tilde{\mathcal{G}}$
from Theorem 4.14, as well as all instances of $\theta_{4}$, $\theta_{5}$,
$\tilde{\theta_{6}}$, $K_{4}^{*}$, and $K_{3,3}^{*}$-graphs, as depicted in
Figure 15. Then $\mathcal{G}\subset\mathcal{G}^{\prime}$.

(a) $\theta_{4}$-graphs.

(b) $\theta_{5}$-graphs.

(c) $\tilde{\theta_{6}}$ graphs.

(d) $K_{4}^{*}$-graphs.

(e) $K_{3,3}^{*}$-graphs.

Figure 15: The remaining possibilities for types of graphs in the set
$\mathcal{G}$. Here, the lines between vertices in the graphs correspond to
paths, possibly with several inner vertices. The hatch mark on one of the
paths in (c) indicates that one of the six paths between the vertices of
degree $6$ necessarily must be an edge, or it would immediately be seen to not
be in $\mathcal{G}$. If we interpret the paths of the two graphs in the bottom
row as edges, observe that the resulting graphs would be isomorphic to $K_{4}$
and $K_{3,3}$.

###### Proof.

As discussed above, no graph $G\in\mathcal{G}$ has a proper barbell subgraph.
Recall that if $G$ is not a cycle graph, it must contain at least two cycle
subgraphs: as such, any such $G$ that is not a cycle, barbell, or a
$\theta$-graph must contain a proper $\theta$-subgraph by Lemma 4.10. Take any
such graph $G$ with a proper $\theta$-subgraph $G_{\theta}$, and let its two
vertices of degree $3$ be denoted $v$ and $w$.

##### Case 1: Either $v$ or $w$ has degree greater than $3$.

Without loss of generality, say $v$ has degree greater than $3$, and consider
an edge incident to $v$ that does not lie in $G_{\theta}$. Continue selecting
edges along a path until we return to a vertex in $G_{\theta}$: this must be
$w$ to avoid a proper barbell subgraph of $G$; call the resulting graph
$G_{\theta}^{\prime}$. From here, it is straightforward to observe that all
vertices in $V(G_{\theta})\setminus\\{v,w\\}$ have degree $2$ in $G$, and the
only way we can append to $G_{\theta}^{\prime}$ is to include additional paths
between $v$ and $w$.

First assume all paths from $v$ to $w$ in $G$ are not edges: any optimal
traversal of $G$ (i.e. that yielding $g(\mathsf{FS}(G,\text{Star}_{n}))$ that
uses a path traverses it at least twice, so $G$ has at most five paths
(indeed, if $G$ had six or more paths, invoke the trajectory given by
Proposition 4.13 on the three shortest paths). If a path from $v$ to $w$ has
(exactly) one edge, then by analogous reasoning, $G$ can have at most six
paths.

##### Case 2: Both $v$ and $w$ have degree $3$.

Let (without loss of generality) $x_{1}\in
V(\mathcal{C}_{1})\setminus\\{v,w\\}$: selecting edges along a path until we
return to a vertex in $G_{\theta}$ must yield $x_{1}^{\prime}\in
V(\mathcal{C}_{2})\setminus\\{v,w\\}$. If there exists a second path from
$x_{2}\in V(\mathcal{C}_{1})\setminus\\{v,w\\}$ to $x_{2}^{\prime}\in
V(\mathcal{C}_{2})\setminus\\{v,w\\}$, we must have
$d_{\mathcal{C}_{1}}(x_{1},v)<d_{\mathcal{C}_{1}}(x_{1}^{\prime},v)$ and
$d_{\mathcal{C}_{2}}(x_{2},w)<d_{\mathcal{C}_{2}}(x_{2}^{\prime},w)$ (again
without loss of generality): if
$d_{\mathcal{C}_{1}}(x_{1},v)<d_{\mathcal{C}_{1}}(x_{1}^{\prime},v)$ and
$d_{\mathcal{C}_{2}}(x_{2},w)>d_{\mathcal{C}_{2}}(x_{2}^{\prime},w)$, there
would exist a proper barbell subgraph, as depicted in Figure 16(a). However,
three such paths necessarily yield a proper barbell subgraph: this follows
from the preceding discussion if we do not have
$d_{\mathcal{C}_{1}}(x_{1},v)<d_{\mathcal{C}_{1}}(x_{2},v)<d_{\mathcal{C}_{1}}(x_{3},v)$,
$d_{\mathcal{C}_{2}}(x_{1}^{\prime},w)<d_{\mathcal{C}_{2}}(x_{2}^{\prime},w)$,
$d_{\mathcal{C}_{2}}(x_{3}^{\prime},w))$, while this case still yields a
proper barbell subgraph as depicted in Figure 16(b). ∎

(a) Two paths above $G_{\theta}$ that fail to cross.

(b) Three paths above $G_{\theta}$ with any two crossing.

Figure 16: Illustrations corresponding to Case 2 in the proof of Proposition
4.16, showing the existence of a proper barbell subgraph. The two cycle
subgraphs of the proper barbell subgraph are colored in red and blue. The
vertices of degree $3$ in the proper $\theta$-subgraph $G_{\theta}$ are
denoted by $v$ and $w$.

######  Proposition 4.17.

Let $X$ be a $\theta_{4}$-graph with paths
$\mathcal{P}_{1},\mathcal{P}_{2},\mathcal{P}_{3},\mathcal{P}_{4}$ between the
vertices $v,w\in V(X)$ with degree $4$, with corresponding path lengths
$p_{1}=1<p_{2}\leq p_{3}\leq p_{4}$, respectively. If
$4+4p_{2}+2(p_{3}+p_{4})<\min\\{p_{2}(p_{2}+1),4(p_{2}+p_{3}+p_{4}),6(1+p_{2}+p_{3})\\}$,
then $X\in\mathcal{G}$.

Such graphs $X$ certainly exist. For example, let
$(p_{1},p_{2},p_{3},p_{4})=(1,p,p,p)$ for $p\geq 8$: we have that
$4+4p_{2}+2(p_{3}+p_{4})<\min\\{p_{2}(p_{2}+1),4(p_{2}+p_{3}+p_{4}),6(1+p_{2}+p_{3})\\}$.

###### Proof.

Let the vertices of degree $3$ be denoted $v,w$, and label the four paths from
$v$ to $w$ in $X$ by $\mathcal{P}_{1}=\\{v_{1}=v,\dots,v_{m_{1}}=w\\}$,
$\mathcal{P}_{2}=\\{w_{1}=v,\dots,w_{m_{2}}=w\\}$,
$\mathcal{P}_{3}=\\{x_{1}=v,\dots,x_{m_{3}}=w\\}$,
$\mathcal{P}_{4}=\\{y_{1}=v,\dots,y_{m_{4}}=w\\}$ in order following the path.
Consider the following sequences of swaps.

$\displaystyle\mathcal{S}_{1}=(v\ v_{2})(v_{2}\ v_{3})\dots(v_{m_{1}-1}\ w)$
$\displaystyle\mathcal{S}_{2}=(v\ w_{2})(w_{2}\ w_{3})\dots(w_{m_{2}-1}\ w)$
$\displaystyle\mathcal{S}_{3}=(v\ x_{2})(x_{2}\ x_{3})\dots(x_{m_{3}-1}\ w)$
$\displaystyle\mathcal{S}_{4}=(v\ y_{2})(y_{2}\ y_{3})\dots(y_{m_{4}-1}\ w)$

Starting $\mathfrak{n}$ at $v$, consider the following sequence $\mathcal{S}$
of $(X,\text{Star}_{n})$-friendly swaps. As in the proof of Proposition 4.13,
$\mathcal{S}$ can conveniently be represented by a (circular) word
$\sigma_{w}$ on a $4$-letter alphabet $\\{1,2,3,4\\}$, where $i\in[4]$
corresponds to applying $\mathcal{S}_{i}$. We elect to use this representation
of $\mathcal{S}$, which we denote $\mathcal{S}_{\mathcal{W}}$.

$\displaystyle\mathcal{S}_{\mathcal{W}}\mathrel{\mathop{\mathchar
58\relax}}312412132142$

It is straightforward to observe that performing $\mathcal{S}_{\mathcal{W}}$
yields a cycle in $\mathsf{FS}(X,\text{Star}_{n})$ with size
$4+4p_{2}+2(p_{3}+p_{4})$. (See Figure 17 for an illustration of this
trajectory.) The statement follows from comparison with the optimal
trajectories given by Corollary 4.5 and Proposition 4.13. ∎

Figure 17: Illustration of the trajectory $\mathcal{S}_{\mathcal{W}}$ given
above; the paths $\mathcal{P}_{1}$ to $\mathcal{P}_{4}$ are from left to
right. We color in the preimages of some key vertices in $V(\text{Star}_{n})$
(note that these are, or are adjacent to, the vertices $v$ and $w$ in the
first configuration), and in particular note that the preimage of
$\mathfrak{n}$ is colored pink. The hatch mark above $\mathcal{P}_{1}$
indicates that it is an edge, while the two hatch marks above
$\mathcal{P}_{3}$ and $\mathcal{P}_{4}$ indicate that both of these paths are
traversed exactly twice over the course of $\mathcal{S}_{\mathcal{W}}$.

In particular, this result shows that $\mathcal{G}\neq\tilde{\mathcal{G}}$, so
the inclusion of Theorem 4.14 is strict. Thus, we can enhance
$\tilde{\mathcal{G}}$ to also include all instances of $\theta_{4}$-graphs
studied by Proposition 4.17, and conclude that we must have
$\tilde{\mathcal{G}}\subset\mathcal{G}$; henceforth, $\tilde{\mathcal{G}}$
will refer to this enhanced set of simple graphs (in particular, that
described by Theorem 1.5). Also observe that this result yields that no
instances of $\tilde{\theta_{6}}$-graphs in Figure 15(c) can be in
$\mathcal{G}$. Specifically, consider any such graph $X$; let
$\phi=(p_{1}=1,\dots,p_{6})$ be the $6$-vector containing the lengths of the
paths $\mathcal{P}_{1},\dots,\mathcal{P}_{6}$ between the vertices of degree
$6$ in increasing order, and $\eta=(n_{1},\dots,n_{6})$ be such that for
$i\in[6]$, $n_{i}$ denotes the number of times $\mathcal{P}_{i}$ is traversed
by $\mathfrak{n}$. Assume $\mathfrak{n}$ traverses all six paths in a cycle in
$\mathsf{FS}(X,\text{Star}_{n})$, so $n_{i}\geq 1$ for all $i\in[6]$. Observe
that $\phi\cdot\eta$ represents the size of this cycle subgraph in
$\mathsf{FS}(X,\text{Star}_{n})$, and that $n_{i}\geq 2$ for all $2\leq i\leq
6$ since all vertices of $V(\text{Star}_{n})$ originally upon inner vertices
of such paths must return to their original positions. Such a trajectory
clearly cannot improve that which lies strictly on the paths
$\mathcal{P}_{1},\dots,\mathcal{P}_{4}$ given by Proposition 4.17, which has
$\eta^{\prime}=(4,4,2,2,0,0)$ (i.e. $\phi\cdot\eta>\phi\cdot\eta^{\prime}$).

Therefore, we have that
$\tilde{\mathcal{G}}\subset\mathcal{G}\subset\mathcal{G}^{\prime}$, and that
$\mathcal{G}\setminus\tilde{\mathcal{G}}$ consists strictly of instances of
graphs in Figure 18. We conjecture that the set of graphs
$\tilde{\mathcal{G}}$ described above is all of $\mathcal{G}$.

######  Conjecture 4.18.

$\mathcal{G}=\tilde{\mathcal{G}}$.

(a) $\theta_{4}$ graphs.

(b) $\theta_{5}$ graphs.

(c) $K_{4}^{*}$-graphs.

(d) $K_{3,3}^{*}$-graphs.

Figure 18: The remaining possibilities for graphs in the set $\mathcal{G}$
that remain unresolved by the present work.

##  5 Acknowledgements

This research was conducted at the University of Minnesota Duluth REU and was
supported, in part, by NSF-DMS grant 1949884 and NSA Grant H98230-20-1-0009.
We would like to thank Professor Joseph Gallian for organizing the Duluth REU,
and are deeply grateful to Colin Defant and Noah Kravitz (authors of the
papers that introduced friends-and-strangers graphs) for many helpful
conversations. We in particular thank Colin Defant for suggesting induction on
the number of ears of a biconnected graph as a possible approach toward
proving Theorem 3.2, introducing us to Inkscape as a tool for making figures,
and for many productive comments on a draft of the manuscript, and Noah
Kravitz for several fruitful discussions on both of the problems studied in
this work. We would also like to sincerely thank David Rolnick for helpful
conversations and for providing access to faster compute.

##  6 References

## References

  * [1] Noga Alon, Colin Defant and Noah Kravitz  “Typical and Extremal Aspects of Friends-and-Strangers Graphs”  In _arXiv preprint arXiv:2009.07840_ , 2020
  * [2] Kiril Bangachev  “On the Asymmetric Generalizations of Two Extremal Questions on Friends-and-Strangers Graphs”  In _arXiv preprint arXiv:2107.06789_ , 2021
  * [3] Colin Defant and Noah Kravitz  “Friends and Strangers Walking on Graphs”  In _Combinatorial Theory, 1. http://dx.doi.org/10.5070/C61055363_ , 2020
  * [4] F. Harary
  * [5] Ryan Jeong  “Diameters of Connected Components of Friends-and-Strangers Graphs are Not Polynomially bounded”  In _arxiv preprint arXiv: 2201.00665_ , 2021
  * [6] Gary L Miller and Vijaya Ramachandran  “Efficient parallel ear decomposition with applications”  In _Manuscript, UC Berkeley, MSRI_ 135, 1986, pp. 162
  * [7] Jens M Schmidt  “A simple test on 2-vertex-and 2-edge-connectivity”  In _Information Processing Letters_ 113.7 Elsevier, 2013, pp. 241–244
  * [8] Hassler Whitney  “Non-separable and planar graphs”  In _Hassler Whitney Collected Papers_ Springer, 1992, pp. 37–59
  * [9] Richard M Wilson  “Graph puzzles, homotopy, and the alternating group”  In _Journal of Combinatorial Theory, Series B_ 16.1 Elsevier, 1974, pp. 86–96