Year: 2021

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 encodingconditioned 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.

heading: 1 INTRODUCTION
text: 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 in 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 so that a 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 to 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 to 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., 2020). Such heterogeneity can often be captured by a graph, where the domains realize the nodes, and the adjacency between two domains can be captured by an edge (see Fig. 1). For example, to capture the similarity of weather in the US, we can construct a graph where each state is treated as a node and the physical proximity between two states results in an edge. There are also many
other scenarios where the relation among domains can be naturally captured by a graph, such as the taxonomies of products in retail or connections among research fields of academic papers. Given a domain graph, we can tailor the adaptation of domains to the graph, rather than dictating the data from all the domains to align perfectly regardless of the graph structure.
One naïve DA method for such graph-relational 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 graphrelational domains, we argue that an ideal method should (1) only enforce uniform alignment when the domain graph is a 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 a clique, and realizes intuitive alignments for other types of graphs such as chains and stars (see Fig. 4). 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 on a graph. • We provide theoretical analysis showing that at equilibrium, our method can retain the capability of uniform alignment when the domain graph is a 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-art DA methods.

heading: 2 RELATED WORK
text: Adversarial Domain Adaptation. There have been extensive prior works on domain adaptation (Pan & Yang, 2009; Pan et al., 2010; Long et al., 2018; Saito et al., 2018; Sankaranarayanan et 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’ statistics (Pan et al., 2010; Tzeng et al., 2014; Sun & Saenko, 2016; Peng et al., 2019; Nguyen-Meidine 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; Zhao et al., 2019), its ability to train end-to-end with neural networks, and consequently its promising empirical performance. These methods typically treat every domain equally and enforce 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 to fool the discriminator that classifies the domain index. In contrast, we naturally relax such uniform alignment using a graph discriminator to reconstruct a domain graph that describes domain adjacency.
Domain Adaptation Related to Graphs. There are also works related to both DA and graphs. Usually they focus on adaptation between two domains where data points themselves are graphs. For example, (Pilancı & Vural, 2019; Pilanci & Vural, 2020) use frequency analysis to align the data graphs between the source domain and the target domains, and (Alam et al., 2018; Ding et 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 a node). Therefore the methods above are not applicable to our setting. Note that (Mancini et al., 2019) uses metadata-weighted 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 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 a natural but unobserved graph relation among domains.

heading: 3 METHOD
text: In this section, we will first briefly introduce the problem setting and then elaborate our domain adaptation method.

heading: 3.1 PROBLEM SETTING AND NOTATION
text: We focus on the unsupervised domain adaptation setting with N domains in total. Each domain has a discrete domain index u ∈ U = [N ] , {1, . . . , N}, belonging to either the source domain index set Us or the target domain index set Ut. The relationship between domains is described by a domain graph with the adjacency matrix A = [Aij ], where i and j index nodes (domains) in the graph. Given labeled data {(xsl , ysl , usl )}nl=1 from source domains (usl ∈ Us), unlabeled data {xtl , utl}ml=1 from target domains (utl ∈ Ut), and the domain graph described by A, we want to predict the label {ytl}ml=1 for data from target domains. Note that the domain graph is defined on domains with each domain (node) containing multiple data points.

heading: 3.2 GRAPH-RELATIONAL DOMAIN ADAPTATION (GRDA)
text: 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 a datum xl, the associated domain index ul, and the adjacency matrix A to generate an encoding el = E(xl, ul,A), (2) a predictor F , which makes predictions based on the encoding el, and (3) a graph discriminator D, which guides the encoding to adapt across graph-relational domains. Specifically, the discriminator D takes in a mini-batch of B encodings el (l ∈ [B]), and tries to reconstruct the domain graph A. By letting the encoder E play adversarially against the discriminator D, the graph-relational information of domains will be removed from the encoding el 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. 2.
Formally, GRDA performs a minimax optimization with the following loss function:
min E,F max D
Lf (E,F )− λdLd(D,E), (1)
where Lf (E,F ) is the predictor loss and Ld(D,E) is the discriminator loss, and λd is a hyperparameter balancing them two. Below we discussed these two terms in detail.
Predictor. In Eqn. 1, the predictor loss Lf (E,F ) is defined as
Lf (E,F ) , Es[hp(F (E(xl, ul,A)), y)],
where the expectation Es is taken over the sourcedomain data distribution ps(x, y, u). hp(·, ·) is a predictor loss function for the task (e.g., L2 loss for regression).
Encoder and Node Embeddings. Given an input tuple (xl, ul,A), the encoder E first computes a graph-informed domain embedding zul based on the domain index ul and the domain graph A. Then we feed zul along with xl into a neural network to obtain the final encoding el. Formally we have
el = E(xl, ul,A) = f(xl, zul), (2)
where f(·, ·) is 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 a bijection to the set of domains [N ]). Here we pre-train the embeddings by a 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 i and j are sampled independently and identically from the marginal domain index distribution p(u); the reconstruction loss is written as
Lg = Ei,j∼p(u)[−Aij log σ(z>i zj)− (1−Aij) log(1− σ(z>i zj))],
where σ(x) = 11+e−x is 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, u,A), for all the methods in the experiments of Sec. 5.
Graph Discriminator. The discriminator loss Ld(D,E) in Eqn. 1 is defined as
Ld(D,E) ,E(x1,u1),(x2,u2)[h(x1, u1,x2, u2)], (3) h(x1, u1,x2, u2) =−Au1,u2 log σ(ẑ>1 ẑ2)− (1−Au1,u2) log(1− σ(ẑ>1 ẑ2),
where ẑ1 = D(E(x1, u1,A)), ẑ2 = D(E(x2, u2,A)) are the discriminator’s reconstructions of node embeddings. The expectation E is taken over a pair of i.i.d. samples (x1, u1),(x2, u2) from the joint data distribution p(x, u). The discriminator loss Ld(D,E) essentially quantifies how well the reconstructed node embedding ẑ1, ẑ2 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 el, the optimal encoder E will have to remove all the information regarding graph-relational domains in the encoding el, thus successfully adapting across graph-relational domains. We will formally elaborate the above arguments further in the next section.

heading: 4 THEORY
text: 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) encoderE tries to prevent such reconstruction. To gain more insight on the encoding alignment, we then further discuss the implication of these general theoretical results on GRDA’s global optimum using simple example graphs such as cliques, stars, and chains. All proofs of Lemmas and Corollaries can be found in Appendix A.

