Coupling Category Alignment for Graph Domain Adaptation

1 Introduction

As a crucial problem in graph classification [Lin et al., 2023; Luo et al., 2023], Graph Domain Adaptation (GDA) has received substantial interest, particularly in the fields of temporally-evolved social analysis [Wang et al., 2021], molecular biology [Zhu et al., 2023; Yin et al., 2023], and protein-protein interaction networks [Cho et al., 2016]. GDA

transfers graph representations learned from the source domain to the target domain, which is necessary in many applications. Domain adaptive learning is inherently challenging due to the distribution shift between source and target domains. This challenge is further amplified when handling graph-structured data, which often represent abstractions of varying natures [You et al., 2022a].

Currently, various GDA methods have been proposed [Yin et al., 2022; Yin et al., 2023; You et al., 2022b] by combining domain adaptation techniques with graphs. They usually assume the distribution invariance is limited [Garg et al., 2020; Verma and Zhang, 2019] and directly employ adversarial training to align source and target distribution [Zhang et al., 2019b; Wu et al., 2020a]. However, the classifier still tends to favor source domain features and makes incorrect predictions on the target domain due to category-agnostic feature alignment [Zhang et al., 2019a], as shown in Figure 1. To solve the issue and efficiently design the GDA framework, we still need to address the following challenges: (i) How to fully exploit the features of the source and target domain for representation learning. Previous approaches typically employ the MPNNs to capture implicit topological semantics. However, the absence of labels for the target domain poses challenges in obtaining sufficient topological semantics. (ii) How to effectively align category-level distribution. While there has been progress in matching the marginal distributions between two domains, they may not efficiently align the category distribution, leading to a degradation in classification performance. Certain methods have attempted to acquire pseudo-labels for the target graphs in target domain training [Yin et al., 2023; Ding et al., 2021; Zhu et al., 2023], they are vulnerable to bias in cases of significant domain shift, leading to error accumulation in subsequent optimization. (iii) How to design the GDA framework with the grounded theoretical foundation. Theoretically, the generic domain adaptation (DA) bound is not specific to graph data and models [You et al., 2023]. However, we can still design a more precise model tailored for graphs with the theoretical guarantee.

To tackle these challenges, we propose a framework named Copling Category Alignment (CoCA) for unsupervised domain adaptive graph classification. Specifically, to fully exploit the features of both source and target graphs, CoCA incorporates an MPNN branch and a shortest path aggregation branch. The MPNN branch leverages neighborhood aggregation to implicitly learn topological semantics, while the shortest path aggregation branch generates paths for each node and utilizes position encoding to extract informative graph-level semantics. This shortest path aggregation branch provides explicit high-order structural semantics, serving as a complementary enhancement. To collaborate knowledge from two branches, we jointly train the branches by iteratively filtering highly reliable samples from the target domain using one branch and fine-tuning the other branch accordingly. Specifically, with the dual pre-trained branches, CoCA first finetunes the shortest path branch with the highly reliable samples filtered from the target domain with the MPNN branch and then optimizes the MPNN branch with the filtered target domain samples labeled by the shortest path branch. Theoretically, the interactive optimization of one branch with the support of the other one would gradually mitigate the category-level distribution shift. Furthermore, we embed the iterative learning process into a holistic contrastive learning framework, incorporating cross-domain contrastive learning to achieve category-level domain consistency, alongside multi-views contrastive learning to ensure consistent representations between branches. Overall, our approach emphasizes a unique focus on achieving category-level domain alignment. Specifically, our methodology is centered on Coupling Category Alignment (CoCA), which systematically iterates between branches to identify and select reliable samples. This process facilitates cross-branch adjustments, effectively mitigating potential domain shifts in an unsupervised manner. By iteratively refining the alignment process, our approach enhances the model's ability to achieve categorylevel alignment, supported by solid theoretical foundations, distinguishing it from prior methods. Extensive experiments conducted on various datasets with domain shifts for graph classification demonstrate the superiority of proposed CoCA.

In summary, the main contributions can be summarized as three-fold: (1) Problem Formulation: We present a novel problem in graph domain adaptation, which highlights the discrepancy in the distribution of graph categories between the source and target domains, posing significant challenges for accurate graph classification across domains. (2) Methodology: We propose a framework named CoCA, which utilizes two branches to explore structural semantics and integrates them into a category-level domain-invariant model. We provide theoretical proof demonstrating that CoCA is specifically designed to more accurately address the challenges of the graph domain. (3) Experiments: Extensive experiments conducted on various domain shift datasets for graph classification demonstrate the effectiveness of the proposed CoCA.

