Domain Adaptive Classification on Heterogeneous Information Networks

1 Introduction

Heterogeneous Information Networks (HIN) are one of the most prevalent data structures and have been wildly utilized to store complex relational data. Node classification in HINs is an important but equally challenging task in that HINs contain various types of nodes and edges, hence rich semantics. Up to now, many representation learning or collective classification models have been proposed to support semi-supervised classification on HINs [Zhang et al., 2018; Wang et al., 2019].

∗Corresponding author

However, supervised models highly rely on labeled data, which may be costly or even impossible to obtain for complex structures like HINs [Jin et al., 2020]. As a result, we intuitively resort to transfer learning when labeled data on HINs are scarce.

Domain Adaptation (DA), which supports transfer learning from a source domain with sufficient labeled data to an unlabeled target domain by minimizing their domain discrepancy [Mansour et al., 2009; Long et al., 2015], has already caught interests from Computer Vision (CV) and Natural Language Processing (NLP) [Long et al., 2018; Rozantsev et al., 2018]. Domain adaptation methods, such as Maximum Mean Discrepancy (MMD) [Dziugaite et al., 2015] and Generative Adversarial Network (GAN) [Goodfellow et al., 2014], are able to align the embedding distributions of different domains, enabling the transfer of downstream machine learning models. We hence resort to DA techniques as potential solutions to the problem of transfer learning on HINs.

Many embedding models on HINs apply a multi-channel architecture based on meta-paths [Sun et al., 2011], where nodes are projected to several embedding spaces through multiple GNN channels before finally fused to a single collection of representations for downstream tasks [Zhang et al., 2018]. While it seems that transferable classification on HINs can be accomplished by simply adding a regularization to such an architecture to minimize distribution discrepancy, it should be noted that the heterogeneity and rich semantics of HINs pose specific challenges:

• HINs feature multiple levels of semantics where domain alignment should be done, which makes it difficult to simultaneously align them in a single embedding space.
• Domain adaptation underscores domain invariant features, which are likely to be homogeneous and uninformative for classification [Chen et al., 2019]. On the other hand, features indicative for classification are generally domain-variant. We hence conclude that the tradeoff between transfer and classification, domain similarity and distinguishability is necessary for the task of DA, especially on HINs where classification is hard.

To solve these problems, in this paper we propose Multi- Space Domain Adaptive Classification (MuSDAC) 1 , which adopts multi-channel shared weight GCNs [Kipf and Welling, 2016] to project the nodes from both source and target domains to multiple embedding spaces, where multi-space alignment is applied, such that the rich levels of semantics of HINs are preserved independently within each space. By doing so, only one pairwise domain alignment, instead of multiple pairs, is needed in each space.

In addition, we propose a Two-level Selection strategy that efficiently aggregates embedding spaces to ensure both domain similarity and distinguishability, in response to the trade-off mentioned above. First, we utilize Heuristic Combination Sampling Algorithm, a polynomial-time algorithm that selects spaces featuring clear class boundaries, alleviating the need for combinatorial search of spaces. In what follows, we propose Moving-averaged Weighted Voting, a weighting scheme to elaborately fuse the selected spaces, hence minimizing both transfer and classification loss. We evaluate MuSDAC quantitatively on three pairs of networks where MuSDAC outperforms various baselines on transferable classification. We also carry out model analysis and visualization to verify contributions of individual model components.

Our contributions are summarized as follows:

• We address the unexplored problem of transferable classification among HINs with MuSDAC, which adopts multi-channel shared weight GCNs [Kipf and Welling, 2016] and applies multi-space alignment to enable domain adaptation on different semantic spaces.
• To achieve the trade-off between transfer and classification, we design Heuristic Combination Sampling Algorithm to pick out discriminative combinations efficiently and apply Moving-averaged Weighted Voting to assemble the outputs from all channels. We also theoretically analyze the weighted voting in multi-space alignment.
• We carry out both quantitative and qualitative experiments where MuSDAC demonstrates itself by outperforming competitive counterparts.

2 RelatedWork