heading: 4.1 ANALYSIS FOR GRDA
text: 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 E min D Ld(D,E), (4)
where Ld(D,E) is defined in Eqn. 3.
Lemma 4.1 below analyzes the optimal graph discriminator D given a fixed joint encoder E. Intuitively, 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, j) sampled from p(u|e) and p(u|e′). Lemma 4.1 (Optimal Discriminator for GRDA). For E fixed, the optimal D satisfies following equation,
σ(D(e)>D(e′)) = Ei∼p(u|e),j∼p(u|e′)[Aij ],
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 a tight upper bound:
Ld(D,E) ≤ H(Ee,e′α(e, e′)) = H(Ei,j [Aij ]), where H denotes the entropy function, H(p) = −p log(p) − (1 − p) log(1 − p), and α(e, e′) = Ei∼p(u|e),j∼p(u|e′)[Aij ]. Furthermore, the equality, i.e., the optimum, is achieved when
α(e, e′) = Ei,j [Aij ], for any e, e′, or equivalently, Ei,j [Aij |e, e′] = Ei,j [Aij ], where (e, e′) is from the encoding space.
Proof. Denoting the discriminator output of the encoding e as de, i.e, de = D(e), we have
Ld(D,E) = E(e,i),(e′,j)∼pE(e,u)[−Aij log(σ(d > e de′))− (1−Aij) log(1− σ(d>e de′))]
= E(e,i),(e′,j)[−Aij log(α(e, e′))− (1−Aij) log(1− α(e, e′))] (5) = Ee,e′ [−α(e, e′) log(α(e, e′))− (1− α(e, e′)) log(1− α(e, e′))] (6) = Ee,e′H(α(e, e′)) (7) ≤ H(Ee,e′α(e, e′)) = H(Ei,j [Aij ]), (8)
Eqn. 5 and Eqn. 6 are due to the optimal discriminator, i.e., Lemma 4.1. The inequality, i.e., Eqn. 8, is due to the concavity of H and Jensen’s inequality. The optimum achieved when α(e, e′) = Ei,j [Aij ] for any e, e′, i.e. Ei,j [Aij |e, e′] = Ei,j [Aij ].
Essentially, Theorem 4.1 shows that if trained to the global optimum, GRDA aligns the domain distribution p(u|e) for all locations in the embedding space such that α(ei, ej) is identical to the constant, Eij [Aij ], for any pair (ei, ej).
We can directly apply Theorem 4.1 to evaluate the training process. During training, if the discriminator loss finally converges to the theoretical optimum H(Ei,j [Aij ]) (Figure 3), we 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 Ld(D,E) is achieved if the encoding of all domains (indexed by u) are perfectly (uniformly) aligned, i.e., e ⊥ u.
Note that replacing the inner product inside σ(·) with other functions (e.g., L2 distance) does not change Lemma 4.1 and Theorem 4.1, as long as cross-entropy loss is used to consider both positive and negative edges in the graph.
We can also analyze the full game as defined in Eqn. 1 (see the Appendix for details). Theorem 4.2. If the encoder E, the predictor F and the discriminator D have enough capacity and are trained to reach optimum, any global optimal encoder E∗ has the following properties:
H(y|E∗(x, u,A)) = H(y|x, u,A), (9) where H(·|·) denotes the conditional entropy.
Theorem 4.2 implies that, at equilibrium, the optimal joint encoder E produces encodings that preserve all the information about the label y contained 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 .

