Pave Your Own Path: Graph Gradual Domain Adaptation on Fused Gromov-Wasserstein Geodesics
Authors: Zhichen Zeng
Ruizhong Qiu
Wenxuan Bao
Tianxin Wei
Xiao Lin
Yuchen Yan
Tarek F. Abdelzaher
Jiawei Han
Hanghang Tong
Venue: Accepted by TMLR ()

Abstract: Graph neural networks, despite their impressive performance, are highly vulnerable to distribution shifts on graphs.
Existing graph domain adaptation (graph DA) methods often implicitly assume a mild shift between source and target graphs, limiting their applicability to real-world scenarios with large shifts.
Gradual domain adaptation (GDA) has emerged as a promising approach for addressing large shifts by gradually adapting the source model to the target domain via a path of unlabeled intermediate domains.
Existing GDA methods exclusively focus on independent and identically distributed (IID) data with a predefined path, leaving their extension to non-IID graphs without a given path an open challenge.
To bridge this gap, we present Gadget, the first GDA framework for non-IID graph data.
First (theoretical foundation), the Fused Gromov-Wasserstein (FGW) distance is adopted as the domain discrepancy for non-IID graphs, based on which, we derive an error bound on node, edge and graph-level tasks, showing that the target domain error is proportional to the length of the path.
Second (optimal path), guided by the error bound, we identify the FGW geodesic as the optimal path, which can be efficiently generated by our proposed algorithm.
The generated path can be seamlessly integrated with existing graph DA methods to handle large shifts on graphs, improving state-of-the-art graph DA methods by up to 6.8% in accuracy on real-world datasets.

Published in Transactions on Machine Learning Research (02/2026)
Pave Your Own Path: Graph Gradual Domain Adaptation on Fused Gromov-Wasserstein Geodesics
Zhichen Zeng
zhichens@rllinois.coo edu
University of Ilinnos Trthna-Champpnn
Ruizhong Qiu University of Ilinois
r95thlknoiss. edu
Wenxuan Bao
wboo @illioois. edu
University of Alinois Urbana- Champ-nn
Tianxin Wei
tweil0@illioiis edu
University of Alinois Situna-Champaiigh
Xiao Lin
riaol13@rllinoss.com edu
University of Alinois Trtana-Champaige
Yuchen Yan
yucheny5@illinois.o edu
University of Alinois Crampa-Champiign
Tarek F. Abdelzaher
zaher@illioois.cm edu
University of Alinois Sibena-Champping
Jiawei Han University of Illinois Urbana-Chuan Chanpaan
hanj@illinois. edu
Hanghang Tong
htongtrilkiois.edi edu
University of Tlinnis Pibana-Champone
Reviewed on OpenReview: https: // openreview. net/ forum? id- dTPBqTKGPs
Abstract
Graph neural networks, despite their impressive performance, are highly vulnerable to distribution shifts on graphs. Existing graph domain adaptation (graph DA) methods often implicitly assume mild shift between source and target graphs, limiting their applicability to real-world scenarios with large shifts. Gradual domain adaptation (GDA) has emerged as promising approach for addressing large shifts by gradually adapting the source model to the target domain via path of unlabeled intermediate domains. Existing GDA methods exclusively focus on independent and identically distributed (IID) data with a predefined path, leaving their extension to non-IID graphs without a given path an open challenge. To bridge this gap, we present GADGET, the first. GDA framework for non-IID graph data. First (theoretical foundation). the Fused Gromov- Wasserstein (FGW) distance is adopted as the domain discrepancy for non-IID graphs, based which, derive error bound on node, edge and graph-level tasks, showing that the target domain error is proportional to the length of the path. Second (optimal path), guided by the error bound, we identify the FGW geodesic as the optimal path, which can be efficiently generated by our proposed algorithm. The generated path can be seamlessly integrated with existing graph DA methods to handle large shifts on graphs, improving state-of- the--rr graph DA methods by up 6.8% accuracy on real-worle datascts.

---

Published in Transactions on Machine Learning Research (02/2026)
1 Introduction
In the era of big data and AI, graphs have emerged as a powerful tool for modeling relational data. Graph neural networks (GNNs) have achieved remarkable success in numerous graph learning tasks such as graph classification Xu et al. (2018), node classification Kipf & Welling (2017), and link prediction (Zhang & Chen (2018). Their superior performance largely relies on the fundamental assumption that training and test graphs are identically distributed, whereas the large distribution shifts real-world graphs significantly undermine GNN performance Li et al. )022).
To address this issue, graph domain adaptation (graph DA) aims to adapt the trained source GNN model to a test target graph Wu et al. (0233) Liu et al. (2023a). Promising as it might be, existing graph DA
methods follow a fundamental assumption that the source and target graphs bear mild shifts, while real-world
graphs could suffer from large shifts in both node attributes and graph structure Hendrycks et al. (2021) ; Shi
et al. (0024). For example, user profiles are likely to vary from different research platforms (e-g., ACM and DBLP), , resulting in attribute shifts citation networks. In addition, while Instagram users are prone to connect with close friends, users tend to connect to business partners on LinkedIn, leading to structure shifts on social networks. To handle large shifts, gradual domain adaptation (GDA) has emerged as a promising approach Kumar et al. (2020); Wang et al. (2022); He et al.] (2023). The key idea is to gradually adapt the source model to the target domain via a path of unlabeled intermediate domains, such that the mild shifts between successive domains are easy to handle. Existing GDA approaches exclusively focus on independent and identically distributed (IID) data, e.g,, images, with a predefined path Kunar et al.) (2020); Wang ct al. (002)) however, the extension of GDA to non-IID graphs without a predefined path remains open challenge. Therefore, question naturally arises:
How to perform GDA on graphs such that large graph shifts can be effectively handled?
Contributions. In this work, we focus on the unsupervised graph DA and propose GADGET, the first GDA framework for non-IID graphs with large shifts. An illustration of GADGET shown in Figure [ While direct graph DA fails when facing large shifts (Figure [a)), GADGET gradually adapts the GNN model via unlabeled intermediate graphs based methods on real-world graphs (Figure [e)). Specifically, to measure the domain discrepancy between non-IID graphs, we adopt the prevalent Fused Gromov-Wasserstein (FGW) distance Titouan et al. (2019) considering both node attributes and connectivity, such that the node dependency, i.e., non-llD property, of graphs can be modeled. Afterwards (theoretical foundation), we derive an error bound for graph GDA, revealing the close relationship between the target domain error and the length of the path. Furthermore (optimal path), based on the established error bound, we prove that the FGW geodesic minimizing the path length provides the optimal path for graph GDA. To address the lack of path in graph learning lasks, we propose a fast algorithm to generate intermediate graphs on the FGW geodesics, which can be seamlessly integrated with various graph DA basclines to handle large graph shifts. Finally (empirical evaluation), we carry out experiments on node-level classification, and the results demonstrate the effectiveness of our proposed GADGET, siguificantly improving graph DA methods by up to 6.8% in classification accuracy.
teff-training (Figure [b), achieving significant improvement on graph DA
2 Related Works
Graph Domain Adaptation. Graph DA transfers knowledge between graphs with different distributions and can be broadly categorized into data and model adaptation. For data adaptation, shifts between source and target graphs are mitigated via deep transformation [Jin et al. (2023); ; Sui ct al. (2023), edge re-weighting Liu et al.] (2023a) and graph alignmen Liu et al.] (2024a). For model adaptation, various general domain discrepancies, e.g., MMD Gretton et al. (2012) and CORAL (Sun et al. (016), and graph domain discrepancies Zhu et al. (201)): Wu et al. (2023); You et al. 2022)) are proposed to align the source and target distributions. In addition, adversarial approaches Dai et al. (002)) Zhang et al. (2019) learn domain-adaptive
embeddings that are robust to domain shifts. However, existing graph DA methods only handle mild shifts between source and target, limiting their application to real-world large shifts.
Gradual Domain Adaptation. GDA tackles large domain shifts by leveraging gradual transitions along intermediate domains. GDA is first studied in Kumar al. (2020), where the self-training paradigm and
2

---

Published in Transactions on Machine Learning Research (02/2020)
CLASSES
DONATNS
source
target
GRADE
40
Accuraxy
20-
Self- Training
Self Training
10
Direct Adaptation
Entropy Weight
Entropy Weight
Source
Target
Source
Intermediate
Target
Arport
Dataset
Social
Citation
(a) Direct Domain Adaptation
(b) Gradual Domain Adaptation
(c) Classification Accuracy
Figure 1: An illustration of graph GDA. Figures (a-b) show the node embeddings, whose colors (blue and red) indicate classes and shapes (o and x) indicate domains, and the decision boundary. (a): Direct adaptation
fails when facing large shifts as all target nodes in class 0 (x) are misclassified. (b): Gradual adaptation successfully handles large shift by decomposing it into intermediate domains on the FGW geodesics with mild shifts, where all target nodes in class (x) correctly separated from those in class 1 (x). (c): Bars w/ and w/o hatches show the performance of direct adaptation and GDA, respectively. Number over bars are the absolute improvement on accuracy. Our proposed GADGET significantly improves various graph DA methods on real-world datascts.
its eπror bound, are proposed. More in-depth theoretical insights Wang et al. (022) identify optimal paths, achieving trade-ofls between efficiency and effectiveness. More recent studies generalize GDA to scenarios without well-defined intermediate domain by either selecting from a candidate pool Chen Chao (2021) or generating from scratch He (2023). However, cxisting GDA methods exclusively focus on IID data, whereas the extension to noD graph data is largely un-explored.
3 Preliminaries
In this section, we first introduce the notations in Section 3.1
based on which, preliminaries on the FGW
space and graph DA are introduced in Sections 3.2 and 3.3 respectively.
3.1 Notations
We use bold uppercase letters for matrices (e.g., A), bold lowercase letters for vectors (e-g., s), calligraphic letters for sets (e.g., 9), and lowercase letters for scalars (e.g., a). The element (i,j) of matrix A is denoted A(i.). The transpose of A is denoted by the superscript (c.g., A").
We use X' for feature space and y for prediction space, with their respective norms as || lIx and ||-|py- A graph g = (V, A, X) has node set V, adjacency matrix A E ||||x|V| and node feature matrix X E x Let @ denote the space of all graphs, a GNN is a function ʃ @ 6 - ylVi mapping a graph g E 6 to the prediction space V. We denote the source graph by Go and the target graph by Gr. We use subscripts n, e, to denote node-level, odge-level and graph-level tasks, respectively.
The simplex histogram with bins is denoted as A, {u E R E ((1)= 1). We denote the probabilistic
coupling II(-;)), and the inner product as (.)). We use 6, to denote the Dirac measure in z. For simplicity, we denote the set of positive integers no greater than as N+ Sn.
3.2 Fused Gromov-Wassersted (FGW) Space
The FGW distance serves as a powerful measure for non-lID graph data by considering both node attributes and connectivity. Formally, the FGW distance can be defined as follows.
Definition 1 (FGW distance: Peyré et al. (2016 2019:
Titouan et al. (019)). Given two graphs Go, G
represented by probability measures 140 Σ
11 (o. 14 Σ} 950 X,(u))), where h E Appl: E
3

---

