Semi-supervised Domain Adaptation on Graphs with Contrastive Learning and Minimax Entropy

Existing work mainly focuses on the UDA problem that assumes the data of target domain are purely unlabeled. The basic approach of UDA is to reduce the domain divergence through moment matching [16, 19, 20] or adversarial learning [17, 21, 22, 23]. Deep adaptation network (DAN) [19] estimates the distribution divergence with maximum mean discrepancy. The reduction of MMD helps match the source and target distributions. DANN [21] introduces a domain classifier that is trained with the feature extractor in an adversarial manner. Specifically, the domain classifier is optimized to tell apart samples from the source and target domains. The feature extractor is trained to produce samples that can deceive the domain classifier, thus matching the feature distributions. Another adversarial adaptation method, WDGRL [17], utilizes the Wasserstein distance as the adversarial loss.

Differing from the mainstream UDA research, a few recent studies investigate the SSDA problem where a small number of data are labeled in the target domain. Minimax entropy model [11] consists of a feature encoder (e.g., AlexNet and VGG16) and a cosine similarity-based classifier [18] devised for the few-shot classification. With the entropy of unlabeled target data calculated as adversarial loss, MME alleviates domain discrepancy by enforcing a minimax game between the feature extractor and the image classifier. ECACL [10] incorporates categorical alignment and consistency alignment to improve the performance of existing UDA methods under the SSDA setting.

Domain adaptation has been widely studied in areas like CV and NLP. However, most previous models are designed for vector-based data (e.g., images and text) that follow the i.i.d. assumption. Our work considers the domain adaptation problem for graph-structured data where nodes have complicated edge connections, thereby violating the i.i.d. assumption. Note that GRDA [24] studies the problem of domain adaptation across multiple domains with adjacency described by a domain graph. Each domain is a node in the domain graph. This problem is completely different from the one we considered, i.e., domain adaptation on graphs, where each domain is a graph. Therefore, GRDA is not applicable to our setting.

Graph representation learning generates low-dimensional representation vectors for graph nodes [1, 4]. There are methods designed to preserve structural properties only [25, 26] or to jointly exploit graph structure and side information such as node attributes [27, 28, 29]. Among them, GNNs [2] have drawn a lot of research interest in recent years.

GraphSAGE [30] pioneers in generating node representations by aggregating information from the sampled neighboring nodes. Unlike GraphSAGE, which is evaluated in the supervised learning scenario, many studies focus on graph semi-supervised learning to overcome the label shortage in a partially labeled graph. The well-known model, GCN [31], simplifies the spectral graph convolution as a first-order approximation. Through jointly encoding local graph structure and node attributes, GCN demonstrates impressive performance and inspires many follow-up studies. GAT [32], for instance, introduces an attention mechanism and assigns learnable weights to the neighbors. Note that GCN and GAT utilize all neighbors of a node without neighborhood sampling.

Self-supervised learning [3] is another way to tackle the lack of labels. It enables the models to produce meaningful node embeddings by conducting various pretext tasks without any node label information. Under this learning paradigm, graph contrastive learning (GCL) maximizes the mutual information (MI) between two (augmented) instances of the same object, such as one graph and a node. For example, DGI [33] maximizes the MI between node representations and the global summaries of a graph. The resulting node representations are expected to encode the global structural information. MVGRL [34] contrasts the node and graph embeddings learned from two structural views of a graph.

The majority of graph representation learning models are not specially designed to address the domain discrepancy between graphs. Although we can sometimes adapt these models for cross-graph node classification, the domain divergence would still hinder their performance.

Recently, a few studies have been conducted to address the problem of cross-graph node classification, specifically focusing on two independent attributed graphs. The objective of this research is to assist in node classification on a target graph that lacks sufficient node labels by transferring knowledge from a source graph with abundant labels.

