Graph Data Selection for Domain Adaptation: A Model-Free Approach

We thank the reviewer for the insightful questions. We address each of those as follows.

(W1) Theorem 3.3 proved minimizing GDD can decrease the discrepancy between training and validation performances. That's true, but cannot infer that validation loss also decreases. They minimized GDD by selecting training data according to validation data, so training loss accordingly changes, then validation loss changes. Therefore, minimizing GDD for a smaller gap cannot theoretically guarantee a better performance on validation.

This is a great observation! We acknowledge that the upper bound of validation loss might end up going up if the training loss is increased significantly during the selection process. However, we empirically observe that mostly, both the training and the validation loss decrease.

To illustrate this, we train a GIN model with 50% GRADATE-selected data and compare it with a counterpart trained with full data. In Table 1, we report the relative change of train/validation loss. For example, Δ train loss = (train loss of 50%-data model - train loss of full model) / train loss of full model; and Δ validation loss is calculated similarly. Thus, a more negative number means GRADATE lowers the train/validation loss more. We can observe that under most cases, not only validation loss drops, the training loss also decreases if we train with 50% high-quality data selected by GRADATE.

• Table 1 (GRADATE data decreases train & validation losses)

(W2) Model complexity. The authors used optimal transportation theory, one of whose characteristics is high complexity with O(N^2) (or O(NM) in this paper).

Thanks for raising the concern. We would like to clarify that the O(NM) complexity is mainly due to the pairwise distance computation between each of N training graphs and each of M validation graphs, which has nothing to do with optimal-transport-based distance itself. With linear optimal transport theory and entropic regularization, the empirical runtime of GRADATE is very affordable compared to GNN training time, which can be observed in Section L (Table 10 in line 724). Additionally, runtime on the other three OGB datasets is reported above in the response to Reviewer pN6d (Table 3 & W4).

(W3) Experiments. 1) All six datasets are small-scale ones. 2) Potential unfair comparison. Proposed GRADATE uses both training and validation labels to update the weight when c ≠ 0. The full-data training GNNs in table 1 and full-data training GDAs in table 3 only use training data. So, it's not clear the improvements come from whether the extra validation labels or not.

We address each concern as follows.

• Scale of the datasets: We would like to argue that we have included significantly larger-scale analysis compared to several other recent works on graph domain adaptation, such as [1,2,3,4]. The largest dataset they use contain at most 2-3K samples; while the largest one (i.e. the ogbg-molhiv dataset) we experiment on contains ~42k samples.

• Potential unfair comparison: As demonstrated in Remark 3.2 (line 165), we have the ability to set c = 0 to avoid any usage of validation label. To fairly address this concern, we restrict GRADATE to this validation-label-free setting and re-evaluate its performance. After restricting to this setting, the advantage of GRADATE remains similar to, or even better than, what is reported in paper. Please refer to Table 1 & 2 in the response to Reviewer pN6d (W3) for more details.

(W4) GDD incrementally adds label distance based on traditional FGW. The label distance is defined in the same way as FGW.

We respectfully disagree with the assessment that GDD merely adds a label distance term on top of FGW in an incremental manner. The novelty of GDD lies not only in considering FGW and label distance, but in introducing a self-contained framework grounded in theoretical insights that motivates a new data-centric method for graph domain adaptation. We summarize on the key components of GDD as follows:

• Theoretical motivation: By Theorem 3.3, GDD upper-bounds the domain generalization gap, which leads to a principled data selection objective: minimizing GDD to align source and target distributions. This offers a theoretically grounded alternative to existing model-centric approaches.

• Justification of FGW: Rather than using FGW as a black-box metric, we provide Theorem 3.1 as a novel theoretical foundation. Specifically, we prove that FGW distance captures discrepancies between attributed graphs in a way that upper-bounds the representation shift induced by any k-layer GNN. To the best of our knowledge, this is the first time to establish such a guarantee for FGW.

• Label distance formulation: The label distance in GDD is not simply adopted from prior work. It is defined as the Earth Mover’s Distance (Wasserstein-1 distance) over graph-label distributions, using FGW as the cost metric. This constitutes the first formal framework for comparing distributions over labeled graphs.

(Q1) GDA aims to make our model suitable to new data, but theoretically, different models prefer different part of data. So, can we really find a set of training graphs that benefits all models?

