# On Evolving Attention Towards Domain Adaptation

Kekai Sheng1 Ke Li1 Xiawu Zheng2 Jian Liang3
Weiming Dong4 Feiyue Huang1 Rongrong Ji2 Xing Sun1
1Youtu Lab, Tencent 2Xiamen University 3National University of Singapore
4NLPR, CASIA
{saulsheng, tristanli, winfredsun<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Corresponding author

###### Abstract

Towards better unsupervised domain adaptation (UDA), recently, researchers
propose various domain-conditioned attention modules and make promising
progresses. However, considering that the configuration of attention, _i.e_.,
the type and the position of attention module, affects the performance
significantly, it is more generalized to optimize the attention configuration
automatically to be specialized for arbitrary UDA scenario. For the first
time, this paper proposes EvoADA: a novel framework to evolve the attention
configuration for a given UDA task without human intervention. In particular,
we propose a novel search space containing diverse attention configurations.
Then, to evaluate the attention configurations and make search procedure UDA-
oriented (transferability + discrimination), we apply a simple and effective
evaluation strategy: 1) training the network weights on two domains with off-
the-shelf domain adaptation methods; 2) evolving the attention configurations
under the guide of the discriminative ability on the target domain.
Experiments on various kinds of cross-domain benchmarks, _i.e_., Office-31,
Office-Home, CUB-Paintings, and Duke-Market-1510, reveal that the proposed
EvoADA consistently boosts multiple state-of-the-art domain adaptation
approaches, and the optimal attention configurations help them achieve better
performance.

##  1 Introduction

Unsupervised domain adaptation (UDA) [15, 33, 23, 42] aims at exploiting the
meaningful knowledge from a labelled source domain to facilitate learning on
another unlabelled target domain. Generally, researchers focus on learning
domain-general features. For better performance in the target domain,
researchers propose domain-conditioned spatial or channel attention mechanisms
[24, 48, 50, 25] to mitigate negative transfer and enhance the insufficient
domain-specific features. However, these works design the attention module by
hand and may fall to a sub-optimal solution in real world application. For
example, in Figure 1, we observe that on a given UDA task and a pre-defined
backbone network, different configurations of the attention module focus on
various visual patterns and thus may come out with different accuracies.
Therefore, given one arbitrary UDA task, a more generalized manner is to
automatically find the optimal attention configuration.

Figure 1: Why Attention Configuration Matters. Intuitively, different
configurations of attention work differently. Given one UDA scenario, our
EvoADA finds which and where to add the attention modules and achieves better
domain adaptation performance.

One natural and widely-used solution is neural architecture search (NAS) [31,
57, 38, 19]. The goal of NAS is to automatically seek for effective
architectures [57, 26]. Nevertheless, [13, 26] point out that existing NAS
algorithms rarely consider the topic of transfer learning and are vulnerable
to large domain shift, resulting in inferior performance for UDA tasks. We
speculate the reasons as follows. The first challenge is the design of search
space. Existing popular search spaces (_e.g_., NASNet [57] or DARTS [31]) are
not specialized to refine the attention module and maybe ineffective in
generating optimal architectures for domain adaptation. The second challenge
is how to evaluate the searched architectures, which is an open question. In a
conventional NAS setting, we have labelled data on both the training and
validation partitions, which are assumed to have little domain shift [37]. It
means that the architectures optimized on the training domain can be directly
evaluated on the validation domain with ground-truth labels. But in an UDA
scenario, no manual annotations are available in the target domain, and the
relatively larger domain shift between the source and the target domains make
it ineffective to evaluate the models only on the source domain.

Figure 2: UDA result comparisons on Office-Home datasets.

In this paper, for the first time, we propose a novel NAS algorithm, termed
EvoADA. It automatically searches attention configurations, _i.e_., the type
and position of attention module, for different UDA scenarios. Specifically,
different from existing search spaces [57, 31] on the basic CNN operations, we
design a novel search space on diverse configurations of typical attention
modules [52, 21, 16]. To evaluate the attention configuration effectively and
make the configuration optimization UDA-oriented, we further propose a simple
yet effective evaluation strategy: train the network weights on both the two
domains with arbitrary UDA methods to learn transferable knowledge and then
evaluate the attention configurations by our pseudo-labeling discrimination in
target domain to check how the learned knowledge are discriminative on target
domain. We find that the estimated qualities are strongly correlates with the
final accuracy in the target domain. Eventually, we propose a new UDA-oriented
NAS scheme based on a typical evolution-based NAS algorithm. Building on
extensive experiments on $4$ cross-domain benchmarks, we verify that the
searched attention configuration via our EvoADA benefits multiple state-of-
the-art methods [27, 17, 47] and lead to better performance in the target
domain (Figure 2). The experiments also provide practical insights for further
research.

The main contributions are summarized as follows:

  * •

We propose a new search space with a set of effective attention modules to
cover diverse attention configurations and reinforce representations for UDA
tasks.

  * •

We propose a simple yet effective strategy to evaluate the UDA performance of
attention configurations. Empirically, the measure of pseudo-labeling in the
target domain is effective to seek for optimal attention configurations.

  * •

Experiments on four benchmarks verify that our algorithm successfully
consolidates various state-of-the-art methods and largely promote their
performance.

##  2 Related Work

#### Unsupervised Domain Adaptation

(UDA) [15, 33, 7] aims to facilitate the learning on one unlabelled target
domain with the knowledge from one labelled source domain, and has practical
value in many tasks [17, 47, 10]. There are three typical settings: closed-set
UDA, partial-set UDA (PDA), and open-set UDA (ODA). Technically, two
fundamental problems lie in the core of UDA: 1) how to diminish the domain
discrepancy on representation spaces of two domains; 2) how to deal with
negative transfer and promote discrimination on target domains. To solve the
problems, researchers propose different methods that can be divided into three
mainstreams: 1) feature disentanglement methods [48, 25]; 2) domain alignment
methods [43, 32]; and 3) discrimination-aware methods [58, 12, 27]. More
recently, novel loss designs (_e.g_., [55, 42] for universal domain
adaptation; [11] for a progressive method) and advanced network modules
(_e.g_., [48] for normalization module; [51] for convolution module; [50, 24,
25] for attention module) are proposed for better domain adaptation
performance. Different from TADA [50], CADA [24], and DCAN [25] that combines
a handcrafted attention module with an elaborate loss design, we solely
investigate the improvement brought by an automatically searched attention
module, which may benefit most of the state-of-the-art UDA methods in a more
flexible way.

#### Neural Architecture Search

(NAS) aims to automate architecture engineering procedure given one certain
problem. There are five NAS mainstreams: random search, Bayesian-based method
[14], reinforcement-learning approach, evolutionary scheme [1], and surrogate-
based framework ($\emph{e.g}.\hbox{}$, gradient-based and predictor-based).
Representative approaches include DARTS [31], P-DARTS [8], AmoebaNet [38],
one-shot NAS [2, 19], path-level NAS [3], NASNet [57], and AdaptNAS [26].
Recently, NAS technique has found its value in wide tasks, such as detection
[9], segmentation [29], and person re-ID [36]. Different from the existing
literature, in this paper, we investigate the possibility and an effective
solution to search for optimal architectures towards better domain adaptation.
Concurrently, we find that Li  _et al_. [26] and Robbiano  _et al_. [40] have
investigated a similar topic: the generalization abilities of architectures
cross domains. The differences are two-fold: 1) we propose a novel search
space for diverse attention configurations, which is different from the search
space of AdaptNAS [26] (akin to NASNet [57]) and ABAS [40] (just change the
architecture of the auxiliary adversarial branch); 2) we focus on an effective
NAS protocol to search for optimal attention configuration towards UDA tasks.

##  3 Methodology

###  3.1 Preliminary

#### Unsupervised Domain Adaptation.

Formally, in one UDA task, we have a labeled dataset
$\\{x^{\mathcal{S}}_{i},y^{\mathcal{S}}_{i}\\}_{i=1}^{N^{\mathcal{S}}}$ of
$N^{\mathcal{S}}$ image-annotation pairs from source domain $\mathcal{S}$ and
an unlabeled dataset $\\{x^{\mathcal{T}}_{i}\\}_{i=1}^{N^{\mathcal{T}}}$ of
$N^{\mathcal{T}}$ images from target domain $\mathcal{T}$. Considering that
the two domains $\mathcal{S}$ and $\mathcal{T}$ are semantically related, UDA
aims to facilitate the learning on $\mathcal{T}$ by exploiting the meaningful
knowledge learned from $\mathcal{S}$ and try to handle the challenges of large
domain shift between source domain $\mathcal{S}$ and target domain
$\mathcal{T}$.

#### Neural Architecture Search.

Given one certain task, its goal to search optimal network architectures
automatically. Without loss of generality, we formulate the search procedure
in a bi-level optimization process:

$\begin{split}\alpha&=\mathop{\arg\min}_{\alpha\in\mathcal{A}}\mathcal{L}_{val}(y,\
F(x;\ \alpha,\theta^{*}(\alpha))),\\\ s.t.,\ \
&\theta^{*}(\alpha)=\mathop{\arg\min}_{\theta}\mathcal{L}_{tr}(y,\ F(x;\
\alpha,\theta)),\end{split}$ (1)

where $\alpha$ is the architecture parameter, $\mathcal{A}$ denotes the search
space that contains all possible architectures, $\theta$ is the network
weights, and $F(;\alpha,\theta)$ is the function of neural network. In Eq.
(1), we optimize $\alpha$ with one certain loss or evaluation function on
validation partition $\mathcal{L}_{val}$ under the constraint that its weight
parameter $\theta^{*}(\alpha)$ is optimal for another loss function on
training dataset $\mathcal{L}_{tr}$. Researchers propose several effective NAS
algorithms [38, 57, 31] to seek for optimal architectures $\alpha$ among
$\mathcal{A}$.

###  3.2 EvoADA

Our goal is to investigate a more generalized UDA framework from the
perspective of attention mechanism: automatically optimizing the configuration
of attention in backbone networks for one arbitrary UDA scenario. To this end,
we propose a new UDA-oriented NAS scheme, termed EvoADA, which searches the
optimal attention in the attention configuration search space by employing our
search algorithm and evaluation method. The overall illustration of the
proposed method is shown in Figure 3.

Figure 3: The pipeline of the proposed evolutionary framework to seek for
optimal attention configurations towards domain adaptation. Given an pre-
defined backbone, we sample several possible attention configurations from our
search space, and then conduct an UDA-oriented performance estimation: train
the network weights on the two domains with arbitrary domain adaptation method
to learn transferable knowledge and evaluate the pseudo-label discrimination
on target domain. Table 1: The basic element to make up various attention
modules. The element can also be easily extended with other kinds of attention
operations for practical usages. Attention Module
---
Module | Attention on | Parameter
spatial position | channel | Choices
SE [21] |  | $\surd$ | #channel
GSoP [16] | $\surd$ | $\surd$ | #channel
CBAM [52] | $\surd$ | $\surd$ | #channel
Identity |  |  | 1
Group Strategy
Group [49] |  | $\surd$ | #group

#### Search Space for Diverse Attention Configuration.

Inspired by recent domain-conditioned attention mechanisms in UDA tasks [48,
25, 51], we propose a novel and effective search space that consists of
diverse attention configurations, we define our search space in two aspects:
the type and the position of attention module.

$\triangleright$ Type. Based on the function, there are two basic types of
attention: spatial type and channel type, where spatial attention aims to
exploit spatial interdependence and the channel one aims to make use of
channel interdependence. When it comes to the choice of its parameter, there
are two extra hyper-parameters, #channel and #group, where the #channel and
the #group denote the number of channels and groups of intermediate features
within attention layers. To produce a diverse search space towards UDA
problems, we summarize the types and parameter choices of the widely-used
attention modules in Table 1 and make up various types of attention modules
with these basic elements. On sampling one type of attention, the procedure
is: i) choose among $4$ kinds of basic types (SE [21], GSoP [16], and CBAM
[52]) or Identity; ii) when we select the first $3$ modules, we have two
additional choices to make: #channel and #group. In our implementation,
#channel is $4$ ({$256$, $512$, $1024$, $2048$}) and #group is $4$ ({$1$, $2$,
$4$, $8$}). Thus, the number of possible attention modules is $(3\times
4\times 4+1)$. It should be noticed that the diversity and completeness of
Table 1 works well to produce optimal attention configurations for UDA
scenarios, as validated later in Section 4.

$\triangleright$ Position. We also need to consider the _position_ in a
backbone network to introduce attention modules, since features from different
intermediate layers have different transferability [54]. Suppose there are $L$
intermediate layers in the backbone network (_e.g_., $L=50$ in ResNet-50
[20]), we then have $L$ possible position choices. Given that low-level
features generally have better transferability, we choose the deeper $L/2$
layers to cut-off unnecessary attempts. For the shallower $L/2$ layers, we
apply weight sharing strategy on the backbone, akin to one-shot NAS algorithms
[2, 19]. To further simplify the search space, on each intermediate layer
within the backbone, we only select one attention module, instead of applying
parallel block design.

$\triangleright$ Overall complexity. Put the type and the position together,
we then formulate the attention configuration parameter $\alpha$ as:
$\alpha=[\alpha_{1},\,\alpha_{2},\,\cdots\,\alpha_{L/2}]$. $\alpha_{i}$
indicates the attention configuration on layer $i$ of the backbone network.
The overall complexity of our search space $\mathcal{A}$ is
$|\alpha_{i}|^{L/2}=(3\times 4\times 4+1)^{25}=49^{25}\approx 1\times
10^{42}$.

#### UDA-oriented Evaluation Strategy.

