Rank and Align: Towards Effective Source-free Graph Domain Adaptation

1 Introduction

Graph Neural Networks (GNNs) have achieved great success in a wide range of applications, including molecular generation [Kim et al., 2023], traffic networks [Li et al., 2019a], social networks [Liu et al., 2021; Li et al., 2021] and relational databases [Cvitkovic, 2020]. They could be used to solve the graph classification problem, which aims to predict the labels of entire graphs [Zhang et al., 2018; Ying et al., 2018; Wu et al., 2020b]. Most of these approaches adopt the message-passing paradigm [Welling and Kipf, 2016] to update node-level representation iteratively, followed by a readout operator to summarize the node-level representations to graph-level representations for downstream classifications.

† Corresponding authors.

Despite their superior performance, these approaches usually assume that the training and test data are from the same data distribution, which is often not the case in real-world scenarios [Wu et al., 2020a; You et al., 2022; Lin et al., 2023]. The out-of-distribution challenge has promoted the development of unsupervised graph domain adaptation [Hao et al., 2020; Yin et al., 2023]. However, these approaches require access to a label-rich source domain to adapt to the labelscarce target domain, meaning that abundant source graphs are needed. The requirement could be difficult due to privacy and storage concerns in practice. This motivates us to study a practical yet underexplored research problem of source-free graph domain adaptation. The objective is to transfer these pre-trained graph models from the source domain to the target domain without accessing source data.

However, formalizing an effective framework for sourcefree graph domain adaptation is a non-trivial problem, which requires us to solve the following two research problems. (1) How to learn semantics on the target domain, given its label scarcity? Previous approaches [Ding et al., 2022; Zhang et al., 2022] usually utilize pseudo-labeling to learn from target data. However, serious distribution shifts could generate biased and inaccurate pseudo-labels, which results in extensive error accumulation and training instability, as demonstrated in Figure 1(a) (b). (2) How to deal with extensive distribution shifts without access to source data? Source and target graphs could belong to very different domains, which strongly decreases the accuracy of predictions. Previous graph domain adaptation approaches [Yin et al., 2022; Yin et al., 2023] usually minimize the distribution discrepancy between the source and target domains, which is not feasible due to the requirement of extensive source data.

In this paper, we propose a novel approach named Rank and Align (RNA) for source-free graph domain adaptation. The high-level idea of our RNA is to infer spectral seriation rankings to guide robust semantics learning and detect harmonic graphs (i.e., close to source graphs) for domain alignment. In particular, RNA utilizes the spectral algorithm to generate seriation similarity rankings among target graphs, which are robust to the potential noise. Then, a ranking-based similarity learning objective is adopted to guide the semantics learning under the target label scarcity. To depict the distribution shift, we introduce the silhouette coefficient after spectral clustering, which identifies harmonic graphs closely related to source graphs on the target domain. To further reduce potential domain discrepancy, we extract subgraphs from inharmonic graphs by sampling edges with adversarial learning, which discards information irrelevant to semantics labels. Then, we conduct invariant learning to ensure our GNNs are insensitive to these irrelevant parts. Finally, we utilize pseudo-labels with multi-view filtering to enhance semantics learning with alleviated error accumulation. Extensive experiments on several benchmark datasets validate the superiority of RNA in comparison to extensive baselines. The contributions can be highlighted as follows:

• New Perspective. We study an understudied yet practical problem of source-free graph domain adaptation and propose a novel approach RNA to solve the problem.
• NewMethod. RNA not only infers spectral seriation rankings to guide robust semantics learning under target domain label scarcity, but also detects harmonic graphs close to the source domain to guide subgraph learning for domain alignment and invariant learning.
• Sate-of-the-art Performance. Extensive experiments conducted on several benchmark datasets demonstrate the superiority of RNA compared to extensive baselines.

2 RelatedWork

