Graph-Relational Domain Adaptation
Authors: Zihao Xu
Hao He
Guang-He Lee
Bernie Wang
Hao Wang
Venue: ICLR 2022 Poster (2022)
Keywords: Graphs
Network Topology
Transfer Learning
Domain Adaptation
Adversarial Learning

Abstract: Existing domain adaptation methods tend to treat every domain equally and align them all perfectly. Such uniform alignment ignores topological structures among different domains; therefore it may be beneficial for nearby domains, but not necessarily for distant domains. In this work, we relax such uniform alignment by using a domain graph to encode domain adjacency, e.g., a graph of states in the US with each state as a domain and each edge indicating adjacency, thereby allowing domains to align flexibly based on the graph structure. We generalize the existing adversarial learning framework with a novel graph discriminator using encoding-conditioned graph embeddings. Theoretical analysis shows that at equilibrium, our method recovers classic domain adaptation when the graph is a clique, and achieves non-trivial alignment for other types of graphs. Empirical results show that our approach successfully generalizes uniform alignment, naturally incorporates domain information represented by graphs, and improves upon existing domain adaptation methods on both synthetic and real-world datasets.

Published as a conference paper at ICLR 2022
GRAPH-RELATION DOMAIN ADAPTATION
Zihao Xu'; Hao He?, Guang-He Lee", Yuyang Wang', Hao Wang' 'Rttgers University, 2 "Massachusetts Institute of Technology. 3 AAWS Al Labs z zihao. xuê rursers. edu, (haohe, guanghe @mit.edu. yuyawange ama amazon. zon. com, hw4888cs rutgers. edu
ABSTRACT
Existing domain adaptation methods tend to treat every domain equally and align them all perfectly. Such uniform alignment ignores topological structures among different domains; therefore it may be beneficial for nearby domains, but not necessarily for distant domains. In this work, we relax such uniform alignment by using domain graph to encode domain adjacency, e.g., a graph of states in the US with each state as a domain and each edge indicating adjacency, thereby allowing domains to align flexibly based the graph structure. We generalize the existing adversarial learning framework with a novel graph discriminator using encoding- conditioned graph embeddings. Theoretical analysis shows that at equilibrium, our method recovers classic domain adaptation when the graph is clique, and achieves non-trivial alignment for other types of graphs. Empirical results show that our approach successfully generalizes uniform alignment, naturally incorporates domain information represented by graphs, and improves upon existing domain adaptation methods on both synthetic and real-world datasets"
INTRODUCTION
Generalization of machine learning methods hinges on the assumption that training and test data follows the same distribution. Such an assumption no longer holds when one trains a model some domains (source domains), and tests it in other domains (target domains) where data follows different distributions. Domain adaptation (DA) aims at improving performance in this setting by aligning data from the source and target domains that model trained in source domains can generalize better in target domains (Ben-David et al.) 2010 Ganin et al. 2016 Tzeng et al.) 2017 Zhang et al. 2019).
Existing DA methods tend enforce uniform alignment, i.e., to treat every domain equally and align them all perfectly. However, in practice the domains are often heterogeneous; one can expect DA work well when the source domains are close to the target domains, but not when they are too far from each other (Zhao et al., 2019 Wang et al.] (020). Such heterogeneity can of- ten be captured by graph, where the domains realize the nodes, and the adjacency between two domains can be captured by an edge (see Fig. [T]. For example, to capture the similarity of weather in the US, we can construct a graph where each state is treated ity between two states results in an edge. There
08
MD
DE
Figure 1: 15 states in the east of the US as 15 do- mains. Left: Traditional DA treats each domain equally and enforces uniform alignment for all domains, which is equivalent to enforcing a fully connected domain graph. Right: Our method generalizes traditional DA to align domains ac- cording to any specific domain graph, e.g., a do- main graph describing adjacency among these 15 states.
node and the physical proxim-
are also many other scenarios where the relation among domains can be naturally captured by graph, such as the taxonomies of products in retail or connections among research fields of academic papers. Given domain graph, we can tailor the adaptation of domains the graph, rather than dictating the data from all the domains to align perfectly regardless of the graph structure.
Work conducted during internship at AWS AT Labs. Code will soon be available htt.ttps:////....... / htt////tttttt http://ooo/ow/gggooe Lab/GRDA

---

Published as a conference paper at ICLR 2022
One naive DA method for such graph-relationll domains is to perform DA for each pair of neighboring domains separately. Unfortunately, due to the strict alignment between each domain pair, this method will still lead to uniform alignment so long as the graph is connected. To generalize DA to the graph- relational domains, we argue that an ideal method should (1) only enforce uniform alignment when the domain graph is clique (i.e., every two domains are adjacent), and (2) more importantly, relax uniform alignment to adapt more flexibly across domains according to any non-clique domain graph, thereby naturally incorporating information on the domain adjacency. In this paper, we generalize adversarial DA methods and replace the traditional binary (or multi-class) discriminator with a novel graph discriminator: instead of distinguishing among different domains, our graph discriminator takes as input the encodings of data to reconstruct the domain graph. We show that our method enjoys the following theoretical guarantees: it recovers classic DA when the the domain graph is clique, and realizes intuitive alignments for other types of graphs such as chains and stars (see Fig. We summarize our contributions as follows:
We propose to use a graph to characterize domain relations and develop graph-relational domain adaptation (GRDA) as the first general adversarial DA method to adapt across domains living a graph.
We provide theoretical analysis showing that at equilibrium, our method can retain the capability of uniform alignment when the domain graph is clique, and achieve non-trivial alignment for other types of graphs.
Empirical results on both synthetic and real-world datasets demonstrate the superiority of our method over the state-of-the- aart DA methods.
2 RELATED WORK
Adversarial Domain Adaptation.
There have been extensive prior works on domain adaptation (Pan
& Yang] 2009; Pan et al. 2010; Long al. 2018 Saito et al. 2018 Sankaranaray
al. 2018
Zhang et al.] 2019 Peng et al.
2019: Chen et al. 2019 Dai et al. 2019 Nguyen- Meidine et al.
2021). Typically they aim to align the distributions of the source and target domains with the hope that the predictor trained on labeled source data can generalize well on target data. Such alignment
can be achieved by either directly matching their distributions' statisties (Pan et al., 2010 Tzeng
let al. 2014: Sun & Saenko, 2016; Peng et al. [2019] Beguyen-Meiding et al. [2021] or training deep
learning models with an additional adversarial loss (Ganin et al. 2016; Zhao et al.]
2017 Tzeng
et al. 2017 Zhang et al. 2019; Kuroki et al. 2019. Chen et al. 2019; Dai et al. 2019). The
latter, i.e., adversarial domain adaptation, has received increasing attention and popularity because
of its theoretical guarantees (Goodfellow et al. 2014 Zhao et al., 2018: Zhang et al.) 2019 ZZhao
ctt al. 2019), its ability to train end-to-end with neural networks, and consequently its promising empincal performance. Also loosely related to our work is continuously indexed domain adaptation (CIDA)]Wang et al. (2020), which considers domains indexed by continuous values. These methods typically treat every domain equally and enforee uniform alignment between source-domain data and target-domain data; this is done by generating domain-invariant encodings, where domain invariance is achieved by training the encoder fool the discriminator that classifies the domain index. In contrast, we naturally relax such uniform alignment using a graph discriminator to reconstruct domain graph that describes domain adjacency.
Domain Adaptation Related to Graphs. There are also works related to both DA and graphs. Usually they focus adaptation between two domains where data points themselves are graphs For example, (Pilancı & Vural, 2019 Pilanci & Vural (2200) use frequency analysis to align the data graphs between the source domain and the target domains, and (Alam al. 2018 Ding al., 2018 perform label propagation on the data graph.
In contrast, GRDA considers a setting completely different from the above references. Instead of focusing on adapting between two domains with data points in the form of graphs (e.g., each data point itself is a node), GRDA adapts across multiple domains (e.g., with each state in the US as a domain) according to a domain graph (i.e., each domain is node). Therefore the methods above are not applicable to our setting. Note that (Mancini et al. 2019) uses metadata-weight batch normalization to propagate information among domains with similar metadata, but it is not an adversarial domain adaptation method. It is orthogonal to GRDA and can be used as a backbone network to further improve GRDA's performance (see the Appendix for empirical results). It is also
2

---

Published as a conference paper at ICLR 2022
Encoding
Encoding
Encoding
D
D
Encoding
Classifying the Domain Index
Reconstructing the Domain Graph
Figure 2: Difference between discriminators in traditional DA methods and the graph discriminator in GRDA. Left: In traditional DA methods, the discriminator classifies the domain index given an encoding. Right: In GRDA, the graph discriminator reconstructs the domain graph given encodings of data from different domains.
worth noting that, in this paper, we assume the domain graph is given. It would be interesting future work to combine GRDA with domain relation inference methods (e-g.. domain embeddings (Peng et al. 2020 when there is natural but unobserved graph relation among domains.
3
METHOD
In this section, we will first briefly introduce the problem setting and then elaborate our domain adaptation method.
3.1 PROBLEM SETTING AND NOTATION
We focus the unsupervised domain adaptation setting with N domains in total. Each domain has discrete domain index 21 [NV] & [1....,N] N,, belonging either the source domain index set U, or the target domain index set Udg The relationship between domains is described by a domain graph with the adjacency matrix A = [Aiyl, where i and j index nodes (domains) in the graph. Given labeled data {xx) ./. u/)]== from source domains (uf E U4,) unlabeled data {xf ul k/) from target domains (u, 24,), and the domain graph described by A. want predict the label {ut m 1==1 for data from target domains. Note that the domain graph is defined on domains with each domain (node) containing multiple data points.
3.2
DOMAIN ADAPTATION (GRDA)
Overview. We use an adversarial learning framework to perform adaptation across graph-relational domains. The adversarial game consists of three players: (1) an encoder E, which takes as input datum Xt, the associated domain index иy, and the adjacency matrix A to generate an encoding e, [(x,, uy A). (2) a predictor F, which makes predictions based on the encoding e;, and (3) graph discriminator D, which guides the encoding to adapt across graph-relational domains. takes in a mini-batch of B encodings e, (1 E [B), and tries to reconstruct the domain graph A. By letting the encoder E play adversarially against the discriminator D. the graph-relational information domains will be removed from the encoding e₁ in order to make the discriminator D incapable of reconstructing the graph. Note that the graph discriminator in our adversarial game is different from classic discriminators which classify the domain index, as shown in Fig.
Specifically, the discriminator
Formally, GRDA performs a minimax optimization with the following loss function:
min max L F), XaLa(D, E),
(I)
E,F D
where (y, F) is the predictor loss and Ld(D, E) is the discriminator loss, and X is hyperpa- rameter balancing them two. Below we discussed these two terms in detail.
Predictor. In Eqn. 1 the predictor loss (F, F) is defined
FF, A E" u, A)).
where the expectation E" is taken over the source cource-domain data distribution pxx y, u). hp(: is predictor loss function for the task (e.g., Ta2 loss for regression).
3

---

Published as a conference paper at ICLR 2022
Encoder and Node Embeddings. Given an input tuple (xi, u,, A), the encoder E first computes graph-informed domain embedding Zu, based on the domain index iy and the domain graph A. Then we feed zu; along with x; into neural network to obtain the final encoding e,. Formally we have
ej = Exi,, ui, A) [x1, )
(2)
where f(.--) a trainable neural network.
In theory, any embeddings for node (domain) indices should work equally well so long as they are distinct from one another (thus forming bijection to the set of domains [M]. Here we pre-train the embeddings by reconstruction loss for simplicity, and our intuition is that good embeddings of nodes should inform us of (thus reconstruct) the graph structure. Suppose the nodes indices and j are sampled independently and identically from the marginal domain index distribution p(u); the reconstruction loss written as
Lg Bi.j--(() Aij log (z, 21) (1 A1y- log(1 oz, 2,))],
where (x) Ite the sigmoid function. Note that in general we could use any node embedding
methods (Grover & Leskovec 2016] "Tang et al.] 2015: Kipf & Welling 2016b), but this is not the focus of this paper. For fair comparison, we use exactly the same encoder, i.e., E(x, A), for all the
methods in the experiments of Sec. [
Graph Discriminator: The discriminator loss La(D, E) in Eqn. is defined as
E) E (x) [h(x1, U1, u2)],
(3)
h hx M1, X2, U2) A uu log 0 (2) 22) (1 Auy,ug log(1 (2] 22).
where 2 = (X)(x)) u1. A)). 22 = D (F 42 A)) are the discriminator's reconstructions of node embeddings. The expectation E is taken over pair of i.i.d. samples (x1; un ).(x2, u2) from the joint data distribution p(x, u). The discriminator loss La(D, EE) essentially quantifies how well the reconstructed node embedding 21, 22 preserve the information of the original connections, or, equivalently. A. We refer readers to the Appendix for detailed model architectures.
Due to the adversarial nature of how the discriminator D and the encoder E engage with the loss, the discriminator D would aim to recover the domain graph via the adjacency structure (A), while the encoder E' would prevent the discriminator D from doing so. Intuitively, if the discriminator D is powerful enough to uncover any information regarding the domain graph in the encoding et, the optimal encoder E will have to remove all the information regarding graph-relational domains the encoding e,, thus successfully adapting across graph-relational domains. We will formally elaborate the above arguments further the next section.
THEORY
In this section, we first provide theoretical guarantees that at equilibrium GRDA aligns domains according to any given domain graph. Specifically, we analyze a game where the graph discriminator D tries to reconstruct the domain graph while the (joint) encoder E tries to prevent such reconstruction. To gain more insight on the encoding alignment, we then further discuss the implication of these general theoretical results GRDA's global optimum using simple example graphs such as cliques, stars, and chains. All proofs of lemma, theorem and corollary can be found in Appendix A.
4.1 ANALYSIS FOR GRDA
For simplicity, we first consider a game which only involves the joint encoder E and the graph discriminator D with extension to the full game later. Specifically, we focus on following loss function:
max LD(DEE,
(4)
where La(D, E) is defined in Eqn.
Lemma 4.1 below analyzes the optimal graph discriminator D given a fixed joint encoder E. In- tuitively, it states that given two encodings e and e', the optimal D will output the conditional expectation of Aij over all possible combinations of domain pairs (i. sampled from p(ule) and plule').
4