Published in Transactions on Machine Learning Research (02/2026)
Ami histograms, cross-graph matrix M P measuring cross-graph node distances based on attributes, and two intra-graph matrices Co E R Volx|Vol, C1 E [M measuring intra-graph node similarity based on graph structure, the FGW distance drowia (9o, 91) is defined as:
SFGWin,(91199
min sell(ua
(E
where
(g) = - (1-a) (),
(1)
MEVO vEVi
where q and a are the order and weight parameters of the FGW distance, respectively.
Intuitively, the FGW distance calculates the optimal matching S between two graphs in terms of both attribute distance M and node connectivity Co, C₁. Following common practice Titouan et al. 2019 Zeng
et al. (2024c), we adopt q = 2 and use the adjacency matrix A, as the intra-graph matrices C. For brevity, we omit the subscripts g, a and use drcw to denote drcW:a.-
Since the FGW distance only pseudometric, we follow a standard procedure Howes (0022) define an induced metric drow- We start with the FGW equivalence class defined as follows.
Definition 2 (FGW equivalence class). Given two graphs Go, 91, the FGW equivalence relation is defined Gu G1, iff drow (Gu, 91) 0. The FGW equivalence class w.r.t. ~ is defined as [[]] g ~g). The FGW space is defined as 6//~ ([9] G
Afterwards, the induced metric diow is defined by (F [91]) = draw (Go. 91), which measures the distance between two FGW equivalence classes. The FGW geodesics is defined as follows
Definition 3 (FGW geodesic). A curve [0, + 6/ 1//~/ is FGW geodesic from [Go]] to [G.] iff 7() [9u]. >(1) = [9 and for every Ao, A E 10,
drow (T))())))) = DA - Aul dFow((9o) [9]]).
Intuitively, the FGW geodesic the shortest line directly linking the source and target graph. To simplify notation, we use [9] and & interchangeably for the rest of the paper.
3.3 Unsupervised Graph Domain Adaptation
Unsupervisod graph DA aims to adapt a GNN model trained on labelod source graph to an unlabeled target graph, which can be formally defined as follows.
Definition 4 (Unsupervised graph DA). Given a source graph Go with labels Yo. where Yo yo for node-level task, Yo E /ol/ool for edge-level tasks and Y, Vy for graph-level tasks, and a target graph Gr. Unsupervised graph DA aims to train model using the labeled source graph (9o, Yo) and the unlabeled larget graph G, to accurately predict larget labels &, = ((1)..
However, existing graph DA methods fundamentally assume mild shifts bet ween source and larget graphs. To handle large shifts, we introduce the idea of GDA to graph DA, which gradually adapts a source GNN the target graph via series of sequentially generated graphs.
4 Theoretical Foundation
In this section, we present the theoretical foundation of graph GDA. The problem is formulated in Section 4.1 We establish the error bound in Section 4.3 and derive the optimal path in Section 4.4
4.1 Problem Setup
To formulate the graph GDA problem, first define the path for graph GDA as follows.
4

---

Published in Transactions on Machine Learning Research (02/2026)
Definition 5 (Path). A path between the source graph Go and target graph G1 is defined H (Ho, Hr), where Ho Go and Hr 91.
In general, for a T staagg graph GDA, given the model ft-1 at stage t and the successive graph H, at stage t, self-training paradigm trains the successive model ft based on the pscudo-labels ft-1(H4). Formally, graph GDA can be defined as follows.
Definition (Graph gradual domain adaptation). Given a source graph 9n with label Yo, and target graph G1. Graph GDA (1) finds path H. with Ho Go. Hr 91, and (2) gradually adapts the source model to the target graph via self-training, that is:
ft = arg min,, (L VI -,,,,,,) 1,2....T
where is the loss function and f (He) is the pseudo-label for the 1-th graph He given by the previous model fi-1- Graph GDA aims to minimize the target error between the prediction fr( and the groundtruth label Y1.
Note that we consider a more general self-training paradigm compared to Empirical Risk Minimization (ERM) Kumar et al. (2020) and do not pose specific constraints on the loss function f. That is to say, our proposed framework is compatible with various graph DA baselines with different adaptation losses.
Definition 7 (Graph convolution). For any graph G = (V. A, X). the graph convolution operation gen for any node depends only on node pair information Ng(u) = (A(u,v), (())eee,, that is gen(g) == gen(Ng(u)) = gen({ u), X (w))eev)) Vu V.
A GNN layer (0) is composition of graph convolution gen, linear transformation and ReLU activation
= ReLU o Linear gen (4)
(2)
We further define nodo-level, edge-level and graph-level tasks follows
Definition 8 (Node-level task). A GNN model is composition of graph convolutions g( i.e., fa g( o o ((), For each node V, the node-level loss is defined by c, (9),w, where the groundtruth label (u) is omitted for brevity. The overall node-level loss of a GNN fx on graph G can be defined as
Sn(An, = DI
Σ NEV
en (9))))))
Definition 9 (Edge-level (ask). A GNN model is composition of graph convolutions g( and pairwise (g)
aggregation function o, i.e., fe = (o.g"))...og"" = fo. The aggregation function & turns the embeddings of two nodes (9), (9) into an edge embedding (e()) = (ff (n) (9))).) For each edge (u, u') E g, the edge-level loss is defined by e. (fe(9) where the groundtruth label Y(u,, u()) is omitted for brevity. The overall edge-level loss of a GNN fe on a graph g can be defined as
(a(Sa,
Σ <a (J.()) U.W'EV
VI2
Definition 10 (Graph-level task). A GNN model is composition of graph convolutions (() and a pooling function r, i.e., f, = r o o... ( The pooling function turns the embeddings of all nodes fG( into a graph embedding (9) = (9).. The overall graph-level loss of a GNN fy on a graph g can be defined as (fg. 9), where the groundtruth label y()) is omitted for brevity.
4.2 Assumptions
To capture the non-lID nature, i.e., node dependency, of graphs, we adopt the FGW distance Titouan et al. (2019) equation 1 as the domain discrepancy, measuring the graph distance in terms of both node attributes X and node connectivity A. We make several assumptions following previous works on graph DA Zhu et al. Bao et al. (2024) and GDA Kumar et al. (2020); Wang et al.) (0022.
(2021):
5

---

Published in Transactions on Machine Learning Research (02/2026)
Assumption 1 (General regularity assumptions). We make several regularity assumptions
A: (Lipschitz continuity of graph convolution). We assume there cxists Ce > 0 such that for any nodes E Vo, E Vi we have
(ggen(Go) gen(G)) S Ce dw (NG,lu),N,,(1),, where dw (I(Ao(m, v²), Xo(u")) ((A1 v'), X1 (i('')) inf 18 ((w/ [o]oo(u A 22 (1 - a)l Xo(u') X2 (co)ll
+Ell(HO,))))
B: (Lipschitz continuity of linear layer). We assume there exists Clia 0 such that for any weight matrices W in linear layers Linear(x:) = Wa b we have [W| S Cli.
Both assumptions ensure the generalization capability and stability of the GNN model. Specifically, As- sumption Assumption A] enforces smoothness with respect to graph topology: nodes with similar local neighborhoods must yield similar embeddings. Assumption Assumption B requires model parameters to be finite, slandard condition satisfied by regularization.
Assumption (Task-specific regularity assumptions). We make the following regularity assumptions for different graph learning tasks
C: (Lipschitz continuity of loss functions). We suppose there exists Ct > 0 for any node-level GNNs fa.. Cr > O for any edge-level GNNs Se,, and Ct, for any graph-level GNNs fao, such that
(ex(fno en (fm (9)w) Ct., Il (Ng(u)) fna (Ng (M)) Ibw. Ico(feo (9)(),))) c. (fes (9)))))) S Cr, I15 (g) - fer (mw))l) 15g 9) - Eo 9)1 S Ct," llf - (9)lx,.
(3)
(4)
(5)
D: (Hölder continuity of loss functions).
We suppose there exists Cw. > for any nodes u E Vo, v V1; Cw. O for any edges (u,u²) E
Go. (v, G1; Cw., for any graphs 61 and q 1, such that
((0())(9))))) - e, (f s Ow. (90) - fn(91)e113.. (ee(fe (9o)(aw))) ce (f)())) &Cw.- (9fe(9)))m.))) fe 90) - 91)1 S &Cw, (90) - fg(()))33,
(6)
(7)
(8)
E: (Lipschitz continuity of aggregation function). We suppose there exists Co > 0 such that for any edges (u,"') E Gu. (2, E G1, we have
(9)
F: (Lápschitz continuity of pooling function). We suppose there exists C, such that for any graphs
Gr G2 and coupling π,, we have
|| (Jn(9o)) r (fx( lb;; C, (( - (n()))
(10)
Assumption Candd Assumption eefforee the smoothness of the loss function with respect to model predictions. Assumption C posits that similar predictions from different models result in similar losses. Assumption D complements this by ensuring that for a fixed model, similar input embeddings load to similar losses. These conditions are mild and satisfied by standard surrogate losses (e.g. MSE, Cross-Entropy) on bounded domains.
Assumption E and Assumption F guarantee that readout operations preserve embedding proximity. As- sumption Assumption El ensures odgo-level aggregation remains stable under small perturbations node embeddings. Similarly, Assumption AAsummttin F requires the graph pooling function to preserve local smoothness, ensuring that graphs with aligned node embeddings map to similar graph-level representations.
6

---

Published in Transactions on Machine Learning Research (02/2026)
4.3 Error Bound
Under Assumption analyze the error bound of graph GDA. We first show that any L-layer GNN is ((Im(( Hölder continuous w.r.t. the 3-FGW distance, where a+ (+
Lemma (Hölder continuity). For uny L-layer node-level GNN fn = Ot- edge-level GNN Sa Φo Ol- and graph-level GNN fg =ro Ol=ig"), where Ol_1g g gl) o... og and g are GNN
layers in equation
Given source graph Go and target graph G1, have:
((ff E(f,91) SC C. C. ooo. 91),
where
- (C C.Cii))
B =
a (1-aa)) (CIlCa))(CCCim
a (1 a) a)) 1- (c.0mm a))
Cgm = CoClin
1 C.Cii a)
Ow, Cgans for node-level tasks
C=
2Cw, CoCgan: for edge-level tasks
Ow, C.Cgan; for graph-level tasks
The proof can be found in Appendix A Intuitively, the upper bound of the performance gap between source loss E(ʃ, 9o) and larget loss E(S, 91) is proportional to the FGW distance between the source graph Go and target graph G1. Therefore, GNNs could suffer from significant performance degradation under large shifts.
To alleviate the effects of large shifts, we investigate the effectiveness of applying GDA on graphs, and derive an error bound shown in Theorem 1
Theorem (Error bound). Let fo denote the source model trained on the source graph Ho = Go- Suppose there are T 1 intermediate stages where in the t-th stage (for = 1, 2, ..., ...,,, we adapt fi-1 1 to graph He to obtain an adapted ft. If every adaptation step achieves ( - fe (HH))ly I ö on the corresponding graph He, then the final error E(JT; Ht) on larget graph HT 91 is upper bounded by
T
(Urr,:))E(foo.. + Ct 8T + C Σ
H,
where === = Ct, for node-level task, Ct Ct, for edge-level tasks, and Ci = Ci2, for graph-level tasks.
The proof can be found in Appendix A In general, the upper bound of the target GNN loss E(fr, G1) is determined by three lerms, including source GNN loss E(So, 9o), (2) the accunulated training error T6, and (3) the generalization error measured by length of the path E deow(He-1 (He-1, H.). In the following subsection, we will analyze which path best benefits the graph GDA process.
4.4 Optimal Path
Motivated by Theorem I we derive the optimal path that minimizes the error bound in Theorem
Theorem 2 (Optimal path). Given source graph Go and a target graph G1, let y: [0, + 6/ ~ be an FGW geodesic connecting 9o and G1. Then the error bound in Theorem attains its minimum when intermediate grophs are H. = ( VI 0, 1,..,, T, where have:
E(T, (0) Cr Cr-OT C. geo 91)
T4-1
The proof can be found in Appendix In general, the key idea minimize the path length, whose minimum is achieved by the FGW geodesic between source and target. As remark, the optimal number T
7

---

Published in Transactions on Machine Learning Research (02/2026)
of intermediate steps can be obtained by
T (q C ) dFGwin 91).
(11)
Intuitively, the number of stages T balances the accumulated training error (the second term on the RHS) and the generalization error (the third term on the RHS). Following Lemma when Cw., Cw Ow, are small, model robust to domain shifts and the error bound dominated by the accumulated training error, thus, we expect smaller T for better performance. On the other hand, when Ow.,, Cw., Ow, are large, model is vulnerable to domain shifts and the crror bound is dominated by the gencralization error, thus, we expect larger T to reduce domain shifts, hence achieving belter performance.
5 Methodology
In this section, we present our proposed GADGET to perform graph GDA on the FGW geodesics. As self-training is highly vulnerable to noisy psendo labels, we first propose an entropy-based confidence to denoise the noisy labels. Motivated by the theoretical foundation, we introduce a practical algorithm to generate intermediate graphs, which as we prove, reside on the approximated FGW geodesic to best facilitate the graph GDA process.
Motivated by Thcorem work Zeng et al. (2024c) generates graphs on the Gromov- Wasserstein geodesic purely based graph structure via mixup. We generalize such idea to the FGW geodesics to consider both graph structure and node features.
2 generate the FGW geodesic as the optimal path for graph GDA. Previous
Specifically, given source graph Go = (Vo: An, Xo), target graph 91 = (Vi, A X1), and their probability distributions No, M1. two transformation matrices Po, P1 are employed to transform them into well-aligned pairs Go- (Vo Ao. X (V, A, xi) with probability distributions Po: Pi as follows Zeng et al. (2024c
Åo = PJ Po. Xo = P Xo, to =PoMos
Á PT P1, X P ji Pi
(12)
where Pg = poo @ 1 1x Pi = 1xpai @ IPal-
Afterwards, the intermediate graphs He are the interpolations of the well-aligned pairs, that is
H²: = Vo V1, ( A0 Al, (1-7) Xo+ x
(13)
With the above transformations, we prove that the intermediate graphs generated by equation 13 are on the FGW geodesics in the following theorem.
Theorem 3 (FGW geodesic). Given source graph Go and target graph G1, the transformed graphs Go &r are in the FGW equivalent class of Go,91, i.e., [Go] = [Go], [9]] = [G]]] Besides that, the intermediatee graphs H4, Vt = 0, T, generated by equation 13 are on an FGW geodesic connecting Go and G1.
According to Theorems and directly applying the generated He best. benefits the graph GDA process.
However, practically, the transformations in equation 12 involve computation in the product space, posing great challenges the scalability to large-scale graphs. For faster computation, we employ an efficient low-rank OT algorithm adapted from Zeng al. (202cc) to generate intermediate graphs the FGW geodesics. Specifically, via change of variable Qu = Podiag(g), (g), Q1 didig()) the transformation matrices Po, Pt can be obtained by solving the following low-rank OT problem
arg argming..Q.. ( (Qg
(14)
s.t. Qu E I[(p Q1 E II(p2. E Ar,
where r is the rank of the low-rank OT problem. When r //ll the optimal solution to equation provides the optimal transformation matrices Po, Pt. By reducing the rank of g from [V/|/// to smaller
8

---

Published in Transactions on Machine Learning Research (02/2020)
rank r, the low-rank OT problem can be efficiently solved via mirror descent scheme by iteratively solving the following problem Scetbon et al. 2022)
Zeng et al. (2024c):
! Q ((t1) (++))
arg min KL (Q),
K2 (0) K35 k)
Qu.Qu.9
s.1. Qo E M1 9),
Q g), g E
K = exp
y BB
diag (1/ (0) 00%
K!a - -ex
(B(O)' diag (1/
where
KS = exp
-ydiag Q B /9 (0)
@g
B = -M-(-aMMM4110000 Ao Qi diag (19
(00 A
Remark. Our path generation algorithm is adapted from Zeng et al. 2024ch but bears subtle difference. First (space), the Gromov-Wassorstee (GW) space in Zeng et al. (2024c) only captures graph structure information, but the FGW space considers both node attributes and graph structure information. Secondly (task), Zeng et al. (2024c) utilizes the GW geodesics mixup graphs and their labels for graph-level classification, while GADGET utilizes the FGW geodesic to generate label-free graphs for node-level classification. Thirdly (label), Zeng et al. (2024c) utilizes the linear interpolation of graph labels as the seeudo-labele for mixup graphs, requiring information from both ends of the geodesic which is inapplicable for graph GDA, while GADGET utilizes self-training to label the intermediate graphs, relying solely on source information.
Self-training paradigm. Self-training predominant paradigm for GDA Kumar et al. et al. (2022), but is known to be vulnerable noisy pseudo labels Chen et al. (2022a). Such vulnerability may be further exacerbated for GNN models as the noise propagate Wang et al. (2024); Liu et al. 2022
(020); Wang
To alleviate this issue, we utilize an entropy-based confidence to depict the reliability of the psoduo-labels.
Given a model output T. E R where C is the number of classes, the confidence score conf(ū;) is calculated
by
max, ent(ū, ent conf(ği) max, ent (1)) min, ent (ū))"
(15)
where ent(.) calculates the entropy of the model prediction. Intuitively, for reliable model outputs, we expect low entropy values and high confidence scores, and vice versa.
Error bound under approximation. Note that the error bound in Theorem | appplees for the ideal case where intermediate graphs Hi are on the exact FGW geodesics. The practical algorithm adopts low-rank formulation which may introduce approximation error. We provide the following theorem to quantify the effect of low-rank approximation errors in practical algorithm.
Theorem 4 (Practical error bound). For sequence of intermediate graphs Hoy..., Hr on the approsimated FGW geodesics generated by GADGET, performing GDA along the path yield a fonal error E(fr, Hr) on target gruph Hr = 9, upper bounded by
E(fr.91) S Original bound + 4C8 drow(H, He-1) + 4CT82 opprox
where original bound is the upper bound the eract geodesics provided in Theorem and Sapprox max; draw(H,, H.) is the maximumm approcimation error between exact geodesic gruph He and low-rank approzimated graph He-
The proof of Theorem 4 is provided in Appendix A As detailed in the Appendix, when rank + |1llV2), iee, full rank, the approximation error Sapprox 0, yielding the original upper bound in Theorem 1
9

---

Published in Transactions on Machine Learning Research (02/2026)
6 Experiments
We conduct extensive experiments to evaluate the proposed GADGET. We first introduce experiment sctup Then, we provide the visualization of graph GDA to assess the necessity of incorporating GDA for graphs in Section 6.3 Afterwards, we evaluate GADGET's effectiveness on benchmark datasets in Section 6.2 We further conduct extensive studies on the varying shift levels (Section 6.4) hyperparameter sensitivity (Section 6.5 and path quality (Section 6.6
in Section 6..
6.1 Experimental Setup
We conduct extensive experiments on node classification using both synthetic and real-world datasets, including Airport Ribeiro al. (2017), Citation [Tang et al. (2008), Social Li et al. (2015), and contextual stochastic block model (CSBM) Deshpande al. (2018). Airport dataset contains flight information of airports from Brazil, USA and Europe. Citation dataset includes academic networks from ACM and DBLP. Social dataset includes two blog networks from BlogCatalog (Blog1) Flickr (Blog2). We also adopt the CSBM model to generate various graph shifts, including attribute shifts with positively (Right) and negatively (Left) shifted attributes, degree shift with High and Low average degrocs, and homophily shifts with high (Homo) and low (Hetero) homophilic scores in the source and target graphs. More details are Appendix D
We adopt two prominent GNN models, including GCN Kipf & Welling (2017) and APPNP Gasteiger et al. (2018), as the backbone classifier. Different adaptation basclines can be utilized to adapt knowledge from one graph to its consecutive graph along the path. Baseline adaptation methods include Empirical Risk
Minimization (ERM), MMD Gretton et al. (2012) CORAL Sun et al. (2016), AdaGCN Dai et al. (0022 GRADE Wu et al. (2023) and StrultW Liu et al. (2023a).
During training, we have full access to source labels while having no knowledge on target la- bels. Results are averaged over five runs avoid randomness. Our code available More details are provided in Appendix D
https: www.tttuub.cmm/hhhhhheeeaeeeeeee
6.2 Effectiveness Results
To evaluate the effectiveness of GADGET in handling large shifts, we carry out experiment on both real-world and synthetic datasets, and the results are shown in Figure? 2 In general, compared direct adaptation (colored bars w/o hatches), observe consistent improvements methods and backbone GNNs different datasets when applying GADGET (hatched bars). Specifically, on real-world datasets, GADGET achieves an average improvement of 6.77% on Airport, 3.58% on Social and 3.43% on Citation, compared to direct adaptation. On synthetic CSBM datasets, GADGET achieves more significant performance, improving various graph DA methods by 36.51% in average. More result statistics are provided in Appendix C.I
the performance of variety of graph DA
Besides, we note small number of cases where direct adaptation performs better than GADGET. According to Theorem D the target error depends on the source performance, the accumulated training error, and the generalization error. When the shift is mild, the accumulated training error dominates the error bound, direct adaptation (T' = 1) is preferable. For extremely large shifts, bridging the gap would require many steps, and the resulting linear growth of accumulated training error can outweigh the reduction of the generalization term. Therefore, it is essential to choose an appropriate T that achieves a good balance between accumulated training error and generalization error.
6.3 Understanding the Gradual Adaptation Process
To better understand the necessity and mechanism of graph GDA, we first visualize the embedding spaces of the CSBM and Citation datasets trained under ERM. The results are shown in Figure 3 where different. colors indicate different classes and different markers represent different domains.
Firstly, is shown that large shifts exist in both datasots, as the source (+) and target samples (x) are scarcely overlapped. Besides that, direct adaptation often fails when facing large shifts. As shown in Figure B for the CSBM dataset, though the well-trained source model correctly classifies all source samples (o.)), all
10

---

Published in Transactions on Machine Learning Research (02/2026)
ERM
KND Attributio:
CORAL Rig-Righh
AdaGCN
GRADE
StruWWW
Homophily Homo-Heteeo
Homophily; Meteo-Homo
Attribute: Right-Leff
Degree: Low-Hligh
Degree: High-Loww
100
Accuracy
25
25
Model
Model
Model
Model
(a) csbm
NND
CORAL
AdsGCN
GRADE Brazii Europe
StruRNN
Use Brazi
Use
Brazik
Europe Use
Europe Brazil
Accuraty
OCN
APPMP
GCN
APPNP
GCN
APPNP
GCN
APPNP
GCN
APPNP
GCN
APPNP
Model
Mocel
Model
Model
Model
Model
(b) airport
MMD
MND ACM-DBLP
Blogi-Blog?
Blog2-Blog
DBLP-ACM
80
10
Accuracy
Accuracc
CCN
AРPИР
GCN
APPNP
GCN
APPNP
GCN
APPNP
Model
Model
Modell
Model
(c) social
(d) citation
Figure 2: Experiment results. Different colors indicate different baseline adaptation methods. Bars with and without hatches indicate direct adaptation and gradual adaptation with GADGET, respectively. Our proposed GADGET consistently achieves better performance than direct adaptation on different backbone GNNs, adaptation methods and datasets. Best viewed in color.
CLASSES
DOMAINS
target
Direct Aduptation
GDA Step
GDA Step 2
GDA Step
Figure 3: Embedding space of CSBM dataset under homophily shifts. Direct adaptation (left) fails when facing large shifts. GDA (right) correctly classifies most samples in each step, resulting in significant improvement in the classification accuracy. Best viewed in color.
target samples from class 0 (x) are misclassified as class (x), due to the large shifts between the source and the target. In contrast, when adopting graph GDA, we expect smaller shifts between two successive domains, as source (+) and target (x) samples are largely overlapped, and the trained classifier correctly classifies most of the target samples.
The embedding space visualization provides further insights in the causes for performance degradation under large shifts, including representation degradation and classifier degradation. For representation degradation, we observe that although source samples are well separated, target samples are mixed together, indicating that source embedding transformation is suboptimal for the shifted target. For classifier degradation, while the classification boundary works well for source samples, it fails classify target samples. However, when adopting GADGET, not only the target samples are well-separated, alleviating representation degradation, but also the classification boundary correctly classifies source and target samples, alleviating classifier degradation.
11

---

Published in Transactions on Machine Learning Research (02/2026)
6.4 Mitigating Domain Shifts
To better understand how GADGET mit- igates domain shifts, we test the GNN performance under various shift levels be- tween source GR and target Ge. Specifi- cally, we vary (1) the attribute shift level measured by Au |avg(XX,) avg( (X,)), (2) the homophily shift level measured by Ah= 1h, - hel, and (3) the degree shift level measured by Ad = d2 del. And the results are shown in Figure [
FAM
Fadigt
homophily
attribute
cegree
80-
Accuracy (%6)
80-
80
80
70
60-
00-
50-
0.0
0.2
0.4
0.5
0.8
0.0
0.2
0.4
3.6
0.8
20
40
60
Shift Level An
Levi
Shift Level dul
Figure 4: Classification accuracy under different shift levels.
As shown in the results, when the shift level increases, the performance of direct adaptation (ERM) drops rapidly, while the performance of gradual GDA (GADGET) is more robust. Compared to the performance under the mildest shift (left), ERM degrades up to 41.5% under the largest shift (right), behaving like random guessing as the classification accuracy approaches 0.5 on a binary classification task. However, GADGET only degrades up to 30.3% on the largest shift compared to performance under the mildest shift and outperforms ERM by up to 26.7% on the largest shift.
In addition, is worth noting that GADGET underperforms direct adaptation when there domain shift does not exist. This is because the gradual GDA process involves self-training, which may introduce noisy pseudo-labels that mislead the training process. As we reveal in Theorem 2 the error bound includes accumulated error 78.. When domain shift is mild, i.e. drow drow(Go. 91) is small, the effects of the accumulated error could be significant. And under such circumstances, as shown in Eq. equation 11 the optimal number of intermediate steps T should be zero, i.e., direct adaptation.
6.5 Hyperparameter Study
We study how hyperparameters affect the performance and run time, including studies on the number T of intermediate steps and the rank of low-rank OT. We experiment on the CSBM datasets with 500 nodes.
For the number of intermediate steps T, the results are shown in Figure ((a) Overall, as T increases, the performance first increases and then decreases, achieving the overall best performance when T 3. This phenomenon aligns with our error bound in Theorem 2 When is smaller than the optimal T in Eq. equation 11 the shifts between two successive graphs is large and the generalization error Cwwdfaw (1)
TV
dominates the performance; Hence, the performance first improves. However, when T is larger than the optimal T in Eq. equation [1] the accumulated training error T6 dominates the performance; Hence, the performance degrades. Besides, we observe that the textittraining time increases almost linearly w.r.t. T, as the gradual domain adaptation process involves repeated training the model for T times. Based on the above observation, we choose T for the benchmark experiments as it achieves good trade-off between performance and efficiency.
For the choice of rank r, the results are in Figure 5(b) Overall, as r increases, the performance first increases and then fluctuates at high level. When r is small, the transformation in Eq. equation [2 projects souree and target graphs to small graphs, causing information loss during the transformation; Hence, the performance degrades. However, when r is large enough, the transformation preserves most information in the source and target graphs; Hence achieving relatively stable performance. Besides, we observe that the generation time increases almost linear w.r.t. r, which aligns with our complexity analysis of O(Ldrr + Ln²r).
Besides, we study the effect of on balancing the importance of node features and graph structure. We report the average performance on the Airport dataset in Figure G Overall, GADGET is relative robust to different selections with a E (0, 1), under which the FGW distance consider both node features and graph structure. However, when a = 0, i.c., Wasserstein distance considering features only, or a = i.e., GW distance considering structure only, we observe performance degradation. This validates that both features and structure are crucial for the construction of the optimal path.
8
Figure 6: Study on a.
12

---

Published in Transactions on Machine Learning Research (02/2026)
Tins
120.0
nomophily
22.0
attribuee
10.90
degree
50
homopnily
degree
15.01
50 t5.0
3.5
2035
060
265
300
400
560
303
200
300
100
900
166
200
204
000
569
(a) Study on the number of intermediate steps T.
(b) Study on the rank
Figure 5: Hyperparameter Study.
6.6 Path quality Analysis
As Theorem 2 suggests, expect the intermediate graphs lie on the FGW geodesics
Citatio (correlation: 0.98)
1.0
connecting source and target graphs. Following Definition g given any two values A1 E [o, IJ, the FGW distance between the generated graphs is expected to be proportional to the difference between the two values. We evaluate such correlation on the Citation dataset with results shown in Figure
0.0
06
The results suggests that draw (7(o), (()))))())))))))))))))) ((A)))(( (9o. 91) is strongly correlated with AA A with Pearson correlation score of nearly This validates that the generated graphs indeed lie along the FGW geodesics, thereby ensuring the effectiveness of graph GDA.
00-
01
02
23
64
Ra-hul
Figure Path quality.
7 Conclusions
In this paper, we tackle large shifts graphs, and propose GADGET, the first graph gradual domain adaptation framework to gradually adapt from source to target graph along the FGW geodesics. We establish theoretical foundation by deriving an error bound for graph GDA based on the FGW discrepancy, motivated by which, we reveal that the optimal path minimizing the error bound lies on the FGW geodesics. A practical algorithm further proposed to generate graphs on the FGW geodesics, complemented by entropy-base based confidence for pseudo-label denoising, which enhances the self-training paradigm for graph GDA. Extensive experiments demonstrate the effectiveness of GADGET, enhancing various graph DA methods different real-world datasets significantly.
Acknowledgement
This work is supported by NSF (2118329, 2505932, 2537827, and 2416070) and AFOSR (FA9550-24-1-0002)
The content of the information in this document does not necessarily reflect the position the policy of the Government, and no 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.
Broader Impact Statement
This paper presents work whose goal is to advance the field of Graph Machine Learning and Transfer Learning. There are many potential socictal consequences of our work, none of which we foel must be spocifically highlighted here.
GenAl Usage Disclosure
In this manuscript, generative AI tool is used to edit and improve the quality of the text, including checking the spelling, grammar, punctuation and clarity.
13

---

Published in Transactions on Machine Learning Research (02/2026)
References
Samira Abnar, Rianne van den Berg, Golnaz Ghiasi, Mostafa Debghani, Nal Kalchbrenner, and Hanie Sedghi. Gradual domain adaptation in the wild: When intermediate distributions are absent. arXiv preprint arXiv:2106.06055 2021.
Wenxuan Bao, Zhichen Zeng, Zhining Liu, Hanghang Tong, and Jingrui He. Adare: Mitigating graph structure shifts during test-time. arXiv preprint arXiv:2410.068: 06966,, 2024.
Baixu Chen, Junguang Jiang, Ximei Wang, Penglei Wan, Jianmin Wang, and Mingsheng Long. Debiased self- training for cemi-supervised learning. Advances in Newral Information Processing Systems, 35:32424-32432 2022a.
Guanzi Chen, Jiying Zhang, Xi Xiao, and Yang Ti. Graphtta: Test time adaptation graph neural networks. arXiv preprint arXix:2208.000 2022b.
Hong-Yon You Chen and Wei-Lau Chao. Gradual domain adaptation without indexed intermediate domains. Advances in neurol information processing systems, 34:8201 8214, 2021.
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):4908-499) 4922,, 2022.
Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual stochastic block models. Advances in Neural Information Processing Systems, 31, 2018.
Dongqi Fu and Jingrui He. Sdg: A simplified and dynamic graph neural network. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp- 2273 2277, 2021.
Dongqi Fu and Jingrui He. Dppin: A biological repository of dynamic protein-protein interaction network data. In 2022 IEEE International Conference on Big Data (Big Data), pp. 5269 5277. IEEE, 2022.
Yaroslav Ganin, Evgeniya. Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario March, and Victor Lempitsky. Domain-adversariall training of neural networks. Journal of machine learning reseorch, 17(59):1-35, 2016.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2018.
Rui Gong, Wen Li, Yuhua Chen, and Lue Van Gool. Dlow: Domain flow for adaptation and generalization. Proceedings of the IEFE/CVF conference on computer vision and pottern recognition, pp. 2477-2480 2019.
Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. kernel two-sample test. The Journal of Machine Learning Research, 13(1):723- 2012.
Gaoyang Guo, Chaokun Wang, Bencheng Yan, Yunkai Lou, Hao Feng, Junchao Zhu, Jun Chen, Fei He, and Philip Yu. Learning adaptive node embeddings across graphs. IEEE Transactions on Knowledge and Data Engineering, 3566) 6042, 2022.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Xiaotian Han, Zhimeng Jiang, Ninghao Liu, and Xia Hu. G-mixup: Graph data augmentation for graph
classification. In International Conference on Machine Learning, pp. 2230-8248. PMLR, 2022.
Yifei He, Haoxiang Wang, Bo Li, and Han Zhao. Gradual domain adaptation: Theory and algorithms. arXiv preprint Xiv:22300. 13852, 2023.
Dan Hendrycks, Nicholas Carlini, John Schulman, and Jacob Steinhardt. Unsolved problems in ml safety. arxi preprint ar xrx::210001390 13916, 2021.
14