heading: 4.2 IMPLICATION OF GRDA’S GLOBAL OPTIMUM
text: Sec. 4.1 analyzes the global optimum of GRDA in its general form. In this section, we further discuss the implication of these general theoretical results using simple example graphs such as cliques, stars, and chains; we show that GRDA’s global optimum actually translates to domain-graph-informed constraints on the embedding distributions of every domain.
With N domains in total, we assume each domain contains the same amount of data, i.e. p(u = 1) = · · · = p(u = N) = N−1. We further use pi(e) as a shorthand for p(e|u = i), the embedding distribution in domain i. With our assumption, the marginal embedding distribution is the average embedding distribution over all domains, i.e., p(e) = N−1 ∑N i=1 pi(e). We define βi(e) = pi(e)/p(e), as the ratio between domain-specific embedding distribution and the marginal embedding distribution.
Figure 4: Example domain graphs as discussed in Sec. 4.2. Left: Cliques. Middle: Star graphs. Right: Chain graphs.
Cliques (Fully Connected Graphs). In this example, the N domains in our domain graph are fully connected, i.e. there is an edge between any pair of domains, as shown in Fig. 4 (left).
Corollary 4.2 (Cliques). In a clique, the GRDA optimum is achieved if and only if the embedding distributions of all the domains are the same, i.e. p1(e) = · · · = pN (e) = p(e),∀e.
Proof. We start from Theorem 4.1. For any embedding pair (e, e′), we have N(N−1)N2 = E[Aij ] = E[Aij |e, e′] = 1N2 ∑ i<j(βi(e)βj(e ′) + βi(e ′)βj(e)). First, consider the case of e′ = e, which
leads to N(N − 1) = ∑ i<j 2βi(e)βj(e). Since ∑ i βi(e) = N , we have ( ∑ i βi(e))
2 = N2. By the subtraction between two equations, we have ∑ i βi(e) 2 = ( ∑ i βi(e)) 2 − ∑ i<j 2βi(e)βj(e) =
N2 −N(N − 1) = N . We can further have that ∑ i<j(βi(e)− βj(e))2 = (N − 1)( ∑ i βi(e)
2)−∑ i<j 2βi(e)βj(e) = (N − 1)N −N(N − 1) = 0, leading to βi(e) = βj(e),∀i 6= j. Considering∑N i=1 βi(e) = N , we have βi(e) = 1,∀i. It is easily to see that the solution also satisfies the case of e 6= e′.
Interestingly, Corollary 4.2 shows that at equilibrium, GRDA recovers the uniform alignment of classic domain adaptation methods when the domain graph is a 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.
Star Graphs. In this example, we haveN domains forming a star graph (as shown in Fig. 4 (middle)), where domain 1 is the center of the star while all other domains are connected to domain 1.
Corollary 4.3 (Star Graphs). In a 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. p1(e) = 1 N−1 ∑N i=2 pi(e),∀e.
Corollary 4.3 shows that compared to cliques, GRDA enforces a much more flexible alignment when the domain graph is a 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 a chain, i.e., domain i is only connected to domain i − 1 (unless i = 1) and domain i + 1 (unless i = N ), as shown in Fig. 4 (right).
Corollary 4.4 (Chain Graphs). Let pi(e) = p(e|u = i) and the average encoding distribution p(e) = N−1 ∑N i=1 p(e|u = i). In a chain graph, the GRDA optimum is achieved if and only if ∀e, e′
N−1∑ i=1 pi(e)pi+1(e ′) + pi(e ′)pi+1(e) p(e)p(e′) = 2(N − 1).
Corollary 4.4 shows that in a chain graph of N domains, direct interactions only exist in domain pairs(i, i− 1) (i.e., consecutive domains in the chain). Chain of Three Nodes. To gain more insight, below we analyze a special case of chain graphs with three domains, i.e., a chain graph of three nodes as the domain graph, where domain 2 is connected to both domain 1 and domain 3. Note that this is also a special case of star graphs, with one center node and two peripheral nodes. By Corollary 4.3 or Corollary 4.4, we can prove the following Proposition 4.1.
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) = 12 (p1(e) + p3(e)),∀e.
Proposition 4.1 states that, for a chain graph of 3 domains, GRDA relaxes classical DA requiring perfect alignment of embedding distributions, and instead only requires linear interpolation/extrapolation relations among embedding distributions. Fig. 5 shows a simple example. If domain 2 (the center domain) is the target domain while others are source domains, GRDA interpolates the embedding distribution of domain 2 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 1 and 2.
The theorems above show that GRDA can enforce different levels of alignment, from perfect alignment to linearly interpolating/extrapolating embedding distributions, according to the domain graph.