We agree with the reviewer that no single set of data samples is optimal across all models. However, in the presence of significant distributional shift between the source and target domains, certain harmful training samples are likely to negatively impact performance and should ideally be excluded by most algorithms. Nevertheless, in paper, we empirically show in Table 3 that combined with the same set of GRADATE-selected data, most GDA methods can lead to improved performance. In our response to Reviewer qLY5 (Q6), we further showcase the robustness of GRADATE-selected data by evaluating on three additional GDA methods and demonstrating their performances can also be boosted by the same set of training graphs.

(Q2) I understand that with the increase of selection ratio, model performance may decrease because of involving irrelevant training data. But I do not understand why the performance firstly decreases and then increases sometimes? For example, GCN+GRADATE on IMDB-MULTI in Table 1, where 20% was the worst. If GRADATE started to involve irrelevant information at 20%, 50% should be lower, since the selection quality continuously descends.

Thanks for pointing out! This is indeed a very interesting observation that we didn't spot previously. One possible explanation is that GRADATE is not perfect in the sense that it gets distracted and selects some harmful data in the middle and then switches back to find higher-quality samples later on. We believe this phenomenon might worth further exploration beyond the current scope.

In addition, we believe this is also related to the discussion in Section 4.5 (line 297-300) and one bullet point in Limitation & Outlook section (line 738-744) where the optimal amount of data for each dataset/shift type/shift level is different and needed to be configured automatically. This question will be left as one of our future studies.

[1] https://arxiv.org/abs/2306.04979

[2] https://dl.acm.org/doi/abs/10.1145/3503161.3548012

[3] https://arxiv.org/abs/2307.11341

[4] https://arxiv.org/abs/2306.03256

Based on the previous discussion, we would like to reply each of the reviewer's concern.

(Q1) Only experimental results are not enough. The proposed GRADATE is fully supported by theorem 3.3. So, if theorem 3.3 cannot strictly benefit target domain, the performace of GRADATE is uncertain. Although the new table 1 partially showed the benefit, we cannot enumerate every dataset in the world. For me, this is a theorem-driven method, so the correctness of theorem is the base of model success.

Firstly, we respectfully disagree reviewer's statement on "whether theorem 3.3 can or cannot strictly benefit target domain affects the correctness of theorem 3.3". We would like to argue that the correctness of Theorem 3.3 is always valid. Recall that this theorem (named as Graph Domain Generalization Gap) mainly focuses on building up the connection of domain generalization gap and Graph Dataset Distance (GDD). The possibility that val_loss (model trained with any selected subset of data) < val_loss (model trained with full data) should not break the validity of the theorem at all.

Together with Discussion (2.1) in our previous comment, we hope these statements could address the over-expectation and possible mis-understanding from the reviewer.

(Q2) In response to W3, the authors claimed that restricting c=0 can match or even outperform c ≠ 0. 1) It's better to also report the percentage of c ≠ 0 in table 1 & 2 for Reviewer pN6d, so I can directly compare the improvements brought by c = 0 and c ≠ 0. 2) Assumed this statement is true, can I understand the FGW is the dominated one, while the newly proposed label distance in GDD did not contribute too much? Because the absence of label distance did not influence or even promote the performance.

We provide the same table 1 & 2 for Reviewer pN6d with c ≠ 0 here for a more direct comparison as the reviewer requested. In addition, we have the following three comments:

• We apologize for the confusion on using the term "sometimes even outperform". What we mean here is empirically we observe adding label information does not improve the performance everywhere.
• We attribute this phenomenon to the fact that GRADATE is approximated, which affects the accuracy of label distance. Specifically, the usage of entropic regularization in FGW computation and the linear optimal transport both introduce noise.
• We thank the reviewer for scrutinizing the empirical usefulness of label signal. We will discuss this possible discrepancy in Section 4.5 as well.

Table 1 (GRADATE vs other data selection methods)

Table 2 (GRADATE vs GDA baselines)

(Q3) I am not fully convinced by the response to Q2. Besides, I further observe that in table 1, GCN+GRADATE on IMDB-MULTI, ogbg-molbace and ogbg-molhiv decreased and then increased, but GIN+GRADATE increased monotonously. This may be an evidence for my Q1 that it's not optimal to use the same set of training graphs for all models. So can we really talk about GDA without the consideration of specific base model, the "model-free" setting in the title?

We believe this concern should be addressed by Discussion (1) and (2.2) in our previous comment.

We thank the reviewer for the quick response. We address the concerns as follows:

1. While the reviewer agrees with us that "This paper studied graph data selection problem under distribution shift setting" (written in the reviewer's Summary section), we are regretful that the emphasis on GDA in our abstract still gives the reviewer an impression that we are exclusively addressing a GDA problem. We would like to point the reviewer to line 5-8 (we propose...) in abstract and also our central question (line 27-28) in the introduction section, namely,

How to select the most relevant source domain data, based on available validation data, for better graph-level classification accuracy evaluated on the target domain?

We would like to clarify that the answer to this question should not be another GDA algorithm, but should be a data selection method that works well in a domain shift setting. GRADATE is a direct answer to this how to select question. How to select is always the core storyline. And this question should be well answered by our Table 1 and 3.

Then what is the role of GDA? We would say GDA is one of the important applications to evaluate the downstream utility of GRADATE. Table 2 deals with the comparison against GDA.

As a final remark, we are happy to slightly down-weight GDA-related sentences in abstract to avoid similar confusion from the reviewer. However, it should be clear from Introduction (line 27-31, line 45-51) and all main tables in the Experiment that we are indeed studying a "data selection problem".

2. For the label distance, we respectfully disagree that it is a must to find a single c≠0 that swipes all c=0 cases to justify label distance's practical usefulness. Such c might be dataset, shift type-dependent, which should not be a central question to answer in this work. Instead, we show that by only searching within two possible values of c, GRADATE's advantage over existing baseline is already evident.

As the rebuttal period comes to an end, we sincerely thank the reviewer's deep engagement to let us clarify and strengthen our work. Thanks!

Thank you for the thoughtful questions. We address each of these as follows.

(W1)(Q1) The model is only evaluated on graph level task. It is unclear whether the proposed model could work in node level task.

We agree with the reviewer that node-level task is also an important aspect of graph domain adaptation. In this work, we focus specifically on the graph-level classification task, which poses unique challenges such as distribution shifts at the graph level. Thus, we believe that addressing graph-level adaptation task is valuable in its own right, as it is essential for real-world applications like molecule property prediction where the prediction target is naturally graph-level.

Although this work explicitly deals with graph-level tasks, one natural extension to solve node-level task is as follows: decomposing both source and target graphs into set of ego-graphs where each of these ego-graphs represent the local topology of each node, and applying graph-level GRADATE to select a subset of nodes from source graph for optimal adaptation.

We acknowledge that this direct extension is non-trivial and requires further investigation into several aspects: (i) how to determine the appropriate size of the local vicinity for each ego-graph, (ii) how to jointly consider node and edge selection for optimal adaptation, and (iii) how to mitigate potential information loss when extracting ego-graphs. We will add this discussion to the Limitations & Outlook section to inspire future research in this direction.

(W2)(Q2) The authors claim that the proposed model is data efficient. However, based on the experimental results, sometimes using more data could achieve better performance.

• Clarification: We would like to clarify that data efficiency does not necessarily imply less data always leads to better performance. We fully acknowledge that, in some cases, training on 50% or even 100% of the data can result in stronger performance. However, our key observation is that GRADATE is able to identify a small subset of high-quality training data that is sufficient to match, or even surpass, the performance of full-data training in many settings. For example, by Table 1 & 2 in the paper, we show that GRADATE can often achieve comparable or superior results using as little as 20% of the training data.

• Related discussion: Another question to ask here is: what is the optimal amount data to select for each setting? We note this in Section M (line 738-744) as one limitation of GRADATE and will leave this as a direction for future work.

(W3)(Q3) The authors claim that the proposed model is model-free data selection. However, lots of other GNN architectures are not evaluated including graph transformer and PPNP.

We conduct extra experiments on one graph transformer (i.e. SGFormer [1]) and APPNP [2]. In Table 1, we report relative performance improvement (%) of GRADATE over the strongest baseline under all settings (i.e. GNN + X% selected data with Dataset Y). We can observe that GRADATE outperforms other baselines mostly.

• Table 1 (GRADATE outperforms other data selection methods)

(Q4) In Table 5, the GAT results for ogbg-molhiv are missing.

We apologize for the mistake. The number will be re-filled in the updated manuscript.

(Q5) For some datasets like IMDB-MULTI, using full data could result in worse performance. However, the authors did not give any explanations on this phenomenon.

We assume the reviewer is referring to Table 1 and Table 3 in the paper.

• For Table 1, the main reason is that because under distribution shift, a certain number of harmful graphs exist in training set. These samples can mislead the model and degrade generalization performance. GRADATE mitigates this issue by selecting a high-quality subset of training graphs that are better aligned with the target domain. As a result, models trained on GRADATE-selected data can outperform those trained on the full dataset.
• For Table 3, the above reasoning also holds similarly. Even equipped with advanced model-centric GDA methods, severe shift level can still hinder their performances. By effective data selection performed by GRADATE, the difficulty of addressing the domain shift can be lowered significantly and thus result in better adaptation performance.

For the updated manuscript, we will state this clearer in Section 4.2 and 4.4, respectively.

(Q6) There are lots of other unsupervised graph domain adaptation baselines. It is unclear whether the proposed model also enhance their performance.

Thank you for pointing to these related works. Due to constraint on resource and open-source code availability, we add three additional experiments based on two variants of A2GNN [3] with different losses and TDSS [4]. In Table 2, we report relative performance improvement (%) of GRADATE over the strongest baseline under all settings (i.e. GDA + X% selected data with Dataset Y). For brevity, we report results with selection ratio equals to 20%. It can be observed that GRADATE consistently provides the most significant enhancements for the three newly evaluated GDA methods compared to other selection baselines.

• Table 2 (GRADATE enhances additional GDA methods)

(Q7) It would be valuable to understand how GRADATE performs in extremely low-resource scenarios. For instance, what happens if only 1% of the selected data is used for training?

To showcase the superiority of GRADATE in low-resource scenarios, we have conducted experiments with 1% training data and three representative backbones, including GAT [5], SGFormer [1] and APPNP [2], on the same six datasets. The baselines are model-free selection methods: random selection and LAVA [6]. In Table 3, we report relative performance improvement (%) of GRADATE over the strongest baseline under all settings (i.e. GNN + 1% selected data with Dataset Y). We can see that under extreme low-resource scenario, GRADATE can achieve the best performance most of the time.

• Table 3 (GRADATE outperforms other selection methods under lower-resource scenario)

[1] https://arxiv.org/abs/2306.10759

[2] https://arxiv.org/abs/1810.05997

[3] https://arxiv.org/abs/2402.05660

[4] https://arxiv.org/abs/2412.11654

[5] https://arxiv.org/abs/1710.10903

[6] https://arxiv.org/abs/2305.00054

Thank you for recognizing our work! For the weakness and question you mentioned, we address each of those as follows.

(W1) I have some concerns regarding Eq. 5. Is it valid to perform the minimization using validation data? Comparing the distance between training and validation data seems to implicitly treat the validation set as part of the training process. Wouldn't this contradict the standard setup of GNN-based methods, where validation data is only used for model selection, not training?

Thank you for pointing out. GRADATE will depend on validation data but not necessarily validation label. As demonstrated in Remark 3.2 (line 165), settingc=0 will allow GRADATE to be independent of validation label during the selection process. Note that the graph domain adaptation (GDA) baselines also have access to validation data during training.

(W2) In Section 4.2, the model trained on the selected 50% of data outperforms the one trained on the full dataset. Was validation data used as a selection criterion in this filtering process? If so, does this raise concerns about potential information leakage from the target domain?

Let us address each question as follows.

• Yes, the validation data is used during selection. Similar to our response to (W1), the dependency on validation data matches the setting of graph domain adaptation baselines.

• No, there is no concern about information leakage. While GRADATE makes use of validation data to select data from training set, the validation label is not used when we set c=0. Even with the constraint of c=0, GRADATE still yields the best performance across settings. (Please refer to Table 1 and 2 in our response to Reviewer pN6d)

• The improved performance of GRADATE with less training data stems from its ability to retain high-quality samples and eliminate distributionally mismatched ones. In contrast, training on the full dataset under severe distribution shift can hurt performance due to the presence of misleading samples.

We thank the reviewer for the feedback and apologize for any possible lack of clarity in our manuscript. It will be very helpful if the reviewer can point us to certain parts of the paper that confuse you and we are happy to provide a more detailed follow-up after that.

To help the reviewer better understand our paper, we would like to summarize the main message we want to convey: We propose GRADATE to take a data-centric perspective to tackle the graph domain adaption problem. Specifically,

• GRADATE is theoretically-motivated:

  • We show Fused Gromov-Wasserstein (FGW) distance's expressiveness in theorem 3.1 to compare attributed graphs, which is an important building block of GRADATE to compute the proximity between domains.
  • The newly introduced concept, Graph Dataset Distance (GDD), theoretically bounds the performance generalization gap between source and target domains. Motivated by theorem 3.3, GRADATE selects the best data from the training set to minimize this gap. As a result, we showcase better adaptation performance by merely training on these selected, target-aligned data.

• GRADATE has strong empirical performance: Across various domain shift types, datasets and GNN backbones,

  • Table 1 on page 7 (GRADATE outperforms other data selection methods)
  • Table 2 on page 8 (GRADATE+vanilla GNNs outperform model-centric graph domain adaption methods)
  • Table 3 on page 9 (GRADATE-selected data can even further enhance graph domain adaption methods)

For the GDA setting,

• We provide a detailed problem definition for graph domain adaptation on page 25.
• [1] provides a very concise background (on page 2) on GDA methods that can benefit the understanding of our studied problem.

[1] Graph Domain Adaptation: Challenges, Progress and Prospects

Thank you for recognizing our work! For the weakness you mentioned, we address each as follows.

(W1) The literature review is somewhat incomplete. The paper does not sufficiently cover some recent graph domain adaptation works.

Thank you very much for pointing out. We have identified some recent works such as [1-5] and will include them in the Related Work section for a more detailed discussion. During rebuttal, we have conducted additional experiments based on recent graph domain adaptation (GDA) works [1-2]. Please refer to our response to (W3) and Table 2 below.

(W2) The method is only evaluated on graph-level tasks, but domain adaptation is also important for node-level prediction with established benchmarks. Discussion of whether and how GRADATE could be applied at the node level would be helpful.

This is a very insightful question. Although GRADATE explicitly deals with graph-level tasks, one possible extension to solve node-level tasks is as follows: decomposing source/target graphs into set of ego-graphs where each of these ego-graphs represent the local topology of each node, and applying GRADATE directly to select the optimal nodes for adaptation.

This is indeed a very interesting future direction that requires more investigation on (i) how to decide the size of local vicinity for each ego-graph, (ii) how to co-consider node/edge selection for optimal adaptation and (iii) how to mitigate the information loss from extracting ego-graphs. We will add this discussion to the Outlook section to inspire further studies.

(W3) The approach relies on labeled target-domain validation data, which is often unavailable in realistic test-time adaptation scenarios.

We would like to clarify that:

• Validation label is not required to apply GRADATE. As demonstrated in Remark 3.2 (line 165), setting label weight c=0 means validation label is un-used during the selection process. While c was originally introduced as a hyper-parameter, we recognize that using c ≠ 0 implicitly assumes access to labeled validation data, which is not always available.

• After restricting to validation-label-free setting, the advantage of GRADATE remains similar to, or even better than, what is reported in paper. To fairly address this concern, we restrict GRADATE to the label-free setting and re-evaluate its performance as follows. Specifically,

  • For Table 1, we report relative performance improvement (%) of GRADATE over the strongest baseline under all settings (i.e. GNN + X% selected data with Dataset Y)
  • For Table 2, we include the (i) best GDA baseline out of the four considered in paper (termed as "Best GDA"), (ii) three new GDA methods (including A2GNN-ADV [1], A2GNN-MMD [1], and TDSS [2]), and (iii) data selection methods combined with the best GNN backbone (termed as "Best Random", "Best LAVA" and "GRADATE"). The numbers represent mean performances. Note that we use bold and italic to indicate the 1st/2nd best results.

• Table 1 (GRADATE outperforms other data selection methods)

• Table 2 (GRADATE outperforms GDA baselines and other selection methods)

(W4) Despite approximations, the method’s time complexity remains high and could limit scalability.

Thank you for raising the concern. We have reported the runtime of GRADATE on three TUD datasets in Section L (Table 10 in line 724) to demonstrate the real-world efficiency of GRADATE. Here, we also provide the runtime on three other OGB datasets. Even for the largest dataset (i.e. ogbg-molhiv , which contains ~42K graph samples), the empirical runtime of GRADATE remains moderate relative to the GNN training time.

• Table 3 (Runtime (in second) of GRADATE)

[1] https://arxiv.org/abs/2402.05660

[2] https://arxiv.org/abs/2412.11654

[3] https://arxiv.org/abs/2403.01092

[4] https://dl.acm.org/doi/abs/10.1145/3503161.3548012

[5] https://arxiv.org/abs/2306.04979