Considering that the core of the UDA task (transferability and
discrimination), we train the network weights with a certain attention
configuration $\theta(\alpha)$ on the two domains to learn transferable
representation and evaluate the discrimination of the models on target domain,
which in our case is mainly determined by the attention configuration
$\alpha$. Formally, we re-write the typical NAS formulation Eq. (1) as
follows:

$\centering\begin{split}\alpha&=\mathop{\arg\min}_{\alpha\in\mathcal{A}}\cdot\mathcal{L}^{PE}_{\mathcal{T}}(F(x;\
\alpha,\theta^{*}(\alpha))),\\\ s.t.,\ \
&\theta^{*}(\alpha)=\mathop{\arg\min}_{\theta}\mathcal{L}^{DA}_{\mathcal{S}+\mathcal{T}}(y,\
F(x;\ \alpha,\theta)),\\\ \end{split}\@add@centering$ (2)

where $\mathcal{L}^{DA}_{\mathcal{S}+\mathcal{T}}$ denotes one certain loss
function for the domain adaptation task from $\mathcal{S}$ to $\mathcal{T}$
(_e.g_., CDAN [32] or SHOT [27]); $\mathcal{L}^{PE}_{\mathcal{T}}$ is the
evaluation function to measure the discrimination of models in target domain
and based on the information maximization loss [18, 22], we propose a pseudo-
label discrimination term to measure the desirable properties of ideal
representations on target domain:

$\begin{split}\mathcal{L}^{PE}_{\mathcal{T}}&=\mathcal{L}^{ent}_{\mathcal{T}}+\mathcal{L}^{div}_{\mathcal{T}}+\mathcal{L}^{pse}_{\mathcal{T}},\\\
\end{split}$ (3)

where $\mathcal{L}^{ent}_{\mathcal{T}}$ is the information entropy of each
output prediction on target domain, $\mathcal{L}^{div}_{\mathcal{T}}$ is to
measure the diversity of output predictions on target domain (_e.g_., the
negative information entropy of the average output predictions), and
$\mathcal{L}^{pse}_{\mathcal{T}}$ is the cross-entropy based on pseudo-labels
$\hat{y}$ via existing self-training methods (_e.g_., DeepCluster [6]). For
the detailed implementation, please refer to the supplementary.

Data: $\\{x^{\mathcal{S}}_{i},y^{\mathcal{S}}_{i}\\}_{i=1}^{N^{\mathcal{S}}}$,
$\\{x^{\mathcal{T}}_{i}\\}_{i=1}^{N^{\mathcal{T}}}$, population size $K$

Result: A list of optimal architectures and corresponding network weights for
the DA task from $\mathcal{S}$ to $\mathcal{T}$

1 Seed Initialization: sample K seeds from the search space $\mathcal{A}$ as
$\mathcal{G}_{seed}$, initialize their weights, and assign various seed
numbers for each seed;

2 $\mathcal{G}_{best}$ = [], t = 1;

3 while  _t $\leq$ T_ do

4 train $\mathcal{G}_{seed}$;

5 inference the performance of $\mathcal{G}_{seed}$;

6 crossover top seeds to get $\mathcal{G}_{crossover}$;

7 mutate the bottom seeds to get $\mathcal{G}_{mutate}$;

8 record mature seeds in $\mathcal{G}_{crossover}$ with $\mathcal{G}_{best}$;

9 pop poor seeds from $\mathcal{G}_{mutate}$;

10

11 $\mathcal{G}_{seed}$ = $\mathcal{G}_{crossover}$ \+ $\mathcal{G}_{mutate}$;

12 if  _$|\mathcal{G}_{seed}| <$ K_ then

13 initialize another $(K-|\mathcal{G}_{seed}|)$ seeds $\mathcal{G}_{rand}$;

14 $\mathcal{G}_{seed}$ = $\mathcal{G}_{seed}$ \+ $\mathcal{G}_{rand}$;

15

16 end if

17

18 t += 1;

19

20 end while

21return $\mathcal{G}_{best}$;

Algorithm 1 EvoADA

#### Overall Search Algorithm.

To make the architecture optimization effective, we integrate the search space
and the performance evaluation with an evolutionary algorithm [1] and propose
our EvoADA (elaborated in Algorithm 1):

  * •

Sample Seed. We sample $K$ possible attention configurations of $\alpha$ as
initial seeds, initialize weights of the backbone on ImageNet, randomly
initialize the weights of introduced attention modules, and assign each seed
with different random seed numbers (_e.g_., random(seed)) to reduce
uncertainty in training procedure.

  * •

Inference.With initialized seeds, we then run several training epochs in each
population in a parallel way, update their network weights, and evaluate their
UDA performance $\mathcal{L}^{PE}_{\mathcal{T}}$ in the target domain.

  * •

Crossover and Mutation. We conduct crossover to get even better performance in
the next generation. On those poor ones, we perform two mutation strategies to
explore for better seeds: 1) drop the seed and initialize another one
randomly; 2) change $\alpha$ by introducing another attention module or
shifting to different layers.

  * •

Update and Early Stop. To promote training efficiency and mitigate the discord
between the estimated performance and the final UDA performance, we adopt
several early-stopping criteria: i) when the accuracy in source domain is
higher than $tr_{acc}$ (_e.g_., $0.95$), it generally indicates the model may
suffer from negative transfer; ii) when the seed finishes $T$ evolution
iterations; iii) when pseudo-label accuracy in target domain keeps being poor
for over $T_{d}$ (_e.g_., $5$ in our implementation) iterations.

We end up with several populations that contain optimal attention
configurations. To report the final performance, we re-train the optimal
architectures on the two domains from scratch with one certain domain
adaptation approaches. It should be noticed that we can also apply other
architecture search algorithms, such as neural network-based reinforcement
learning NAS [57]. Thanks to the flexibility of evolution-based NAS scheme,
the proposed EvoADA can be easily applied on arbitrary domain adaptation
methods and is compatible with two typical training modes of existing UDA
methods: 1) single-stage mode trains on two domains simultaneously (_e.g_.,
[32, 47]); 2) two-stage mode trains first in the source domain and then in the
target domain (_e.g_., [27, 17]).

#### Differences from Concurrent Methods.

Concurrently, Li _et al_. [26] and Robbiano _et al_. [40] also propose to seek
for better transferable network architectures. The differences between our
EvoADA and them are: 1) on the design of search space: AdaptNAS [26] adopted
the search space of NASNet [57] that includes basic operations in CNNs
(_e.g_., different pooling or convolution operations) and seeks for optimal
structures in a cell perspective, ABAS [40] only changes the structure of the
auxiliary branch. In EvoADA, we design a new space to produce diverse
attention configurations and apply different modules on various intermediate
layers of the backbone network, which is a more generalized manner; 2) on the
architecture search process: AdaptNAS adopts a gradient-based differentiable
scheme [31], which might result in sub-optimal solutions; ABAS leverages the
BOHB [14], a Bayesian-based hyper-parameter optimization method, which is not
suitable for a high-dimensional optimization problem. We adopt an Evolution
based NAS framework [1], which is a more flexible and stable test-bed for the
propose of implementation. Experiments in Section 4 demonstrate the
effectiveness and versatility of EvoADA in various UDA scenarios.

##  4 Experiments

###  4.1 Setup

#### Implementation details.

To check the effectiveness and versatility of our NAS algorithm, we experiment
on $5$ scenarios: closed-set UDA, PDA, ODA, UDA in fine-grained classification
(FGDA), and UDA in person re-ID. Without loss of generality, we select $3$
state-of-the-art methods as baselines: SHOT [27] for UDA, PDA, and ODA; PAN
[47] for FGDA; and MMT [17] for UDA in person re-ID. For fair comparisons, i)
we use the same backbone, _i.e_., ResNet-50 [20], which is prevailing in
domain adaptation literature [32, 12, 47, 17]; 2) in PDA and ODA, we follow
the same data pipeline as [4, 5, 30, 27]; 3) in FGDA, we use the data pipeline
of PAN [47]; 4) to reduce the uncertainty from random seeds, we train the
searched architectures with baseline methods three times using different
random seeds and report the average results. On these baselines, we adopt our
EvoADA to investigate whether the searched architectures help boost
classification performance on the target domain. Experimental results also
verify the versatility of our method in various domain adaptation tasks.

To train the network weights $\theta$, we use the same settings (including
data augmentation, learning-rate schedule, batch-size, etc.) as the
aforementioned UDA baseline methods. EvoADA run $T=100$ epochs and $K=20$
different seeds evolve. We implement the proposed EvoADA with pytorch platform
[35]. We adopt $8$ NVIDIA Tesla V-100 GPUs and it takes approximately $20$
hours to finish the search procedure on one UDA task on average.

#### Datasets.

We experiment on multiple benchmarks:

Benchmark I: Office-Home & Office-31. Office-Home [45] is one challenging
medium-sized dataset. It contains $12$ adaptation tasks from $4$ distinct
domains: Artistic (Ar), Clip Art (Cl), Product (Pr), and Real-World (Rw).
Office31 [41] is a popular small-scale domain adaptation benchmark with
$4,110$ images and $31$ classes. It consists of $6$ cross-domain tasks from
$3$ distinct domains: Amazon (A), Webcam (W), and DSLR (D). Follow the
practice, we report classification accuracy on each adaptation task.

Benchmark II: FGDA. CUB-200-2011 [46] and CUB-200-Paintings [47] are datasets
for fine-grained UDA. CUB-200-2011 [46] is a fine-grained visual
categorization dataset with $12$K bird images in $200$ species.
CUB-200-Paintings is a dataset of $3$K bird paintings collected by Wang  _et
al_. [47] and its class lists are identical to CUB-200-2011. We follow the
same data pipeline as PAN [47] and report classification accuracy on the two
tasks.

Benchmark III: UDA in person Re-ID. Duke [39] and Market1501 [56] are two
widely-used person re-ID datasets. Market-1501 [56] consists of $32$K labelled
images of $1,501$ identities shot from $6$ cameras. $13$K images of $751$
identities are used for training and $19.7$ images of $750$ identities are
used for inference. Duke [39] contains $16.5$K photos of $702$ identities for
training, and photos out of additional $702$ identities for testing. We follow
the same pipeline on these benchmarks as Ge  _et al_. [17] and report mean
average precision (mAP) to evaluate the performance.