2.1 HINClassification

Many models have been designed to perform classification on HINs [Hosseini et al., 2018]. [Zhang et al., 2018] proposed GraphInception to handle collective classification on HINs by learning the deep relational features. Besides, heterogeneous network embedding models, which project nodes in HINs to a low-dimensional space, also enables classification [Gui et al., 2016; Dong et al., 2017; Shi et al., 2018; Lin et al., 2019]. HAN [Wang et al., 2019] learns representations based on hierarchical attention, while NEP [Yang et al., 2019] leverages distributed embeddings to represent objects and dynamically composed modular networks to model their complex interactions. However, these models may fail on new domains without labeled instances due to domain discrepancies.

1 Code available on https://github.com/PKUterran/MuSDAC

2.2 Domain Adaption

Domain adaption is wildly used to enable transfer learning among different but relevant domains without manual tagging in fields like CV and NLP. Recent studies mainly focus on learning the domain invariant features for instances in different domains by minimizing their distribution discrepancy via regularizations such as MMD or GAN. [Long et al., 2018; Rozantsev et al., 2018]

To the best of our knowledge, DANE [Zhang et al., 2019] is the only work considering domain adaption among homogeneous networks in the field of network representation. However, DANE is unable to deal with the rich semantics in HINs as the shared weight GCN architecture is specially designed for homogeneous networks.

3 Problem Statement

3.1 Definitions

Definition 1 (Heterogeneous Network [Shi et al., 2016]). A heterogeneous network G consists of a node set V = ⋃ni=1 Vi with n types of nodes and an edge set E = ⋃mi=1 Ei with m types of edges.

In heterogeneous networks, a meta-path Φi is the path in the form of Vi1 Ei1 --→ Vi2 Ei2 --→ · · · Eil --→ Vi(l+1), which defines a composite relationship between two nodes Vi1 , Vi(l+1).

Definition 2 (Multi-channel Network [Zhang et al., 2018]). Given V1 as the node type pending classification. We decompose HIN to a multi-channel network with meta-path set Φ = {Φ1, · · · ,ΦN}, where each channel is a homogeneous network containing nodes V1 connected via a certain type of meta-path. The resulting network is defined as G = {(Vl,Al)|l = 1, · · · ,N}, where meta-path adjacency matrix Al represents the number of meta-path Φl connecting each node pair in V1.

3.2 Problem: Transferable Classification on HINs

Given two HINs (GS, XS) and (GT , XT ), where GS, GT share the same node and edge types and X represents the features of V1, transferable classification on HINs aims to utilize the structural information on both networks as well as labels on VS,1 to predict the labels on VT,1.

4 ProposedMethod

4.1 Overview of MuSDAC

In this section we introduce MuSDAC, an unsupervised domain adaptive classification model on HINs (see Fig. 1 for an overview). We first introduce general pipelines before elaborating on details of individual components.

Multi-channel Shared Weight GCN

To process the heterogeneous information, we decompose source and target HINs GS, GT to multi-channel networks with meta-path set Φ, and feed both of them through N independent GCNs [Kipf and Welling, 2016] to produce original channel embedding sets C = {Cl|l = 1, · · · ,N}:

where ˆ A = ˜D- 12 ˜ A˜D- 12 with ˜ A = A + IN and ˜Dii = ∑j ˜ Aij. Inside channel l, we apply a shared parameter set {W (0) l ,W (1) l } to project the nodes in both networks to the same embedding space.

Multi-space Alignment

To extract complex relational features in HINs, we combine CZ = {Cl|l ∈ Z}, a subset of C with combination Z ⊆ {1, · · · ,N} and Z ̸= ∅, through 1-dimensional convolution [Zhang et al., 2018]. We denote MZ to be the embeddings of aggregated channel with combination Z.

Here we utilize Algorithm 1 to generate a set of combinations Z = {Zj|j = 1, · · · ,M}, containing M = O(N) combinations featuring distinguishability, which will be elaborated in Section 4.2. We then re-project the nodes to several new embedding spaces and get aggregated channel embedding setM= {MZj |j = 1, · · · ,M} whereMZj is a single embedding matrix.

