# Pred&Guide: Labeled Target Class Prediction for Guiding Semi-Supervised
Domain Adaptation

Megh Bhalerao, Anurag Singh, and Soma Biswas Megh Bhalerao, Anurag Singh and
Soma Biswas collaborated in this work at the Department of Electrical
Engineering at the Indian Institute of Science, Bangalore, India. E-mail
(corresponding author<EMAIL_ADDRESS>
###### Abstract

Semi-supervised domain adaptation aims to classify data belonging to a target
domain by utilizing a related label-rich source domain and very few labeled
examples of the target domain. Here, we propose a novel framework, Pred&Guide,
which leverages the inconsistency between the predicted and the actual class
labels of the few labeled target examples to effectively guide the domain
adaptation in a semi-supervised setting. Pred&Guide consists of three stages,
as follows (1) First, in order to treat all the target samples equally, we
perform unsupervised domain adaptation coupled with self-training; (2) Second
is the label prediction stage, where the current model is used to predict the
labels of the few labeled target examples, and (3) Finally, the correctness of
the label predictions are used to effectively weigh source examples class-wise
to better guide the domain adaptation process. Extensive experiments show that
the proposed Pred&Guide framework achieves state-of-the-art results for two
large-scale benchmark datasets, namely Office-Home and DomainNet.

###### Index Terms:

semi-supervised domain adaptation, source example weighting, pseudo-labeling.

##  1 Introduction

In real world, the training data distribution is often different from the
testing data distribution, necessitating that deep learning models learnt
using data from one domain are adapted to data from a different distribution.
Unsupervised Domain Adaptation (UDA) [1, 2, 3, 4] addresses this problem by
utilizing a related label rich source domain and unlabeled samples from the
target domain. Recent research has shown that only unlabeled target samples
may not be sufficient to counter the domain shift, and thus the area of Semi-
supervised Domain Adaptation (SSDA) [5, 6, 7, 8, 9, 10] is gaining traction,
where additionally, a few labeled targets are utilized to aid the adaptation
process.

The advantage of SSDA over UDA approaches lies in the manner in which the few
labeled targets are utilized in the adaptation process. A straightforward
approach is to include them along with the labeled source examples in the
Cross-Entropy loss [5, 6]. Though this approach helps in improving the final
performance, it does not fully leverage the usefulness of the labeled target
samples, since they form a very small part of the final loss as compared to
the large number of source examples.

In this work, we propose a novel framework Pred&Guide, which utilizes the
class label prediction inconsistencies on the few target labeled examples to
effectively guide the domain adaptation process. Pred&Guide has three main
stages: (1) UDA with Self-Training: Access to a few labeled target data can
create bias in the domain adaptation process from the very beginning towards
those samples as also noted in [3, 11]. Thus, we propose to utilize an UDA
framework to start the domain adaptation process in an unbiased manner, which
utilizes all the target data, but ignores the available labels of the few
target examples. Simultaneously, we also compute the pseudo-labels of all the
unlabeled data using the current model, and perform strong augmentations of
those target examples, for which we are confident about their pseudo-labels
[12, 13, 13]. (2) Labeled Target Prediction: The model trained in the first
stage is used to predict the labels of the targets (which have ground truth
labels available) to analyze the adaptation process, and further guide it. (3)
Source Example Weighting: We surmise that different source examples either
help or hinder the process of domain adaptation. Based on the inconsistency of
the predicted and true labels of the few labeled target examples, Pred&Guide
steers the adaptation process by appropriately weighing the source samples
according to their cosine similarity to the labeled target examples of the
corresponding class. Specifically, the source samples in the neighborhood of
the incorrectly classified targets are given more weight and the ones which
are far away are down-weighed, following a linear weighing scheme as described
in Section 4.3, so that the classifier can eventually classify the labeled
targets correctly.

We extensively evaluate the proposed Pred&Guide framework on two large-scale
benchmark datasets, namely Office-Home [14] and DomainNet [15]. Pred&Guide
outperforms all the state-of-the-art approaches for both the datasets. The
main contributions of our work are as follows:

  1. 1.

We propose a novel approach for semi-supervised domain adaptation, termed
Pred&Guide, by leveraging the prediction inconsistency of the labeled targets.

  2. 2.

We propose to effectively weigh the source examples based on the label
prediction inconsistency to guide the DA process.

  3. 3.

Extensive experiments on two benchmark datasets show the effectiveness of the
proposed framework.

We now describe the related work in literature followed by the proposed
approach and results of extensive evaluation.

##  2 Related Work

Here, we provide pointers to the related work in literature on domain
adaptation, data augmentation and semi-supervised learning.
Domain Adaptation: Most of the current literature in domain adaptation can be
broadly categorized into unsupervised (UDA) and semi-supervised domain
adaptation (SSDA). UDA approaches, which use only unlabeled target domain data
have been explored rigorously in [1, 2, 11, 16, 17]. Initial approaches used
statistical methods such as Maximum Mean Discrepancy [18], Correlation
Alignment (CORAL) [19] and Geodesic Flow Kernel [4] to handle the mismatch in
feature distribution. More recently, DL based UDA approaches such as [2, 1]
aim to learn a domain invariant features by a domain confusion module for
feature alignment. It has been observed that UDA performance can be boosted
significantly with just a few labeled examples from the target domain, as
noted in works such as [5, 8, 9, 20]. Most of the recent SSDA approaches use
$1-3$ labeled target examples per class. The seminal work in [5] uses a mini-
max entropy to compute domain-invariant class-representatives. In [21] authors
propose an adversarial loss instead of min-max entropy. In [9], adversarial
examples are used to bridge the source and target domain gap. [20, 22] use a
style-agnostic network and contrastive learning for reducing the source and
target domain gaps.

However, majority of approaches treat examples of labeled target no
differently than the labeled source, thus not fully leveraging information
contained in them. Some works have attempted to use labeled target in triplet
loss for bringing source closed to target [23] and [24] propose an effective
pseudo labeling strategy using labeled target. Presence of few labeled target
examples in SSDA setting results in intra-domain discrepancy, which is
recently noted and addressed in [8]. We also address this critical issue
Pred&Guide.

Data Augmentation: Data augmentation [25, 26, 27] is widely used as a
regularizer to prevent overfitting. Different data augmentation policies have
been proposed in works such as [26, 25, 12]. From a pool of augmentations,
[25] randomly selects augmentation to be used. [26] selects an augmentation
during model training using reinforcement learning. Other approaches such as
CT-Augment have been proposed in [12, 28] which uses a similar strategy as
AutoAugment [26], but uses a fixed algorithm for assigning augmentation
magnitudes. In our work, we use an augmentation based consistency-
regularization, based on RandAugment [25] to assign pseudo-labels to the
unlabeled targets to boost the performance.

Semi-Supervised Learning (SSL): SSL approaches utilize a small amount of
labeled data and a huge amount of unlabeled data for the required task [29,
30, 31, 12, 32, 33, 13, 28], which reduces the labeling cost. Several SSL
algorithms use consistency constraint, i.e. they aim to minimize the entropy
between prediction of different versions of a data-point [12, 13, 13, 33].

Mean-Techer [33] trains a student and a teacher model and forces their
predictions to match. The student model is updated at every iteration, while
the teacher model is updated with a suitable momentum. Virtual Adversarial
Training [32] uses adversarial perturbations to train the SSL model. Pseudo-
labeling [31] predicts labels of the unlabeled data and uses these as true
labels for supervised learning. Recent approaches such as Mixmatch [13],
ReMixmatch [28] and Fixmatch [12] provide an elegant framework for SSL,
leveraging consistency regularization and MixUp [34] to obtain state-of-the-
art results for SSL. The proposed SSDA framework Pred&Guide is inspired by
these seminal SSL approaches, but utilizes the few labeled target domain
examples in a novel manner to guide the adaptation process.

##  3 Problem Definition

We first discuss the problem statement and the notations used. In this work,
we address the SSDA task, where there are very few labeled target examples
available (i.e. one and three shot settings). The training data consists of
(1) labeled source:
$\mathcal{D}_{ls}=\\{x^{s}_{i},y^{s}_{i}\\}_{i=1}^{i=n_{s}}$, where $n_{s}$ is
the number of labeled source examples, (2) unlabeled target:
$\mathcal{D}_{ut}=\\{x^{ut}_{i}\\}_{i=1}^{i=n_{ut}}$, where $n_{ut}$ is the
number of unlabeled target examples and (3) few labeled target:
$\mathcal{D}_{lt}=\\{x^{t}_{i},y^{t}_{i}\\}_{i=1}^{i=n_{t}}$, where $n_{t}$ is
the number of labeled target examples. Here $x_{i}$ denotes the $i^{th}$ data-
point and $y_{i}$ denotes the corresponding class label, which belongs to one
of the $K$ classes (same for both source and target domains). We test the
model’s performance on $\mathcal{D}_{ut}$. For all the experiments, we have a
feature extractor network $F$ (with parameters $\Theta_{F}$), sequentially
followed by a classifier $C$ (with parameters $\Theta_{C}$).

##  4 Proposed Pred&Guide Framework

Figure 1: Figure showing the complete Pred&Guide framework and its different
modules. The different modules get activated at different iteration steps,
when the corresponding losses are computed as seen from the indicator
functions in equation (15). The distance to source samples are calculated
efficiently using a feature bank (not shown in figure) in the feature space.

The proposed SSDA framework has three sequential modules, namely (1)
unsupervised domain adaptation (UDA) with self-training (2) labeled target
prediction, where we predict the labels of the target domain data using the
current model, for which we have the ground truth labels and finally (3)
source sample weighting, where the source examples are effectively weighted
using the prediction inconsistencies of the labeled target examples in the
previous step. Figure 1 illustrates the proposed Pred&Guide framework and its
different modules. Each of the modules with its motivation are explained below
in detail.

###  4.1 UDA with Self-Training

In SSDA, though few labeled target samples are available in the training data,
using them from the beginning may bias the domain adaptation process towards
these examples, as noted in recent works [3, 11]. This has motivated us to use
an UDA approach to initiate the adaptation process in an unbiased manner,
which treats all the target samples equally. For this, any UDA approach can be
utilized. Most UDA approaches usually learn a domain invariant feature
extractor and a classifier [2, 1, 3]. Let us denote this model as
$\mathbf{U_{M}}$.

Inspired by the recent works in consistency regularization and self-
training/pseudo-labeling [12, 28, 13], while training $\mathbf{U_{M}}$, we
incorporate an augmentation-consistency based self-training to further aid the
unsupervised learning, which is briefly described below for completion.

During every training iteration, for all the unlabeled target data
$x^{ut}\>\in\>\mathcal{D}_{ut}$ we compute

$\vspace{-8px}x^{ut_{s}}=\mathcal{S}(x^{ut});\qquad
x^{ut_{w}}=\mathcal{W}(x^{ut})$ (1)

where $x^{ut_{s}}$ and $x^{ut_{w}}$ are the strong and weak augmentations of
the given data $x^{ut}$. The strong augmentation function $\mathcal{S}$ is
obtained using RandAugment [25], while the weak augmentation function
$\mathcal{W}$ is simply flipping, random cropping and padding. In every
forward pass of the current model $\mathbf{U_{M}}$, for all the unlabeled
target samples, we compute the predicted class probability distribution of the
weak and strong augmentations, denoted by $p^{ut_{w}}$ and $p^{ut_{s}}$
respectively. Using $p^{ut_{w}}$, we compute the one-hot pseudo-label

$y^{ut_{w}}=\mathbf{O}(\arg\max(p^{ut_{w}}))$ (2)

where the function $\mathbf{O}$ produces a valid one-hot vector corresponding
to the predicted label. Our per example pseudo-labeled target loss is:

$\begin{split}\mathcal{L}_{p}=\mathbf{1}(\max(p^{ut_{w}})>\tau)\,\mathbf{H}(y^{ut_{w}},p^{ut_{s}})\end{split}$
(3)

Here, we only consider the loss for the unlabeled targets whose prediction
confidence is greater than a threshold $\tau$. $\mathbf{H}(.,.)$ is the
standard cross-entropy function, where the first parameter is the ground truth
label and the second is the predicted class probability distribution over the
labels. The proposed method calculates the pseudo-labels on-the-fly for every
example as opposed to static pseudo-labels being updated at different time-
steps [31].

For the source, we consider standard cross entropy loss $\mathbf{H(.,.)}$,
until $t<T_{1}$. Here, $T_{1}$ is the number of iterations for which UDA with
self-training runs till the validation accuracy saturates. After $T_{1}$, we
use the weighted cross entropy for the source examples, as explained later in
Section 4.3. The loss for source example $(x^{s},y^{s})$ is given as:

$\mathcal{L}_{s}=\mathbf{H}(y^{s},p^{s})$ (4)

where $y^{s}$ is the label of the source example and $p^{s}$ is the predicted
class probability distribution of $x^{s}$.

For the unlabeled target example $x^{ut_{w}}$ we use the mini-max entropy
approach [5], with the loss function denoted by $\mathcal{L}_{ULT}$, where
$\mathcal{L}_{ULT}$ is given by:

$\vspace{-3px}\mathcal{L}_{ULT}=-\sum_{k=1}^{K}(p^{ut_{w}}_{k})\log(p^{ut_{w}}_{k})$
(5)

Thus, in this step, the domain adaptation uses all the target samples, but
without the labels of the few target examples which are available. In the next
stage, we check how good the current model is in predicting the labels of the
labeled targets and its augmentations, which is then used to guide the
adaptation process.

###  4.2 Labeled Target Prediction

In this stage, we leverage the additional label information provided for few
target examples to analyze how well the current model has adapted to the
target domain. Since the number of labeled targets is very less, we leverage
their strong and weak augmentations denoted by $x^{t_{s}}$ and $x^{t_{w}}$ for
this analysis, calculated following equation (1). Let us denote this new
augmented data as $\mathcal{D}_{lt_{a}}$.

First, the current model is used to predict the class labels of the examples
in $\mathcal{D}_{lt_{a}}$ for which we know the ground truth class labels.
Computing the label prediction accuracy for each class in this manner gives a
weak indication of the class-wise adaptation of the current model. For
example, if most of the (labeled) target samples of a class have been
classified correctly, it indicates that domain adaptation is successful for
that class, otherwise, it is not satisfactory. Obviously, as the number of
labeled target samples increases, this becomes a strong indicator of the
class-wise domain adaptation accuracy, hence we use the labeled data along
with its augmentations. We define the class-wise accuracy vector as follows:

$\mathbf{A}=[a_{1},a_{2},\dots,a_{K}],\;\;\mathbf{A}\in\mathbb{R}^{K\times 1}$
(6)

and $a_{i}$’s are the individual class accuracies as calculated on
$\mathcal{D}_{lt_{a}}$ using the current model $\mathbf{U_{M}}$, and $K$ is
the total number of classes. Pred&Guide aims to utilize the class-wise
information about adaptability, rather than just the domain-wise adaptability,
since different classes vary in their ability to adapt. This follows from the
fact that it may easier for some classes of a domain to adapt (if those
classes look similar across domains), while it may be difficult for others.

The goal is to aid the classes which have not yet adapted satisfactorily,
based on the accuracy computed. For the classes which have lesser accuracy,
more (less) weightage is given to the neighboring (far) source samples of the
corresponding labeled target examples. This helps the corresponding class
prototypes adapt to the target domain samples, as will be explained in
detailed next.

###  4.3 Source Example Weighing

Once UDA is performed, the label prediction in the previous module is used to
weigh source examples accordingly at regular intervals. If a target example is
wrongly classified, we weigh its neighbouring source samples of the same class
relatively more (based on a linear weighing scheme as explained next), which
will guide the model towards classifying this target sample correctly. To
further aid the adaptation, we also relatively down-weigh the source samples
of the same class far away from the wrongly classified labeled targets, since
these source examples hinder the adaptation process. To perform this step
efficiently with reduced computational complexity, we use a feature bank to
store the representations of the source examples as described next.

Feature Bank Based Source Identification: To compute the distances of source
examples of the same class as the labeled target examples, we need to compute
the distance between the labeled target and the source examples of the same
class. To compute this distance efficiently, we maintain a feature bank
$\mathbf{S}$ as defined below:

$\vspace{-7px}\mathbf{S}=[s_{1},s_{2},\dots,s_{n_{s}}],\;\;\mathbf{S}\in\mathbb{R}^{d_{f}\times
n_{s}}$ (7)

where $s_{i}$ is the representation of the $i^{th}$ source example. $n_{s}$
denotes the number of examples in the source domain (as defined in Section 3)
and $d_{f}$ is the dimension of the representation space. $\mathbf{S}$ is
updated on the fly batch-wise with momentum $m_{s}$ as:

$\vspace{-5px}\mathbf{S}_{t+1}\leftarrow
m_{s}\mathbf{S}_{t}+(1-m_{s})\,\mathbf{f}_{bs}$ (8)

where $\mathbf{f}_{bs}$ are the representations of the current batch of source
examples. $\mathbf{S}_{t}$ denotes the feature bank at a given iteration-step
$t$. For simplicity we assume that in (8), only the source examples
corresponding to the ones in the mini-batch are updated. Now, we describe how
our linear weighing scheme works.

Let $\mathcal{D}^{k}_{ls}\subset\mathcal{D}_{ls}$ denote the set of source
examples belonging to class $k\>\in\>\\{1,2,\dots,K\\}$. Similarly, let
$\mathcal{D}^{k}_{lt}\subset\mathcal{D}_{lt}$ be the set of labeled targets
belonging to class $k$. Now for every element $x^{t,k}$ in
$\mathcal{D}_{lt}^{k}$ (sample index $i$ is omitted for simplicity), we
compute an ordered set
$\tilde{\mathcal{D}}_{ls}^{k}=\\{x^{s,k}_{j}\in\mathcal{D}_{ls}^{k}\text{ s.t.
}d(s^{s,k}_{j+1},F(x^{t,k}))>d(s^{s,k}_{j},F(x^{t,k}))\\}$ where $s^{s,k}_{j}$
is the corresponding feature from the feature bank $\mathbf{S}_{t}$ for sample
$x^{s,k}_{j}$ and $d(.,.)$ is cosine similarity between the feature
representations of the datapoints. Let $min_{sim}$ and $max_{sim}$ denote the
minimum and maximum cosine similarities from the set of source examples
($\tilde{\mathcal{D}}^{k}_{ls}$) of the given class $k$. We compute the class
wise max and min weights as:

$\begin{split}max_{w}=1+\phi/\exp(a_{k})\\\
min_{w}=1-\phi/\exp(a_{k})\end{split}$ (9)

where $a_{k}$ is the accuracy computed using the predictions of the labeled
targets of class $k$, as computed in the previous step of Pred&Guide and
$\phi$ is a hyper-parameter. Thus, the $i^{th}$ source sample belonging to
class $k$ is weighted with $w_{i}$ as

$w_{i}=m\times(d(s^{s,k}_{i},F(x^{t,k}))-min_{sim})+min_{w}$ (10)

where $m$ is the slope of the linear weighting scheme

$m=\frac{max_{w}-min_{w}}{max_{sim}-min_{sim}}$ (11)

In other words, we up-weigh the near source samples and down-weigh the far
source samples, with the weight varying according to a linear function
dependent on the similarity of the source sample with respect to the labeled
target sample as in equation (10).  If the accuracy for class $k$ is less
(i.e. $a_{k}$ is small), the prototype for that particular class probably has
not adapted properly. For these classes, the weights of source examples
$w_{i}$ in the neighbourhood of the labeled targets of that class is
increased, and those which are far away are decreased, which will help the
domain adaptation process. Thus, the weighted loss for a source example
$(x^{s},y^{s})$ with predicted class probability distribution $p^{s}$ is
expressed as follows:

$\mathcal{L}^{w}_{s}=w^{s}\times\mathbf{H}(y^{s},p^{s})$ (12)

where $w^{s}$ is weight of the example whose loss is being calculated. Figure
2 illustrates the near and far examples at different iterations of Pred&Guide
using t-SNE plots [35].

(a)

(b)

(c)

Figure 2: Figure showing the t-SNE [35] plots at different stages of training
for one particular class in the P to C domain adaptation setting for
DomainNet. The labeled source and labeled target (above) and the unlabeled
target (below) are shown in separate plots for clarity (but share the same set
of axes). The target classification accuracy for this class at these three
stages (from left to right) are $47.9\%$, $76.7\%$ and $81.5\%$ for the
$2000^{th}$, $7500^{th}$, and $15000^{th}$ iterations respectively, as can be
clearly seen from the increasing number of correctly classified target
examples. Color coding - $\times$: unweighted labeled source,
$\blacktriangledown$ and $\blacktriangle$ : 5 near and 5 far weighted samples
respectively; Orange Square: labeled targets; $\times$: wrongly classified
unlabeled targets; $\times$: correctly classified unlabeled targets. Figure 3:
Figure showing 5 nearest and farthest source samples corresponding to labeled
targets of four different classes. Green (red) boundaries of the labeled
targets indicate whether they are correctly (incorrectly) classified after UDA
with self-training (first column) and after Pred&Guide training is complete
with effective source weighting (last column). We observe that for the first
two rows, Pred&Guide is able to effectively correct the labels, while in the
third row, though the near and far source examples are quite intuitive, the
final prediction is still incorrect. The last row shows one example which is
always correctly classified. This example is for the Real to Sketch setting of
DomainNet with ResNet34 backbone.

Once we have used the labeled target accuracy to calculate and assign weights
for the source examples $T_{1}$ number of iterations as described above, we
bring in the labeled target examples $(x^{t},y^{t})$, with predicted class
probability $p^{t}$, into the training. For these samples, we use the standard
cross-entropy loss starting at iteration $T_{2}$ (number of iterations after
which source example weighing validation accuracy saturates) as follows:

$\mathcal{L}_{lt}=\mathbf{H}(y^{t},p^{t})$ (13)

Input: Feature extractor $F$, classifier $C$, total number of iterations $T$
Data: Labeled source $\mathcal{D}_{ls}$, unlabeled target $\mathcal{D}_{ut}$,
labeled target $\mathcal{D}_{lt}$, augmented labeled target
$\mathcal{D}_{lt_{a}}$.

while  _$t <T$_ do

Calculate pseudo-labeled target loss $\mathcal{L}_{p}$ according to (3).
Calculate unlabeled target loss $\mathcal{L}_{ULT}$ according to (5).
if  _$t >T_{1}$_ then

if  _$t\bmod T_{n}==0$_ then

Calculate accuracy on $\mathcal{D}_{lt_{a}}$ to obtain $\mathbf{A}$ as in
equation (6).
Calculate and update source example weights using equation (10).

end if

Calculate and backpropagate $\mathcal{L}^{w}_{s}$ according to equation (12).

end if

else if  _$t <T_{1}$_ then

Calculate cross-entropy loss for the labeled source examples $\mathcal{L}_{s}$
according to (4).

end if

if  _$t >T_{2}$_ then

Calculate cross-entropy loss for the labeled target examples
$\mathcal{L}_{lt}$ according to (13).

end if

$t\leftarrow t+1$

end while

Algorithm 1 Proposed Pred&Guide algorithm

###  4.4 Complete Pred&Guide Framework

The complete Pred&Guide Framework is summarized in this section. As stated
earlier, we optimize the parameters of the feature extractor $\Theta_{F}$ and
classifier $\Theta_{C}$ using the mini-max approach [5]:

$\begin{split}\hat{\Theta}_{F}=\underset{\Theta_{F}}{\operatorname*{argmin}}\;\mathbf{\mathcal{L}_{1}}+\lambda\mathcal{L}_{ULT}\\\
\hat{\Theta}_{C}=\underset{\Theta_{C}}{\operatorname*{argmin}}\;\mathbf{\mathcal{L}_{1}}-\lambda\mathcal{L}_{ULT}\end{split}$
(14)

Here $\mathbf{\mathcal{L}_{1}}$ is the sum of all losses except
$\mathcal{L}_{ULT}$ loss given by

$\begin{split}\mathbf{\mathcal{L}_{1}}=\mathcal{L}_{p}+\mathbf{1}(t<T_{1})\mathcal{L}_{s}+\mathbf{1}(t>T_{1})\mathcal{L}^{w}_{s}+\mathbf{1}(t>T_{2})\mathcal{L}_{lt}\end{split}$
(15)

Here, $T_{1}$ is the iteration after which we start weighing the source
examples and $T_{2}$ is the iteration at which the labels of the few target
examples are exposed to the training algorithm. More details about calculating
$T_{1}$ and $T_{2}$ are given in Section 5. The complete Pred&Guide algorithm
is given in Algorithm 1.

##  5 Experimental Evaluation

Here, we provide details of the extensive experiments conducted to evaluate
the efficacy of Pred&Guide for semi-supervised domain adaptation. First, we
discuss the benchmark datasets used, the implementation details before
reporting the results. We also conduct detailed analysis of Pred&Guide and
perform ablation studies to evaluate the usefulness of the individual modules.

Datasets Used and Evaluation Protocol:  To evaluate Pred&Guide, we use two
large-scale benchmark domain adaptation datasets, DomainNet [15] and Office-
Home [14]. DomainNet consists of $6$ domains with $345$ classes, comprising of
about $0.6M$ images. Since the entire DomainNet dataset is noisy, we select
$4$ domains (Real, Painting, Clipart, Sketch) and $126$ classes with $7$
standard domain adaptation scenarios, which are generally used to benchmark DA
methods [5, 9, 8, 6]. In addition to DomainNet, we also evaluate Pred&Guide on
the Office-Home dataset, which is a smaller, but challenging dataset. It
consists of $65$ classes and $4$ domains (Real, Clipart, Product, Art). We
evaluate Pred&Guide on all the $12$ possible adaptation scenarios for Office-
Home.

Implementation Details: The code is implemented using PyTorch [36] on a single
Nvidia RTX-2080 GPU. The underlying domain adaptation technique that we used
in Pred&Guide is the very successful mini-max entropy approach [5]. We use
Resnet34 [37] and AlexNet [38] for the feature extractor network $F$ to
compare with state-of-the-art approaches. For the classifier $C$, we use a
$4096\times K$ fully-connected layer for AlexNet and a $512\times K$ fully-
connected layer for ResNet34. We use SGD optimizer, with the starting learning
rate of $0.01$, momentum of $0.9$, weight decay of $0.0005$ and $\lambda=0.1$
for the weight of $\mathcal{L}_{ULT}$. We use batch size of $24$ and $32$ for
Resnet34 and Alexnet backbones respectively on labeled samples, and twice the
batch size for unlabeled data. We set $\phi=0.5$ in Equation (9) for DomainNet
and $\phi=0.1$ for Office-Home, and $m_{s}=0.1$ in Equation 8 for all our
experiments. We run the first module, i.e. UDA with self-training for $T_{1}$
iterations. $T_{1}$ is the iteration-step when UDA with self-training has
converged. Then, the weights of the source examples are computed every $T_{n}$
iterations. $T_{n}=1000$ for DomainNet and $T_{n}=140$ for Office-Home.
Finally, we bring in the labeled target examples in the CE loss at the $T_{2}$
iteration. $T_{2}$ is started when the source example weighing performance has
converged. To calculate $T_{1}$ and $T_{2}$, we consider the validation
accuracy to be converged when it has not increased for $500$ iterations.

Evaluation for SSDA:  The results of Pred&Guide for Office-Home dataset with
AlexNet backbone for both $1$-shot and $3$-shot scenarios are reported in
Table I. Comparison with the recent approaches show that Pred&Guide achieves
the state-of-art results on an average for both the settings and also
outperforms the others for most of the individual domain pair settings. The
results on DomainNet dataset for both $1$ and $3$ shots (i.e. one and three
target samples of each class in the target domain are labeled) using AlexNet
and ResNet34 backbones are reported in Table II. The results of all the other
approaches has been directly taken from [5]. We observe that the proposed
approach significantly outperforms all the recent SSDA approaches, thus
justifying its usefulness.

Method | R to C | R to P | R to A | P to R | P to C | P to A | A to P | A to C | A to R | C to R | C to A | C to P | Mean
---|---|---|---|---|---|---|---|---|---|---|---|---|---
One-Shot
S+T [39] | 37.5 | 63.1 | 44.8 | 54.3 | 31.7 | 31.5 | 48.8 | 31.1 | 53.3 | 48.5 | 33.9 | 50.8 | 44.1
DANN [2] | 42.5 | 64.2 | 45.1 | 56.4 | 36.6 | 32.7 | 43.5 | 34.4 | 51.9 | 51.0 | 33.8 | 49.4 | 45.1
ADR [6] | 37.8 | 63.5 | 45.4 | 53.5 | 32.5 | 32.2 | 49.5 | 31.8 | 53.4 | 49.7 | 34.2 | 50.4 | 44.5
CDAN [40] | 36.1 | 62.3 | 42.2 | 52.7 | 28.0 | 27.8 | 48.7 | 28.0 | 51.3 | 41.0 | 26.8 | 49.9 | 41.2
ENT [30] | 26.8 | 65.8 | 45.8 | 56.3 | 23.5 | 21.9 | 47.4 | 22.1 | 53.4 | 30.8 | 18.1 | 53.6 | 38.8
BiAT [9] | - | - | - | - | - | - | - | - | - | - | - | - | 49.6
MME [5] | 42.0 | 69.6 | 48.3 | 58.7 | 37.8 | 34.9 | 52.5 | 36.4 | 57.0 | 54.1 | 39.5 | 59.1 | 49.2
Pred&Guide | 44.4 | 73.2 | 50.0 | 59.6 | 38.2 | 37.0 | 54.4 | 34.8 | 55.6 | 52.8 | 38.0 | 59.2 | 49.8
Three-Shot
S+T [39] | 44.6 | 66.7 | 47.7 | 57.8 | 44.4 | 36.1 | 57.6 | 38.8 | 57.0 | 54.3 | 37.5 | 57.9 | 50.0
DANN [2] | 47.2 | 66.7 | 46.6 | 58.1 | 44.4 | 36.1 | 57.2 | 39.8 | 56.6 | 54.3 | 38.6 | 57.9 | 50.3
ADR [6] | 45.0 | 69.3 | 46.9 | 57.3 | 38.9 | 36.3 | 57.5 | 40.0 | 57.8 | 53.4 | 37.3 | 57.7 | 49.5
CDAN [40] | 41.8 | 69.9 | 43.2 | 53.6 | 35.8 | 32.0 | 56.3 | 34.5 | 53.5 | 49.3 | 27.9 | 56.2 | 46.2
ENT [30] | 44.9 | 70.4 | 47.1 | 60.3 | 41.2 | 34.6 | 60.7 | 37.8 | 60.5 | 58.0 | 31.8 | 63.4 | 50.9
BiAT [9] | - | - | - | - | - | - | - | - | - | - | - | - | 56.4
MME [5] | 51.2 | 73.0 | 50.3 | 61.6 | 47.2 | 40.7 | 63.9 | 43.8 | 61.4 | 59.9 | 44.7 | 64.7 | 55.2
APE [8] | 51.9 | 74.6 | 51.2 | 61.6 | 47.9 | 42.1 | 65.5 | 44.5 | 60.9 | 58.1 | 44.3 | 64.8 | 55.6
Pred&Guide | 53.4 | 75.0 | 51.9 | 64.0 | 48.7 | 43.6 | 65.7 | 45.7 | 60.6 | 60.0 | 43.0 | 67.5 | 56.6

TABLE I: Semi-supervised DA results (%) on Office-Home data for both $1$ and
$3$-shot protocols using Alexnet backbone for four domains with $12$ total
domain combinations.

Net | Method | R to C | R to P | P to C | C to S | S to P | R to S | P to R | Mean
---|---|---|---|---|---|---|---|---|---
1 shot | 3 shot | 1 shot | 3 shot | 1 shot | 3 shot | 1 shot | 3 shot | 1 shot | 3 shot | 1 shot | 3 shot | 1 shot | 3 shot | 1 shot | 3 shot
Alexnet |  S+T [39] | 43.3 | 47.1 | 42.4 | 45.0 | 40.1 | 44.9 | 33.6 | 36.4 | 35.7 | 38.4 | 29.1 | 33.3 | 55.8 | 58.7 | 40.0 | 43.4
DANN [2] | 43.3 | 46.1 | 41.6 | 43.8 | 39.1 | 41.0 | 35.9 | 36.5 | 36.9 | 38.9 | 32.5 | 33.4 | 53.6 | 57.3 | 40.4 | 42.4
ADR [6] | 43.1 | 46.2 | 41.4 | 44.4 | 39.3 | 43.6 | 32.8 | 36.4 | 33.1 | 38.9 | 29.1 | 32.4 | 55.9 | 57.3 | 39.2 | 42.7
CDAN [40] | 46.3 | 46.8 | 45.7 | 45.0 | 38.3 | 42.3 | 27.5 | 29.5 | 30.2 | 33.7 | 28.8 | 31.3 | 56.7 | 58.7 | 39.1 | 41.0
ENT [30] | 37.0 | 45.5 | 35.6 | 42.6 | 26.8 | 40.4 | 18.9 | 31.1 | 15.1 | 29.6 | 18.0 | 29.6 | 52.2 | 60.0 | 29.1 | 39.8
MME [5] | 48.9 | 55.6 | 48.0 | 49.0 | 46.7 | 51.7 | 36.3 | 39.4 | 39.4 | 43.0 | 33.3 | 37.9 | 56.8 | 60.7 | 44.2 | 48.2
BiAT [9] | 54.2 | 58.6 | 49.2 | 50.6 | 44.0 | 52.0 | 37.7 | 41.9 | 39.6 | 42.1 | 37.2 | 42.0 | 56.9 | 58.8 | 45.5 | 49.4
APE [8] | 47.7 | 54.6 | 49.0 | 50.5 | 46.9 | 52.1 | 38.5 | 42.6 | 38.5 | 42.2 | 33.8 | 38.7 | 57.5 | 61.4 | 44.6 | 48.9
| Pred&Guide | 54.5 | 57.3 | 54.4 | 56.7 | 52.8 | 56.9 | 41.6 | 48.3 | 36.9 | 44.9 | 38.4 | 46.9 | 61.9 | 65.4 | 48.6 | 53.8
Resnet34 |  S+T [39] | 55.6 | 60.0 | 60.6 | 62.2 | 56.8 | 59.4 | 50.8 | 55.0 | 56.0 | 59.5 | 46.3 | 50.1 | 71.8 | 73.9 | 56.9 | 60.0
DANN [2] | 58.2 | 59.8 | 61.4 | 62.8 | 56.3 | 59.6 | 52.8 | 55.4 | 57.4 | 59.9 | 52.2 | 54.9 | 70.3 | 72.2 | 58.4 | 60.7
ADR [6] | 57.1 | 60.7 | 61.3 | 61.9 | 57.0 | 60.7 | 51.0 | 54.4 | 56.0 | 59.9 | 49.0 | 51.1 | 72.0 | 74.2 | 57.6 | 60.4
CDAN [40] | 65.0 | 69.0 | 64.9 | 67.3 | 63.7 | 68.4 | 53.1 | 57.8 | 63.4 | 65.3 | 54.5 | 59.0 | 73.2 | 78.5 | 62.5 | 66.5
ENT [30] | 65.2 | 71.0 | 65.9 | 69.2 | 65.4 | 71.1 | 54.6 | 60.0 | 59.7 | 62.1 | 52.1 | 61.1 | 75.0 | 78.6 | 62.6 | 67.6
MME [5] | 70.0 | 72.2 | 67.7 | 69.7 | 69.0 | 71.7 | 56.3 | 61.8 | 64.8 | 66.8 | 61.0 | 61.9 | 76.1 | 78.5 | 66.4 | 68.9
BiAT [9] | 73.0 | 74.9 | 68.0 | 68.8 | 71.6 | 74.6 | 57.9 | 61.5 | 63.9 | 67.5 | 58.5 | 62.1 | 77.0 | 78.6 | 67.1 | 69.7
APE [8] | 70.4 | 76.6 | 70.8 | 72.1 | 72.9 | 76.7 | 56.7 | 63.1 | 64.5 | 66.1 | 63.0 | 67.8 | 76.6 | 79.4 | 67.6 | 71.7
| Pred&Guide | 74.7 | 79.2 | 75.9 | 74.8 | 74.8 | 75.9 | 66.0 | 69.5 | 71.4 | 71.2 | 68.7 | 72.5 | 78.5 | 80.2 | 72.9 | 74.8

TABLE II: Semi-supervised DA performance ($\%$) on DomainNet dataset for both
$1$ and $3$-shot protocols on 4 domains, R: Real, C: Clipart, P: Clipart, S:
Sketch.

##  6 Additional Analysis

Here, we perform extensive analysis and ablation studies of the proposed
Pred&Guide framework.

Importance of Source Example Weighing: To analyze the importance of weighting
the source examples in the proposed Pred&Guide framework, we run the algorithm
with and without the source example weighing on the DomainNet dataset. The
results in Table IV show that when the algorithm is trained using the standard
cross entropy loss $\mathcal{L}_{s}$ without the weighting (i.e. No weights),
the performance is considerably lower as compared to when the source samples
are properly weighted. Figure 3 gives a visual illustration of the near and
far source examples of the labeled targets for one class of DomainNet. We
would like to highlight that the proposed source example weighting (SEW) can
be seamlessly integrated with other SSDA methods to improve their performance.
We experiment with a recent SSDA approach CDAC [41], and observe that SEW
improves the mean performance ($\%$) of CDAC for both 1-shot and 3-shot
settings from 73.6 to 74.4 and from 76.0 to 76.2 respectively.

Weighting Scheme:  Now, we analyze the effectiveness of the proposed weighting
strategy based on class-wise adaptability. Specifically, we compare with fixed
up-weighing and down-weighting. For this experiment, we used fixed weights of
$1.5$ and $0.5$ for the near and far samples respectively. We observe from
Table III that fixed weighting can give unpredictable results, i.e. for some
cases (1-shot, R to C), it improves the results, and for other cases (3-shot R
to S and R to C), the performance degrades. We observe that for almost all
scenarios, the proposed source example weighting helps to boost the
performance. We also compare with another popular weighting scheme, namely
Focal Loss [42], which emphasizes on correct classification of hard training
examples by weighing them more. We observe that for all scenarios, the
proposed technique outperforms focal loss. As an example, for 3-shot setting,
the proposed technique gives 72.5$\%$ and 79.2$\%$ for R to S and R to C as
compared to 69.6$\%$ and 74.8$\%$ obtained using Focal loss.

Near & Far Weighing: Next, we analyze the effect of weighing only the near or
far samples, and the results are reported in Table IV. Near source samples are
defined as the samples having weight $w_{i}>1$ and far samples are defined as
the ones having $w_{i}<1$. The results obtained using only UDA with self-
training is shown in the first row. If we introduce the labeled target samples
right after this stage, as expected, the performance improves as shown in the
second row. The third and fourth rows show the performance when only near and
far away source examples are weighted. We observe that both these steps help
to boost the performance. The final row is the complete Pred&Guide, which
weighs both the near and far away source examples and outperforms all the
other variants.

Sensitivity Analysis of Hyperparameters: There are two primary hyperparamters
in Pred&Guide, $\phi$ which control the amount of weighing for the source
examples and $T_{n}$. We plot the SSDA results (%) for a wide range of $\phi$
values for the 3-shot R to S setting of DomainNet in Fig. 4 (using Resnet34).
We observe that the performance is quite stable for a wide range of parameter
values, and even the lowest accuracy is better than the second best approach.
We also vary the values of $T_{n}$ between 1000 to 2000 for DomainNet and
observe that the performance is stable for all the $T_{n}$ values. Note that
we have used the same $\phi$ and $T_{n}$ values for all the domain settings of
a dataset.

Weighing Strategy | R to S | R to C
---|---|---
1 shot | 3 shot | 1 shot | 3 shot
No Weights | 68.8 | 70.8 | 71.3 | 76.3
Fixed Weights | 68.8 | 68.6 | 74.3 | 73.2
Class-wise Adaptability Based Weights | 68.7 | 72.5 | 74.7 | 79.2

TABLE III: Performance of Pred&Guide with no weighting, fixed weighting and
classwise adaptability based weighing of source examples.  Figure 4: Plot of
hyperparameter $\phi$ vs. accuracy for 3 shot R to S setting of the DomainNet
dataset

Components | R to S | R to C
---|---|---
UDA | N | F | LT | 1 shot | 3 shot | 1 shot | 3 shot
✓ |  |  |  | 63.5 | 63.5 | 69.2 | 69.2
✓ |  |  | ✓ | 68.8 | 70.8 | 71.3 | 76.3
✓ | ✓ |  | ✓ | 69.0 | 68.9 | 71.5 | 77.4
✓ |  | ✓ | ✓ | 68.1 | 71.9 | 72.4 | 77.3
✓ | ✓ | ✓ | ✓ | 68.7 | 72.5 | 74.7 | 79.2

TABLE IV: Ablation study for Pred&Guide depicting performance of individual
components using Resnet34: (1) UDA: Unsupervised domain adaptation with self-
training, (2) N and F: class-wise source weighing of Near and Far examples
respectively, (3) LT: labeled target examples are included in training
starting at iteration $T_{2}$.

##  7 Conclusion

In this work, we addressed the importance of using labeled target samples
effectively for the domain adaptation task in the semi-supervised setting. The
proposed Pred&Guide framework initially performs the domain adaptation in an
unsupervised manner to avoid any bias that may be introduced due to the few
labeled target examples. After this stage, we introduce two effective modules,
labeled target prediction and source example weighting to effectively weigh
the source examples to better guide the adaptation. With Pred&Guide, we set a
new state-of-the-art for semi-supervised domain adaptation as illustrated by
extensive experiments on two large-scale benchmark datasets.

## References

  * [1] Y. Ganin, E. Ustinova, H. Ajakan, P. Germain, H. Larochelle, F. Laviolette, M. Marchand, and V. Lempitsky, “Domain-adversarial training of neural networks,” in _JMLR_ , 2016.
  * [2] Y. Ganin and V. Lempitsky, “Unsupervised domain adaptation by backpropagation,” in _ICML_ , 2015.
  * [3] W. Li and S. Chen, “Unsupervised domain adaptation with progressive adaptation of subspaces,” in _arXiv_ , 2020.
  * [4] B. Gong, Y. Shi, F. Sha, and K. Grauman, “Geodesic flow kernel for unsupervised domain adaptation,” in _CVPR_ , 2012.
  * [5] K. Saito, D. Kim, S. Sclaroff, T. Darrell, and K. Saenko, “Semi-supervised domain adaptation via minimax entropy,” in _ICCV_ , 2019.
  * [6] K. Saito, Y. Ushiku, T. Harada, and K. Saenko, “Adversarial dropout regularization,” in _ICLR_ , 2018.
  * [7] J. Donahue, J. Hoffman, E. Rodner, K. Saenko, and T. Darrell, “Semi-supervised domain adaptation with instance constraints,” in _CVPR_ , 2013.
  * [8] T. Kim and C. Kim, “Attract, perturb, and explore: Learning a feature alignment network for semi-supervised domain adaptation,” in _ECCV_ , 2020\.
  * [9] P. Jiang, A. Wu, Y. Han, Y. Shao, M. Qi, and B. Li, “Bidirectional adversarial training for semi-supervised domain adaptation,” in _IJCAI_ , 2020.
  * [10] T. Yao, Yingwei Pan, C. Ngo, Houqiang Li, and Tao Mei, “Semi-supervised domain adaptation with subspace learning for visual recognition,” in _CVPR_ , 2015.
  * [11] M. Long, H. Zhu, J. Wang, and M. I. Jordan, “Unsupervised domain adaptation with residual transfer networks,” in _NIPS_ , 2016.
  * [12] K. Sohn, D. Berthelot, C.-L. Li, Z. Zhang, N. Carlini, E. D. Cubuk, A. Kurakin, H. Zhang, and C. Raffel, “Fixmatch: Simplifying semi-supervised learning with consistency and confidence,” in _NIPS_ , 2020.
  * [13] D. Berthelot, N. Carlini, I. Goodfellow, N. Papernot, A. Oliver, and C. Raffel, “Mixmatch: A holistic approach to semi-supervised learning,” in _NIPS_ , 2019.
  * [14] H. Venkateswara, J. Eusebio, S. Chakraborty, , and S. Panchanathan, “Deep hashing network for unsupervised domain adaptation,” in _CVPR_ , 2017.
  * [15] X. Peng, Q. Bai, X. Xia, Z. Huang, K. Saenko, and B. Wang., “Moment matching for multi-source domain adaptation,” in _ICCV_ , 2019.
  * [16] K. Saito, K. Watanabe, Y. Ushiku, and T. Harada, “Maximum classifier discrepancy for unsupervised domain adaptation,” in _CVPR_ , 2018.
  * [17] B. Gong, K. Grauman, and F. Sha, “Connecting the dots with landmarks: Discriminatively learning domain-invariant features for unsupervised domain adaptation,” in _ICML_ , 2013.
  * [18] D. Sejdinovic, B. Sriperumbudur, A. Gretton, and K. Fukumizu, “Equivalence of distance-based and rkhs-based statistics in hypothesis testing,” _The Annals of Statistics_ , 2013.
  * [19] B. Sun, J. Feng, and K. Saenko, “Correlation alignment for unsupervised domain adaptation,” in _Domain Adaptation in Computer Vision Applications_ , 2016\.
  * [20] H. Nam, H. Lee, J. Park, W. Yoon, and D. Yoo, “Reducing domain gap via style-agnostic networks,” in _arXiv_ , 2020.
  * [21] J. Li, G. Li, Y. Shi, and Y. Yu, “Cross-domain adaptive clustering for semi-supervised domain adaptation,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2021, pp. 2505–2514.
  * [22] A. Singh, “Clda: Contrastive learning for semi-supervised domain adaptation,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 5089–5101, 2021.
  * [23] K. Li, C. Liu, H. Zhao, Y. Zhang, and Y. Fu, “Ecacl: A holistic framework for semi-supervised domain adaptation,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 8578–8587.
  * [24] J. Liang, D. Hu, and J. Feng, “Domain adaptation with auxiliary target domain-oriented classifier,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2021, pp. 16 632–16 642.
  * [25] E. D. Cubuk, B. Zoph, J. Shlens, and Q. V. Le, “Randaugment: Practical automated data augmentation with a reduced search space,” in _NIPS_ , 2020\.
  * [26] E. D. Cubuk, B. Zoph, D. Mane, V. Vasudevan, and Q. V. Le, “Autoaugment: Learning augmentation policies from data,” in _CVPR_ , 2019.
  * [27] F. H. K. dos Santos Tanaka and C. Aranha, “Data augmentation using gans,” in _arXiv_ , 2019.
  * [28] D. Berthelot, N. Carlini, E. D. Cubuk, A. Kurakin, K. Sohn, H. Zhang, and C. Raffel, “Remixmatch: Semi-supervised learning with distribution alignment and augmentation anchoring,” in _ICLR_ , 2020.
  * [29] Y. Chen, C. Wei, A. Kumar, and T. Ma, “Self-training avoids using spurious features under domain shift,” in _NIPS_ , 2020.
  * [30] Y. Grandvalet and Y. Bengio, “Semi-supervised learning by entropy minimization,” in _NIPS_ , 2004.
  * [31] D.-H. Lee, “Pseudo-label : The simple and efficient semi-supervised learning method for deep neural networks,” _ICML 2013 Workshop : Challenges in Representation Learning (WREPL)_.
  * [32] T. Miyato, S. ichi Maeda, M. Koyama, and S. Ishii, “Virtual adversarial training: A regularization method for supervised and semi-supervised learning,” in _IEEE Transactions on PAMI_ , 2018.
  * [33] A. Tarvainen and H. Valpola, “Mean teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results,” in _NIPS_ , 2017.
  * [34] H. Zhang, M. Cisse, Y. N. Dauphin, and D. Lopez-Paz, “mixup: Beyond empirical risk minimization,” in _ICLR_ , 2018.
  * [35] L. van der Maaten and G. Hinton, “Visualizing data using t-sne,” _JMLR_ , vol. 9, 2008. [Online]. Available: http://jmlr.org/papers/v9/vandermaaten08a.html
  * [36] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Köpf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala, “Pytorch: An imperative style, high-performance deep learning library,” in _NIPS_ , 2019.
  * [37] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _CVPR_ , 2016.
  * [38] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “Imagenet classification with deep convolutional neural networks,” in _NIPS_ , 2012.
  * [39] R. Ranjan, C. D. Castillo, and R. Chellappa, “L2-constrained softmax loss for discriminative face verification,” in _arXiv_ , 2017.
  * [40] M. Long, Z. Cao, J. Wang, and M. I. Jordan, “Conditional adversarial domain adaptation,” in _NIPS_ , 2018.
  * [41] J. Li, L. Guanbin, S. Yemin, and Y. Yu, “Domain adaptation with auxiliary target domain-oriented classifier,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2021, pp. 16 632–16 642.
  * [42] T.-Y. Lin, P. Goyal, R. Girshick, K. He, and P. Dollár, “Focal loss for dense object detection,” in _Proceedings of the IEEE international conference on computer vision_ , 2017, pp. 2980–2988.

|  Megh Bhalerao received his Bachelor’s of Technology Degree in Electrical
Engineering from the National Institute of Technology Karanataka, India in
2020. He is currently an MS EE Student at the University of Washington
Seattle.
---|---
|  Anurag Singh is currently MS in Computer Science student at TU Munich. He
completed his undergraduate in CS from NSIT, University of Delhi in 2018.
---|---
|  Soma Biswas received the PhD degree in Electrical Engineering from
University of Maryland, College Park in 2009. She is currently an Associate
Professor in the Electrical Engineering Department, Indian Institute of
Science, Bangalore. Her research interests is in Computer Vision, Pattern
Recognition, Machine Learning and related areas. She is a Senior Member of
IEEE.
---|---

##  8 Supplimentary Material

###  8.1 Modularity of our Source Example Weighing Framework

We can seamlessly integrate our source example weighing scheme with any given
SSDA framework. In Table V we show that our proposed source example weighing
framework can improve the performance of a recently proposed SSDA work Cross
Domain Adaptive Clustering [41].

Net | Method | R to C | R to P | P to C | C to S | S to P | R to S | P to R | Mean
---|---|---|---|---|---|---|---|---|---
1 shot | 3 shot | 1 shot | 3 shot | 1 shot | 3 shot | 1 shot | 3 shot | 1 shot | 3 shot | 1 shot | 3 shot | 1 shot | 3 shot | 1 shot | 3 shot
ResNet34 | CDAC | 77.4 | 79.6 | 74.2 | 75.1 | 75.5 | 79.3 | 67.6 | 69.9 | 71.0 | 73.4 | 69.2 | 72.5 | 80.4 | 81.9 | 73.6 | 76.0
CDAC + SEW | 78.1 | 80.1 | 75.1 | 75.5 | 75.7 | 78.7 | 68.7 | 70.7 | 71.8 | 73.7 | 70.8 | 72.8 | 80.9 | 82.6 | 74.4 | 76.2

TABLE V: Comparison of CDAC performance ($\%$) w.r.t. CDAC + SEW (source
example weighing) on DomainNet dataset for both $1$ and $3$-shot protocols on
4 domains, R: Real, C: Clipart, P: Clipart, S: Sketch.

###  8.2 Comparison of SEW with standard focal loss

In table VI, we compare our proposed source example weighing scheme with the
standard focal loss which assigns weights to examples based on hardness. Our
SEW scheme is in contrast to focal loss where we assign example weights based
on domain similarity.

Weighting-Strategy | R to S | R to C
---|---|---
No Weights | 70.8 | 76.3
Fixed Weights | 68.6 | 73.2
Focal Loss | 69.6 | 74.8
Proposed Class-wise Adaptability Based Weights | 72.5 | 79.2
TABLE VI: Comparison of the proposed weighting scheme and Focal loss in 3-Shot
setting on Domainnet dataset with ResNet-34 as backbone.


# Note on disjoint faces in simple topological graphs

Ji Zeng Department of Mathematics, University of California San Diego, La
Jolla, CA, 92093 USA. Supported by NSF grant DMS-1800746. Email:
<EMAIL_ADDRESS>
###### Abstract

We prove that every $n$-vertex complete simple topological graph generates at
least $\Omega(n)$ pairwise disjoint $4$-faces. This improves upon a recent
result by Hubard and Suk. As an immediate corollary, every $n$-vertex complete
simple topological graph drawn in the unit square generates a $4$-face with
area at most $O(1/n)$. This can be seen as a topological variant of
Heilbronn’s problem for $4$-faces. We construct examples showing that our
result is asymptotically tight. We also discuss the similar problem for
$k$-faces with arbitrary $k\geq 3$.

##  1 Introduction

A _topological graph_ is a graph drawn in the plane such that its vertices are
represented by points, and its edges are represented by non-self-intersecting
curves connecting the corresponding points. The curves are not allowed to pass
through vertices different from their endpoints, and if two edges share an
interior point, then they must properly cross at that point in common. A
topological graph is _simple_ if any two of its edges intersect at most once,
either at a common endpoint or at a proper crossing point. A subgraph $H$ of a
simple topological graph $G$ is said to be _plane_ if its edges do not cross.
A _$k$ -face_ generated by $G$ refers to the bounded open cell enclosed by a
plane $k$-cycle in $G$. Here a $k$-cycle means a cycle of length $k$. We
remark that the boundary cycles of two disjoint faces can share vertices or
edges.

The main result of this paper is the following theorem. It improves the main
result in a recent paper [7] by Hubard and Suk from a weaker bound of
$\Omega(n^{1/3})$ in the same context.

######  Theorem 1.1.

Every $n$-vertex complete simple topological graph generates at least
$\Omega(n)$ pairwise disjoint $4$-faces.

This gives us the following immediate corollary.

######  Corollary 1.2.

Every $n$-vertex complete simple topological graph drawn in the unit square
generates a $4$-face with area at most $O(1/n)$.

We also show that Corollary 1.2, and hence Theorem 1.1, are asymptotically
tight.

######  Theorem 1.3.

For every $n\geq 1$, there is a $n$-vertex complete simple topological graph
drawn in the unit square such that every face it generates has area at least
$\Omega(1/n)$.

The famous Heilbronn’s problem [9] asks to determine the smallest $h(n)$ such
that any set of $n$ points in the unit square form a triangle with area at
most $h(n)$. This problem is still open despite many efforts through over 70
years. The current best known bounds (due to [8, 3]) for $h(n)$ are

$\Omega\left(\frac{\log
n}{n^{2}}\right)<h(n)<O\left(n^{-\frac{8}{7}-\frac{1}{2000}}\right).$

We call a topological graph _geometric_ if its edges are straight line
segments. With this notion, Heilbronn’s problem can be reformulated as
follows: What is the smallest $h(n)$ such that any $n$-vertex complete
geometric graph drawn in the unit square generates a $3$-face with area at
most $h(n)$? Therefore, Corollary 1.2 and Theorem 1.3 can be seen as answers
to a topological variant of Heilbronn’s problem for $4$-faces.

It’s natural to consider the topological Heilbronn’s problem for $3$-faces.
However, Hubard and Suk [7] pointed out that we cannot expect a similar
phenomenon for $k$-faces when $k$ is odd.

######  Theorem 1.4 (Hubard–Suk).

For every $n\geq 1$ and every $\epsilon>0$, there is a $n$-vertex complete
simple topological graph drawn in the unit square such that every odd face it
generates has area at least $1-\epsilon$.

In particular, Theorem 1.4 tells us that it’s possible for all odd faces to
have a nonempty intersection. On the other hand, we can still prove the
existence of many pairwise disjoint $k$-faces when $k$ is even.

######  Theorem 1.5.

For even $k\geq 4$, every $n$-vertex complete simple topological graph
generates at least $(\log n)^{1/4-o(1)}$ pairwise disjoint $k$-faces.

We conjecture that the bound of $(\log n)^{1/4-o(1)}$ in Theorem 1.5 can be
improved to a bound of $\Omega(n)$. This will (if true) asymptotically match
the counterpart given by Theorem 1.3.

##  2 Proof of Theorem 1.1

Our proof is based on a phenomenon of simple topological graphs discovered by
Fulek and Ruiz-Vargas [4, 10].

######  Lemma 2.1 (Fulek–Ruiz-Vargas).

Suppose $G$ is a complete simple topological graph, $H$ is a plane connected
subgraph, and $v$ is a vertex of $G$ not in $H$, then there exist at least two
edges between $v$ and the vertices of $H$ that do not cross $H$.

The following lemma is the key to our proof. It has been essentially proven
(using Lemma 2.1) by Hubard and Suk [7] except for some small cases.

######  Lemma 2.2.

Suppose $G$ is a complete simple topological graph and $C\subset G$ is a plane
$k$-cycle, if the face $F$ enclosed by $C$ contains at least $6k$ vertices of
$G$ in its interior, then $G$ generates a $4$-face that lies inside $F$.

###### Proof Sketch.

When $k=3$, Lemma 2.1 obviously guarantees a $4$-face inside $F$ as long as
$F$ contains $1$ vertex of $G$. When $k\geq 5$, Lemma 3.4 in [7] states that
if $F$ contains more than $6(k-4)$ vertices, then $G$ generates a $4$-face
inside $F$. This implies what we want. When $k=4$, we apply Lemma 2.1 to any
vertex $v$ of $G$ inside $F$, so we obtain two edges emanating from $v$ to $C$
that lie inside $F$. This divides $F$ into two faces $F_{1}$ and $F_{2}$. If
$F_{1}$ and $F_{2}$ are $4$-faces, then we are done. Otherwise, we can assume
without loss of generality that $F_{1}$ is a $3$-face and $F_{2}$ is a
$5$-face. By our hypothesis and the Pigeonhole principle, either $F_{1}$
contains $1$ vertex or $F_{2}$ contains $6k-1=23$ vertices, hence we finish
the proof by reduction to previous cases. ∎

We need a fact by García, Pilz, and Tejel [5], whose proof also relies on
Lemma 2.1.

######  Lemma 2.3 (García–Pilz–Tejel).

In a complete simple topological graph, every plane subgraph is contained in
another plane subgraph that is spanning and biconnected.

Our proof is inspired by the argument of the main result in [1] by Aichholzer
et al.

###### Proof of Theorem 1.1.

Let $G$ be any $n$-vertex complete simple topological graph. A $4$-cell refers
to a (bounded) $4$-face generated by $G$ or an unbounded cell enclosed by a
plane $4$-cycle of $G$. We consider a partial order on collections of pairwise
disjoint $4$-cells of $G$. For two collections $\mathcal{C}_{1}$ and
$\mathcal{C}_{2}$ of disjoint $4$-cells, we say
$\mathcal{C}_{1}\preceq\mathcal{C}_{2}$ if
$|\mathcal{C}_{1}|<|\mathcal{C}_{2}|$, or if
$|\mathcal{C}_{1}|=|\mathcal{C}_{2}|$ and each $4$-cell in $\mathcal{C}_{2}$
is contained in some $4$-cell in $\mathcal{C}_{1}$. Let $\mathcal{C}$ be a
maximal element with respect to this partial order.

Let $H$ be the subgraph of $G$ that consists of all the vertices and edges on
the boundaries of the $4$-cells in $\mathcal{C}$. Notice that $H$ is plane. By
Lemma 2.3, we can augment $H$, by adding only edges of $G$, to another plane
subgraph $H^{\prime}\subset G$ such that $H^{\prime}$ is biconnected and the
vertex sets of $H$ and $H^{\prime}$ coincide. Since $H^{\prime}$ is plane and
biconnected, it cuts the plane into cells $f_{0},f_{1},\dots,f_{k}$ each of
whose boundaries is a plane cycle. Here, $f_{0}$ denotes the unbounded cell of
this cutting.

Let $|f_{i}|$ be the number of vertices on the boundary of $f_{i}$, and
$v(f_{i})$ be the number of vertices in the interior of $f_{i}$. Suppose that
$v(f_{0})\geq 6|f_{0}|$, we consider $G$ as drawn on a sphere, choose a new
pole outside $f_{0}$, and apply Lemma 2.2, then we conclude that $G$ generates
a $4$-cell inside $f_{0}$. However, this contradicts $\mathcal{C}$ being
maximal with respect to $\preceq$. Similarly, by the maximality of
$\mathcal{C}$ and Lemma 2.2, we must have

$v(f_{i})<6|f_{i}|.$

On the other hand, we have $\sum_{i}(|f_{i}|+v(f_{i}))\geq n$, so
$\sum_{i}|f_{i}|>n/7$.

Let $v(H^{\prime})$ be the number of vertices of $H^{\prime}$, and
$e(H^{\prime})$ be the number of edges of $H^{\prime}$. We know that
$2e(H^{\prime})=\sum_{i}|f_{i}|$ by double-counting, so we have
$e(H^{\prime})>n/14$. Since $H^{\prime}$ is plane, we have the classical bound
$3v(H^{\prime})-6\geq e(H^{\prime})$. Hence, we have
$v(H)=v(H^{\prime})>n/42$. Since each vertex of $H$ lies on the boundary of
some cell in $\mathcal{C}$, and each cell in $\mathcal{C}$ has $4$ vertices on
its boundary,

$|\mathcal{C}|\geq v(H)/4>n/168.$

Notice that $\mathcal{C}$ contains at most one unbounded $4$-cell, and the
others form a collection of pairwise disjoint $4$-faces. Therefore we conclude
the proof. ∎

##  3 Proof of Theorem 1.3

We describe a complete simple topological graph $D_{n}$ drawn in the unit
square $S=[0,1]\times[0,1]$.

First, for each $1\leq i,j\leq n$, we pick a point

$v_{ij}=(\frac{i-1}{n}+\frac{j}{n(n+1)},0.5)\in S.$

We also define a region $S_{i}=(\frac{i-1}{n},\frac{i}{n})\times(0.5,1)$ for
$1\leq i\leq n$. Notice that $v_{ij}$ is located on the lower side of the
boundary of $S_{i}$. Since each $S_{i}$ has area $1/(2n)$, we can place a
closed rectangle $R_{i}$ inside $S_{i}$ that has area $1/(3n)$.

Then, we draw curves in the upper half part of $S$. For each $i\neq j$, we
draw a convex curve $c_{ij}$ emanating from $v_{ii}$ to $v_{ij}$ such that the
interior of $c_{ij}$ is contained in $S_{i}$. These curves can be drawn
without any crossings. Furthermore, we make sure that $R_{i}$ is contained
inside the convex hull of the curve $c_{ij}$ whenever $j<i$. See Figure 1.

Figure 1: Illustration of the drawing in $S_{i}$.

Next, we draw curves in the lower half part of $S$. For each $1\leq
i_{1}<i_{2}\leq n$, we take $j_{1}=i_{1}+(n+1-i_{2})$ and $j_{2}=i_{2}-i_{1}$.
Then we draw a lower semicircle $s_{i_{1}i_{2}}$ from $v_{i_{1}j_{1}}$ to
$v_{i_{2}j_{2}}$. We can check that two semicircles $s_{i_{1}i_{2}}$ and
$s_{i_{3}i_{4}}$ cross if and only if $i_{1}<i_{3}<i_{2}<i_{4}$ or
$i_{3}<i_{1}<i_{4}<i_{2}$. Note that two semicircles here can have at most one
crossing.

Finally, we define the complete simple topological graph $D_{n}$. We take the
point $v_{ii}$ as the vertex $v_{i}$ of $D_{n}$ for each $i$. For each $1\leq
i_{1}<i_{2}\leq n$, we take $j_{1}=i_{1}+(n+1-i_{2})$ and $j_{2}=i_{2}-i_{1}$
and draw the edge $v_{i_{1}}v_{i_{2}}$ by concatenating the curve
$c_{i_{1}j_{1}}$ in $S_{i_{1}}$, the semicircle $s_{i_{1}i_{2}}$, and the
curve $c_{i_{2}j_{2}}$ in $S_{i_{2}}$. Because crossings of edges only happen
between their semicircle part, we can check that $D_{n}$ is indeed simple
using the crossing pattern of our semicircles.

###### Proof of Theorem 1.3.

Let $C$ be a plane $k$-cycle in $D_{n}$. Because two edges
$v_{i_{1}}v_{i_{2}}$ ($i_{1}<i_{2}$) and $v_{i_{3}}v_{i_{4}}$ ($i_{3}<i_{4}$)
cross in $D_{n}$ if and only if $i_{1}<i_{3}<i_{2}<i_{4}$ or
$i_{3}<i_{1}<i_{4}<i_{2}$, we can check that $C$ can be written as
$v_{i_{1}}\to v_{i_{2}}\to\dots\to v_{i_{k}}\to v_{i_{1}}$ for some
$i_{1}<i_{2}<\dots<i_{k}$. Therefore, the face enclosed by $C$ must contain
the rectangles $R_{i_{2}},R_{i_{3}},\dots,R_{i_{k-1}}$ each of whose areas is
at least $1/(3n)$, concluding the proof. ∎

##  4 Proof of Theorem 1.5

In this proof, we shall consider two prototypes of simple topological graphs:
convex geometric graphs and twisted graphs.

The complete _convex geometric graph_ $C_{m}$ is a complete simple topological
graph whose vertices are $m$ points in convex position, and edges are straight
line segments. We remark that any complete geometric graph must have its
vertices in general position (i.e. no collinear triples). The vertices of
$C_{m}$ can be labelled as $v_{1},v_{2},\dots,v_{m}$, such that two edges
$v_{i}v_{j}$ ($i<j$) and $v_{k}v_{\ell}$ ($k<\ell$) cross if and only if
$i<k<j<\ell$ or $k<i<\ell<j$.

The complete _twisted graph_ $T_{m}$ is a complete simple topological graph
whose vertices can be labelled as $v_{1},v_{2},\dots,v_{m}$, such that two
edges $v_{i}v_{j}$ ($i<j$) and $v_{k}v_{\ell}$ ($k<\ell$) cross if and only if
$i<k<\ell<j$ or $k<i<j<\ell$. Specifically, for $j$ ranging from $1$ to $m$,
we let $v_{j}$ be the point $(j,0)$ on the $x$-axis and draw the edges
$v_{i}v_{j}$ ($i<j$) as follows: for $i$ ranging from $1$ to $j-1$, we draw a
convex curve $c_{ij}$ from $v_{j}$ to a point $u_{ij}$ on the $y$-axis; we
make sure the interior of the convex hull of $c_{ij}$ contains the plane
origin, the points $v_{1},v_{2},\dots,v_{j-1}$, and all the previously drawn
edges; we draw the edge $v_{i}v_{j}$ by concatenating the curve $c_{ij}$ and
the line segment from $u_{ij}$ to $v_{i}$. See Figure 2.

Figure 2: Illustration of $T_{5}$. The cross represents the plane origin.

Our proof is based on a Ramsey-type result on the crossing patterns of simple
topological graphs by Suk and Zeng [11]. Two simple topological graphs $G$ and
$H$ are said to be _weakly isomorphic_ if there is an incidence preserving
bijection between $G$ and $H$ such that two edges of $G$ cross if and only if
the corresponding edges in $H$ cross as well.

######  Theorem 4.1 (Suk–Zeng).

Every $n$-vertex complete simple topological graph has an induced subgraph on
$m\geq(\log n)^{1/4-o(1)}$ vertices that is weakly isomorphic to either
$C_{m}$ or $T_{m}$.

Another ingredient of our proof is the following theorem by Gioan [6] (see
also [2]). A _triangle mutation_ is a process of moving an edge over the
crossing point of two other edges, assuming all three edges are pairwise
crossing and the triangular region bounded by them doesn’t intersect other
vertices or edges throughout this process. See Figure 3.

Figure 3: Illustration of a triangle mutation. The triangular region is
shaded.

######  Theorem 4.2 (Gioan).

If two complete simple topological graphs $G$ and $H$ are weakly isomorphic,
then we can transform $G$ to $H$ by a sequence of triangle mutations and a
homeomorphism of the sphere.

###### Proof of Theorem 1.5.

Let $G$ be any $n$-vertex complete simple topological graph. By Theorem 4.1,
there are $m\geq(\log n)^{1/4-o(1)}$ vertices of $G$ inducing a subgraph $H$
that is weakly isomorphic to either the convex geometric graph $C_{m}$ or the
twisted graph $T_{m}$. By Theorem 4.2, we can transform $H$ to either $C_{m}$
or $T_{m}$ by a sequence of triangle mutations and a homeomorphism of the
sphere.

If $\mathcal{C}$ is a collection of pairwise disjoint $k$-faces, then after a
triangle mutation, the cells corresponding to elements in $\mathcal{C}$ still
form a collection of pairwise disjoint $k$-faces. Indeed, we consider a
triangle mutation moving an edge $e_{1}$ over the crossing point of $e_{2}$
and $e_{3}$. If $e_{1}$ is not contained in the boundary of any face in
$\mathcal{C}$, then $\mathcal{C}$ remains unchanged after the triangle
mutation. If $e_{1}$ is contained in the boundary of some face in
$\mathcal{C}$, then neither $e_{2}$ nor $e_{3}$ is the boundary of any face in
$\mathcal{C}$ as $e_{1},e_{2},e_{3}$ are pairwise crossing. Because the
triangular region bounded by $e_{1},e_{2},e_{3}$ doesn’t intersect other
vertices or edges, the triangle mutation only affects $\mathcal{C}$ by a
deformation of the one or two faces containing $e_{1}$. Moreover, a
homeomorphism of the sphere may make at most one cell in $\mathcal{C}$ become
unbounded, the others still form a collection of pairwise disjoint $k$-faces.

It suffices for us to show that both $C_{m}$ and $T_{m}$ generate $\Omega(m)$
many pairwise disjoint $k$-faces. For the convex geometric graph $C_{m}$, we
can label its vertices as $v_{1},v_{2},\dots,v_{m}$ in a non-decreasing order
of their $x$-coordinates. Then we divide the vertex set into $\Omega(m)$ many
$k$-tuples

$\tau_{i}=\\{v_{(i-1)k+1},\ v_{(i-1)k+2},\ \dots,\
v_{ik}\\}\quad\text{for}\quad 1\leq i\leq\lfloor m/k\rfloor.$

Because $C_{m}$ is a convex geometric graph, the interior of the convex hull
of each $\tau_{i}$ is a $k$-face. Furthermore, the projections of these
$k$-faces on the $x$-axis are pairwise disjoint open intervals, so $C_{m}$
generates $\Omega(m)$ many pairwise disjoint $k$-faces.

For the twisted graph $T_{m}$, we recall, from the beginning of this section,
that the vertices of $T_{m}$ are labelled as $v_{1},v_{2},\dots,v_{m}$. We
divide the vertex set into $\Omega(m)$ many $k$-tuples $\tau_{i}$ as we did
for $C_{m}$. For a particular $k$-tuple (for example) $\tau_{1}$, we define
its corresponding cycle

$C_{1}=v_{1}\to v_{\frac{k}{2}+1}\to v_{k}\to v_{\frac{k}{2}}\to v_{k-1}\to
v_{\frac{k}{2}-1}\to v_{k-2}\to v_{\frac{k}{2}-2}\to\dots\to
v_{\frac{k}{2}+2}\to v_{2}\to v_{1}.$

Using the crossing pattern of $T_{m}$, we can check that $C_{1}$ is plane and
hence it encloses a $k$-face $F_{1}$. Similarly we can define the cycle
$C_{i}$ and the face $F_{i}$ according to $\tau_{i}$ for all $1\leq
i\leq\lfloor m/k\rfloor$. We claim that any two faces $F_{i}$ and $F_{j}$
($i<j$) are disjoint. Indeed, we use $R$ to denote the convex hull of the edge
$v_{(i+1)k}v_{jk+1}$. By the process of drawing $T_{m}$, the induced subgraph
on $\tau_{i}$ is inside $R$, and the induced subgraph on $\tau_{j}$ is outside
$R$. As a consequence, $F_{i}$ is contained in $R$, and $F_{j}$ either
contains $R$ or doesn’t intersect $R$. Notice that the negative portion of the
$x$-axis is a ray emanating from the plane origin that crosses $C_{j}$ an even
number of times. This means the plane origin is outside the face $F_{j}$
enclosed by $C_{j}$. However, the plane origin is contained inside $R$. So
$F_{j}$ doesn’t intersect $R$ and hence is disjoint from $F_{i}$. Therefore,
we conclude that $T_{m}$ generates $\Omega(m)$ many pairwise disjoint
$k$-faces. ∎

Acknowledgement. I wish to thank Andrew Suk for reading an early draft of this
paper and Alexandra Weinberger for discussions at SoCG 2023. This paper is
dedicated to the memory of Emily Zhu.

## References

  * [1] O. Aichholzer, A. García, J. Tejel, B. Vogtenhuber, and A. Weinberger.  Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs.  In 38th International Symposium on Computational Geometry (SoCG 2022), pages 5:1–5:18, 2022.
  * [2] A. Arroyo, D. McQuillan, R. B. Richter, and G. Salazar.  Drawings of $K_{n}$ with the same rotation scheme are the same up to triangle-flips (Gioan’s Theorem).  Australasian Journal of Combinatorics, 67(2):131–144, 2017.
  * [3] A. Cohen, C. Pohoata, and D. Zakharov.  A new upper bound for the Heilbronn triangle problem.  arXiv preprint arXiv:2305.18253, 2023.
  * [4] R. Fulek and A. J. Ruiz-Vargas.  Topological graphs: empty triangles and disjoint matchings.  In Proceedings of the twenty-ninth annual Symposium on Computational Geometry, pages 259–266, 2013.
  * [5] A. García, A. Pilz, and J. Tejel.  On plane subgraphs of complete topological drawings.  Ars Mathematica Contemporanea, 20(1):69–87, 2021.
  * [6] E. Gioan.  Complete graph drawings up to triangle mutations.  Discrete & Computational Geometry, 67(4):985–1022, 2022.
  * [7] A. Hubard and A. Suk.  Disjoint Faces in Drawings of the Complete Graph and Topological Heilbronn Problems.  In 39th International Symposium on Computational Geometry (SoCG 2023), pages 41:1–41:15, 2023.
  * [8] J. Komlós, J. Pintz, and E. Szemerédi.  A lower bound for Heilbronn’s problem.  Journal of the London Mathematical Society, 2(1):13–24, 1982.
  * [9] K. F. Roth.  On a problem of Heilbronn.  Journal of the London Mathematical Society, 1(3):198–204, 1951\.
  * [10] A. J. Ruiz-Vargas.  Empty triangles in complete topological graphs.  Discrete & Computational Geometry, 53(4):703–712, 2015.
  * [11] A. Suk and J. Zeng.  Unavoidable patterns in complete simple topological graphs.  In Graph Drawing and Network Visualization, pages 3–15. Springer, 2022.