Table 2: Accuracy ($\%$) on Office-Home for UDA, PDA, and ODA methods (ResNet-50). Closed-set UDA |  Ar$\to$Cl |  Ar$\to$Pr |  Ar$\to$Rw |  Cl$\to$Ar |  Cl$\to$Pr |  Cl$\to$Rw |  Pr$\to$Ar |  Pr$\to$Cl |  Pr$\to$Rw |  Rw$\to$Ar |  Rw$\to$Cl |  Rw$\to$Pr | AVG
---|---|---|---|---|---|---|---|---|---|---|---|---|---
ResNet-50 [20] | 34.9 | 50.0 | 58.0 | 37.4 | 41.9 | 46.2 | 38.5 | 31.2 | 60.4 | 53.9 | 41.2 | 59.9 | 46.1
DANN [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
JAN [33] | 45.9 | 61.2 | 68.9 | 50.4 | 59.7 | 61.0 | 45.8 | 43.4 | 70.3 | 63.9 | 52.4 | 76.8 | 58.3
CDAN [32] | 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
ABAS [40] | 51.5 | 71.7 | 75.5 | 59.8 | 69.4 | 69.5 | 59.8 | 47.1 | 77.7 | 70.6 | 55.2 | 80.2 | 65.7
TADA [50] | 53.1 | 72.3 | 77.2 | 59.1 | 71.2 | 72.1 | 59.7 | 53.1 | 78.4 | 72.4 | 60.0 | 82.9 | 67.6
CADA-A [24] | 56.9 | 75.4 | 80.2 | 61.7 | 74.6 | 74.9 | 62.9 | 54.4 | 80.9 | 74.3 | 61.1 | 84.4 | 70.1
DCAN [25] | 54.5 | 75.7 | 81.2 | 67.4 | 74.0 | 76.3 | 67.4 | 52.7 | 80.6 | 74.1 | 59.1 | 83.5 | 70.5
SHOT [27] | 56.9 | 78.1 | 81.0 | 67.9 | 78.4 | 78.1 | 67.0 | 54.6 | 81.8 | 73.4 | 58.1 | 84.5 | 71.6
SHOT+Ours | 60.0 | 78.0 | 83.5 | 74.0 | 77.9 | 79.8 | 71.2 | 56.3 | 82.8 | 77.5 | 59.0 | 86.2 | 73.9
Partial-set UDA |  Ar$\to$Cl |  Ar$\to$Pr |  Ar$\to$Rw |  Cl$\to$Ar |  Cl$\to$Pr |  Cl$\to$Rw |  Pr$\to$Ar |  Pr$\to$Cl |  Pr$\to$Rw |  Rw$\to$Ar |  Rw$\to$Cl |  Rw$\to$Pr | AVG
ResNet-50 [20] | 46.3 | 67.5 | 75.9 | 59.1 | 59.9 | 62.7 | 58.2 | 41.8 | 74.9 | 67.4 | 48.2 | 74.2 | 61.3
DANN [15] | 35.5 | 48.2 | 51.6 | 35.2 | 35.4 | 41.4 | 34.8 | 31.7 | 46.2 | 47.5 | 34.7 | 49.0 | 40.9
SAN [4] | 44.4 | 68.7 | 74.6 | 67.5 | 65.0 | 77.8 | 59.8 | 44.7 | 80.1 | 72.2 | 50.2 | 78.7 | 65.3
ETN [5] | 59.2 | 77.0 | 79.5 | 62.9 | 65.7 | 75.0 | 68.3 | 55.4 | 84.4 | 75.7 | 57.7 | 84.5 | 70.5
SAFN [53] | 58.9 | 76.3 | 81.4 | 70.4 | 73.0 | 77.8 | 72.4 | 55.3 | 80.4 | 75.8 | 60.4 | 79.9 | 71.8
BA3US [28] | 60.6 | 83.2 | 88.4 | 71.8 | 72.8 | 83.4 | 75.5 | 61.6 | 86.5 | 79.3 | 62.8 | 86.1 | 76.0
SHOT [27] | 62.8 | 84.2 | 92.3 | 75.1 | 76.3 | 86.4 | 78.5 | 62.3 | 89.6 | 80.9 | 63.8 | 87.1 | 78.3
SHOT+Ours | 66.5 | 84.7 | 89.8 | 80.3 | 80.9 | 86.3 | 83.3 | 64.1 | 90.1 | 85.5 | 61.4 | 89.9 | 80.2
Open-set UDA |  Ar$\to$Cl |  Ar$\to$Pr |  Ar$\to$Rw |  Cl$\to$Ar |  Cl$\to$Pr |  Cl$\to$Rw |  Pr$\to$Ar |  Pr$\to$Cl |  Pr$\to$Rw |  Rw$\to$Ar |  Rw$\to$Cl |  Rw$\to$Pr | AVG
ResNet-50 [20] | 53.4 | 69.3 | 78.7 | 61.4 | 61.8 | 71.0 | 64.0 | 52.7 | 74.9 | 70.0 | 51.9 | 74.1 | 65.3
DANN [15] | 54.6 | 69.5 | 80.2 | 61.9 | 63.5 | 71.7 | 63.3 | 49.7 | 74.2 | 71.3 | 51.9 | 72.9 | 65.4
OSBP [44] | 56.7 | 67.5 | 80.6 | 62.5 | 65.5 | 74.7 | 64.8 | 51.5 | 71.5 | 69.3 | 49.2 | 74.0 | 65.7
STA [30] | 58.1 | 71.6 | 85.0 | 63.4 | 69.3 | 75.8 | 65.2 | 53.1 | 80.8 | 74.9 | 54.4 | 81.9 | 69.5
ETN [5] | 58.2 | 79.9 | 85.5 | 67.7 | 70.9 | 79.6 | 66.2 | 54.8 | 81.2 | 76.8 | 60.7 | 81.7 | 71.9
SHOT [27] | 60.5 | 59.2 | 69.5 | 63.4 | 73.6 | 61.8 | 54.7 | 80.4 | 81.8 | 82.3 | 82.6 | 77.2 | 70.6
SHOT+Ours | 62.1 | 60.2 | 79.2 | 69.4 | 73.6 | 63.7 | 58.1 | 82.7 | 87.0 | 87.4 | 86.5 | 79.3 | 74.1
Table 3: Accuracy ($\%$) on Office-31 for UDA (ResNet-50). Method | A$\to$W | D$\to$W | W$\to$D | A$\to$D | D$\to$A | W$\to$A | AVG
---|---|---|---|---|---|---|---
ResNet-50 [20] | 68.4 | 96.7 | 99.3 | 68.9 | 62.5 | 60.7 | 76.1
DANN [15] | 82.0 | 96.9 | 99.1 | 79.7 | 68.2 | 67.4 | 82.2
JAN [33] | 86.0 | 96.7 | 99.7 | 85.1 | 69.2 | 70.7 | 84.6
MCD [43] | 88.6 | 98.5 | 100.0 | 92.2 | 69.5 | 69.7 | 86.5
CRST [58] | 89.4 | 98.9 | 100.0 | 88.7 | 72.6 | 70.9 | 86.8
CDAN [32] | 94.1 | 98.6 | 100.0 | 92.9 | 71.0 | 69.3 | 87.7
TADA [50] | 94.3 | 98.7 | 99.8 | 91.6 | 72.9 | 73.0 | 88.4
BSP [7] | 93.3 | 98.2 | 100.0 | 93.0 | 73.6 | 72.6 | 88.5
CADA-A [24] | 96.8 | 99.0 | 99.8 | 93.4 | 71.7 | 70.5 | 88.5
SHOT [27] | 90.9 | 98.8 | 99.9 | 93.1 | 74.5 | 74.8 | 88.7
SHOT+Ours | 94.0 | 97.9 | 100.0 | 94.2 | 74.6 | 74.9 | 89.3

#### Baselines.

We compare with multiple state-of-the-art approaches: DANN [15], JAN [33],
OSBP [44], CDAN [32], IBN-Net [34], MCD [43], SAN [4], TADA [50], BSP [7],
SAFN [53], STA [30], CADA-A [24], ETN [5], CRST [58], BA3US [28], DCAN [25],
MMT [17], PAN [47], SHOT [27], and ABAS [40]. Among them, TADA [50], CADA-A
[24], DCAN [25] are the competitive approaches of better attention module
design towards domain adaptation and ABAS [40] (one current work) also adopts
NAS to search optimal architectures for domain adaptation, which provide a
good counterpart to investigate the effect of network design in the topic of
domain adaptation.

###  4.2 Results on Office-Home & Office-31

Experiments on Office-Home benchmark in Table 2 include $3$ typical settings:
closed-set UDA, PDA, and ODA 111To compare with other ODA methods, we report
the OS values. Results of the baseline methods come from [27].. As we can
observe that, in term of average accuracy, the proposed NAS algorithm helps
SHOT achieve better performance: $+2.3\%$ on closed-set UDA tasks, $+1.9\%$ on
PDA tasks, and $+3.5\%$ on ODA tasks. We also notice that sometimes, optimal
performances can be obtained when only one GSoP [16] attention layer is put at
Layer3 for ResNet-50. These observations encourage advanced development of the
attention mechanism in domain adaptation problems.

Numerical results on Office-31 dataset are listed in Table 3. Again, the
proposed EvoADA generally helps SHOT promote its classification performance on
target domain. These results indicate the importance of optimal attention
configuration and the effectiveness of our EvoADA in typical domain adaptation
scenarios.

###  4.3 Results on FGDA and UDA in Person Re-ID

We also experiment on two additional cross-domain applications: FGDA tasks and
UDA tasks of person re-ID. Results are listed in Table 4. On FGDA: The
performance gains from the searched attention configurations are generally
large on both FGDA scenarios. In terms of average accuracy, our EvoADA helps
PAN achieve $4.1\%$ gains. Similar to the observations previously, we find
that the gains can be achieved by automatically introducing $2$ or $3$
attention modules at proper layers of the backbone network. On UDA in Person
Re-ID: For full comparisons, we experiment with different configurations of
MMT [17]: MMT-500 and MMT-700 means that in the MMT framework, $500$ and $700$
centroids are adopted when k-means clustering is used, and MMT-DBSCAN means
DBSCAN clustering is adopted for pseudo-labels. As listed in Table 4, the
architecture searched by our EvoADA generally outperforms the other two
competitive baselines, _i.e_., ResNet-50 [20] and IBN-Net-50 [34], over
different configurations of MMT method and two UDA person re-ID task
scenarios.

Together, we verify the effectiveness and versatility of the proposed NAS
scheme in searching for optimal attention configurations for various domain
adaptation scenarios.

Table 4: Accuracy ($\%$) on CUB-Paintings (ResNet-50) and mAP (%) Market-1501-Duke (ResNet-50 vs IBN-Net-50 vs ours). FGDA | CUB-200-2011$\to$ | CUB-200-Paintings | AVG
---|---|---|---
CUB-200-Paintings |  $\to$CUB-200-2011
ResNet-50 [20] | 47.9 | 36.6 | 42.3
DANN [15] | 57.5 | 43.0 | 50.3
JAN [33] | 62.4 | 40.4 | 51.4
MCD [43] | 63.4 | 43.6 | 53.5
CDAN [32] | 63.2 | 45.4 | 54.3
BSP [7] | 63.3 | 46.6 | 55.0
SAFN [53] | 61.4 | 48.9 | 55.2
PAN [47] | 67.4 | 50.9 | 59.2
PAN+Ours | 70.5 | 56.0 | 63.3
UDA in Person ReID | Market1501 | Duke$\to$ | AVG
$\to$Duke | Market-1501
MMT-500 [17] | 63.1 | 71.2 | 67.2
\+ IBN-Net-50 [34] | 65.7 | 76.5 | 71.1
\+ Ours | 69.6 | 79.9 | 74.8
MMT-700 [17] | 65.1 | 69.0 | 67.1
\+ IBN-Net-50 [34] | 68.7 | 74.5 | 71.6
\+ Ours | 71.0 | 78.5 | 74.8
MMT-DBSCAN [17] | 64.3 | 75.6 | 70.0
\+ IBN-Net-50 [34] | 68.8 | 80.5 | 74.7
\+ Ours | 71.4 | 84.3 | 77.9

###  4.4 Ablation Study & Insight Analysis

Table 5: Comparison of the proposed search space and two existing typical ones. The Experiments are conducted on the four closed-set UDA settings on Office-Home dataset. Settings |  NASNet [57] |  DARTS [31] |  ABAS [40] | Ours
---|---|---|---|---
Ar $\to$ Cl | 57.1 | 56.8 | 51.5 | 60.0
Cl $\to$ Pr | 78.1 | 77.3 | 69.4 | 77.9
Pr $\to$ Rw | 81.3 | 80.7 | 77.7 | 82.8
Rw $\to$ Ar | 73.0 | 74.6 | 70.6 | 77.5
AVG | 72.6 | 72.3 | 67.3 | 74.6

#### Comparison with Other Search Spaces.

To demonstrate the effectiveness of the proposed search space in the topic of
domain adaptation, we also compare with two typical search spaces in NAS
methods: the search space of NASNet [57] and that of DARTS [31]. Both of them
are based on basic operations in convolutional neural networks (_e.g_.,
dilated convolution, pooling, and skip connection). We randomly select $4$
close-set UDA settings from Office-Home dataset and alternate our search space
with the two to investigate how their performance in the context of domain
adaptation. For full comparison, we also report the results from ABAS [40]. As
listed in Table 5 the proposed attention-based search space does outperform
other existing alternatives and yields the best domain adaptation results.

#### Comparison with Random Search.

The search curves of our EvoADA and one random search algorithm are shown in
Figure 4. As we can observe that our EvoADA is more effective in optimizing
the attention configurations for domain adaptation settings. We find similar
observations on Office-Home benchmark with two additional baseline methods
(random search v.s. ours): CDAN [32] (66.4% v.s. 69.8%) and SHOT [27] (71.9%
v.s. 73.9%). Therefore, the results of random search demonstrate the necessity
of an effective NAS algorithm towards domain adaptation tasks.

Figure 4: The comparison of EvoADA and random search on the partial UDA task
Pr$\to$Rw on Office-Home dataset. The prevailing backbone, ResNet-50, is
denoted as the dashed horizontal bar.

#### Hyper-parameter Sensitivity.

We investigate the sensitivity to $3$ hyper-parameters, $tr_{acc}$, $T$,
$T_{d}$. Empirically, we observe that: When $t_{acc}=0.98$, the results go
worse; when $t_{acc}\in\\{0.9,0.93,0.95\\}$, the results are similar; when
$t_{acc}\in\\{0.8,0.85\\}$, the results become worse again. ii) When $T\geq
100$, the results are slightly better but the cost also arises. iii) When
$T_{d}>5$, the results are relatively worse; when $T_{d}\leq 5$, the results
are similar. Thus, our EvoADA is relatively robust to these hyper-parameters.

#### Effectiveness of Performance Estimation.

To further demonstrate the rationale of our performance estimation strategy,
we show the rank correlation, _i.e_., Spearman $\rho$, between our estimation
results and the final accuracy in the target domain. For comparison, we also
show the rank correlation between the accuracy in the source domain and that
in the target domain. The results are shown in Table 6. Obvious, the rank
correlation between the accuracy in the source domain and that in the target
domain is relatively low, due to the large domain shift between two domains.
The estimation results via our evaluation strategy, on the other hand, are
highly correlated with the accuracy in the target domain and are effective to
guide search procedures to seek optimal architectures for domain adaptation.

Table 6: Comparison of the rank correlation between the estimation results via the accuracy on source domain and that via our evaluation protocol. Criteria | Office-31 | Office-Home
---|---|---
Accuracy on Source Domain | 0.40 | 0.23
Our estimation protocol | 0.68 | 0.54

Figure 5: (a) Histogram of the accuracies for 500 random populations on the
FGDA task of CUB-200-Painting to CUB-200-2011. The dashed vertical line
indicates the result of ResNet-50. (b) Some seeds on the PDA task of Rw $\to$
Ar on Office-Home. The numbers indicate their corresponding accuracies on
target domain. Figure 6: (a) and (b): The curves of three backbone networks on
UDA tasks over person re-ID benchmarks. The x-axis is training epochs and the
y-axis is the accuracy ($\%$) on target domain. (c) and (d): The differences
between ResNet-50 and ours on fine-grained UDA tasks over CUB-Paintings. The
x-axis indicates training iterations. The y-axis indicates the training loss.

#### Good and Bad Case Analysis.

Finally, we take a closer look at the searched attention configurations.
Figure 5 displays the accuracies of $500$ randomly sampled populations on the
FGDA task of CUB-200-Painting $\to$ CUB-200-2011. The histogram verifies the
benefit from refining the attention configurations and the effectiveness of
the proposed attention configuration. For better understanding the searched
optimal architectures, we also visualize some attention configurations with
good and sub-optimal UDA results (Figure 5), and the training curves of the
optimal networks (Figure 6). Experiments indicate that Layer 3 and Layer 4
seem to be optimal positions to introduce attention modules, and we achieve
the gains in accuracy when only moderate amounts of parameters and #FLOPs are
introduced. All these numerical results can help and encourage researchers to
cast a new light on designing novel attention modules towards better domain
adaptation.

##  5 Conclusion