Graph neural networks (GNNs) [Wu et al., 2020b; Ju et al., 2024a] have made significant progress in a variety of tasks, including graph classification [Yin et al., 2023], visual grounding [He et al., 2021; Luo et al., 2022]. The majority of GNNs follow the message-passing mechanism [Xu et al., 2018], which updates node information by aggregating from neighboring nodes. When applied to graph-level tasks, these updated node features are then combined into a comprehensive graph representation using various pooling techniques [Lee et al., 2019; Bianchi et al., 2020], which can be utilized for downstream graph classification. However, these techniques [Li et al., 2019b] usually assume that training and test data are from the same distribution, which often does not hold in practical scenarios. To solve the out-ofdistribution problem, some approaches have been proposed, where typically the source data is required [Yin et al., 2023; Tang et al., 2024; Ju et al., 2024b]. However, it is not practical to guarantee that the source data is available, due to, e.g., privacy and storage concerns. To address this, our research focuses on source-free graph domain adaptation, which transfers the model to new domains without requiring access to the original data.

Source-free Domain Adaptation (SFDA) [Fang et al., 2022; Yu et al., 2023] eliminates the dependence on source data [Yang et al., 2024; Yang et al., 2021; VS et al., 2023; Peng et al., 2023]. The assumption that adequate source data are available for adaptation does not always hold in realworld scenarios. On one hand, issues of privacy, confidentiality, and copyright restrictions may hinder access to the source data. On the other hand, storing the complete source dataset on devices with limited capacity is often impractical. Extensive approaches attempt to solve this problem, which can be classified into two primary categories, i.e., self-training approaches [Sun et al., 2020b; Saito et al., 2017; Liang et al., 2020] and generative approaches [Nado et al., 2020; Schneider et al., 2020]. Self-training approaches usually adopt contrastive learning framework and pseudo-labeling strategy for semantics learning on the unlabeled target domain. Generative approaches typically reconstruct virtual samples using stored statistics in the source model and reduce the domain discrepancy. However, SFDA has not been explored for non-Euclidean graph data. In this paper, we detect harmonic graphs close to the source domain and extract subgraphs from inharmonic graphs for domain alignment.

3 The Proposed RNA

3.1 Preliminaries

Problem Definition. A graph is represented as G = (V, E), where V is the set of nodes and E is the set of edges. The nodes' attribute is denoted as X ∈ R|V |×df , where |V | is the number of nodes, and df is the dimension of a node's attribute. A dataset from the source domain is denoted as Dso = {(Gso i , yso i )}Ns i=1 , where Gso i is the i-th graph from the source and yso i is its corresponding label. An unlabeled dataset from the target domain is represented as Dta = {Gta j }Nt j=1 , where Gta j is the j-th target sample. yta j is its corresponding label but is not available. Both domains share the same label space {1, · · · ,C}, but the data distributions are distinct. Our objective is to transfer a model pretrained on the source domain to the target domain. Note that the source graphs are not available during the adaptation.

Graph Neural Networks. Given a node representation h(l) v for v at layer l, the updating rule can be formalized as:

in which AGG(l) (·) and COM(l) (·) represents the aggregation and combination operators respectively. N(v) collects all the neighbors connected with v. Finally, we introduce READOUT(·) for node representation summarization:

where K denotes the number of layers. A classifier CLA(·) is adopted to map deep embedding into label distribution:

where Φ represents the entire graph neural network, pretrained using the source graphs beforehand.

3.2 Framework Overview

This work studies the problem of Source-free Graph Domain Adaptation (SFGDA), which is challenging due to target domain label scarcity and distribution shifts from source to target domain, without access to source graphs. We propose a novel approach named RNA for this problem. In particular, to guide the semantics learning under label scarcity, RNA introduces spectral seriation rankings among graph representations, which are robust to noise attack. In addition, RNA utilizes spectral clustering and silhouette coefficients to identify harmonic graphs close to the source domain. Subgraphs with domain-invariant semantics are extracted in inharmonic graphs using an adversarial edge sampling process, which can guide invariant learning of GNNs. Pseudo-labeling on harmonic graphs with filtering is conducted to further enhance semantics learning. An overview of RNA can be found in Figure 2 and then we elaborate on the details.