In the j-th aggregated channel Zj, we denote MZj,S,MZj,T as the embeddings of source and target instances, upon which a classifier is employed for prediction

where W C j are parameters of the classifier in the j-th channel.

Model Learning

Theorem 1 (Domain Adaptive Classification (DAC) [BenDavid et al., 2010]). The upper-bound of prediction error on target domain can be reduced by minimizing: (a) the error of hypothesis h on source domain; (b) the H∆H distance between both domains, which measures the domain discrepancy; (c) the error λ of the ideal joint hypothesis h∗ :

According to Theorem 1, we apply DAC, where the prediction error on target labels in the j-th channel can be reduced by minimizing the classification loss on MZj ,S as well as the distance between MZj ,S and MZj ,T :

where CE is the cross entropy function, MMD is the Maximum Mean Discrepancy measuring the distribution distance and γ is a hyper-parameter controlling the gradients.

In LZj,D the final prediction is a weighted voting of the outputs from all classifiers with a weight vector θ. The overall loss is also a weighted sum of DAC losses from the aggregated channels, where the same weight θ is adopted.

4.2 Heuristic Combination Sampling Algorithm

In this section we introduce our design of Heuristic Combination Sampling Algorithm. We first introduce and verify an important assumption related to the design of our algorithm, before introducing the algorithm.

Assumption of Estimating Distinguishability

Inspired by [Rafailidis and Weiss, 2019], we formally define distinguishability and domain similarity of a combination.

Definition 3. Given Z, by minimizing LZ = LZ,D + γLZ,T according to Eq.4, we measure Z's distinguishability DZ and domain similarity TZ by:

Definition 4 (Sub-combination). ˜ Z is a sub-combination of Z iff ˜ Z ⊂ Z ∧ ˜ Z ̸= ∅. We denote Z's sub-combination set as S(Z) 1 .

Based on the definitions we present an important assumption on estimating DZ .

1 In this paper we use lowercase z ∈ {1, 2...n} to denote a channel id, capitalized Z to denote a combination, i.e. set of channels Z ⊆ {1, 2...n} and calligraphy Z to denote a set of combinations Z = {Zi}.

Assumption 1 (Estimation of Distinguishability). For a combination Z and ZT = argmax Z′∈S(Z) TZ′ , It is satisfied that:

In brief, DZ can be estimated by the distinguishability of Z's sub-combination with highest domain similarity.

Analysis of Assumption 1

In this section we present analysis of Assumption 1 from both theoretical and empirical point-of-view.

Definition 5 (Emphasis of features in embedding matrix). Given a matrix M, we apply singular value decomposition (SVD), yielding M = UΣVT. We define Ui (i-th singular vector) to be an extracted feature and its corresponding singular value Σii to be its emphasis. The features embodied in M is defined as F = {Ui, Σii > ε}.

In domain adaptation, the singular vectors representing the domain invariants are more likely to be emphasized. In addition, some of them might be excessively emphasized and hence acquire an unduly high singular value. We refer to them as "trap-vectors", in that they boost domain similarity at the expense of other singular vectors that embody rich semantics crucial for distinguishability [Chen et al., 2019].

Based on this phenomenon, we formulate how features are extracted during aggregation. Denote FZ to be the features embodied in the aggregated channels with combination Z:

where ˜ FZ refers to the features after aggregating all channels in Z and φ is a function mapping the features to the corresponding embedding space MZ. When filtering the features, the combination ZT = argmaxZ′∈S(Z) T ′Z should generally be favorable in domain adaptation. However, such combination is vulnerable to "trap-vectors" as it is likely to impose excessive weight on domain invariants [Chen et al., 2019] and stifle semantics from other channels. On such occasions, low DZT indicates low DZ and vice versa. Consequently, we claim that DZ can be approximated by DZT since ZT is most likely to be extracted in domain adaptation, where "trap vectors" are likely to be produced.