In this paper, we devise a novel and effective NAS algorithm for UDA problems.
We propose a more generalized way to apply the attention module for domain
adaptation: to automatically optimize the attention configuration for one
arbitrary UDA dataset. We propose a new search space with a set of attention
modules and their positions in the backbone network. To be consonant with UDA
settings, we propose a UDA-oriented estimation strategy: train the weights on
two domains and evaluate the attention configurations in the target domain
with a self-training pseudo-label strategy. We implement the EvoADA framework
based on an evolution-based NAS algorithm. Extensive experiments on multiple
cross-domain benchmarks and typical adaptation scenarios verify that our
scheme generally promotes popular domain adaptation methods.

For future work, we will investigate the transferability of various
architectures and study the topic in other scenarios, _e.g_., object detection
and semantic segmentation.

## References

  * [1] Thomas Back.  Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms.  Oxford university press, 1996.
  * [2] Gabriel Bender, Pieter-Jan Kindermans, Barret Zoph, Vijay Vasudevan, and Quoc Le.  Understanding and simplifying one-shot architecture search.  In ICML, 2018.
  * [3] Han Cai, Jiacheng Yang, Weinan Zhang, Song Han, and Yong Yu.  Path-level network transformation for efficient architecture search.  In ICML, 2018.
  * [4] Zhangjie Cao, Mingsheng Long, Jianmin Wang, and Michael I Jordan.  Partial transfer learning with selective adversarial networks.  In CVPR, 2018.
  * [5] Zhangjie Cao, Kaichao You, Mingsheng Long, Jianmin Wang, and Qiang Yang.  Learning to transfer examples for partial domain adaptation.  In CVPR, 2019.
  * [6] Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze.  Deep clustering for unsupervised learning of visual features.  In ECCV, 2018.
  * [7] Xinyang Chen, Sinan Wang, Mingsheng Long, and Jianmin Wang.  Transferability vs. discriminability: Batch spectral penalization for adversarial domain adaptation.  In ICML, 2019.
  * [8] Xin Chen, Lingxi Xie, Jun Wu, and Qi Tian.  Progressive differentiable architecture search: Bridging the depth gap between search and evaluation.  In ICCV, 2019.
  * [9] Yukang Chen, Tong Yang, Xiangyu Zhang, Gaofeng Meng, Xinyu Xiao, and Jian Sun.  Detnas: Backbone search for object detection.  In NeurIPS, 2019.
  * [10] Zhihong Chen, Taiping Yao, Kekai Sheng, Shouhong Ding, Ying Tai, Jilin Li, Feiyue Huang, and Xinyu Jin.  Generalized representation learning for mixture domain face anti-spoofing.  In AAAI, 2021.
  * [11] Shuhao Cui, Xuan Jin, Shuhui Wang, Yuan He, and Qingming Huang.  Heuristic domain adaptation.  In NeurIPS, 2020.
  * [12] 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.
  * [13] Thomas Elsken, Jan Hendrik Metzen, Frank Hutter, et al.  Neural architecture search: A survey.  JMLR, 2019.
  * [14] Stefan Falkner, Aaron Klein, and Frank Hutter.  Bohb: Robust and efficient hyperparameter optimization at scale.  In ICML, 2018.
  * [15] Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky.  Domain-adversarial training of neural networks.  In JMLR, 2016.
  * [16] Zilin Gao, Jiangtao Xie, Qilong Wang, and Peihua Li.  Global second-order pooling convolutional networks.  In CVPR, 2019.
  * [17] Yixiao Ge, Dapeng Chen, and Hongsheng Li.  Mutual mean-teaching: Pseudo label refinery for unsupervised domain adaptation on person re-identification.  In ICLR, 2020.
  * [18] Ryan Gomes, Andreas Krause, and Pietro Perona.  Discriminative clustering by regularized information maximization.  In NeurIPS, 2010.
  * [19] Zichao Guo, Xiangyu Zhang, Haoyuan Mu, Wen Heng, Zechun Liu, Yichen Wei, and Jian Sun.  Single path one-shot neural architecture search with uniform sampling.  In ECCV, 2020.
  * [20] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In CVPR, 2016.
  * [21] Jie Hu, Li Shen, and Gang Sun.  Squeeze-and-excitation networks.  In CVPR, 2018.
  * [22] Weihua Hu, Takeru Miyato, Seiya Tokui, Eiichi Matsumoto, and Masashi Sugiyama.  Learning discrete representations via information maximizing self-augmented training.  In ICML, 2017.
  * [23] Guoliang Kang, Lu Jiang, Yi Yang, and Alexander G Hauptmann.  Contrastive adaptation network for unsupervised domain adaptation.  In CVPR, 2019.
  * [24] Vinod Kumar Kurmi, Shanu Kumar, and Vinay P Namboodiri.  Attending to discriminative certainty for domain adaptation.  In CVPR, 2019.
  * [25] Shuang Li, Chi Harold Liu, Qiuxia Lin, Binhui Xie, Zhengming Ding, Gao Huang, and Jian Tang.  Domain conditioned adaptation network.  In AAAI, 2020.
  * [26] Yanxi Li, Zhaohui Yang, Yunhe Wang, and Chang Xu.  Adapting neural architectures between domains.  In NeurIPS, 2020.
  * [27] 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.
  * [28] Jian Liang, Yunbo Wang, Dapeng Hu, Ran He, and Jiashi Feng.  A balanced and uncertainty-aware approach for partial domain adaptation.  In ECCV, 2020.
  * [29] Chenxi Liu, Liang-Chieh Chen, Florian Schroff, Hartwig Adam, Wei Hua, Alan L Yuille, and Li Fei-Fei.  Auto-deeplab: Hierarchical neural architecture search for semantic image segmentation.  In CVPR, 2019.
  * [30] Hong Liu, Zhangjie Cao, Mingsheng Long, Jianmin Wang, and Qiang Yang.  Separate to adapt: Open set domain adaptation via progressive separation.  In CVPR, 2019.
  * [31] Hanxiao Liu, Karen Simonyan, and Yiming Yang.  Darts: Differentiable architecture search.  In ICLR, 2018.
  * [32] Mingsheng Long, Zhangjie Cao, Jianmin Wang, and Michael I Jordan.  Conditional adversarial domain adaptation.  In NeurIPS, 2018.
  * [33] Mingsheng Long, Han Zhu, Jianmin Wang, and Michael I Jordan.  Deep transfer learning with joint adaptation networks.  In ICML, 2017.
  * [34] Xingang Pan, Ping Luo, Jianping Shi, and Xiaoou Tang.  Two at once: Enhancing learning and generalization capacities via ibn-net.  In ECCV, 2018.
  * [35] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al.  Pytorch: An imperative style, high-performance deep learning library.  In NeurIPS, 2019.
  * [36] Ruijie Quan, Xuanyi Dong, Yu Wu, Linchao Zhu, and Yi Yang.  Auto-reid: Searching for a part-aware convnet for person re-identification.  In ICCV, 2019.
  * [37] Joaquin Quionero-Candela, Masashi Sugiyama, Anton Schwaighofer, and Neil D Lawrence.  Dataset shift in machine learning.  The MIT Press, 2009.
  * [38] Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le.  Regularized evolution for image classifier architecture search.  In AAAI, 2019.
  * [39] Ergys Ristani, Francesco Solera, Roger Zou, Rita Cucchiara, and Carlo Tomasi.  Performance measures and a data set for multi-target, multi-camera tracking.  In ECCV, 2016.
  * [40] Luca Robbiano, Muhammad Rameez Ur Rahman, Fabio Galasso, Barbara Caputo, and Fabio Maria Carlucci.  Adversarial branch architecture search for unsupervised domain adaptation.  arXiv preprint arXiv:2102.06679, 2021.
  * [41] Kate Saenko, Brian Kulis, Mario Fritz, and Trevor Darrell.  Adapting visual category models to new domains.  In ECCV, 2010.
  * [42] Kuniaki Saito, Donghyun Kim, Stan Sclaroff, and Kate Saenko.  Universal domain adaptation through self supervision.  In NeurIPS, 2020.
  * [43] Kuniaki Saito, Kohei Watanabe, Yoshitaka Ushiku, and Tatsuya Harada.  Maximum classifier discrepancy for unsupervised domain adaptation.  In CVPR, 2018.
  * [44] Kuniaki Saito, Shohei Yamamoto, Yoshitaka Ushiku, and Tatsuya Harada.  Open set domain adaptation by backpropagation.  In ECCV, 2018.
  * [45] Hemanth Venkateswara, Jose Eusebio, Shayok Chakraborty, and Sethuraman Panchanathan.  Deep hashing network for unsupervised domain adaptation.  In CVPR, 2017.
  * [46] Catherine Wah, Steve Branson, Peter Welinder, Pietro Perona, and Serge Belongie.  The caltech-ucsd birds-200-2011 dataset.  In California Institute of Technology, 2011.
  * [47] Sinan Wang, Xinyang Chen, Yunbo Wang, Mingsheng Long, and Jianmin Wang.  Progressive adversarial networks for fine-grained domain adaptation.  In CVPR, 2020.
  * [48] Ximei Wang, Ying Jin, Mingsheng Long, Jianmin Wang, and Michael I Jordan.  Transferable normalization: Towards improving transferability of deep neural networks.  In NeurIPS, 2019.
  * [49] Xijun Wang, Meina Kan, Shiguang Shan, and Xilin Chen.  Fully learnable group convolution for acceleration of deep neural networks.  In CVPR, 2019.
  * [50] Ximei Wang, Liang Li, Weirui Ye, Mingsheng Long, and Jianmin Wang.  Transferable attention for domain adaptation.  In AAAI, 2019.
  * [51] Ze Wang, Xiuyuan Cheng, Guillermo Sapiro, and Qiang Qiu.  A dictionary approach to domain-invariant learning in deep networks.  In NeurIPS, 2020.
  * [52] Sanghyun Woo, Jongchan Park, Joon-Young Lee, and In So Kweon.  Cbam: Convolutional block attention module.  In ECCV, 2018.
  * [53] Ruijia Xu, Guanbin Li, Jihan Yang, and Liang Lin.  Larger norm more transferable: An adaptive feature norm approach for unsupervised domain adaptation.  In ICCV, 2019.
  * [54] Jason Yosinski, Jeff Clune, Yoshua Bengio, and Hod Lipson.  How transferable are features in deep neural networks?  In NeurIPS, 2014.
  * [55] Kaichao You, Mingsheng Long, Zhangjie Cao, Jianmin Wang, and Michael I Jordan.  Universal domain adaptation.  In CVPR, 2019.
  * [56] Liang Zheng, Liyue Shen, Lu Tian, Shengjin Wang, Jingdong Wang, and Qi Tian.  Scalable person re-identification: A benchmark.  In ICCV, 2015.
  * [57] Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc V Le.  Learning transferable architectures for scalable image recognition.  In CVPR, 2018.
  * [58] Yang Zou, Zhiding Yu, Xiaofeng Liu, BVK Kumar, and Jinsong Wang.  Confidence regularized self-training.  In ICCV, 2019.


# A Note on the Modeling Power of Different Graph Types