Similar to the UDA studies in CV and NLP, most existing methods are devised for a cross-graph scenario that assumes the target graph is unlabeled. To capture the attributed affinity and topological proximity, ACDNE [12] constructs two feature extractors that encode node attributes and neighborhood attributes, respectively. UDA-GCN [6] utilizes dual graph convolutional networks to exploit the local and global consistency on a graph. Both ACDNE and UDA-GCN follow the adversarial training paradigm in DANN [21] to match the embedding distributions of source and target graphs. ASN [13] also adopts the dual GCNs and improves the extraction of domain-shared features by separating the domain-private features. Xiao et al. recently proposed a GNN-based model (i.e., AdaGIn) that aligns the multimodal embedding distributions by conditional adversarial networks [35]. To capture the global graph information, AdaGIn maximizes mutual information between the node and graph-level representations.

Very recently, a few studies design theory-grounded algorithms for domain adaptation on graphs. For example, MFRReg [14] regularizes the GNN spectral property (i.e., maximum frequency response) to improve the GNN transferability. Additionally, inspired by the Weisfeiler-Lehman graph isomorphism test, GRADE [36] proposes a graph subtree discrepancy to measure the graph distribution shift. The reduction of graph subtree discrepancy contributes to aligning the graph data distributions.

Unlike these UDA methods, CDNE [5] and AdaGCN [15] consider a target graph in which a percentage of nodes are randomly selected to have accessible labels. CDNE generates node representations with stacked autoencoders. The source and target distributions are aligned by reducing the maximum mean discrepancy. AdaGCN extracts node representations with GCN and minimizes the Wasserstein distance [17] to reduce domain discrepancy. Our work focuses on the SSDA problem on graphs. To our knowledge, this problem has never been formally considered by the prior art. To address this problem, we devise a novel GNN-based model empowered by graph contrastive learning and minimax entropy training.

An attributed graph, or an information network, is mathematically described as $\mathcal{G}\left(\bm{V},\bm{A},\bm{X},\bm{Y}\right)$, including node set $\bm{V}\in\mathbb{R}^{N}$, adjacency matrix $\bm{A}\in\mathbb{R}^{N\times N}$, attribute matrix $\bm{X}\in\mathbb{R}^{N\times L}$, and label matrix $\bm{Y}\in\mathbb{R}^{N\times C}$. $N$, $L$, and $C$ denote the number of nodes, the dimension of a node attribute vector, and the number of node classes, respectively. The $i$-th rows of $\bm{A}$, $\bm{X}$, and $\bm{Y}$ are associated with the $i$-th node $v\in\bm{V}$. Adjacency matrix $\bm{A}$ and label matrix $\bm{Y}$ contain binary values. Specifically, $A_{ij}=1$ indicates the $i$-th node has an edge connection with the $j$-th node; $Y_{ic}=1$ means the $i$-th node belongs to the $c$-th class. The degree of node $v$ is the number of its edge connections, i.e., $\sum\nolimits_{j}A_{ij}$. In this paper, we consider the undirected graph. The average degree is computed by $\sum\nolimits_{i}\sum\nolimits_{j}A_{ij}/N$, revealing the graph density. Table 1 summarizes the main notations in this paper.

Graph representation learning encodes each node $v\in\bm{V}$ into a low-dimensional representation vector, that is, node embedding vector $\bm{e}_{v}$. In representation matrix $\bm{E}\in\mathbb{R}^{N\times l}$, $\bm{e}_{v}^{\top}$ is stored as one row. The embedding dimension is denoted as $l$. Using the learned node embeddings, a node classifier can be trained to perform node classification tasks.

In this paper, we study the problem of semi-supervised domain adaptation on graphs. The source domain refers to a labeled graph $\mathcal{G}^{s}\left(\bm{V}^{s},\bm{A}^{s},\bm{X}^{s},\bm{Y}^{s}\right)$, in which the label of each node is known. The target domain is a partially labeled graph $\mathcal{G}^{t}\left(\bm{V}^{t},\bm{A}^{t},\bm{X}^{t},\bm{Y}^{t}\right)$, where only a few nodes have known labels. In line with the common SSDA setting [10, 11], we randomly choose an equal number of nodes from each class to form the set of labeled nodes in the target graph. The objective of this study is to improve the node classification performance on the target graph by transferring knowledge from the source graph. To accomplish this, it is essential to produce node representations that are both transferrable and discriminative. This research problem is challenging because of the distinction between the source and target graphs. Since these two graphs have no edge connections or shared common nodes, they represent independent domains. The discrepancy between the domains arises from variations in graph scales and differences in the distributions of node attributes, edge connections, and node labels.