heading: 5 EXPERIMENTS
text: In this section, we compare GRDA with existing methods on both synthetic and real-world datasets.

heading: 5.1 DATASETS
text: DG-15. We make a 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 [ai, bi] as the node embedding for each domain i and denote the angle of the unit vector as ωi = arcsin( biai ). We then randomly generate positive data (x, 1, i) and negative data (x, 0, i) from two different 2-dimensional Gaussian distributions, N (µi,1, I) and N (µi,0, I), respectively, where µi,1 = [ ωi π ai, ωi π bi] and µi,0 = [− ωi π ai,− ωi π bi]. To construct the domain graph, we sample Aij ∼ Bern(0.5aiaj+0.5bibj+0.5), where Bern(θ) is a Bernoulli distribution with the parameter θ. With such a generation process, domains with similar node embeddings [ai, bi] will (1) have similar µi,1 and µi,0, indicating similar decision boundaries, and (2) are more likely to have an edge in the domain graph. We select 6 connected domains as 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 as DG-15, except that it contains 60 domains, with 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 in Fig. 6:
• E (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, as shown in Fig. 6.
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 car type based on the image, with each view point and each YOM as a seperate domain. We choose a subset of CompCars with 4 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 × 6 YOMs) and 24,151 images in all. We choose cars with front view and being produced in 2009 as a 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 if their viewpoints are ’F’ and ’FS’, respectively.

heading: 5.2 BASELINES AND IMPLEMENTATION
text: We compared our proposed GRDA with state-of-the-art 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 et 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, 2016a; Zhou et al., 2020). We prove that the first variant cannot work (Theorem C.1), and our experiments show that the second variant performs worse than most domain adaptation baselines (see the Appendix for details). All the algorithms are implemented in PyTorch (Paszke et al., 2019) and the balancing hyperparameter λd is chosen from 0.1 to 1 (see the Appendix for more details on training). Note that since MDD is originally designed for classification tasks, we replace its cross-entropy loss with an 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 z as inputs to the encoder (as mentioned in Eqn. 2).

heading: 5.3 RESULTS
text: DG-15 and DG-60. We show the accuracy of the compared methods in Table 7. Based on the table, 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 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 shows the accuracy of different DA methods on DG-15 for each domain, where the spectrum from ‘red’ to ‘blue’ indicates accuracy from 100% to 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 50% for every domain.
TPT-48. Table 2 shows the mean square error (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)→ S (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, we also report more fine-grained results to see how the error distributes across different target domains. Specifically, Table 2 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).

