Graph Data Selection for Domain Adaptation: A Model-Free Approach
Authors: Ting-Wei Li
Ruizhong Qiu
Hanghang Tong
Venue: NeurIPS 2025 poster ()
Keywords: data-centric AI
domain adaptation
graph machine learning
Primary area: general_machine_learning
TL;DR: We propose a model-free data selection method to address domain adaptation problem for graph classification.

Abstract: Graph domain adaptation (GDA) is a fundamental task in graph machine learning, with techniques like shift-robust graph neural networks (GNNs) and specialized training procedures to tackle the distribution shift problem. Although these model-centric approaches show promising results, they often struggle with severe shifts and constrained computational resources. To address these challenges, we propose a novel model-free framework, GRADATE (GRAph DATa sElection), that selects the best training data from the source domain for the classification task on the target domain. GRADATE picks training samples without relying on any GNN model’s predictions or training recipes, leveraging optimal transport theory to capture and adapt to distribution changes. GRADATE is data-efficient, scalable and meanwhile complements existing model-centric GDA approaches. Through comprehensive empirical studies on several real-world graph-level datasets and multiple covariate shift types, we demonstrate that GRADATE outperforms existing selection methods and enhances off-the-shelf GDA methods with much fewer training data.

Graph Data Selection for Domain Adaptation: A Model-Free Approach
Ting-Wet Wei Li University of Illinois Urbana- Champaign, IL USA twli@illinois.edd
Ruizhong Qiu
Hanghang Tong
University of Illinois Urbana- Champaign,,,, IL USA rq5@illinois.edu
University of Illinois
Urbana Chama--a,,,,inn USA
htong@i 1iniiii.iiio...ee edu
Abstract
Graph domain adaptation (GDA) is a fundamental task in graph machine learning, with techniques like shift-robust graph neural networks (GNNs) and specialized training procedures to tackle the distribution shift problem. Although these model- centric approaches show promising results, they often struggle with severe shifts and constrained computational resources. To address these challenges, we propose novel model-free framework, GRADATE (GRAph DATa sElector), that selects the best training data from the source domain for the classification task on the target domain. GRADATE picks training samples without relying on any GNN model's 's predictions or training recipes, leveraging optimal transport theory to capture and adapt to distribution changes. GRADATE is data-efficient, scalable and meanwhile complements existing model-centric GDA approaches. Through comprehensive empirical studies on several real-world graph-level datasets and multiple covariate shift types, we demonstrate that GRADATE outperforms existing selection methods and enhances off-the-shelf GDA methods with much fewer training data.
Introduction
Graphs have emerged as a fundamental data structure for representing complex relationships across diverse domains, from modeling molecular interactions in biological networks [3] 6 37 85 to
capturing user behaviors in recommendation systems [5 19 g 9 73 In graph-level classification
where the goal is categorize graph structures, the distribution shift between source and target domains poses significant challenges. While numerous graph neural network (GNN) methods have been proposed for graph domain adaptation (GDA) [6] 12 62 55
tasks [64 666
81
20 38
they predominantly relies on model architecture design and training strategies, which are inherently model-de modee-deeendent and brittle. This model-centricity introduces practical challenges: (i) the need for extensive resources to train and validate different architectural variants and (ii) the ignorance of source data quality. To address these aforementioned issues, rather than relying on sophisticated GNN architectures or training procedures, we aim to answer fundamental question:
How select the relevant source domain data, based available validation data, for betler gruph-level classification accuracy evaluated on the larget domain ?
In this paper, we propose a model-free method, GRADATE (GRAph DATa sElector), that selects subset of important training data in the source domain independently any specific GNN model design, making it both data-efficient and versatile. GRADATE reduces computational overhead and enables quick adaptation to unseen graph domains based on available validation data. Conceptually, Saatmoo-Wssseeeeeii Wasserstein (FGW) distance [57] compare graph samples. We provide a theoretical justification to demonstrate FGW's 's unique advantage over multi-layer GNNs for graph comparison. Then, FGW is used building block measure the dataset-level distance between training and validation sets, which is termed as Graph Dataset Distance (GDD). Through
GRADATE first leverages Fused Gromov-
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

theoretical analysis, we demonstrate that the domain generalization gap between source and target domain is opper-bounded by GDD, which naturally motivates us to minimize this GDD between training and validation sets by identifying the optimal subset of training graph data. At the core of GRADATE lies our novel optimization procedure, GREAT (GDD shRinkagE via spArse projecTion), that interleaves between (i) optimal transport-based distribution alignment with gradient updates on training sample weights and (ii) projection of training sample weights to sparse probability simplex. This dual-step process systematically increases the weights of beneficial training samples while eliminating the influence of detrimental samples that could harm generalization performance.
By extensive experiments on six real-world graph-level datasets and two types of covariate shifts, we first show that GRADATE significantly outperforms existing data-efficient selection methods. When coupled with vanilla GNNs that are only trained on its selected data, GRADATE even surpasses state-of-the-art GDA methods. Intriguingly, the practical implications of GRADATE extend beyond mere data selection. By operating independently of model architecture, GRADATE can seamlessly complement existing off-the-shelf GDA methods, further enhancing their performance through better data curation while significantly improving the data- data-efficiency.
In summary, our main contributions in this paper are as follows:
Theoretical justification of FGW distance. We show in Theorem 3.1 that the output distance
of multi-layer GNNs is apper-bounded by Fused Gromov-Wassersten Wasserstein distance (57] between graphs, which motivates us to use FGW as a building block to compare graphs.
2. Novel graph dataset distance formulation. Through Theorem 3.3] we prove that the graph domain generalization gap is upper-bounded by a notion of Graph Dataset Distance (GDD).
3. A strong model-free graph selector. We introduce GRADATE (GRAph DATa sElector) the first model-free method tailored for domain shift problem for graph-level classification tasks, complementing the predominant model-centric GDA methods (see Section 4.2).
4. A data-efficient and powerful GDA method. We show that trained with data selected by GRADATE, even vanilla GNN can beat sophisticated GDA baselines (see Section 4.3)
5. A universal GDA model enhancer. We demonstrate that the data selected by GRADATE can be combined with GDA methods to further enhance their performance and efficiency (see Section 4.4)
The rest of the paper is organized as follows. Section introduces needed background knowledge. Section details our definition of Graph Dataset Distance (GDD) and proposed GRADATE, followed by experimental results in Section 4 Section 5 presents related works. Finally, the conclusion is provided in Section 6
2 Preliminaries
In this section, we briefly introduce optimal transport and graph optimal transport, which are funda- mental background related to proposed method. We also provide the formal problem formulation of graph domain adaptation (GDA) in Appendix K
2.1 Optimal Transport
Optimal transport (OT) 27 defines distance between probability distributions. It is defined as follows:
given cost function d(.,-) X'x - RR20 and probability distributions p. E P(2)), where X' is metric space, (p, q. d) min Jxxx d(x, x')=(1 x²) dædx', where 11(p, q) is the set of couplings with marginals and q. For supervised learning scenarios, we consider the empirical measures: p - 8s, and q = >Ø= day. where 8 is the Dirac delta function. With the pairwise cost matrix M = [d(x,, 25) we can re-formulate the OT problem as OT(p, q, d) = OT(P, q, M) e min Ei= E My
Optimal Trunsport Dataset Distance (OTDD). Alvarez-Melis and Fusi 2 construct a distance metric between datasets, where each dataset is represented as a collection of feature-label pairs (z. E ((= X Y). The authors propose label-specific distributions, which can be seen as distributions over features X of data samples with specific label y, i.e. a:y (x) & P(X y). The metric on the space of feature-label pairs can thus be defined as a combination of feature distance and label distance: dz((z, v), (a', v)) A (d)( + + aty ) where dx is metric on X,
d(ay,
2

---

d(ay, avy) ) is the label distance between distributions of features associated with labels and y', r 2 1 the order of the distances and 0 is pre-defined weight parameter. Consider two datasets D,
:. Dr = {=] (2f, ) [e(js)] and their corresponding uniform empirical distribu- {2f (xf, vt ie|m.).
tions p. 9 E 2, where p E mi pug and q Di=1 ng dzf, OTDD between D, and D, is com- puted as: OTD D₂) = (P q, dz) = OT q. M) minxell(p.a) (e) (dz (z", =*)],
where (p, q) is the set of valid couplings and M [dz (2 29)1e; kj is the pairwise cost matrix.
2.2 Graph Optimal Transport
The Fused the
(FGW) distance [57] integrates the Wasserstein distances [52 and distances [54] 42). Formally, a graph G with nodes can be represented as a distribution over vectors in d-dimensional space, where d is the dimension of the node feature. The features are represented as X E Rnxd and the structure can be summarized in an adjacency matrix A E R=xa We further augment G a probability distribution p R" over nodes in the graph, where Σi= P: = 1 and P: 2 0, vi E [n]. To compute FGW distance between two attributed graphs (9) {A, P1) and G2 = (A2, X2.2)) we use pairwise feature distance as inter-graph distance matrix and adjacency matrices as intra- similarity matrices. The FGW distance is defined as the solution of the following optimization problem: FGW (91, 92) A FGW (I
Xgbiibby A1, A Pr. P2,
+
min *Ell(pr.Ps)
(1-
X + (l) A20.D)
where 11(pI. p2) A { = PI, T = P2, n 2 0} is the collection of feasible couplings
between D1 and P2. a E [0, acts trade-off parameter, and 2 1 is the order of the distances.
3 Methodology
In this section, we propose our framework, GRAph DATa sElector, abbreviated as GRADATE. In Section 3.1 we first introduce Theorem 3.1 to motivate our use of LinearFGW 46) for graph distance computation. After that, we define the Graph Dataset Distance (GDD). which measures the discrepancy between graph sets, In Section [.2] we provide Theorem 3.3 to bound the domain generalization gap using GDD and then propose GDD minimization problem that is solved by novel optimization algorithm, GREAT (GDD shRinkagE via spArse projecTion). Finally, we introduce GRADATE that combines GDD computation and GREAT to select the most important subset of the training data to solve graph domain adaptation problem (definition is detailed in Appendix K).
3.1
Graph Dataset Distance (GDD): A Novel Notion to Compare Graph Datasets
3.1.1
FGW Distance For Graph Comparison
Challenges in Graph Distance Computation. To find the optimal samples that can achieve bet- ter performance on the target domain, we first need an efficient way that can accurately capture the discrepancy among graphs. To achieve this, most methods rely on Graph Neural Networks (GNNs) 62 55 72 obtain meaningful representations of these structured objects. However, these approaches face critical limitations: (i) high computational complexity to train on full training set and (ii) sensitivity to GNN byper-parameters. To address these drawbacks, we propose to use FGW distance [57] for replacing GNNs. As demonstrated in the following Theorem 3.1 FGW offers provable advantages that make it more suitable than GNNs to compare attributed graphs.
Theorem 3.1. Given two graphs G1 (A1,X) and G2 (A2, X2), for a k-layer graph neural network (GNN) f with ReLU activations, under regularity assumptions in Appendix F.I.I we have
dw(f(()).f(St < C FGW (2),
(1)
where dw denotes the r- Wasserstein distance, C and 3 are constants depending on GNN f. regularity constants and k.
Proof. The proof is in Appendix F1
3

---

We have the following two main insights: (1) since the theorem holds for any possible k-layer GNNs, with ReLU activations, FGW is provably able to capture the differences between attributed graphs in a way that upper-bounds the discrepancy between learned GNN representations; (ii) to the best of our knowledge, this is the first time that FGW is proved to be the distance metric that enjoys this theoretical guarantee, and hence we adopt it as the major basis for our graph data selection method.
Implication of Theorem 3.7
Practical Consideration. We utilize LinearFGW [46] as an efficient approximation of FGW dis- tance. Formally, LinearFGW defines distance metric diineurr where dimeattrGW (9,, is the LinearFGW distance between any pair of graphs Gi Gj. LinearFGW offers an approximation to FGW with linear time complexity with respect the number of training graphs. While we omit the details of LGW here for brevity, they can be found in Appendix and Algorithm T
3.1.2 Graph-Label Distance
With FGW as a theoretically grounded metric for model-free comparison between individual attributed graphs, we further extend it to compare sets of labeled graphs across domains, which aids our domain (detailed in Section 2.T]. we extend the original definition of label distance to incorporate distributions in graph subsets S, namely ag and ag. Given a set of labeled graphs D = {9i, yi J and label set V, we formulate the graph-label distance between label E y in graph subset S = { y heess S D and label y' y in graph subset S' = 19 "v²" hesss" C D as follows:
adaptation process. Inspired by OTDD 2
d(ay a OT(P, S b dLinsarFGW).
(2)
3. =vl =y are label-specific uniform empir- ical measures with the distance metric measured by LinearFGW. Intuitively, we collect graphs in subset S with label y and graphs in subset S" with label y' as distributions. Then, we compute the optimal transport distance between these distributions and define the distance as graph label distance.
where p b:y =y
En
3.1.3 Graph Dataset Distance (GDD)
Building upon the aformentioned graph-label distance, we then propose the notion of Graph Dataset Distance (GDD), which compares two graph subsets at detaset-level. Specifi- cally, based on Equation (2). we can define a distance metric dø2 between graph subsets S.S':
(9 uf (9 ., -u²")) drinear (9, ,955 a
(3)
which is a combination of Lin distance and graph-label distance with a weight parameter 2 0 balancing the importance of two terms. GDD can thus be defined as:
GDD(DS D = OT(p q. dzz),,
where Dd [ST Eielss 60p )²) and q
E 8 (g y are uniform empirical mea-
sures. We summarize the computation of GDD in Appendix and Algorithm 2
Remark 3.2. If we set = 0, GDD will omit the label information and only consider the distributional differences of graph data themselves, which matches the setting of unsupervised GDA problem.
3.2
GRADATE: A Model-Free Graph Data Selector
3.2.1 GDD Bounds Domain Generaization Gap
We give the following Theorem 3.3 to elucidate the utility of GDD and its relation to model per- formance discrepancy between graph domains. short, we seek to utilize empirical observations in the source domain to minimize the expected risk calculated on the target domain Pt, namely, which promotes the model performance (i.e., lower expected risk) on the
[L(())))) P, target domain.

---

Theorem 3.3 (Graph Domain Generalization Gap). Define the cost function among graph-label pairs as dy with some positive e (via Equation (3V). Let w denote the source distribution weight. Suppose that Lzz C-iischiizz Then for any model f trained on a training set, we have
E
(C
5
E (9. (9.u)~-phi(w))
(C(T()),)) v)) C GDD((DW :
(
where (DD( D = OT(p train (w), q dzzz) is the graph dataset distance between the weighted training dataset (defined by w) and target dataset.
Proof. The proof can be found in Appendix
Implication of Theorem 3.3 If we can lower the GDD between training and validation data, the discrepancy the model performance with respect to training and validation sets may also decrease. Specifically, under the scenario where distribution shift occurs, some source data might be irrelevant or even harmful when learning GNN model that needs to generalize well on the target domain. This motivates us to present our main framework, GRADATE (GRAph DATa sElector), which selects the best training data from the source domain for graph domain adaptation.
3.2.2 GDD Minimization Problem
Guided by the implication of Theorem 3.3 we formulate the GDD minimization problem follows.
Definition 3.4 (Graph Dataset Distance Minimization). Given training and validation sets Dirain and D we aim to find the best distribution weight w that minimizes GDD betwen the training and validation sets under the sparsity constraint. Namely,
min OT(p tiii (w)) qadl dzz),
S.L.
Σ W 1, 2 0, 11 S [n.
(5)
where p priin = EiE(())
and nrd
1
Eye(m) (appl -
Optimization Procedure (GREAT algorithm). To solve the above GDD minimization problem, we propose GREAT (GDD shRinkagE via spArse projecTion) to optimize the weight w over the entire training set. Starting from uniform training weight vector w, GREAT iteratively refines the importance of training samples through two key steps. In each iteration, it first computes the Graph Dataset Distance (GDD) between the reweighted training distribution train (w) and the validation
distribution nd using pairwise cost matrix D Raxm that encodes distances between individual training and validation samples. The gradient of GDD with respect to w, denoted gw. is then used to update the weight& Following this, the weight vector largest entries and re-normalized to remain on the probability simplex. After T such iterations, the non-zero indices in the final define the selected training subset S. The detailed algorithm procedure is presented in Appendix C and Algorithm] 3
sparsified by retaining only the top-k
3.2.3 GRADATE
Combining GDD computation and optimization module GREAT, summarize the main procedure of GRADATE in Algorithm 4 (details can be found Appendix D). In short, given training and validation data, GRADATE iteratively calculates GDD based current training weight and searches for a better one through GREAT. The final output of GRADATE corresponds to the selected subset of training data that is best suitable for adaptation the target domain. We further provide the time complexity analysis of GRADATE as follows.
Time Complexity of GRADATE. Let N be the number of training graphs, M be the number of validation graphs, n be the number of nodes in each graph (WLOG, we assume all graph share the same size), L be the largest class size, the approximation error introduced by approximate OT solvers 2] K be the number of iterations for solving LinearFGW, and the number of update steps used in GREAT The runtime complexity can be summarized in the following proposition.
Note that we leverage the conclusion introduced in 2 to compute this gradient (stated as Theorem F3 2This due to the entropic regularization Sinkhom iterations for empirical OT calculation. For empirical runtime behavior, we refer readers Appendix
5

---

Proposition 3.5 (Time Complexity Analysis 2 26 1). The off- procedure of GRADATE (i.e. can be computed before accessing the test set) has the time complexity O +NML log and the on-line procedure of GRADATE has the time complexity O (oa(m, M))
4 Experiments
We conduct extensive experiments to evaluate the effectiveness of GRADATE across six real-world graph classification settings under two different types of distribution shift. Our experiments are designed to answer the following research questions:
(RQI): How does GRADATE compare to existing data selection methods?
(RQ2): How does GRADATE vanilla GNNs compare to model-centric GDA methods?
(RQ3): To what extent can GRADATE enhance the effectiveness of model-centric GDA methods?
We will answer these research questions in Section 4.2
4.3 and 4.4 correspondingly.
4.1 General Setup
In this section, we state the details of datasets and settings of GRADATE and baseline methods.
Datasets and Graph Domains. We consider graph classification tasks conducted on six real-world graph-level datasets, including IMDB-BINARY [69), IMDB-MULTI [69], MSRC_2 21 (45). ogbg-molbace [22], lgbg-molbbbb [22] and ogbg-molhiv [22) The former three datasets are from the TUDataset [4;; while the latter three datasets are from the OGB benchmark [22). We define the graph domains by graph density and graph size, which are the types of covariate shift that are widely studied in the literature [72 [1 [66 S 71 10, 84). Specifically, graphs are sorted by corre- sponding properties in ascending order and split into train/val/test sets with ratios 60% 11%%//0%/ 22%%/20% For brevity, we provide results on graph density shift in the main content. Additional experiments on graph size shift can be found in Appendix G We also include the empirical cumulative distribution function (ECDF) plots of all settings in Appendix P to demonstrate the shift level.
Details of GRADATE and Baselines. To compute I LinearFGW within GRADATE, follow the default parameter settings in its github repository The trade-off parameter a is computed in 5 and the order r' set to 2. The update step fixed to T 10 and the learning rate equal
{0.5, 0.93 to = 10 across different settings. A popular model-free data valuation method is LAVA [26). We apply LAVA for graph data selection and make the following modifications. We first leverage LinearFGW to form the pairwise distance matrix and compute GDD. LAVA then picks the smallest k entries of the calibrated gradients as output. For the computation of GDD, we consider label signal E {0, 5). We also incorporate KIDD-LR [66] model-centric but data-efficient baseline, which a state-of-the-art graph dataset distillation method.
4.2 GRADATE as a Model-Free Graph Selector
To answer (RQ1), we compare GRADATE with other data-efficient methods, including (1) model-free techniques: random selection and LAVA 2 and (2) model-centric techniques: KIDD-LR [66].
Experiment Setup. To test the effectiveness of these selection methods, fix the backbone GNN models in use to train the data selected by each method. Two popular GNN models are chosen, including GCN (30] and GIN (65] with default syper--arameters following Zeng et al. [81] and the corresponding original papers. We also consider results on GAT (58) and GraphSAGE [8]. Please see Appendix G. G.2 and G.3 for more details. Here consider selection ratio E 0...,..2.0.5).
More details on the architectures and training protocol can be found in Appendix !|
across all datasets, GRADATE outperforms the baseline methods Results. As shown in Table I
under different selection ratios. It is also worth noting that even with few selected data, GRADATE
http://ggihubbboommmaangggg/g//e FnneaF/GG
"Sinee the datasets do not contain node features, we consider larger a to place greater emphasis on the structural properties.

---

GNN Architecture
GCN
GIN
Selection Method
10%6
207%
50%
Pull
F 10%
20%
50%
Poll
Random KIDD-LR
0.660).
0.868
0,600
0.710s
0.7704
0.7874
0.810 ove
0.682
0.772
0.795:
IMDB-BINARY
LAVA
0630
0.621 0100
0.620 onee
0.822
0.777 36
0.795 moe0
80002
0.783
GRADATE
0.00
0,855 0004
1.N90 oons
0,800 1038
0.832 poee
0.900 nots
Random
0.139 0212
0.092s 0502
0.080 ouee
0.102s 2015
0.180 cued
0. 156s eas7
IMDB-MULTI
KIDD- LR
LAVA
0 wo0
0.1561:8140 0.
0,171
00002
0,058:
0.190
0.093
0.077
0.143
GRADATE
0.34
0.183
0.266 613
Randoen
0.576
0.7022
0.800
0.427 3.35
0.801
001s
0.857 n011
MSRC
KIDD-LR
LAVA
w.70
0623
0.7662 9303
0.84K UARA
0.895
0.860
0.763 2825
0,667
0,851 0000
0.792 w0t
0 36344 om1
9333 000
0.883gn015
GRADATE
0.719
0.797
0,906
0.787
0,860
0.942
a
0.575
2012
0.621 10C7
0.537
ogbg-axebace
KIDD-LK LR
LAVA
0.592
0,484
0,637
0.592
0.637
0004
0.617 200T
0,802
0.913=2200
0.456 NAM
0.633 WIM
0 0.589: oas
0.672+ 0122
0.560.000
GRADATE
0.66
0.578 9005
0.614: 0003
0.642 3043
0.660 pnts
0.684; nahh
Random
0,488: 0.567
D.478:
agig-mmol bobbp
KIDD-LR
LAVA
0.5962
0.977=
0.566 9101
0.547 0064
0.478.0006
0.424
30619933044
0.642 0119
0.16122038
0.747.2
0.671
GRADATE
0.604: 0.3
0,601 spi7
0.557
600
0.657 2039
0.677
num
0.715 0015
Random
0,003 nar
0,615 8:04
0.621 one
0.608 2015
0.609 oee
0.593 0012
egig oggg-xelbiv
KIDD-LI LR
LAVA
0.590s o.0
0.531
0.608
0,504::
0.625
0.597
0.614
0.595
0.638:
60008:11
0.596.0315
GRATDATR
8.607
0.599
0.622: 0101
0.640
0.65%:nnas nois
Table 1: Performance comparison across data selection methods for graph density shift. We use bold/underline to indicate the 1st/2nd best results. In most settings, GRADATE achieves the best performance across datasets.
already achieve excess GNN performance trained with full data, showing the importance of data quality in the source domain. The main reason is that because under distribution shift, a certain number of harmful graphs exist in training set. These samples mislead the model and degrade generalization performance.
4.3 GRADATE GDA Method
We answer (RQ2) by directly compare the combination of GrADATE and vanilla GNNs (including non-domain-adaple adapted GCN, GIN, GAT and GraphSAGE) with state-of- ofetthe-art GDA models. We fix the sparsity ratio 7 to 20% across all selection methods.
Experiment Setup The four GDA methods we consider include AdaGCN [1], GRADE [61]. ASN 83 and UDAGCN 622. We conduct GDA experiments based on the codebase of OpenGDA [53). We include more details of model-speeific parameter settings in Appendix We set the training set the source domain and the validation set as the target domain. For GDD computation, we set label signal c = 0 to match the requirement of unsupervised GDA methods. Results on graph size shift can be found in Appendix G.4
Results. Results are in Table 2 For model-centric GDA methods trained with full training data, the severe domain shift prohibits these methods from learning rich knowledge to perform well on the test data in the target domain. Instead, GRADATE finds the most useful data in the training set that results in simple GNN models with extraordinary classification accuracy while maintaining data efficiency. In addition, similar to the observation in Section 4.2 GRADATE selects non-trivial training data that outperforms other model-free data selection methods. In Appendix
4.4 GRADATE Model-Free GDA Enhancer
In order to answer (RQ3), we combine GATE with off-the-shelf GDA methods to study whether fewer but better training data can lead to even stronger adaptation performance.
Experiment Setup. Coupled with 10%, 20%, 50% data selected by each model-free method (i.e., random, LAVA and GRADATE), four GDA baselines (considered in Section[4.3 are directly run on the shrunk training dataset with the same validation dataset under graph density shift. For results on graph size shift, we refer the readers to Appendix G.5
7

---

Dataet
Type
Model
Data
BIBB-BINARY
IMDB-MULLE
MSRC_21 21
ogbg-aolbace
ogbg
bbbbb
ogbg-nolbiv
AdsGCN
0.073 tuxo
0.319
0.778
0.428 wdt1
GDA
GRADE
ASN
Fall
Pall
0,7821
0.822
0.119 0017
0.123: 1001
0,833 om0
0.804 0001
0:5801 oies
0.683 cute
0.489
0.476110007
0.516, n0t
0.564: was
UDAGCN
Fall
0.807..48:3
0.114;
0.351
0.541
0.522
0.451:
Random 20%
0862
0.022 0002
0,702 D00
0.529 0.124
0.528:20.00
0. 0.59%= 000
GCN
LAVA 20%
0.6200a 0.00
01092 note
0.8 19819gm0 2011
0.541 o067
0.5032.000
0. 0.591 0030
GRADATE 20%
0.830s
0.349 0323
0.797
0.585
0.5
0.583=
0.74
0.100= tuee
0.480
0.590
GIN
LAVA 20%
0.778=
0.170 tome
0.851 6012
0.655 coed
0.6
0.638- 0012
GRADAYH 20%6
088
0,266) 6353
01860 ox0n
0.662 5ree
0.665 1005
0.644 0017
Vanilla
Random 209
0.6
0.077
0.713
0.472.
4.4861
1.993_
GAT
0.835
tuxc
exds
0.515 2009
0.511 d.ea
0.602; wd17
GRADATE 20%
0.868:
0,800 0,188
0.852 9006
0,5 18 6x0e
0.338 0.099
0. 1.59% 0003
Random 20%
0.7
0.132 tubs
0.731
0.4 0.45 cue7
0.472+
0 00:02= 0000
GraphSAGE
0.835:20000
6,33
0,491
GRADATE 20
0.855 0.8c
0.580 0220
0.842 Buen
0.536 cuea
0.533 0.07
0 0.54 1 0014
Table 2: Performance comparison across GDA and vanilla methods for graph density shift. We use bold/underline to indicate the 1st/2nd best results. GRADATE can consistently achieve top-2 performance across all datasets.
Results. As shown in 3 for most of the settings, GRADATE selects data that is the most benefi- cial to adapting to the target set. Notably, across many settings, only 10% or 20% GRADATE-selected data can outperform naively applying GDA methods on the full training data. This suggests that GRADATE can indeed improve dala-efficiency by promoting the quality of training data. Furthermore, 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.
4.5 Further Discussion
LAVA vs GRADATE. The modified version of LAVA utilizes LinearFGW to compare graphs and selects the training data with the smallest gradient value w.r.t. GDD. contrast, GRADATE aims at finding optimal training data that directly minimizes GDD, which has complete different motivation and enjoys a theoretical justification. Empirically, we also observe the superiority of DATE in most cases. Occasionally, LAVA achieve marginally better results than GRADATE, which may be attributed to the approximation error of LinearFGW and thus over-optimization on GDD.
Random vs GRADATE. From Table we found GRADATE occasionally underperforms random selection with GrE, possibly because the neighbor sampling strategy introduces noise into global representations, weakening the supervision signal even for well-chosen training graphs
Selection Ratio vs GNN Performance. From Tables & we find that larger selection ratio may not always guarantee a better performance for selection methods including LAVA and GRA DATE. This is because, under severe distribution shift between domains, larger portion of training data may actually contain patterns that are irrelevant or even harmful to the target domain.
Effect of label signal c. While we treat e as a tunable ppprr-prramttr that can be optimized for different settings (i.c. various combinations of dataset, shift types and selection ratio), we empirically find that searching within {0, 5) can already lead to good performance throughout all experiments in this paper. We also provide additional experiments under a label-free setting (i.e. c is forced to be equal 0) in Appendix G.6
5
Related Work
Data Selection. Recent advancements in data selection have focused on optimizing data utilization, mainly on text and vision data to facilitate efficient training for large language/image models (2 28
43 3
63
13
70 35 For general model-free data selection, LAVA (26] offers a learning-agnostic
data valuation method by seeking the data point that contributes the most to the distance between training and validation datasets. However, the paper studies predominantly on raw image datasets such
8

---

GDA Melhod +
AdaGCN
GRADE
Selection Method|
7- 107
2036
50%
Full
107%
20%
1036
Full
Random
0.263
0,373,
0
0.683:
0.792
0,780
AIDB-BINARY
LAVA
0.623
066724900
0.508
0.620
0.627=
0,680
0.822 w012
GRAD
0810 o0e2
0.817 1022
4.822
0.7822
0.832
0003
0.848
Random
0.100 ooee
0.168 oxrz
0.1161
0.106 c.5s
0.112
0059
0. 1. 0010
IMDB MULTI
LAVA
0.19 onen
0.182 nue
0. 1.44 0.00
0.073 0:00
0,183 0.00
0.189
0.186 0000
0.123
GRADATE
0,333
0.373
0.391 291
0.15
0,386
(399
0.173 13
Ramdon
0.20%
4.3
0.512
0.626
MSRC_21
LAVA
0.398 0004
0.456: o012
0.450 0.301
0.319 0232
0
0.743
0003
0.860s
0.504 0:11
GRADATE
0.415 6012
0.406s 0043
0.664: 0.21
0.778
0003
0.865 EUIT
Random
0.466 one
0.485 wors
9.565
0.5
0.554
1805
0.61 1z tors
oglg-mmo back
baec
LAVA
0.574: o00
0.5802 no14
0.5572-1655
0.653
1001
0.625
0.683
GRADATE
0.598
0.614:
0.572
0.599 0.44
0.636
0.634
Rundom
0.494a o014
0,469
4.527
0.51
0.433
5000
0.495
ogig-mol bhhp
LAVA
0.583 owns
0.556 o014
0.5611-439
0.778
0.549
0.579
0001
0,543
0
GRADATE:
0.593 oons
0.596 nots
0.5461 98%
0.582 0877
D. 1-103-
5003
0.490 6/066
Random
0.407 ove
0.429 0
0.417
0
0,544 CA00
0.58 tuee
ogog zolbiv
LAVA
0:053
12
0.440+
0.566
0
0,572
0.561
GRADATE
0.584
0.589
GDA Method
ASN
UDAGCN
Dataset
Selection Method
10%
20%
50%
Full
10%
2076
10%
Full
Random
0.660: on0
0.702
4.6784--331
0.620
0.263
0.823:
IMDB IMDB-BINARY BINARY
LAVA
0.733 one
0.620 waw
0.620g-1300
0.782+ 430
0.620=-2001
0.643 USe
0.620
0.807
GRADATE:
0.748: 0001
0,818: n016
0.770 2485
0.847
2003
0.852 6006
Random
0.126 om0
0.101 nors
O. 0.15
0.150 4804
0.101
2015
0,076 0000
IMDB-MULTI
LAVA
0,183
0,183
1,09
0.119
0,183
0.183
0,182
0.114a
GRAD
0,292
1
0.554
Random
=:421 one
0.673umm
4
0.287
0.178
0.287 tono 0.623 ouee
MSRC_21
LAVA
0.638 0015
0.740 o01e
0.868 a 0.344
0.833 8003
0,453 c035
0.442
0003
0.35 0019
GRADATE
0.687 onss
0.804: 0321
0.904 0312
0.444: 2048
0,453 5001
0.664 D0129
Ramdon
0.539
0.507
0.47
0,581
1.513
ophg-mol bace
LAVA
0.57N:
0.5801
0.562
0.578
0.54
GRADATE
0.636 oxe2
0.596
0
0.533
0.565
b009
Random
0.504 non
0.533 outs
a 0332
0.538 ca2s
0.529
D043
0.530 tuet
ogbg-mol bhhp
LAVA
0.567: onn
0.616 nom
0.573 9935
0.4762
0.579
0,547
1400
0.558 0001
0.522 wa1s
GRADATE
0.573 orea
0. 1.59 10100
03535 w887
0,575
6009
0,570
Random
0.436
0.483
0.455
0,45
0.406
0.464
ogog zolbiv
LAVA
0.511= ow0s
0.540 onto
0.482 0.823
0.516 amzi
0.458=
0.427 EX07
0.445
0.45
GRADATE
0.527
D:491 12 (185
0.445 EVII
0:444
Table 3: Performance comparison across combinations of GDA methods and data selection methods for graph density shift. We use bold/underline indicate the 1st/2nd best results. GRADATE achieves the best performance in most settings.
as CIFAR-10 31 and MNIST 32), where they already have high-quality pixel-value representations
for computation. Unlike text or images, graphs lack a natural and uniform representation, making the development of model-free data selection more intricate. Tailored for graph-level tasks, graph dataset distillation is also a related topic. For example, Jin et al. (25) and Xu et al. [66] both propose to formulate a bi-level optimization problem to train a graph-level classifier. Jain al. (24, on the other hand, utilizes Tree Mover Distance [IT to conduct graph-level sub- sampling with theoretical guarantees. However, these non-model-free methods might not be able to combat severe downstream distribution changes.
Graph Domain Adaptation (GDA). For grpah classification, GDA focuses on transferring knowl- edge from a source domain with labeled graph target domain. Model-centric GDA methods relying on GNNs have been pivotal in this area. For instance, Wu et al. (62) introduce UDAGCN, which integrates domain adaptation with GNNs to align feature distributions between domains. AdaGCN [12 addresses netss-k node classification leveraging adversarial domain adaptation to transfer label information between domains. Wu et al. [61] explore cross-network transfer learn- graph isomorphism test and introduce the GRADE algorithm that minimizes distribution shift to perform adaptation. ASN {3 explicitly separates nomain-privan and domain-shared information while capturing network consistency. More recently, Liu et al. (34] argue that excessive message passing exacerbates domain bias and propose A2GNN as a refined propagation scheme that disentangles transferable and domain-specifee information; Chen et al. 7
ing through Weisfeiler-

---

highlight the critical role of graph smoothness, presenting TDSS that enforces cross-domain consis- tency through spectral alignment. Meanwhile, Liu al. [36] introduce pairwise alignment strategy that leverages node-level relational matching to enhance inter-domain correspondence. However, these approaches mostly focus on designing architectures or training procedures and often rely heavily on the assumption that provided data in the training set is already optimal for the task, which is often
invalid in real-world scenarios.
6 Conclusion
We introduce GRADATE, model-free framework for graph classification that addresses distribution shift by solving a Graph Dataset Distance (GDD) minimization problem. By selecting the most beneficial data from the source domain, it offers novel approach to improving GNN performance without relying on specific model predictions or training procedures. We also establish theoretical analysis on Fused Gromov-Wor Wassersteen distance meaningful upper bound on GNN representation differences, and further justifies GDD an optimization target to improve generalization performance. Across multiple real-world datasets and shift types, GRADATE consistently outperforms existing selection methods and GDA methods with better data efficiency. For future directions, we consider graph continual learning and multi-source domain adaptation.
Acknowledgement
This work is supported by NSF (2416070) and AFOSR (FA9550-2441100022 The content of the information in this document does not necessarily reflect the position or the policy of the Government, and official endorsement should be inferred. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation here on.
10

---

References
[1] Jason Altschuler, Jonathan Niles-Weed, and Philippe Rigollet. Near-linear time approxima- tion algorithms for optimal transport via sinkhorn iteration. Advances in neural information processing systems, 30, 2017.
[2] David Alvarez-Melis and Nicolo Fusi. Geometric dataset distances via optimal transport. Advances in Neural Information Processing Systems, 33:21 13:21428--2449, 2020.
[3] Tianyi Bai, Ling Yang, Zhen Hao Wong, Jiahui Peng, Xinlin Zhuang, Chi Zhang. Lijun Wu, Jiantao Qiu, Wentao Zhang, Binhang Yuan, et al. Multi-agent collaborative data selection for efficient IIM pretraining. arXiv preprint 0rXiv:2410.08100 2024.
[4] Dimitri Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 48 5y:334-334 1997.
[5] Beatrice Bevilacqua, Yangze Zhou, and Bruno Ribeiro. Size-invariant graph representations for graph classification extrapolations. In International Conference on Machine Learning, pages 837-851, PMLR, 2021.
[6] Pietro Bongini, Niccolò Pancino, Franco Scarselli, and Monica Bianchini. Biognn: how graph neural networks can solve biological problems. Artificial Intelligence and Machine Learning for Healthcare: Vol. 1: Image and Duta Analytics, pages 211-231. Springer, 2022.
[7] Wei Chen, Guo Ye, Yakun Wang, Zhao Zhang, Libang Zhang, Daixin Wang, Zhiqiang Zhang, and Fuzhen Zhuang. Smoothness really matters: A simple yet effective approach for unsuper- vised graph domain adaptation. In Proceedings of the AAAI Conference on Artificial Intelligence,
pages 15875-15883, 2025.
[8] Zhiyong Cheng, Sai Han, Fan Liu, Lei Zhu, Zan Gao, and Yuxin Peng. Multi-behavior recommendation with cascading graph convolution networks. In Proceedings of the ACM Web Conference 2023, pages 1181-1189, 2023.
[9] Nikzad Chizari. Keywan Tajfar, and María N Moreno-García, Bias assessment approaches for addressing userecentered fairness in gan-based recommender systems. Information, 14(2):131, 2023.
[10] Xu Chu, Yujie Jin, Xin Wang. Shanghang Zhang, Yasha Wang, Wenwu Zhu, and Hong Mei. Wasserstein barycenter matching for graph size generalization of message passing neural networks. International Conference on Machine Learning, pages 6158-618 6184. PMLR, 2023.
[11] Ching- Yao Chuang and Stefanie Jegelka. Tree mover's distance: Bridging graph metrics and stability of graph neural networks. Advances in Neural Information Processing Systems, 35: 2944-20 2957, 2022.
[12] Quanyu Dai, Xiao-Ming Wu, Jiaren Xiao, Xiao Shen, and Dan Wang. Graph transfer learning via adversarial domain adaptation with graph convolution. IEEE Transactions on Knowledge and Data Engineering. 35(5):4988-4922) 2022.
[13] Simin Fan, Matteo Pagliardini, and Martin Jaggi. Doge: Domain reweighting with generalization estimation. arXiv preprint 2rXiv:2310.15.99) 2023.
[14] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: 1903:090,..,228, 2019.
[15] Chen Gao, Xiang Wang, Xiangnan He, and Yong Li. Graph neural networks for recommender system. In Proceedings of the fifteenth ACM international conference web search and data mining, pages 1623-1625, 2022.
[16] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Combining neural networks with personalized pagerank for elassification on graphs. In International Conference on Learning Representations, 2019. URLhtttss httttss://pperrevieett httpeewwwwwwwwwweeeeeeeeeee mett/ooummidd-Hl....
11

---

[17] Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773, 2012.
[18] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[19] Xiangnan He, Kuan Deng. Xiang Wang. Yan Li, Yongdong Zhang, and Meng Wang. Lightenn Simplifying and powering graph convolution network for recommendation. In Proceedings of the 43rd International ACM SIGIR conference on research and development Information Retrieval, pages 639-648, 2020.
[20] Xiaobin Hong, Wenzhong Li, Chaoqun Wang, Mingkai Lin, and Sanglu Lu, Label attentive distillation for gnn-based graph classification. In Proceedings of the AAAI Conference on Artificial Intelligence, 2024.
[21] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.006m 2020.
[22] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. Advances in neural information processing systems, 33:22118-222 13-2233,, 2020.
[23] Kexin Huang, Cao Xiao, Lucas M Glass, Marinka Zitnik, and Jimeng Sun. Skipgnn: predicting molecular interactions with skip-graph networks. Scientific reports, 10(1)2210 2020.
[24] Mika Sarkin Jain, Stefanie Jegelka, Ishani Karmarkar, Luana Ruiz, and Ellen Vitereik. Subsam- pling graphs with gnn performance guarantees. arXiv preprint arXiv:2502.16703, 2025.
[25] Wei Jin, Xianfeng Tang, Haoming Jiang, Zheng Li, Danqing Zhang, Jiliang Tang, and Bing Yin. Condensing graphs via one-step gradient matching. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 720-730, 2022.
[26] Hoang Anh Just, Feiyang Kang, Jiachen T Wang. Yi Zeng, Myeongseob Ko, Ming Jin, and Ruoxi Jia. Lava: Data valuation without pre-specified learning algorithms. arXiv preprint arXiv:2305.00055 2023.
[27] Leonid V Kantorovich. On the translocation of masses. In Dokl. Akad. Nauk. USSR (NS). volume 37, pages 199-201, 1942.
[28] Krishnateja Killamsetty, Sivasubramanian Durga, Ganesh Ramakrishnan, Abir De, and Rishabh Iyer. Grad-match: Gradient matching based data subset selection for efficient deep model training. In International Conference on Machine Learning, pages 5464-54555 5474. PMLR, 2021.
[29] Krishnateja Killamsetty, Durga Sivasubramanian. Ganesh Ramakrishnan, and Rishabh Iyer. Glister: Generalization based data subset selection for efficient and robust learning. In Pro- ceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 8110-8118, 2021.
[30] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint
2016.
[31] Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009. Technical Report.
[32] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 1):2278:227222 2324,, 1998.
[33] Ting Wei Li. Qiaozhu Mei, and Jiaqi Ma. A metadata-driven approach to understand graph neural networks. Advances in Neural Information Processing Systems, 16:15300-5534, 2023.
[34] Meihan Liu, Zeyu Fang, Zhen Zhang, Ming Gu, Sheng Zhou, Xin Wang, and Jiajun Bu. Rethinking propagation for unsupervised graph domain adaptation. In Proceedings of the AAAI Conference Artificial Intelligence, 2024.
12

---

[35] Qian Liu, Xiaosen Zheng, Niklas Muennighoff, Guangtao Zeng, Longxu Dou, Tianyu Pang. Jing Jiang, and Min Lin. Regmix: Data mixture as regression for language model pre-training. arXiv preprini arXiv:2407.01499 2024.
[36] Shikun Liu, Deyu Zou, Han Zhao, and Pan Li. Pairwise alignment improves graph domain adaptation. International Conference on Machine Learning, pages 32552-32575. PMLR, 2024.
[37] Tianyu Liu, Yuge Wang, Rex Ying, and Hongyu Zhao. Muse-gnn gnn: Learning unified gene repre- sentation from multimodal biological graph data. Advances in neural information processing systems, 36:24661 24677, 2023.
[38] Xingyu Liu, Juan Chen, and Quan Wen. A survey on graph classification and link prediction based on gnn. arXiv preprint arXiv:2307.00865, 2023.
[39] Zhining Liu, Zhichen Zeng, Ruizhong Qiu, Hyunsik Yoo. David Zhou, Zhe Xu, Yada Zhu, Kommy Weldemariam, Jingrui He, and Hanghang Tong. Topological augmentation for class- imbalanced node classification, 2023.
[40] Zhining Liu, Ruizhong Qiu, Zhichen Zeng, Hyunsik Yoo, David Zhou, Zhe Xu, Yada Zhu, Kommy Weldemariam, Jingrui He, and Hanghang Tong. Class-mballacee graph learning without class rebalancing. In Proceedings of the 4 41st International Conference on Machine Learning, 2024.
[41] Junyu Luo, Zhiping Xiao, Yifan Wang, Xiao Luo, Jingyang Yuan, Wei Ju, Langechuan Liu, and Ming Zhang. Rank and align: towards effective source-free graph domain adaptation. arXiv preprint arXiv:2408. 12185, 2024.
[42] Facundo Mémoli. Gromov-wasserstin Foundations of computational mathematics, 11:417-487, 2011.
wasserstein distances and the metric approach to object matching.
[43] Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovec. Coresets for data-efficient training of machine learning models. In International Conference on Machine Learning, pages 0950-6960.
PMLR, 2020.
[44] Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint w0Xiv:2007.08663, 2020.
[45] Marion Neumann, Roman Garnett, Christian Bauckhage, and Kristian Kersting. Propagation kernels: efficient graph kernels from propagated information. Machine learning, 102:209-244 2016.
[46] Dai Hai Nguyen and Koji Tsuda. On a linear fused gromov-wasserstein distance for graph structured data. Pattern Recognition, 138: 109351, 2023.
[47] Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. DIMES: A differentiable meta solver for combinatorial optimization problems. In Advances in Neural Information Processing Systems, volume 35, pages 25531-2553 -25546, 2022.
[48] Ruizhong Qiu, Gaotang Li, Tianxin Wei, Jingrui He, and Hanghang Tong. Saffron-1: Safety inference scaling, 2025.
[49] Ruizhong Qiu, Ting-Woi Wei Li, Gaotang Li, and Hanghang Tong. Graph homophily booster: Rethinking the role of discrete features on heterophilic graphs. arXiv preprint arXiv:2509.12538 2025.
[50] Ruizhong Qiu, Zhe Xu, Wenxuan Bao, and Hanghang Tong. Ask, and it shall be given: On the Turing completeness of prompting. In 13th International Conference on Learning Representations, 2025.
[51] Ruizhong Qiu, Weiliang Will Zeng. Hanghang Tong. James Ezick, and Christopher Lott. How efficient L.MM-geneateed code? rigorous & high-standard benchmark. In 13th International Conference Learning Representations, 2025. 2025.
13

---

[52] Yossi Rubner, Carlo Tomasi, and Leonidas J Guibas. The earth mover's distance as metric for image retrieval. International journal of computer vision, 40:99-121. 10199-11,2220 2000.
[53] Boshen Shi, Yongqing Wang, Fangda Guo, Jiangli Shao, Huawei Shen, and Xueqi Cheng. Opengda: Graph domain adaptation benchmark for cross-netwond learning. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pages 5396-54000 2023.
[54] Karl-Theodor Sturm. The space of spaces: curvature bounds and gradient flows on the space of metric measure spaces, volume 290. American Mathematical Society, 2023.
[55] Ke Sun, Zhanxing Zhu, and Zhouchen Lin. Adagen: Adahoosting graph convolutional networks into deep models. arXiv preprint / 2019.
[56] Yuhao Tang, Junyu Luo, Ling Yang. Xiao Luo, Wentao Zhang, and Bin Cui. Multi-view teacher with curriculum data fusion for robust unsupervised domain adaptation. In 2024 IEEE 40th International Conference on Data Engineering (ICDE), pages 2598-2611. IEEE, 2024.
[57] Titouan Vayer, Lactitia Chapel, Rémi Flamary, Romain Tavenard, and Nicolas Courty. Fused gromov-wasserstein distance for structured objects. Algorithmss, 13(9):212, 2020.
[58] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 2017.
[59] Wei Wang, Dejan Slepčev, Saurav Basu, John A Ozolek, and Gustavo K Rohde. A linear optimal transportation framework for quantifying and visualizing variations in sets of images. International journal of computer vision, 101:254-2611 2013.
[60] Fang Wu, Nicolas Courty, Shuting Jin, and Stan Li. Improving molecular representation learning with metric learning- caaming-enhanced optimal transport. Patterns, 4(4), 2023.
[61] Jun Wu, Jingrui He, and Elizabeth Ainsworth. Non-iid transfer learning on graphs. In Pro- ceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 10342-10350, 2023.
[62] Man Wu, Shirui Pan, Chuan Zhou, Xiaojun Chang, and Xingquan Zhu. Unsupervised domain adaptive graph convolutional networks. In Proceedings of the web conference 2020, pages 1457-1467, 2020.
[63] Sang Michael Xie, Hieu Pham, Xuanyi Dong, Nan Du, Hanxiao Liu, Yifeng Lu, Percy S Liang, Quoc Le, Tengyu Ma, and Adams Wei Yu. Doremi: Optimizing data mixtures speeds up language model pretraining. Advances in Neural Information Processing Systems, 36, 2024.
[64] Yu Xie, Yanfeng Liang, Maoguo Gong, A Kai Qin, Yew-Soon Ong, and Tiantian He. Semisu- pervised graph neural networks for graph classification. IEEE Transactions on Cybernetics, 53 (10):6222-6235. 2022.
[65] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint #:Xiv:/800.00822 2018.
[66] Zhe Xu, Yuzhong Chen, Menghai Pan, Huiyuan Chen, Mahashweta Das, Hao Yang, and Hanghang Tong. Kernel ridge regression- graph dataset distillation. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2850 2861, 2023.
[67] Zhe Xu, Kaveh Hassani, Si Zhang, Hanqing Zeng, Michihiro Yasunaga, Limei Wang, Dongqi Fu, Ning Yao, Bo Long, and Hanghang Tong. Language models are graph learners, 2024.
[68] Zhe Xu, Ruizhong Qiu, Yuzhong Chen, Huiyuan Chen, Xiran Fan, Menghai Pan, Zhichen Zeng, Mahashweta Das, and Hanghang Tong. Discrete-state continuous-time diffusion for graph generation. In Advances in Neural Information Processing Systems, volume 37, 2024.
[69] Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 1365-1374, 2015.
14

---

[70] Jiasheng Ye, Peiju Liu, Tianxiang Sun, Yunhua Zhou, Jun Zhan, and Xipeng Qiu. Data mixing laws: Optimizing data mixtures by predicting language modeling performance. arXiv preprint arXiv:2403. /6952, 2024.
[71] Gilad Yehudai, Ethan Fetaya, Eli Meirom, Gal Chechik, and Haggai Maron. From local structures to size generalization in graph neural networks. In International Conference Machine Learning, pages 1 11975-11986. PMLR, 2021.
[72] Nan Yin, Mengzhu Wang, Zhenghan Chen, Li Shen, Huan Xiong, Bin Gu, and Xiao Luo. Dream: Dual structured exploration with mixup for open-set graph domain adaption. In The Twelfth International Conference Learning Representations, 2024.
[73] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 974-983, 2018.
[74] Hyunsik Yoo, Zhichen Zeng, Jian Kang, Ruizhong Qiu, David Zhou, Zhining Liu, Fei Wang, Charlie Xu, Eunice Chan, and Hanghang Tong. Ensuring user-side fairness in dynamic rec- ommender systems. In Proceedings of the ACM on Web Conference 2024, pages 3667-3678, 2024.
[75] Hyunsik Yoo, SeongKu Kang, Ruizhong Qiu, Charlie Xu, Fei Wang, and Hanghang Tong. Embracing plasticity: Balancing stability and plasticity in continual recommender systems. In Proceedings of the 48th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2025.
[76] Hyunsik Yoo. Ruizhong Qiu, Charlic Xu, Fei Wang, and Hanghang Tong. Generalizable recommender system during temporal popularity distribution shifts. In Proceedings of the 31t ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2025.
[77] Qi Yu, Zhichen Zeng, Yuchen Yan, Lei Ying, R Srikant, and Hanghang Tong. Joint optimal transport and embedding for network alignment. In Proceedings of the ACM on Web Conference 2025, pages 2064-2075, 2075, 2025.
[78] Zhichen Zeng, Si Zhang, Yinglong Xia, and Hanghang Tong. Parrot: Position-awand regularized optimal transport for network alignment. In Proceedings of the ACM web conference 2023, pages 372-382, 2023.
[79] Zhichen Zeng, Ruike Zhu, Yinglong Xia, Hanqing Zeng, and Hanghang Tong. Generative graph dictionary learning. In International Conference Machine Learning, pages 40749-40766 PMLR, 2023.
[80] Zhichen Zeng, Boxin Du, Si Zhang, Yinglong Xia, Zhining Liu, and Hanghang Tong. Hierar- chical multi-marginal optimal transport for network alignment. In Proceedings of the AAAI Conference Artificial Intelligence, volume 38, pages 16660-16668. 2024.
[81] Zhichen Zeng, Ruizhong Qiu, Zhe Xu, Zhining Liu, Yuchen Yan, Tianxin Wei, Lei Ying, Jingrui He, and Hanghang Tong. Graph mixup approximate gromov-wasserstin geodesics. In Forty-first International Conference on Machine Learning, 2024.
[82] Zhichen Zeng, Ruizhong Qiu, Wenxuan Bao, Tianxin Wei, Xiao Lin, Yuchen Yan, Tarek F Abdelzaher, Jiawei Han, and Hanghang Tong. Pave your own path: Graph gradual domain adaptation on fused gromov-wasserstein geodesics. arXiv preprint arXiv:2505.122 12709, 2025.
[83] Xiaowen Zhang, Yuntao Du Rongbiao Xie, and Chongjun Wang. Adversarial separation network for cross-network node classification. In Proceedings of the 30th ACM international conference on information & knowledge management, pages 2618-2626, 2021.
[84] Yangze Zhou, Gitta Kutyniok, and Bruno Ribeiro. Ood link prediction generalization capabilities of message-passing passing gnns in larger test graphs. Advances in Neural Information Processing Systems, 35:20257-2000 -02722, 2022.
[85] Marinka Zitnik, Michelle M Li, Aydin Wells, Kimberly Glass, Deisy Morselli Gysi, Arjun Krishnan, T_M Murali, Predrag Radivojac, Sushmita Roy, Anais Baudot, et al. Current and future directions in network biology, 2024.
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes]
Justification: Our main contributions are summarized in five bullet points in Section and we point the readers corresponding sections to see justification (including theorems, methodologies and empirical results). Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification:
We discuss potential limitations of our presented work in Appendix N
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms
and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faireess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We provide all proofs and assumptions of our theorem results in Appendix
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
16

---

All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide all experimental details needed in Section Appendix and Appendix[] []]
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (c.g.. with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We will provide the code package during submission and make the code available upon acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not
17

---

reproducible, they including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
CodeSubmisssi wwwihabmmissiiooo ssioniiiccy for more details. httpsccccpbbccccccccc www.c/guiieeeeee /ttp:///uudde//eeeuuuiiiii
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why. At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: We provide all experimental details needed in Section Appendix | and Appendix [
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We include std in all of our main tables (see Section Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text. 8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification:
We specify the compute resources in Appendix
18

---

Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: We confirm that this work is conducted with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there special consid-
eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We provide related discussion in Section O
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal
impact or why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (c.g.. disinformation. generating fake profiles, surveillance), fairness considerations (e.g., deploymeett of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and funetioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA]
Justification: We confirm that this work does not pose safety risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring
19

---

that users adhere to usage guidelines or restrictions to access the model or implementing
safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors
should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We provide the related details in Appendix Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [No]
Justification: We did not introduce new assets in this paper.
Guidelines:
The answer NA means that the paper does release new assets. Researchers should communicate the details of the dataset/code/mooel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with
human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
20

---

15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLM is not important part of the core methods in this paper. Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non non-standard components.
Please refer to LLM policy pattps://neuriin wct//onfeeeennee/2255//////////e for what should or should not be described.
21

---

Appendix
The content of appendix organized as follows:
1. Algorithms:
Appendix A
talks about the details of LinearFGW [46 that we omit in the main text. We
summarize the overall procedure of LinearFGW in Algorithm [
Appendix B goes through the steps to compute Graph Dataset Distance (GDD). The entire procedure 18 included in Algorithm
Appendix summarizes the submodule GREAT used in our main algorithm (Algorithm)
Appendix summarizes our main algorithm GRADATE (Algorithm 4
2. Proofs:
Appendix provides the proofs for all the theorems in the main text.
Additional Experiments:
Appendix G. with additional
compares GRADATE with other data selection methods under graph size shift
GNN backbones.
Appendix G.2
compares GRADATE with other data selection methods under graph density
shift.
Appendix G.3 compares GRADATE with other data selection methods under graph size shift
with additiona GNN backbones.
Appendix G.4 compares the combination of GRADATE and vanilla GNNs with other GDA methods under graph size shift.
Appendix G.5 compares the combination of GDA methods and GRADATE against other data selection methods under graph size shift.
Appendix ablates the palidation-label-fees setting.
Appendix G.7 includes results on additional graph backbones.
Appendix G.8 includes results on additional GDA methods.
4. Discussions:
Appendix discusses FGW and Graph Dataset Distance (GDD) in relation to prior notions such as Tree-Mover Distance (TMD) [1] and Maximum Mean Discrepancy (MMD) [17
[ppeendxxNdissuussss potential limitations and future direction of our work.
5. Reproducibility:
Appendix provides the dataset statistics and licenses used this work. Appendix Intrrouuces the overall settings of GNN to use for the graph data selection evaluation, including the model we select and the training protocols.
H
Appendix D includes GDA method-specine parameter settings, where follow the default
settings the OpenGDA package [53]
6. Others:
Appendix K includes problem definition of Graph Domain Adaptation (GDA).
Appendix provides additional related work.
Appendix contains the empirical runtime of GRADATE.
Appendix
includes the ECDF plots of graph properties across datasets.
A Details of LinearFGW (Algorithm I
Formally, consider a set of N graphs D [9 where each (A,X) represents an attributed graph with adjacency matrix A E R and node feature matrix E Bux Note that is the number of nodes of G and d is the dimension of node features. LinearFGW first requires reference graph / = (A, X) where A E Raxa X E Baxd ń the number of nodes and d is the dimension of node features. Typically, 9 is obtained by solving an FGW barycenter problem, which aims find "center" graph that has the minimum sum of pairwise graph distances over the entire graph set D.
Following the notation used in Section 2.2 define the inter-graph distance matrix M ((G.,a)) between any pair of graphs (named as pairwise Fuclidean distance of node features. Namely, M C2) [||X ولللنلل addition, the intra-gras graaa similarity matrix is chosen to be defined as their corresponding adjacency matrices
XI, P1} and G2 (A2, X2, P2)) to be the
22

---

(i.e.. c - A, and C₁2 = A2). Together with uniform distribution Ps. Lng and pg:
6
1nz
over the nodes of Gi and G2 (with sizes n and n2), correspondingly, the FGW barycenter problen can be formulated as follows:
arg min
Σ (G.GM) Cg., Cg. Ps., Ps,..s..
(6)
where a E (0, 1] the pre-defined trade-off parameter.
After calculating the reference graph G, we then obtain N optimal transport plans (Te) the solutions by computing FGW(G, 9) for each 9 E D (via solving Equation [1 projection [46] of each graph's node edge with respect
Then, the barycentric
can be written as
T nude (TT; = 7 π X; Raxd
(7)
T odee (T,; = n. ग. C, E R
(8)
Finally, we can define the LinearFGW distance based on these barycentric projections. Namely, for any pair of graphs (9i, Gÿ), we define distance metric di dnnneurFGW (., over the graph set D:
dLnearFFWW (9i, Gj)
(1 11-a)l| ( (T:) T pode (T )1
+ a Te odge (T;; Tedge (Tr)) 1|p,
(9)
for i,j E [AV. Note that ||- represents the Frobenius norm.
Algorithm LinearFGW [46]
Input: N graphs D {G trade-off parameter a.
2: Initialize pairwise distance matrix D R
3: Solve the FGW barycenter problem in Equation (6) and obtain the reference graph ;;
4: for graph Gj in do
5: Compute FGW(G,, 9) via solving Equation and obtain π:;
6: Compute T mode (T:) and Todge (T,) via Equation (8)
7: end for
8: for Gs in D do
9: for Gj in D do
10: Compute D(i,j] dlincaFow Gj) via Equation
11: end for
12: end for
13: return LinearFGW pairwise distance matrix D.
B Summarization of GDD (Algorithm 2
"Since have prior the node importance in either graphs, the probability simplex will typically be set uniform.
'The optimization algorithm for solving this problem is omitted, Please refer to the original paper for more details.
23

---

Algorithm 2 (Training-Vare Validation) GDD Computation
1: Input: labeled training graphs Dirain = {g. y " Jim1 labeled validation graphs D
(gra) V/ m === trade-off parameter a, label signal strength e 0, a shared label set y
2: Compute pairwise I LinearFGW distance matrix D IR via Algorithm with the graph set
D= D=Diran Dral and parameter a;
3: Initialize new pairwise distance matrix D ==D D;
4: Initialize uniform empirical measures:
p
= = Eienn "gg!" y. q
m EjE(m) (oyy,o9")
5: for training label & in ) do
6: for validation label l, in y do
7:
Collect training index set with label l;
I. = {ilyy (z);
8:
Collect validation data set with label ex:
Ir = {il y = t.}:
9:
Compute graph-label distance in Equation (
d(l,, (x) = Op(,
train qe, dLincaFFo)):
10:
Update distance sub-matrix D(i J E I.,] = D(i E I,Jj It,l + d(l,,
11: end for
12:
end for
13: Compute ODDD Dval)= (p train q D) via the equation in Section 2.1
return GDD(Dimnn D OTDD (Dirin )
C Summarization of GREAT (Algorithm 3
Starting from uniform training weight w, GREAT alternates between two subroutines: (i) computes GDD between the two sets using pairwise distances D Raxm as the cost matrix (Line 4) and obtains the gradient gw V GDD(p (w), val D) for updating w (Line 5) and (ii) gradually sparsifies w by retaining only the top-k entries followed by normalization to ensure w is on the probability simplex (Line 6-9). After T iterations, we extract the non-zero entries from the resulting w and name this training index set as S.
Algorithm 3 GREAT
1: Input: pairwise LinearFGW distance matrix D E Raxm, selection ratio update step T, learning rate 7).
2: Initialize uniform training weights: In.
3: for = 1 to T
4: Compute GDD (w), q D) via Algorithm
5: Compute gw V w GDD(p (rain qrdd D) via Theorem F33
6:
Compute current sparsity level:
h = n max(r, T-I
7-+++1 r-1):
7:
Update data weight:
max(w 1) gw: O);
8: Sparsify data weight: w w o Top-k(w):
9: Apply & -noomallization w w/|lw/]
|||]]] |||l: 1
10: end for
return training data index S nonzero w).
D Summarization of GRADATE (Algorithm) 4
E Discussions on FGW & GDD and Previous Measures
Comparison between FGW 57 and TMD [T]. Specifically, FGW has the following advantages
Tree Mover Distance (TMD) Firstly, Linear optimal transport theory (59 46 can be

---

Algorithm 4 GRADATE
1: Input: labeled training graphs Dirii = [Grain 1a "/=
Ji=1 labeled validation graphs D " trade-off parameter a, label signal strength e 2 0, selection ratio т, update step
[gral, V. =i=1+
T. learning rate 1)-
2: Compute pairwise LinearFGW distance matrix D RR via Algorithm I
with the graph set
Dimin D and parameter o;
3: Compute the (label-informed) pairwise distance matrix D with label signal (line 3-12) in Algorithm
4: Compute GREAT(D, T.
7)) 5: return selected training data index set S.
utilized bring down the costs for pairwise FGW distance computation while TMD does not have similar technique. Secondly, a single-pair FGW computation (with time complexity ((D)))) is cheaper than single-pair TMD computation (with time complexity (CC])))) where V is graph size and C is the depth of TMD. While cheaper, FGW can achieve similar theoretical results as TMD.
Comparison between GDD and MMD AZ7V GDD offers a more flexible and expressive notion of graph dataset similarity than Max Mean Discrepency (MMD) [17], which solely compares aggregated graph embeddings. To be more specific, GDD has the following three advantages over MMD. Firstly, unlike MMD, which often depends on model-specific representations (such as pre-trained encoder) or require training, GDD does not involve training and is model- ffeee. This makes it broadly applicable across various graph-level datasets without the need for task-specific models. Secondly, GDD can optionally incorporate auxiliary label information (when available), enabling more fine-graines and task-relevant comparisons between data distributions classification settings. Finally, GDD is based on Wasserstein distance. Although not explicitly stated in our paper, this results in interpretable correspondences between data points across datasets that can directly be used for data selection or data re-weighting algorithms for domain adaptation applications.
F Proofs of Theorems
F.1 Proof of Theorem 3.1
In this section, we prove Theorem 3.1 We first focus on simplified case with k = 1, which implies that the underlying GNN has only one layer. Then, based on this result, we use induction generalize the conclusion to any positive k, which represents multi-layer GNNs.
F111 Assumptions
With a slight abuse of notation, let graph G denote its node set as well. We assume that f only uses one-hop information followed by a linear transformation. Specifically, for any graph = (A, () and any node as Ng(u) == {A ju, v), X[u]]vec. This localized aggregation is first computed by a convolution function g. and the result is then passed through linear transformation with weights W and bias b, giving:
G. the output f()), depends only on the local neighborhood of u, defined
f()), = W v(N((N) + b W w.g ((A(u, v), X (u]] + b.
(10)
We assume the convolution function is Cw-LLischitz w.r.t the following FGW distance dw for any nodes U1 Gi and U2 E Go.
dw:a (ws),No (u2))
(11)
1/r
= inf
E [(1 a: X1 X2 [ellll" + a|Ai[ur, 0nl Agluz, 02]l"]
REIll( (2) (2)
(12)
where we use #1 Uni and μ2 : Unif(G2) in this work.
25

---

F11.2
Proof for k =
Proof. H1 = Unif(G1), #22 == Unif(G2).
For any coupling x E (2), by Jensen's inequality w.r.. the concave function x + x//r,
E [IIf(G)), J: f(G2).,l1)
(13)
(u1,
[W. ((((A((u. +b] -W..WW(geeee g(((An[u2, vzl. x, v2c0.) +b]] (m1
(14)
E (w1,u2)ar
Ow | -Wll-ww:aa (1(A (X) {( 02). Hrles))
(15)
Cw
||
(w 1( inf (CTT(() (2
[11 - x X2[v2]1'+
(16)
alAi[uu: vi] - A2lu2, v21"") 1/7
( ( (11
E [1 x X2/e=]1l'' alA [u, A2lu2, w2]l")] "]
S. E
(17)
E [1 -1- x)llx m1 X2/eelll' + aa/Ailun vil -2luu, 1/r (11,02)~a (11,2))r
SC- E
(18)
where C = CwI[W]] We explain the inequalities as follows. The first inequality is from our smoothness assumption stated in the previous subsection. The second is by removing the infimum. The third is another use of Jensen's 's inequality.
Since the above inequality holds for any valid coupling n, we can take infimum on both side. Thus, follows that dw (Gi), f()))
is at most
inf =E) (M1222) [IIf()))ur
I
- f(92)
(19)
inf =EIl(a1m22)
C
E
E
(1- (x) X
(20)
(21 (11122)0T
Agluz, U2 12]l")]] 1/r
a|A1 (1,, 01]
=C inf
E
[11 a [ - X2|v=]1'+
(21)
=()) (ui.u2)<n (11,22)
a|A1 [11, 01] [on]-A2(usg A2(u2, U2 12]]""]] 1/r
(22)
=G in inf IE (xTl))))))))) (11
(UIN22)w [(1 [x) Xo|va]1l'+
E
(23)
a|Ai[un vil A2(u2, val")) 1/r
(24)
C FGW.(GI.G)) 92),
(25)
which completes the proof the case of k = 1. Note that the inequality is from our smoothness assumption stated in the previous section and the last equality is due to the definition of FGW distance with trade-off parameter 3 = a.
F.1.3
Proof for general A:
Proof. For general ls 1, we can iteratively apply similar logic as in the case of k 1 bound the output distance with multi-layer GNNs. Specifically, we can write a k-layer GNN f as composite function that concatenates multiple convolution layer (i.e. fi.... f with ReLU activation functions (i.e. d1, "-..," .k-1)): f = f& 0 fk-1 o... o 01 o f1, where oj = ReLU(-). For any
m S k. define hin == fm d o hm = fm o Nm-11 where N = dm-1 hm-1-
'We assume all these convolution functions (sm fismak satisfy the assumption we made in Section F.I.1 with constant Cw.
26

---

Note that we have f hg.
Then, for any coupling π E (1(1, we have:
E
(1)( - m22)
(26)
(11,02)
E
(11 - (2
(27)
E
[lI(fu - 1 - (fx 1
(28)
E
[l|C1 da 19 (1)) (921
(29)
(wi,w2)mar
=
Cj
E
[( inf
E
(1 - a) || (1)) - 1
(30)
(1l wz)
al /11, vil A2(u2, 02) [oa]""] 1/07
C1
(M1.Mg)~ (11112)0 (11-a) a)) |11//-1 (9 - (92-
(31)
A2/u22 02]1"]] 1/77
a[A1(us [11, vi
(32)
S <
(1 (1-a)
a)
(91)) -14 1n
(33)
(1) 12 Iua
1/r
A1 [11, enl - A2fu2, m2ll"]
(34)
(uy ( Jur (11,0g)
<G
(1 a)
E
h2 - 1n] (11)
(35)
(ts (2)
1/r
[ v1] A2(u2, we]l"]
(36)
(u1.42) mx
(2),0))~
Note that the first inequality is from the smoothness assumption, the second by removing infimum, the third is by Jensen's 's inequality and the fourth is because ReLU(-) a contraction function.
Here, we can iteratively apply the regularity assumption specified in Section F.1.1 to expand the term above: | (G1)e, (92)) I1", Vm E [k..... .13 to have the following deduction.
[1]f((r) - f(
(37)
(0))
< C1
C k-11 (1
a)* E
|| [11] X2[u>]117]
(38)
1-1
1/r
Σ
C1(1
a))
E
A A1 vil Ag(u2, Ael") v2]l"]]
(M1:42)~s (11
m=0
1/r
-c
(1-
E
[1
+ [2(12]11"]
E
[ 01] vall")
(V1.P2)~x
(ui,u2)
(39)
where C= Ci a+(1- -tC and B (1
1-C1(1-a)
27

---

Since the above equation holds for any coupling we can take infimum from both sides to get:
(40)
inf E (1)(()))
1(92)wall)
(41)
(E)())))))) (11,02)~~
C inf xeMl()))1))
(1 (1-33)
(3)
E
[1 X2 [1(++]|]]+
(42)
(2).0
1/r
B E
Ailuu, vil [alue,bel1"]]
(43)
(u1.02)mm (0)
= C FG.FFWs(9,,9)))
(44)
which completes the proof.
Remark F.I. To justify the smoothness assumption on g, we note that it an abstraction of GNN aggregation functions. For example, aggregation operations such as mean, max and sum all satisfy our assumption.
Remark F.2. Note that our technical assumption and the results of Theorem 3.1 are independent. Firstly, the assumption the convolution function g is about the smoothness property between node representations within a single graph; while the results of Theorem 3.1 is bounding the FGW distance between sets of node representations between two graphs.
F.2
Proof of Theorem 3.3
For any coupling π E [T(ptain(w) q ), by Jensen's inequality and the Lipschitzness assumption,
E (G.))~mm (w)
[C(f(S)
E
[C(f()).)))
201|
(45)
(G.1)~--"
[C(I() (raing)
E (g (ud) [C()()))), yr
(46)
(gnin y (w)
E 1 ((gra yrin)
[f ) ghine, )) [C(f(gra)) )((0)
(47)
E
(gtran)))))) ), - C((())))) ), y3 }]
(48)
((irain min)
E
[[ ), C(f(g)a)) ).y"
(49)
((iin pii M
P0
E ((gluis ) (g
[C d m, (g (y")a [(
(50)
y
E = =C ((Gmm gam), (SOu)
[d ((grrin " (g y )]]
(51)
Since this holds for any coupling m(p )
then we have
E (G.))~tthh inf Tell(pri(w)) (w).q ((guni, guiss (0 yU)) (d ((graan, . main) (gta), -yy"
[C(f())))]
E [C(f()). x)]
(52)
(G.))~ga)
S.
E
(53)
C. OT (w) q val dgz))
(54)
C- CDDDDDDD )
(55)
It follows that
E (G.))~q'u
(C(())
<
E (G.))~p'ms(w)) 1
[C(()),)] + C. GDDD(Diin DVal).
(56)
which completes the proof. Note that the first inequality follows from Jensen's 's inequality (w.r.t the absolute function). The second and third inequalities are both due to the smoothness assumption stated in Theorem 3.3
28

---

F.3 Proof of Theorem F.3
Theorem F.3 (Gradient of GDD w.r.t. Training Weights: Given a distance matrix D, a validation empirical measure qtd and training empirical measure pirain (w) based the weight w. Let 3 x be the dual variables with respect to p piraing (w) for the GDD problem defined in Equation 5). The gradient of GDD muin (w), qual D) with respect to can be computed as:
V GDD(D uain (ww) q = (TT"
(w),
=
where 3r (T*) ) is the optimal solution w.r.l. p"rin(() to the dual of the GDD problem.
Proof. Omitted. Please see the Sensitivity Theorem stated by Bertsekas
G Additional Experiments
G.1
Comparing data selection methods for graph size shift GCN & GIN
We conduct the same evaluation as Table on graph size shift with GCN and GIN as backbone model in Table 4
GNN Architecture +
GCN
GIN
Dataset
Selection Method
T= 10%6
r = 20%
= 50%
Full
7 10%%
20%
T: 50%
Full
Random KIDD-LR
0.612= 0.573
0.645
0.620s
0.582 woee
0 0.605
AIB-BBIARY
LAVA
0,5921
0.82
0.560
0.823
0.652:
0.837
0.630
0.553
0.822
0.830
0.555
GrADATE
0.8
0
0.830 tuen
0.823: 2002
0.820 Rooe
0.832 0.0
Random KIDD-LR
074
0.554g
D. 166: orea
0.351 3.08
0.372 oone
0 n819
IMDR-MULTI
LAVA
0.3141000
0.320
0.4161
0,426
0.432 onn
0,600
0
0.346 304
0.388
0.371 0015
0.563
0.4121n088
0.368
GRADATE
0.524
Random
0.50
0.19
0 unns
2,07
0.418= woke
0.690: um1
MSRC_21
KIDD-LR
LAVA
0.6
0.725 0017
0.819 0005
0.825 9304
0 noes
0.918= onss
0.816
0.649: 2012
0.617s
0,743 noee
0.810 to04
0.781 0250
0,859 0011
0.749
GRADATE
06702
0.629 3011
11M13 mi8e
0 0.90
Random
0.476
0.471
oghg-moll bace
KIDI&LR
LAVA
0.4610000
0.563 ose
0.574 8567
0.535 0064
0.4442003
0,547
0.645 2.35
0.523 nnce
0.641 2007
0.648 na25
0.571.nn0t
0.548
GRADATE
0.599 0
0,575 ores
0.646: 2855
0.61 toe
0.630
Random
0.635; so1
D. 0.648 om
0 3610
0.633 n00
0.001..n0m
KIDD-LR
0,339
0.599)
0.546
0.656
ogbg zolbbbp
LAVA
0.6
0.675
0.691
0.618
nous
13394-0011
0.779
GRADATE
0.677
0.673: 0.671 on)
0.866 3018
0.890 mm
0.1951
Random
0.5762
9.5
0,594 one
0.613 2.04
0.617 uoes
0014
ogog-rolbiv
KIDD-LRR JR LAYA
0 0.551: 0.556g2
2.6
0.683
D 0.595 ome
0.659
0.592auue
0.586 8.55
0,769
0.737
0.586 no1
629% nare
7964
0.664
GRADATE
0.629
0
Table 4: Performance comparison across data selection methods for graph size shift on GCN and GIN. We use bold/underline to indicate the 1st/2nd best results. GRADATE achieves top-2 performance across all datasets and is the best-performer in most settings.
G.2 Comparing data selection methods for graph density shift on GAT & GraphSAGE
We conduct the same evaluation Table I on graph density shift with GAT and GraphSAGE. as backbone model in Table
G.3
Comparing data selection methods for graph size shift on GAT & GraphSAGE
We conduct the same evaluation as Table on graph size shift with GAT and GraphSAGE as backbone model in T
G.4 Comparing GDA and vanilla methods for graph size shift
We conduct the same evaluation as Table on graph size shift in Table 7
29

---

GNN Architecture +
GAT
GraphSAGE
Selection Method
10%
207
50%
Pull
F 10%%
20%
50%
Poll
Random KIDD-LR
0,002.00
0.695
a
0.730),
0.637
0 0.7622
0.803
0.817
0.662s
0.785=
IMDB-BINARY
LAVA
08182000
0.857
0.885 onn
0.507 20003
0.877 3005
0.840 mo0a
0.823,aa
GRADATE
0250
0.865 s0e4
I.N92 0013
0.835 2015
0,852 poes
0.907 nar
Random
0 000
0.076
ouea
0,090s 2035
0,203 uoe
0. 126 0234
IMDB-MULTI
KIDD LR
LAVA
0.121 0
0.597
0.59
0,158
0.000
0.154s
0,341:3541 2047
0,307
0.124
0.054
0.097
GRADATE
0.790
6358
0.776
0.306
0.209 0:30
Randoas KIDD-LR
0.7681,000
0.857 nons
0.617
0.728
6003
0 0.842 nate
MSRC
LAVA
0.09
0666
0.7782
0.8162907
0.860 wee
0,912
0.360
0,766 9:20
0.681 2.15
0.787 WgD
0.857
0 0.984
0.857 119
0
GRADATE
0,71610017
0.822:
0.921
0.781
0.877
0.944:
Randoms
0,4801 0.10
0.6061
8:65
a tuns
0 3:34
0.478 1000
0354
ogbg-xelbace
KIDD-LK LR
LAVA
+
0.564
0,6431
0.519
0.628 Doa
0,69 0v0)
0.583 BUN2
0.620= 2.13
0.606= 2023
0.649 UAA
0.596 Nmm
0 0.607 0347
0.651 0139
0.622
GRADATE
0:541g
0.720
0.621 3.67
0.587 oii
0. 565681 015
Random
0.51
3:513 8.529
0.385
4
agig-moo bhhp
KIDD-LR
LAVA
0.584g
0.105 0,44
0.552
0:434 ove>
D 60 one)
0.56P
0.392s 2822
0.526 2007
0.115=
0.612 mi0
0.1664
0.495
0.447.036
GRADATE
0.617 0.06
0.578 0201
0.632 Do0e
0.580 3567
0.558
0004
0.528 0,27
Random
0.001 6017
0,5911 9801
0 a onns
0.577 3.16
0.591 o00
0 0.594] n.0
egig bogg-xllbiv
KIDD-LK LR
LAVA
0.620s
0.6161
0.631
0.624:
0.615
0.57
0.575
0.607
0.607
0.534
603
0.588
GRAADATR
0.638
0.621 610 0.619 one
0.599 3631
0.508 0188
0.610 naw
Table 5: Performance comparison across data selection methods for graph density shift on GAT and GraphSAGE. We use bold/underling to indicate the 1st/2nd best results. GRADATE is the best- performer in most settings.
GNN Architecture +
GAT
GraphSAGE
Dataset
Selection Method
= 1055
r = 20%
= 50%
Full
7 10%%
20%
T 50%
Fell
Random
0.558k 06678
O. 6166 ores
0.555 2011
0,563 o0zz
0 0.122-0012
IMDB-BINARY
KIDD-LR
LAVA
0.5872 0683gm
0.00
0.830).000
0.665
onee
0.505
0.66313605
0 3636
0.558:
0.808
0.800 now
0055
0.567
GRADATE
0.835
0.837 UNIE
0,808: 2016
0.828 1004
0.8
Random
0.408: 0.34
0,384s 10D4
0.336 2010
0.357 wse
0.38
IMDB MULTI
KIDD-LR
LAVA
0.333
3.66 onto
0.417a
0.434 0005
0.404 one
0,572
0.339) 3.50
0.324
0.389
0.418 onee
0.422
0.392
1011
GRAD
0.537
0,392: 3392
0,360
0.517
Random
0.6142 0.2
9109
0.731 unn
0.412 wee
0. 0.725 4zzz
MSRC_21
KIDD-LRR IR
LAVA
0.746 0626:000
0.620 0013
0.798 9352
D 909 DUIS
0.89 o0))
0.787
a.722 3600
0,893 2.29
0.79% onne
0.827 un
0.918 0pe
7899 nih
0.810
GRADATE
0.6
0,947
0,760 2035
0.842
0.944:
Random
0,464
D.488
0.523
0.583100077
oghg-mol bace
KIDI-LR
LAVA
0.524 0x37
04801
0,452:8004
0.545 c 0201
0.613 Does
D.467 0003
0.46
0.650 2011
0
0.457: nice
0,481 8000
0.550) 0.000
0.467
0.487
GRADATE
0,570 6.52
0. 5.509 tiee
0.556 3541
0,561
0.564 1995
Random
0.66
0.677=
0. 1.68
0.634 pous
0.618 wucs
0.611
oghg zobbbbp
KIDD-LR
LAVA
0.7
0,731
0.5062:000
0.650
0.210 suee
0.679
0,518s
0.639 2022
tuee
0.615 0r20
0,680=aa
GrADXTE
0.735 oz21
0.699 9307
0.713 Doee
0.023: 2041
0.650 no1
0.682: 0341
Random
0 0.5K5 005
D. 589 orea
0.610g 3:04
0.491 = nmn
O 06602 nan
eglg-xolbivv
KIDD-LR
LAYA
0,704
(1 0.584 8601
0.773
0.1844 0001
2008
0.721
0.549 36h1
0.588 orea
0,701
O 1.5641 nall
0.686
0.5962500
GRADATE
0.663
0.655=
0.860:
0.637 2002
0.610
Table 6: Performance comparison across data selection methods for graph size shift on GAT and GraphSAGE. We use bold/underline to indicate the 1st/2nd best results. GRADATE achieves top-2 performance across most settings. The under-performancee on ogbg-mo moliv might due to the reason discussed in Section 4.
G.5 Enhancing GDA methods for graph size shift
We conduct the same evaluation as Table 3 on graph size shift in Table
g
G.6 Validation-labell-ree setting
While we originally consider tunable parameter, we acknowledge that the existence of validation labels will be implicitly required when e & O, which might not practical under some real-world scenarios. Here, pick two GNN backbones (i.e. GCN [30] and GIN (65)) evaluate the effectiveness
30

---

Dataet
Type
Model
Data
IMDB- IMDB-BINARY BINARY
IMDB-MULLE
MSRC_21 21
ogbg-aolbace
ogbg-nou bbbbbbolbbbpp
ogbg-nolbiv
0.59
no17
0.625
wat
GDA
GRADE
ASN
Fall
Pall
0.6331
0.648:-0355
0.390s o0t
0,372L uow
0.734 o00
0.696: euee
0:5231 c191
0.403 cumn
0.6161490
0.669x-0.00
0.519 0077
0.599 was
UDAGCN
Fall
0.688.1044
0,392:
0.260
0.448:
0.513a
0.439
Random 20%
0.61222008
0,354 0006
0.497
0,504 0002
0.635
0.579=000 0004
GCN
LAVA 20%
0.8232.004
0.426 nom
0.825 0014
0.574 o0e7
0.675g.000
0.683; 088
GRADATE 20%
0.8
0,524:
0.836
0.599
0.67
0.638
0.372 suee
a.633
GIN
LAVA 20%
0.8302 0:0
0.388 nots
0.8 0.810 9004
0.641 DueT
0.889
0.737= 0012
GRADAYH 20%6
O 9
0.497, nons
03813 bork
0.6181 5/6)
0.890 1.0
0.767 n93
Vanilla
Random
0,408,
0.614
0.4044
0.677...000
GAT
nuts
cues
0.731
wa7
GRADATE 20%
0.833
0,537: 0008
0.860 6/21
0,5 7070 G002
0.699 0.00
0.655: 0,09
Random 20%
0. 0882
0.357 come
0.412s
0.463+ CVED
0.648
0.491 0081
GrahSAAE
GRADATE 20
0.828 0.804
0.360: tuis
0.842 B
0.561 D00e
0.650 0.009
0.646 6019
Table 7: Performance comparison across GDA and vanilla methods for graph size shift. We use bold/underline to indicate the 1st/2nd best results. GRADATE can consistently achieve top-2 perfor- mance across all datasets and is the best performer in most settings.
of GRADATE with e 0 (i.e. validation-label-Fees The result is shown in Table For simplicity, we only report relative performance improvement (%) of GRADATE over the strongest baseline under all settings. We can observe that the advantage of GRADATE remains comparable to what is reported in the main text.
G.7 Additional backbones
In addition to typical GNN backbones, we also conduct experiments on wider range of graph algorithms, including SGFormer [60] and APPNP [66. In Table[[0] we report relative performance improvement (%) of GRADATE over the strongest baseline under all settings. We can observe that GRADATE still outperforms other baselines mostly.
G.8 Additional GDA methods
We add additional experiments based on two variants of A2GNN 34 with different losses and TDSS 77. In Table [T] we report relative performance improvement (%) of GRADATE over the strongest baseline under all settings. For simplicity, 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.
H Datasets
In Table 12 we provide details of datasets used in this work. For # NODES and EDGES, we report the mean sizes across all graphs the dataset.
I Backbone GNN Settings for Graph Selection Evaluation
GNN Models. We consider four widely used graph neural network architecture, GCN 30 GIN 665) GAT [58) and GraphSAGE [T]. The detailed model architectures are described as follows: For GCN, we use three GCN layers with number of hidden dimensions equal to 32. ReLU is used between layers and a global mean pooling layer is set as the readout layer to generate graph-level embedding.
A dropout layer with probability
0.5 is applied after the GCN layers. Finally, linear layer with softmax placed at the end for graph class prediction. (ii) For GIN, we use three-layer GIN with 32 hidden dimensions. We use ReL.U between layers and global mean pooling for readout. A dropout layer with probability 0.5 is placed after GIN layers and finally linear layer with softmax for prediction. (ii) For GAT, use two-layer GAT layers with four heads with global mean pooling
31

---

GDA Method -+
AdaGCN
GRADE
Selcetion Method
7 10%
2015
5076
Full
10%5
200%
5056
Full
Random
0.582, coe:
0,520,
0,455
0.5721
0.522
0.613
BIDB-BINARY
LAVA
0.818 0002
0.815
0.810
0.593 0002
0.8134
0.814
0.816
0.648 0.35
GRADATE
0834
0.826
0.827
Random
0.261
0.247 was
0.252 9109
0
0.280 o0e0
0.282+0029
IMDB-MULTI
LAVA
0.374: 6065
187 0030
D. 1.36% 9164
0.362 0003
n 3800 0307
0.402
0.411 4:000
0.3001
GRADATE
0.386
0.442:
6.50
0
0,411
0.503
Random
eods
0.079
0.1
0,667
MSRC_21
LAVA
0.377%
0.472 0.30
0.580
0.202 E0T3
0 0.532-0022
0.728 0A06
0.854 0.235
0.696
GRADATE
0.411: eans
0.465 0988
0.593 son
0
0.744 0004
0.867: 9:315
Random
0.4982 arw 0.510- 600
0477
0,49KK
0.474
0.468
0.475
oplog-rol bade
LAVA
0.523
0.529
0.513
0.5024.00005
0.589
0.552.0031
0.4031
GRADATE
0.524: 6307
0.560
0.39
0.556
0.512
Random
0.539 exes
0.600 0.44
0.538
0083
0.632
0.648: DA02
0.650:0.30
ogig-arolbhig bhhp
LAVA
0.583: euns
D.633 0000
0.6577 0001
0.625 0.33
0.631
0.640) 6000
0.669 60e5
GRADATE
IL662; 6000
0.654 0:9
(.664 900
0.6361 0:30
0.641
0005
0.6901033
Random
0.356
0,35%
0. 1.36418800
033
0.615
0,502..030
ogig zolbiv
LAVA
0.382 0009
0.403
0.38/
0.412 0002
0.633
0,681
0.668:00.9
0.599t
GRADATE
0.393: 6143
0,287 MAMe
0.395
0.6 DARD
0.612
GDA Method
UDAGCN
Datavet
Selection Method
1|
== 10%
2055
r 50%
Full
== 10%
20%
50%
Full
Random
0.615 e.33
0.568 noms
0.515 0004
0.507 0:77
0.467 a Dx04
0,008 0.30
HIDB-BINARY
LAVA
0.812 ema
08810 0012
0,847 9807
0,633 0054
0.817 0312
0.811 Dxes
0.837 0.11
0.688
GRADATE
0,255
0.819
0.834
0.840:
0,831
0.8161
Random
0.156
0.340
0.
IMDB-MULTI
LAVA
(.379
0.445 0087
0.8V3 9164
0.372 0009
0.34822-351
0.387 0063
0.519
0.392:
GRADATE
0.425: ems
0.455 009
0.577 9166
0. 1
0.444 0184
0.451 9
Random
0,481 eom 0,561=
0.277 oate
0,556 8812
0.15 0372
0.204 ooed
0,209:00000
MSRC_21
LAVA
0.779
0
0,734
0.435+
0.498
0.563
0 0.260=:399)
GRADATE
(.666
Random
0.465
0,440 n3w
0,4661 616d
0.485
0.503
0.5442:0311
agig-arol baze
bare
LAVA
0,496 exn
0.560s 0018
0.5%6 8003
0,523 D00
0.499 no
0.553
0.5174
0.448
GRADATE
0,568 eans
0.596 0233
0.5466 9323
0.521 0.3
0,519 exe2
0.555 0.24
Random
0.537s eoe:
0,530s
0.5
0 0.54
0,568
0.536
ogbg zolbbbp
LAVA
0.606 6004
0.635=
0.646
0.6166 00M2
0.655
0.619
0.67--0211
0.513s
GRADATE
(U621 Boos
0,640
(U650)
0.660
0.674:
0.677
Random
0.385 om
4.4%) now
0. 0.597 0.03
0.446
0.412 oee
0.4092
egog-xelbiiy
LAVA
0.449 ends
0,465 0.065
0 (1599) 9.04
0.519% OXTT
0.436 0321
0.431
0.433 0:17
0.439) aSs
GRADATE
0:435e 6044
0. 123
0,474
0,434
0 0335
Table 8: Performance comparison across combinations of GDA methods and data selection methods for graph size shift. We use bold/underline to indicate the 1st/2nd best results. GRADATE achieves the best performance in most settings.
GCN
GCN (r=20%)
GCN (r=50%)
GIN
GIN
GIN
Dataset
(r=10%)
(r=10%)
(r=20%)
(r=50%)
IMDB-BINARY
+11.13
+9.92
+2.76
+4.63
+5.16
+13.37
IMDB MULTI
+221.31
+201.09
+189.61
+45.78
+95.01
+87.04
MSRC 21
+1.99
+1.36
+3.01
+2.36
+0.09
+2.88
ogbg molbace
+1.32
-4.39
+13.17
-16.32
+2.84
+7.48
Sggg-molbbbp
+0.00
-14.46
+0.00
-0.08
+2.18
+2.22
ogbg-molhiv
+3.05
+0.75
+0.48
-1.24
+0.35
+2.52
Table 9: Relative improvement (%) of GRADATE over the strongest baseline under different settings.
for readout. A dropout layer with probability 0.5 is placed after GIN layers and finally a linear layer with softmax for prediction. (iv) For GraphSAGE, we two GraphSAGE layers with mean aggregation operation. The hidden dimension is set to 32. A dropout layer with probability p = 0.5 is applied after the GCN layers. Finally, linear layer with softmax is placed at the end for graph class prediction.
Experiment Details. We perform all our methods in Python and GNN models are built-in modules
of PyTorch Geometric [1]. The learning rate is set to 10-2 with weight decay 5 10-1. We
32

---

SGFormer (7=10%)
SGFormer (r=20%)
SGFormer (7=50%)
APPNP (T=10%)
APPNP (T=20%)
APPNP
Dataset
(T=50%)
IMDB-BINARY
+9.82
+0.59
-0.34
+7.28
+3.01
-0.35
IMDB-MULTI
+6.46
+57.40
+1.65
-13.46
-2.59
+13.71
MSRC_2 21
+14.26
+3.58
+2.13
+9.54
+3.18
+1.27
ogbg-molbace
99.66
+0.05
+1.90
+4.03
-2.31
+2.84
ogbg-molbbbp
42.93
+5.47
-3.71
+22.80
+6.33
-4.58
ogbg-molhiv moohiv
+1.51
-1.79
+1.65
-12.00
+6.07
+1.88
Table 10: Relative improvement (%) of GRADATE over the strongest baseline under different settings.
A2GNN-ADV
A2GNN-MMD (T=20%)
TDSS
Dataset
(T=20%)
(7=20%)
+31.12
+11.40
+3.12
IMDB-MULTI
+26.54
+58.88
-42.10
MSRC_21
+20.63
-4.40
+25.09
ogbg-molbace
+1,46
-2.57
+2.88
ogbg-molbbbp
+17.34
+5.85
-5.71
egbg-molhiee +0.65
+0.81
+0.55
Table 11: Relative improvement (%) of GRADATE over three additionally added GDA methods under different datasets.
train 200 epochs for datasets -BBNAY,,, IMDB-MULTI, MSRC 21 and 100 epochs for datasets ugbg-molbace
ogbg-molinn molhiv with early stopping, evaluating the test set on the model checkpoint that achieves the highest validation performance during training. For each combination of data and model, we report the mean and standard deviation of classification performance over 3-5 random trials. For TUDatasets, we use accuracy the performance metric; for OGB datasets, we use AUCROC as the performance metric. The computation is performed on Linux with NVIDIA Tesla V100-SXMM-3220 GPU. For graphs without node features, we also follow Zeng et that generates Segree-specific one-hot features each node in the graphs.
J GDA Method-Specific Settings
We train 200 epochs for datasets BIDB-B, IMDB-MULTE MSRC_21 and 100 epochs for datasets ogbg-molbace, ogbg-molbbbp, ogbg-molhiv with early stopping, evaluating the test set on the model checkpoint that achieves the highest validation performance during training.
We follow the default parameter settings in the code repository of OpenGIDA 53
We set the learning rate to 10-3 with regularization coefficient equal to 10-4 Dropout rate is 0.3 and A Agp 5.
AdaGCN 12]:
We set the leamning rate 10-3 with regularization coefficient equal 10-1, The dropout rate is 0.5. The difference loss coefficient, domain loss coefficient and the reconstruction 10-6 0.1, 0.5.
ASN
33
loss coefficient is
GRADE [61]: We set the learning rate to 10 with regularization coefficient equal to 10-4
Dropout is
0.1.
UDAGCN [62]: We set the learning rate to 10-3 with regularization coefficient equal to 10-4
The domain loss weight equals 1.
K Additional Preliminary: Graph Domain Adaptation (GDA)
Consider a source domain D. (9) " and target domain D, (g) " where each = (A, X) represents attributed graph with the adjacency matrix A p and the node feature
matrix X paxd, where n is the number of nodes and is the dimension of node features. With
33

---

DATASET
# GRAPHS
NODES
EDGES
#FEATURES
CLASS
DATA SOURCE
LICENSE
HIDB-BINARY
1000
19.77
96.53
None
PyG
MIT License
IMDB-MULTI
1500
12.74
53.88
None
PyG
MIT License
MSRC_2
563
77.52
198.32
None
20
PyG
MIT License
ogbgemolbace
1513
34,08
36.85
9
2
OGB
21
MIT License
ogbg-molbbiy
20.39
24.06
25.95
9
2
OGB
MIT License
ogbg-molhiv 41127
25.51
27.46
9
OGB
MIT License
Table 12: Dataset Statistics and Licenses.
shared label set V, the graphs in the source domain are labeled with yē V. The two domains are drawn from shifted joint distributions of graph and label space, i.e., P.(9,)) + Pi y). The goal of GDA is to learn a classifier f y with the source domain data that minimizes the expected risk on the target domain: B( ((C y)], where C is task-specific loss function.
Additional Related Work
In the era of big data and Al 40
48
67 33
efficient data utilization has
become paramount for scalable machine learning. Beyond the data selection and domain adaptation methods discussed in the main text, our work also connects to several related research directions that graph learning and distribution matching. Specifically, there
provide complementary perspectives a rich body of work the intersection of optimal transport theory and graph data [24 77 80 82).
which are closely related to main methodology.
M Empirical Runtime of GRADATE
In Table 1 and Table 14] we provide the empirical runtime datasets (IMDB-BINARY, IMDB-
MULTI and MSRC 21) and datasets bogbg-molbacee ogbg-molbbbp and molhivv, respec- tively. We observe that the on-line runtime is insignificant compared to typical GNN training time. And the off-line computation is only run once, which can be pre-computed. Furthermore, we can achieve much better accuracy compared to LAVA with nearly no additional runtime.
Procedure Dataset
BIBB-BINARY
IMDB-MULTI
MSRC 21
Off-line Computation
FGW Pairwise distance Label-informed pairwise distance
7.41
9,61
18.18
(GDD Computation)
0.04
0.06
0.24
GREAT (Algorithm
0.28
0.52
0.11
On-line Computation
LAVA
0.09
0.14
0.03
GCN (w/ 10% data)
13.45
16.36
9,59
GNN Training Time
GCN (w/ 20% data)
17.64
21.40
13.85
GCN (w/ 50% data)
29.92
45.82
19.57
Table 13: Empirical run-time behavior for TUDatasets (in seconds). We can observe that the off-line procedures can be run comparable to a single GNN training time and the on-line procedure has a negligible runtime compared to GNN training. In addition, we can achieve significantly better performance compared to LAVA with slight additional on-line runtime.
N Limitations and Outlook
1. How to eliminate the dependence on validation data? Although it is common in machine learning research assume we have some validation that represents the data distribution on the target set (or "statistically closer" to the target set), it might not be always available under certain extreme scenarios. Thus, our interesting future direction to extend our framework to no-validation-dal -ata or test-time adaptation settings.
2. Can our proposed method scule to extremely large settings? When we have millions of large graphs in both training and validation set, the efficiency of GRADATE might be concern. However, most of the computationally intensive sub-procedure of our method can be done off-line (see complexity analysis in Section 3.2 and empirical runtime in Appendix M) and
34

---

Procedure Dataset
ogbg-molbace
ogbg-molbbbp
ogbg-molhin
Off-line Computation
FGW Pairwise distance
15.44
19.67
283,99
(GDD Computation)
Label-informed pairwise distance
0.12
0.17
53.82
GREAT (Algorithm
3
0.43
0.84
295.42
On-lins line Computation
LAVA
0.13
39.45
GCN (w/ 10% data)
12.76
13.91
190,34
GNN Training Time
GCN (w/ 20% data)
13.08
22.59
312.08
GCN (w/ 50% data)
22.21
30.48
845.46
Table 14: Empirical run-time behavior for OGB datasets (in seconds). We can observe that the off-line procedures can be run comparable to a single GNN training time and the on-line procedure has negligible runtime compared to GNN training. In addition, we can achieve significantly better performance compared to LAVA with slight additional on-line runtime.
the online runtime is ignorable compared typical GNN training on full dataset. One possible mitigation is to do data clustering using FGW distance before running our main algorithm GRADATE to avoid computational overhead.
3. How to select the optimal amount of data? We demonstrate that in Section 4.5 the relation- ship between selection ratio and GNN adaptation performance is not always trivial across different settings. To ease the comparison pipeline, we fix to some target selection ratios (i.e. 10%, 20%, 50%) for our main experiments, but we acknowledge that these ratios might not yield the best adaptation performance or serve as the best indicator to comparison across different methods. Thus, one potential extension of our method is to automate the process of selecting the optimal selection ratios when dealing different levels of domain shifts.
4. How to extend GRADATE to node-level graph domain adaption setting? One possible extension solve node-level tasks is follows: decomposing source/target graphs into set of ego-grraph graphs where each these ego-graphs represent the local topology of each node, and applying GRADATE directly select the optimal nodes for adaptation. Future directions that require more investigation include (i) how to decide the size of local vicinity for each ego-graph, (ii) how co-consider node/edge selection for optimal adaptation and (iii) how to mitigate the information loss when extracting ego-graphs.
Impact Statement
This paper discusses the advancement of the field of Graph Machine Learning. While there are potential societal consequence of our work, none of which feel must be hightlighted.
35

---

P ECDF Plots of Different Covariate Shift Settings
1.0
144
0.2
0.2
Tark
Text
(a) BMDB-BINARY (Density)
(b) IMDB-BINARY (Size)
ECSE baniyy 96.0 (Aacending
ECSF Graph Abr MEB (Accanding
0.4
Vandeteen
0.0
02-
IMDB-MULTI (Density)
(d) IMDB- (Size)
EC2P Srigh Danily PBPC (Aucendeg))
ICCP (Gigg Siee MDRC 21 (Aocondin))
2.2
0.0
0.5
624
3.56
3.50
2022
105
(c) MSRC_21 (Density)
(f) MSRC_21 (Size)
Figure 1: ECDF plots of graph density and size for IMDB-BINARY, IMDB-MULTI, and MSRC 21 datasets. The Blue, Orange, and Green curves represent the distributions of the training, validation, and test splits, respectively, Graphs are sorted in the ascending order by the specified shift (density or size).
36

---

ECoF Greph banily (Aacending)
E:01 ash igtemdtam (acerdin)
0.4
0.2
Vilostion
Valaatce
0.9
02
(a) ogbg-
ogbg-molbase molbace (Density)
(b) rgbg-molbace (Size)
2007 of Graph Ceralty 2g2g mobbop Mapanding)
ICCT of craph 5ks ogbg mobbbl (Aicending)
0.5
0.5
(c) ogbg-moot mo bbbb (Density)
(d) ogbg-molbbbp molbbbp (Size)
Benity
3.09
1.5
0.4
Validation
Valdalden
Tark
Taxt
(e) ogbg-molhiv (Density)
(f) ogbg-molhiv (Size)
Figure ECDF plots of graph density and size for ogbg-molbbbp, ogbg-molbace, and ogbg-molhiv datasets. The Blue, Orange, and Green curves represent the distributions of the training, validation, and test splits, respectively. Graphs are sorted ascending order by the specified shift (density size).
37


Reviews:
[{"review_id": "frDJtm0ToC", "reviewer": "Reviewer_pN6d", "summary": "The paper proposes GRADATE, a novel model-free framework for graph domain adaptation that selects useful training data using optimal transport theory. It offers theoretical guarantees for its distance metric, introduces an effective optimization algorithm, and demonstrates strong data efficiency. Extensive experiments on multiple real-world datasets show that GRADATE outperforms existing selection methods and can enhance standard GDA models with less data.", "questions": "none.", "limitations": "yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. GRADATE is explicitly model-agnostic, avoiding reliance on any specific GNN architecture.\n\n2. The paper gives a clear theoretical justification for using Fused Gromov-Wasserstein distance. It also provides an explicit bound on the domain generalization gap via the proposed Graph Dataset Distance.\n\n3. GRADATE shows it can achieve strong performance with significantly less training data.\n\n4. The paper includes experiments on six real-world graph-level datasets under multiple types of covariate shift, outperforming state-of-the-art GDA baselines.\n\n\n\nWeaknesses:\n\n1. The literature review is somewhat incomplete. The paper does not sufficiently cover some recent graph domain adaptation works.\n\n2. 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.\n\n3. The approach relies on labeled target-domain validation data, which is often unavailable in realistic test-time adaptation scenarios.\n\n4. Despite approximations, the method’s time complexity remains high and could limit scalability.", "was_revised": true, "final_justification": "The authors have addressed my concern by providing additional experimental results. I am therefore setting my final score to 4, leading to acceptance.", "rebuttal": "Thank you for recognizing our work! For the weakness you mentioned, we address each as follows.\n\n    \n> **(W1) The literature review is somewhat incomplete. The paper does not sufficiently cover some recent graph domain adaptation works.**\n\n\nThank 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. \n\n> **(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.**\n\nThis 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. \n\nThis 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.\n\n> **(W3) The approach relies on labeled target-domain validation data, which is often unavailable in realistic test-time adaptation scenarios.**\n\nWe would like to clarify that:\n- **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.\n\n- **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,\n    - 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*)\n    - 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.\n\n- **Table 1 (GRADATE outperforms other data selection methods)**\n\n| Dataset   | GCN (10%)  | GCN (20%) | GCN (50%) | GIN (10%) | GIN (20%) | GIN (50%) | \n|:-----------:|:-----------:|:-----------:|:-----------:|:-----------:|:-----------:|:-----------:|\n| IMDB-BINARY | +11.13%  | +9.92%    |  +2.76%   | +4.63%     |  +5.16%   | +13.37%     |\n| IMDB-MULTI | +221.31%   | +201.09%    |  +189.61%   | +45.78%    |  +95.01%   | +87.04%     |\n|  MSRC_21  | +1.99%  | +1.36%     |  +3.01%   | +2.36%     |  +0.09%   | +2.88%     |\n|  ogbg-molbace  | +1.32%  | -4.39%    |  +13.17%   | -16.32%     |  +2.84%   | +7.48%     |\n|  ogbg-molbbbp  | +0.00%  | -14.46%     |  +0.00%   | -0.08%    |  +2.18%  | +2.22%     |\n|  ogbg-molhiv  | +3.05%  | +0.75%     |  +0.48%   | -1.24%     |+0.35%   | +2.52%     |\n\n- **Table 2 (GRADATE outperforms GDA baselines and other selection methods)**\n\n| Dataset   | Best GDA| A2GNN-ADV| A2GNN-MMD | TDSS | Best Random| Best LAVA | GRADATE\n|:-----------:|:-----------:|:-----------:|:-----------:|:-----------:|:-----------:|:-----------:|:-----------:|\n| IMDB-BINARY| 0.822 | 0.831 | *0.845* | 0.753 | 0.738 | 0.835 | **0.858**\n| IMDB-MULTI| 0.123 | 0.099 | 0.142 | 0.136 | 0.180 | *0.790* | **0.800**\n| MSRC_21| 0.833 | 0.824 | 0.818 | 0.833 | 0.801 | *0.851* | **0.865**\n| ogbg-molbace | **0.683** | 0.602 | 0.590 | 0.641 | 0.622 | 0.637 | *0.651*\n| ogbg-molbbbp | **0.778** | 0.528 | 0.564 | 0.560 | 0.528 | 0.642 | *0.656*\n| ogbg-molhiv | 0.567 | 0.622 | 0.620 | 0.466 | 0.602 | *0.633* | **0.637**\n\n\n> **(W4) Despite approximations, the method’s time complexity remains high and could limit scalability.**\n\nThank 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.\n\n- **Table 3 (Runtime (in second) of GRADATE)**\n\n| **Procedure / Dataset**            | **ogbg-molbace** | **ogbg-molbbbp** | **ogbg-molhiv** |\n|:---------------------------------:|:------------------:|:------------------:|:-----------------:|\n| **Off-line Computation**          |                  |                  |                 |\n| FGW Pairwise distance             | 15.44            | 19.67            | 283.99          |\n| Label-informed pairwise distance  | 0.12             | 0.17             | 53.82           |\n| **On-line Computation**           |                  |                  |                 |\n| GREAT algorithm (Algorithm 2)     | 0.43             | 0.84             | 295.42          |\n| LAVA algorithm                    | 0.06             | 0.13             | 39.45           |\n| **GNN Training Time**             |                  |                  |                 |\n| GCN (w/ 10% data)                 | 12.76            | 13.91            | 190.34          |\n| GCN (w/ 20% data)                 | 13.08            | 22.59            | 312.08          |\n| GCN (w/ 50% data)                 | 22.21            | 30.48            | 845.46         |\n\n\n[1] https://arxiv.org/abs/2402.05660\n\n[2] https://arxiv.org/abs/2412.11654\n\n[3] https://arxiv.org/abs/2403.01092\n\n[4] https://dl.acm.org/doi/abs/10.1145/3503161.3548012\n\n[5] https://arxiv.org/abs/2306.04979"}, {"review_id": "xVEFyIWTgI", "reviewer": "Reviewer_y91a", "summary": "Graphs have become a fundamental data structure for representing complex relationships, with wide applications in areas such as molecular interaction modeling and recommendation systems. However, in graph-level classification tasks, distribution shift between the source and target domains poses a significant challenge.\n\nLimitations of existing methods:\nAlthough many Graph Neural Network (GNN)-based approaches have been proposed for Graph Domain Adaptation (GDA), most of them rely heavily on model architecture design and training strategies. This model-centric paradigm faces practical issues, such as the need for substantial computational resources to train and validate various architectural variants. Moreover, it often overlooks the quality of the source data. As a result, these methods tend to perform poorly under severe distribution shifts or limited computational budgets.\n\nTo address these limitations, this paper aims to answer a core question:\nHow can we select the most relevant training data from the source domain—based on available validation data—in order to improve graph-level classification accuracy on the target domain?\n\nThe paper proposes a novel model-free framework named GRADATE (GRAph DATa sElector), which aims to select the most relevant training data from the source domain to improve classification performance on the target domain.", "questions": "See weaknesses.", "limitations": "yes", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper provides solid theoretical insights.\n- The introduction is clear and easy to understand.\n- The experimental evaluation is comprehensive.\n\nWeaknesses:\n- 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?\n\n- 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?", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for recognizing our work! For the weakness and question you mentioned, we address each of those as follows.\n\n\n> **(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?**\n\n\nThank you for pointing out. GRADATE will depend on validation **data** but not necessarily validation **label**. As demonstrated in Remark 3.2 (line 165), setting`c=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*.\n\n\n> **(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?**\n\n\nLet us address each question as follows.\n\n- **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.\n\n- **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)\n\n- 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."}, {"review_id": "GpuDngYy1t", "reviewer": "Reviewer_qLY5", "summary": "This paper studies model-free graph data selection under distribution shift. The authors claim that existing methods belong to model-centric approaches and they often struggle with severe shifts and constrained computational resources. To address these issues, the authors proposed to select the best training data from the source domain for the classification task on the target domain. Specifically, it utilizes optimal transport theory to pick training samples without relying on any GNN model predictions, which is data-efficient. Comprehensive experiment results on several graph level datasets demonstrate that the proposed model can outperform existing selection methods and enhance existing GDA methods.", "questions": "1.\tThe model is only evaluated on graph level task. It is unclear whether the proposed model could work in node level task.\n2.\tThe authors claim that the proposed model is data efficient. However, based on the experimental results, sometimes using more data could achieve better performance. \n3.\tThe authors claim that the proposed model is model-free data selection. However, lots of other GNN architectures are not evaluated including graph transformer [1] and PPNP [2].\n4.\tIn Table 5, the GAT results for ogbg-molhiv are missing.\n5.\tFor some datasets like IMDB-MULTI, using full data could result in worse performance. However, the authors did not give any explanations on this phenomenon.\n6.\tThere are lots of other unsupervised graph domain adaptation baselines. It is unclear whether the proposed model also enhance their performance [3,4,5,6].\n7.\tIt 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?\n\nReferences:\n[1] Chen J, Gao K, Li G, et al. NAGphormer: A Tokenized Graph Transformer for Node Classification in Large Graphs[C]//The Eleventh International Conference on Learning Representations. 2023.\n[2] Gasteiger J, Bojchevski A, Günnemann S. Predict then Propagate: Graph Neural Networks meet Personalized PageRank[C]//International Conference on Learning Representations. 2018.\n[3] Liu S, Zou D, Zhao H, et al. Pairwise alignment improves graph domain adaptation[J]. arXiv preprint arXiv:2403.01092, 2024.\n[4] Liu M, Fang Z, Zhang Z, et al. Rethinking propagation for unsupervised graph domain adaptation[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2024, 38(12): 13963-13971.\n[5] Chen W, Ye G, Wang Y, et al. Smoothness really matters: A simple yet effective approach for unsupervised graph domain adaptation[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2025, 39(15): 15875-15883.\n[6] Fang R, Li B, Kang Z, et al. On the benefits of attribute-driven graph domain adaptation[J]. arXiv preprint arXiv:2502.06808, 2025.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Pros:\n1.\tThis paper proposes a model-free approach, which is new and different from existing model-centric methods.\n2.\tTheoretical justification is given to guide the design of the proposed components.\n3.\tThe proposed model could enhance the performance of existing unsupervised graph domain adaptation methods.\n\nCons:\n1.\tThe model is only evaluated on graph level task. It is unclear whether the proposed model could work in node level task.\n2.\tThe authors claim that the proposed model is data efficient. However, based on the experimental results, sometimes using more data could achieve better performance. \n3.\tThe authors claim that the proposed model is model-free data selection. However, lots of other GNN architectures are not evaluated including graph transformer [1] and PPNP [2].\n[1] Chen J, Gao K, Li G, et al. NAGphormer: A Tokenized Graph Transformer for Node Classification in Large Graphs[C]//The Eleventh International Conference on Learning Representations. 2023.\n[2] Gasteiger J, Bojchevski A, Günnemann S. Predict then Propagate: Graph Neural Networks meet Personalized PageRank[C]//International Conference on Learning Representations. 2018.", "was_revised": true, "final_justification": "Thanks for the rebuttal. I have adjusted my score.", "rebuttal": "Thank you for the thoughtful questions. We address each of these as follows.\n\n> **(W1)(Q1) The model is only evaluated on graph level task. It is unclear whether the proposed model could work in node level task.**\n\nWe 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.\n\nAlthough 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. \n\nWe 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.\n\n> **(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.**\n\n- **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.**\n\n- **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.\n\n\n> **(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.**\n\nWe 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.\n\n- **Table 1 (GRADATE outperforms other data selection methods)**\n\n| Dataset   | SGFormer (10%) | SGFormer (20%) | SGFormer (50%) | APPNP (10%) | APPNP (20%) | APPNP (50%) \n|:-----------:|:-----------:|:-----------:|:-----------:|:-----------:|:-----------:|:-----------:|\n| IMDB-BINARY | +9.82%  | +0.59%   | -0.34% | +7.28%   | +3.01%     |  -0.35%   | \n| IMDB-MULTI | +6.46%   | +57.40%    |  +1.65%   | -13.46%    | -2.59%   | +13.71%     |\n|  MSRC_21  | +14.26%  | +3.58%     |  +2.13%   | +9.54%     |  +3.18%   | +1.27%     |\n|  ogbg-molbace  | -9.66%  | +0.05%    |  +1.90%   | +4.03%     |  -2.31%   | +2.84%     |\n|  ogbg-molbbbp  | +2.93%  | +5.47%     |  -3.71%   | +22.8%    |  +6.33%  | -4.58%     |\n|  ogbg-molhiv  | +1.51%  | -1.79%     |  +1.65%   | -12.00%     |+6.07%   | +1.88%     |\n\n\n> **(Q4) In Table 5, the GAT results for ogbg-molhiv are missing.**\n\nWe apologize for the mistake. The number will be re-filled in the updated manuscript.\n\n> **(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.**\n\nWe assume the reviewer is referring to Table 1 and Table 3 in the paper.\n\n- 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.\n- 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.\n\nFor the updated manuscript, we will state this clearer in Section 4.2 and 4.4, respectively.\n\n\n> **(Q6) There are lots of other unsupervised graph domain adaptation baselines. It is unclear whether the proposed model also enhance their performance.**\n\nThank 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.\n\n- Table 2 (GRADATE enhances additional GDA methods)\n\n| Dataset   |A2GNN-ADV (20%)| A2GNN-MMD (20%)| TDSS (20%)|\n|:-----------:|:-----------:|:-----------:|:-----------:|\n|IMDB-BINARY| +31.12% | +11.40%|+3.12% |\n|IMDB-MULTI| +26.54% |+58.88% |-42.1% | \n|MSRC_21| +20.63% |-4.40% |+25.09% |\n|ogbg-molbace| +1.46% | -2.57%|+2.88% |\n|ogbg-molbbbp|+17.34%| +5.85%|-5.71%|\n|ogbg-molhiv|+0.65% |+0.81% |+0.55%|\n\n\n> **(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?**\n\nTo 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.\n\n\n- Table 3 (GRADATE outperforms other selection methods under lower-resource scenario)\n\n| Dataset   |GAT (1%)| SGFormer (1%)| APPNP (1%)|\n|:-----------:|:-----------:|:-----------:|:-----------:|\n|IMDB-BINARY| +10.74% | +3.24%|+6.92% |\n|IMDB-MULTI| +0.00% |+0.00% |+43.36% | \n|MSRC_21| -3.94% |-8.21% |+35.04% |\n|ogbg-molbace| +0.00% | +16.96%|+27.85% |\n|ogbg-molbbbp|+2.19%| -17.21%|+6.60%|\n|ogbg-molhiv|+0.01% |+8.93% |+2.01%|\n\n\n\n[1] https://arxiv.org/abs/2306.10759\n\n[2] https://arxiv.org/abs/1810.05997\n\n[3] https://arxiv.org/abs/2402.05660\n\n[4] https://arxiv.org/abs/2412.11654\n\n[5] https://arxiv.org/abs/1710.10903\n\n[6] https://arxiv.org/abs/2305.00054"}, {"review_id": "4a57VFEp7u", "reviewer": "Reviewer_ThiT", "summary": "This paper studied graph data selection problem under distribution shift setting. Specifically, the authors proposed a data-centric rather than model-centric framework. They designed Graph Dataset Distance inspired by FGW distance, and utilized optimal transport to find the most adaptive source data by minimizing GDD.", "questions": "1. 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 benifits all models?\n2. I understand that with the increase of seleciton 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.", "limitations": "yes.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strenghts:\n1. Clear motivation. The authors listed the drawbacks of model-dependent GDA, i.e., extensive resources and ignorance of source data quality. These drawbacks can actually motivate the model-free framework.\n2. Theoretical support. The proposed framework is theorem driven. I roughly checked the correctness. It's generally ok, but I cannot guarantee the details.\n3. Reasonable experimental settings. The authors did three types of numerical comparisons, verifying the improvement over data selection and model-centric GDA.\n\nWeaknesses:\n1. 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 vallidation 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.\n2. 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).\n3. 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\\neq0$. 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. \n4. GDD incrementally adds label distance based on traditional FGW. The label distance is defined in the same way as FGW.", "was_revised": true, "final_justification": "I stick to my negative evaluation.\n\n1. This paper studies graph domain adaption (GDA) problem, which is for a better performance on target domain. The proposed technique was for decreasing domain gap between source and target by reselecting source graphs. But this operation will also change the source performance, so it cannot theoretically guarantee how the target performance changes. Therefore, the designed method is not theoretically correct for GDA.\n\n2. In the introduced GDD, the authors added label distance on FGW. But label distance does not work as shown in the tables in rebuttal, where only 50% cases shows the gains from label distance, while for the other 50% cases, label distance degrads the model. I do not think such random performances can support the usefulness of the proposed label distance, and then GDD.\n\nTherefore, the two main contributions exist flaws.\n\nFor the first point, the authors finallly attempted to argue that this paper is for data selection, not for GDA. I am skeptical, because for me, the logic in abstract and introduction follows 1) what's GDA, 2) problems of model-centric methods for GDA, and 3) the authors proposed model-free method to tackle the challenges. \\\nAnthor point, please refer to line 72-73 in Section 2 Preliminaries, the authors wrote \"We also provide the formal problem formulation of graph domain adaptation (GDA) in Appendix K.\" I do not understand if this paper is not for GDA but data selection, why the authors did not give the formal formulation for the latter?", "rebuttal": "We thank the reviewer for the insightful questions. We address each of those as follows.\n\n> **(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.**\n\n\nThis 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.\n\nTo 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. \n\n\n- **Table 1 (GRADATE data decreases train \\& validation losses)**\n\n\n| Dataset | Δ train loss | Δ validation loss | \n|:-----------:|:-----------:|:-----------:|\n|  IMDB-BINARY  | -38.3%  | -29.2% |\n|  IMDB-MULTI   | -30.7%  | -0.45% |\n|  MSRC_21      | -60.4%  | +12.7% |\n|  ogbg-molbace | +17.1%  | -31.4% |\n|  ogbg-molbbbp | -79.3%  | -37.7% |\n|  ogbg-molhiv  | -64.1%  | -3.78% |\n\n\n\n> **(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).**\n\nThanks 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)**.\n\n\n> **(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.**\n\nWe address each concern as follows.\n\n- **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.\n\n\n- **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.\n\n\n> **(W4) GDD incrementally adds label distance based on traditional FGW. The label distance is defined in the same way as FGW.**\n\nWe 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:\n\n- **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.\n\n- **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.\n\n- **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.\n\n> **(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?**\n\n\nWe 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.\n\n> **(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.**\n\nThanks 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.\n\nIn 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.\n\n[1] https://arxiv.org/abs/2306.04979\n\n[2] https://dl.acm.org/doi/abs/10.1145/3503161.3548012\n\n[3] https://arxiv.org/abs/2307.11341\n\n[4] https://arxiv.org/abs/2306.03256"}]

Author rebuttal:

Meta-review: This paper proposes GRADATE, a model-free approach for data selection to address domain adaptation in graph-level classification. Shifting the focus from model-centric to data-centric solutions, this work leverages optimal transport (OT) theory to select a subset of source data that is most aligned with the target domain, without relying on a specific GNN architecture for the selection process. The method is supported by theoretical motivation and extensive empirical results.

The reviewers recognized the novelty of the data-centric approach for graph domain adaptation (GDA). However, the idea of using OT-based approaches for graph data selection is not entirely new, given existing works [1, 2] that have proposed to use Tree Mover's Distance for size generalization and graph subsampling. Initial reviews also raised important concerns, primarily regarding the use of labeled validation data in the selection process, which could lead to an unfair comparison with standard GDA methods. However, the authors effectively addressed this in their rebuttal by providing new experiments in a completely label-free setting, demonstrating that the method's strong performance holds. While some debate remained regarding the precise theoretical guarantees and the distinction between a data selection method versus a GDA method, the majority of reviewers were satisfied with the authors' clarifications and the strength of the empirical evidence.

Overall, this paper introduces a valuable and well-motivated data-centric perspective to the problem of graph domain adaptation. Despite some lingering discussion on its theoretical framing, the method's simplicity and strong empirical results make it a solid contribution to the field. Therefore, I recommend acceptance.

That said, I strongly encourage the authors to incorporate the following points in the camera-ready version:

1. While the proposed method could be applicable to other problems, the current paper is centered on graph domain adaptation, as stated in the introduction and validated by the experiments. The present title is too broad and does not reflect the actual scope. In particular, the phrase “under distribution shifts” is ambiguous—it can refer to both out-of-distribution (OOD) generalization and domain adaptation, whereas this work focuses only on the latter. Moreover, the method specifically addresses covariate shifts, which are only one type of distribution shift. I therefore recommend specifying “domain adaptation” and “covariate distribution shifts” explicitly in the title.

2. The additional experiments provided in the rebuttal substantially strengthen the paper—for example, the evaluation under the validation-label-free setting, the results with graph transformers, and the time cost comparison. These results should be incorporated into the main paper.

3. As noted earlier, prior studies [1, 2] have already explored optimal transport (OT) approaches for graph data selection. These works should be properly discussed in both the method and related work sections.

[1] Georgiev et al., Beyond Erdos-Rényi: Generalization in Algorithmic Reasoning.

[2] Jain et al., Subsampling Graphs with GNN Performance Guarantees.
Decision: Accept (poster)