Based on prior studies [5, 6, 15], it is necessary for the source and target graphs to have the same set of node classes. However, these two graphs possess different attribute sets, namely $\bm{\mathcal{X}}^{s}$ and $\bm{\mathcal{X}}^{t}$. A union attribute set is created and denoted as $\bm{\mathcal{X}}=\bm{\mathcal{X}}^{s}\cup\bm{\mathcal{X}}^{t}$. The attribute matrices can then be expressed as $\bm{X}^{s}\in\mathbb{R}^{N^{s}\times U}$ and $\bm{X}^{t}\in\mathbb{R}^{N^{t}\times U}$, where $U=\left|\bm{\mathcal{X}}\right|$ represents the total number of attributes across both graphs. This union attribute set enables parameter sharing, allowing the same model to be applied to both graphs. Many modern domain adaptation techniques rely on parameter sharing [11, 17, 21]. To quantify the extent of attribute overlap, we define a common attribute rate as $R_{a}=\left|\bm{\mathcal{X}}^{s}\cap\bm{\mathcal{X}}^{t}\right|/\left|\bm{\mathcal{X}}\right|$, showing the percentage of node attributes present in both graphs.

As shown in Figure 2, the proposed SemiGCL model is made up of two modules: the GNN encoders and the node classifier. In addition to using the original graph as a regular structural view, we use graph diffusion to obtain an augmented graph that serves as an additional structural view. Two GNN encoders are used to encode the original graph and the augmented graph, respectively. Representation vectors generated by the GNN encoders are then concatenated to obtain the node embedding vector. A cosine similarity-based classifier is employed as the node classifier, which takes the embedding vector as input and outputs the label prediction.

There are three losses involved in the model optimization. The contrastive loss is calculated for each graph in a self-supervised way. By minimizing the contrastive loss, the agreement is maximized between the representations learned from the two structural views. The cross-entropy loss is computed with the labeled nodes in the source and target graphs. The minimization of cross-entropy loss contributes to extracting discriminative node representations. The entropy loss is calculated on the unlabeled target nodes. To mitigate domain divergence, the GNN encoders and the node classifier are adversarially optimized with the entropy loss.

We consider two structural views of the same graph: one regular view (local view) and one additional view (global view). The regular structural view is the original graph represented by binary adjacency matrix $\bm{A}$. The adjacency matrix stores the edge connection, which is a kind of local structural information around a node. Hence, the regular view is also regarded as a local view. The additional structural view is an augmented graph described by diffusion matrix $\bm{P}$. The augmented graph is generated using graph diffusion [37].

where $\bm{D}$ is the diagonal degree matrix of adjacency matrix $\bm{A}$, $\bm{I}_{N}\in\mathbb{R}^{N\times N}$ is an identity matrix, $\tilde{\bm{P}}$ is the transition matrix, and $\alpha\in\left(0,1\right)$ is the teleport probability. The edge weight in diffusion matrix represents the influence between two nodes that may not be in the one-hop neighborhood of the original graph. In other words, diffusion matrix can establish links to the distant nodes of original graph. The application of diffusion matrix makes nodes in multi-hop neighborhoods directly get involved in the node representation learning, capturing the global information. Therefore, the augmented structural view can be treated as a global view. Following GCN [31], the calculation of diffusion matrix is regarded as a pre-processing step before loading the graph data to conduct model training.

The cosine similarity-based classifier is found to be effective in the few-shot classification where a few labeled data from the new classes are given to train a classification model [18]. The few-shot classification shares certain similarities with the SSDA problem, where a few labeled nodes in the new domain (target domain) are provided. Following [11], we devise node classifier $f_{c}$ to be cosine similarity-based:

where $\bm{W}_{c}$ is the learnable weight matrix; $T$ is a temperature parameter for scaling; nonlinear activation $\sigma_{3}$ is a softmax function for multiclass classification; class probability vector $\hat{\bm{y}}_{v}^{\top}$ is one row in label prediction matrix $\hat{\bm{Y}}$. Weight matrix, $\bm{W}_{c}=\left[\bm{w}_{1},\bm{w}_{2},\ldots,\bm{w}_{C}\right]$, consists of a series of weight vectors (i.e., $\bm{w}_{j},j\in\left\{1,\ldots,C\right\}$). In order to classify the nodes correctly, the direction of weight vector $\bm{w}_{j}$ has to be representative to the normalized node representations of class $j$. Therefore, each weight vector can be treated as an estimated prototype for the corresponding class [11].