3.3 Robust Semantics Learning with Seriation Similarity Rankings

The significant challenge by SFGDA is label scarcity in the target domain. Due to serious distribution shifts, target data often contains noise and inaccurate pseudo-labels, leading to error accumulation and instability. RNA addresses this issue from a spectral perspective, utilizing the intrinsic ranking information for better semantics learning. In this part, we will introduce our Seriation Similarity Rankings (SSR) to guide semantics learning and theoretically demonstrate its robustness to noise.

We first extract the similarity matrix S by,

where sim denotes the cosine similarity function, and zi and zj represent the graph representations as Section 3.1. Then, we employ the spectral seriation method [Atkins et al., 1998] to obtain the data ranking matrix R within unlabeled target data, from the correlation matrix. The higher correlation values suggest a closer proximity in ranking. Spectral seriation can be effectively utilized to reconstruct R from S, since the cosine similarity corresponds to correlation following L2 normalization. The seriation ranking can be derived by minimizing the following equation:

which brings sample pairs with a higher degree of correlation closer to the learned representation space, by minimizing the loss function that encourages proximity between Ri and Rj . According to the spectral seriation [Atkins et al., 1998; Gong et al., 2022; Dai et al., 2024], the optimal ranking R can be obtained from the Fiedler vector. This is formalized in Theorem 3.1.

Theorem 3.1. The seriation ranking that most accurately reflects observed S is the ranking of the values in the Fiedler vector λ of the Laplacian matrix L by

The Fiedler vector λ is the eigenvector corresponding to the second smallest eigenvalue of the Laplacian matrix L = diag(S1) - S. The ranking R given from the spectral seriation can be used to guide semantics learning by

where B is the sampled batch, [i] denotes the i-th value of a vector, rk denotes the ranking operator. rsim is a differentiable ranking similarity function which is the differential combinatorial solver [Poganˇci´c et al., 2019].

Robustness under Perturbation. In this part, we will discuss the inherent noise-robustness of the spectral seriation method theoretically by deriving the approximate bounds.

We first give the perturbation bounds for eigenvalues and the upper bound for the Fiedler value. Let A,B ∈ C be Hermitian matrices. Let the eigenvalues of A and B are λi and µi, with the eigenvalues sorted in non-decreasing order. Then, for each corresponding pair of eigenvalues, the following inequality holds on the perturbation bounds for the eigenvalues:

Moreover, when λ is the Fiedler value of the Laplacian matrix L from the similarity matrix S, then the upper bound of the λ is given by

Then we analyze the potential noise on the similarity matrix.

Theorem 3.2. Consider the perturbation matrix of S is ∆S, when 2∥∆S∥F ≤ 1 - min1≤i≤n ∑t̸=i |Sit| n-1 , the ranking obtained by the SSR algorithm using S is the same as that obtained by the SSR algorithm using S + ∆S.

∥·∥F denotes the Frobenius norm. The theorem utilizes the first-order approximation to establish a bound that the spectral ranking can tolerate without altering results.

In summary, given the significant noise in the target domain, SSR provides theoretically error-bounded data relationships. This allows us to obtain better target domain representations through similarity learning.

3.4 Subgraph Extraction for Domain Alignment

To address label scarcity of target graphs, RNA detects harmonic graphs that are close to the source domain from a spectral perspective. Then, we extract subgraphs in inharmonic graphs with an adversarial edge sampling process, which guides effective invariant learning for GNNs.

Harmonic Graph Detection. RNA uses spectral clustering and silhouette coefficients to discover the harmonic graphs with the source domain. This process is instrumental in guiding the domain alignment for subgraph extraction that has domain-invariant semantics.

In detail, we utilize the similarity matrix S and the Laplacian matrix L computed in Section 3.3 to obtain the eigenvectors U. To compute the eigenvectors, we address the generalized eigenvalue problem:

where U ∈ Rn×k represents the matrix of eigenvectors corresponding to the k smallest eigenvalues, and Λ ∈ Rk×k is the diagonal matrix containing these eigenvalues. We then apply k-means clustering algorithm to the rows of U, to obtain the clustering labels c. After the clustering, we calculate the silhouette coefficient to detect the harmonic graphs, which are close to the source graphs. For a data point i within a cluster, the silhouette coefficient S(i) [Rousseeuw, 1987; Monshizadeh et al., 2022] is :

where a(i) is the mean dissimilarity of i to all other points in the same cluster, while b(i) is the smallest mean dissimilarity to all points in any other cluster. Since S(i) ∈ [-1, 1], a coefficient close to 1 indicates that the data point is well-matched to its cluster and distinctly separated from neighboring clusters. These graphs have the potential to be well-classified using source GNNs, which are more close to the source domain. Therefore, we rank the target graphs by silhouette coefficients and select the top ρ graphs to construct a harmonic set. ρ is set heuristically to 40%.

Domain-invariant Subgraph Extraction. After partitioning the dataset, we utilize the harmonic set to simulate the unavailable source graphs to depict domain discrepancy. To identify crucial parts invariant to different domains, we sample edges for inharmonic graphs, which extract domaininvariant subgraphs using adversarial learning. Moreover, invariant learning is introduced to encourage consistent predictions of GNNs after removing redundant information.

In particular, we use a neural subgraph extractor fθ. For edge embedding e concatenated from node embedding h, we predict the sampled adjacency matrix ˆAsub with:

where A is the original adjacency matrix. Since the sampling process is not differentiable, we apply GumbelSigmoid [Jang et al., 2016] for differentiable training. Then, we extract the subgraph Gsub according to ˆAsub.

To train the subgraph discovery network, we adopt an adversarial learning framework. The discriminator is to distinguish the domain of the input graph, while the subgraph discovery network is used as the adversarial component, and aims to extract domain-invariant subgraphs that confuse the discriminator. Let D denote the discriminator and G denote the subgraph discovery network. The training loss can be formulated as follows:

where Gh and Gi are the harmonic and inharmonic graphs respectively, pdata(·) represent the data distributions. Subgraph extractor can effectively extract domain-invariant components under domain shift. Then, we introduce invariant learning to encourage the consistency of predictions after extracting domain-invariant subgraphs, which ensures GNNs are insensitive to the domain-specific information on the target domain. In formulation, the invariant learning objective is defined as:

where I is the inharmonic set, ˜ pta i is the label distribution of the subgraph fθ(Gi). When the KL divergence is minimized, RNA enables the model to leverage the inharmonic graphs, which are initially more challenging due to the domain shift, and gradually adapt to the target domain.

Finally, the overall training objective for the subgraph discovery network can be formulated as a combination of the adversarial loss and the invariant learning loss:

By jointly optimizing the subgraph discovery network and the discriminator, we can effectively extract domain-invariant subgraphs that confuse the discriminator while preserving the original semantics.

3.5 Semantics Enhancement with Filtered Pseudo-labeling

To enhance the semantics learning under label scarcity and potential noise, we propose to obtain the confident discriminative learning set from multi-view filtering. From the global view, we have detected harmonic graphs on the target domain. Then, from the local view, we leverage the predicted confidence scores to select reliable samples. The combination of these two perspectives yields a more confident set.

To filter samples in the harmonic set H and generate the confident set C, we define a threshold τ for the confidence scores. Samples with confidence scores exceeding τ are considered to be part of the confidence set. Formally, the confident set C is defined as:

where pta j represents themodel prediction, indicating the predicted probability distribution over classes, and τ is the predefined threshold.

Then, the standard cross-entropy loss is minimized in the confident set C:

where ˆ yta j denotes the pseudo-label of Gta j . Our pseudolabeling strategy provides a reliable optimization process with reduced error accumulation. After a certain adaptation period, we re-perform the harmonic set partitioning operation to include more confident data into the harmonic set. This iterative process helps to gradually enhance semantics learning by incorporating more reliable pseudo-labeled data.