2 RelatedWork

Graph Classification. GNNs [Kipf and Welling, 2017a] have shown exceptional performance across a wide range of graph-based machine learning tasks, such as node classification [Kipf and Welling, 2017a], graph classification [Wu et al., 2020b] and link prediction [Cai et al., 2021]. The most prevalent GNNs follow the message-passing paradigm, which aggregates the neighbors for node update and applies graph pooling for graph representation. Nevertheless, MPNNs have limited capacity to capture high-order topological structures, such as paths and motifs [Ju et al., 2022]. Therefore, numerous graph kernel methods have emerged to overcome this flaw [Long et al., 2021]. However, these approaches typically require an ample supply of labeled annotations [Yin et al., 2023] while this work delves into the realm of unsupervised graph domain adaptation and introduces a novel approach CoCA to tackle this challenge.

UnsupervisedDomainAdaptation. Unsupervised domain adaptation is to learn domain-invariant representations that enable the transfer of a model from a source domain with abundant labels to a target domain with a scarcity of labels [Feng et al., 2023]. The majority of technical routes can be broadly categorized into domain discrepancy-based methods and adversarial approaches. The former methods typically incorporate different distribution metrics like maximal mean discrepancy [Saito et al., 2018] and Wasserstein distance [Shen et al., 2018] to measure the discrepancy between different domains. Conversely, adversarial approaches involve a domain discriminator that is fused to implicitly reduce the domain discrepancy. However, these methods typically concentrate on Euclidean data such as images and texts, while graph domain adaptation has not been extensively explored. In this work, we explores graph semantics by utilizing dual perturbation branches for effective graph domain adaptation.

Graph Domain Adaption. Due to the potential economic value, graph domain adaptation [Lin et al., 2023; Wu et al., 2022; Luo et al., 2023] is a crucial problem in the fields of social analysis and molecular biology [You et al., 2022b; Zhu et al., 2023]. Existing methods mainly focus on how to transfer information from source graphs to unlabeled target graphs to learn effective node-level [Dai et al., 2022] and graph-level [Yin et al., 2023; Ding et al., 2021] representation. However, these approaches commonly merge GNNs with domain alignment [Luo et al., 2023] methods, which overlook the alignment of category distributions in the presence of label scarcity and domain shift, consequently leading to a deterioration in classification performance. Towards this end, CoCA couples the dual branch in a variational optimization framework to address the issue.

3 Methodology

This work studies the unsupervised GDA problem [Yin et al., 2023; Yehudai et al., 2021] and proposes a new approach CoCA (see Figure 2). CoCA consists of two parts, the dual graph branch explores semantics from implicit and explicit perspectives; the branch coupling module interactively optimizes one branch with highly reliable sample filtered from the other branch to minimize the category distribution discrepancy. CoCA incorporates the iterative process into a learning framework and theoretical proof the designed method is more precisely tailored for the graph domain.

3.1 Dual Branch for Semantics Mining

Current graph transfer learning methods [Lin et al., 2023; Wu et al., 2022] typically rely on MPNNs to implicitly capture topological semantics through neighborhood aggregation for transfer learning. However, these approaches may be suffered under domain shift. To address this issue, we introduce a dual-branch architecture for graph representation learning, comprising a MPNNs branch for implicit topological semantics and a shortest path aggregation branch for explicit topological semantics derived from high-order structures.

Message Passing Branch. MPNNs extract graph semantics by aggregating neighborhood nodes to update each central node representation. We update the representation of node u at layer l in the massage passing branch f MP ω (·) and summarize the node representations into graph-level as:

where N(u) is the neighbours of node u. C lMP and AlMP are combination and aggregation functions at layer l, and READOUT is the pooling function. In this way, the message passing branch learns the topological structure in an implicit manner under label supervision.

Shortest Path Aggregation Branch. However, the message passing branch merely extracts topological structural semantics in an implicit manner, which would be challenged under the circumstance of domain shift. Considering an alternative technical route, graph kernels [Shervashidze et al., 2011] are capable of explicitly extracting high-order semantics. We introduce a shortest path aggregation branch that generates various shortest paths from local substructures to extract high-order semantics into graph-level representations. Thus, the representations alleviate the impact of structural shift across domains.