Cross-entropy loss, $\mathcal{L}_{\rm CE}$, is computed using the labeled nodes in both the source and target graphs:

Here, $\bm{B}^{s}$ represents a batch of source graph nodes, $\bm{T}_{l}$ denotes the set of labeled nodes in the target graph, binary element $Y_{vj}$ in label matrix $\bm{Y}$ indicates if a node $v$ belongs to class $j$, and $\hat{Y}_{vj}$ is the corresponding entry in label prediction matrix $\hat{\bm{Y}}$. The source and target graphs are distinguished by two superscripts, namely $s$ and $t$. By minimizing the cross-entropy loss, the GNN encoders are expected to generate discriminative node representations.

If the model is optimized using the cross-entropy loss calculated by the labeled source and target nodes, the trained model is likely to be biased towards the source graph, since the source labels are dominant. The node representations of unlabeled target nodes would not be discriminative enough. To address this issue, we apply minimax entropy training [11] as a domain adaptation technique.

Minimax entropy optimizes the model on the entropy of unlabeled nodes in the target graph. With the model optimized on the cross-entropy loss (Eq. 14), the estimated prototypes (i.e., $\bm{w}_{j},j\in\left\{1,\ldots,C\right\}$) will be closer to the embedding distribution of source graph. Then the “position” of each prototype $\bm{w}_{j}$ is moved to the target graph by training the node classifier to increase the entropy of unlabeled target nodes:

where $\bm{B}^{t}$ is a batch of nodes sampled from the set of unlabeled nodes in target graph, i.e., $\bm{T}_{u}$. Increasing the entropy leads to a more uniform prediction score for each class, which means each prototype $\bm{w}_{j}$ shall be similar to all unlabeled target node representations. In contrast, the GNN encoders are optimized to decrease the entropy. The embedding vectors of unlabeled target nodes are expected to be clustered around one of the prototypes by reducing the entropy, which results in discriminative node representations.

To summarize, the domain adaptation process is modeled as a minimax game between the GNN encoders and the node classifier. Specifically, the node classifier is trained to maximize the entropy, whereas the GNN encoders are optimized to minimize it. We insert a gradient reversal layer [21] between the GNN encoders and the node classifier, so that these two model modules can be updated in one backpropagation.

The proposed SemiGCL model is trained with cross-entropy loss $\mathcal{L}_{\rm CE}$, contrastive loss $\mathcal{L}_{\rm CL}$, and entropy loss $\mathcal{L}_{\rm EN}$. The overall learning objective functions are:

where balance coefficients, $\lambda_{1}$, $\lambda_{2}$ and $\lambda_{3}$, are contrastive learning coefficient, domain adaptation coefficient and entropy coefficient, respectively; $\bm{\theta}_{g}$ and $\bm{\theta}_{c}$ are the sets of learnable parameters in the GNN encoders and in the node classifier, respectively.

Algorithm 1 provides an outline of the main procedures for training and testing. During the training stage, the nodes are initially sampled independently from the source graph and the unlabeled set of the target graph (Line 4). Subsequently, the GNN encoders are utilized to generate representations for both the source and target nodes (Line 5). Following this, the contrastive loss, the cross-entropy loss, and the entropy loss are computed (Lines 6-8). Finally, the trainable parameters in SemiGCL are updated using the overall losses defined in Eq. 16 and Eq. 17 (Line 9). With the completion of multiple epochs, the model reaches convergence. The node representations produced by the GNN encoders would become transferrable and discriminative. During the testing stage, we apply the trained node classifier to categorize the unlabeled target nodes using their corresponding node representations.