Josephine Thomasa,1,, Alice Moallemy-Oureha,1, Silvia Beddar-Wiesinga,1,
Rüdiger Nathera,1
aGAIN - Graphs in Artificial Intelligence and Neural Networks,
Faculty of Computer Science and Electrical Engineering,
University of Kassel, Wilhelmshöher Allee 71-73, 34121 Kassel, Germany
Email addresses: {jthomas, amoallemy, s.beddarwiesing<EMAIL_ADDRESS>

1Contributed equally
Corresponding Author

###### Abstract

Graphs can have different properties that lead to several graph types and may
allow for a varying representation of diverse information. In order to clarify
the modeling power of graphs, we introduce a partial order on the most common
graph types based on an expressivity relation. The expressivity relation
quantifies how many properties a graph type can encode compared to another
type. Additionally, we show that all attributed graph types are equally
expressive and have the same modeling power.

_Keywords_ graph expressivity $\And$ graph representation $\And$ information
encoding

##  1 Introduction

Let $g=(\mathcal{V},\mathcal{E})$ be a simple graph. The attributed version
$g^{\prime}=(\mathcal{V},\mathcal{E},\alpha,\omega)$ with attribute mappings
$\alpha:\mathcal{V}\rightarrow\mathcal{A}$ and
$\omega:\mathcal{E}\rightarrow\mathcal{B}$ into attribute spaces
$\mathcal{A},\mathcal{B}$ may intuitively express more information than the
unattributed graph. However, there are several different graph types, for
example, heterogeneous graphs, multigraphs, hypergraphs, directed or
undirected graphs, and the question arises: which graph type can express how
much information?

Irrespective of the graph type, two graphs
$g_{1}=(\mathcal{V}_{1},\mathcal{E}_{1}),g_{2}=(\mathcal{V}_{2},\mathcal{E}_{2})$
were compared in standard literature by checking if they are structurally
isomorphic [Grohe, Martin and Schweitzer, Pascal(2020)], i.e., finding
bijections
$f_{1}:\mathcal{V}_{1}\rightarrow\mathcal{V}_{2},f_{2}:\mathcal{E}_{1}\rightarrow\mathcal{E}_{2}$
between their node and edge sets. For the attributed case, the equality of two
graphs requires additional bijections between the attribute sets of nodes and
edges, respectively. In this note, however, two graphs are not distinguished
by their structure, but the modeling power of different graph types are
analyzed, i.e., the number of graph properties that can be encoded by sets of
graphs that differ in their structure by definition. We call the relation
graph type expressivity and define it as follows.

######  Definition 1.1 (Graph Type Expressivity).

A graph type $\mathcal{G}_{2}$ is at least as expressive as a graph type
$\mathcal{G}_{1}$, if and only if $\mathcal{G}_{2}$ encodes at least as many
graph properties as $\mathcal{G}_{1}$ denoted as
$\mathcal{G}_{1}\preccurlyeq\mathcal{G}_{2}$. In case both types encode the
same graph properties, i.e.,
$\mathcal{G}_{1}\preccurlyeq\mathcal{G}_{2}\wedge\mathcal{G}_{2}\preccurlyeq\mathcal{G}_{1}$,
it is denoted as $\mathcal{G}_{1}\approx\mathcal{G}_{2}$.

The fact that the graph type expressivity induces a partial order leads to the
following theorems for unattributed graphs 1.2, partially attributed graphs
1.3 and attributed graphs 1.4.

######  Theorem 1.2.

Let $\mathcal{G}_{h},\mathcal{G}_{\bar{h}},\mathcal{G}_{d}$ and
$\mathcal{G}_{het}$ be the sets of hypergraphs, non-hypergraphs, directed and
heterogeneous graphs. Then it holds
$\mathcal{G}_{h}\approx\mathcal{G}_{\bar{h}}$, and
$\mathcal{G}_{d}\preccurlyeq\mathcal{G}_{het}$.

######  Theorem 1.3.

Let $\mathcal{G}_{a},\mathcal{G}_{ia}$ be the sets of attributed and integer-
attributed graphs, and
$\mathcal{G}_{\bar{a}},\mathcal{G}_{\bar{a},het},\mathcal{G}_{\bar{a},m}$ be
the sets of unattributed graphs, unattributed heterogeneous and unattributed
multigraphs. Then it holds $\mathcal{G}_{\bar{a}}\preccurlyeq\mathcal{G}_{a},\
\mathcal{G}_{a}\approx\mathcal{G}_{\bar{a},het}$, and
$\mathcal{G}_{ia}\approx\mathcal{G}_{\bar{a},m}$.

######  Theorem 1.4.

All attributed graph types are equally expressive.

The paper is structured as follows. In sec. 2 the different graph types and
properties are defined. The proof of thm. 1.2 is given in sec. 3, the proof of
1.3 can be found in sec. 4 and thm. 1.4 is proven in sec. 5. For the
composition of graph types, a note is given in sec. 6 . Finally, the paper is
concluded in sec. 7.

##  2 Preliminaries

######  Definition 2.1 (Elementary Graphs).

  1. 1.

A directed graph is a tuple $G=(\mathcal{V},\mathcal{E})$ with
$\mathcal{V}\subset\mathbb{N}$ and
$\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$. The set of all directed
graphs is denoted here as $\mathcal{G}_{d}$.

  2. 2.

A (generalized) directed hypergraph is defined as
$G=(\mathcal{V},\mathcal{E})$ with nodes $\mathcal{V}\subset\mathbb{N}$ and
hyperedges
$\mathcal{E}\subseteq\\{(\mathsf{x},f_{i})_{i}\mid\mathsf{x}\subseteq\mathcal{V},\,f_{i}\mathbin{:}\mathsf{x}\rightarrow\mathbb{N}_{0}\\}$
including a numbering of the nodes in the hyperedge.111W.l.o.g. it can be
assumed that the numbering is gap-free, so if there exists a node
$u\in\mathsf{x}$ with ${f(u)=k>1}$ then there will also exist a node $v$ s.t.
$f(v)=k-1$. The set of all (generalized) directed hypergraphs is denoted as
$\mathcal{G}_{h}$.

######  Remark 2.2.

Def. 2.1[2] differs from the common definition of a directed hypergraph with
edges
${\mathcal{E}\subseteq\\{(\mathsf{x},\mathsf{y})\mid\mathsf{x},\mathsf{y}\subseteq\mathcal{V}\\}}$
[Bretto(2013)]. We obtained a more generalized definition by introducing a
numbering mapping for each hyperedge that indicates an ordering of the nodes
in a hyperedge. On a generalized hyperedge we defined the ordering by
equipping the node set $\mathsf{x}$ with a function
$f:\mathsf{x}\rightarrow\mathbb{N}$ s.t. for ${u,v\in\mathsf{x}:u\leq
v\Leftrightarrow f(u)\leq f(v)}$. With this, the common notion of a directed
hyperedge $(\mathsf{x},\mathsf{y})$ can be depicted by mapping the nodes in
$\mathsf{x}$ to $1$ and the nodes in $\mathsf{y}$ to $2$.

$1_{\alpha}$$2_{\alpha}$$2_{\alpha}$$3_{\alpha}$$4_{\alpha}$$4_{\alpha}$adbcfeabfced$2_{\beta}$g$\alpha$$\beta$$1_{\beta}$g$\beta$$\alpha$
Figure 1: Left: Two generalized hyperedges with numbering. Right: The same
hyperedges with arrows indicating the ordering of the nodes.

######  Definition 2.3 (Graph Properties).

An elementary graph $G=(\mathcal{V},\mathcal{E})$ is called

  1. 1.

undirected if the directions of the edges are irrelevant, i.e.,

    1. (a)

for directed graphs: if $(u,v)\in\mathcal{E}$ whenever $(v,u)\in\mathcal{E}$
for $u,v\in\mathcal{V}$.

    2. (b)

for directed hypergraphs: if $f_{i}\mathbin{:}\mathsf{x}\rightarrow 0$ for all
$(\mathsf{x},f_{i})_{i}\in\mathcal{E}$. Abbreviated by
$\mathcal{E}\subseteq\\{\mathsf{x}\mid\mathsf{x}\subseteq\mathcal{V}\\}$.

In what follows $\mathcal{G}_{u}$ is the set of all undirected graphs.

  2. 2.

multigraph if it is a multi-edge graph, i.e., the edges $\mathcal{E}$ are
defined as an (ordered) multiset, denoted by $\\{\\!|\cdot|\\!\\}$, a multi-
node graph, i.e., the node set $\mathcal{V}$ is an (ordered) multiset, or
both. All multigraphs are written as the set $\mathcal{G}_{m}$.

  3. 3.

heterogeneous if the nodes or edges can have different types (node- or edge-
heterogeneous). I.e., the node set is determined by
$\mathcal{V}\subseteq\mathbb{N}\times\mathcal{S}$ with a node type set
$\mathcal{S}$ and the edges are extended by the edge type set $\mathcal{R}$.
The set of all heterogeneous graphs is denoted as $\mathcal{G}_{het}$.

  4. 4.

attributed if the nodes $\mathcal{V}$ or edges $\mathcal{E}$ are equipped with
node- or edge attributes. These attributes are given by a node and edge
attribute function, respectively, i.e.,
$\alpha:\mathcal{V}\rightarrow\mathcal{A}$ and
$\omega:\mathcal{E}\rightarrow\mathcal{W}$, where $\mathcal{A}$ and
$\mathcal{W}$ are arbitrary attribute sets. The set of all attributed graphs
is denoted as $\mathcal{G}_{a}$.

  5. 5.

dynamic if the graph structure or the graph properties are time dependent. In
the following, the notion $G_{i}=(\mathcal{V}_{i},\mathcal{E}_{i}),\;t_{i}\in
T$ is used, where $T$ is a finite set of (not necessarily equidistant)
timestamps to emphasize the time-dependence and therefore the dynamics.

In the literature there are many graph types composed from the above
definitions of graph properties, but the resulting graph types are not always
named accordingly. Therefore, in the following important composed graphs are
listed and named according to the definitions from above.

######  Example 2.4 (Composed Static Graphs).

  1. 1.

Knowledge graphs are defined in several ways. In [Wang et al.(2021)Wang, Qiu,
and Wang], they are defined as heterogeneous directed graphs, while in [Zhu et
al.(2020)Zhu, Wei, Sisman, Zheng, Faloutsos, Dong, and Han] knowledge graphs
are heterogeneous graphs. But some definitions that do not define knowledge
graphs as a graph consisting of a combination from the aforementioned types,
see [Ehrlinger and Wöß(2016)].

  2. 2.

A multi-relational graph [Hamilton(2020)] is an edge-heterogeneous but node-
homo- geneous graph.

  3. 3.

A content-associated heterogeneous graph is a heterogeneous graph with node
attributes that correspond to heterogeneous data such as, e.g., attributes,
text or images [Zhang et al.(2019)Zhang, Song, Huang, Swami, and Chawla].

  4. 4.

A multiplex graph/multi-channel graph corresponds to an edge-heterogeneous
graph with self-loops [Hamilton(2020)]. Here, we have $k$ layers, where each
layer consists of the same node set $\mathcal{V}$, but different edge sets
$\mathcal{E}^{(k)}$. Additionally, inter-layer edges $\tilde{\mathcal{E}}$
exist between the same nodes across different layers.

  5. 5.

A multiscale graph is a multiplex graph with edges between different nodes of
differing layers [Li et al.(2020)Li, Chen, Zhao, Zhang, Wang, and Tian].

  6. 6.

A spatio-temporal graph is a multiplex graph where edges per each layer are
interpreted as spatial edges and the inter-layer edges indicate temporal steps
between a layer at time step $t$ and $t+1$. They are called temporal edges
[Kapoor et al.(2020)Kapoor, Ben, Liu, Perozzi, Barnes, Blais, and O’Banion].

######  Remark 2.5.

Graphs can have further additional semantic properties such as connectedness,
(a-)cyclicity, scale-freeness, etc. However, these are independent from the
basic graph type. Since we consider graphs syntactically in this article, we
do not go into further graph properties that result from interpretations of
the given graph structure. For further readings see [Korte et al.(2012)Korte,
Vygen, and Randow].

##  3 Modeling Power of Unattributed Graphs

######  Lemma 3.1.

The set of directed hypergraphs and non-hypergraphs are equally expressive,
i.e., $\mathcal{G}_{h}\approx\mathcal{G}_{\overline{h}}$.

###### Proof.

Let $g\in\mathcal{G}_{h}$, $g^{\prime}\in\mathcal{G}_{\bar{h}}$ be an
arbitrary hyper- and non-hypergraph of the forms $g=(\mathcal{V},\mathcal{E})$
with
$\mathcal{V}\subset\mathbb{N},\;{\mathcal{E}\subseteq\\{(\mathsf{x},f_{i})_{i}\mid\mathsf{x}\subseteq\mathcal{V},\,f_{i}\mathbin{:}\mathsf{x}\rightarrow\mathbb{N}_{0}\\}}$
and $g^{\prime}=(\mathcal{V}^{\prime},\mathcal{E}^{\prime})$ with
$\mathcal{V}^{\prime}\subset\mathbb{N}$ and
$\mathcal{E}^{\prime}\subseteq\mathcal{V}^{\prime}\times\mathcal{V}^{\prime}.$

  1. $\preccurlyeq$:

Let
$f\mathbin{:}\mathcal{G}_{h}\rightarrow\text{Im}(f)\subseteq\mathcal{G}_{\bar{h}}$
be a mapping with $f(g)=g^{\prime}=(\mathcal{V},\mathcal{E}^{\prime})$ and
$\mathcal{E}^{\prime}=\mathcal{E}^{\star}\cup\mathcal{E}^{\star\star}$, with

    1. (a)

the translation of undirected hyperedges to fully connected subgraphs
(cliques):
${\mathcal{E}^{\star}=\\{(u,v)\mid\exists(\mathsf{x},f_{i})_{i}\in\mathcal{E}\mathbin{:}f_{i}(w)=0\,\forall
w\in\mathsf{x}\wedge u,v\in\mathsf{x}\\}}$ as illustrated in fig. 2 a),

    2. (b)

the translation of directed hyperedges to chains of fully connected bipartite
subgraphs (bicliques):
${\mathcal{E}^{\star\star}=\\{(u,v)\mid\exists(\mathsf{x},f_{i})_{i}\in\mathcal{E}\mathbin{:}u,v\in\mathsf{x}\wedge
f_{i}(v)=f_{i}(u)+1\\}}$ as illustrated in fig. 2 b).

Then $f$ is bijective, while the injectivity is insured by the ordering
functions $f_{i}$ of the corresponding edges.

  2. $\succcurlyeq$:

This direction is straight forward since every non-hypergraph is per
definition a hypergraph.

Figure 2: embedding of hyperedges to directed edges: a) undirected hyperedge,
b) directed hyperedge.

∎

######  Lemma 3.2.

Let $\mathcal{G}_{d}$ be the set of directed graphs and $\mathcal{G}_{het}$
the set of undirected heterogeneous graphs. Then
$\mathcal{G}_{d}\preccurlyeq\mathcal{G}_{het}$.

###### Proof.

Let $g:=(\mathcal{V},\mathcal{E})\in\mathcal{G}_{d}$ be a directed graph with
$\mathcal{V}\subset\mathbb{N},\
\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$. Then the function
${f:\mathcal{G}_{d}\rightarrow\text{Im}(f)\subseteq\mathcal{G}_{het}}$ defined
by $f(g)=g^{\prime}:=(\mathcal{V},\mathcal{E}^{\prime})$ with
$\mathcal{E}^{\prime}=\\{(u,v,0),(v,u,0)\mid(u,v)\in\mathcal{E}\\}\cup\\{(u,v,1),(v,u,1)\mid(v,u)\in\mathcal{E}\\}$
is a bijective embedding. ∎

From lem. 3.1 and lem. 3.2 follows directly thm. 1.2.

##  4 Modeling Power between Attributed and Unattributed Graphs

######  Lemma 4.1.

Let $G_{a}$ be the sets of attributed graphs and $\mathcal{G}_{\bar{a}}$ the
set of unattributed graphs. Then it holds
$\mathcal{G}_{\bar{a}}\preccurlyeq\mathcal{G}_{a}$.

###### Proof.