In particular, denote Nk(u) as the set of nodes reachable from u through a shortest path of length k, and the representation of node u can be updated with N1(u) → · · · → Nk(u) → · · · →NK(u), K is the hyperparameter of largest length. We update the nodes on different path length k:

where C lSP and AlSP denotes combination and aggregation operators at layer l on shortest path branch. Thus, we obtain the embeddings from different path length, i.e., {mlu↪N1(u) ↪ · · · ↪mlu↪NK(u)}, and update the representation of u as follows:

where ε ↑ R, Atten is the self-attention mechanism, ♣♣ denotes the concatenation operation, and ♣♣Kk=1mlu↪Nk(u) ↑ RK↓d→ , d↔ is the feature dimension of mlu↪Nk(u) . MLP is the fully connected layer. After stacking L layers, we take the average of all nodes into a graph-level representation:

The READOUT function is similar to Eq. 1. The shortest path aggregation branch acquires topological semantics by focusing on paths of varying lengths, which help mitigate the impact of structural domain shifts, such as differences in density and graph size.

3.2 Coupling for Category Alignment

Recent work attempted to obtain target graph pseudo-labels for training [Yehudai et al., 2021; Ding et al., 2021; Zhu et al., 2023]. However, due to discrepancies in the category distribution, they may suffer from error accumulation during subsequent optimization. To address this issue, we cleverly utilize the characteristics of the dual branch to obtain pseudolabels and mitigate error accumulation.

With the message passing branch (MP branch) and the shortest path branch (SP branch), our target is to identify highly dependable pseudo-labels in the target domain and integrate them with the source domain to fine-tune the model. In this way, we can efficiently align the category distribution. Nevertheless, with category discrepancy and error accumulation challenges, we cannot achieve satisfactory pseudo-labels in a signal branch. To address the issue, we introduce the classifier HMP (·) and HSP (·) for the MP and SP branches. Specifically, we filter the highly dependable pseudo-labels with the threshold ϑ in the MP branch:

and then use those samples to help fine-tune the SP branch:

where HMP (zMP Gti ) is the target graph pseudo-labels filtered from the MP branch, l(·) is the loss function. Similarly, we utilize the target samples filtered from the SP branch to support the fine-tune of the MP branch:

and then use those samples to help fine-tune the MP branch:

where HSP (zSP Gti ) is the target graph pseudo-labels filtered from the SP branch. The interactive optimization of the MP and SP branches offers two advantages. First, by incorporating highly confident target pseudo-labels into source domain training, we can effectively align the category distribution. Second, the pseudo-labels filtered from the other branch help mitigate the error accumulation issue caused by the single model.

Theoretical Analysis. Intuitively, incorporating training samples from target and source domains would effectively align the category distribution between domains. However, the theoretical basis for why iterative fine-tuning achieves category alignment still requires further investigation. Additionally, the graph category alignment bound remains agnostic. To address this, we present Theorem 1 demonstrating that employing a category distribution alignment module results in a lower bound on the empirical risk in the target domain than without this module.

Theorem 1. Assume that there exists a small amount of high dependable i.i.d. samples with pseudo labels ¶(Gn↪ Yn)♦N →T n=1 filter from the target distribution PT (G↪ Y ) (N ↔T ↔ NS) and bring in the conditional shift assumption that domains have different labeling function ˆhS ↗= ˆhT and maxG1↪G2 ♣ˆhD(G1)→ˆhD(G2)♣ ϑ(G1↪G2) = Ch ↘ CfCg(D ↑ ¶S↪ T♦) for some constant Ch and distance measure ϖ. Let H := ¶h : G ≃ Y♦ be the set of bounded real-valued functions with the pseudo-dimension Pdim(H) = d, with probability at least 1 ⇐ ϱ the following inequality holds:

where ς = min♣♣g♣♣Lip↗Cg↪♣♣f♣♣Lip↗Cf ¶εS(h↪ ˆhS) + εT (h↪ ˆhS)♦ and ς↔ = min(♣εS(h↪ ˆhS) ⇐ εS(h↪ ˆhT )♣↪ ♣εT (h↪ ˆhS) ⇐ εT (h ⇐ ˆhT )♣).

The proof is detailed in Appendix A. From Theorem 1, we observe that the bound of CoCA is lower than GDA by incorporating source and target samples during training, demonstrating that it is possible to design a more accurate model specifically tailored for graphs with a theoretical guarantee.

3.3 Learning Framework