The time complexity of SemiGCL is derived by investigating its two modules: the GNN encoders (Eq. 5 and Eq. 7) and the node classifier (Eq. 13). Since the GNN encoders employ neighborhood aggregation, each GNN encoder has time complexity similar to the one of GraphSAGE [30], i.e., $\mathcal{O}\left(\prod_{k=1}^{K}s_{k}\right)$ per node. $s_{k}$ represents the sample size of neighboring nodes at search depth $k$. $K$ is the maximum search depth. The time complexity of node classifier is linear to the number of processed nodes. Consequently, the overall time complexity of SemiGCL is linear with respect to the number of nodes.

Following MME [11], we theoretically analyze the mechanism of minimax entropy training for reducing domain divergence. As shown in [39], domain divergence can be measured with a domain discriminator. Let $f_{d}\in\mathcal{H}$ be a domain discriminator from hypothesis space $\mathcal{H}$, the ${\cal H}$-divergence between source domain distribution $p$ and target domain distribution $q$ is

where $\bm{e}$ denotes the node representation in Eq. 8. This theory reveals that domain divergence can be measured by training a domain discriminator $f_{d}$ that distinguishes distributions $p$ and $q$.

Although there is no domain discriminator in the model (see Figure 2), SemiGCL minimizes the divergence between the source and target graphs through minimax training on the entropy of unlabeled target nodes. Without any additional model modules, the domain discriminator can be regarded as a classifier that assigns a binary domain label for a node representation according to its entropy:

where $f_{c}$ is the node classifier, $H$ is the entropy, and $\gamma$ is a threshold. As shown in Eq. 13, node classifier, $f_{c}$, outputs the probability of class prediction. The ${\cal H}$-divergence in Eq. 18 can be rewritten as

where $\mathcal{C}$ is the hypothesis space of node classifier $f_{c}$. In the final inequality, it is assumed that $\mathop{\Pr}\limits_{{\bm{e}}\sim p}\left[{H(f_{c}(\bm{e}))\geq\gamma}\right]\leq\mathop{\Pr}\limits_{{\bm{e}}\sim q}\left[{H(f_{c}(\bm{e}))\geq\gamma}\right]$. The reason is that the entropy of a source node is driven to be a small value by minimizing the cross-entropy loss in Eq. 14.

The inequality in Eq. 20 shows that domain divergence can be bounded by the proportion of target nodes with entropy surpassing threshold $\gamma$. The upper bound can be obtained by finding a node classifier $f_{c}\in\mathcal{C}$ that attains maximum entropy for the node representations of target graph. Our goal is to find node representations that achieve the lowest domain divergence. Thus, the minimax objective is

It is required to find the GNN encoders that achieve the minimum with respect to node representations ${\bm{e}}\sim q$. The above minimax objective corresponds to the objective functions Eq. 16 and Eq. 17. In summary, the minimax entropy training adopted by SemiGCL can theoretically bound and reduce the domain divergence between the source and target graphs by maximizing entropy and minimizing entropy, respectively. Thus minimax entropy training can align the data distributions of these two graphs, promoting knowledge transfer from the source graph to the target graph.

In this section, the proposed method and the baselines are evaluated on the cross-graph node classification tasks. Under this cross-graph scenario, all models perform node classification tasks by leveraging information from both a fully labeled source graph and a partially labeled target graph. We randomly select five nodes per class (i.e., $n=5$) to form the labeled set of target graph. Classification accuracy is reported to quantify the performance of a model in classifying the unlabeled nodes of target graph. As a supplementary evaluation, we also conduct semi-supervised node classification on the partially labeled target graph. In such a single-graph scenario, the models are trained and evaluated with the target graph only.

In this section, we study four key components in the SemiGCL model, including contrastive learning (CL), global view (GV), local view (LV), and domain adaptation (DA). Each component is removed from the SemiGCL model individually to investigate its contribution. We construct the following model variants.

• 1.

  SemiGCL-CL: A variant of SemiGCL without contrastive learning (CL). The contrastive loss is removed from the overall objective function (i.e., Eq. 16).

• 2.

  SemiGCL-GV: A variant of SemiGCL without learning node representations from the global view (GV). The node embedding vector in Eq. 8 is the representation of local view.

• 3.

  SemiGCL-LV: A variant of SemiGCL without learning node representations from the local view (LV). The embedding vector of a node (see Eq. 8) is the representation of global view.