heading: 6 CONCLUSION
text: In this paper, we identify the problem of adaptation across graph-relational domains, i.e., 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 in 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 superiority over state-of-the-art methods. Future work could include fusing automatic graph discovery with our method, as well as extending our method to multiple or heterogeneous domain graphs with real-value weights. It would also be interesting to consider other applications such as recommender systems and natural language processing.

heading: A PROOF
text: Lemma 4.1 (Optimal Discriminator for GRDA). For E fixed, the optimal D satisfies following equation,
σ(D(e)>D(e′)) = Ei∼p(u|e),j∼p(u|e′)[Aij ], where e and e′ are from the encoding space.
Proof. With E fixed, the optimal D is argmin
D E(x,j),(x′,j)∼p(x,u)[Ld(D(E(x, u,A))>D(E(x′, zj)),Aij)]
= argmin D
E(e,j),(e′,j)∼p(e,u)[Ld(D(e)>D(e′),Aij)]
= argmin D
E(e,j),(e′,j)∼p(e,u)[Aij log(σ(D(e)>D(e′))) + (1−Aij) log(1− σ(D(e)>D(e′)))]
= argmin D
Ee,e′∼p(e)Ei∼p(u|e),j∼p(u|e′)[Aij log(σ(D(e)>D(e′))) + (1−Aij) log(1− σ(D(e)>D(e′)))]
= argmin D
Ee,e′∼p(e)[α(e, e′) log(σ(D(e)>D(e′))) + (1− α(e, e′)) log(1− σ(D(e)>D(e′)))]
where α(e, e′) = Ei∼p(u|e),j∼p(u|e′)[Aij ]. Notice that the global minimum is achieved if for any (e, e′), σ(D(e)>D(e′)) minimize the negative binary cross entropy α(e, e′) log(σ(D(e)>D(e′)))+ (1− α(e, e′)) log(1− σ(D(e)>D(e′))), or equivalently, σ(D(e)>D(e′)) = α(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 = 1. The probability of domain index u conditioned on encoding e (i.e., p(u|e)) is 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, x1 and x2, with their encodings e1 = 0 and e2 = 1. Their corresponding domain indices u1 and u2 given e1 and e2 follow the distributions p(u|e = 0) and p(u|e = 1), respectively. Note that here e1 and e2 correspond to e and e′ in Lemma 4.1, while u1 and u2 correspond to i and j in Lemma 4.1. Based on such a realization, we can obtain Eu1∼p(u|e=0),u2∼p(u|e=1)[Au1u2 ] = 0.38 (assuming no self-loop in the domain adjacency graph). To minimize the loss, the optimal discriminator will then try to output σ(D(e1)>D(e2)) = 0.38.
Theorem 4.1 has been proved in the paper. We repeat it here for reference. Theorem 4.1 (Global Optimum for GRDA). Given an adjacency matrix A, the total loss Ld(D,E) has a tight upper bound: Ld(D,E) ≤ H(Ee,e′α(e, e′)) = H(Ei,j [Aij ]),
where H denotes the entropy function, H(p) = −p log(p) − (1 − p) log(1 − p), and α(e, e′) = Ei∼p(u|e),j∼p(u|e′)[Aij ]. Furthermore, the equality, i.e., the optimum, is achieved when
α(e, e′) = Ei,j [Aij ], for any e, e′, or equivalently, Ei,j [Aij |e, e′] = Ei,j [Aij ], where (e, e′) is from the encoding space. Corollary 4.1. For GRDA, the global optimum of total loss Ld(D,E) is achieved if the encoding of all domains (indexed by u) are perfectly (uniformly) aligned, i.e., e ⊥ u.
Proof. From Theorem 4.1, we have: Ld(D,E) = Ee,e′H(α(e, e′))
= Ee,e′H(Ei∼p(u|e),j∼p(u|e′)Aij) = Ee,e′H(Ei∼p(u),j∼p(u)Aij) (10) = H(Ei∼p(u),j∼p(u)[Aij ]) = H(Ei,j [Aij ]),
which achieves the global optimum. Note that Eqn. 10 is due to the perfect alignment condition, i.e., p(u|e) = p(u).
Lemma (Optimal Predictor). Given the encoder E, the prediction loss Vp(F,E) , Lp(F (E(x, u)), y) ≥ H(y|E(x, u,A)) where H(·) is the entropy. The optimal predictor F ∗ that minimizes the prediction loss is
F ∗(E(x, u,A)) = Py(·|E(x, u,A)).
Assuming the predictor F and the discriminator D are trained to achieve their optimal losses, by Lemma , the three-player game, min
E,F max D Lf (E,F ) − Ld(D,E), can be rewritten as following training procedure of the encoder E,
min E
C(E) , H(y|E(x, u,A))− λdCd(E), (11)
where Cd(E) , minD Ld(E,D) = Ld(E,D∗E).
Theorem 4.2. Assuming u ⊥y, if the encoder E, the predictor F and the discriminator D have enough capacity and are trained to reach optimum, any global optimal encoder E∗ has the following properties:
H(y|E∗(x, u,A)) = H(y|x, u,A), (12) Cd(E
∗) = max E′ Cd(E ′), (13)
where H(·|·) denotes the conditional entropy.
Proof. Since E(x, u,A) is a function of x, u, and A, by the data processing inequality, we have H(y|E(x, u,A)) ≥ H(y|x, u,A). Hence, C(E) = H(y|E(x, u,A)) − λdCd(E) ≥ H(y|x, u,A)− λdmaxE′ Cd(E′). The equality holds if and only if H(y|x, u) = H(y|E(x, u,A)) and Cd(E) = maxE′ Cd(E′). Therefore, we only need to prove that the optimal value of C(E) is equal to H(y|x, u,A) − λdmaxE′ Cd(E′) in order to prove that any global encoder E∗ satisfies both Eqn. 12 and Eqn. 13.
We show that C(E) can achieve H(y|x, u,A) − λdmaxE′ Cd(E′) by considering the following encoder E0(x, u,A) = Py(·|x, u,A). It can be examined that H(y|E0(x, u,A)) = H(y|x, u,A) and E0(x, u,A) ⊥u which leads to Cd(E0) = maxE′ Cd(E′) using Corollary 4.1, completing the proof.
Note that u ⊥y is a weak assumption because it can be true even if both y 6⊥⊥ u|x,A and y 6⊥⊥ x|u,A are true.
Corollary 4.3 (Star Graphs). In a 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. p1(e) = 1 N−1 ∑N i=2 pi(e),∀e.
Proof. Similarly, we start from Theorem 4.1. For any embedding pair (e, e′), we have 2(N−1)N2 = E[Aij ] = E[Aij |e, e′] = 1N2 ∑N i=2(β1(e)βi(e
′) + β1(e ′)βi(e)). Leveraging the fact that∑N
i=1 βi(e) = N , we have 2(N−1) = β1(e)(N−β1(e′))+β1(e′)(N−β1(e)). Let’s first consider the case of e′ = e, we have N − 1 = β1(e)(N − β1(e)) which means that, for any e, β1(e) is either 1 or N − 1. Now consider the case of e′ 6= e with the constraint that β1(e), β1(e′) ∈ {1, N − 1}; the solutions are β1(e) = β1(e′) = 1 or β1(e) = β1(e′) = N − 1, for any pair (e, e′). Clearly it is not possible that α(e) = N − 1,∀e, since it violates the equality Ee[1|u = 1] = Ee[1]. Therefore the only solution is α(e) = 1,∀e, which implies that p1(e) = 1N−1 ∑N i=2 pi(e),∀e.
Corollary 4.4 (Chain Graphs). Let pi(e) = p(e|u = i) and the average encoding distribution p(e) = N−1 ∑N i=1 p(e|u = i). In a chain graph, the GRDA optimum is achieved if and only if ∀e, e′
N−1∑ i=1 pi(e)pi+1(e ′) + pi(e ′)pi+1(e) p(e)p(e′) = 2(N − 1).
Proof. By Theorem 4.1, ∀e, e′ 2(N − 1) = N2E[Aij |e, e′] = N2 N∑ i=1 N∑ j=1 Aijp(u = i|e)p(u = j|e′)
= N2 N∑ i=1 N∑ j=1 Aij pi(e)p(u = i)pj(e ′)p(u = j) p(e)p(e′) = N−1∑ i=1 pi(e)pi+1(e ′) + pi(e ′)pi+1(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) = 12 (p1(e) + p3(e)),∀e.
Proof. Since a chain graph of three nodes is also a star graph, we have that p2(e) = 12 (p1(e) + p3(e)),∀e.

heading: B ADAGRAPH + ADVERSARIAL LEARNING METHODS
text: Tabel 5 shows the results when using Adagraph(Mancini et al., 2019) as the backbone encoders for different adversarial methods on the CompCars image classification task. From the table, we 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).