Through the iterative learning process of the MP and SP branches, we integrate them into a unified contrastive learning framework. Specifically, this framework employs crossdomain contrastive learning to achieve category-level domain consistency, while multi-view contrastive learning ensures consistent representation between the branches [Yin et al., 2023].

Multi-view Contrastive Learning. For each a graph Gi, we first obtain the embeddings from MP and SP branches, i.e., zMP i and zSP i . Then, we introduce the InfoNCE loss to enhance the consistency representation cross coupled branches:

where φ is set to 0▷5 as default .

Cross-domain Contrastive Learning. To achieve the category-level domain consistency, we construe the crossdomain contrastive learning with the help of pseudo-labels from each branch. Taking the MP branch as an example, we first filter highly dependable samples with the threshold ϑ as introduced in 3.2, and then calculate the loss between source and target domain with the same category.

where !(j) = ¶i♣ys i = ˆ yt j ♦ denotes the index of all positives in the source domain, "(i) is the index of filtered highly dependable samples from the target domain.

Iterative Optimization. As introduced in Section 3.2, we first filter the highly dependable samples in the MP branch, i.e., "(i) = ¶i♣HMP (zMP Gti ) > ϑ♦, and then optimize the objective function to update ↼ in the SP branch:

After that, we utilize the updated SP branch to filter the highly dependable samples, i.e., "(i) == ¶i♣HSP (zSP Gti ) > ϑ♦, and update ⇀ in the MP branch:

where ω and ↽ are the hyper-parameters. Additionally, we analysis the model complexity, which is presented in Appendix B.

4 Experiments

4.1 Experimental Settings

Datasets. We use 4 graph classification benchmarks: Mutagenicity (M) [Kazius et al., 2005], FRANKENSTEIN (F) [Orsini et al., 2015], NCI1 (N) [Wale et al., 2008], and PROTEINS (P) [Dobson and Doig, 2003], obtained from TUDataset [Morris et al., 2020] to evaluate the effectiveness of the CoCA. The details are presented in Appendix C. To assess the domain shift in each dataset, we follow [Yin et al., 2023] and partition each dataset into four sub-datasets (D0, D1, D2, and D3, where D represents the respective dataset) based on edge and node density and graph flux.

Baselines. We compare the proposed CoCA with various state-of-the-art methods, including the kernel-based approach: WL subtree [Shervashidze et al., 2011], GNNs methods: GCN [Kipf and Welling, 2017b], GIN [Xu et al., 2019a], GMT [Baek et al., 2021], CIN [Bodnar et al., 2021], and domain adaptation methods: CDAN [Long et al., 2018], ToAlign [?], MetaAlign [Wei et al., 2021], and GDA methods: DEAL [Yin et al., 2022], CoCo [Yin et al., 2023], SGDA [Qiao et al., 2023], DGDA [Cai et al., 2024], A2GNN [Liu et al., 2024a] and PA-BOTH [Liu et al., 2024b]. The details are introduced in Appendix E and the implementation details are proposed in Appendix D.

4.2 Performance Comparison

Table 1, 2 and 3 show the comparison performance of CoCA and baselines on Mutagenicity, FRANKENSTEIN and NCI1 datasets under different domain shift. More results are shown in Appendix F. From the results, we find that: (1) The GDA

methods, including DEAL, CoCo, CoCA, etc., consistently outperform the kernel and GNN methods. This demonstrates that domain shift limits the expressive capability of traditional graph methods. Therefore, it is critical to design the domain invariant methods for GDA. (2) The GDA methods demonstrate competitive performance compared to traditional domain adaptation approaches. This achievement can be attributed to the challenges associated with obtaining highquality graph representations, which make the direct application of domain adaptation techniques to graphs a demanding task. (3) The proposed CoCA outperforms recent GDA methods. We attribute this performance gain to two factors: (i) The dual branch approach for graph semantic extraction, which effectively leverages the complementary strengths of message passing and shortest path aggregation models. (ii) The architecture of the branch coupling module effectively aligns the category-level distribution, addressing the category-agnostic limitations typically encountered with GDA methods.

4.3 Flexibility of CoCA

To show the flexibility of CoCA, we replace the MP and SP branches with different GNNs and kernels. Specifically, we replace the MP branch with GCN [Kipf and Welling, 2017b], GIN [Xu et al., 2019b] and Graphsage [Hamilton et al., 2017], and the SP branch with Graph Sampling [Leskovec and Faloutsos, 2006], RandomWalk [Kalofolias et al., 2021] and WL kernel [Neumann et al., 2016]. Figure 3 shows the performance of different GNNs and graph kernels on four datasets, and we have similar observations on other datasets.