As a preliminary, we adopt an off-the-shelf model trained on the source domain. Then, the loss objectives are minimized in the target data, which is summarized in Algorithm 1.

Algorithm 1 Optimization Algorithm of RNA

Input: Pre-trained model Φ(·), target graphs Dta , Output: GNN-based model Φ(·)

• 1: for epoch = 1, 2, · · · do
• 2: Generate harmonic and inharmonic sets using Eq. 10;
• 3: for each batch do
• 4: Sample a mini-batch from Dta ;
• 5: Calculate the loss objective using Eq. 6;
• 6: // For the harmonic set
• 7: Calculate the discriminating loss using Eq. 16;
• 8: // For the inharmonic set
• 9: Calculate the discriminating loss using Eq. 14;
• 10: Back-propagation;
• 11: end for
• 12: end for

Complexity Analysis. The computational complexity of seriation similarity and spectral clustering is O(|Dta |2d), where |Dta | is the target graph amount, d is the feature dimension. Given a graph G = (V,E), ∥A∥0 is the number of nonzero entries in the adjacency matrix, |V | is the number of nodes, and K is the number of GNN layers. The complexity of the GNN is O(K|V |d2 ). The subgraph extractor takes O(K∥A∥0d). Therefore, the complexity for each sample is O(K|V |d2 +K∥A∥0d), which is linear to ∥A∥0 and |V |.

4 Experiments

4.1 Experimental Settings

Datasets. We perform experiments with practical sourcefree domain adaptation settings and benchmark datasets. We test our RNA in cross-dataset and split-dataset scenarios. For biochemical datasets, e.g., Mutagenicity [Kazius et al., 2005], PROTEINS [Borgwardt et al., 2005], and FRANKENSTEIN [Orsini et al., 2015]. The source-free domain adaptation is performed over sub-datasets, which are partitioned by graph density. Furthermore, we test our method on the sub-datasets of the COX2 [Sutherland et al., 2003] and BZR [Sutherland et al., 2003] datasets. In source-free domain adaptation, only the target dataset is available during domain adaptation.

Baselines. We compare RNA with a wide range of existing methods. These baseline methods fall into three categories: (1) Graph neural netowrks, e.g., GCN [Welling and Kipf, 2016], GIN [Xu et al., 2018], GAT [Veliˇckovi´c et al., 2018] and GraphSAGE [Hamilton et al., 2017]. These methods only use the source data. (2) Graph semi-supervised learning methods, e.g., Mean-Teacher [Tarvainen and Valpola, 2017], InfoGraph [Sun et al., 2020a] and TGNN [Ju et al., 2022]. They use information from both the source and target domain. (3) Source-free domain adaptation, e.g., PLUE [Litrico et al., 2023], which is the state-of-the-art source-free domain adoption method devised for image classification.

Implementation Details. For RNA, we encode the graph data with a 2-layer GCN encoder, with an embedding dimension of 128. We optimize the model with an Adam optimizer with a mini-batch of 128 and a learning rate of 0.001. The model is initialized with 100 epochs of pre-training on the source domain In domain adaptation, the harmonic set ratio is 40%. For baselines, we configure the methods with the same hyperparameters from the original papers and further fine-tune them to optimize performance. To reduce randomness, we perform 5 runs and report the average accuracy.

4.2 Performance Comparison

Observation. From Table 1, 2, 3 and 4, we can observe that: (1) Source-free domain adaptation shows significant challenges. Current baseline methods are insufficient, given that previous research has not effectively tackled such real-world conditions. (2) Semi-supervised settings can only slightly alleviate the problem. Although some of these methods outperform graph neural network methods, e.g., InfoGraph, they rely on both labeled data from the source domain and unlabeled data from the target domain. However, in real-world scenarios, it is not always feasible to access source data. (3) Source-free method shows better results. PLUE is the stateof-the-art for source-free domain adaptation in computer vision. However, it is important to note that PLUE was neither designed for graphically-structured datasets, nor for scenarios with large domain shifts. (4) RNA show notable performance improvements, on both sub-datasets and cross-dataset tasks. This is especially true where other methods perform poorly.