heading: C SEMI-SUPERVISED METHODS
text: 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, 2016a) and GAT (Velivcković 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 on the whole predictor and it often dictates smoothness of the predictor w.r.t. the graph. In contrast, graph-relational domain alignment (GRDA) focuses on the embeddings (latent representations), and allows a 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 as well as 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-V1): We treat each sample as a node and connect two samples if their domains are the same or immediately adjacent. We then perform node classification on samples.
For Variant 1, if we use Graph Convolutional Network (GCN) as our GNN, we 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 l-th neural network layer will perform the operation h(l+1)i = σ(b (l) +∑
j∈N (i) 1 cji h (l) j W
(l)), where N (i) contains the neighbours of node i, cij = √ |N (j)| √ |N (i)|,
and σ is an activation function. h(l)i is the output of the (l− 1)-th graph convolution layer (h (0) i is the node feature). W (l) and b(l) denote weight and bias of the l-th layer, respectively (Kipf & Welling, 2016a).
Based on the definition of this method, if data points k and m belong to the same domain, they will have N (k) = N (m) = N (each node has a self loop). Therefore we have
h (l+1) k − h (l+1) m = σ( ∑ j∈N ( 1 cjk h (l) j − 1 cjm h (l) j )W (l))
= σ( ∑ j∈N ( 1√ |N (j)| √ |N (k)| h (l) j − 1√ |N (j)| √ |N (m)| h (l) j )W (l)) = 0,
completing the proof.
Theorem C.1 indicates that if we use GCN, the data points in 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 we use GCN as our graph neural network during derivation, we can easily generalize our conclusion to other GNNs as long as they follow similar neighbour aggregation strategies.
For Variant 2 (GCN-SSL-V2), we conduct experiments on both DG-15 and DG-60 as 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 VISUALIZATION OF ENCODINGS
We also visualize the encodings of data produced on DG-15 here. All the encodings are reduced to 2 dimensions by TSNE.
Figure 9(a) shows the domain graph for DG-15. To showcase GRDA’s ability to align encodings according to the domain graph, Figure 8(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 9, 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 0 and 9 are distant, they still align with each other, showing that classical domain adaptation methods lack the flexibility of alignment compared with GRDA.

heading: E DATASET VISUALIZATION
text: Figure 9(a) and 9(b) show the angle ωi = arcsin( biai ) of each domain for DG-15 and DG-60 (the angle of each ground-truth boundary is ωi). Figure 10 visualizes a part of the TPT-48 dataset that is used for training and testing.

heading: F THE EFFECT OF SOURCE DOMAIN NUMBERS
text: Table 7 provides results on 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.
G IMPLEMENTATION DETAILS
G.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 ul to the domain embeddings el.
• A raw data encoder embeds the data xl into data embeddings hl.
• A joint encoder then takes as input both el and hl and produces the final embeddings.
For DG-15, DG-60 and TPT-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 2 FC layers.
The discriminators of different algorithms all have 6 FC layers, with slight differences on the output dimension. GRDA’s discriminator produces a k-dimensional node (domain) embedding.
G.2 OTHER HYPERPARAMETERS
For experiments on all 4 datasets, we choose k = 2. We use a 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 sub-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 1× 10−5 to 1× 10−4, and λd 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).
G.3 TRAINING PROCESS
We perform the standard gradient-based alternating optimization for minimax games (e.g., DANNs and GANs); we iteratively perform the following 2 steps: (a) optimizing discriminator D with the encoderE and predictor F fixed, and (b) optimizing encoderE and predictor F 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 discriminator loss (i.e., Lf (E,F ) − λdLd(D,E)) to 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 to align different domains in the encoding space.
We perform these 2 steps iteratively until convergence.
H 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.

heading: I CODE
text: We attach the code for GRDA on DG-15. Please refer to "README.md" in "GRDA_toy.zip" for instructions on running the code.

Review summaries:
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.

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.

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.