---

Published in Transactions on Machine Learning Research (02/2026)
Norman R Howes. Modern analysis and topology. Springer Science & Business Media, 2012.
Han-Kai Kai Hsu, Chun-Han Yao, Yi-Hsuan Tsai, Wei-Chih Hung, Hung- Yu Tseng, Maneesh Singh, and Ming- Hsuan Yang. Progressive domain adaptation for object detection. In Proceedings of the IEEE/CVF winter conference applications of computer vision, pp- 749-757, 2020.
Wei Jin, Tong Zhao, Jiayuan Ding, Yozen Liu, Jiliang Tang, and Neil Shah. Empowering graph representation learning with test-time graph transformation. arXiv preprint arXiv:2210.0338 03561, 2022.
Wei Jin, Tong Zhao, Jiayuan Ding, Yozen Liu, Jiliang Tang, and Neil Shah. Empowering graph representation lcarning with test-time graph transformation. In The Eleventh International Conference on Learning Represenlations, 2023.
Baoyu Jing, Yuchen Yan, Kaize Ding, Chanyoung Park, Yada Zhu, Huan Liu, and Hanghang Tong. Sterling: Synergistic representation learning on bipartite graphs. In Proceedings of the A AAT Conference on Arlificial Intelligence, volume 38, pp. 12976-12984, 2024.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Soheil Kolouri, Navid Naderializadeh, Gustavo K. Rohde, and Heiko Hoffmann. Wasserstein embodding for graph learning. In International Conference on Learning Representations, 2021.
Ananya Kumar, Tengyu Ma, and Percy Liang. Understanding self-training for gradual domain adaptation. In International conference on machine learning, pp. 1468-5479. PMLR, 2020.
Haoyang Li, Xin Wang, Ziwei Zhang, and Wenwu Zhu. Out-of-distribution generalization on graphs: A survey. Xrv preprint orXiv:2202.00 0779977 2022.
Jundong Li, Xia Hu, Jiliang Tang, and Huan Liu. Unsupervised streaming feature selection in social media. In Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, pp. 1041 1050, 2015.
Zihao Li, Yuyi Ao, and Jingrui He. Sphere: Expressive and interpretable knowledge graph embedding for set retrieval. In Proceedings of the 4 17th International ACM SIGIR Conference on Research and Development Information Retrieval, pp. 2629 2634, 2024a.
Zihao Li, Dongqi Fu, Mengting Ai, and Jingrui He. Apex?: Adaptive and extreme summarization for personalized knowledge graphs. arXiv preprint arXio:2412.11338 2024b.
Mingfu Liang, Xi Liu, Rong Jin, Boyang Liu, Qiuling Suo, Qinghai Zhou, Song Zhou, Laming Chen, Hua Zheng, Zhiyuan Li, et al. External large foundation model: How to efficiently serve trillions of parameters for online ads recommendation. arXiv preprint arXiv:2502. 17494, 2025.
Xiao Lin, Jian Kang, Weilin Cong, and Hanghang Tong. Bemap: Balanced message passing for fair graph neural network. In Learning on Graphs Conference, pp. 37 1. PMLR, 2024a.
Xiao Lin, Mingjic Li, and Yisen Wang. Made: Graph backdoor defense with masked unlcarning. arXiv preprint 2rX:::2411.18645 2024b.
Xiao Lin, Zhining Liu, Dongqi Fu, Ruizhong Qiu, and Hanghang Tong. Backtine: Backdoor attacks on multivariate time series forecasting. Advances in Neural Information Processing Systems, 37:131344-122 131368, 2024c.
Xiao Lin, Zhichen Zeng, Tianxin Wei, Zhining Liu, Hanghang Tong, al. Cats: Mitigating correlation shift. for multivariate time series classification. arXiv preprint arXiv:2004.00 04283, 2025.
Hongrui Liu, Binbin Hu, Xiao Wang, Chuan Shi, Zhiqiang Zhang, and Jun Zhou. Confidence may cheat: Self-training on graph neural networks under distribution shift. In Proceedings of the ACM Web Conference 2022, pp. 1248-122 1258, 2022.
15