Discussion. The improvements can be attributed to three key factors: (1) Robust adaptation from a spectral perspective. The experimental results agree with our theoretical analysis in Section 3.3 that RNA is robust to noisy and inaccurate target data. (2) Reduce task complexity through a divide-andconquer strategy. We prioritize domain adaptation on subtasks that are more similar to the source domain, and then align the remaining data across domains. (3) Efficient domain alignment by subgraph extraction. For non-Euclidean data with domain shift, subgraph extraction can achieve domaininvariant semantics learning effectively.

4.3 Ablation Study

To evaluate the effectiveness of the components, we introduce the following variants of our model: (1) V1, which removes the SSR module in Section 3.3. (2) V2, which excludes the partitioning of the harmonic and inharmonic set, together with the subgraph extractor. This variant only filters the target data with confidence. (3) V3, which only removes the domain alignment with the subgraph extractor. (3) V4, which omits the multi-view data filter in Section 3.5.

From Table 5, we draw the following insights. (1) The full model RNA yields the best performance, emphasizing the importance of components' cooperation. (2) Each module independently contributes to the final results. Among them, the detection of harmonic data and the subgraph extraction invariant learning make the most significant contribution. (3) Regarding the multi-view pseudo-label filter, both global and local view filters have shown their effectiveness.

4.4 Visualization

To verify our motivation, we use t-SNE [Van der Maaten and Hinton, 2008] for visualization on the Mutagenicity dataset. The results can be found in Figure 3. From the results, we can observe that: (1) There is a significant domain discrepancy between the source and target domain. (2) The harmonic set of the target domain is closer to the source domain, which facilitates the pseudo-label discriminative learning. (3) The inharmonic set of the target domain is more distant from the source domain. In RNA we employ subgraph extraction for effective domain-invariant learning and domain alignment.

4.5 Sensitivity Analysis

Analysis of the harmonic set ratio. We first examine the influence of the harmonic set ratio within the target domain, as shown in Figure 4. As the ratio increases from 20% to 40%, we observe an upward trend in accuracy, suggesting that splitting the harmonic set and using domain alignment and pseudo-label learning is beneficial. However, as the ratio increases from 40% to 60%, there is a noticeable decrease in accuracy. This suggests that an overly large harmonic set may introduce additional noise that could adversely affect performance. Therefore, we set the ratio of 40% as the default size.

Analysis of the confident set threshold. We explore the effects of the confident set threshold τ. This threshold is used to filter pseudo-labels within the harmonic set. As τ increases from 0.91 to 0.95, we see an improvement in final accuracy for both datasets. This shows that cleaner pseudo-labels are beneficial for adaptation. However, further increasing τ to 0.99 results in a decrease in accuracy. This suggests that an overly strict pseudo-label threshold may limit the model's ability to learn from the target domain, and thus harm the performance. Consequently, we set τ to 0.95 as default.

5 Conclusion

In this paper, we study the problem of source-free graph domain adaptation and propose a novel approach RNA for this problem. Our RNA leverages the spectral seriation algorithm to generate robust pairwise rankings, which can guide reliable semantics learning under label scarcity. Moreover, RNA adopts spectral clustering to detect harmonic graphs which close to the source domain, and introduces an adversarial edge sampling process to extract subgraphs from inharmonic graphs for invariant learning. Extensive experiments demonstrate the superior performance of our RNA over existing baselines. In future work, we will extend RNA to more practical scenarios such as the open-set graph domain adaptation.

Acknowledgments

This paper is partially supported by the National Natural Science Foundation of China with Grant (NSFC Grant Nos. 62276002 and 62306014) as well as the China Postdoctoral Science Foundation with Grant No. 2023M730057.