More results are shown in Appendix G. From the results, we observe that when compared to other GNNs and graph kernels, GMT and shortest path aggregation consistently achieve the best performance in most cases. This can be attributed to the powerful representation capabilities of GMT and the shortest path kernel. This observation further justifies our choice of GMT and shortest path aggregation to improve performance in our GDA task.

4.4 Ablation Study

To assess the impact of each module on CoCA, we conduct ablation experiments with various configurations: (1) CoCAMP, where both branches exclusively use the message passing model; (2) CoCA-SP, where both branches exclusively use the path aggregation model; (3) CoCA/BC, removal of the branch coupling module; (4) CoCA/MV, removal of the multi-view contrastive learning module; (5) CoCA/CD, removal of the cross-domain contrastive learning module.

We conducted these experiments on the Mutagenicity dataset, and the results are presented in Table 4. From the results, we observe that: (1) CoCA consistently outperforms both CoCA-MP and CoCA-SP, emphasizing the critical importance of extracting graph semantics from both implicit and explicit perspectives in order to achieve superior performance. (2) The performance of CoCA is significantly superior to models that lack the branch coupling module (i.e., CoCA/BC), highlighting that by aligning the category-level distributions, the branch coupling module effectively resolves the category-agnostic issue that arises when attempting to align the entire feature distribution, which could otherwise impair model performance. (3) CoCA/MV and CoCA/CD perform worse than CoCA, and we attribute this to the fact that by ignoring multi-view and cross-domain contrastive learning, CoCA is unable to efficiently learn consistent representations between the source and target domains, ultimately leading to a notable reduction in predictive performance.

4.5 Sensitivity Analysis

In this part, we investigate the influence of hyperparameters on the performance of the proposed CoCA. We specifically examine the effects of two key hyperparameters, including the threshold ϑ in the branch coupling module for category alignment, and the shortest path length K in the SP branch. We report the results of ϑ and K in Figure 4. ϑ determines the number of reliable samples selected from each branch, and we vary ϑ in the range from 0.5 to 0.9. The experimental results presented in Figure 4 (a), (b) indicate an initial increase followed by stability or a decreasing trend in performance as ϑ increases. We attribute the reason to the fact that smaller values of ϑ introduce low-confidence samples, which would detriment the performance of CoCA. Conversely, larger values of ϑ introduce high-confidence samples for training. However, excessively high values of ϑ may lead to fewer filtered samples, potentially resulting in a decline in model performance. Therefore, we set ϑ to 0.7 as default. Additionally, the parameter K controls the number of shortest paths extracted in the SP branch, and we vary K in the range of ¶2↪ 3↪ 4↪ 5↪ 6♦. The results are shown in Figure 4 (c) and (d). From the results, we observe that increasing K generally leads to improved performance when the value is small. This suggests that incorporating more shortest path aggregations can enhance the representation capability. However, when K becomes large, the performance stays stable. Considering the significant increase in algorithmic complexity associated with higher values of K, we set K = 5. Additionally, we examine the accuracy of filtered samples from MP and SP branches, and the results are shown in Appendix H.

5 Conclusion

In this paper, we address the practical challenge of unsupervised graph classification and introduce a novel approach called CoCA. We leverage a dual-branch architecture, consisting of a message passing branch and a shortest path aggregation branch, to capture graph semantics from both implicit and explicit perspectives. The incorporation of the branch coupling module ensures effective category-level alignment, thereby mitigating the category-agnostic issues commonly encountered in traditional graph domain adaptation methods. Additionally, our framework integrates cross-domain and multi-view contrastive learning, which enhances the consistency of representations across domains and branches. Theoretical analysis shows that CoCA achieves a tighter empirical risk bound compared to existing GDA methods. Extensive experiments across multiple datasets demonstrate the superior performance of CoCA in handling domain shifts. In future work, we plan to extend CoCA to more complex scenarios, including domain generalization and source-free GDA.

Contribution Statement

Nan Yin and Xiao Teng are contributing equally. Mengzhu Wang is the corresponding author.

Acknowledgments

This research was supported by the Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier 1 grant, the National Natural Science Foundation of China under Grants No. 62406100, Tianjin Natural Science Foundation under Grants No. 24JCQNJC00320, Beijing Postdoctoral Research Foundation and Beijing Natural Science Foundation No. 4254079.