---

Published in Transactions on Machine Learning Research (02/2026)
Shikun Liu, Tianchum Li, Yongbin Feng, Nhan Tran, Han Zhao, Qiang Qiu, and Pan Li. Structural re- weighting improves graph domain adaptation. In International Conference on Machine Learning, pp- 21778 21793. PMLR, 2023a.
Shikun Liu, Deyu Zou, Han Zhao, and Pan Li. Pairwise alignment improves graph domain adaptation. arXiv preprint ar Xio:224033.00 01092, 2024a.
Xiaolong Liu, Zhichen Zeng, Xiaoyi Liu, Siyang Yuan, Weinan Song, Mengyue Hang, Yiqun Liu, Chaofci Yang, Donghyun Kim, Yen Chen, et al. A collaborative ensemble framework for ctr prediction. arXiv preprint 111::2411.19706, 2024b.
Zhining Liu, Zhichen Zeng, Ruizhong Qiu, Hyunsik Yoo, David Zhou, Zhe Xu, Yada Zhu, Kommy Welde- mariam, Jingrui He, and Hanghang Tong. Topological augmentation for class-imbalanced node classification. arXiv preprint ar Xiv: 14181, 2023b.
Zhining Liu, Ruizhong Qiu, Zhichen Zeng, Yada Zhu, Hendrik Hamann, and Hanghang Tong. Aim: Attributing, interpreting, mitigating data unfairness. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2014 2025, 2024c.
Xinyu Ma, Xu Chu, Yasha Wang, Yang Lin, Junfeng Zhao, Liantao Ma, and Wenwu Zhu. Fused gromov- wasserstein graph mixup for graph-level classifications. Advances in Neural Information Processing Systems, 36, 2024.
Hermina Petric Maretie, Mireille El Gheche, Giovanni Chierchia, and Pascal Frossard. Got: an optimal transport framework for graph comparison. Advances in Neural Information Processing Systems, 32, 2019.
Facundo Mémoli.
distances and the metric approach to object matching. Foundations of Computational Mathematics, 11:417 487, 2011.
Gabriel Peyré, Marco Cuturi, and Justin Solomon. Gromov-wassorstein averaging of kernel and distance matrices. In International Conference on Machine Learning, pp. 2664 2672. PMLR, 2016.
Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport: With applications to data science. Foundalions and Trends& in Machine Learning, (5-6))):355 607, 2019.
Ruizhong Qiu, Dingsu Wang, Lei Ying, H Vincent Poor, Yifang Zhang, and Hanghang Tong. Reconstructing graph diffusion history from single snapshot. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1978 1988, 2023.
Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel R Figuciredo. struc2vec: Learning node representations from structural identity. In Proceedings of the 23rd ACM SIGKDD internalional conference on knowledge discovery and data mining, pp. 385-394, 2017.
Shogo Sagawa and Hideitsu Hino. Gradual domain adaptation via normalizing flows. arXio preprinl Xiv: 21..2222..1499 11492, 2022.
Meyer Scetbon, Marco Cuturi, and Gabriel Peyré. Low-rank sinkhorn factorization. In International Conference on Machine Learning, pp. 9344 9354. PMLR, 2021.
Meyer Scetbon, Gabriel Poyré, and Marco Cuturi. Lincar-time gromov wasserstein distances using low rank couplings and costs. In International Conference on Machine Learning, pp. 19347 19365. PMLR, 2022.
Xiao Shen, Quanyu Dai, Fu-lai Chung, Wei Lu, and Kup-Sze Choi. Adversarial deep network embedding for neoss- node classification. In Proceedings of the AAAT conference on artificial intelligence, volume 34, pp. 2991-2999, 2020.
Boshen Shi, Yongqing Wang. Fangda Guo, Jiangli Shao, Huawei Shen, and Xueqi Cheng. Improving graph domain adaptation with network hicrarchy. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pp. 2249 2258, 2023a.
16

---