• 4.

  SemiGCL-DA: A variant of SemiGCL without domain adaptation (DA). We remove the entropy loss from the objective functions Eq. 16 and Eq. 17.

Note that, in SemiGCL-GV and SemiGCL-LV, as the embedding vector is only extracted from one structural view (i.e., local view or global view), the contrastive loss (Eq. 12) cannot be calculated to optimize the model. In this section, the labeled set of target graph is identical to that of Section 4.2. Each class in the target graph has five labeled nodes, i.e., $n=5$.

In this section, we investigate the model performance when the number of labeled nodes per class (i.e., $n$) varies from 0 to 10 in the target graph, that is, $n\in\left\{0,5,10\right\}$. In the case that $n=0$, the target graph is completely unlabeled, which corresponds to the UDA setting. When there are five labeled nodes per class (i.e., $n=5$), the labeled set of target graph is the same as the one in Section 4.2. As introduced in Section 2, CDNE and AdaGCN are cross-graph models that investigate the adaptation scenario with a partially labeled target graph. In addition to CDNE and AdaGCN, we also make comparisons with three competitive UDA cross-graph models, i.e., ACDNE, AdaGIn, and MFRReg.

Figure 7 shows the average accuracy of each model on the six transfer tasks of citation graphs, i.e., C$\rightarrow$A, D$\rightarrow$A, A$\rightarrow$C, D$\rightarrow$C, A$\rightarrow$D, and C$\rightarrow$D. The SemiGCL variant without domain adaptation (i.e., SemiGCL-DA) is also included. SemiGCL is the top-performing model on the SSDA tasks, i.e., $n=5$ and $n=10$. A significant performance lift is observed in SemiGCL from $n=0$ to $n=5$. Therefore, SemiGCL can effectively exploit a few labeled nodes in the target graph to improve the model performance. In contrast, the accuracies of UDA approaches (i.e., ACDNE, AdaGIn, and MFRReg) remain stable with the increase of labeled target nodes. Moreover, the accuracies of CDNE and AdaGCN slightly increase from $n=0$ to $n=5$. It indicates these five cross-graph models lack the capability to utilize the target labels well. Note that, under the UDA setting ($n=0$), SemiGCL has no an improvement over SemiGCL-DA, since the domain adaptation component of SemiGCL (i.e., minimax entropy training) is devised for the SSDA tasks.

In this section, we analyze the influences of four key hyperparameters on the model performance, including embedding dimension $l$, contrastive learning coefficient $\lambda_{1}$, teleport probability $\alpha$, and temperature parameter $T$. The aim is to gain insights into how these hyperparameters should be configured. When investigating a specific hyperparameter, the remaining hyperparameters are set to their default values provided in A. Note that, in this section, the labeled set of target graph is identical to the one in Section 4.2.

Figure 8 presents the classification accuracies of transfer tasks on the citation and social graphs. Embedding dimension, $l$, refers to the dimension of a node representation vector learned by the SemiGCL model. The model achieves the highest accuracy with an embedding dimension of $128$ on the citation graph tasks (i.e., C$\rightarrow$A and D$\rightarrow$A). On the social graph tasks (i.e., B2$\rightarrow$B1 and B1$\rightarrow$B2), embedding dimensions $l\in\left\{128,256,512\right\}$ can all lead to fairly good performance. Contrastive learning coefficient, $\lambda_{1}$, is the weight of contrastive loss when optimizing the GNN encoders. As discussed in Section 4.3.1, contrastive learning has a more significant impact on the citation graphs. Therefore, the model performance is more sensitive to the contrastive learning coefficient on transfer tasks C$\rightarrow$A and D$\rightarrow$A. When $\lambda_{1}=0.1$, the best accuracy is observed on all four transfer tasks. Teleport probability, $\alpha$, plays an important role in constructing the diffusion matrix. It is observed that the optimal value is around $\alpha=0.1$. Temperature parameter, $T$, scales the output of node classifier. When $T=5.0$, the classification accuracy reaches its peak value on transfer tasks B2$\rightarrow$B1 and B1$\rightarrow$B2. On the citation graph tasks, a larger temperature parameter (i.e., $T=20.0$) is more desirable.