Let $g\in\mathcal{G}_{\bar{a}}$ be an arbitrary graph of the form
$g=(\mathcal{V},\mathcal{E})\text{ with
}\mathcal{V}\subset\mathbb{N},\;\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$.
Then the function
$f\mathbin{:}\mathcal{G}_{\bar{a}}\longrightarrow\mathcal{G}_{a}$, defined by

$\displaystyle(\mathcal{V},\mathcal{E})$
$\displaystyle\longmapsto(\mathcal{V},\mathcal{E},\alpha,\omega),\;\text{ with
}\;\alpha\mathbin{:}\mathcal{V}\longrightarrow\mathcal{A}\cup\\{\sigma\\},\;\omega\mathbin{:}\mathcal{E}\longrightarrow\mathcal{B}\cup\\{\sigma\\},$
$\displaystyle\alpha(v)$
$\displaystyle=\sigma\;\forall\;v\in\mathcal{V}\;\text{ and
}\;\omega(e)=\sigma\;\forall\;e\in\mathcal{E}.$

where $\sigma$ is the blank symbol, is a bijective embedding from the
unattributed graph into the attributed graph type. ∎

The inverse direction of lem. 4.1 must not necessarily hold. The main problem
lies in encoding the node and edge attributes into the graphs structure.
However, for some special cases we show in the following (cf. lem. 4.2, 4.3),
that restricted versions of the inverse direction hold. These could be seen as
indicators for the reverse direction hypothesis of lem. 4.1.

######  Lemma 4.2.

An attributed graph can be embedded into an unattributed heterogeneous graph
type, i.e., it holds $\mathcal{G}_{a}\preccurlyeq\mathcal{G}_{\bar{a},het}$.

###### Proof.

Let $g\in\mathcal{G}_{a}$ be an arbitrary graph with
$g=(\mathcal{V},\mathcal{E},\alpha,\omega)$, $\mathcal{V}\subset\mathbb{N},\
\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V},\
\alpha\mathbin{:}\mathcal{V}\rightarrow\mathcal{C}$ and
$\omega\mathbin{:}\mathcal{E}\rightarrow\mathcal{C}$. Then
${f\mathbin{:}\mathcal{G}_{a}\rightarrow\text{Im}(f)\subseteq\mathcal{G}_{\bar{a},het}}$
with $f(g)=g^{\prime}:=(\mathcal{V}^{\prime},\mathcal{E}^{\prime})$, where
$\mathcal{V}^{\prime}=\mathcal{V}\times\alpha(\mathcal{V})$
$\mathcal{E}^{\prime}=\mathcal{E}\times\beta(\mathcal{E})$ is bijective. The
injectivity follows from the usage of a node or edge type for each attribute
respectively. ∎

######  Lemma 4.3.

Every unattributed multigraph type is at least as expressive as an integer-
attributed graph type. Formally, $G_{ia}\preccurlyeq G_{\bar{a},m}$.

###### Proof.

Let $g\in\mathcal{G}_{ia}$ be an arbitrary integer-attributed graph with
$g=(\mathcal{V},\mathcal{E},\alpha,\omega)$, $\mathcal{V}\subset\mathbb{N},\
{\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V},}\
{\alpha\mathbin{:}\mathcal{V}\rightarrow\mathbb{N}}$ and
$\omega\mathbin{:}\mathcal{E}\rightarrow\mathbb{N}$. Then the mapping
$f\mathbin{:}\mathcal{G}_{ia}\rightarrow\text{Im}(f)\subseteq\mathcal{G}_{\bar{a},m}$
defined as $f(g)=g^{\prime}=(\mathcal{V}^{\prime},\mathcal{E}^{\prime})$,
where

$\mathcal{V}^{\prime}=\bigcup\limits_{i\in[\alpha(v)]\;\mathbin{:}\;v\in\mathcal{V}}\\{\\!|v|\\!\\},\quad\mathcal{E}^{\prime}=\bigcup\limits_{i\in[\omega(e)]\;\mathbin{:}\;e\in\mathcal{E}}\\{\\!|e|\\!\\}.$

is a bijective embedding.∎

Lem. 4.1, 4.2 and 4.3, lead immediately to thm. 1.3.

######  Remark 4.4.

Lem. 3.1, 3.2, 4.1, 4.2 and 4.3 naturally hold in the fully attributed case,
where the additional attributes remain unchanged.

##  5 Universal Modeling Power of Attributed Graphs

Due to the proof of lem. 4.1 there exists an embedding function from each
unattributed graph to an attributed one, encoding the same information.
Therefore, it is assumed in everything that follows that the graph types in
consideration are attributed. Unless otherwise mentioned the notation is kept
simple and the attributedness of the graph types is not explicitly mentioned.
Additionally, for any two graphs
$(\mathcal{V},\mathcal{E},\alpha,\omega),(\mathcal{V}^{\prime},\mathcal{E}^{\prime},\alpha^{\prime},\omega^{\prime})$,
with node attribute sets $\mathcal{A},\mathcal{A}^{\prime}$ and edge attribute
sets $\mathcal{B},\mathcal{B}^{\prime}$, it can be assumed w.l.o.g. that it is
$\mathcal{A}=\mathcal{A}^{\prime}$ and $\mathcal{B}=\mathcal{B}^{\prime}$
222Otherwise, the attribute domains can be extended arbitrarily..
$\mathcal{C}$ will be used to refer to an extended attribute space to prevent
confusion.

######  Lemma 5.1.

Let $\mathcal{G}_{d}$ be the sets of attributed directed graphs and
$\mathcal{G}_{\bar{d}}$ the set of attributed undirected graphs. Then it holds
$\mathcal{G}_{d}\approx\mathcal{G}_{\overline{d}}$.

###### Proof.

Let $g\in\mathcal{G}_{d}$ be an arbitrary directed graph of the form
$g=(\mathcal{V},\mathcal{E},\alpha,\omega)\text{ with
}\mathcal{V}\subset\mathbb{N},$
$\;{\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}},$
$\;{\alpha\mathbin{:}\mathcal{V}\rightarrow\mathcal{C}},\;{\omega\mathbin{:}\mathcal{E}\rightarrow\mathcal{C}.}$

  1. $\preccurlyeq$:

Let
$f\mathbin{:}\mathcal{G}_{d}\rightarrow\text{Im}(f)\subseteq\mathcal{G}_{\bar{d}}$
be a mapping defined by
$f(g)=g^{\prime}=(\mathcal{V}^{\prime},\mathcal{E}^{\prime},\alpha^{\prime},\omega^{\prime})$,
where

    1. (a)

$\mathcal{V}^{\prime}=\mathcal{V}$,
$\mathcal{E}^{\prime}=\\{\\{u,v\\}\mid(u,v)\vee(v,u)\in\mathcal{E}\\}$,
$\alpha^{\prime}(v)\mapsto\alpha(v)\ \forall v\in\mathcal{V}^{\prime}$ and

    2. (b)

$\omega^{\prime}(\\{u,v\\})\mapsto\begin{cases}\left(\omega((u,v)),1\right),&\text{if
}(u,v)\in\mathcal{E}\wedge(v,u)\notin\mathcal{E},\\\
\left(\omega((v,u)),-1\right),&\text{if
}(v,u)\in\mathcal{E}\wedge(u,v)\notin\mathcal{E},\\\
\bigl{(}\left(\omega((u,v)),1\right),\left(\omega((v,u)),-1\right)\bigr{)}&\text{if
}(u,v),(v,u)\in\mathcal{E}.\\\ \end{cases}$

Then $f$ is bijective.

  2. $\succcurlyeq$:

This direction is straight forward, since every undirected edge formally
corresponds to two directed edges.

∎

######  Lemma 5.2.

The set of attributed multigraphs and attributed non-multigraphs are equally
expressive, i.e., $\mathcal{G}_{m}\approx\mathcal{G}_{\bar{m}}$.

###### Proof.

Let $g\in\mathcal{G}_{m}$ be an arbitrary multigraph of the form
$g=(\mathcal{V},\mathcal{E},\alpha,\omega)$ with
$\mathcal{V}\subset\\{\\!|v\mid v\in\mathbb{N}|\\!\\},$
$\;{\mathcal{E}\subseteq\\{\\!|(u,v)\mid u,v\in\mathcal{V}|\\!\\},}\;$
${\alpha\mathbin{:}\mathcal{V}\rightarrow\mathcal{C},\;\omega\mathbin{:}\mathcal{E}\rightarrow\mathcal{C}}$.

  1. $\preccurlyeq$:

Let
$f\mathbin{:}\mathcal{G}_{m}\rightarrow\text{Im}(f)\subseteq\mathcal{G}_{\bar{m}}$
be a mapping with
$f(g)=g^{\prime}=(\mathcal{V}^{\prime},\mathcal{E}^{\prime},\alpha^{\prime},\omega^{\prime})$
and $\mathcal{V}^{\prime}=\\{v\mid v\in\mathcal{V}\\}$,
$\mathcal{E}^{\prime}=\\{e\mid e\in\mathcal{E}\\}$,
$\alpha^{\prime}(v)\mapsto(\alpha(v)\mid v\in\mathcal{V})$ and
$\omega^{\prime}(e)\mapsto(\omega(e)\mid e\in\mathcal{E})$. Since the
multisets are ordered the function is injective.

  2. $\succcurlyeq$:

This direction is straight forward since every set is a multiset.

∎

######  Lemma 5.3.

The set of attributed heterogeneous and attributed homogeneous graphs are
equally expressive, i.e.,
$\mathcal{G}_{het}\approx\mathcal{G}_{\overline{het}}$.

###### Proof.

Let $g\in\mathcal{G}_{het}$ be an arbitrary heterogeneous graph of the form
$g=(\mathcal{V},\mathcal{E},\alpha,\omega)$ with
${\mathcal{V}\subset\mathbb{N}\times\mathcal{S}},$
$\;{\mathcal{E}\subseteq\\{\mathcal{V},\mathcal{V}\\}\times\mathcal{R}},$
${\alpha\mathbin{:}\mathcal{V}\rightarrow\mathcal{C},}$
$\;\omega\mathbin{:}\mathcal{E}\rightarrow\mathcal{C}$.

  1. $\preccurlyeq$:

Let
$f\mathbin{:}\mathcal{G}_{het}\rightarrow\text{Im}(f)\subseteq\mathcal{G}_{\overline{het}}$
be a mapping with
$f(g)=g^{\prime}=(\mathcal{V}^{\prime},\mathcal{E}^{\prime},\alpha^{\prime},\omega^{\prime})$,
where

    1. (a)

$\mathcal{V}^{\prime}=\\{v\mid(v,s)\in\mathcal{V}\\}$,
$\mathcal{E}^{\prime}=\\{(u,v)\mid(u,v,r)\in\mathcal{E}\\}$,

    2. (b)

$\alpha^{\prime}(v)\mapsto(\alpha((v,s)),s\mid(v,s)\in\mathcal{V})\ \forall
v\in\mathcal{V}^{\prime}$, and
$\omega^{\prime}(e)\mapsto(\omega((e,r)),r\mid(e,r)\in\mathcal{E})\ \forall
e\in\mathcal{E}^{\prime}$.

The concatenation of the node and edge types to the attributes directly
constitutes the injectivity of the mapping.

  2. $\succcurlyeq$:

This direction is straight forward by introducing one node and one edge type
since every homogeneous graph is a heterogeneous graph with just one node and
edge type.

∎

######  Lemma 5.4.

The set of attributed dynamic and attributed static graphs are equally
expressive, i.e., ${\mathcal{G}_{dy}\approx\mathcal{G}_{\overline{dy}}}$.

###### Proof.

Let $G\in\mathcal{G}_{dy}$ be an arbitrary dynamic graph of the form
$G=(\mathcal{V}_{t},\mathcal{E}_{t},\alpha_{t},\omega_{t})_{t\in[T]}$ with
${\mathcal{V}_{t}\subset\mathbb{N}},$
$\;{\mathcal{E}_{t}\subseteq\mathcal{V}_{t}\times\mathcal{V}_{t},}$
${\alpha_{t}\mathbin{:}\mathcal{V}_{t}\rightarrow\mathcal{C},\;\omega_{t}\mathbin{:}\mathcal{E}_{t}\rightarrow\mathcal{C}\quad\forall
t\in[T]}$.

  1. $\preccurlyeq$:

Let
$f\mathbin{:}\mathcal{G}_{dy}\rightarrow\text{Im}(f)\subseteq\mathcal{G}_{\overline{dy}}$
be a mapping with
$f(G)=g^{\prime}=(\mathcal{V}^{\prime},\mathcal{E}^{\prime},\alpha^{\prime},\omega^{\prime})$,
where

    1. (a)

$\mathcal{V}^{\prime}=\bigcup\limits_{t\in[T]}\mathcal{V}_{t}$,
$\mathcal{E}^{\prime}=\bigcup\limits_{t\in[T]}\mathcal{E}_{t}$,

    2. (b)

$\alpha^{\prime}(v)\mapsto((\alpha_{t}(v),t)\mid v\in\mathcal{V}_{t})\ \forall
v\in\mathcal{V}^{\prime}$, and
$\omega^{\prime}(e)\mapsto((\omega_{t}(e),t)\mid e\in\mathcal{E}_{t})\ \forall
e\in\mathcal{E}^{\prime}$.

Despite the union of the node and edge sets, the function is injective due to
the ordering of the graph attributes in the static graph.

  2. $\succcurlyeq$:

This direction is straight forward by introducing one time stamp since every
static graph is dynamic with only one time stamp.

∎

### Proof of Theorem 1.4

All attributed graph types are equally expressive.

###### Proof.

With lem. 5.4 dynamic and static graph types are equally expressive. In all
other lemmata we did not distinguish between dynamic and static graphs.
Therefore, by ring closure these types are equally expressive to the
hypergraph type (cf. lem. 3.1), the multigraph type (cf. lem. 4.3), the
(un)directed type (cf. lem. 5.1), and the heterogeneous type (cf. lem. 5.3).