Published in Transactions on Machine Learning Research (02/2026)
Boshen Shi, Yongqing Wang, Fangda Guo, Jiangli Shao, Huawei Shen, and Xueqi Cheng. Opengda: Graph domain adaptation benchmark for cross-network learning. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pp. 5396 5400, 2023b.
Boshen Shi, Yongqing Wang, Fangda Guo, Bingbing Xu, Huawei Shen, and Xueqi Cheng. Graph domain adaptation: Challenges, progress and prospects. ar preprint arXiv:2402.0090, 2024.
Karl-Thcodor Sturm. The space of spaces: curvature bounds and gradient flows on the space of metric measure spaces. arXie preprint arXiv: 1.X8::200.000 208.0434, 2012.
Yongduo Sui, Qitian Wu, Jiancan Wu, Qing Cui, Longfei Li, Jun Zhou, Xiang Wang, and Xiangnan He. Unleashing the power of graph data augmentation on covariate distribution shift. Advances in Newral Information Processing Systems, 36:18109 18131, 2023.
Baochen Sun, Jiashi Feng, and Kate Sacnko. Return of frustratingly easy domain adaptation. In Proceedings of the AAAI conference on artificial intelligence, volume 30, 2016.
Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. Arnetminer: extraction and mining of academic social networks. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pp.
2008.
Vayer Titouan, Nicolas Courty, Romain Tavenard, and Rémi Flamary. Optimal transport for structured data with application on graphs. In International Conference on Machine Learning, pp. 6275 6284. PMLR, 2019.
Titouan Vayer, Lactitia Chapel, Rémi Flamary, Romain Tavenard, and Nicolas Courty, Fused gromov- wasserstein distance for structured objects. Algorithmss, 13(9):212, 2020.
Petar Velickovie, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, Yoshua Bengio, et al. Graph attention networks. stat, (1550(0):10-48560)) 2017.
Cédric Vincent-Cuss Titouan Vayer, Rémi Flamary, Marco Corneli, and Nicolas Courty, Online graph dictionary learning. In International conference on machine learning, pp. 10564-10574. PMLR, 2021.
Botao Wang, Jia Li, Yang Liu, Jiashun Cheng, Yu Rong, Wenjia Wang, and Fugee Tsung. Deep insights into noisy pseudo labeling on graph data. Advances in Neural Information Processing Systems, 36, 2024.
Dingsu Wang, Yuchen Yan, Ruizhong Qiu, Yada Zhu, Kaiyu Guan, Andrew Margenol, and Hanghang Tong. Networked time series imputation via position-aware graph enhanced variational autoencoders. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp.
2256 2268, 2023.
Haoxiang Wang, Bo Li, and Han Zhao. Understanding gradual domain adaptation: Improved analysis, optimal path and beyond. In International Conference on Machine Learning, pp. 2022.
PMLR,
Tianxin Wei, Ziwei WU, Ruirui Li, Ziniu Hu, Fuli Feng, Xiangnan He, Yizhon Sun, and Wei Wang. Fast adaptation for cold-start collaborative filtering with meta-learning. In 2020 IEEE International Conference on Data Mining (ICDM), pp- 661-670 IEEE, 2020.
Jun Wu, Jingrui He, and Elizabeth Ainsworth. Non-iid transfer learning on graphs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 10342- 10342-10350, 2023.
Man Wu, Shirui Pan, Chuan Zhou, Xiaojun Chang, and Xingquan Zhu. Unsupervised domain adaptive graph convolutional networks. In Proceedings of the web conference 2020, pp. 1457-1467, 2020.
Man Wu, Xin Zheng, Qin Zhang, Xiao Shen, Xiong Luo, Xingquan Zhu, and Shirui Pan. Graph lcarning under distribution shifts: A comprehensive survey on domain adaptation, out-of-distribution, and continual learning. ar Xii preprint arXiv:2402 16374, 2024.
17

---

Published in Transactions on Machine Learning Research (02/2026)
Haobo Xu, Yuchen Yan, Dingsu Wang, Zhe Xu, Zhichen Zeng, Tarek F Abdelzaher, Jiawei Han, and Hanghang Tong. Slog: An inductive spectral graph neural network beyond polynomial filter. In Forty-first International Conference on Machine Learning, 2024a.
Hongteng Xu, Dixin Luo, and Lawrence Carin. Scalable gromov-wassersten learning for graph partitioning and matching. Advances in Neural Information Processing Systems, 32, 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2018.
Zhe Xu, Ruizhong Qiu, Yuzhong Chen, Huiyuan Chen, Xiran Fan, Menghai Pan, Zhichen Zeng, Mahashweta Das, and Hanghang Tong. Discrete-state continuous-time diffuusion for graph generation. or XrXie preprinl arXiv:2405.110 11416, 2024b.
Yuchen Yan, Qinghai Zhou, Jinning Li, Tarek Abdelzaher, and Hanghang Tong, Dissecting cross-layer depen- dency inference on multi-layered inter-dependent networks. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, pp. 2341-2333 2022.
Yuchen Yan, Yuzhong Chen, Huiyuan Chen, Minghua Xu, Mahashweta Das, Hao Yang, and Hanghang Tong. From trainable negative depth to edge heterophily in graphs. Advances in Neural Information Processing Systems, 36:70162 70178, 2023.
Yuchen Yan, Yuzhong Chen, Huiyuan Chen, Xiaoting Li, Zhe Xu, Zhichen Zeng, Lihui Liu, Zhining Liu, and Hanghang Tong. Thegen: Temporal heterophilic graph convolutional network. arXio preprint 241.24412.66..5 2024a.
Yuchen Yan, Yongyi Hu, Qinghai Zhou, Lihui Liu, Zhichen Zeng, Yuzhong Chen, Menghai Pan, Huiyuan Chen, Mahashweta Das, and Hanghang Tong. Pacer: Network embedding from positional to structural. In Proceedings of the ACM on Web Conference 2024, pp. 2485-2496 2024b.
Yuchen Yan, Baoyu Jing, Lihui Liu, Ruijie Wang, Jinning Li, Tarck Abdelzaher, and Hanghang Tong. Reconciling competing sampling strategies of network embedding. Advonces in Neural Information Processing Systems, 36, 2024c.
Hyunsik Yoo, Zhichen Zeng, Jian Kang, Zhining Liu, David Zhou, Fei Wang, Eunice Chan, and Hanghang Tong. Ensuring uidr-side fairness in dynamic recommender systems. arXie preprint arXiv:2308. 15651, 2023.
Yuning You, Tianlong Chen, Zhangyang Wang, and Yang Shen. Graph domain adaptation via theory- grounded spectral regularization. In The eleventh international conference on learning representations, 2023.
Qi Yu, Zhichen Zeng, Yuchen Yan, Zhining Liu, Baoyu Jing, Ruizhong Qiu, Ariful Azad, and Hanghang Tong, Planetalign: A comprehensive python library for benchmarking network alignment. arXiv preprint ar Xrx:22505. 2166666 2025a.
Qi Yu, Zhichen Zeng, Yuchen Yan, Lei Ying, Srikant, and Hanghang Tong. Joint optimal transport and embedding for network alignment. In Proceedings of the ACM on Web Conference 2025, pp. 2064 2075, 2025b.
Zhichen Zeng, Si Zhang, Yinglong Xia, and Hanghang Tong. Parrot: Position-aware regularized optimal transport for network alignment. In Proceedings of the ACM Web Conference 2023, pp.
2023a.
Zhichen Zeng, Ruike Zhu, Yinglong Xia, Hanqing Zeng, and Hanghang Tong. Generative graph dictionary learning. In International Conference on Machine Learning, pp. 40749-40769. PMLR, 2023b.
Zhichen Zeng, Boxin Du, Si Zhang, Yinglong Xia, Zhining Liu, and Hanghang Tong. Hicrarchical multi- marginal optimal transport for network alignment. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 16660-1666) 2024a.
18

---