Alternatively from the empirical point of view, we visualize the relationship between DZ and DZT in Fig.2. The result shows that DZT approximately follows ZT in most of the times, hence verifying Assumption 1.

Algorithm: Heuristic Combination Sampling

To select linear number of combinations with high distinguishability, a naive method is to minimize Eq.4 (referred to as pre-test) for every combination Z and compare DZ. However, such enumeration would bring prohibitive complexity (O(2N )). Alternatively, we design a heuristic algorithm to select the combinations Z, which is presented in Algo.1. In the first iteration, we pre-test the combinations in Ztest(|Z| = 1, ∀Z ∈ Ztest), then we try to append a new channel for each in Ztest and predict DZ (Line 7-13) according to Assumption 1. Finally, a linear number of combinations that have high DZ will form new Ztest, and so on.

Algorithm 1 Heuristic Combination Sampling Algorithm

1: Pre-tested set ˜ Z := ∅. 2: Under-test set Ztest := {{i}|i = 1, · · · ,N} 3: for w = 1, 2, · · · ,N do 4: Pre-test the combinations in Ztest. 5: ˜ Z := ˜ Z ∪Ztest, ˜ Ztest := ∅ 6: if w ̸= N then 7: for Z ∈ Ztest do 8: for i ∈ 1, 2, · · · ,N ∧ i /∈ Z do 9: ˜ Z = Z ∪ {i} 10: Predict ˜L˜ Z,D according to Assumption 1 11: ˜ Ztest := ˜ Ztest ∪ { ˜ Z} 12: end for 13: end for 14: Ztest := up to N-w elements in ˜ Ztest with lowest ˜L ˜ Z,D 15: end if 16: end for 17: returnM elements in ˜ Z with lowest LZ,D

4.3 Moving-averagedWeighted Voting

In this section we introduce our scheme of weighted voting. We first extend DAC theory, which links voting weights θ to classification error, before introducing methods to decide θ.

Theoretical Foundation of Weighted Voting

Theorem 1 proves that DAC works for a single embedding space in unsupervised domain adaption, while it remains unexplored for domain adaption in multiple embedding spaces. We hence extend it towards the scenario where multiple embedding spaces exist.

Theorem 2 (Multi-space Domain Adaption). The upperbound of prediction error in target labels can be reduced by minimizing the weighted sum of DAC loss in all embedding spaces: (λ is treated as a constant [Chen et al., 2019])

Proof. While the optimization objective L = ∑j θjLZj is a weighted sum of DAC loss in individual combinations, instead of loss on the assembled final label, we find that due to a consistent weight θ, the prediction error is upper bounded by the objective L through Jensen Inequality and Theorem 1.

Moving-averaged Strategy

As Theorem 2 draws the connection between the final prediction error and errors on individual embedding spaces, we hence focus on the appropriate choice of θ. To obtain voting vector θ corresponding to the performance of each channel, we first calculate ˜ θ by their loss values: [Zhu et al., 2017]

where η is a hyper-parameter. The higher η is, the larger disparity among ˜ θj will be. However, directly using θ = ˜ θ may cause Weight Dominance, where a converged combination illustrates a much lower loss and obtains overwhelming voting power, stifling the other combinations that may be potentially helpful. To address this problem, the voting power θ is moving-averaged here to avoid the abrupt change of θ and hence assure that every combination will have adequate gradients to converge in early training periods. At the end of each iteration, we update θ with θ ← αθ + (1 - α)˜ θ. Note that 0 < α < 1 and θj is originally set to 1/M.

5 Experiments

5.1 Experiment Setup

Datasets

We sample pairs of structurally different graphs respectively from ACM [Kong et al., 2012], AMiner and DBLP [Wang et al., 2019]. The statistics of these datasets are presented in Tab.1, hence showing their structural difference. For each pair of graphs, the density of meta-path edges is quite different between each other, which shows that these graph pairs are domain compatible (i.e. structurally dissimilar). 1

1 The explicit description of datasets is on https://github.com/ PKUterran/MuSDAC/blob/master/data/DATA.md.

Baselines