---

Published as a conference paper at ICLR 2022
Lemma 4.1 (Optimal Discriminator for GRDA). For E fixed, the optimal D satisfies following equation.
dDi()) ((ee)) Bxwppallehss-ppttleelA.
where e and e' are from the encoding space.
Theorem 4.1 (Global Optimum for GRDA with General Domain Graphs), Given an adjacency matrix A, the total loss in Eqn. 4 has tight upper bound:
La(D, E) S H(Be,e
= (((,),(AA)))
where H denotes the entropy function, (p) -plog(p) - (1 - p) log(1 p), and a(e, = Bi--pulee..--poalee))a. Furthermore, the equality, i.e., the optinum,, is achieved when
ale, e') E.g]AAih for any e,e',
or equivalently, (Aslee E.,((AAs) [Ai)] where (e, ) is from the encoding space.
Essentially, Theorem 4.1 shows that if trained to the global optimum, GRDA aligns the domain distribution p(ule) for all locations in the embedding space such that are,, eÿ) identical to the constani, E,gl ig]. for any pair ee),
We can directly apply Theorem 4.1 to evaluate the training process. During training, if the discrimi- nator loss finally converges to the theoretical optimum H (E,,, (A,))) (Figure 3), would know that our training succeeds.
An interesting property of GRDA is that uniform alignment is a solution for any domain graph, as shown in Corollary 4.1 below.
Corollary 4.1. For GRDA, the global optimum of total loss La(D, E) is achieved if the encoding of all domains (indexed by u) are perfectly (uniformly) aligned, i.e., e 1. u.
Note that replacing the inner product inside o-)) with other functions (e.g., L2 distance) does not change Lemma 4.1 and Theorem [ as long as cross-entropy loss is used consider both positive and negative edges in the graph.
Global Optimum of GRDA v.s LD)
We can also analyze the full game defined in Eqn. (see the Appendix for details).
(AE,)(A)))
Discriminator Loss
Theorem 4.2. If the encoder E, the predictor and the discriminator D have enough capacity and are trained reach optimum, any global op- timal encoder E= has the following properties:
Hyy|E" (x, u. A)) H u. A),
50
100
150
200
250
Epochs
where H(.).) denotes the conditional entropy.
Figure 3: Global Optimum of GRDA
La(D, E) during training process. The loss of the discriminator finally converges the theoret- ical optimum (TE., (Ai))).
Theorem 4.2 implies that, at equilibrium, the op- timal joint encoder E produces encodings that preserve all the information about the label y con- tained in the data x and the domain index u. There- fore, the global optimum of the two-player game between E and D matches the global optimum of the three-play game between E, D. and F.
4.2 IMPLICATION OF GRDA'S GLOBAL OPTIMUM
Sec. 4.1 annalyzes the global optimum of GRDA its general form. this section, we further discuss the implication of these general theoretical results using simple example graphs such cliques, stars, and chains; we show that GRDA's global optimum actually translates to domain- domain-graph-ine -rapp--iffrrmeedd constraints the embedding distributions of every domain.
With N domains in total, we assume each domain contains the same amount of data, ie. p(u = p(u N) N-1, We further p: pe(e) shorthand for p(elu i). the embedding
5

---

Published as a conference paper at ICLR 2022
Graph:
pi(e)
px(e))
Px(e))
Encading Disributions:
Figure 4: Example domain graphs as discussed in Sec. 4.2 Left: Cliques. Middle: Star graphs. Right: Chain graphs.
Figure 5: Possible encoding distributions of three domains forming a chain graph of three nodes at equilibrium. We can see that for any encoding. e.g., e1, we have P2 (2 = = (pi(e)) + ps(ei)).
distribution in domain i. With our assumption, the marginal embedding distribution is the average em- bedding distribution over all domains, i.e., p(e) N -i (e))). We define (e) p; (e)))()). as the ratio between domain-speciin embedding distribution and the marginal embedding distribution.
Cliques (Fully Connected Graphs). In this example, the N domains in domain graph are fully connected, i.c. there is an edge between any pair of domains, as shown Fig. (left).
Corollary 4.2 (Cliques). In a clique, the GRDA optimum achieved if and only if the embedding distributions of all the domains are the same, iee. p1 (c())
(e) = p(e), ve.
shows that at equilibrium, GRDA recovers the uniform alignment of classic domain adaptation methods when the domain graph is clique. Among all connected graphs with N nodes (domains), a clique has the largest number of edges, and therefore GRDA enforces the least flexible alignment, i.e., uniform alignment, when the domain graph is a clique.
Interestingly, Corollary 4.2
Star Graphs. this example, we have N domains forming star graph (as shown in Fig. 1 (middle)) where domain 1 is the center of the star while all other domains are connected to domain
Corollary 4.3 (Star Graphs). In star graph, the GRDA optimum is achieved if and only if the embedding distribution of the center domain is the average of all peripheral domains, i.e. 1 Σ P.))) Vc.
(c(c) N-1
Corollary 4.3 shows that compared to cliques, GRDA enforces a much more flexible alignment when the domain graph is star graph. It only requires the embedding distribution of the center domain to be the average of all peripheral domains. In this case, peripheral domains can have very different embedding distributions.
Chain Graphs. In this example, we consider the case where N domains form chain, i.c., domain only connected domain (unless i 1) and domain + (unless N). as shown in Fig. (right).
Corollary 4.4 (Chain Graphs). Let p:(c) = p(c/u = i) and the average encoding distribution p(e) N-1 E p(elu i). In chain graph, the GRDA optimum is achieved if and only if'Ve, el
(r(e)pui(e)) ((e))(()))) 2(N p(e)p(e')
Corollary 4.4 shows that in a chain graph of N domains, direct interactions only exist in domain p (i.e., consecutive domains the chain).
Chain of Three Nodes. To gain more insight, below we analyze special case of chain graphs with three domains, i.c., chain graph three nodes as the domain graph, where domain connected to both domain 1 and domain 3. Note that this is also special case of star graphs, with one center node and two peripheral nodes. By Corollary or Corollary we can prove the following Proposition 4.1
Proposition 4.1 (Chain of Three Nodes). In this length three chain graph, the GRDA optimum achieved and only if the embedding distribution of the middle domain is the average of the embedding distributions of the domains the two sides, i.e. (2(e) 1 (pi (e) + pa(e)). Ve.
Proposition states that, for a chain graph domains, GRDA relaxes classical DA requiring per- fect alignment of embedding distributions, and instead only requires linear interpolation/extrapllatto

---

Published as a conference paper at ICLR 2022
WA
NY
W
W
CD
DE
Level1
Level2
Target Demains
Level3
Level- Tanget Dunsiny, Target Dumainy larget Domains
Level-2
Level1
Target Dumains
Figure 6: Domain graphs for the two adaptation tasks on TPT-48, with black nodes indicating source domains and white nodes indicating target domains. Left: Adaptation from the 24 states in the east to the 24 states in the west. Right: Adaptation from the 24 states in the north to the 24 states in the south.
relations among embedding distributions. Fig. shows a simple example. domain 2 (the center domain) is the target domain while others are source domains, GRDA interpolates the embedding distribution of domain according to domain 1 and 3. Similarly, if domain 3 (the peripheral domain on the right) is the target domain while others are source domains, GRDA extrapolates the embedding distribution of domain 3 according to domain and 2.
The theorems above show that GRDA can enforce different levels of alignment, from perfect alignment to linearly interplaaingglettapoolaingg embedding distributions, according to the domain graph.
EXPERIMENTS
In this section, we compare GRDA with existing methods on both synthetic and real-world datasets.
5.1 DATASETS
DG-15. We make synthetic binary classification dataset with 15 domains, which we call DG-15. Each domain contains 100 data points. To ensure adjacent domains have similar decision boundaries, we generate DG-15 as follows. In each domain i, we first randomly generate a 2-dimensional unit vector [a,, b,] as the node embedding for each domain and denote the angle of the unit vector as wi = arcsin( ). We then randomly generate positive data (x, i) and negative data (x, 0, i) from two different 2-dimensional Gaussian distributions, (M I) and N I), respectively, where |4,1 = 1 a; b,] and 14.00 = [- 04, # hz). To construct the domain graph, we sample Aij ~ Bern((055,,a) + 0.5b.by + 0.55), where Bern(f) is a Bernoulli distribution with the parameter 0. With such a generation process, domains with similar node embeddings [ai, 6.] will (1) have similar 1 and 14.0- indicating similar decision boundaries, and (2) are more likely to have an edge in the domain graph. We select 6 connected domains the source domains and use others as target domains, as shown in Fig. 7
DG-60. We make another synthetic dataset with the same procedure DG-15, except that it contains 60 domains, with 6, 6,000 data points in total. The dataset is called DG-60. We again select 6 connected domains as the source domains, with others as target domains.
TPT-48. TPT-48 contains the monthly average temperature for the 48 contiguous states in the US from 2008 to 2019. The raw data are from the National Oceanic and Atmospheric Administration' 's Climate Divisional Database (nClimDiv) and Gridded 5km GHCN-Daily Temperature and Precipitation Dataset (nClimGrid) (Vose et al., 2014). We use the data processed by Washington Post (WP) 2020).
Here we focus on the regression task to predict the next 6 months' temperature based on previous first 6 months' temperature. We consider two DA tasks as illustrated Fig. 6
(24) - W (24): Adapting models from the 24 states in the east to the 24 states in the west.
N (24) + S (24): Adapting models from the 24 states in the north to the 24 states in the south.
We define target domains one hop away from the closest source domain as Level-1 Target Domains, those two hops away as Level-2 Target Domains, and those more than two hops away as Level-3 Target Domains, shown in Fig.
7

---

Published as a conference paper at ICLR 2022
Ace
100%
Source-Only Ace: 39.77%
DANN Ace: 72.11%
ADDA Acc: 69.00%
Data
Source domain
MDD Acc: 51.33%
CDANN Acc: 72.44%
GRDA Acc: 84.44%
0%
Figure 7: Detailed results on DG-15 with 15 domains. On the left is the domain graph for DG-15. We use the 6 domains in the dashed box source domains. On the right are the accuracy of various DA methods for each domain, where the spectrum from 'red' to 'blue' indicates accuracy from 100% 0% (best viewed in color).
Table 1: Accuracy (%) DG-15 and DG-60.
Method
Source-Oni
DANN
ADDA
CDANN
MDD
GRDA (Ours)
DG-15
39.77
72.11
69.00
72.44
51.33
84.44
DG-60
38.39
61.98
32.17
61.70
66.24
96.76
CompCars. Comprehensive Cars (CompCars) (Yang et al. 2015) contains 136,726 images of cars with labels including car types, viewpoints, and years of manufacture (YOMs). Our task is to predict the type based on the image, with each view point and each YOM seperate domain. We choose a subset of CompCars with car types (MPV, SUV, sedan and hatchback), 5 viewpoints (front (F), rear (R), side (S), front-side (FS), and rear-side (RS)), ranging from 2009 to 2014. It has 30 domains (5 viewpoints x 6 YOMs) and 24,151 images in all. We choose cars with front view and being produced in 2009 as source domain, and the others as targets domains. We consider two domains connected if either their viewpoints or YOMs are identical/nearby. For example, Domain A and B are connected their viewpoints are 'F' and 'FS', respectively.
5.2 BASELINES AND IMPLEMENTATION
We compared our proposed GRDA with sfate-of-the-ar DA methods, including Domain Adversarial Neural Networks (DANN) (Ganin et al. 2016), Adversarial Discriminative Domain Adaptation (ADDA) (Tzeng et al. 2017). Conditional Domain Adaptation Neural Networks (CDANN) (Zhao et al. 2017), and Margin Disparity Discrepancy (MDD) (Zhang al. 2019). We also report results when the model trained in the source domains is directly tested in the target domains (Source-Only). Besides the baselines above, we formulated the DA task as a semi-supervised learning (SSL) problem and adapted two variants of graph neural networks (Kipf & Welling 201 Zhou et al. 2020). We prove that the first variant cannot work (Theorem C.I and our experiments show that the second variant performs worse than most domain adaptation baselines. For completeness, result of SENTRY, a recent entropy-bast the algorithms are implemented in Py PyTorch (Paszke et al. 2019) and the balancing hyperparameter Ad is chosen from 0.1 to (see the Appendix for more details on training). Note that since MDD originally designed for classification tasks, replace its cross-entrops loss with L2 loss so that it could work in the regression tasks on TPT-48. For fair comparison, all the baselines use x, the domain index u, and the node embedding inputs the encoder (as mentioned in Eqn. 2
also report the method, on our tasks (see the Appendix for details). All
5.3 RESULTS
DG-15 and DG-60. We show the accuracy of the compared methods in Table 10 it is clear that training on the source domains without adaptation (Source-Only) leads to even worse results than random guess (50% accuracy), simply due to overfitting the source domains under domain shifts. While existing DA methods such as DANN and MDD may outperform Source-Only in most of the cases, their improvements over random guess are limited. In some cases, they barely improve upon 'random prediction' (e.g., MDD on DG-15) or even underperform Source-Only (e.g., ADDA
Based on the table,
8

---

Published as a conference paper at ICLR 2022
Table 2: MSE for various DA methods for both tasks E (24) + W (24) and N (24) (24) on 7PT-48. We report the average MSE of all domains as well as more detailed average MSE of Level-1, Level-2, Level-3 target domains, respectively (see Fig. 6 Note that there only one single DA
model per column. We mark the best result with bold face and the second best results with underline.
Task
Domain
Source-Only
DANN
ADDA
CDANN
MDD
GRDA (Ours)
Average Level-1 Domains
1.852
2.449
0.902
0.995
0.936
Average of 7 Level.2 Domains
1.992
2,186
2.401
2.335
1.383
1,255
E. (24)
Average Level-3 Domains
1.942
1.939
1.966
3.002
1.830
Average of All 24 Domains
1,926
2.679
2:254
2,108
1.335
1,297
Average of 10 Level-1 Domains
2.255
1,851
2.172
0.924
1,159
0.754
N ((24)=+5 Average Level-3 Domains
Average Level-2 Domains
1,900
1.964
2,600
6.434
2,087
0.882
3.032
4.015
3,462
1.882
3.149
1.889
Average of All 24 Domains
2,426
2,600
2.709
2.621
2.054
1.165
Table 3: Accuracy (%) on CompCars (4-Way Classification).
Method
Source-Only
DANN
ADDA
CDANN
MDD
GRDA (Ours)
CompCars
46.5
50.2
46.1
48.2
49.0
51.0
on DG-60). In contrast, GRDA can successfully perform adaptation by aligning data according to the domain graph and achieve much higher accuracy.
Fig. 7 showss the accuracy of different DA methods on DG-15 for each domain, where the spectrum from "red' to 'blue' indicates accuracy from 100% 0%. Without domain adaptation, Source-Only only achieves high accuracy for the domains immediately adjacent to the source domains, while its accuracy drops dramatically when the target domain is far away from the source domains, achieving nearly 0% accuracy in the three most distant domains, While existing DA methods may improve the overall accuracy, all of them are worse than random guess (50% accuracy) in at least one domain. Notably, MDD achieves accuracy of only 50% in almost all the target domains. In contrast, the accuracy of GRDA never falls below 30% for every domain.
TPT-48. Table 2 shows the mean square eπrо (MSE) in both adaptation tasks for different DA methods on the dataset TPT-48. In terms of average performance of all the target domains, we can see that DANN, ADDA and CDANN achieve negative performance boost in both E (24) - W (24)
and N (24) - (24). highlighting the difficulty of performing DA across graph-relational domains. MDD can achieve stable improvement upon Source-Only, and our proposed GRDA can further improve the performance, achieving the lowest average MSE in both tasks.
Besides average MSE of all the target domains, also report more fine grninee results to see how the error distributes across different target domains. Specifically, Table(]shows shows the average MSE of Level-1, Level-2, and Level-3 target domains (see Fig. 6 for an illustration) for both tasks. These results show GRDA can consistently achieve low MSE across all the levels of target domains.
CompCars. Table 3 shows the average classification accuracy on CompCars for different DA methods. We found that all the DA methods, except ADDA, outperforms Source Only. Our proposed method GRDA takes full advantage of the domain graph and achieves the most significant accuracy improvement (9.68%) (see the Appendix for more detailed results).
6 CONCLUSION
In this paper, we identify the problem of adaptation across graph-relational domains, i.c., domains with adjacency described by a domain graph, and propose a general DA method to address such a problem. We further provide theoretical analysis showing that our method recover uniform alignment classic DA methods, and achieve non-trivial alignment for other types of graphs, thereby naturally incorporating domain information represented by domain graphs. Empirical results demonstrate our method's 's superiority over state-of-the- of-the-art methods. Future work could include fusing automatic graph discovery with our method, well extending method to multiple heterogeneous domain graphs with value weights. It would also be interesting to consider other applications such as recommender systems and natural language processing.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENT
The authors thank the reviewers/AC for the constructive comments to improve the paper. HW is partially supported by NSF Grant IIS-2127918. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of the sponsors.
REFERENCES
Climate change in the contiguous united states. httpesr/g@thabb.oom/ssssiitttttt data- 2C bew.beyyooodie-eeee the limis usa 2020.
Firoj Alam, Shafiq R. Joty, and Muhammad Imran. Domain adaptation with adversarial training and graph embeddings. In Iryna Gurevych and Yusuke Miyao (eds.), ACL, pp. 1077-1087, 2018.
Shai Ben-David. John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan. A theory of learning from different domains. Machine learning, 79(1-2):151-175, 2010.
Ziliang Chen, Jingyu Zhuang, Xiaodan Liang, and Liang Lin. Blending-target domain adaptation by adversarial meta-adaptation networks. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 2248-2257, 2019.
Shuyang Dai, Kihyuk Sohn, Yi-Hsuan Tsai, Lawrence Carin, and Manmohan Chandraker. Adaptation across extreme variations using unlabeled domain bridges. arXiv preprint arXiv:1906.00 02238, 2019.
Zhengming Ding, Sheng Li, Ming Shao, and Yun Fu. Graph adaptive knowledge transfer for unsupervised domain adaptation. In ECCV, volume 1 11206, pp. 36-52, 2018
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, Franccois Laviolette, Mario Marchand, and Victor Lempitsky. Domain-adversarie training of neural networks. JMLR, ((1):2096-2030) 2016.
lan Goodfellow, Jean Pouget-Abadia Mehdi Mirza, Bing Xu, David Warde- FarleyFarly, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In NIPS, pp. 2672-2680, 2014.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In KDD, pp. 855-864, 2016.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
Thomas N Kipf and Max Welling. Semi-supervin classification with graph convolutional networks. arXiv preprint arXiv: (e..1669999999 2016a.
Thomas Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.07335 2016b.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep con- volutional neural networks. Advances in neural information processing systems, 25:1097-1105, 2012.
Seicchi Kuroki, Nontawat Charoenphakdee, Han Bao, Junya Honda, Issei Sato, and Masashi Sugiyama. Unsupervised domain adaptation based on source-guide -ource-guided discrepancy. In AAAI, pp. 4122-4129, 2019.
Edo Liberty, Zohar Karnin, Bing Xiang, Laurence Rouesnel, Baris Coskun, Ramesh Nallapati, Julio Delgado, Amir Sadoughi, Yury Astashonok, Piali Das, et al. Elastic machine learning algorithms in amazon sagemaker. In SIGMOD, pp. 731-737, 2020.
Mingsheng Long, Zhangjie Cao, Jianmin Wang, and Michael I. Jordan. Conditional adversarial domain adaptation. In NIPS, pp. 1647-1657, 2018.
Massimiliano Mancini, Samuel Rota Bulo, Barbara Caputo, and Elisa Ricci. Adagraph: Unifying predictive and continuous domain adaptation through graphs. In CVPR, pp. 6568-66 66686657, 2019.
10

---

Published as a conference paper at ICLR 2022
Le Thanh Nguyen-Meidhee Atif Belal, Madhu Kiran, Jose Dolz, Louis-Antoine Blais-Morin, and Eric Granger. Unsupervised multi-target domain adaptation through knowledge distillation. In Proceedings of the IEEE/CVF Winter Conference Applications of Computer Vision, pp. 1339- 1347, 2021.
Sinno Jialin Pan and Qiang Yang. A survey on transfer learning. TKDE, 22(10): 2009.
Sinno Jialin Pan, Ivor W Tsang, James T Kwok, and Qiang Yang. Domain adaptation via transfer component analysis. TNN, 22(2):1992210 2010.
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 NIPS, pp. 8024-8035, 2019.
Xingchao Peng, Qinxun Bai, Xide Xia, Zijun Huang, Kate Saenko, and Bo Wang. Moment matching for multi-source domain adaptation. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 1406-1415, 2019.
Xingchao Peng, Yichen Li, and Kate Saenko. Domain2vee: Domain embedding for unsupervised domain adaptation. arXiv preprint arXiv:2007.092.57 2020.
Mehmet Pilanci and Elif Vural. Domain adaptation on graphs via frequency analysis. In SIU, pp. 1-4, 2019.
Mehmet Pilanci and Elif Vural. Domain adaptation on graphs by learning aligned graph bases. TKDE, 2020.
Viraj Prabhu, Shivam Khare, Deeksha Kartik, and Judy Hoffman. Sentry: Selective entropy opti- mization via committee consistency for unsupervised domain adaptation. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp. 8558-8567, 2021.
Kuniaki Saito, Kohei Watanabe, Yoshitaka Ushiku, and Tatsuya Harada. Maximum classifier
discrepancy for unsupervised domain adaptation. In CVPR, pp. 3723-3732. 2018.
Swami Sankaranarayanan, Yogesh Balaji, Carlos D. Castillo, and Rama Chellappa. Generate to adapt: Aligning domains using generative adversarial networks. In CVPR, pp. 8503-8512. 2018.
Baochen Sun and Kate Saenko. Deep CORAL: correlation alignment for deep domain adaptation. In ICCV workshop on Transferring and Adapting Source Knowledge in Computer Vision (TASK-CV), pp. 443-450, 2016.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. In wWW, pp. 1067-1077, 2015.
Eric Tzeng, Judy Hoffman, Ning Zhang, Kate Saenko, and Trevor Darrell. Deep domain confusion: Maximizing for domain invariance. arXiv preprint 141iv:1412.3441 2014.
Eric Tzeng, Judy Hoffman, Kate Saenko, and Trevor Darrell. Adversarial discriminative domain adaptation. In CVPR, pp. 7167-7176, 2017.
Petar Velivcković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017.
Vose, S Applequist, M Squires, Durre, MJ Menne, CN Williams Jr, C Fenimore, K Gleason, and D Arndt. Gridded 5km ghen-daily temperature and precipitation dataset (nclimgrid) version 1. In Maximum Temperature, Minimum Temperature. Average Temperature, and Precipitation. 2014.
Hao Wang, Hao He, and Dina Katabi. Continuously indexed domain adaptation. ICML, 2020.
Linjie Yang, Ping Luo, Chen Change Loy, and Xiaoou Tang. A large-scale car dataset for fine ana-grained categorization and verification. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3973-3981, 2015.
Yuchen Zhang, Tianle Liu, Mingsheng Long, and Michael I Jordan. Bridging theory and algorithm for domain adaptation. arXiv preprint arXiv:1904 9904008001 2019.

---

Published as a conference paper at ICLR 2022
Han Zhao, Shanghang Zhang, Guanhang Wu, José M. F. Moura, João Paulo Costeira, and Geoffrey J.
Gordon. Adversarial multiple source domain adaptation. In NIPS, pp.
2018.
Han Zhao, Remi Tachet des Combes, Kun Zhang, and Geoffrey J. Gordon. On learning invariant representations for domain adaptation. In ICML, pp. 7523 2523,753,, 2019.
Mingmin Zhao, Shichao Yue, Dina Katabi, Tommi S. Jaakkola. and Matt T. Bianchi. Learning sleep stages from radio signals: A conditional adversarial architecture. In ICML, pp. 4100-4109, 2017.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: review of methods and applications. Al Open, 1:57-81, 2020.
A PROOF
Lemma 4.1 (Optimal Discriminator for GRDA), For fixed, the optimal D satisfies following equation,
(D(()) Eispptulee..-pttleeee
where e and e' are from the encoding space.
Proof.
With fixed, the optimal D
argmin wbw. (ttp://wwww/LaLLa/aaoaa A)) ((E(x,,,)) D A.))
argmin (e (L(((e) D(e'),
D
argmin E s) s)mple.)) Aog D(e'))) + (1g1 o(()) D(e')))
D
-argmin Ee - pe bgga (og(r( D(e'))) + Aij) a(D(e) D(e'))))
-argmin E. Fe pp log(o(((()) D(e')) + a<e, e )) log(1 (olll--(DD())) (DD(e)
D
where ale, ) Eisppule)..-p(xeee)) [Ay]] Notice that the global minimum achieved if for any (e, e'), (D(e) D(ee)) minimize the negative binary cross entropy ar(e, e') (og(a(D(e) D(e')))
(1 ale, e')) log(1 - or (D((e) D(e'))), or equivalently, o (D(()) D(e')) e').
Here we will use the chain of 3 nodes as a simple explanatory example: domain 2 is connected to both domain 1 and domain 3. Suppose data are mapped to either of the 2 encodings, e = 0 and e The probability of domain index u conditioned on encoding e (i.e., p(u e)) given in
Table 4 The discriminator will output the reconstruction result based on what encoding it obtains. For example, suppose we have two data points, 21 and #2, with their encodings e₁ = 0 and e₂ Their corresponding domain indices ij and u2 given e and e₂ follow the distributions p(uje 0) and p(uje 1). respectively. Note that here e and e2 correspond to and in Lemma 4. can obtain
while ú1 and tz correspond to i and j in Lemma 4.1 Based such realization, Emp=-e(uee-- O) mpp(alemm))) [Au = 0.38 (assuming no self-loop in the domain adjacency graph).
To minimize the loss, the optimal discriminator will then try to output a (D(e))) D(ez)) = 0.38.
Theorem 4.1 (Global Optimum for GRDA), Given an adjacency matrix A, the total loss LD F))
has tight upper bound:
E) ([)
where H denotes the entropy function, H(p) = -plog(p) - (1- p) log(1 p), and alc, c') Eis-ptulel.--ppeeeee)A Furthermore, the equality, i.e., the optimum, is achieved when
a(e,e') Er,i(Ais) for any e,e',
or equivalently, Big ( e¹] = BRg [Aig] where (e,e') is from the encoding space.
12

---

Published as a conference paper at ICLR 2022
Proof. Denoting the discriminator output of the encoding de, ie, de D(e), have
La(D, E) ((,,)),e' ()onxeeer))) A. log(o(d,. de/)) (1 A,j) log o(d de))]
(e A, log(a(c, - (1 A,,) log(1 a(e,
(6)
Fec)l-oa(c."))))0(((c - (1-a(e, log(1 - a(c,))))
(7)
E (((((())))))) (Bo.'' e')) H (I (Ac)))
Eqn. and Equ. are due to the optimal discriminator, i.e, Lemma 4.1 The inequality, i.c., Eqn.
due to the concavity of and Jensen's s inequality. The optimum achieved when a(e, e') = E,, A for any e, e', i.e. E,,j Aj e, ee B..](As)
Corollary 4.1. For GRDA, the global optimum of total loss La(D, E) is achieved if the encoding of all domains (indexed by u) are perfectly (uniformly) aligned, i.e., e 1 u.
Proof. From Theorem 4.1
we have:
La(D, E)
Ee,ed H (a(eeee))
Ea,e' H ( ptr.p
Ee,e' H ((
(10)
H. (Bpsp(u))ssp()) A.))
H (l)))
which achieves the global optimum. Note that Equ. 10 is due the perfect alignment condition, i... p(ule) = p(u).
Lemma (Optimal Predictor). Given the encoder E, the prediction loss (2(F,, E) (,(F(E(x, v) 2 (y), u, A)) where H-) is the entropy. The optimal predictor F* that
minimizes the prediction loss
F'(E(x, -
Assuming the predictor F and the discrimi- nator are trained to achieve their optimal losses, by Lemma the three-player game, min max LL),,,) can be rewritten E,F D
Table 4: Values of pl ulee) for different and
u
e
0
=
1
0.1
0.7
2
0.3
0.2
as following training procedure of the encoder E, min C(E) A ([yyB(xx u, A)) XaCa( EE), E
3
0.6
0.1
(11)
where Co(E) & minp D)= DT).
Theorem 4.2. Assuming u u,l if the encoder E, the predictor and the discriminator D have enough capucity and are trained to reuch optimum, any globul optimal encoder E" has the following properties:
(x) u, A)) (1 u, A), Ca(EE) max Ca(E'),
(12)
(13)
where H(-I-) denotes the conditional entropy.
Proof. Since Exx, u, A) a function of x, u. and A, by the data processing inequality, we
have Ex) A)) > H u, A). Hence, C(E) H(y E(x, u, A)) AsCa(E) >
H u. A) - Xa maxg Ca (E'). The equality holds and only if H (y)xx, u) = H(y E(x, u, A)) and Ca( E) maxg Ca(E'). Therefore, we only need prove that the optimal value of C(E) is
equal to H(y) x, u, A)
Xa maxg Ca(E") in order to prove that any global encoder E satisfies
both Eqn. [2 and Eqn.
13
13

---

Published as a conference paper at ICLR 2022
We show that C(E) can achieve Hy) u, A) Ya maxg' Ca(E") by considering the following encoder Eo(x, u, A) = ( u, A). It can be examined that H (y) Eo u, A)) = Hyyy/ u, A)
and (x, u, A) IL which leads to Ca(Eo) max Ca(E") using Corollary 4.1 completing the proof.
IT
Note that u u.lly is a weak assumption because it can be true even if both y 4f u|x, A and y H x/u, A true.
Corollary 4.2 (Cliques). In clique, the GRDA optimum is achieved if and only if the embedding distribations of all the domains are the same, iee. pi (e) =... PN = p(e), Ve.
Proof. We start from Theorem 4.1 For any embedding pair (e, e'), have N(N-1) B[[As]]
N E[A,yl c, c'] N2 Eis (B)()),, (,))). First, consider the case of e' c, which
leads to NNN - 1) = Ei<, (e) Since Σ; B((e) = N, we have (E, R(e))) = N2. By
the subtraction between two equations, we have Σ, (()e) = - ())
N2 N(N - N. We can further have that Σ (B:
= (N (N-
Σ k (e) = (N 1)N - N(N - 1) = 0, leading to (e = -,(e), j.. Considering
Σ (e(e) N. we have (e 1, Vi. It easily to see that the solution also satisfies the case of #
Corollary 4.3 (Star Graphs). In star graph, the GRDA optimum is achieved if and only if the embedding distribution of the center domain the average of all peripheral domains, i.e. Pi(e) = - P:(e),)) Ve.
Proof. Similarly, we start from Theorem 4.1
For any embedding pair (e, e'), we have 2(-11) N
(cc)))(()) Leveraging the fact that (e) 8 (e))) (e') 31 (e)). Let's first consider the case of = e, we have N - 11 1= (((())))((())) which means that, for any e, (1 is either
[[A = [[A,yle,eT] = 1
N2 Σ (e)
Ei=1 (e) = N, we have 2
1 or N - 1. Now consider the case of * with the constraint that B1 (e), (e') {1, 1};
the solutions are (c) = 31 (c') 1 or (e()) = =3i(c') = N - 1. for any pair (c, e²). Clearly is
not possible that a(c) N 1, Ve, since it violates the equality E. [.[1ju- 1] E.[1] Therefore
the only solution is a(e) ve, which implies that (1) x Σ Ve.
Corollary 4.4 (Chain Graphs). Let p:(e) = p(e/u i) and the average encoding distribution DN p(e u i). In chain graph, the GRDA optimum achieved if and only if
p(e) N-
N p. (())))+)(ee) p. = -((N-) 1).
p(c)p(c')
Proof. By Theorem 4.1
Ve, e'
N N
2(N 1) = 12 N2
Σ
A App((u ilepp(u jle')
=1j=1
N Aij pr(e)p(u= = Op,, (e' )r =
N-1 pe(e)pi-((e)) + p.(ee) (e)
= N2
p(e)p(e')
p(e)p(e")
which completes the proof.
Proposition 4.1 (Chain of Three Nodes). In this length three chain graph, the GRDA optimum is achieved if and only if the embedding distribution of the middle domain is the average of the embedding distributions of the domains on the two sides, i.e. p2(e) (p (e) pa pa())). Ve.
Proof. Since a chain graph of three nodes is also a star graph, we have that pz(e) = (p) ps(e)), Ve.
14

---

Published as a conference paper at ICLR 2022
Table 5: Accuracy (%) on CompCars with Mdanraph(Mancini et al.) 2019) backbone encoders. In this experiment, we used the network proposed by Adagraph and trained it with adversarial domain adaptation methods. We mark the best result with bold face and the second best results with underline.
Method
Ada Only
Ada + DANN
Ada + ADDA
Ada CDANN
Ada + MDD
Ada GRDA (Ours)
CompCars
55.05
0.87
55.87 + 1.22
55.12 1.28
55.82 1.16
56.63 0.64
56.56 0.38
B ADAGRAPH ADVERSARIAL LEARNING METHODS
sshows the results when using Adagraph(Mancinn et al. 2019) as the backbone encoders for different adversarial methods on the CompCars image classification task. From the table, could see that adversarial methods consistently improve the adaptation performance, which demonstrates the orthogonality of Adagraph and adversarial methods. In this experiment, our method GRDA achieves high accuracy and stability (the lowest standard deviation among all adversarial methods).
C SEMI-SUPERVISED METHODS
At first blush, our problem setting may look similar to semi-supervised learning (SSL) on graphs, which can be handled by graph neural networks (GNN), e.g., GCN (Kipf Welling) 201 and GAT (Velivcković et al. 2017). However, unsupervised domain adaptation (UDA) problem and SSL are very different from various perspectives.
First, in semi-supervised learning (SSL) problems, the focus is typically the whole predictor and often dictates smoothness of the predictor w.r.. the graph. In contrast, graph-relational domain alignment (GRDA) focuses the embeddings (latent representations). and allows much more flexible predictor. For example, the predictor in GRDA does not have to be smooth w.r.t. the graph.
Second, these two problems have very different assumptions. Specifically, UDA often assumes domain shift and tries to align data from different domains before learning a predictor. In contrast, SSL does not assume domain shift and directly uses unlabeled data to improve the decision boundary. Therefore, when domain shift exists, formulating the problem as UDA often leads to better accuracy.
Both our theoretical analysis and empirical results on DG-15 well DG-60 show that typical GNN-SSL methods do not work. Specifically, in this section we discuss 2 variants of GNN-SSL methods adapted for our setting:
Variant 1 (GNN-SSL-VI)) We treat each sample as a node and connect two samples their domains are the same or immediately adjacent. We then perform node classification samples.
Variant 2 (GNN-SSL-V2): We treat each domain as a node and treat each sample as a node well. Domain nodes connect to adjacent domain nodes while sample nodes only connect to domain nodes that they belong to. We then perform node classification on samples.
For Variant 1, if we use Graph Convolutional Network (GCN) our GNN, can prove the following theorem:
Theorem C.1 (Negative Results on Variant 1). For Variant 1, every node (data point) from the same domain will have the same node embedding after applying GCN.
Proof. For GCN, the (-th neural network layer will perform the operation h (1+1) = (b2))
(1) EjeNto egs n WW"), where (i))) contains the neighbours of node i, Gj ((TI
and a an activation function. (0()) is the output of the (1 - 1)-th graph convolution layer (h)0) (0) is the node feature). (')) and (( denote weight and bias of the /-th layer, respectively (Kipf & Welling 2016a).
15

---

Published as a conference paper at ICLR 2022
Table 6: Accuracy (%) on DG-15 and DG-60.
Method
Source-Only
GNN-SSL-VI GNN-SSL-V2
DANN
ADDA
CDANN
MDD
GRDA (Ours)
DG-15
39.77
50.00 50.00
60.15
72.11
69.00
72.44
51.33
84.44
DG-60
38.39
35.07
61.98
32.17
61.70
66.24
96.76
Table 7: Accuracy (%) on DG-15 and DG-60.
Method
Source-Only
SENTRY
DANN
ADDA
CDANN
MDD
GRDA (Ours)
DG-15 DG-60
39.77 38.39
43.67
72.11
69.00
72.44
51.33
84.44
47.80
61.98
32.17
61.70
66.24
96.76
Table 8: Accuracy (%) on TPT-48.
Method
Source- Onlr
SENTRY
DANN
ADDA
CDANN
MDD
GRDA (Ours)
E (24)--W (24)
1.926
2.73
2.679
2.254
2.108
1.335
1.297
N (24)-+5
2.426
9.44
2.600
2.709
2.621
2.054
1.165
Table 9: Accuracy (%) on CompCars (4-Way Classification).
Method
Source-Only SENTRY DANN
ADDA
CDANN
MDD
GRDA (Ours)
CompCars 46.5
31.39
50.2
46.1
48.2
49.0
51.0
Based on the definition of this method, if data points & and m belong to the same domain, they will have ((k)= (mm))= N (each node has self loop). Therefore we have
h (1+1)
((++1)
n )
Cjk
Gjm
JEN
19 )))()) O,
VWGIV/N((
(NGGIW((()))
JEN
completing the proof.
Theorem C.I indicates that we use GCN, the data points the same domain will obtain same prediction result (because their node embeddings are the same). This explains the experiment results in Table 6 Specifically, for binary classification tasks on DG-15 and DG-60, the number of positive and negative samples are identical in each domain. The polarized prediction (samples in the same domain are predicted as either all positive or all negative) leads to an accuracy of exactly 50%. Although use GCN as graph neural network during derivation, conclusion to other GNNs as long as they follow similar neighbour aggregation strategies.
easily generalize
For Variant 2 (GCN-SSL-V2),
conduct experiments on both DG-15 and DG-60 well. As shown in the Table 6 GCN-SSL-V2 methods perform worse than most domain adaptation baselines on DG-15, and do not even outperform Souce-Only on DG-60.
D ENTROPY-BASED DOMAIN ADAPTATION METHODS
For completeness, we include SENTRY (Prabhu al. 2021). recent entropy-based method as baseline. Essentially, entropy-based methods perform self-training by minimizing the conditional entropy of model predictions, making the predictions more confident on the target domain. Naturally such a training strategy can only work on single-source single-target adaptation. To adapt SENTRY to our tasks, we combine all the data in multiple source domains into single source domain, and similarly for multiple target domains. On DG-15 and DG-60 (Table 7). SENTRY only outperforms Source-Only; on TPT-48 (Table 8) and CompCars (Table SENTRY even underperforms Source- Only, possibly due the mixture of source data and target data.
16

---

Published as a conference paper at ICLR 2022
Model: GRDA
Model: DANN
20-
20
-20
-20
GRDA
(b) DANN
Figure 8: Visualization of the encodings of data produced DG-15.
Table 10: Accuracy of GRDA and DANN on DG-15,
Source Domains
2
4
6
GRDA DANN
64.7
74.1
81.5
84.4
100.0
42.1
44.6
33.5
72.11
88.7
E VISUALIZATION OF ENCODINGS
We also visualize the encodings of data produced on DG-15 here. All the encodings are reduced to dimensions by TSNE.
Figure (a) shows the domain graph for DG-15. To showcase GRDA's ability to align encodings
according to the domain graph, Figure [(a) plots the encodings of domains 0, 1, 7, and 9 produced by
GRDA. We can see the encodings from adjacent domains (i.e., domains 7, and 1) align with each other, while the encodings from distant domains (i.e., domains 0 and 9) do not align with each other.
This demonstrates that our model successfully relaxes uniform alignment according to the domain
graph.
Figure 8(b) shows the encodings of DANN. We can see that although domain and 9 are distant, they still align with each other, showing that classical domain adaptation methods lack the flexibility of alignment compared with GRDA.
F DATASET VISUALIZATION
Figure ((a) and 9b)) show the angle wi aresin of each domain for DG-15 and DG-60 (the angle of each ground-truth boundary w.). Figure T0 visualizes part of the TPT-48 dataset that is used for training and testing.
G THE EFFECT OF SOURCE DOMAIN NUMBERS
Table 10 provides results DG-15 for different numbers of source domains. It shows that the accuracy increases with more source domains, and that GRDA still outperforms the baselines in all cases.
17

---

Published as a conference paper at ICLR 2022
(a) DG-15
(b) DG-60
Figure 9: Visualization of the DG-15 (left) and DG-60 (right) datasets. We use 'red' and 'blue' to roughly indicate positive and negative data points inside domain. The boundaries between 'red' half circles and 'blue" half circles show the direction of ground-truth decision boundaries in the datasets.
Temperature Fahrenheit
90
80
M
70
60
50
40
30
20
10
20
40
60
80
100
120
140
Figure 10: Visualization for data of four of the states in 7PT-48, Here we show the states' monthly average temperature in Fahrenheit.
H IMPLEMENTATION DETAILS
H.1 MODEL. ARCHITECTURES
To ensure fair comparison, all algorithms use the same network architecture for the encoder and the predictor. The encoder of each model consists of 3 components.
A graph encoder embeds the domain graph A and the domain index to the domain embeddings et.
A raw data encoder embeds the data xy into data embeddings h4-
A joint encoder then takes input both and b; and produces the final embeddings.
For DG-15, DG-60 and 7P7-48, the raw data encoder contains 3 fully connected (FC) layers, and the predictor contains 3 FC layers, both with ReLU as activation functions, For CompCars, we use AlexNet (Krizhevsky et al. 2012) as the raw data encoder. All joint encoders contain FC layers.
The discriminators of different algorithms have FC layers, with slight differences on the output dimension. GRDA's discriminator produces k-dimensional node (domain) embedding.
18

---

Published as a conference paper at ICLR 2022
Ace
Source Sounce-Only Ace: 38.39%
DANN Acc: 61.98%
ADDA Ace: 32.17%
100%
Data
MDD Acc: 66.24%
CDANN Acc: 61.70%
GRDA Acc: 96.76%
Source domain
0%
Detailed results on DG-60 with 60 domains. On the left is the domain graph for DG-60. We use the 6 domains in the dashed box as source domains. On the right is the accuracy of various DA methods for each domain, where the spectrum from 'red' to 'blue' indicates accuracy from 100% to 0% (best viewed in color).
Figure 11:
H.2 OTHER HYPERPARAMETERS
For experiments on all 4 datasets, we choose i: 2. We use mixture policy for sampling nodes (domains) to train GRDA's discriminator. One method is to randomly sample several nodes, and another is to pick the nodes from randomly chosen connected uub-graphs. We pick one of the policies randomly in each iteration and calculate the loss of each forward pass. The models are trained using the Adam (Kingma & Ba 2015) optimizer with learning rates ranging from x 10 10-5 to x 10 and Xa ranging from 0.1 to 1.For each adaptation task, the input data is normalized by its mean and variance. We run all our experiments on a Tesla V100 GPU using AWS SageMaker (Liberty et al. 2020
H.3 TRAINING PROCESS
We perform the standard gradient-based alternating optimization for minimax games (e.g., DANNS and GANs); we iteratively perform the following steps: (a) optimizing discriminator D with the encoder E' and predictor F" fixed, and (b) optimizing encoder E' and predictor I' with the discriminator D fixed. Specifically:
For (a), we first use the encoder mentioned above to produce the encoding and then use the loss function in Equation (3) of the main paper to train the discriminator D. This loss function quantifies whether the node embedding reproduced by D preserves domain connection information in A.
For (b), we fix the discriminator D and minimize the predictor loss plus the negation of the discrim- inator loss (i.e., (F, F) LDD E)) train the encoder E and the predictor F. This loss function enables the encoder to preserve useful features for prediction while removing domain-related information in the encoding align different domains in the encoding space.
We perform these 2 steps iteratively until convergence.
I DETAILED RESULTS FOR EACH DOMAIN ON DG-60 AND CompCars
Figure 11 shows the detailed results on DG-60. It shows that GRDA significantly outperforms all baselines. We also include the detailed results on CompCars (Figure 12), where GRDA also outperforms all the other methods.
19

---

Published as a conference paper at ICLR 2022
ccc
Source- Only cc: 46.5%
DANN 50.2%
ADDA A 46.1%
65%
Data
MDD Ac:: 49.0%
CDANN A 48.2%
GRDA Acc: 51,0%
Source domain
30%
Figure 12: Detailed results on CompCars with 30 domains. On the left is the domain graph for CompCars. We use the domain in the dashed box the source domain. On the right the accuracy of various DA methods for each domain, where the spectrum from 'red' to 'blue' indicates accuracy from 65% 30% (best viewed color).
20


Reviews:
[{"review_id": "zBPWgB91val", "reviewer": "Reviewer_uDYW", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nStrengths:\n1.\tThis paper propose novel method multi-target domain adaptation. Authors introduce the adversarial learning method for this issue, which looks interesting.\n2.\tThe paper gives clear description about this problem, and the proposed method, which is easy to follow.\n3.\tUsing varying kinds of datasets to test the provided method, which is solid.\n4.\tI like the shown figure in this paper, which is great for me to depict how the proposed method works.\n\nWeaknesses:\n1.\tDo this proposed method for traditional domain adaptation with two domain. What I mean is to learn the graph for data instead of domain.\n2.\tThe reported results looks has little advantage compared to baselines. Do authors pay more energy and parameters ?\n\n\n--------------------After rebuttal----------------------\n\nThanks for authors' response. Authors have addresses my concerns excepting for the further experiment for two domain, which does not influence my score. After reading other reviewers' comments (e.g., on one mention the less novelty), it think the proposed method still keep advantages compared existing methods.  I would like  keep my score.", "summary_of_the_paper": "This paper explore multi-target domain adaptation by graph.  For this setting, It is not suitable to treat equally every domain, and align them all perfectly.  To remedy this problem, In this paper authors propose the graph-based method to learn the adjacency between domains.  In this paper, authors propose adversarial learning method, which refers the encoder and the discriminator. What is more,  authors show the theoretical analysis for this problem. The reported results shows that the proposed method successfully generalizes uniform alignment.", "summary_of_the_review": "It looks the proposed method is new, since it built an adversarial learning for this question. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "E_padgPh39", "reviewer": "Reviewer_rNQp", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work includes some advantages:\n1. The authors generalize the adversarial learning framework by replacing the domain discriminator with a graph discriminator.\n2. Some theoretical analyses support their claims on such a replacement.\n3. Experimental results validate the usefulness of the proposed method on domain adaption.\n\nSome concerns are listed as follows.\n1. Domain alignment has been intensively studied and graph-based domain adaptation also has been well discussed in the existing works.  There are lots of variants on the adversarial discriminator or entropy-based or distribution alignment theories. The authors fail to convince the reviewer the proposed graph discriminator is better than the original adversarial discriminator or its variants, although they present a series of theorems and corollaries in the support section. To me, adversarial discriminators are more general than the given graph discriminator.\n2. Graph-based discriminator has appeared in the existing works. The authors should give the reviewer a full explanation of your contributions.\n3. For experiments, there are many advanced SOTA works, while the authors mainly compared some conventional methods, which are not the SOTA domain adaption works.\n4. If the proposed method can replace the original adversarial works, this paper could be rated a high score for acceptance. The authors should pay more attention to the advantages of the proposed methods, and how could you make your work outperform these popular works, which is also the goal of ICLR.", "summary_of_the_paper": "This work optimizes the adversarial domain adaption model by generalizing the uniform domain alignment with a domain encoding graph. The proposed method is simple and easy to follow, and the overall idea is clearly described. Some experiments show the effectiveness of the proposed method on both synthetic and real-world datasets. ", "summary_of_the_review": "This paper proposes a new graph discriminator to replace the conventional adversarial discriminator in adversarial domain adaptation. Some theoretical and experimental analyses validate their claims, while some concerns should be clarified and improved.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "350prKu96dF", "reviewer": "Reviewer_n4Lk", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Some specific comments are as follows:\n\nPros:\n- Paper presents interesting ideas on how to utilize the original topological structures among different domains to benefit the domain adaptation results. The idea of using a discriminator to reconstruct rather than classify is novel.\n- Very detailed theoretical analysis is provided which makes the result be persuasive.\n- Experiments are well thought out and highlight the parameter study which makes the results of the work reproducible.\n\nCons:\n- Lemma 4.1 “Optimal Discriminator for GRDA”. This lemma is intuitively correct. However, the authors don’t show the strict analysis to this basic assumption, that is, the optimal discriminator will output the conditional expectation of A_ij over all possible combinations of domain pairs (i, j) sampled from p(u|e) and p(u|e’). Maybe giving an example would help readers understand this better.\n- Proposition 4.1 “Chain of Three Nodes”. This is a very interesting idea. However, there is no strict proof provided. \n- The authors didn’t analyze why the change of the task of discriminator from classification to generation would help the model’s performance in domain adaptation. Some intuitive analysis would not be enough.\n", "summary_of_the_paper": "This paper proposes a new model called GRDA to relax the uniform alignment which ignores topological structures among different domains. GRDA uses a domain graph to encode domain adjacency. The authors also generalize the existing adversarial learning framework with a novel graph discriminator using encoding conditioned graph embeddings. Detailed math inductions and proofs are given. Empirical results on both synthetic and real-world datasets demonstrate the superiority of this method.", "summary_of_the_review": "Overall, being among the few papers that venture into the domain adaptation of graph, the paper introduces a number of new concepts and mechanisms. This framework is promising.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes to leverage topological structure between domains, expressed as a graph, towards solving the domain adaptation problem.

Reviewer n4Lk thought the ideas were interesting, appreciated the theoretical analysis and indicated that the experiments were “well thought out”. The reviewer asked for more detail on Lemma 4.1 and suggested that a proof be provided for Proposition 4.1. They asked for more justification on why the change of task for the discriminator from classification to generation would improve performance. The authors responded to these comments, clarifying the proof of Lemma 4.1 in the appendix. They clarified that proposition 4.1 can be derived from Corollary 4.3 or Corollary 4.4. On the point of classical vs. enhanced discriminator the authors provided additional experiments. 

Reviewer rNQp commented that the method was easy to follow and noted the theoretical and empirical analysis. They expressed some concern that previous work on graph-based domain adaptation was inadequately addressed. Like reviewer n4Lk they seemed unconvinced that the proposed graph discriminator was an improvement over past SOTA and questioned its novelty. In terms of claims about novelty and competitiveness relative to previous works I would have liked to see the reviewer make specific references rather than criticize in general terms. The authors’ responded to the reviewer, adding a recent entropy-based method (SENTRY) to the experiments and showed that their method outperformed this ICCV 2021 work by a large margin. They responded to the reviewer’s remarks about the original discriminator and variants, pointing out that this was already established in the paper. They used the other reviews to dispute the claim of lack of novelty. 

Reviewer uDYW felt that the work was novel and interesting. Like rNQp they thought the paper was clear. They questioned the practical advantage over baselines. The authors responded to the reviewer’s question about using a data graph. They responded to the question about parameter tuning and computational cost. They addressed the question about limited improvements in real-world datasets.

I had some difficulty motivating the reviewers to engage in the discussion and acknowledge the authors’ response. The authors also politely attempted to nudge the reviewers to consider their updated results. In my opinion, the author responses have addressed most of the reviewer concerns  and I don’t see any critical issues remaining. Therefore I think that this paper should be accepted as a poster.
Decision: Accept (Poster)