$\displaystyle\underset{dynamic}{\underbrace{\mathcal{G}_{h}\overset{lem.\leavevmode\nobreak\
\ref{eq:hyper}}{\approx}\mathcal{G}_{\overline{d}}\overset{lem.\leavevmode\nobreak\
\ref{lem_multigraph_unattrib}}{\approx}\mathcal{G}_{m}\overset{lem.\leavevmode\nobreak\
\ref{eq:directed}}{\approx}\mathcal{G}_{d}\overset{lem.\leavevmode\nobreak\
\ref{eq:heterogeneous}}{\approx}\mathcal{G}_{het}}}$ $\displaystyle\hskip
88.2037pt\overset{lem.\leavevmode\nobreak\ \ref{lem_dynamic_static}}{\approx}$
$\displaystyle\overset{static}{\overbrace{\mathcal{G}_{h}\overset{lem.\leavevmode\nobreak\
\ref{eq:hyper}}{\approx}\mathcal{G}_{\overline{d}}\overset{lem.\leavevmode\nobreak\
\ref{lem_multigraph_unattrib}}{\approx}\mathcal{G}_{m}\overset{lem.\leavevmode\nobreak\
\ref{eq:directed}}{\approx}\mathcal{G}_{d}\overset{lem.\leavevmode\nobreak\
\ref{eq:heterogeneous}}{\approx}\mathcal{G}_{het}}}.$

∎

##  6 Expressivity of Composed Graph Types

In sec. 3, 4, and 5 we investigated the expressivity relation between graph
types defined by a single graph property. However, as seen in def. 2.4,
composed graph types can also be related to each other by their expressivity
relation. In this case, a bijective embedding between multiple composed graphs
consists of the composition of the individual embeddings determined for single
structural properties from sec. 3, 4, and 5. The composed embedding is
illustrated in fig. 3.

Let $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ be two arbitrary (composed) graph
types and $p_{i}$ for all indices $i\in[1,\ldots,j]$ the structural graph
properties or a property describing an elementary graph from def. 2.1 and 2.3.
Here, $j$ is the number of properties that have to be changed to come from
$\mathcal{G}_{1}$ to $\mathcal{G}_{2}$. Further, let $t(g,p_{i})$ be the
embedding for adding or removing the property $p_{i}$ to or from a graph $g$.
Then, the following composition of single embeddings $t(g,p_{i})$ describes
one existent bijective embedding from graph $g\in\mathcal{G}_{1}$ into the
graph type $\mathcal{G}_{2}$, namely

$t(g,[p_{1},p_{2},\ldots,p_{j}])=t(g,p_{1})\circ t(g,p_{2})\circ\cdots\circ
t(g,p_{j})\in\mathcal{G}_{2}.$

${\mathcal{G}_{1}}$${\mathcal{G}_{1}^{1}}$${\mathcal{G}_{1}^{2}}$${\cdots}$${\mathcal{G}_{1}^{j-1}}$${\mathcal{G}_{2}}$$\scriptstyle{t(p_{1})}$$\scriptstyle{\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}t(g,[p_{1},p_{2},\ldots,p_{j}])}$$\scriptstyle{t(p_{2})}$$\scriptstyle{t(p_{3})}$$\scriptstyle{t(p_{j-1})}$$\scriptstyle{t(p_{j})}$
Figure 3: embeddings between composed graphs as composition of single
structural property embeddings.

Note that, having fixed the embedding functions for simple graph type
embeddings, the order within the composition of embeddings is not unique. I.e.
in particular, that the embedding from $\mathcal{G}_{1}$ to $\mathcal{G}_{2}$
is deterministic in the result but not in the process.

##  7 Conclusion

In order to clarify the modeling power of graphs, we evaluated the power to
encode different properties, i.e. the expressivity power, for common graph
types. First, we compared unattributed graph types w.r.t. their expressivity
power. We proved that hyper- and non-hypergraphs are equally expressive, i.e.,
$\mathcal{G}_{h}\approx\mathcal{G}_{\bar{h}}$ and that heterogeneous graphs
are at least as expressive as directed graph types, i.e.,
$\mathcal{G}_{d}\preccurlyeq\mathcal{G}_{het}$. For this purpose, we showed
the existence of bijective embeddings between the graph types. Next, in the
case of one attributed and one unattributed graph type, we could show that it
holds $\mathcal{G}_{\bar{a}}\preccurlyeq\mathcal{G}_{a}$ for unattributed and
attributed graphs. In contrast, for attributed and unattributed heterogeneous
graphs and integer-attributed and unattributed multigraphs, it is
$\mathcal{G}_{a}\approx\mathcal{G}_{\bar{a},het}$, and
${\mathcal{G}_{ia}\approx\mathcal{G}_{\bar{a},m}}$, respectively.
Subsequently, we proved that attributed graphs of any graph type could encode
any graph property leading to the equal expressivity power of attributed graph
types, cf. thm. 1.4. Finally, we noted the expressivity relation between
composed graphs resulting from the composition of existing embeddings between
the attributed and unattributed graph types having just one graph property.

## Acknowledgements

This work was supported by the Ministry of Education and Research Germany
(BMBF, grant number 01IS20047A). Further, we would like to thank Abdul Hannan,
Franz Götz-Hahn, Jan Schneegans and Bernhard Sick for review of the manuscript
and fruitful discussions.

## References

  * [Grohe, Martin and Schweitzer, Pascal(2020)] Grohe, Martin and Schweitzer, Pascal.  The Graph Isomorphism Problem.  _Communications of the ACM_ , 63(11):128–134, 2020.
  * [Bretto(2013)] Alain Bretto.  _Hypergraph Theory_.  Springer, 2013.
  * [Wang et al.(2021)Wang, Qiu, and Wang] Meihong Wang, Linling Qiu, and Xiaoli Wang.  A Survey on Knowledge Graph Embeddings for Link Prediction.  _Symmetry_ , 13(3), 2021.  doi:10.3390/sym13030485.
  * [Zhu et al.(2020)Zhu, Wei, Sisman, Zheng, Faloutsos, Dong, and Han] Qi Zhu, Hao Wei, Bunyamin Sisman, Da Zheng, Christos Faloutsos, Xin Luna Dong, and Jiawei Han.  Collective multi-type entity alignment between knowledge graphs.  In _Proceedings of The Web Conference 2020_ , WWW ’20, page 2241–2252, New York, NY, USA, 2020. Association for Computing Machinery.  ISBN 9781450370233.  doi:10.1145/3366423.3380289.  URL https://doi.org/10.1145/3366423.3380289.
  * [Ehrlinger and Wöß(2016)] Lisa Ehrlinger and Wolfram Wöß.  Towards a definition of knowledge graphs.  In Michael Martin, Martí Cuquet, and Erwin Folmer, editors, _SEMANTiCS (Posters, Demos, SuCCESS)_ , volume 1695 of _CEUR Workshop Proceedings_. CEUR-WS.org, 2016.  URL http://dblp.uni-trier.de/db/conf/i-semantics/semantics2016p.html#EhrlingerW16.
  * [Hamilton(2020)] William L. Hamilton.  Graph representation learning.  _Synthesis Lectures on Artificial Intelligence and Machine Learning_ , 14(3):1–159, 2020.  doi:10.2200/S01045ED1V01Y202009AIM046.  URL https://doi.org/10.2200/S01045ED1V01Y202009AIM046.
  * [Zhang et al.(2019)Zhang, Song, Huang, Swami, and Chawla] Chuxu Zhang, Dongjin Song, Chao Huang, Ananthram Swami, and Nitesh V. Chawla.  Heterogeneous graph neural network.  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, KDD ’19, page 793–803, New York, NY, USA, 2019. Association for Computing Machinery.  ISBN 9781450362016.  doi:10.1145/3292500.3330961.  URL https://doi.org/10.1145/3292500.3330961.
  * [Li et al.(2020)Li, Chen, Zhao, Zhang, Wang, and Tian] Maosen Li, Siheng Chen, Yangheng Zhao, Ya Zhang, Yanfeng Wang, and Qi Tian.  Dynamic multiscale graph neural networks for 3d skeleton based human motion prediction.  In _2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020_ , pages 211–220. IEEE, 2020.  doi:10.1109/CVPR42600.2020.00029.  URL https://doi.org/10.1109/CVPR42600.2020.00029.
  * [Kapoor et al.(2020)Kapoor, Ben, Liu, Perozzi, Barnes, Blais, and O’Banion] Amol Kapoor, Xue Ben, Luyang Liu, Bryan Perozzi, Matt Barnes, Martin Blais, and Shawn O’Banion.  Examining COVID-19 Forecasting using Spatio-Temporal Graph Neural Networks, 2020.
  * [Korte et al.(2012)Korte, Vygen, and Randow] Bernhard Korte, Jens Vygen, and Rabe Randow.  _Kombinatorische Optimierung: Theorie und Algorithmen_.  Masterclass. Springer Berlin Heidelberg, 2012.  ISBN 9783642254017.  URL https://books.google.de/books?id=Rj0lBAAAQBAJ.


11institutetext: Dept. Computer Science & Engineering
Ohio State University
Columbus OH 43210 USA
11email<EMAIL_ADDRESS>
# Posterior Model Adaptation
With Updated Priors

Jim Davis

###### Abstract

Classification approaches based on the direct estimation and analysis of
posterior probabilities will degrade if the original class priors begin to
change. We prove that a unique (up to scale) solution is possible to recover
the data likelihoods for a test example from its original class posteriors and
dataset priors. Given the recovered likelihoods and a set of new priors, the
posteriors can be re-computed using Bayes’ Rule to reflect the influence of
the new priors. The method is simple to compute and allows a dynamic update of
the original posteriors.

##  1 Introduction

A common probabilistic approach to classification in Machine Learning is the
Maximum A Posteriori (MAP) technique in which the class $k$ having the largest
posterior probability with test example $T$ is selected

$k_{MAP}=\operatorname*{argmax}_{i}P(C_{i}|T)$ (1)

One approach to MAP is to estimate the data likelihood for each class
$P(T|C_{i})$ and use the class priors $P(C_{i})$ within Bayes’ Rule to compute
the posterior

$P(C_{i}|T)=\frac{P(T|C_{i})P(C_{i})}{\sum_{j}P(T|C_{j})P(C_{j})}$ (2)

If only the resulting maximal class is desired, and not the actual posterior
itself, the denominator in Eqn. 2 need not be calculated as it is constant
across all classes. However, in some situations it is not clear how to model
or learn an appropriate likelihood model.

Alternatively, one can sometimes compute the posterior directly, without
specific knowledge or application of the likelihoods or priors. One simple
approach with sufficient training data is based on K-nearest neighbors, where
the proportions of each class within the set of K-nearest training examples to
a test example can be used to locally estimate class posteriors [3]. In [2],
several one-vs-all SVM classifiers are initially trained and the output from
each SVM is modeled as a posterior using Platt Scaling (logistic regression
with a single logit). The set of posteriors are L1-normalized to get multi-
class posterior estimates for the test example. In [1], a posterior method is
outlined with logistic regression on the full set of neural network output
logits corresponding to the target classes. As the output of modern neural
networks is often uncalibrated (i.e., the softmax value for the argmax class
does not properly represent the accuracy of classification) [4], any post-
calibration of the argmax-selected output can also be considered a posterior
model. In these (and other) approaches, the posteriors are computed without
explicit use of any likelihood or prior components in the model, instead
relying on the data distribution itself during training.

One issue with these “direct” approaches when deployed in practice is that the
posterior model can give inaccurate results if the class priors change over
time due to external factors. To aid in the flexibility of direct posterior-
based approaches within a dynamic domain, we present a technique to uniquely
recover (up to scale) the corresponding class likelihoods of a test example
given its class posteriors and priors from the original model. The priors can
simply be represented by the class frequencies in the original dataset and no
specific proportion relationship is required (i.e., the priors need not be
equal). The recovered likelihoods and a set of new priors can then be used
within Bayes’ Rule (Eqn. 2) to compute the updated posteriors representive of
the new situation.

##  2 Approach

Assume a probabilistic model is trained on a dataset and gives the following
class posteriors for test example $T$

$P(C_{i}|T)>0,\;\;\sum_{i}P(C_{i}|T)=1$ (3)

with the following underlying dataset priors

$P(C_{i})>0,\;\;\sum_{i}P(C_{i})=1$ (4)

Bayes’ Rule (Eqn. 2) on class $C_{i}$ forms the posterior from a combination
of likelihoods $P(T|C_{j})>0$ and priors. Manipulation of the terms in Eqn. 2
for class $C_{i}$ yields

$\displaystyle P(C_{i}|T)\sum_{j}P(T|C_{j})P(C_{j})-P(T|C_{i})P(C_{i})$
$\displaystyle=$ $\displaystyle 0$ (5)
$\displaystyle(P(C_{i}|T)-1)P(T|C_{i})P(C_{i})+\sum_{j\neq
i}P(C_{j}|T)P(T|C_{j})P(C_{j})$ $\displaystyle=$ $\displaystyle 0$ (6)

Doing this for each class posterior and factoring out the likelihoods yields a
homogeneous set of linear equations $M{\vec{x}}={\vec{0}}$ with

$M=\begin{bmatrix}(P(C_{1}|T)-1)P(C_{1})&P(C_{1}|T)P(C_{2})&\cdots&P(C_{1}|T)P(C_{n})\\\
P(C_{2}|T)P(C_{1})&(P(C_{2}|T)-1)P(C_{2})&\cdots&P(C_{2}|T)P(C_{n})\\\
\vdots&\vdots&\vdots&\vdots\\\
P(C_{n}|T)P(C_{1})&P(C_{n}|T)P(C_{2})&\cdots&(P(C_{n}|T)-1)P(C_{n})\end{bmatrix}$
(7)