Published in Transactions on Machine Learning Research (02/2026)
Zhichen Zeng, Xiaolong Liu, Mengyue Hang, Xiaoyi Liu, Qinghai Zhou, Chaofei Yang, Yiqun Liu, Yichen Ruan, Laming Chen, Yuxin Chen, et al. Interformer: Towards effective heterogeneous interaction learning for click thik-th rate prediction. orXiv preprint (rXic:2411.09852, 2024b.
Zhichen Zeng, Ruizhong Qiu, Zhe Xu, Zhining Liu, Yuchen Yan, Tianxin Wei, Lei Ying, Jingrui He, and Hanghang Tong. Graph mixup on approximate gromov-waserstecn geodesics. In Forty-first International Conference on Machine Learning, 2024c.
Zhichen Zeng, Mengyue Hang, Xiaolong Liu, Xiaoyi Liu, Xiao Lin, Ruizhong Qiu, Tianxin Wei, Zhining Liu, Siyang Yuan, Chaofei Yang, et al. Hierarchical lora moe for efficient ctr model scaling. or Xiv preprinl arXiv:2510.10433 2025a.
Zhichen Zeng, Qi Yu, Xiao Lin, Ruizhong Qiu, Xuying Ning, Tianxin Wei, Yuchen Yan, Jingrui He, and Hanghang Tong. Harnessing consistency for robust test-time Ilm ensemble. ai preprint arXiv.2510.1855 2025b.
Zhichen Zeng, Wenxuan Bao, Xiao Lin, Ruizhong Qiu, Tianxin Wei, Xuying Ning, Yuchen Yan, Chen Luo, Monica Xiao Cheng, Jingrui He, et al. Subspace alignment for languu- model test-time adaptation. Xixiv preprint arx::2200.008 001199 2026.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in neural information processing systems, 31, 2018.
Yuchen Zhang, Tianle Liu, Mingsheng Long, and Michael Jordan. Bridging theory and algorithm for domain adaptation. In International conference machine learning, pp. 7404 7413. PMLR, 2019.
Lecheng Zheng, Baoyu Jing, Zihao Li, Zhichen Zeng, Tianxin Wei, Mengting Ai, Xinrui He, Lihui Liu, Dongqi Fu, Jiaxuan You, et al. Pyg-ssl: A graph self-supervised learning toolkit. arXiv preprint 1rX.v2441.221151, 2024.
Qinghai Zhou, Yuzhong Chen, Zhe Xu, Yuhang Wu, Menghai Pan, Mahashweta Das, Hao Yang, and Hanghang Tong. Graph anomaly detection with adaptive node mixup. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, pp. 3494-3504, 2024.
Qi Zhu, Carl Yang, Yidan Xu, Haonan Wang, Chao Zhang, and Jiawei Han. Transfer learning of graph neural networks with ego-graph information maximization. Advances in Neural Information Processing Systems, 34:1766-1777 2021.
Zhan Zhuang, Yu Zhang, and Ying Wei. Gradual domain adaptation via gradient flow. In The Twelfth International Conference on Learning Representations, 2024.
19

---

Published in Transactions on Machine Learning Research (02/2026)
Appendix
Contents
A Proof
21
A.1
Proof for Hölder Continuity
21
2.2
Proof for Error Bound
24
A.3 Proof for Optimal Path
26
Proof for practical error bound
28
B Al Algorithm
30
C
Additional Experiments
30
C.1
Experiment Result Statistics
................................
30
C.2
Computation Complexity Analysis
31
C.3
Intermediate graphs
31
Psendo-label confidence
31
Reproducibility
32
Dalasels
D.2 Pipeline
33
E More Related Works
34
F Limitations and Future Directions
35
20

---

Published in Transactions on Machine Learning Research (02/2026)
A Proof
In this section, we provide detailed proof for all the Lemmas and Theorems. We first prove the Hölder contimuity in Section
A.1 [Lemmna
I) then we prove the error bounds for node-level, edge-level and graph-level
tasks in Scction A.2 (Thoorem Finally, we prove the optimality of the FGW geodesic for graph GDA
Section
A.3
Theorems
2 and
A.1 Proof for Hölder Continuity
Lemma (Hölder continuity). For any L-layer node-level GNN fn Ol-Lo") edge-level GNN @o Ol and graph-level GNN fg =ro Oi=Lgh) where Ol=Lgh) glul o... o g(t)) and g are GNN layers in equation
Given source graph Go and target graph G1, have:
(((f E(f,9t) C. CWw.C.ooWwa..... L (1).
where
a (1-11 (C
B = a (C)))) 1-1 C.Clin)
a + (1 - aC).0mm -
(C.Cin(1 -CCCn-
Cgnn
C.Clin
1 1- C.Clin a)
Ow, Cguns for node-level tasks
20w, CoCgan: for edge-level tasks
Ow, C.Cgun, for graph-level tasks
Proof. We start with the node-level tasks based on Assumptions and 2 Given two graphs Go = (Vo, Ao, Xo), 91 = (V1, ,,,x), corresponding graph g()) (V, A,A,X" x Let the marginal constraints be μ4 = Uni(([Vo)), ir Unif([V)))
X1). We denote the 1-th layer embedding as X (() o...o o (G) with
for any coupling E 11( 11), have
EEF, E(f.
Σ Xo(())))
Σ (eG(L((v)))
Vol NEVO
[Vil
DE
Σ Mo(u)e(J, (Ao(u, u'), NeVa
Σ (A Xi(e') NE
(16)
B (e(f, (Ao u') - (A) x (('))
(((f. -
(Ao (u, u²) Xo ( -(f. X1 (1))
o Ow (90) ((9)) (equation 6
Now consider the (-th layer GNN f() ReLU Linear g(), with input graph ((I-1), For ReLU activation, given two inputs Xo. X,, it is casy to show that
[[ReLU(X.) ReLU(X))]xx S Xo X xil
(17)
For linear layer Linear(æ) = Wæ + b, given two inputs Xo, X1, we can show that
[inearr (Xo) - Linear Linear(Xi)llx
< W|] X Xilxx
(18)
< Cti X X1 1
Assumption B
21

---

Published in Transactions on Machine Learning Research (02/2026)
Combining equation 17 and equation 18
for any coupling π [[ M1), we have
||ReLU o Linear o (0'-1) - ReLU o Linear g0) (g
"halll (G 900
- (0("
Sin (N (Ngn-n(u). Nou-u(())
Assumption A
(19)
-C Cii inf Bi ( yur alAoou, A1,,, (10 (v)) - x x (0')11
TEll(po(m)
SC..OinB(u',ee
|alAolu, - Ai Al( (1-a))x - x 11 (0 (r))1
=CeClin (cB(u,,))<<AA((u,
(()=)/))00(0)))00000000)0 ) y (و
By repeatedly applying equation 19 to equation
16
we have:
S Ow (
= =B (15(() (g( - -(1)
aB (u.u)mm AAo(u, Ai + (1- -1- 11 (( (equation 19 (ow
< Cww. C.Chin
Sww, C.Crn
ICc,0mal1 - w)l'E (u.s)am (Aolu,')) - Al(v, (C.C - a) (n (( (x)) (w
1=0
=Ca [B (n.0lom (al )our
Aulu,, Al(v,6'11 -1-3) - (x(1)
inf SC, (1)l(
BE (u.eiam (Ao(u,''-AAlle - (x -x(())1 (w
-adloowe (g) g(())
(20)
where B, On are defined as
(C-((CCuu(1-a)))) B = (1 CCC
a
Cn = Cw, C.O
1- (-CCmil1-aa)
To this point, we prove the node-level loss & is Hölder continuous w.r.t. the B-FGW distance.
22

---

Published in Transactions on Machine Learning Research (02/2026)
We can derive a similar proof for edge-level tasks. Let the marginal constraints be Mi Unif((Vol), un Uni(((D))), for any coupling E [T(o0, M1), we have
Ise, 90) - (e(ee
Σ ce (fe(9)))(w)))) 1212 V,
Σ ce (fe((())))))))
u,W'EVo
=B ce (fe(9))(u,w)) Eugormee Ee (fe(91)
<B(,,)) (fe(9))
SOw. B(n,)) fe (90) (u,a²) - (1,0)) (equation 7
-Ww. [(u,,), 0 f, (9)) ).. fn (90) (.
SCw.Co Co ((u,)) fn (90) fn (91))ll1 + (S0) - -n(())) (1xe) Assumption E.
(9) )) -y0² (1 >0l13 + (1 (g( ),-- 101
-Cw. Co Blu,,),
=2Cw. Ce B( 1g (1) (g) (1- 1) -gg 9dh (
Similar Lemma ! we can leverage equation 19 and equation 20
derive the following inequality
(fee,, 90) Ee(fe,9i)
-2ww. Co Elu,))~ (g (00 )ol
S2Cw.CoC.Cms CoC dw (Ngge-u(u), Ng:c-1(()))
Assumption A
SCo
[E (oru)am jalie
+(1 Ao(u, u() - A1(1, + (1- - (a, [Xo(u) - (1))1
<C.
inf =ETT(H.-11))
BE
(oLv)~ (Al(u, - Ailu,, 0')8 + -11 (1- 3)BB(u.)) Xo(w) - X (v)l
-C.
(g( (
where B, C. are defined as
B a (1
a))² C. CC2CCw,CC C.C.C.C.m a (1- -L) (C.Cim a))* 1 C.CCnnl
To this point, we prove the edge-level loss & is Hölder continuous w.r.t. the 3-FGW distance. Finally, we prove for graph-level lasks
(J, 90) - [c((G, G1) Ow, (I5)(G)) fo(9))133
23

---

Published in Transactions on Machine Learning Research (02/2026)
Similar to the proof for Lemma 1 can leverage equation 19 to derive the following inequality
15 (g: Go)
Eo(oo: G1)l
Ow, (lfg((9) (
= Ow, Ir f(9o) ro f(gi)llx
I Ow, C. ((
- f(G))) Assumption F)
Ow, C. -eu,,)a ( (16 (1
Dollx Dollxx
S Ow, C.C.Chin dw (Ng Nogu-
Assumption A
S Cg
AAlu, 1.) A1(u, r')1 + (1 () | (o(u)) - (1(1))1
S Cg Hell(po.ma))
inf
BE
(u.0)aw AAb(u, Ae(v, + (11- -3) (oo(u)) x1(0) (slia
C. ((0))
where B, Cg are defined as
(11 (L1-(CCCn((1-
8 = a (1 (t (CcClll- a))
Cg Cg= Cw, C,C. a + (1- am --) (CCCm(11-))
C-Coin(1-a
To this point, we prove the graph-level loss Eg Hölder continuous w.r.t. the 3-FGW distance.
A.2 Proof for Error Bound
Theorem 1 (Error bound). Let fo denote the source model trained on the source graph Ho = Go- Suppose there are T 1 intermediate stages where in the t-th stage (for = 1,2,.... T) we adapt fi-1 to graph He to obtain an adapted ft. If every adaptation step achieves I - fe(H)) lly I 5 on the corresponding graph He, then the final error E(JT, HT) on largel graph Hr = 91 is upper bounded by
E(fr, C 8T C. Σ
(Fow...HHep Hi).
t=1
where C+= = Ct, for node-level task, Ct Ct, for edge-level tasks, and C Ci, for graph-level tasks.
Proof. For any intermediale stage = 1,2, v.. T, we first consider node-level loss En:
(n(mm- Hi) - En He)1
1
G I (u))
Σ
[
NEV.
KE
1
C (e, - en (n,
WEV.
1
Σ Ct [|5mm (Nv, - fra (Nvr (w))
Assumption C
(21)
VVl
WEV.
Ct. MV
[| (Hi)) - Snn (HWullla
uEV.
-Ct [| (Hi, - fn. (Hi))l
S Ct, 5
24

---

Published in Transactions on Machine Learning Research (02/2026)
Similarly, for edge-level loss Se, have:
(f Hi) EolSec Hi))
1
Σ
Celfer
Σ "EV.
celfer (He))anr))
D.12 a.''EV
[
Σ
ce "e(Ser- (He))a()))) Σ
celSer (Hi)
NEV.
(22)
Σ NEV.
Cr ||feer- (He) fee (He))
Assumption C
Cr. [2/1 WEV.
[| (He)(a,a)) - fer (ww)lll
= Cr. ||fer.. (HH)) - (Heolla..
I Cr. .
Similarly, for graph-level loss Egp we have:
(fo He) (4))-f((ee Ho)l S Ct (1lfe-((H)))) - Sa, (H+))l
Assumption C
(23)
S Ct 5
For simplicity, we slightly abuse C₁ as a general notation for Ct. Cr. Ct. and abuse f as a general notation for Ses fg. Therefore, equation equation 22 and equation 23 can be uniformly written as
15(f Hd) E(fi, Ho) s 8
(24)
Based on equation 24 and Lemma 1 we have
1 H+-1) E(fe, Hc)l
$ 1(f(-1, H+-1) - E(fe, H4-1)) + (E(f,, H4-1) E(fe, H.)l
C 8 CC ..braw:ggs (1 Hi)
(74-1;;,
Therefore, we have:
E(fr,9) = E(frr,
Ho) + (E(TT, H7) - E(Jo, Ho)l
Ho) +
(E(J-11, H.) - E(S,, H.))
S {((fo, Ho) + Σ
16(f-11, Ho) -Eft,7H))
{((fo, Ho) + Σ
(G. 1 + C.. Ha))
T
= =(fo, + G. 8T + C Σ
da &ow,,, (H1-11 He)
E(fo.o) + C. 8T + + Σ
deow (H: (H,-1, Hi)
25

---

Published in Transactions on Machine Learning Research (02/2026)
A.3 Proof for Optimal Path
Theorem 2 (Optimal path). Given source graph Go and target graph 91, let y: 1 be FGW geodesic connecting Go and 91. Then the error bound in Theorem attains its minimum when intermediate
graphs are He = )),,,, Vt = 0, l...... T, where we have:
C. doo.n. 91)
E(T,,)) S 90) CF OT +
T4-1
Proof. Note that for any intermediate graphs Hi...., HT-1, by Jensen's inequality of the convex function + |2|" and the triangle inequality of deGw, we have:
d a 1 1Hz-1, Hi)
Σ (Ho =T) _
(He-1,
drow: (He-1, Hc)
T
T
Σ de draw:g. (He (1
T4-1
FGW HH Hc)
T4-1
When the intermediate graphs H4, Vt 1,2,..., T are on the FGW geodesies, i.e., He y (+), by the geodesic property in Definition we have
(t-1
g (H--1, H4)
dFGW
T
1 1
l
drow:y (7(0), 71))
T
drow: (9o, 91)
T
Therefore, we have
T
E(fr,9)) s {(fo. + Ct. 8T + C E
di PBow,,,((l-11 He)
T
= 90) + Cr, +T + + Σ
ddow.. G1)
1=1
C C. 91)
E(fo. + Ct, 8T +
T4-1
which realize the lower bound. Therefore, the geodesic y gives the optimal path for graph GDA.
Theorem 3 (FGW geodesic). Given source graph Go and target graph G1, the transformed graphs Go, 91 are in the FGW equivalent class of Go, 91, i.e,, [ = [Go]. [9.] = [9]]- Besides that, the intermediate graphs H4, = 0, I,.,," T, generated by equation 13 are on an FGW geodesic connecting Go and Gr.
Proof. Given a source graph Go = (Vo, Ao, X,) and a target graph G = (V1, X1), as well as their probability measures μı, μ2, we obtain the optimal FGW matching S based on equation [
We first show that the transformed graphs Go. فJ from equation 12 are in the FGW equivalent classes of Go G1, respectively. The transformed graphs the product space of Go and G1, and write out.
26

---

Published in Transactions on Machine Learning Research (02/2026)
the FGW distance between Gu and Go follows
dGo Go) min (1 a ( (I, y)) aB (u.eaa AAu(, Au(( v), (/11 sell(mm-pt) Consider a the following naive coupling satisfying the marginal constraint S E Ll( (oo)
(o(u)
Mil fu=r
Su, (z,
(25)
0, else
the FGW distance deo Go) with optimal coupling S* upper bounded by co. (So) as follows
foo (Go. 30)
= (1 -- M(u, (I. + a. ()) (ul (02"--""
Ao(u, Ao(( v), (a', 1)1
(1 (u..)))) X(u)- [)((((
aE (x.))))))-
Ao(u,u) Σ (c.
(w (1'"""1)"))"
ie
1c SEVi
(1 a) (( [((u) X (x))l +aB (1(4))))
Aol(, nl))
A0(z, (equation 12
$ (1 a =.. ((u) x(u]]" aB (000000
Ao(u,u') Au(u, (equation 25
=0
Due to the uon-negativity property of the FGW distance Vayer et al. (020)) we prove that dFow(Go, Gn) = 0, i.., Go G.. Similarly, we can show that G1 91
Afterwards, we prove that the interpolation in equation 12 and equation 13 generate intermediate graphs
the FGW geodesics. According to Vayer et al. (2020), the FGW geodesics connecting Go and Gi is graph in the product space g = (Vo @ V1, A. satisfying the following property:
& (V+. A A x)
V Vo & V1
A (4((,, v), (v(,
(1-11 Aolu,u') _ Ai Yu,u' Vo, e eM
(26)
where
x+((u,))) (1-7) t Xo(u) t T x1(1)) Vo
Following the transformation equation] 12 for nodes u, w E Vo and u, E Vi, we can rewrite the transformed adjacency matrix Ås and attribute matrix Xo as follows
Àn((u, v), (1),
Σ
Po (u, Ao (vl, = Ao(u, u²)
VEVo.EE
Xo((u,v)) Σ
Poli, (u, Xo(i) Xo(u)
iEVo
Therefore, the intermediate graph H4 in equation
13 can be expresserd by:
H4 = (V+, A X+)
144 = Vo V1
(x'')')) = (1 -11-)
À A (x,,,,,
7 Ao(u, w') + A10,0)
where
x {4((wv)) = (1 (1- t - Xo(u)= + + (w)
27

---

Published in Transactions on Machine Learning Research (02/2026)
Now, consider naive 'diagonal' coupling T4, between Hei He, follows
u(, if u = u' and v = o'
The ((u, u) (u', v)) 0, else
Afterwards, the FGW distance between He, and Hi, should be less or equal to the FGW distance under the 'diaonall' coupling, that is:
dFow(He, Hea)
Σ
[11 (1-a)] a)) aa)aaXXl0 (x()= Xx (u'' + ox. IA (u, - Ag (u', (q(",, w')] Tes (u) (())
8,0,8,
Σ 16,21
(1 [ (u) X (w] + a |A (u, A
(u, T(
According to equation 26 we have
x (u) (u) (u) [1 Xo(u) $ Xi()) (1 (1-
1/ [x((u) [1=()x
t2 Xz(u)
-1 1
(o(u))X((u))
T
T
Ag (u, 0) A (u, u) = (1 -
4 Ao(u, +/2 (u, - (1 - A2 0)
t2 A2(u, v)
t1 - tu
|Ao(u, 2)) A (1(
Combine the above two equations, we have
drow (Hr, H4a)
12
1(11-a)x4p
X1(1)) a (Ao(u,) v) A2(u, (1),
T
(27)
by
drawwGGo, Gi)
T
The above inequality holds for any 0 5
4 S 4 1. In particular, we have
4
4 Arow(Gor 91) "T drooowGoo (Go, 91)
draw(Go, He,)
0
T
11
l2
1/2 - 4 T
dFe, Hip) x
drow
drow 91)
T
T
t2
t2
draw(Hleg 91)
<
(Go 91) = ddrw 91)
T
Finally, by the triangle inequality of FGW distance
Vayer et al. 2020
have
t _ drow 91) + t2 - t1 drow(Go, 91) + (1 ddrow (9o, 91) = draw 91) T
to
draw (1) &
T
Hence, the < in this inequality is actually in particular, dFow(He,) H42) 14 (drow 91). Therefore, prove that the intermediate graphs H, generated by equation 13 the FGW geodesics connecting Go and G1.
A.4 Proof for practical error bound
Theorem 4 (Practical crror bound). For sequence of intermediate graphs Ho...., Hr on the approzimated FGW geodesics generaled by GADGET, performing GDA along the path yield a fonal error E(Sr, Hr) on largel graph Hy = G. upper bounded by
T
((JT,I) < Original bound + 4C8 4C8 draw(H,, He-1) + 40 apprenn
28

---

Published in Transactions on Machine Learning Research (02/2026)
where original bound is the upper bound the eract geodesics provided in Theorem and Ōapproz max, drow(H,, H₂) is the maximum approcimation error between eaact geodesic graph Hr. and low-rank approzimated graph He.
Proof. Let H. be the graph on the exact geodesic and H. be the graph on the approximate path with rank-r. We use P to denote the optimal coupling and P to denote the approximated low-rank coupling. We denote Ap = P - Pllp. We denote δapprox = max, deGw (H,, Ha) as the maximum approximation error between the exact geodesic graph He (full-rank) and approximated geodesic graph He.
First, we bound the approximation gap Oapprox- When considering naive identity coupling (i.e., the i-th node in He align with the i-th node in H4) between H4 and He. it induces upper bound of the FGW distance as
&ow (H., Ho) S (1- a) X + aal A
According to the transformation in Eq. 13 feature error at step t can be written as
|X, X.IF= (I(1 ) Xo + [ - P S (1 ) Xoll+ - |
Similarly, the structure error at step t can be written as
|A AellF [1(1 t
(P P. - ( -(A.P)))
(1 + | Po
Pb) + (Po Po) L - PIAIPI
S (1 7 ) A Pol| Pol(=) - || (|BII))
Therefore, the approximation error can be bounded by
&eow H., Ho) S |111001(((00000000//////11111110
Afterwards, we analyze the impact of the approximation error on the error bound. We first apply the triangle inequality on the FGW distance as
draw Hl+t)) & draw(H, H4) + draw(H, He-1) + ddw.w(H.. Het1)
Therefore, the error bound in Theorem can be written as
fifT, Go) S Original bound + 406 dHo He+1) + 4CT82
Spprox
approx
Note that when [il[/a], i.e., full rank, have Ap. - 0, i..., | A.ll + - 0. Therefore, we have Óapprox mar,drow (H,, Hi) 0 where approximation errors are eliminated.
X111r
3
29

---

Published in Transactions on Machine Learning Research (02/2026)
B Algorithm
We first provide the detailed algorithm of the proposed GADGET in Algorithm ! which generates the path for graph GDA.
Algorithm GADGET
1:
Input source graph Gn = (Vo, Ag, Xo), target graph 91 = (V1, A1, X1), number of stages T, marginals Po: P1, rank r, step size 7, lower bound a, error threshold 5.
2: Initialize transformation matrices gd)) E Ar, (0) E 1( g), º E [[,,,)) g):
3: Compute attribute distance matrix (u, v) = [oo(u) - (1) Vu E Vo. V1:
for t 0, 1,.. do
((t) a-aM +4(1 a:) 4 diag(1 ( (g)
A
BBO 1 ( diag(1/g ① 0
1 exp
BBO' o 10 diag(1 (1/ /g)))
Q!"
a exp
E3 exp
-ddiag Q e
B
/g (1))
Og "g
Q (++1)
(
g (++)) LR-Dykstraf E1. E2. Ea, Mn, M4, a, 8) Scetbon et al. 2021
10: end for
11: Normalize transformation matrices Po (gdiag(1/g)) P1 Qidiag 1/g);
12: Compute transformed adjacency matrices Ao Pj Ao Po. A PT A
13: Compute transformed attribute matrices Xo = Po X1 = PP'
14: Compute transformed marginals ño = Po No: fi = Pi M1;
15: Generate intermediate graphs :4:= (Vo V1, Ao + År, (L x) (x1 .t Vt= 1,2,
16: return path H (Ho, Hi,..., HT)
After obtaining the path by Algorithm we can perform self-training along the path for GDA. The detailed algorithm is provided in Algorithm 2
Algorithm Graph gradual domain adaptation
1: Input source graph Go (Vo, Ao, Xo), source node label Yo, target graph 91 (Vi, A1, X1), number of stages T;
2: Generate path 71 = (Hu, .I.... for graph GDA by GADGET in Algorithm Set initial confidence score conf, = Unil([Vol)
for t= 0, 1..,,
do Train and adapt GNN model f. by arg min,, E(He, He+1, Ye41, conf:);
Obtain pseudo-labels by Y(+1 feH441));
7: Compute confidence score conf441 on Het1 by Eq. equation 15
8: end for
9:
return larget GNN model ST.
C Additional Experiments
We provide additional experiments and analysis to better understand the proposed GADGET.
C.1 Experiment Result Statistics
We We provide more statistics on the benchmark results in Figure 2 and the statistics are shown in Table I
report the Average Maximum and Minimum improvement of GADGET on direct adaptation with different DA methods and backbone GNNs. We also report the percentage of cases where GADGET outperforms (Positive) or underperforms (Negative) direct adaptation. is shown that GADGET achieves positive average improvement all datasets, with impressive maximum improvements of at least 9.83%. For cases where
30

---

Published in Transactions on Machine Learning Research (02/2026)
Table Statistics on experiment results. All number are reported in percentage (%).
Dataset
Average
Max
Min
Positive
Negative
Airport
6.77
26.30
-1.75
94.40
5.56
Social
3.58
15.00
-2.51
91.57
8.33
Citation
3.43
9.83
-1.81
91.57
8.33
CSBM
36.51
48.00
16.67
100.0
0.00
GADGET fails, it still achieves comparable results with at most 2.51% degradation. However, as the columns Positive and Negative show, GADGET outperforms direct DA in over 90% cases, with only less than 9% cases with negative transfer.
C.2 Computation Complexity Analysis
We analyze the time complexity of GADGET. Suppose we have source and target graphs with ((n) nodes, node feature dimension of d, and low-rank OT rank of r. The time complexity for path generation is O Ln?r), where L is the number of iterations in the low-rank OT algorithm in Algorithm Besides, gradual GDA involves repeated training along the path, additional (TTaia)))) complexity is needed, where O(trrain) is the time complexity for training a GNN model. Therefore, the overall training complexity is O(Lndr + Ln²r + Thraii,, which is linear w.r.t. the feature dimension d and the number of steps T, and quadratic w.r.t. the number of nodes n.
Run Time Analysis
200
*-
rank=0,255
rank-0.50n
rank-0.755
Run time (s)
rank=1.00m
x
10
2000
4000
6000
8000
10000
Number of nodes
We also carry out experiments analyze the run time w.r.t. the number of nodes with different ranks and the result is shown in Figure S It is shown that GADGET scales relatively well w..t. the number of nodes, exhibiting a sublinear scaling of lig(time) w.r.t. the number of nodes. Moreover, the computation can further accelerated by reducing the rank. When reduced from full-rank (1.00n) to low-rank (0.25m), the run time can be reducod from 175 seconds to 30 seconds on graphs with 10,000 nodes.
Figure 8: Run time analysis w.r.t. graph size. The y-axis is in the log scale.
C.3 Intermediate graphs.
We provide visualization results to understand the proposed graph GDA process, where the intermediate graphs between a 3-block graph and 2-block graph are shown in Figure We observe a smooth transition from 3-block graph to 2-block graph with small shifts between two consocutive graphs.
Figure 9: Visualization of the intermediate graphs.
C.4 Pseudo-label confidence
To understand how entropy-basod confidence facilitates self-training, we visualize the embedding spaces learned with and without entropy- confidence, and the results are shown in Figure 10 It is shown that noisy pseudo-labels near the decision boundary assigned with lower confidence, contributing less
31

---

Published in Transactions on Machine Learning Research (02/2020)
Geogel
GeMauu
Aisort
Socia
claton
Datavat
(a) embedding w/o confidence
(b) embedding w/ confidence
performance comparison
Figure 10: Evaluation on pscudo-label quality. Larger marker size indicate more confident pscudo-label. (a) Embedding space w/o confidence; (b) Embedding space w/ confidence. (c) Performance comparison: we evaluate graph GDA guided by different paths w/ (hatched bars) and w/o (colored bars) confidence scores.
to self-training. In addition, we observe that the embedding space trained with confidence better separates different classes in the target domain, hence achieving better performance. Besides, we also quantitatively evaluate the universal benefits of entropy-baa baasep confidence by generating the intermediate graphs via different graph mixup methods Han et al. (2022; Ma et al. (2024).
D Reproducibility
D.1 Datasets
We first introduce the datasots used in this paper, including three real-world datasets and three synthetic CSBM datasets, and the datasets statistics provided in Table 2 For real-world datasets, give brief introduction follows
Airport Ribeiro et al. (2017) set of airport traffic networks, each of which is an unweighted, undirected network with nodes as airports and edges indicate the existence of commercial flights. Node labels indicate the level of activity of the corresponding airport. We use degree- bucking generate one-hot node feature embeddings. The datasct includes three airports from USA, Europe and Brazil.
Citation Tang et al. (2008) is a set of co-authorship networks, where nodes represent authors and an edge exists between two authors if they co-authored at least one publication. Node labels indicate the research domain of the author, including "Database", "Data mining', "Artificial intelligence', "Computer vision', "Information security' and 'High performance computing'. Node features are extracted from the paper content. The dataset includes two co-author networks from ACM and DBLP.
Social Li et al. (2015) is a set of blog networks, where nodes represent bloggers and edges represent friendship. Node labels indicate the joining groups of the bloggers. Node features are extracted from blogger's self-description. The dataset includes two blog networks from BlogCatalog (Blog1) and Flickr (Blog2).
For synthetic datasets, we generate them based on the contextual block stochastic model (CSBM) Deshpande et al. (2018). In general, we consider a CSBM with two classes C4 = (v, 34 = +1} and C_ = {v; y 1), each with nodes. For node U, the node attribute is independently sampled from Gaussian distribution ac Nu, I). For nodes from class C4, have μ f44 and for nodes from class C_,, have ii n_..
32

---

Published in Transactions on Machine Learning Research (02/2020)
Table Dataset statistics.
Dataset
Domain
#node
#edge
#
#class
USA
1,190
13,599
64
4
Airport
Brazil
131
1,038
64
4
Europe
399
6,193
64
4
ACM
7,410
14,728
7,537
6
Citation
DCLP
5,995
10,079
7,537
6
Blogl
2,300
34,621
8,189
6
Social
Blog2
2,896
55,284
8,189
6
Left
500
5,154
64
2
Right
500
5,315
64
2
Low
500
2,673
64
2
CSBM
High
500
10,302
64
2
Homophily
500
5,154
64
2
Hetcrophily
500
5,163
64
2
Each pair of nodes are connected with probability p if they are from the same class, otherwise q. By varying the value of M., we can generate graphs with feature shifts. By varying the value of p, 9. we can generate graphs with homophily shifts with homophily score as h = ptg and degree shifts with average degree as d = N(x+9) We provide more detailed description of generating the CSBM graphs as follows
CSBM-Attribute a set of CSBM graphs with attribute shifts. We generate two graphs with attributes shifted left (namely Left) and right (namely Right). We the number of nodes as 500, homophily score h 0.5, average degree as 40, and feature dimension 64. For node attributes, set the p4+ = 0.6, μ 00.4 for Right, and μ4+ 0.4, μ -0.6 for Left.
CSBM-Degree is set of CSBM graphs with degree shifts. We generate two graphs with degroe shifted high (namely High) and low (namely Low). We set the number of nodes as 500, homophily score h = 0.5, feature dimension as 64, and features with μ4 = 0.5, p -055. For node degree, we set = 80 for High and = 20 for Low.
HSBM-Homophily a set CSBM graphs with homophily shifts. We generate two graphs with homophilic score (namely Homophily) and heterophilic score (namely Heterophily). We set the number of nodes as 500, average degree as 40, feature dimension 64, and fcatures with μ4+ = 0.5, p. = -0.5. For homophily score, we set the h 0.8 for Homophily, and h 0.2 for Heterophily.
D.2 Pipeline
We focus on the unsupervised node classification task, where we have full access to the source graph, the source node labels, and the target graph during training. Our main experiments include two parts, including direct adaptation and GDA using GADGET. For direct adaptation, we perform directly adapt the source graph to target graph. For GDA, first use GADGET to generate intermediate graphs, then gradually adapt along the path.
For path generation, we set the number of intermediate graphs as T 3, and have all graphs uniformly distributed on the geodesic connecting source and target. We set == and a = 0.5 for the FGW distance, and adopt uniform distributions Uni(([V))) Unif([Vi) as the marginals.
For GNN models, we adopt light 2-layer GNNs with 8 hidden dimensions for smaller Airport and CSBM datasets, and heavier 3-layer GNNs with 16 hidden dimensions for larger Social and Citation datasets. We set the initial learning rate as 10-2 and train the model for 1 1,000 epochs.
33

---

Published in Transactions on Machine Learning Research (02/2026)
We implement the proposed method in Python and all backbone models based on PyTorch. For model training, all GNN models are trained on the Linux platform with an Intel Xeon Gold 6240R CPU and an NVIDIA Tesla V100 SXM2 GPU. We run all experiments for 5 times and report the average performance.
E
More Related Works
Graph Domain Adaptation Graph DA transfers knowledge between graphs with different distributions and can be broadly categorized into data and model adaptation. Early graph DA methods drew inspiration from vision tasks by applying adversarial training to learn iivaaiinn node embeddings [Shen et al. (2020); Dai et al. (2022), analogous to DANN in images Ganin al. (2016). Wu et al. (2020) introduced an insupervised domain adaptive GCN that minimizes distribution discrepancy between graphs. Others exploit structural properties Wu et al. (2023) : Guo et al. (2022), such as degree distribution differences Guo el. al. (2022) and Subtree distance Wu et al. (023). A hierarchical structure is further proposed by [Shi et al. (2023a) to align graph structures hicrarchically. The rapid progress in this area has led to dedicated benchmarks Shi et al. (223bb) and surveys Wu et al. (2024); Shi el al. (0024). consolidating GDA techniques. These studies consistently report that large distribution shifts between non-IID graph domains remain difficult overcome, motivating novel solutions such as our OT--baed geodesic approach for more effective cross-graph knowledge
transfer.
Gradual Domain Adaptation Gradual domain adaptation (GDA) addressos scenarios of extreme domain shifts by introducing a sequence of intermediale domains that smoothly connect the source to the larget. Traditional methods in vision have instantiated the idea of GDA by generating intermediate feature spaces or image styles that interpolate between domains GoonginGGong et al. (2019): Hsu et al. (2020). For instance, DLOW Gong et al. (2019) learns a domain flow to progressively morph source images toward target appearance, and progressive adaptation techniques have improved object detection across environments Hsu et al. (2020).
Recently, the theory of gradual adaptation has been formalized Kumar et al. (2020); Wang et al. (022)) );
Abnar et al.] (2021): Chen & Chao (2021), where the benefits of intermediate distributions and optimal path
have been studied. He et al. (2023) further provides generalizat ion bounds proving the efficacy of gradual adaptation under certain conditions. On the algorithmic front, methods to construct or simulate intermediate domains have emerged. (Sagawa & Hino (2022) leverages normalizing flows to synthesize a continuum of distributions bridging souree and target, while Zhuang et al. (2024) employs Wasserstein gradient flow to gradually transport source samples toward the target distribution. This gradual paradigm has only just begun to be explored for graph data, e.g., recent work suggests that interpolating graph distributions siguilicantly improve cross-graph transfer when direct adaplation fails due lo a large shift. By viewing domain shift as a trajectory in a suitable metric space, one can effectively guide the model through intermediate graph domains, which is prociscly the principle our FGW geodesic stratogy instantiates.
Graph Neural Networks Graph Neural Network (GNN) is a prominent approach for learning on graph-
structured data, with wide applications in fields such as social network analysis Jing et al. (2024): : Fu & He
(2021]
Yan et al. (2024a). bioinformatics Fu & He (2022):
; Xu et al. (2024b), information retrieval Wei et al
(2000
Li et al.
[2024a]] b): Liu et al. (022cc and recommendation Liu et al. (2024b); Zeng et al. (2024b)
2025a
b) Liang et al.
2025
: Yoo et al. (022)) and tasks like graph classification Xu et al. 20188): Lin et al.
(2024b);
Zheng et al.
22024) node classification Yan et al. (0024c); Liu et al. ) Lin et al. (2024a) Xu
let al.
2024a): Yan et al. (023). link prediction Yan et al. (2022 2024b). and time-series forecasting Lin
et al.
2025 2024c): Qiu et al. (2023); WWan et al. (2023). Foundational architectures such as GCN Kipf & Welling (0017), GraphSAGE Hamilton et al. (2017), and GAT Velickovic et al. (2017) introduced effective
message-passing schemes to aggregate neighbor information, and subsequent variants have continuously pushed state-of-the-aee performance. However, distribution shift poses a serious challenge to GNNs in practice: models trained on a source graph often degrade when applied to different graph whose propertics deviate significantly. This lack of robustness to domain change has prompted research into both graph domain generalization and graph domain adaptation. On the generalization side, methods inject regularization or data augmentation to make GNNs invariant to distribution changes such as graph mixup Ma et al. (2024); Zeng et al. (202cc:: Zhou et al. (2024). On the adaptation side, numerous domain addative GNN frameworks aim transfer knowledge from labeled source graph to an unlabeled target graph by aligning feature and
34

---

Published in Transactions on Machine Learning Research (02/2026)
structural representations Shen et al. (2200): Dai al. (2022) Liu et al (2023a) Despite these advances, adapting GNNs to out-of-distribution graphs remains non-trivial, especially under large shifts. Besides, test-time adaptation on graphs has been studied recently [ao et al. (2024); Chen et al. (2022b); Jin et al. [2022]; Zeng et al. (2026) where the GNN model is adapted at test time without re-accessing the source graph. However, existing graph DA methods implicitly assume a mild shift. between the source and the target graph, while our work focuses on the more challenging setting where source and target graphs suffer from
large shifts.
Optimal Transport Graphs Optimal Transport (OT) provides principled framework to compare
and align distributions with geometric awareness, making it particularly well-suited for graph-structured data. OT-based methods have been used in graph alignment Xu et al. (2019); Zeng et al. (2023a 2024a): Yu
lt al. 2025b a), graph comparison Maretic et al. (2019): ; Titouan et al. (2019), and graph representation
learning Kolouri et al. (2021); Vincent-Cuaz et al. (2021) ; Zeng et al. (0023)) The Gromov Wasserstein
(GW) distance Mémoli (2011 Peyré et, al. (2016) enables comparison between graphs with different node
sets and topologies, and defines metric space where geodesics can be explicitly characterized Sturm (2012).
Recent work SSethoon et al. (2022) further demonstrates how OT couplings serve transport maps that align and interpolate between graphs in this space. These advances provide the theoretical foundation for our work, which leverages Fused GW distances to construct geodesic paths between graph domains for GDA.
F Limitations and Future Directions
In this paper, we explore the idea of apply GDA for non-IID graph data to handle large graph shifts. We mainly focus on the unsupervised DA setting, with only one source domain and one target domain. Based on this limitation, we discuss possible directions and applications to further benefit and extend the current. framework, including:
Multi-source graph GDA. In this paper, we focus on the graph DA setting with one labeled source graph and unlabeled target graph. In real-world scenarios, we often have labeled information from multiple domains. Therefore, it would be beneficial to study multi-source graph GDA to leverage information from multiple source graphs.
Few-shot graph GDA. In this paper, we focus on the unsupervised graph DA task where there is no label information for target samples. There may be cases where few target labels are available, and it would be beneficial to leverage such information into the graph GDA process. One possible solution is to leverage the graph mixup techniques Han et al. (0022; Ma el al. (202)); Zeng et al. (2024c) to generate pscudo-labels for intermediate nodes by the linear interpolation of source and target samples.
When to adapt. While we mainly focus on how to best adapt the GNN model, an important question when to adapt. For example, to what extent the domain shift is large enough to perform GDA? To what extent the domain shift is mild enough to perform direct adaptation or no adaptation. We believe that more powerful graph domain discrepancies such as the FGW distance provide solution to this problem.
Scalable GDA via Graph Coarsening. To extend GADGET to massive-scale graphs (e.g., millions of nodes) where quadratic complexity prohibitive, a promising future direction Hierarchical Graph GDA. We plan to incorporate graph coarsening techniques (e.g., spectral clustering or edge contraction) to abstract the original graph into smaller 'super-node' graph. The FGW geodesic and transport plan can be efficiently computed this coarsened level and then projected back to the original fine- grained graph. This "Coarsen-Alis Align- Refinee strategy aims to reduce the effective number of nodes n in the OT solver, potentially achieving near-linear time complexity while preserving global structural alignment.
35


Reviews:
[{"review_id": "ErGZyJVpxc", "reviewer": "Reviewer_DNXZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose a new method called GADGET. This method is based on Gradual Domain Adaptation and Graph Neural Networks. It learns a mapping according to the Fused Gromov–Wasserstein distance and, instead of solving a single hard domain-adaptation problem, it solves a sequence of small ones along the geodesic of this mapping. The method is supported by an interesting theoretical study that provides insights into its behavior.\nStrengths:\n- The paper is easy to follow, and apart from the figures, everything is clear.\n- The new method is supported by a theoretical study that provides insight into how many steps are optimal.\n- The authors present interesting experiments and compare their approach with a variety of methods and architectures.\n\nWeaknesses:\n- It is difficult to distinguish the domains in Figure 1; the crosses and circles are not easily recognizable.\n- The same issue appears in Figure 3.\n- There is no discussion of why GADGET performs better on csbm but worse on airport, social, and media. Similarly, there is no intuition for why GADGET fails to improve the score for some methods. Could you provide a potential failure case to clarify when GADGET is or is not useful? For example, when GADGET fails, do we effectively end up with T = 1 in your formulation?\nIt is unclear how GADGET is applied across all baselines, given the diversity of methods: shallow techniques like CORAL, deep methods like AdaGCN, and already-gradual DA methods like GRADE. How is GADGET combined with GRADE, for instance? Is GRADE simply the specific case where alpha = 0?\n- There is no discussion of the method’s limitations. Up to what graph size can GADGET be used? Solving FGW can be time-consuming when the number of nodes is large. What is the proposed solution? A larger dataset could also strengthen the experimental validation.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The authors claim that DA method for graph was supposing mild shift when real datasets suffer from larger shift. \nThe theoretical study shows that the performance on the target is bounded by the shift between the two graph and the experiments show that limiting this shift with GDA brings increase in the performance.", "audience_yn": "Yes", "audience_explanation": "Yes, GNN is becoming a big field in machine learning nowadays and this paper brings a new method to tackle efficiently the shift between graph.", "requested_changes": "- Add study of parameter alpha\n- Add limit of the method in the conclusion.", "broader_impact_concerns": "No concern", "additional_comments": "In figure 5, you are plotting the time. Does it refers to the total training of you method ? 1 sec seems very fast.", "extra_scores": {}, "extra_text": {}}, {"review_id": "85syYNwok7", "reviewer": "Reviewer_83tt", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces GADGET, the first framework for gradual domain adaptation (GDA) on non-IID graph data, designed to address the challenge of large distribution shifts where conventional graph DA methods often fail. The authors establish a rigorous theoretical foundation by adopting the Fused Gromov-Wasserstein (FGW) distance to measure discrepancy between graphs, which uniquely accounts for both node attributes and graph structure. Based on this, they derive a novel error bound for graph GDA, revealing that the target domain error is proportional to the length of the adaptation path. Motivated by this bound, the paper proves that the optimal path is the FGW geodesic and proposes an efficient practical algorithm to generate intermediate graphs along this path. The framework is designed as a versatile wrapper that can be seamlessly integrated with existing graph DA methods, and its effectiveness is demonstrated through extensive experiments, showing significant performance improvements on various real-world datasets.", "claims_and_evidence_yn": "No", "claims_explanation": "The evidence has a notable weakness, creating a gap between the convincing theory and the convincing experiments. The theoretical proofs of optimality rely on the true FGW geodesic, but for practical scalability, the paper's algorithm implements a low-rank approximation. The review points out that the submission lacks a theoretical analysis of the error introduced by this approximation. Consequently, while the algorithm is empirically effective, the evidence that the generated path is a close or sufficient approximation of the theoretically optimal path is not provided, making this part of the claim less supported. Furthermore, the review notes the algorithm's novelty is \"somewhat limited\" as it is a direct adaptation of a prior method, which slightly tempers the claim of a novel generation technique.", "audience_yn": "Yes", "audience_explanation": "The findings of this paper would be of interest to the TMLR audience, particularly those working in graph machine learning, transfer learning, and robust AI.", "requested_changes": "1. **Clarify Algorithmic Novelty and Positioning:** The path generation algorithm presented in Section 4 is a direct adaptation of the method from Zeng et al. (2024). The current \"Remark\" on page 8 is insufficient. Please revise the main text in Section 4 to explicitly state that the algorithm adapts this prior work for the FGW space and the novel task of unsupervised node-level GDA. This will more accurately frame the paper's core contribution, which is the theoretical framework and problem formulation for gradual adaptation on graphs, rather than a new optimization algorithm.\n2. **Address the Gap Between Theory and Practice:** There is a significant disconnect between the theoretical analysis, which relies on the exact FGW geodesic (Theorems 1-3), and the practical algorithm, which uses a low-rank approximation for scalability (Eq. 14). The paper currently lacks any analysis of the error introduced by this approximation.\n3. **Strengthen Justification for Theoretical Assumptions:** The mathematical assumptions in Section 3.2 need better intuition and justification to make the theoretical claims more convincing and accessible.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ibpIeVluur", "reviewer": "Reviewer_eCgC", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper tackles the graph Gradual Domain Adaptation (GDA) with Graph Neural Networks (GNN), handling large shifts between source and target graphs. In fact, as stated by the authors, here are the main contributions in this paper:\n1) they extend GDA to non-IID graphs by leveraging the Fused Gromov-Wasserstein (FGW) distance;\n2) they derive an error bound for graph GDA, highlighting the impact of the source GNN loss, the accumulated training error and the generalization error measured by length of the path;\n3) they show that there exist an optimal path minimizing this error bound;\n4) they provide an efficient way to generate intermediate graphs on this path;\n5) they provide an extensive empirical evaluation of their method, showing improvements over existing DA methods on classification datasets.\n\nStrengths:\n- The paper is rather well written.\n- The related works are discussed and the paper is clearly motivated.\n- The claims are supported by theoretical and empirical evidences.\n\nWeaknesses:\n- The theoretical assumptions should be more commented.\n- The computational cost of the method is not clearly discussed.\n- The paper lacks some discussions on the limitations of the frameworks and future work directions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The authors support their framework by providing theoretical guarantees, namely the error bound and the optimal path. All of these are provided with proofs. Moreover, they provide an extensive empirical evaluation, including accuracy results on various classification datasets, domain shifts, hyperparameter and path quality analyses.", "audience_yn": "Yes", "audience_explanation": "I am not familiar with this literature, but the related works seem thoroughly discussed and the authors identified a hole in the literature regarding GDA. In fact, they propose to use FGW to handle non-IID graphs and provide some theoretical guarantees. Hence, in my opinion, the TMLR's audience should be interested in this paper.", "requested_changes": "1) For the presentation, I would move the related works section after the introduction.\n2) Could you please elaborate a little more about the assumptions you consider? First, could you comment assumptions A and B? Second, are all of these assumptions standard in the literature or do you introduce new ones?\n3) Could you give more insights about the computational cost of the whole method? What is the complexity of generating the optimal path for instance? How does your method compare with respect to existing GDA methods in terms of computational cost?\n4) Could you elaborate a little more about the limitations of your frameworks in your opinion and any research directions to alleviate them?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)