We select some state-of-the-art baselines to verify the ability of MuSDAC to handle transferable classification on HINs. For baselines working on homogeneous networks, we merge the adjacency matrices of all meta-paths into one adjacency matrix, hence obtaining a unified network.

• GCN [Kipf and Welling, 2016]: a typical graph neural network designed for homogeneous networks.
• GraphInception [Zhang et al., 2018]: a deep GCN for collective classification on HINs.
• HAN [Wang et al., 2019]: a heterogeneous graph embedding method based on hierarchical attention.
• DANE [Zhang et al., 2019]: It adopts domain adaption to learning transferable embeddings on different homogeneous networks.
• MuSC: a variant of MuSDAC, which removes MMD loss in Eq.4.
• SingleDAC: a variant of MuSDAC, which uses only one combination with the best distinguishability.
• MuSDAC-GAN: a MuSDAC variant applying GAN and average voting instead of MMD and weighted voting.

Hyper-parameter Settings

We use default parameter settings for GCN, GraphInception, HAN and DANE. In MuSDAC and its variants, the dimensionality of the first and second hidden layers of the multichannel GCN is 64 and 32 respectively, before aggregated to 16 in the aggregated channel. The number of sampled combinations |Z| = M = 2N - 1. In DAC, we use 5 Gaussian kernels for MMD and γ = 10. In weighted voting, we take η = -25 and α = 0.95.

5.2 Classification Results

The results of classification with different transfer settings are shown in Tab. 2, where we are able to draw four observations.

1. Compared to GraphInception, HAN, MuSC which neglect transfer learning, MuSDAC achieves improvement especially in ACM B→A and AMiner A→B where a significant difference in meta-path density between the graph pair is observed (as shown in Table 1).

1. Compared to DANE which deals with homogeneous networks, a significant improvement by MuSDAC is observed, especially in DBLP where heterogeneity is most prominent (as shown by denser meta-paths).
2. MuSDAC is able to recover more complex semantics than SingleDAC via multiple channel combinations, hence performing better.
3. MuSDAC-GAN fails to outperform MuSDAC as MMD is able to more precisely reflect domain distances while GAN losses cannot, hence facilitating the use of weighted voting.

5.3 Analysis of Two-level Selection

In this section, we analyze two-level selection strategy from the following perspectives.

• Selection: whether to randomly select M combinations (Random) or use heuristic algorithm (Heuristic).
• Voting: whether to use average voting (Average), weighted voting (Weighted) or moving-averaged weighted voting (Moving).

The results are shown in Table 3 which shows that twolevel selection strategy is indeed able to significantly improve the performance compared to simpler counterparts, especially when they are used simultaneously.

5.4 Hyper-parameter Sensitivity

We test the sensitivity of γ in Eq.4 on AMiner A→B and plot the results in Fig.3(a). It can be shown that as long as regularization is used (γ > 0), no significant change in performance is observed.

We also vary the number of combinations to sample M = 1 to 6 (with N = 3) on ACM B→A and plot the results in Fig. 3(b). We conclude that better performance is attained as we sample more combinations and levels of semantics. 1

5.5 Visualization

We visualize 3 out of 5 aggregated channels on AMiner A→B in Fig.4 to provide an intuitive understanding about our voting scheme. It can be shown that the first two channels with high voting power perform well in that they illustrate both clear boundaries among categories, and similar embedding distributions. Contrarily, the last channel is hardly effective in voting due to its blurred boundaries. The result qualitatively shows that MuSDAC is able to pick indicative combinations for transferable classification task.

1 More experimental materials can be found on https://github. com/PKUterran/MuSDAC/tree/master/result.

6 Conclusion

We propose MuSDAC featuring multi-space architecture and two-level selection, which succeeds in solving the problems underlying in domain adaptive classification on HINs. Compared to various baselines, MuSDAC shows promising performance from both prediction accuracy and visualization.

Acknowledgments

This work was supported by the National Natural Science Foundation of China. Besides, we are thankful to Yizhou Zhang for his helpful suggestions.