${\vec{x}}=\begin{bmatrix}P(T|C_{1})\\\ P(T|C_{2})\\\ \vdots\\\
P(T|C_{n})\end{bmatrix}$ (8)

Therefore the vector of likelihoods is the non-trivial
(${\vec{x}}\neq{\vec{0}}$) solution to this homogeneous linear system.
However, does an exact positive solution to ${\vec{x}}$ exist? We will show
that the answer is yes, and thus enable computation of updated posteriors with
new/evolving class priors. Note that the solution to ${\vec{x}}$ in
$M{\vec{x}}=0$ will be valid up to a scalar, as $M(\alpha{\vec{x}})=0$,
however this will not be problematic when updating the posteriors due to the
normalization within Bayes’ Rule.

###  2.1 Proof of a Positive, Exact Solution

Inspection of matrix $M$ shows that it has positive off-diagonal elements, but
negative diagonal elements bound by $-1<M_{i,i}<0$. Consider matrix $A=M+I$

$\small
A=\begin{bmatrix}(P(C_{1}|T)-1)P(C_{1})+1&P(C_{1}|T)P(C_{2})&\cdots&P(C_{1}|T)P(C_{n})\\\
P(C_{2}|T)P(C_{1})&(P(C_{2}|T)-1)P(C_{2})+1&\cdots&P(C_{2}|T)P(C_{n})\\\
\vdots&\vdots&\vdots&\vdots\\\
P(C_{n}|T)P(C_{1})&P(C_{n}|T)P(C_{2})&\cdots&(P(C_{n}|T)-1)P(C_{n})+1\end{bmatrix}$
(9)

where $A$ is a real positive (all $A_{i,j}>0$) square matrix.

Perron-Frobenious Theory [6] states that any positive real square matrix has a
single positive eigenvector that corresponds to its largest eigenvalue (which
is positive and real). Furthermore, any other eigenvalue (possibly complex) in
absolute value is strictly smaller than the maximum eigenvalue. Therefore $A$
has a positive eigenvector which will be shown to be the solution to
${\vec{x}}$ (the desired likelihoods, up to scale).

Following the theory applied to $A$, there is a positive eigenvector
$v^{A}_{+}$ corresponding to the maximum eigenvalue $\lambda^{A}_{max}$ such
that

$A{\vec{v}^{A}_{+}}=\lambda^{A}_{max}\cdot{\vec{v}^{A}_{+}}$ (10)

The theorem further states that the maximum eigenvalue $\lambda^{A}_{max}$ is
bound by the minimum and maximum row sums of $A$:

$\min_{i}\sum_{j}A_{i,j}\leq\lambda^{A}_{max}\leq\max_{i}\sum_{j}A_{i,j}$ (11)

Since, the eigenvalues of a matrix and its transpose are the same, the maximum
eigenvalue of $A$ is the maximum eigenvalue of $A^{T}$ (i.e.,
$\lambda^{A}_{max}=\lambda^{A^{T}}_{max}$). Therefore, we can equivalently use
the minimum and maximum column sums

$\min_{j}\sum_{i}A_{i,j}\leq\lambda^{A}_{max}\leq\max_{j}\sum_{i}A_{i,j}$ (12)

as it is trivial to show that $\sum_{i}A_{i,j}=1$ for any column $j$

$\displaystyle\sum_{i}A_{i,j}$ $\displaystyle=$
$\displaystyle(P(C_{j}|T)-1)P(C_{j})+1+\sum_{i\neq j}P(C_{i}|T)P(C_{j})$ (13)
$\displaystyle=$ $\displaystyle 1-P(C_{j})+\sum_{i}P(C_{i}|T)P(C_{j})$ (14)
$\displaystyle=$ $\displaystyle 1-P(C_{j})+P(C_{j})$ (15) $\displaystyle=$
$\displaystyle 1$ (16)

Thus a single maximum eigenvalue $\lambda^{A}_{max}=1$ exists for $A$.

Substituting $M+I=A$ in Eqn. 10 gives

$\displaystyle\left(M+I\right){\vec{v}^{A}_{+}}$ $\displaystyle=$
$\displaystyle\lambda^{A}_{max}\cdot{\vec{v}^{A}_{+}}$ (17) $\displaystyle
M{\vec{v}^{A}_{+}}$ $\displaystyle=$
$\displaystyle\lambda^{A}_{max}\cdot{\vec{v}^{A}_{+}}-{\vec{v}^{A}_{+}}$ (18)
$\displaystyle M{\vec{v}^{A}_{+}}$ $\displaystyle=$
$\displaystyle\left(\lambda^{A}_{max}-1\right)\cdot{\vec{v}^{A}_{+}}$ (19)
$\displaystyle M{\vec{v}^{A}_{+}}$ $\displaystyle=$
$\displaystyle\rho\cdot{\vec{v}^{A}_{+}}$ (20)

where $\rho=\left(\lambda^{A}_{max}-1\right)$. Since $\lambda^{A}_{max}=1$,
the value of $\rho=\left(\lambda^{A}_{max}-1\right)=0$. Therefore $\rho=0$
provides the optimized solution to $M{\vec{x}}=0$ with the non-trivial vector
${\vec{x}}={\vec{v}^{A}_{+}}$.

This proof shows the existence and guarantee of a positive vector
${\vec{v}^{A}_{+}}$ (the likelihoods, up to scale) with zero error ($\rho=0$).
The computed eigenvector is typically normalized to a unit vector, but its use
within Bayes’ Rule would remove any scaling.

###  2.2 Relationship to the Non-Square Matrix Solution

Given $B{\vec{x}}=0$ with non-square matrix $B$, the classic approach (as
commonly used in camera calibration techniques [5]) to solving the non-trivial
solution to ${\vec{x}}$ is to find the eigenvector corresponding to the
smallest eigenvalue of $B^{T}B$ in

$\left(B^{T}B\right){\vec{x}}={\vec{0}}$ (21)

This form is derived from a Lagrangian loss function based on minimizing
$||Bx||^{2}=\left(B{\vec{x}}\right)^{T}(B{\vec{x}})={\vec{x}}^{T}B^{T}B{\vec{x}}$
subject to $||{\vec{x}}||^{2}={\vec{x}}^{T}{\vec{x}}=1$.

Though our matrix $M$ is square, we can easily confirm the above non-square
formulation holds by substituting $B=M$ and ${\vec{x}}={\vec{v}^{A}_{+}}$ into
the loss (we already know that $||{\vec{v}^{A}_{+}}||^{2}=1$)

$\displaystyle||M{\vec{v}^{A}_{+}}||^{2}$ $\displaystyle=$
$\displaystyle(M{\vec{v}^{A}_{+}})^{T}(M{\vec{v}^{A}_{+}})$ (22)
$\displaystyle=$
$\displaystyle(\rho{\vec{v}^{A}_{+}})^{T}(\rho{\vec{v}^{A}_{+}})$ (23)
$\displaystyle=$
$\displaystyle\rho^{2}({\vec{v}^{A}_{+}})^{T}{\vec{v}^{A}_{+}}$ (24)
$\displaystyle=$ $\displaystyle\rho^{2}$ (25)

This loss is minimized as $\rho^{2}=0$. Thus the required positive eigenvector
can be computed directly from matrix $A$ without the need for any matrix
transpose multiplication.

###  2.3 Posterior Update Procedure

To update the existing posterior for a test example with new priors, we form
matrix $A$ using the current posterior estimates $P(C_{i}|T)$ and the original
dataset priors $P(C_{i})$. Then the eigenvector corresponding to the maximum
eigenvalue of $A$ is computed, which is the vector of scaled likelihoods
$P(T|C_{i})$. Bayes’ Rule is applied with these likelihoods and the set of new
priors ${\hat{P}}(C_{i})$ to provide the updated posteriors
${\hat{P}}(C_{i}|T)$

${\hat{P}}(C_{i}|T)=\frac{P(T|C_{i}){\hat{P}}(C_{i})}{\sum_{j}P(T|C_{j}){\hat{P}}(C_{j})}$
(26)

These updated posteriors reflect the new class priors and can be used in any
further decision or classification process.

##  3 Example

To demonstrate the method, we created a set of synthetic data from which the
known posteriors, likelihoods, and priors are known. We employed a 1-D
Gaussian likelihood distribution for each of two classes ($C_{1}$, $C_{2}$)
using

$P(d|\mu_{C_{i}},\sigma)=\frac{1}{\sqrt{2\pi\sigma^{2}}}\exp{-\frac{(d-\mu_{C_{i}})^{2}}{2\sigma^{2}}}$
(27)

with $\mu_{C_{1}}=-1.0$, $\mu_{C_{2}}=1.0$, and $\sigma^{2}=1.0$. In this
example we start with equal priors $P(C_{1})=P(C_{2})=.5$. Sampling a total of
$N=10K$ values provides the dataset having the histogram distributions shown
in Fig. 1(a).

(a) | (b)
---|---
Figure 1: Data distributions with (a) original priors and (b) new priors.

We simulated a Bayesian classifier that directly computes the posterior
probabilities for a test sample and then chooses the class with the largest
posterior. We computed the optimal posteriors for each sample using Bayes’
Rule (Eqn. 2) with the ground truth Gaussian likelihood models and priors
(though the likelihoods would not be available to a direct, posterior-based
classifier). Given the Gaussian likelihood distributions and the priors, the
optimal Bayesian classification boundary with our class means and unit
variance is the location $d$ where the two probabilities are equal

$\displaystyle P(C_{1}|d)$ $\displaystyle=$ $\displaystyle P(C_{2}|d)$ (28)
$\displaystyle P(d|C_{1})P(C_{1})$ $\displaystyle=$ $\displaystyle
P(d|C_{2})P(C_{2})$ (29) $\displaystyle\frac{P(d|C_{1})}{P(d|C_{2})}$
$\displaystyle=$ $\displaystyle\frac{P(C_{2})}{P(C_{1})}$ (30)
$\displaystyle\ln{\frac{P(d|C_{1})}{P(d|C_{2})}}$ $\displaystyle=$
$\displaystyle\ln{\frac{P(C_{2})}{P(C_{1})}}$ (31)
$\displaystyle\frac{-(d-\mu_{C_{1}})^{2}}{2\sigma^{2}}-\frac{-(d-\mu_{C_{2}})^{2}}{2\sigma^{2}}$
$\displaystyle=$ $\displaystyle\ln{\frac{P(C_{2})}{P(C_{1})}}$ (32)
$\displaystyle(d+1)^{2}-(d-1)^{2}$ $\displaystyle=$
$\displaystyle-2\ln{\frac{P(C_{2})}{P(C_{1})}}$ (33) $\displaystyle d$
$\displaystyle=$ $\displaystyle-\frac{1}{2}\ln{\frac{P(C_{2})}{P(C_{1})}}$
(34)

This boundary is $d=0$ for equal priors and is shown as the vertical dashed
line in Fig. 1(a).

Let us assume that some time in the future the class priors have changed,
e.g., $\hat{P}_{C_{1}}=.8$ and $\hat{P}_{C_{2}}=.2$, and we collect $N$ new
data samples. The corresponding histogram distributions and optimal Bayesian
decision threshold for this new collection are shown in Fig. 1(b). Notice that
the new optimal boundary ($\hat{d}=.69$) has shifted to the right due to the
stronger prior of $\hat{P}_{C_{1}}$. If we use the maximum of the posteriors
computed from our previous posterior model (based on the old priors and
corresponding to $d=0$), the total error rate is 15.9% (1269/8000 errors in
$C_{1}$ and 319/2000 errors in $C_{2}$). The new data obviously does not
reflect the previous equal priors.

Instead, we compute for each new data sample its original class posteriors
(based on the previous priors), use the proposed method to recover the
likelihoods using these posteriors and previous priors, and then use Bayes’
Rule to re-compute the posteriors using the likelihoods and new priors.
Classification by selecting the maximum of these new posteriors yields a
reduced total error rate of 11.2% (362/8000 errors in $C_{1}$ and 756/2000
errors in $C_{2}$). These are the exact results if the optimal Bayesian
threshold $\hat{d}=.69$ is used to classify the sample data. Therefore, the
proposed approach can be used to properly update the posteriors to achieve
more prior-aware classifications.

##  4 Summary

We presented an approach to recover (up to scale) the underlying likelihoods
of a test example from its original class posteriors and priors. As fixed
classification models become inaccurate over time if the priors begin to
change, the proposed method enables an update of the posterior estimates with
new class priors. This approach is applicable to those classification models
that directly estimate the posterior of each class, without explicitly using
the likelihood or priors (relying only on the underlying data distribution).
We expect this technique to be useful in variety of dynamic classification
scenarios.

## References

  * [1] Davis, J., Liang, T., Enouen, J., Ilin, R.: Hierarchical classification with confidence using generalized logits. In: ICPR (2021)
  * [2] Deng, J., Krause, J., Berg, A.C., Fei-Fei, L.: Hedging your bets: Optimizing accuracy-specificity trade-offs in large scale visual recognition. In: CVPR (2012)
  * [3] Fukunaga, K.: Introduction to Statistical Pattern Recognition. Academic Press, New York, 2 edn. (1990)
  * [4] Guo, C., Pleiss, G., Sun, Y., Weinberger, K.: On calibration of neural networks. In: ICML (2017)
  * [5] Hartley, R.: In defense of the eight-point algorithm. IEEE Trans. Pattern Analysis and Machine Intelligence 19(6), 580–593 (1997)
  * [6] Meyer, C.: Matrix Analysis and Applied Linear Algebra. SIAM, Philadelphia, PA (2000)