An Efficient Orlicz-Sobolev Approach for Transporting Unbalanced Measures on a Graph
Authors: Tam Le
Truyen Nguyen
Hideitsu Hino
Kenji Fukumizu
Venue: NeurIPS 2025 spotlight ()
Keywords: Orlicz-Wasserstein
generalized Sobolev transport
Orlicz geometric structure
Lp geometric structure
measures on a graph
measures with different total mass
Primary area: other
TL;DR: Moving beyond $L_p$ geometric structure, we propose novel efficient Orlicz-Sobolev approaches (i.e., Orlicz-EPT, and Orlicz-Sobolev transport) for measures on a graph, possibly having different total mass.

Abstract: We investigate optimal transport (OT) for measures on graph metric spaces with different total masses. To mitigate the limitations of traditional $L^p$ geometry, Orlicz-Wasserstein (OW) and generalized Sobolev transport (GST) employ \emph{Orlicz geometric structure}, leveraging convex functions to capture nuanced geometric relationships and remarkably contribute to advance certain machine learning approaches. However, both OW and GST are restricted to measures with equal total mass, limiting their applicability to real-world scenarios where mass variation is common, and input measures may have noisy supports, or outliers. To address unbalanced measures, OW can either incorporate mass constraints or marginal discrepancy penalization, but this leads to a more complex two-level optimization problem. Additionally, GST provides a scalable yet rigid framework, which poses significant challenges to extend GST to accommodate nonnegative measures. To tackle these challenges, in this work we revisit the entropy partial transport (EPT) problem. By exploiting Caffarelli \& McCann's insights, we develop a novel variant of EPT endowed with Orlicz geometric structure, called \emph{Orlicz-EPT}. We establish theoretical background to solve Orlicz-EPT using a binary search algorithmic approach. Especially, by leveraging  the dual EPT and the underlying graph structure, we formulate a novel regularization approach that leads to the proposed \emph{Orlicz-Sobolev transport} (OST). Notably, we demonstrate that OST can be efficiently computed by simply solving a univariate optimization problem, in stark contrast to the intensive computation needed for Orlicz-EPT. Building on this, we derive geometric structures for OST and draw its connections to other transport distances. We empirically illustrate that OST is several-order faster than Orlicz-EPT. Furthermore, we show preliminary evidence on the advantages of OST for measures on a graph in document classification and topological data analysis.

An Efficient Orlicz-Sobolev Approach for Transporting Unbalanced Measures on a Graph
Tam Le"
Truyen Nguyen" University of Akron
Institute of Statistical Mathematics
tam@ish mim0@is... ac jp
truyenaguyendmeta.comm
Hideitsu Hino
Kenji Fukumizu
Institute of Statistical Mathematics hino@i sm. .c.jp
Institute of Statistical Mathematics mukumizu@ism ac.. jp
Abstract
We investigate optimal transport (OT) for measures on graph metric spaces with different total masses. To mitigate the limitations of traditional TP geometry, Orlicz- Wasserseiin (OW) and generalized Sobolev transport (GST) employ Orlicz geometric structure, leveraging convex functions to capture nuanced geometric relationships and remarkably contribute to advance certain machine learning ap- proaches. However, both OW and GST are restricted to measures with equal total mass, limiting their applicability to real-world scenarios where mass variation is common, and input measures may have noisy supports, or outliers. To address unbalanced measures, OW can either incorporate mass constraints or marginal discrepancy penalization, but this leads more complex two-level optimiza- tion problem. Additionally, GST provides scalable yet rigid framework, which poses significant challenges to extend GST accommodate nonnegative measures. To tackle these challenges, in this work we revisit the entropy partial transport (EPT) problem. By exploiting Caffarelli & McCann [12's insights, we develop a novel variant of EPT endowed with Orlicz geometric structure, called Orlicz-EPT. We establish theoretical background to solve Orlicz-EPT using a binary search algorithmic approach. Especially, by leveraging the dual EPT and the underlying graph structure, we formulate a novel regularization approach that leads to the proposed Orlicz-Sobolev transport (OST). Notably, we demonstrate that OST be efficiently computed by simply solving a univariate optimization problem, stark contrast to the intensive computation needed for Orlicz-EPT. Building this, we derive geometric structures for OST and draw its connections to other transport distances. We empirically illustrate that OST is several-order faster than Orlicz-EPT, Furthermore, we show initial evidence on the advantages of OST for measures graph in document classification and topological data analysis.
Introduction
-iiis--eassrsttei (OW) extends L geometry by leveraging a specific class of convex functions for Orlicz geometric structure. Intuitively, OW is an instance of optimal transport (OT), which utilizes Orliez metric as ground cost [67 32 28 41. Building on this foundation, OW has proven instrumental in advancing certain machine learning approaches. For example, recent works have leveraged OW tackle challenging problems: Altschuler & Chewi use OW as metric
: equal contribution. Correspondence to: Tam Le <tam0ism. ac. jp>.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

shift for Rényi divergence, enabling novel differential- privacy-inspired techniques to overcome longstanding challenges for fast convergence of hypocoercive differential equations, while Guha et al. [28] employ OW metric to significantly improve Bayesian contraction rates in hierarchical Bayesian nonparametric models by overcoming limitations raised from the usage of traditional OT with Euclidean ground cost. However, OW's high computational complexity, stemming from its two-level optimization formula, poses a significant limitation. To address this challenge, Le et al. 41 introduce generalized Sobolev transport (GST), scalable variant of OW suitable for practical application domains, especially for large-scale settings. Moreover, Orlicz geometric structure has been successfully applied to various machine learning problems, including linear regression [4] 66), scalable approaches [21] for reinforcement learning, kernelized support vector machines, and clustering. Additionally, Orlicz metrics play a crucial role in deriving deviation bounds for polynomial- growth functions to approximate kernel derivatives [13]. and have been used as regularization in OT problems (66] For in-depth studies Orlicz functions,
[2 60).
When dealing with input measures having different total masses, various approaches have been proposed in the literature to address this challenge [30
22
6
12 25 57
58 26
33
45
18
g 27
[4] 72. These approaches for unbalanced measures have proven effective in various domains, including color transfer [8) shape matching g image- to-image translation [72). multi-label learning [26), positive-unlabeled learning [15). point-cloud
63 64, 56 62 [5] 48 36 24 16 65
40 52
gradient flow (72), natural language processing [36 40), topological data analysis (TDA) [6 40).
generative modeling [5] [2]. domain adaptation S and robust approaches for handling noisy
supports, outliers [26 5 48 or noisy ground cost 54
In this work, we focus on the OT problem with Orlicz geometric structure for unbalanced measures supported on a graph metric space. On one hand, OW naturally extends OT's flexibility to handle unbalanced measures by incorporating either mass constraints or marginal difference penalization, formulated as partial OT (POT) unbalanced OT (UOT) respectively. However, these approaches result in more complex two-level optimization problem, analogous to POT/UOT with Orlicz metric cost, which poses significant computational challenges. On the other hand, although GST provides a scalable alternative to the computationally intensive OW, it still assumes equal-mass optimization over the critic function,
input measures. Moreover, due to GST's definition extending it to unbalanced measures is nontrivial. To address these limitations, we revisit the entropy partial transport (EPT) problem 36 40 72 and leverage insights from Caffarelli & McCann (12) to reformulate EPT as a standard complete OT problem. Then by carefully calibrating the corresponding ground cost for its nonnegativity, we propose Orlicz-EPT and establish theoretical foundation for solving it by a binary search algorithmic approach. Furthermore, by exploiting the dual EPT and underlying graph structure, we introduce a novel regularization approach, leading to Orlicz-Soboley transport (OST), which scales Orlicz-EPT for practical applications.
Contribution. In summary, our contributions are two-fold as follows:
We revisit the EPT problem and leverage Caffarelli & McCann 121's insights to reformulate EPT as a standard complete OT, leading to the development of the proposed Orlicz-EPP We establish its theoretical foundations, enabling a binary search algorithmic approach for its computation. Additionally, we develop a novel regularization approach, resulting in the proposed OST. We show that OST can be efficiently computed by simply solving a univariate optimization problem, unlike the computationally intensive Orlicz-EPTT.
We derive geometric structures for OST and establish its connections to other transport distances. Our empirical results demonstrate that OST is several-order faster than Orlicz- EPT. We also provide initial evidence on the advantages of OST for document classification and TDA.
Organization. In $2 we briefly review relevant background and notions. We revisit EPT problem and propose Orlicz-EPT in 3 In $4 we introduce the computationally efficient OST. Then we derive geometric structures for OST and draw its connections to other transport distances in $ In $6 discuss related work. Empirical results are presented in $7 followed by concluding remarks in $3) Proofs of key theoretical results and additional materials are deferred to the Appendices. Furthermore, we have released code for our proposed approaches ?
TThe code repository is on halhtts:: http:////ggtuuubec//tttta//////a 00010//

---

2 Preliminaries
In this section, we introduce notations, and briefly review graph, and Orlicz functions.
Graph. We follow the graph setting as in 39.. Let V. be the sets of nodes and edges respectively. We consider connected, undirected, and physica graph G (V, E) with positive edge lengths fwe)eEg. For continuous graph setting, we regard G as the set of all nodes in V and all points forming the edges in E. We equip G with graph metric (x y) which equals to the length of the shortest path between x and in G. Additionally, we assume that there exists fixed root node z0 V such that the shortest path connecting zo and x: is unique for any x E G, i.e., the uniqueness property of the shortest paths. We denote P(G) (resp. ( x G)) as the set of all nonnegative Borel measures on G (resp. G G) with a finite mass. Let [z, 2] be the shortest path connecting x and in G. For I E G, edge E E, define the sets Azz) and Ne as follows:
A(x) == (y E G x E [20.v]},
Y = (v= ec (20.0.3)
(1)
Functions on graph. By continuous function f on G, we mean that f G + R is continuous w.r.t. the topology on G induced by the Euclidean distance. Henceforth, C(G) denotes the set of all continuous functions on G. Similar notation is used for continuous functions on G x G. Given a positive scalar > O, then a function f : - R is called 6-Lipschitz w.r.t. de [f(x) [w)] < (dc v) for every x and y in G.
family of convex functions. We consider the collection of N N-functions 2
$8.2] which are special
convex functions on R4,. Hereafter, a strictly increasing and convex function Φ : (0) + [0, 20) is
called N-function if lim 2
(tt) O and lim,-+400 (+)) +00.
Orlicz functional space. Given an N-function & and nonnegative Borel measure w on G, let La (G,w) w) be the linear hull of the set of all Borel measurable functions f G + R satisfying SG ((If())))w(d) < co. Then, (G, w) is a normed space with the Luxemburg norm, defined as
ll == inf {
=inf
{ [t>01/
0
[ +
[f(x)] f
w w(dr) S $1
(2)
3 Orlicz-EPT: Entropy Partial Transport with Orlicz Geometric Structure
In this section, we revisit the entropy partial transport (EPT) problem [36
40
72
then develop
Orlicz-EPT variant of EPT endowed with Orlicz geometric structure.
3.1 Entropy Partial Transport (EPT)
Let 71, 72 be the first and second marginals of of P(G x G) respectively. For unbalanced measures M, E P(G), we consider the set 11 (p, ;= {7: 71 μ4, 722 S <>} Additionally, let f1, f2 be the Radon-Nikodym derivatives of 71 w.r.t. j and of 72 w.r.t. V/ respectively, i.e., 71 = f1
(0 S f1 1, p-a.e.) and 1/2 = f2 (0 < f2 I 1, v-a.e.).
For convex and lower semicontinuous entropy functions Fi, F2: [0, 1| + (0, oo), and nonnegative weight functions w1,w2 G + [0, oo), we consider the weighted relative entropies Fi Fi(m Sa wi (a:) F (fi (x)))(dx) and F2(1221) == Ss Fa(a())((((())))((
For scalar b O, scalar min (Gi), (G) and graph metric ds as ground cost, the EPT problem
m E [0, m] with
(G)).
F1(ml + F2(72l1) + b [ da(z, v)r(dr dy)] oxS
inf W Wm(Hv) (ellg(ua) (GxG)=m
(3)
Following 40 $3], by using entropy functions (i = F2(s) = Is s 1| and considering a Lagrange
multiplier À E R conjugate the constraint 7G x G) = m. instead study the problem
(T) gEll (n.v)
inf C2(7);
'I sense that is subset of Euclidean space R." and each edge e the standard line segment RR connecting the two vertices the edge e. 'y μ means that y (B) & ((B) for all Borel set B C G. similarly for 72 $ v.
3

---

where Cx(r) Je wid(dz) + fc wzu(dx) Jc wi - fs "212(dx) + + fxxolda (2
A/((dz, dy)
EPT as a standard OT. Following Caffarelli & McCann 12 's insights, we can reformulate prob- lem (4) as the standard complete OT problem. However, it is not guarantee that the corresponding standard OT has a nonnegative ground cost, e.g., see 12 6, 40 72 Therefore, such OT reformula-
41 since N-function is only defined for nonnegative domain ($2). Therefore, it essential to carefully calibrate the ground
tion may not be applicable derive corresponding OW as in 67 32 28
cost of the corresponding standard OT of EPT to ensure its nonnegativity.
Precisely, following [40] Theorem 3.1], we henceforth consider 2 0 Then let point outside graph G, i.e., 3 & C, and extend graph metric cost de & to a new nonnegative cost function with bX-deviation on G G U {3} as follows:
dd (z, y) (1) bd
xr y E G; if E G and y 8, if = and E G, 8.
8(x,))= ==
(5)
w2(1) bd by
if
For unbalanced measures Ja, V, construct corresponding probability (balanced) measures j n+v(C)6 Let (] = P(G x G) fi()) +U x G). ((U) ,+v(C)6, and é ((G)+
((G)+
1G x U) for all Borel sets U c c& G then one can recast EPT
standard OT with cost é
Proposition 3.1. Consider the standard OT We berween probability measures Jú, with cost | E(x, ((x,))f(dr,dy))
inf Wa(d, SETT(A,))
then we have
KT (u(G) (G)) (WalA,)) DA) = =FTx(1
The proof is placed in Appendix A.2.
Thus, we have reformulated EPT for unbalanced measures as corresponding standard complete OT 7 with nonnegative ground cost. Consequently, bypass the technical challenges inherent in unbalanced settings and can leverage abundant existing results and approaches in the standard balanced setting for OT problems with unbalanced measures graph.
Remark 3.2 (Nonnegativity). Unlike existing approaches, e.g., as in [12 36 40 72], the new ground cost of the corresponding standard OT problem (7) for EPT guaranteed to nonnegative. Our
calibration is essential for developing the associated OW from its standard OT as in 67
32 28 17
3.2 Orlicz-EPT
Following the approaches in 66 667
we define Orlicz-EPP which is EPT endowed with an Orlicz geometric structure, based on the standard OT problem 7 as follows:
28 17.
( v) = (a(G) + v(G) (Wi (p, D) bA).
(8)
where Wo (j D) inf inf f 0 fexe & ((xr.))
(x. =1]
It should be noted that, similar to OW. Orlicz-EPT 8 is derived from the standard OT problem 77) which circumvents all challenges coming from the setting of unbalanced measures.
We next show that the objective function of Orlicz-EPT is monotone non-increasing w.r.t. Proposition 3.3 (Monotonicity). Let & be an N N-function, and let è be the cost given by For any probability measures j and é on G. define
(((2,)) (((a))0)
A(t; = inf gEII(A.)) f6x6
+b
dF(z.)) for t> 0.
Then the function & E (0, -20) A(t: 11) is monotone non-increasing.
The proof is placed in Appendix $A.2.2
*The relationship between Problem and Problem 4 is established in 40 Theorem A.
'The dual EPT result is the foundation for developing Orliez-Sobolev transport where À is nonnegative.

---

Computation. Observe that for a fixed t. A is a standard OT problem between f and á with the cost function +
For computational efficiency we consider its corresponding entropic regularization [20], and show that the monotonicity is preserved.
Proposition 3.4 (Entropic regularization), Define the entropic regularization of A as
U + ((cx.)) d7(x.)) -
Aett;p,0) = inf SEll(a.))
(10)
where and H is Shannon entropy defined by H(5) == Sexe (log 5(x, v) 11)0-11--44 ()d5(r, v). Then the function t E (0,+00) + Ae(t: (, D) is monotone non-increasing.
The proof is placed in Appendix $A.2.3
In addition, we obtain following upper and lower bounds for Ac. Proposition 3.5 (Bounds). Let supp(-) be a set of supports of a measure, then we have
We( 2)) Ac Φ 1 (1 [1++ (p) + (D) - 11) 1.. 2 and A A La,0
x (1) (,.0 S
where Lp.0 = max, (supp(() 6(x, y).
The proof is placed in Appendix $A.2.4
Thanks to the monotonicity of Ar in Proposition 3.4 and the limits of A in Proposition 3.5 we can leverage the binary search approach to compute the entropic regularized Orlicz-EPT, which corresponds to the original Orlicz-EPT ( Precisely, this entropic regularization defined as
(E == (p(G) + v(G) (Wi. (R, bA),
(11)
where Wa. (A, D) == inf inf inf 0: Sexa & ( d7(xx,) - -H s1]
Discussions. Orlicz-EPT is novel variant of EPT that incorporates Orlicz geometric structure. Leveraging Caffarelli & McCann [2]s insights and carefully calibrating the ground cost of the corresponding standard OT to ensure its nonnegativity. unbalanced measures and derive the proposed Orlicz-EPT from the standard OT, similar to OW [67]. We note that OE [1] performs binary search with quadratic complexity A (10), instead of dealing with super-cubic complexity structure of + still retains significant complexity, severely limiting its practical applications, particularly in large-scale settings. To address this computational challenge, in the next section we exploit the dual EPT and graph structure to develop novel regularization approach, resulting in the proposed Orlicz-Sobolev transport. This approach adopts the Orlicz geometric structure used in Orlicz-EPT, but offers much more efficient computation.
are able to bypass all challenges of
OE S Unfortunately, the two-level optimization
4 Orlicz-Sobolev Transport: A Scalable Variant of Orlicz-EPT
In this section, we leverage the dual EPT and underlying graph structure to develop novel regular- ization approach, resulting in the proposed Orlicz-Soboley transport (OST).
Dual EPT. For b-Lipschitz wi, w2 (w.r.t. de), from 440 Corollary 3.2], the dual EPT is
ETx(M, v) = sup [ f(u - -v) - by f
[m(G) + +(G)].
(12)
where U:= (f -w2 <s w1 + 22 1f(x) f(0) S bdb(
Let V be the complement N-function of and w be a nonnegative Borel measure on G. Then let
WL. (G,w) be the graph-based Orlicz-Sobolev space [4] Definition 3.1] associated vi and Inspired by the approach of GST [11. we consider the critic function f E U within WT (G,w). Consequently, the b-Lipschitz constraint the critic function f U is replaced by I b.
EEtropic regularized OT reduces the computational cost of OT from super-cubic quadratic complexity 20
5

---

For f E WL (G, w), we have f(z) f(zo) + [po..a (')))(dy)) Vr E G. Let 1 be the indicator
function. Then by using the generalized Hölder inequality [2] $8.11] and II S b, we can control the integral part over the generalized graph derivative f for f(x) follows:
J (()) S 2 [I |=,0::)|22. - 26 | [20
2b
La. S Φ (1w()/)(G)
(13)
where the last inequality is due to the increasing property of N-function Φ. Therefore, instead of the bounded constraint on the critic function in U, we constraint only on f(2o).
Definition 4.1 (Orlicz-Sobolev transport (OST)), For a E [0, [ wi (zo) + w2(2)))) let Zn (-w2(20)
6λ + a, w2 + BA a). The Orlicz-Sobolev transport for μe E P(G) defined
2
[Le (()))(dd)) - ((x))(da))
(So, = sup
(14)
Setv,a
where Uv.a = 1s (G,) II s b, E }.).
Intuitively, Wv,a is the collection all functions f expressed by f(x) = =++ (1o.) hdy) Va e
G, where In. and | I b. The upper bound constraint is to ensure that I, is nonempty. When a = 0, In is the largest interval. Also, OST is an instance of the integral probability metric [49].
Computation. Given unbalanced measures μ., v E P(G), for brevity let us define
+
w1
(0))
6λ 3
a
if (G 2 v(G),
(15)
W2 (0))
if (G (GG)
Theorem 4.2 (Univariate optimization problem for OST). OST can be computed as follows
/ + (bblu(A(z)) ((Ax))))) ((dr))
OS = (l((G) v(G)
inf RSO &
1
(16)
The proof is placed in Appendix $A.2.5
We derive the discrete case for OST which provides explicit expression for the integral in 663 Corollary 4.3 (Discrete case). Let w be the length measure of graph G, and assume that input measures μ. are supported on nodes in V of graph G Then, we have
OS ( v(G)
iif RSO Te
1
1+ Σ eEE
w. ((bbl)(())) - (((T))-((7e))) -(Toll)
(17)
The proof is placed in Appendix $A.2.6
Therefore, OST can be efficiently computed by simply solving the univariate optimization prob- lem (17). thanks the proposed novel regularization for critic functions Us.a-
Remark 4.4 (Non-phi connphhyical graph). In $ G is assumed to be physical graph. Corollary 4.3 implics that OST only depends graph structure (V, EE) and edge weights we when input measures are supported on nodes V of G. Hence, OST applicable for non-physical graph C for such cases.
Remark 4.5 (Complementary pairs of N-functions). Corollary 4.3 also implics that one can compute OST with N V-function & without involving its complementary N -function V (17), unlike its defini- tion (1)). The univariate optimization formula (17) for OST requires that is finite-valued, which satisfied for any N-function & it grows faster than linear.
Preprocessing for Ye- Similar to the GST computation 41 we precompute set Te 1 for all edge in G. More concretely, we apply the Dijkstra algorithm to recompute the shortest paths from zo to all other vertices in V with complexity O(E) + |ol [V), where denotes the set cardinality.
Sparsity. Observe that for every x supp(u), its mass is gathered into p(Te) if and only if E 3e (#) U supp(r)), C [žo. 2}} C E. Then it suffices
C. [zo,2] [T.. Let == fe+
to compute the summation only over edges e Ep,, 17 for OST, i.e., screen out all edges E E Ey.--
SIt can be extended for measures supported in G (see B.2

---

Theoretical Properties
In this section, we leverage the computational efficiency of OST to derive its geometric structure and explore its connections to other transport distances.
Geometric structures of OST.
Proposition 5.1 (Geometric structure). Let S a bA minffw (=o), w2(20)) and u, P(G).
(, 0Sa,
ii) OS is a divergence annd OSo,a (1, S (U, a
tii) With an additional assumption w1 (zo) w2(z0). then OS is a metric.
We next establish connections of OST with other transport distances, including GST 41 Soboley transport (ST) 39 unbalanced Sobolev transport (UST) 40
Connection of OST with GST. Denote GS$ for the GST with N-function /b
Proposition 5.2. For ((G) = (G), b 1, then OS (,, v) = GS
Connection of OST with ST. Denote Sp for the p-order ST, for 1 <. p Proposition 5.3. For ((G) = vG). b and ((1) (p- 1)p-1 IP, then OS OSo Sp(u,
pp
Connection of OST with UST. Denote U.S.pc for UST, for 1 < <pc0 00. Proposition 5.4. For N N-function ((1) (p-1)p-1 pF P, then (0, = USS p.o (1, v).
Additionally, we investigate the limit case for N-function, i.c., 2 for OST and Orlicz-EPT.
Proposition 5.5 (Limit case for OST). For ((t) t, and with the same assumptions in Corol- lary then OST yields a closed-form expression as follows:
(8, = Σ We v(())) (l(a))))) v(G).
(18)
eEE
Proposition 5.6 (Limit case for Orlicz-EPT), For (t)) then we have ( KT(p,v) for every μ. V E P(G).
Proposition 5.7 (Relation of OST and Orlicz-EPT), For ((1) = I, length measure w on G, b-Lipschitz W1, u2 (w.rf. de). a = 0, and = 1, then OS (14, v) 2 08 (1,, + 2 (m(G) + v(G).
The proofs for these theoretical results (in $ are respectively placed in $A.2.7 A.2.13
6 Related Works and Discussions
In this section, we discuss relations between our proposals with related works in the literature.
GST [1]. Proposition 5.2 shows that OST provably generalizes GST 41 for unbalanced measures. We emphasize that GST is restricted for balanced measures and defined as an optimization over the critic function, making it nontrivial to directly extend it to accommodate unbalanced measures.
EPT [36, 40, (22. Orlicz-BPT and OST are developed from the primal and dual EPT respectively. Notably, the corresponding standard OT following [12] is not guarantee nonnegativity for ground
cost, see 22 36 40). Additionally, Caffarelli & McCann 12 insights may not be applicable to
certain other UOT formulations, such those proposed in 66 26
18
63
64
27
48 52) The
calibration is essential to guarantee nonnegativity for ground cost of the corresponding standard OT for EPT, paving ways to develop Orlicz-EPT. Similar to OW, Orlicz-EPT is derived from standard OT, thereby circumventing the challenges associated with unbalanced measures. Furthermore, we derive novel regularization, resulting in the proposed OST with efficient computation.
9 O0So. (1, v) 2 and OS v) if only μ v.
Notice that (tt) is not an N W-function due to its linear growth. It can be considered as the limit p - 17 of the N funcciion ((t) (? with p > 1.
7

---

UST [40] and ST [39] Proposition 5.4 shows that OST provably generalizes UST to a more general collection of N N-functions. Consequently, OST also provably generalizes ST to unbalanced measures, and to a more general set of N-functions (see Proposition 5.3
Measures
graph. We study OT problem between swo unbalanced measures supported on the same graph, a setting also explored in [40]. One should distinguish our considered problem
with the research lines on computing either distanceesdiiscreaancis [55 74
73
22
47
or
kernels 100 34 53
between two (different) input graphs.
7 Experiments
In this section, we illustrate that the computation of Orlicz-EPT is costly. Especially, OST is several- order faster than Orlicz-EPT. Following the problem setups in 44), we evaluate OST for unbalanced measures supported given graph [T and show initial evidences on its advantages for document classification and topological data analysis (TDA).
Document classification. We use 4 real-worid document datasets: TWITTER, RECIPE, CLASSIC, and AMAZON as in [40], and summarize their characteristics in Figure 2 By regarding each word in a document as a support with unit mass, we represent each document as a nonnegative measure. Consequently, the representations of documents with different lengths are measures with different total mass. We apply the same word embedding procedure in [40] to map words into vectors in R000
TDA. We consider orbit recognition Orbit t dataset M1 and object shape classification MPEG7 dataset (35) as in [40]. We summarize these dataset characteristics in Figure 3 We use persistence diagrams (PD), multiset of 2-dimensional data points summarized topological features, to represent objects of interest. We then consider each data point in PD as a support with a unit-mass, and represent PD as nonnegative measures. As result, PD having different numbers of topological features are presented as measures with different total mass 12
Graph. Following [4).
the graphs GLog and Gsyn [39 $5] for our experiments which empirically satisfy the assumptions in $2 Additionally, set . = 10 for the number of nodes for these graphs, except experiments on MPEG7 dataset with M/ = 10 due to its small size.
N-function. Following 41, we consider two N-functions: 2 (t) = exp(f) - -t- - 1, and (t)
exp(t?) 1, and the limit case of N N-functions, i.e., (t
Parameters. For simplicity, we follow the experimental setup in 40 We set A = b = 1, a = 0.
and consider the weight functions wi (2:) = (2) = aadds (20, x) + an where di = and ag = 1. The entropic regularization ē is chosen from {0.01, 0.1, 1, 10). typically via cross validation.
Optimization algorithm. For OST, we use fmincon MATLAAB solver with trast-rggion-refectiie algorithm, for solving the univariate optimization problem (77.
SVM classification. For document classification and TDA, we use support vector machine (SVM) with kernels cxp(-td((,-) -)), where d is a distance/diserepancy (e.g., OST, Orlicz-EPT) for unbalanced measures on graph, and f > 0. We regularize Gram matrices by adding a sufficiently large diagonal term for indefinite kernels 20). Additionally, we note that there are more than 29M pairs for AMAZON which we need to evaluate distancessdiiereppaniis for SVM in each run to illustrate the experiment scale
Set up. We randomly split each dataset into 70%/30% for training and test, and use 10 repeats. We basically choose hyper-parametert via cross validation. More coneretely, we choose kernel hyperparameter from {1/g., 0.5/q., 0.2/q. with s = 10, 20..... .00, where qa is the s% quan- tile of a subset of distances observed on a training set; SVM regularization hyperparameter from {0.01, 0.1, 1, 10}; root node žy from a random 10-root-node subset of V in graph C. Note that reported time consumption includes all preprocessing procedures, e.g., preprocessing for Te for OST.
''One should distinguish the considered problem, i.c., compare two imput unbalanced measures supported in the same graph, with either OT or Gromov- Wasserstein problem between two different imput graphs ($6). We distinguish our problem setup with AT]. where objects are represented as probability measures instead.
Due to the space limitation, corresponding experimental results for graph GLog are placed in BB.
"See Table I in BB. for the details.
8

---

7.1
Computation
Orlicz-EPT
10
OST
Time consumption (
103
102
10
10
(()=exp[()---1
<(t==exp(()-)
Figure 1: Time consumption.
We compare the time consumption of OST and Orlicz-EPT with 11, Φ2 and with the limit case Po-
Set up. We randomly sample 10 pairs of nonnegative measures on AMAZON dataset for evaluation. We consider M = 10s for graphs, and & = 0.1 for Orlicz-EPT.
Gsa in Figure OST is several-order faster than Orlicz-EPT, ie.. at least 250 13800x, 11200x for 2 21 L2 respectively, Notably, for N- functions 1 22, Orlicz-EPT takes at least 2.6 days, while OST takes less than 21 seconds. Note that for the limit case 2o. Drlicz-EPT is equal to EPT on a graph (Proposition 5.6). and OST admits closed-form expression (Proposition 5.5) for fast computation. Consequently, Orliez-EPT and OST with Py more computationally efficient than those with @2, 422.
Results. We illustrate the time consumptions
7.2
Document Classification
TWITTER (3/3108/26)
RECIPE (15/4370/340)
CLASSIC (4/7093/197)
AMAZON (4/8000/884)
0.98
Average Accurscy
0.73
0.55
0.96
0.72
0.94
0.71
0.82
0.85
0.45
0.8
0.88
0.88
0.86
0.67
0.4
0.75
Time Consumpilon (8)
104
HEEE
10a
10a
10
10"
10
10a
10
Jd.-Tree
regEPT-Tree
OST-4
OST-
OST-
Figure Document classification on graph G For each dataset, the numbers in the parenthesis are respectively the number of classes; the number of documents; and the maximum number of unique words for each document.
Set up. We evaluate OST with Po 1 t 7.1.. denote them as OST- for 0, We exclude Orlicz-EPT due to their heavy computations 7.1.. Additionally, following [40], we consider

---

UOT 26 63 with ground cost de 15 and special cases with tree-structure graph. More concretely, we randomly sample tree from the given graph G, then consider the regularized EPT and dg, denoted as do-Treee and TegEPT-Tree [36 Proposition 3.8, Equation (9)].
Results. We show SVM results and time consumptions of kernels GSyn in Figure 2 The performances of OST with all & functions are comparable to UOT, but the computation of UOT more costly than OST. Additionally, OST outperforms do-Tree and regEPT-Tree. However, the computations of 1 OST-P2 are more expensive while the computation of OST-Po is comparative to those cisttcomputational variants of UOT on tree (i.e., du-Tree and regEPT-Tree). Moreover, OST-4; and OST-P2 improve performances of OST-Pu, but their computational time is several-order higher, which may imply that Orlicz geometric structure in OST may be helpful for document classification. The performances of UOT also agree with observations in [4)].
7.3 Topological Data Analysis (TDA)
Orbit (5000/300)
MPEG7 (200/80)
Average Accuracy
0.4
0.7
0.3
0.6
0.2
0.5
0.1
0.4
0.3
108
Time Consumption
10
10
UOT
-Tee
regEPT-Tree
OST-
OST- +
OST-4,
Figure 3: TDA on graph G For each dataset, the numbers in the parenthesis respectively the number of PD; and the maximum number of points in PD.
Set up. Similarly, we evaluate OST-Pp, OST-4,, OST-42, UOT, do-Tree, and regEPT-TTre for TDA.
Results. We illustrate SVM results and time consumptions of kernels on GSgn in Figure 3 The performances of OST with all & functions compare favorably with other transport distance approaches. Especially, the performances of OST-4; and OST-4, compare favorably with those of OST-4p, but comes with higher computational cost (i.c., OST-2o has glosed-form expression (Proposition 5.5 which may imply that Orlicz geometric structure may be also helpful for TDA tasks.
8 Conclusion
In this work, we propose novel approaches to extend OW/GST for unbalanced measures on graph. Building the EPT problem and leveraging Caffarelli & McCann [12's insights, we derive Orlicz-EPT by recasting as standard OT with carefully calibrated ground cost, thereby bypassing challenges raised from unbalanced measures. Furthermore, by exploiting dual EPT and the underlying geometric structure, we formulate a novel regularization. resulting in the proposed OST, which is efficient in computation. It provably suffices to compute OST by simply solving univariate optimization problem, unlike the computationally intensive Orlicz-EPT, Moreover, we illustrate empirical evidence the advantages of OST in document classification and topological data analysis.
"'éjoouné et al. 63 65 derived debiased version for (Sinkhorn based) UOT which may be helpful in applications 40) |B.3.... It has the same computational complexity UOT, and is also empirically indefinite.
10

---

Acknowledgments and Disclosure of Funding
We thank the area chairs and anonymous reviewers for their comments. KF has been supported part by Grant-in-Aid for Transformative Research Areas (A) 22H05 106 and JST CREST JPMJCR2015. HH acknowledges the support of JSPS KAKENHI JP25H01494 and JP23K24909, TL gratefully acknowledges the support of JSPS KAKENHI Grant number 23K1 1243, and Mitsui Knowledge Industry Co., Ltd. grant.
References
[1] Adams, H., Emerson, T., Kirby, M., Neville, R., Peterson, C., Shipman, P., Chepushtanova, S., Hanson, E., Motta, F., and Ziegelmeier, L. Persistence images: A stable vector representation of persistent homology. Journal of Machine Learning Research, 18(1):218 252, 2017.
[2] Adams, R. A. and Fournier, J. J. Sobolev spaces. Elsevier, 2003.
[3] Altschuler, J. M. and Chewi, S. Faster high-accuracy log-concave sampling via algorithmic warm starts. Journal of the ACM, (13::1155,, 2024.
[4] Andoni, A., Lin, C., Sheng, Y., Zhong, P., and Zhong, R. Subspace embedding and linear regression with Orlicz norm. In International Conference on Machine Learning, pp. 224 233. PMLR, 2018
[5] Balaji, Y., Chellappa, R., and Feizi, Robust optimal transport with applications in generative modeling and domain adaptation. Advances in Neural Information Processing Systems, 33: 12934 12944, 2020.
[6] Benamou, J.-D. Numerical resolution of an "unbalanced" mass transport problem. ESAIM: Math- ematical Modelling and Numerical Analysis-Modéltsttion Mathématique et Analyse Numérique, 37(5):851-868, 2003.
[7] Bonet, C., Nadjahi, K., Sejourne, T., Fatras, K., and Courty, N. Slicing unbalanced optimal transport. Transactions on Machine Learning Research, 2024.
[8] Bonneel, N. and Coeurjolly, D. SPOT: sliced partial optimal transport. ACM Transactions on Graphics (TOG), 38(4):1-13, 2019.
[9] Bonneel, N., Rabin, J., Peyré, G., and Pfister, H. Sliced and Radon Wasserstein barycenters of measures. Journal of Mathematical Imaging and Vision, 51(1):22-45, 2015.
[10] Borgwardt, K., Ghisu, E., Llinares-López, F., O' Bray, L., Rieck, B., et al. Graph kernels: State-of-the-art and future challenges. Foundations and Trends@ in Machine Learning, 13(5-6); 531-712, 2020.
[11] Brogat-Motte, L., Flamary, R., Brouard, C., Rousu, J., and d' Alché Buc, Learning to predict graphs with fused iromov-wasserstein barycenters. In International Conference Machine Learning, pp. 2321-2335. PMLR, 2022.
[12] Caffarelli, L. A. and McCann, R. J. Free boundaries in optimal transport and Monge-Ampere obstacle problems. Annals of mathematics, pp. 673-730, 2010.
[13] Chamakh, L., Gobet, E., and Szabó, Z. Orlicz random Fourier features. The Journal of Machine Learning Research, 21(1):5739-577 2020.
[14] Chapel, L. and Tavenard, R. One for all and all for one: Efficient computation partial Wasserstein distances on the line. In The Thirleenth International Conference Learning Representations, 2025.
[15] Chapel, L., Alaya, M. Z., and Gasso, G. Partial optimal tramport with applications on positive- unlabeled learning. Advances in Neural Information Processing Systems, 33:2903-291 2020.
[16] Chapel, L., Flamary, R., Wu, H., Févotte, C., and Gasso, G. Unbalanced optimal transport through non-negative penalized linear regression. Advances Neural Information Processing Systems, 34:23270-23288 2021.

---

[17] Chewi, S. An optimization perspective on log-concave sampling and beyond. PhD thesis, Massachusetts Institute of Technology, 2023.
[18] Chizat, L., Peyré, G., Schmitzer, B., and Vialard, F.-X. Unbalanced optimal transport: Dynamic and Kantorovich formulations. Journal of Functional Analysis,
2018.
[19] Cover, T. M. and Thomas, J. A. Elements of information theory. John Wiley & Sons, 1999.
[20] Cuturi, M. Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in Neural Information Processing Systems, pp. 2292-2300, 2013.
[21] Deng, Y., Song, Z., Weinstein, O., and Zhang, R. Fast distance oracles for any symmetric norm. Advances in Neural Information Processing Systems, 35:7304-7317, 2022.
[22] Dong, and Sawin, W. COPT: Coordinated optimal transport on graphs. Advances Neural Information Processing Systems, 33:19327-19338, 2020.
[23] Edelsbrunner, H. and Harer, J. Persistent homology A survey, Contemporary Mathematics, 453:257-282, 2008.
[24] Fatras, K., Séjouméé, T., Flamary, R., and Courty, N. Unbalanced minibatch optimal transport; applications to domain adaptation. In International Conference Machine Learning, pp. 3186-3197. PMLR, 2021.
[25] Figalli, A. The optimal partial transport problem. Archive for rational mechanics and analysis, 195(2)-533-560, 2010.
[26] Frogner, C., Zhang, C., Mobahi, H., Araya, M., and Poggio, T. A. Learning with Wasserstein loss. In Advances in neural information processing systems, pp. 2053-2061, 2015.
[27] Gangbo, W., Li, W., Osher, S., and Puthawala, M. Unnormalized optimal transport. Journal of Computational Physics, 399: 108940, 2019.
[28] Guha, A., Ho, N., and Nguyen, X. excess mass behavior in Gaussian mixture models with Orlicz-Wasserster Wasserstein distances. In International Conference on Machine Learning, ICML, volume 202, pp. 11847-11870, PMLR, 2023.
[29] Guittet, K. Extended Kantorovich norms: a tool for optimization. INRIA report, 2002.
[30] Hanin, L. G. Baatorovich-Rubinster norm and its application in the theory of Lipschitz spaces. Proceedings of the American Mathematical Society, 115(2):345-352, 1992.
[31] Hertzsch, J.-M., Sturman, R., and Wiggins, S. DNA microarrays: Design principles for maximizing ergodic, chaotic mixing. Small, 3(2):202-218, 2007.
[32] Kell, M. On interpolation and curvature via Wasserstein geodesics. Advances in Calculus of Variations, 10(2):125-167, 2017.
[33] Kondratyev, S., Monsaingeon, L., and Vorotnikov, D. A new optimal transport distance on space of finite Radon measures. Advances in Differential Equations, 21(11/12)1117-1116 2016.
[34] Kriege, N. M., Johansson, F. D., and Morris, C. A survey on graph kernels. Applied Network Science, 5:1 421-42,222 2020.
[35] Latecki, L. J., Lakamper, R., and Eckhardt, T. Shape descriptors for non-rigid shapes with single closed contour. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), volume 1, pp. 424-429, 2000.
[36] Le. Т. and Nguyen, Entropy partial transport with tree metrics: Theory and practice. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp. -343,, 2021.
[37] Le, T., Yamada, M., Fukumizu, K., and Cuturi, M. Tree-sliced variants of Wasserstein distances. In Advances in neural information processing systems, pp. 12283-12294, 2019.
12

---

[38] Le, T., Ho. N., and Yamada, M. Flow-based alignment approaches for probability measures in different spaces, International Conference on Artificial Intelligence and Statistics (AISTATS). 2021.
[39] Le, T., Nguyen, T., Phung, D., and Nguyen, V. A. Sobolev transport: A scalable metric for probability measures with graph metrics. In International Conference on Artificial Intelligence and Statisties, pp. 9844-9863 2022.
[40] Le, T., Nguyen, T., and Fukumizu, K. Scalable unbalanced Sobolev transport for measures on graph. In International Conference on Artificial Intelligence and Statistics, pp. 8521-8560, 2023.
[41] Le, T., Nguyen, T., and Fukumizu, K. Generalized Sobolev transport for probability measures on a graph. In Forty-first International Conference on Machine Learning, 2024.
[42] Le, T., Nguyen, T., and Fukumizu, K. Optimal transport for measures with noisy tree metric. In International Conference on Artificial Intelligence and Statisties, pp. 31 3115-3123, 2024.
[43] Le, T., Nguyen, T., Hino, H., and Fukumizu, K. Scalable Sobolev IPM for probability measures on a graph. In Forty-second International Conference on Machine Learning. 2025.
[44] Lellmann, J., Lorenz, D. A., Schonlieb, C., and Valkonen, T. Imaging with Kantorovich- Rubinstein discrepancy. SIAM Journal on Imaging Sciences, 7(4):2833-2859, 2014.
[45] Liero, M., Mielke, A., and Savaré, G. Optimal antropy-transpon problems and a new Hellinger- Kantorovich distance between positive measures. Inventiones mathematicae, 211(3):969-111 2018.
[46] Lorenz, D. and Mahler, H. Orlicz space regularization of continuous optimal transport problems. Applied Mathematics & Optimization, 85(2):14, 2022.
[47] Ma, X., Chu, X., Wang, Y., Lin, Y., Zhao, J., Ma, L., and Zhu, W. Fused Gromov- W Wasserstein graph mixup for graph-level classifications. Advances Neural Information Processing Systems, 36:15252-15277 15276, 2023.
[48] Mukherjee, D., Guha, A., Solomon, M., Sun, Y., and Yurochkin, M. Outlier-robust optimal transport. In International Conference on Machine Learning. pp. 7850-7860. PMLR, 2021.
[49] Müller, A. Integral probability metries and their generating classes of functions. Advances in Applied Probability, 29(2):429-443, 1997.
[50] Musielak, J. Orlicz spaces and modular spaces, volume 1034. Springer, 2006.
[51] Nguyen, K., Zhang, S., Le, T., and Ho, N. Sliced Wasserstein with random-path projecting directions. In Forty-first International Conference Machine Learning, 2024.
[52] Nguyen. Q. M., Nguyen, H. H., Zhou, Y., and Nguyen, L. M. On unbalanced optimal transport: Gradient methods, sparsity and approximation error. The Journal of Machine Learning Research, 2023.
[53] Nikolentzos, G., Siglidis, G., and Vazirgiannis, M. Graph kernes:: A survey, Journal of Artificial Intelligence Research, 72:943-1027. 2021.
[54] Paty, F.P. and Cuturi, M. Subspace robust Wasserstein distances. In Proceedings of the 36th International Conference Machine Learning, pp. 5072-5081, 2019.
[55] Petric Maretic, H., El Gheche, M., Chierchia, G., and Frossard, P. GOT: An optimal transport framework for graph comparison. Advances in Neural Information Processing Systems, 32, 2019.
[56] Pham, K., Lee. K., Ho, N., Pham, T., and Bui, H. On unbalanced optimal transport: An analysis of Sinkhorn algorithm. Proceedings of the International Conference on Machine Learning, 2020.
13

---

[57] Piccoli, B. and Rossi, F. Generalized Wasserstein distance and its application to transport equations with source. Archive for Rational Mechanics and Analysis, 211(1):335-355 2014.
[58] Piccoli, B. and Rossi, F. On properties of the generalized Wasserstein distance. Archive for Rational Mechanics and Analysis, 222(3):1339-136) 2016.
[59] Rabin, J., Peyré, G., Delon, J., and Bernot, M. Wasserstein barycenter and its application to texture mixing. In International Conference on Scale Space and Variational Methods in Computer Vision, pp. 435 446, 2011.
[60] Rao, M. M. and Ren, Z. Theory of Orlicz spaces. Marcel Dekker, 1991.
[61] Sando, K., Le, T., and Hino, Tree structure for the categorical Wasserstein Weisfeiler-Lehman graph kernel. Transactions on Machine Learning Research (TMLR), 2025.
[62] Sato, R., Yamada, M., and Kashima, H. Fast unbalanced optimal transport on tree. In Advances neurul information processing systems, 2020.
[63] Séjourné, T., Feydy, J., Vialard, F.-.., Trouvé, A., and Peyré, G. Sinkhorn divergences for unbalanced optimal transport. arXiv preprint arXiv: 2019.
[64] Séjourné, T., Vialard, F.-X., and Peyré, G. Faster unbalanced optimal transport: Translation invariant Sinkhorn and I-D Frank- In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151, pp. 4995-5021. PMLR, 2022.
[65] Séjouréé, T., Peyré, G., and Vialard, F.-. Unbalanced optimal transport, from theory to numerics. Handbook of Numerical Analysis, 24:407-471, 2023.
[66] Song, Z., Wang, R., Yang, L.,, Zhang, H., and Zhong, P. Efficient symmetric norm regression via linear sketching. Advances in Neural Information Processing Systems, 32, 2019.
[67] Sturm, K.-T. Generalized Orlicz spaces and Wasserstein distances for convex-concave scale functions. Bulletin des sciences mathématiques, 135(6-7):795 (00,))0)9999,0---.- 2011.
[68] Tran, T., Tran, V.H.,, Chu, T., Pham, T., Ghaoui, L. E., Le, T., and Nguyen, T. Tree-sliced Wasserstein distance with nonlinear projection. In Forty-second International Conference on Machine Learning, 2025.
[69] Tran, V.-H., Chu, T., Nguyen, K., Pham, T., Le, T., and Nguyen, T. Spherical tree-sliced Wasserstein distance. In The Thirteenth International Conference on Learning Representations, 2025.
[70] Tran, V.-H., Nguyen, K., Pham, T., Chu, T., Le, T., and Nguyen, T. Distance-based tree-sliced Wasserstein distance. In The Thirteenth International Conference on Learning Representations, 2025.
[71] Tran, V.H.., Pham, T., Tran, T., Nguyen, K., Chu, T., Le, T., and Nguyen, T. Tree-sliced Wasserstein distance: geometric perspective. In Forty-second International Conference on Machine Learning, 2025.
[72] Tran, V.-H., Tran, T., Chu, T., Le, T., and Nguyen, T. Tree-sliced Entropy Partial Transport, In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025.
[73] Xu, H., Luo, D., and Carin, L. Scalable Gromov-Wassersen Wasserstein learning for graph partitioning and matching. Advances in neural information processing systems, 32, 2019.
[74] Xu, H., Luo, D., Zha, H., and Duke, L. C. Gromov-Wassersee Wasserstein learning for graph matching and node embedding. In International conference on machine learning, pp. 9932-6941. PMLR, 2019.
14

---

Supplement to "An Efficient Orlicz-Sobolev Approach for Transporting Unbalanced Measures on a Graph"
In this appendix, we provide further theoretical results and detailed proofs in $ Additionally, we give brief reviews on related notions used in our work, together with further discussions, and empirical results in B
A Detailed Proofs and Further Theoretical Results
In this section, we provide further theoretical results, and detailed proofs for all the theoretical results.
A.1 Further Theoretical Results
We investigate special cases for OST, alternative upper limit for Ag. and the limit case of N- N-function for entropic regularized Orlicz-EPT.
A.1.1 Special Cases for OST
We exam the special cases of OST when graph is tree.
Proposition A.1 (Relation of OST and a variant of regularized EPT). Under the same assumptions as in Proposition 5.5 and assume in addition that graph G is a tree, then
OS au, v) =d du, v):
where da is a variant of the regularized EPT in 136 Equation (9)].
The proof is placed in Appendix $A.2.14
Proposition A.2 (Relation of OST and standard OT). Under the same assumptions as Proposi- tion A.7 and assume in addition that ((G) = ((G) and b = 1, then
OS v) Wa (H,
where Wag is the standard OT with graph metric ground cost de.
The proof is placed in Appendix AA22.15
A.1.2 Upper Limit of Ae w.r.t. Entropic Regularized OT
With technical assumption that entropic regularized input is nonnegative for N-function + derive an alternative upper limit of Ag w.r.t. entropic regularized OT as summarized in the following proposition.
Proposition A.3 (Upper bound entropic regularized OT). We have + (D))
W (ū, 5 5 A (1 + (H( + (()) - 1]) (t, 21,
where (f, 0) is the entropic regularized OT between probability measures j., with ground cost defined as
I/ Lex c(x, ((x,v) dy) -HH(T))
(e,
inf 7Ell(a.0)
(19)
The proof is placed in Appendix 1A.2.16
A.1.3 Limit Case for Entropic Regularized Orlicz-EPT
We consider the limit case for N-function, i.e., ++()= 1, for 0E,,c similar to Proposition 5.6 for the original Orlicz-EPT.
The technical assumption is specified in the proof (5 A.2.16
15

---

Proposition A.4 (Limit case for entropic regularized Orlicz-EPT). For (tt) = t, and μ. V P(G), we have
o ( v) = ( (We.((,
bA),
(20)
where We.s the entropic regularized optimal transport (see Equation 19
The proof is placed in Appendix A.2.17
A.2
Detailed Proofs
A.2.1 Proof for Proposition 3.1
Proof. Consider the cost function on G follows:
(1 X)
if y G, if E and y = 8, if and y E G, if = S.
(z)
ट(z, v) =
(21)
w2
Additionally, for unbalanced measures we construct corresponding balanced measures jı == a + (( and i V + p(G) where measures jı, i have the same total mass (u(G)+v(G)) Let
(Ā, B) { E P(G G): (U) 70U G), (UU) 3( U) for all Borel sets U C G].
then following 440 Lemma A.8], we have
ET, = D).
(22)
where Wa(ū, D) is standard complete OT between two balanced measures jı and i (i.e., having the same total mass p(G) (G)), with cost defined
/ ((x,))((drddy)
Wa(a,
inf sEll(B,)) Ax
Moreover, from Equation 22 we have
(Tx v)
= -Wela, 8)
(M(G) v(G) We(d,
(23)
(((G)) + v(G) (Welft, BA)
(24)
KT(H,))
where the equality in Equation 24 is due to č(σ, y) c(xx bd for all x, E G.
Hence, the proof is completed.
A.2.2 Proof for Proposition 3.3
Proof. From the definition, we have
((x,))) (x)))))
A(t;A,0) = inf sell(p,0) Jex
(25)
t
Let 0 < 4 < ly < co, denote ni 7i, as the optimal transport plans of A(ti: A, A(tz; respectively. Then, have
A. D)
=/ene
Č(a,, y)
Al12; = fex6
dri, (s. v)
12
c(x, y)
$ faxc
+
dri (x. v)
ty
c(x,8) v)
<
dri (x. v)
Jext
4
= A(li; D).
where the second inequality is due to the strictly increasing property of the N-function + Hence, the proof is completed.
16

---

A.2.3 Proof for Proposition 3.4
Proof. The result is followed by the same reasoning in the proof for Proposition 3.3 where we leverage the strictly increasing property of the N-function & and the optimal transport plans for Ag.
More concretely, let 4 I l2 < oc, denote 7h 7t as the optimal transport plans of Ag A), D) respectively. Then, we have
Sexa f
((2,,)
Ac(12;0,
dr (I, (H(
12
((x,V) v)
drf (x, v) =H()
exc
t2
Jana
Ac(1;;,,)) (((x8)
drf, (a, 8) (H.)
41
Hence, the proof is completed.
A.2.4 Proof for Proposition 3.5
Proof. We provide the proof for the lower and upper limits for Ag as follows: For lower limit. From the definition in Equation (1O), we have
As La.0 ④ 11 - 8) R.D)
[Laee +
c(..u)
inf 5e ()
(
La.e
(-11)
Additionally, since N-function & is strictly increasing, we have
č(x, 4)
( (1+ = 1+
La.e 6-1 (1+E)
For convenience, given any [1 D). we define
/ 6x6
H())
(x) v).
(26)
From the definition of H in Proposition
3.4 for any 7y E 11( P). we have
f
H()) =
log 5(x y) y) 3) +121, Jexé
where the inequality is followed by using [19 Lemma 2.1.1] (i.e., H(()) 2 0).
Thus, have
Lae As x- R $ (1++) - = 1. The proof for the lower limit is completed.
(27)
For upper limit. For any 7/ E II( 1), we have
T = I Jex +
((x.y)
d7(x, =
② (Jence (d(a,
d5(rr w) =H(i)
t.
① (1// Ö(z, ((x,,)))(xx.)) v) cH()),
where we use the Jensen's 's inequality for the second row.
17

---

Additionally, for any 7 E [1(,, 2), we have
(() H(()) +1
H(A) + H(2) +1
H()) + (D)
where we apply Thus, we have
19 Theorem 2.2.1 and Theorem 2.6.5] for the inequality in the second row.
T T2 + 1 f c(z, ())(()))) E (H( + H 1)
(28)
Taking the infimum of y in II( D), we obtain
A (t: f, 0) + (twa(an -E (H(()) + H()) 1)
(29)
Therefore, by choosing t + [(A) H(D)-1I then we have
Weld.e)
We( D)
A ② (1 +e (H()) H(D) 115:) 2 1.
The proof for the upper limit is completed.
A.2.5 Proof for Theorem 4.2
Proof. For f E WL+(G, w), as in Equation 663 we have
/ ('(y)((d)) Vo E G.
f(x) = f(zo) +
[=0.a]]
Thus, following the Definition 4.1 have
OS sup f(=))e, f(z) v(G)
(UD) so Sc (Jionn ((w))((d)) (m(x) - u(x)) dx
Thus, we can rewrite OS (u, v) as follows:
sup (6W), Lo sous L (1ro ((oow(dss)) (u(z)-m(z)) v(x) de Olm(() v(G)
OSo
le (T ((wl(da) (u(x) - v(x)) Olm(G) - -GG))
sup JEWL
(30)
where recall that θ is defined in Equation [5]
Additionally, recall that the indicator function of the shortest path [zo, xr] is follows:
1 [o (2)
(
y E [zo.2]
(31)
otherwise.
We rewrite the objective function for the first term of OS in Equation 30 follows:
1/ (Mrom ((w))(d))) (m(x) - u(x))
/c | (1) (v) (m(xr) v(x)) (dy)da
.f [/e ()o (u(x)) - u(x)) de I' (()))((dy)
(32)
/ Iu(A())) - ( (d))
(33)
18

---

where we apply the Fubimi's theorem to interchange the order of integration for the second row, and use the definition of A in Equation (I) for the last row. Consequently. following 660, Proposition 10, pp.81] and notice that [|b blll"ll L.v for b > O, we have
sup feWLe (I,,),l) l So (rrnn (())s(d))) ) (u(x) - ((()) dx
{ bl((A())) -((())) ( w(dy)
sup
(GW).o 12. S1
= =115||
(34)
where f(x) = b((AA()))) -(A(x))) Vo G, and we write for the Orlicz norm of f with
N-function 4 160 Definition 2. pp.58] (i.e., see review in Equation 558 in BBI.3).
Moreover, following
60
Theorem 13, pp.69], we also have
/ (k ((o))) w(dr)
||
inf #20
(35)
Hence, putting these Equations
(30
34
35
together, we have
1
OS v) = inf
o
+ (lbblu - v(A(x)))) w(dr) + @lx(G) v(G)).
(36)
k>0 &
The proof is completed.
A.2.6 Proof for Corollary 4.3
Proof. Following Theorem
we have
OS = ())(() v(G) + inf
1 +
a (kb p(A(z)) - =(A(x))) w(dr) (37)
ES0
We next follow the same reasoning as in 41 Corollary 3.4] to compute the integral in 37 by an explicit expression.
For an edge e between two nodes u, o V of graph G. then u, u are also two data points RR as G a physical graph. For convenience, denote (u, v) as the line segment in RR connecting the two data points u, v. and (u, v) as the same line segment but without its two end-points. Therefore, we have (u, v).
Additionally, for any x E (u,v), Equation (I) for the definitions of A(z) and ye). Thus, we have
v), we have y (u, v) belongs to A(x) if and only if y Ye (see
A(r) \ (u, v) %e.
(38)
Consider the case where w is the length measure of graph G, we have w((x)) = 0 for every x E G. Consequently,
[ I o (bO)l(())))) u((())) (dxx)
Σ
/ $ (Hbba(A(z)) ~(((<)))) (39)
(0,0EE (a,e)
Additionally, for measures supported on nodes V of G, and using Equation (38 then we have In(A(z)) v(A(z)) = [μ{A(x)) \ (u, v)) v(A(x) (u, w))l = lm(r)) (Yeel. for every edge (u,2) v) E E of graph G.
19

---

Therefore, we can rewrite the identity
39
as follows:
Je (kb (((()))
E I (kbl (kblu((7e) v(reell w(dz).
((A())))
t= (u,)))E (a.v)
Σ
+ (kb (all)(ee)) -m()))) S w(dx)
(0,D)E
Σ
Wp & (kb (u(T)) - v(26))).
EEB
By combining with 37 we obtain
OS
+
Σ CE
we + (kblal(Te) v((e)l).
Hence, the proof is completed.
A.2.7 Proof for Proposition 5.1
Proof. The proof for each property on geometric structure of OST is as follows:
i) The result is directly followed from Equation [14 Theorem 4.2 with the observation that
(m(G) vG) (mu o)) (v + +G)
and
[<A(z)) v(A())) 1( o) - (v (v+))
ii) From Definition
4.1 choosing / - 0, then Up and for any p, P(G), have that O 2 0.
Assume that OS4. (1, (u, 0. Then, from Theorem 4.2 we obtain
Olu(G) vG) + inf
1 JG
(kb (kblp(A(z)) (A(z)))
k>0
Additionally, for S a < 2
bA
min(w1(2o), w2 w2(20)} we have > O. Consequently, we must have
m(G) v(C) and
inf
1
2 (K6 (((()((()) - - -(((()))) = 0.
k>0
k
Thus, (<A(z)) = (((())), Vr G.
By applying 40 Lemma A.9] it leads to V.
Moreover, from Definition 4.1 we also have OS4.o (1, u) O.
Furthermore, for any feasible function Uv.a, we have
[ [())p(dx)) / ((r))(dr)
f [())((d))) [(x))(da))
[/ f(x) I f(z)v(d))
SSS (1, +
Therefore, by taking the infimum for Uw it implies that
& v) < ( + (S,
Hence, OS,,a satisfies the triangle inequality.
iii) With an additional assumption wi (2o) = wy w2(22)). (2o). then for any function f E Uv.av we also have (-f) E Uw
Therefore, from Definition we obtain OS (M, u) (
Thus, together with results in ii), we have OS.,a is metric.
In B.1.6 (emma B.3 review the Lemma A.9 in Le et al. 40
20

---

A.2.8
Proof for Proposition 5.2
Proof. For (GG) v(G) and b 1, then following Theorem 4.2 for OST and 41 Theorem 3.3] for
GST, we have
OS (p, = inf
1 1 (I (e(p(())) -)(A(=)) w(dx) = =GS((H,
150
The proof is completed.
A.2.9 Proof for Proposition 5.3
Proof. For (C v(G), 1, by applying Proposition 5.2 we have
OS+.a (14, v) GS
(40)
where we recall that GS is the GST for balanced measures on a graph.
Additionally, for 1 < < oo and N-function (t)) (m-1)e-1 EP, by leveraging 41 Proposition
4.4] for the connection between GST and ST, we have
GS*(p,v) Sp(,,)).
(41)
Therefore, by combining Equations 440 and we obtain
OS (u, v) vp(u,v)
The proof is completed.
A.2.10 Proof for Proposition 5.4
Proof. For N-function (t) (p-1)² to with <p oc, from Theorem 4.2 we have p"
= v(G))
infa>o 1 (1 (1+
kPb (((())( v(A(x)) w(xx)) (42) (1-1)p-1 pd
For convenience, for l > 0, let
T(k) =
1)1-1
1-1
(u(A())) - v(Ax))) w(dx),
p2
i.e,, the objective function of the univariate optimization problem for OS
We next consider two cases:
Case 1: Ig [[A(z)) v(A(x))) w(dx) = Then, we have
inf T(k)
inf O.
k20
k30
Consequently, from Equation (42 we have
- ( (ddz) O)u(G) -(G)
(()(())))))((()----)))))))) (G))=
=US
Case 2: Ic [())) w(r) # 0. Then, we have
lim + J: k-++
T(k)
lim T(k) +o0.
Therefore, Equation
42 we have
OS (). =
- -vG)) (Tko),
(43)
21

---

for some finite number ku E (0, +oo) satisfying (ko) = 0. Additionally, have
(k)
1.2 + (p- (
) 2p -(A(())))(A(())))) w(dx).
Consequently, by solving the equation (ka) w.rt. Ko. we obtain
Ko P-1 (Ja (m(((=)) - (A(x))) (((x))) #
Therefore, by plugging this value ko into T, we have
T(ko)= Ko 1 (p-
1)p-1
kgD0 / Im(A(O)) - ((A()))) w(dz)
pp
(Lo |I((A(=))) -((x))) - w((x)))))()))))) )(a))) $ x
p p-1 b
1 (p 1)P-1
by (Je Iu(A(=)) v(A()))] w(dx)) 1P /
w(dr)
(p-1)p
p
- u(A())) ((dx))
Thus, by plugging this value of (ko) into Equation 43 we obtain
( INAAGE - v(Axx)) w(dr)
OSa,a(1,V) Olp(G) v(G) + (G)) UUS v).
Hence, we have shown that OS (1,, v) US p.aa (1, v) in both cases.
The proof is completed.
A.2.11 Proof for Proposition 5.5
Proof. Following Corollary
we have
+ inf
1+
w. ( ((=)))
AS0
cEE
For (1) = I, then we have
OS =0)(() v(G) inf
1
1+ 1+ (ockbll(Te) - v(12))
8>0 h
1
-0)x(C)-
(G))+ inf
+
Σ
woblup - -M(Te)
ESU k
=lm(G (G) + Σ
Wh (m(Te) v(je)l-
eEE
Hence, the proof is completed.
22

---

A.2.12 Proof for Proposition 5.6
Proof. From Equation 8 we have
(1,, (m(G) +(G) (Wo(i, 12).
For (t) t, we further have
t 1>0: 0: / jaxé
((x,V) d5 v) s1]
(o( D)
inf inf
Then, the infimum (t", satisfies
Sene ((22y) (x, =1.
Therefore, obtain t" = Jêxo 6( y)d7" = We(ú,
Hence, we have
(E (m(G) + +v(G)) (Wel(,, B) bA)
= -)
The proof is completed.
A.2.13 Proof for Proposition 5.7
Proof. For (() p from Theorem 4.2 have
1+ / kb ((A(x)) =(A(z)) w(xx)
OS v) O)((G) - - -(G) + inf
k2O &
= =O]p(G) - v(G) + inf + b [ (m(A(z)) v(A(=)) wdxx)
1
A3O k
(l)(G) uGG b / (((())))v(A()))) (dx>)
USS.o p.a (p, v).
Additionally, for (t)) t, from Proposition 5.6 we have
O8 (1. = KT(H,
With additional assumptions that À 2 0 and the nonnegative weight functions w1, wy are b-Lipschitz w.r.t. dg, then by applying [40] Corollary 3.2], we have
(E+(u,v) KT v) ET (
Consequently, for a = 0, and the length measure w on G, then following 40 Proposition 5.2), we have
by OS0.a 0E((U,)) v) (p(G)+v(G))
The proof is completed.
A.2.14
Proof for Proposition A.I
Proof. From Proposition 5.5
we have
OSHalu,,v = (Ip(G) + Σ cEE
we (u(T)) - v(ye)l
(44)
-USia (M, v).
(45)
For the case when G is tree, then following 40 Proposition 5.3 i)], we further have US (n, v) da (1, v).
(46)
Thus, from Equations 44 and (4).. we have
OS, = da (14.
The proof is completed.
23

---

A.2.15 Proof for Proposition A.2
Proof. From Equation (44) in the proof of Proposition A.1 we have
OS4,a (1, 1/) 1, (H, v).
(47)
Additionally, when G is tree, and with additional assumption that ((G) =vG), by applying [40 Proposition 5.3 ii), and notice that p = 1 and = 1, we obtain
us a, (1, v) = Was (p, v),
(48)
where recall that Wa, the standard optimal transport with graph metric ground cost de. Hence, from Equations
47 and 48
get
(S Was V).
The proof is completed.
A.2.16 Proof for Proposition A.3
Proof. Following [19 Theorem 2.2.1] and definition of conditional entropy 19 any 7 [1((,,)), D), we have
Equation 2. 10], for
H((9) 1 (H( H(()))
(49)
H(5) +1 (H(A) + H((D) +1
(50)
2
H(9) 2 2 ((()) + H())),
(51)
where we recall that H. and are defined in Equation 26 and Proposition 3.4 respectively,
Therefore, as in the proof for Proposition 3.5 in A.2.4 from Equation 28 we have
T 2 + Jexa ((., (o
- (H()) + H(D) -
(52)
2 + (L a(x, (z,,)) -) =H)))) E (H( ((OO)) (H H()) 1)
(53)
where we assume that the entropic regularized input of N-function & is nonnegative in the second row (Fquation (53)). i.e.,
Sene E(0, (1,,8)d((z,))) - =HH(?) + 2
(H(A) + H(D)) 2 0,
for any 5 E M(a, D).
Taking the infimum of 7 in I), we obtain
A (t: (t:A,0) D) 2 + We(A, D) + e (H(P) + H(D))) -e (H(()) + H(D) -
(54)
5 & then we have
Therefore, by choosing
We 0) + 5 (H + H(D))
A
② 1- H()) 11) (..0 2 1.
The proof is completed.
24

---

A.2.17 Proof for Proposition A.4
Proof.
We use the same reason as in the proof for Proposition 5.6 From Equation 11
we have
(,, = (a(G) + v(G) (Wir,e (1, bA).
For ((t) = i, we further have
((x,,)) di(a,, - =
(R. inf inf t> 1>00 0: SEll(P.))
fxt
Then, let %/g is the optimal solution for the entropic regularized OT
Veec Č(x, ((dx,) dy) - sH(
(a, SEtT(P.))
inf
Thus, for the infimum (2), we have
J
(x,y)) 1"
d5c (2, 3) = 1.
Therefore, we obtain
1" / ((2,))d We,c D).
Bxb
Hence, we have
(p) (v(G)+++(()))) (We, -D))
The proof is completed.
B Brief Reviews, Further Discussions and Empirical Results
In this section, we give brief reviews on important related notions to our proposed approaches. We next give further discussions several aspects, and provide further empirical results.
B.1 Brief Reviews
We provide brief reviews on important related notions to our proposed approaches.
B.1.1 Sobolev Transport (ST)
We briefly review main notions for Sobolev transport (ST) 39 for probability measures on a graph.
LP functional space. For nonnegative Borel measure on G, denote LP) as the space of all Borel measurable functions f G - R such that Se ff)) Pu(dy) < co. For p co, we instead assume that f is bounded w-a.e. Then, I.P w) is normed space with the norm defined by
|| ( ((w)))((d))) for Sp<
and for p [[ = inf inf R [f(z) < for waee G).
Functions fı, LP(G,w) are considered to be the same if (i f2(x) for w-a.e x G.
Let w be a nonnegative Borel measure on G, and let 1 S co. A continuous function f G + R. is said to belong to the Sobolev space W-I-P w) if there exists function h E (GG,ww) satisfying
Graph-based Sobolev space [3
f(x) - f(z)) f(z0)= [so.a]
(dy)
E.
(55)
Such function is unique in TP(G, w) and is called the generalized graph derivative f w.r.t. the measure The generalized graph derivative of f E WlP w)) is denoted f' (G,,w)..
(G,w)
25

---

Sobolev transport (39]. Let be a nonnegative Borel measure on G. Given 1 p < oc, and let p' be its conjugate, i.e., the number p' oo] satisfying ; + supported on graph G, the p-order Sobolev transport (ST) 39 Definition 3.2] is defined as
For probability measures μ.,
sup [e f())u(dx) Js [())
sp(u,))=
(56)
s.t.fe W 1I. ( $
where write f' for the generalized graph derivative of f. W for the graph-based Sobolev space on G, and L (G, for the I.P functional space G.
B.1.2 Length measure
We briefly review the length measure on graph G in
Definition B.1 (Length measure [39]] Let w" be the unique Borel measure on G such that the restriction of w' on any edge the length measure of that edge. That is, w" satisfies:
For any edge connecting
nodes and v, have w" ((r, I = (1 s)u + su and y = (1 t)u + to for s, t [0,1) with s S t, where recall that (x, y) denotes the line segment in e connecting and y.
s)w, whenever
ii) For any Borel set C G, we have
w wG(G)= Σ (Gnee. eEE
Lemma B.2 (w" is the length measure on graph (39). Suppose that G has no short cuts, iee, any edge shortest path connecting its end-points. Then, w is length measure in the sense that
w ([z, vl) = dc(x,y)
for any shortest path (z. v] connecting Particularly, w" has alom in the sense that wt ((x}) O for every x E G.
B.1.3 Orlicz functions
We describe brief review on Orlicz functions summarized in 41 for completeness. Please see 60), for in-depth studies on Orlicz functions.
A family of convex functions. We consider the collection of N-functions 2 $8.2] which are special
convex functions on R,, Hereafter, a strictly increasing and convex function [0, oc) [0, 20)
called an N-function lim t = O and lim4-++00
((t)
((t) +00.
Examples of N-functions.
Some popular examples for N- N-functions 2 $8.2] are
1. (() = (P with 1 < < co.
2. (()) exp(()
1.
3. (() = exp(IP) with 1 < p < co.
4. ((t) (1 + t) log(1 +
For Luxemburg norm. For Luxemburg norm (see Equation (2) for Orlicz functional space, the infimum in its definition is attained (2] $8.9].
Complementary function. For fufuntioon 4 its complementary function V R. + R. 2 $8.3] is the -fuuccton, defined as follows
v (t) sup lat 4(a) | 0], for 2 0.
(57)
26

---

Examples of complementary pairs of N-functions. Some popular complementary pairs of N-
functions 2 $8.3]. 660 $2.2] are as follows:
1. (t) = 1" and (t) = where is the conjugate of p. ie., + and < < co.
2. (() (x)(() - ( and (1) = (1 + () log(1 + () L.
3. For the .N N-function (t()) = exp(t") with < p < oo, its complementary N-function
yields an explicit for, but not simple [60] $2.2], see 41 $A.8] for the detailed derivation of the complementary N-function.
Young inequality.
Let O V be pair of complementary N-functions, then we have
st S (s) + +(t).
Orlicz norm. Besides the Luxemburg norm, the Orlicz norm 60 $3.3, Definition 2] also popular norm for Lo (G, defined as
l == sup { {f [(())(())(((z))
/ (1((x)))((c)) s $1).
(58)
where is the complementary N-function of +
Computation for Orlicz norm. By applying (60] $3.3, Theorem 13], we can rewrite the Orlicz norm as follows:
(+ / @ ((+(s())))(dz))
||ll inf K5O T
Therefore, one can use any second-order method, egg., fmincon solver in MATLAB (with trust region reflective algorithm), for solving the univariate optimization problem.
Equivalence [2] $8.17) (50, $13.11]. The Luxemburg norm is equivalent the Orlicz norm. In fact, we have
Il s ll 2 2
(59)
Connection between L and La functional spaces. 1 1<p< < oo, we have
When the convex function + tP, for
IP(G,w) (G,
Generalized Hölder inequality. Let + v a pair complementary N-functions, then general- ized Hölder inequality w.rt. Luxemburg norm 2 $8.11) is as follows:
I f(z)g(z))(dz)) s 2 fIfll ll
(60)
Additionally, we have the generalized Hölder inequality w.r.t. Luxemburg norm and Orlicz norm $13.13] is follows:
50
V (())(())((d)) s 11 llgllo.
(61)
B.1.4 Wasserstein Distance and Orlicz Wasserstein (OW)
We briefly review p- Wasserstein distance with graph metric cost, and the Orlicz Wasserstein (OW) for probability measures on graph.
Wasserstein distance with graph metric cost. Given 1 S oo, and probability measures y and supported on graph G, then the p-order Wasserstein distance is defined as follows:
Wp(u.v) = ( inf
L
(SEIK)R.)) Sexe do(x, (dæ,, dy)
where M( v) = (1 E(GGXG) 71 =1, 7/ = v) and 71, 72 are the first and second marginals of y respectively.
27

---

Orlicz Wasserstein (OW). Following Guha et al. (28) Definition 3.2], the OW with the N N-function for probability measures j.v supported on graph defined as follows:
W) inf inf 0: x
(de(x,))
2T(x,
dT(x,, 2) s $1].
(62)
GXG
where recall that 11( 2) is the set of all couplings between μ and
B.1.5 Generalized Sobolev transport (GST)
We briefly review main results on generalized Sobolev transport (GST) 41 for probability measures on graph.
Graph-based Orlicz-Sobolev space Let & be an N-function and be nonnegative Borel measure on graph G. A continuous function f G + R is said to belong to the graph-base based Orlicz-Sobolev space WT. (G. w) if there exists a function h E T. (G,w) satisfying
ff h())
f(x) f(zo) = [oo.al
E G.
(63)
Such function h is unique in L (G, w) and is called the generalized graph derivative of w.r.t. the measure w. This generalized graph derivative of f is denoted as f".
Let & be an N-function and w be nonnegative Borel measure on G. For probability measures μa, v on a graph G, the generalized Sobolev transport (GST) is defined as follows:
Generalized Sobolev transport (GST) 41].
sup f()))((d))) - -o fo f(z))(dz)) s.t. fE WEWLWG ll 1,,
(p,
where is the complementary function of 4 (see
B.1.6 Unbalanced Sobolev transport (UST)
We give a brief review main results of unbalanced Sobolev transport (UST) 44 for measures graph, possibly having different total masses.
The regularized set Ug for critic function 40) For S S oe and 0 < < [ + wi(=0) +
w2(2))), let Uh be the collection of all functions f E W. (G, w) satisfying
f(20) E Ta = --w02(0)
[ (22(20)
6Λ
+ a wi (20) + 2 a
2
and
1f (G,w) b.
Equivalently, Ug is the collection of all functions f of the form
f [ hdy)w(dy)
f(x) s
(64)
with La and with h: G + R being some function satisfying
[ (G.w) I b.
Unbalanced Sobolev transport (UST) 440 Let be nonnegative Borel measure on graph G. Given 1 < S oo and 0 < a [bλ (2o) + w2 (z(=))]. For unbalanced measures μa, P(G). the unbalanced Sobolev transport (UST) is defined as follows
V. f(x))(dx)) -s. (())vla))
us (,,,)a
sup fEUs
For simplicity, also use uS, for the p-order UST when the context for a is clear.
28

---

Equal measures on a graph [40].
Lemma B.3 (Lemma A.9 in 40). For unbalanced measures μ., P(G), then and only if ((A(z)) = v(((z)))))))))))))))))))())))v for every a G.
B.1.7
Regularized EPT and Distance da
We briefly review main results for the regularized EPT and distance da in [36 for probability measures on tree T.
Regularized set of critic functions 36 Let Tae be collection of all functions of the form
/ [iae]
f(z) = +
(())wddy)
where is the tree root, and is constant in the interval with I S b.
(-wg(r) - b2 + wr)r) and
Regularized EPT (36.. For unbalanced measures μ, v supported on tree the regularized EPT is defined as follows:
ET (T,)) = sup { f(u v): f La } --
( ([((())((T))
(65)
Following 336
Proposition 3.8), have
ET (1, v) | In(A(z)) (A(x))) - 11 [u(T) + u(T)] + [ws(r) + bd
2 - -a]lu(T) - x(T)
2
with p() (T) and i 2 (T) v(T).
Distance da (36]. We briefly review the definition of distance d, in 36
da( [M) + bd 2 [M(T) (T)).
(66)
Following
336 Proposition 3.10), the distance d, a metric.
B.2
Further Discussions
We give further discussions and details for various aspects in our work. For completeness, recall important discussions the graph in [39 (for Sobolev transport for probability measures), since these discussions and results are also applied and/or easily adapted for our proposed approaches.
Further details for the computation of Orlicz-EPT and OST. computation for Orlicz-EPT and OST.
We describe further details for the
For Orlicz-EPT. Following the theoretical ground derived for the computation of the entropic regularized Orlicz-EPT, i.c., the objective function is monotone non-increasing (Proposition 3.4). and the lower and upper limits for the objective functions (Proposition 3.5), one can compute the entropic regularized Orlicz-EPT by binary search algorithmic approach. For completeness, straightforwarddy describe the pseudo-code for Algorithm I Additionally, notice that we can leverage Proposition A.3 in AA.1.2 to alternatively set the initial value for t in Algorithm [ (line 3).
For OST. For popular N-function, is easy to derive its gradient and Hessian for the objec- tive function of the univariate optimization problem. Therefore, in our experiments, we leverage the fmincon MATLABB solver with the rrust-region-rellecte algorithm to solve the univariate optimization problem for OST computation.
29

---

Algorithm Compute entropic regularized Orlicz-EPT OE
Input:
Input measures μ. v, function 4, graph parameters b, X, E, and stopping threshold entropic regularized Orlicz-EPT a (p,
Output:
Construct G G U (&) and corresponding nonnegative cost function ($3
Construct corresponding probability measures f +[G)+v(3]
,+ and (())
G
We(a.)) Set F... and tt ([-==)00)--000
[1-=]
while 4 - l do
Set tm tett.
Compute fm At
if' fm < then
Set bm if fm = then Break
10
else
11
Set te = tm
Return 08 (H, v)) (m(G) v(G)) (tr 6A)
65
66
E1
466
P5
02
C10
C7
310
611
C15
e12
e4
62
14
613
T8
Eg
37g
68
C3
373
......, F10) Figure 4: A geodetic graph illustration. The set of nodes V has 10 nodes, i.e., V {x1, (2,, The set of edges E has 15 edges, i.e., F = {C1, ...... C1s} where each edge weight/length is set one, i.e., We, 1, for S 15. For any 24, 2G, there is a unique shortest path between them, with length 2. Let æ1 be the unique-patt root node (i.c., 20 x1) and G be subgraph containing nodes (at, za, x and 2 edges (012,615), then we have A(xa) = 7(8)) C.
Further discussion on Orlicz-EPT and OST. Following Proposition 5.2 we can view OST as an
extension GST [41] for handling unbalanced measures, and Orlicz-EPT for unbalanced measures. Notably, when the input measures have equal mass (i.e., p(G) = v (G).
extension of OW 667
and b = 1, Orlicz-EPT reduces OW. Furthermore, Orlicz-EPT shares the same computational complexity as OW, as shown in Equation
(). It is worth noting that GST is a scalable variant of OW for balanced measures, in the same sense, OST can be seen as scalable variant of Orlicz-EPT.
As a result, Orlicz-EPT applicable for all applications OW and extends OW to handle unbalanced input measures, whereas OST may not reserve all the properties of OW.
Like OW, Orlicz-EPT involves two-level optimization problem, limiting its applicability to small- scale domains. In contrast, OST, similar to GST, is scalable and can be applied to large-scale domains.
Illustrations for notations on graph. We illustrate notions on graph in our work in Figure 4
Geodetic graph. Recall that for graph, for every pairs of nodes, the shortest path between them is unique, then it is called geodetic graph [39]. Therefore, geodetic graphs are special examples
30

---

satisfying the uniqueness property of the shortest paths 2 We give an illustration of geodetic graph in Figure 4
Path length. As discussed in 39 can compute path length connecting any two points I, E G, where the points z, y are not necessary to be nodes in V (but even for any point on an edge well). Indeed, for the points x, y E IR belonging the same edge (u, v), connecting two nodes u, U E V. We have
x (1 8)u + sU,
y (1 t)u + tv:
for scalars 1,8 j0, 1]. Thus, the length of the path connecting x; y along the edge e (i.e., the line segment (x, v)) can be computed by [ 8|Uee
Consequently, the length for arbitrary path in G can be computed by breaking down into pieces over edges, and then summing over their corresponding lengths [39
Extension measures supported on G. For the discrete case, similar to ST 39 OST is
extendable for measures with finite supports on G. i.e., measures which may have supports on edges, by following the strategy to compute path length for points in G. Precisely, break down edges containing supports into pieces, and then sum over their corresponding values, instead of the sum over edges as in (17) for OST.
About the uniqueness property of the shortest paths on G. As discussed in [39] note that edge length a real nonnegative scale, w. 2 for any edge E' in G., it almost surely that every node in V can be regarded as unique-path root node since with a high probability, lengths of paths connecting any two nodes in graph G different.
Moreover, for some special graph, c.g., a grid of nodes. there is no unique-pate root node for such graphs. However, by perturbing each node (or also perturbing edge lengths in case G is non- physical graph) with a small deviation, the perturbed graph will satisfy the unique-path root node assumption.
For continuous case, when measures are extended to support on G. and input measures are fully supported, then for some finite special nodes where there are multiple shortest paths, we fix one of the shortest paths to those points, and treat it as the chosen shortest path for those special points. However, for practical applications, the number of supports are finite, which bypasses the mentioned issue.
For the given graph setting. As in (39 we assume that the graph metric space is given. The question to learn an optimal graph metric structure from data is considered in this work and leave for future investigation.
Measures on a graph. In this work, we consider OT problem for two input unbalanced measures supported on the same graph. See (40) for the same problem setting.
The proposed approaches, Orlicz-EPT and OST, are for input unbalanced measures, i.e., to compute the distance between two unbalanced measures, on the same graph. We distinguish our considered problem to the following related problems:
Compute distanccs/diseerppaneiss between two (different) input graphs. For examples, [55] 22
compute distance/discrepancy between two (different) inpul graphs. They are essentially different to our considered problem which computes distance between two impul probability measures supported problem for
on the same graph. In particular, Le al. (38] consider a variant of Kromov-Wassersee two input probability measures, but possibly supported on different tree metric spaces.
Compute kernels between two (different) input graphs. Graph kernels are kernel functions between two input (different) graphs to assess their similarity. See [10
34 53 for comprehensive proposed approaches to compute distances
reviews graph kernels. Essentially, it is different between two input unbalanced measures on the same graph.
For (variational) OT problems on graph. OT problems for measures supported on graph metric space have been explored in previous studies [T9 Additionally, Le et al. [43] have recently studied variational OT problem, e.g., Sobolev IPM where the critic function is constrained within
31

---

unit ball of Sobolev norm involving both the critic function and its gradient, for graph based measures, Notably, graph metries extend tree metrics, which are utilized in scalable optimal transport methods like tree-sliced Wasserstein (TSW) 37
69 TSW, in turn, generalizes the The graph structure offers greater flexibility and degrees of freedom compared to the tree structure in TSW and the line structure in SW. For more in in-depth discussion on the motivation for OT on a graph, please refer to
70
68
71
popular Wassersenn (SW) approach [59] 9 51
Persistence diagrams for TDA. Persistence diagrams (PD) multisets of data points in R?, containing the birth and death time respectively of topological features (c.g., connected component, ring, cavity), extracted by algebraic topology methods (e.g.. persistence homology) 23
Graphs GLog and GSrrt (39.. For completeness, we review the construction for graphs Glog and Gsgi in [39]. We utilize the farthest- point clustering method to cluster supports of measures into at most . clusters. Then, let the vertex set V be the collection of centroids of these clusters, i.c., graph vertices. For edges, we randomly select (M log M) edges, and 3/2 edges for graphs Goog and Gsan respectively. Let be the set of those randomly sampled edges. For each edge its edge length/weight we is computed by Euclidean distance between the two corresponding end points (i.e., corresponding nodes of edge e). Let n. be the number of connected components in G(V, EV. We randomly add (n. - 1) more edges between these ne connected components to form a connected graph G from &. Let E. be the set of these (n. - 1) added edges, and denote set E = E U Ec, then GV, E) is the constructed graph.
Further discussion on graphs in experiments. For all datasets, except MPEG7 dataset, Gsyt consists of 10K nodes and 1 million edges, while GLog comprises 10K nodes and 100K edges. Due to the smaller size of the MPEG7 dataset, we constructed GSqn with IK nodes and 32K edges, and GLog with IK nodes and 7K edges.
Datasets and Computational Devices. For the datasets in experiments, can contact the authors of Sobolev transport 339 to access to them. Additionally, all of our experiments are run on commodity hardware.
In our experiments, we demonstrate the effectiveness of our approach in document classification on four real-world datasets and topological data analysis (TDA), including orbit recognition for linked twist maps, i.e., discrete dynamical system modeling flows DNA microarrays (31, and object shape recognition in MPEG7. These evaluations on document classification and TDA are often used for tasks involving comparing measures on a graph, see 39 We believe that such experimental coverage is rich and diverse enough.
Hyperparameter validation. We use the same validation as in [40] Precisely, we further randomly split the training set into 70%/30% for validation-training and validation with 10 repeats choose hyper-parameters for the experiments.
Further discussion on hyperparameters. The performance of OST/Orlicz-EPT typically depends on the choice of the N-function Φ. similar to how kernel functions impact performance in kerne-- dependent machine learning frameworks. In our experiments with N-functions & and ob ($7). we observed slightly different performances. Similar findings have been reported for GST 41.
Determining the optimal N-function + for OST in given task is open problem that warrants further investigation. We leave it for future work. As an interim solution, cross-validation can be used select & from set of candidate functions.
Regarding the regularization weight b, we used b = 1 in our experiments based on the results in Propositions 5.2 and 5.3 as well as for simplicity. This choice of b is supported by theoretical results on EPT on a graph 40. Lemma A.6, Remark 4.8] and has been used previous experiments for
EPT 36 40).
For a, from the result in Proposition 5.7 and for simplicity, we use a 0 for experiments. Such value for is also supported by theoretical results of EPT on graph 44 Lemma 4.4, Proposition
5.2] and used experiments for EPT 36 40) Additionally, recall that I,, is the largest interval
when a 0.
32

---

approach Table 1: The number of pairs for SVM.
Datasets TWITTER
#pairs
4394432
RECIPE
8687560
CLASSIC
22890777
AMAZON
29117200
Orbit 11373250
MPEG7
18130
The number of pairs for kernel SVM 41). Denote Ntr, Nte for the number of measures used for training and test respectively. For the kernel SVM training, the number of pairs for computing the distances is (N,, - 1) Ntr For the test, the number of pairs for computing the distances is Ner Nie- Thus, for each rum, the number of pairs for computing the distances for both training and test is totally Nr, x (Nay- + Nee). In Table we summarize the number of pairs which we need to evaluate distancee/diserpaaccies for SVM in each run to illustrate the experimental scale, e.g., more than 29M pairs for AMAZON.
2.
Debiased approaches for (Sinkhorn-based) UOT 65
We review the discussion and evalua- tion in 44) for the debiased approaches for "Sinkhom-based UOT in 63 65], with the same setup as in our experiments. As noted the main text, the debiased version for Sinkhorn-basee for UOT [26 63 which may be helpful for applications, and the debiased version is empirically indefinite. Both UOT and debiased version have the same computational complexity.
Empirical results for the debiased version 663 65 are given in 40 Figures 41-44]. As in [40]. the debiased version improve performances of UOT in some datasets, especially for datasets in TDA tasks (Orbit t and MPEG7). For document datasets, performances of the debiased version and UOT are comparative, i.e., the role of debias property is not clear for advantages in applications.
Broader impacts. In this work, we propose novel approaches to extend OW/GST for unbalanced measures graph. The proposed Orlicz-EPT is directly derived from standard OT, bypassing chal- lenges raised from unbalanced measures, as in OW. Additionally, we formulate a novel regularization approach, resulting in the proposed OST, which is efficient in computation. Therefore, our proposals pave the ways to use OT approach endowed with Orlicz geometric structure for applications with unbalanced measures, which is common real- world scenarios. To our knowledge, there is no foresee negative social impacts for our research.
B.3 Further Empirical Results
Further empirical results on graph GLog- We provide corresponding results in
7 for
graph GLog-
In Figure compare the time consumption of OST and Orlicz-EPT with oo 11 D2 graph Log
In Figure 6 we illustrate the SVM results and time consumptions of kernels on document classification with graph GLog-
In Figure we illustrate the SVM results and time consumptions of kernels on TDA with
graph GLag-
Further empirical results for different hyperparameters and a. We carry out more additional experiments for different b, a. The results for average accuracy, and the standard deviation (in the parentheses) are as follows:
For document classification.
We present further SVM results for document classification on TWITTER dataset with graph Gsqit and different hyperparameters and in Tables 2 and respectively.
We present further SVM results for document elassification on TWITTER dataset with graph Gog and different hyperparameters b and in Tables and respectively.
33

---

Orlicz-EPT
10
OST
Time consumption
10a
10a
10
10
+(1)
(()=exp(t)---11
+(0=exp(()11
Figure 5: Time consumption on graph G
TWITTER (3/3108/26)
RECIPE (15/4370/340)
CLASSIC (4/7093/197)
AMAZON (4/8000/884)
0.73
0.55
0.98
0.72
0.94
0.71
0.5
0.92
Average
0.7
0.9
0.69
0.45
0.88
0.88
Time Consumption (8)
10
10a
105
10
10
10
10
10
10a
10a
10
Tree
regEPT-Tree
OST-60
OST-
OST-
Figure 6: Document classification on graph GLog
For TDA.
We present further SVM results for TDA MPEG7 dataset with graph Gsgn and different
and hyperparameters b and a in Tables and 7 respectively.
We present further SVM results for TDA on MPEG7 dataset with graph GLog and different hyperparameters b and in Tables g and respectively.
We observe that turning these hyperparameters b and e.g., via cross-validation, may help to improve the performances further.
Table SVM results document classification on TWITTER dataset with graph GSyn and different hyperparameter b.
2
b
0.5
71.66 + 0.63
72.03 + 0.56
72.12 + 0.57
b= 2
71.54 + 0.49
72.15 + 0.42
72.28 + 0.34
34

---

Orbit (5000:300)
MPEG7 (200/80)
Average Accuracy
0.3
0.2
Time Consumption
109
10"
10
UOT
Tree
regEPT-Tree
OST-48
OST-
OST-
Figure 7: TDA graph Glogg
Table SVM results for document classification on TWITTER dataset with graph Gsqr and different hyperparameter
22
a 0.1
71.48 0.43
0.55 72.34
72.64 = 0.50
a = 0.2
71.64 0.50
72.12 + 0.36
72.27 + 0.30
Table 4: SVM results for document classification on TWITTER dataset with graph GLog and different hyperparameter b.
Pp
2
b 0.5
70.97 + 0.29
71.74 + 0.33
71.78 + 0.41
b= 2
71.58 + 0.41
71.92 + 0.16
71.96 + 0.22
Table SVM results for document classification on TWITTER dataset with graph GLog and different hyperparameter
Pu
Φ2
a 0.1
71.57
0.23
71.87 E 0.36
72.04 1 0.28
a 0.2
71.59
+ 0.35
71.74 E 0.22
71.95 = 0.19
Table 6: SVM results for TDA on MPEG7 dataset with graph Gsgn and different hyperparameter b. +
4p
42
b = 0.5
66.67 3.45
71.67 + 5.40
68.83 + 3.09
b 65.00 + 3.58
69.13 3.87
67.33 + 3.55
Table 7: SVM results for TDA on MPEG7 dataset with graph GSqn and different hyperparameter +
40
42
0.1
66.43 4.81
70.47 4.51
68.50
4.54
a 0.2
66.82 + 4.01
68.43 + 4.63
69.17 + 3.60
Table 8: SVM results for TDA on MPEG7 dataset with graph 4
GLog and different hyperparameter b.
4p
4 68.67 + 5.61
b = 0.5
65.87 + 5.68
67.00 - 5.60
b 65.93 + 5.11
68.91 + 6.00
66.17 + 4.60
Table 9: SVM results for TDA on MPEG7 dataset with graph Grag and different hyperparameter a.
4
42
0.1
65.94 + 4.19
67.83 + 5.83
66.46 - 4.58
a 0.2
65.84
5.45
69.61
5.56
69.86 + 5.22
35

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The proposed Orlicz-EPTi is presented in where revisit the EPT problem, leverage Caffarelli & McCann [2] s insights to reformulate EPT as a corresponding standard OT. By carefully calibrating the ground cost of the corresponding standard OT, guarantee that its ground cost nonnegative, which essential to develop Orlicz-EPP a variant of EPT with Orlicz geometric structure, since the N-funetion is only defined on the nonnegative domain. Additionally, we provide theoretical background to solve Orlicz-EPT by a binary search approach.
Justification:
Additionally, we present the proposed Orlicz-Sobolev transport (OST) the dual EPT and the underlying graph structure, we derive novel regularization for the critic function, develop the proposed OST. We prove that OST can be computed by simply solving a univariate optimization problem.
By leveraging
Furthermore, in $ derive geometric structures for OST, and show its connections to other transport distances. In $7 we empirically illustrate that OST is several-order faster than Orlicz-EPT. We also show evidences the advantages of OST for unbalanced measures a graph for document classification and TDA. Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification;
We consider OT problem for unbalanced measures supported on a graph metric
space.
For Orlicz-EPT, we show that it is directly derived from standard OT, with guarantee the nonnegativity for its ground cost via calibration, similar to OW approach (derived from bypass all challenges raised from unbalanced measures. We develop theoretical backgrounds to solve by binary search approach. However, Orlicz-EP" is still two-level optimization problem, it has a high computational cost, illustrated in $7
corresponding standard OT with nonnegative ground cost (67). Therefore,
For OST, it is efficient in computation by simply solving a univariate optimization problem ($4). Although OST is regularized approach, we theoretically show that OST generalize
GST for unbalanced measures on graph (Proposition 5.2).
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
36

---

The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Detailed proofs of theoretical results are placed in Appendix $A.2.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: we provide detailed setup for our experiments in 7 We discuss further details in Appendix B.2. We also submit the code together with our submission.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often
37

---

one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: Details of the experiments are given in 7 We use public datasets for experiments. Code is submitted together with the submission. We also discuss further details in Appendix B.2.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
sws.iiissssiiiiioiooooo.i for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips
www.oooooidissiooooooooooo www.bmmiiiiioooooccc.c.... for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Please see 7 Appendix B.2.
38

---

Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Please see reported empirical results. Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of eтrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please see Appendix $B.2, where we describe that all experiments are carried commodity hardware.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of http::////eaaapp...ooo//////ataa
39

---

Answer: [Yes]
Justification: The research in our submission is to advance the machine learning field. To our knowledge, there is foresee harmful consequences.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., s,, if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Please see Appendix $B.2, where we describe that our research aims to advance to the machine learning field. The proposed OST has an efficient computation, which may help to reduce the computational cost. To our knowledge, there is no foresee negative social impacts for our research.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our research poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
40

---

Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Please see 7 where we give proper credit/citation to the original owners.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, pappessii thcode wwwccoo/aaaooooo datasat has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question:
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
41

---

Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the method development in this research does involve L.MSs as any important, original, or non-standard components.
Please refer to our LLM policy (https: /tttp:://neuris... cttpeiissscco///oooo /Ctc///rnnnee//22///////// for what should or should not described.
42


Reviews:
[{"review_id": "ZSYGhfXSwE", "reviewer": "Reviewer_VFH4", "summary": "The authors investigate numerical methods to perform unbalanced optimal transport where the support of the measures is a graph. This paper proposes Orlicz-EPT and Orlicz-Sobolev Transport. Orlicz-EPT builds on the entropy partial transport (EPT) framework, extending it with Orlicz geometry by calibrating the ground cost to ensure nonnegativity—allowing standard optimal transport techniques to be applied. To accomplish this, the authors use insights once used by Caffarelli and McCann (2010) based on the obstacle problem. However, due to its two-level optimization structure, Orlicz-EPT remains computationally intensive. The authors then introduce Orlicz-Sobolev Transport (OST) as a means to address these computational hurdles, which is a dual formulation that regularizes the critic function using Orlicz-Sobolev spaces and reduces the problem to a single-variable optimization. The authors prove several theoretical properties about OST. Empirical results show that OST achieves competitive performance in document classification and topological data analysis while being several orders of magnitude faster than Orlicz-EPT.", "questions": "- The topic of OT on a graph (why this would happen, for example) is not appropriately motivated, and some more context would be appreciated.\n\n- It seems like the computations leading up to equation (6) is relevant enough to be a Theorem or proposition --- why is this not the case?", "limitations": "N/A", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 2, "originality": 2, "strengths_and_weaknesses": "A main strength of the paper is the development of a novel optimal transport algorithm on graphs for unbalanced measures, which is a common situation that does not appear to lie in the scope of many existing approaches. The paper contains many theoretical results and is the first instance I have seen Orlicz geometries used in this context, which is quite nice (though, there do appear related works cited by the authors here). The Orlicz structure leads to an expensive two-layer optimization problem, which the authors find a work-around for. Their numerical speedups are impressive as well as the newfound accuracy on several tasks.\n\nA main weakness of the paper is the writing and lack of clarity. From even the abstract, there are many repetitive concepts and sentence structures that make reading this paper incredibly difficult. There are simply too many equations (in-display equations) crammed into the text. The same is true for the tables and figures---everything is so small! I think the authors are trying to write too much instead of giving a more high-level insights into the problem and their proposed solution.", "was_revised": true, "final_justification": "I believe my existing score is what the paper deserves.", "rebuttal": "Dear Reviewer VFH4,\n\nThank you for your valuable feedback. Below are the answers for your questions and comments.\n\n**(1) [...] (OT on a graph) is not appropriately motivated [...] some more context would be appreciated [...]**\n\n→ OT problems for measures supported on a graph metric space have been explored in previous studies [34, 35, 36]. Notably, graph metrics extend tree metrics, which are utilized in scalable optimal transport methods like tree-sliced Wasserstein [R1, R2, R3, R4]. Tree-sliced Wasserstein, in turn, generalizes the popular sliced-Wasserstein approach [R5, R6]. The graph structure offers greater flexibility and degrees of freedom compared to the tree structure in tree-sliced Wasserstein and the line structure in sliced-Wasserstein. For a more in-depth discussion on the motivation behind optimal transport on graphs, please refer to [34]. We will elaborate on this further.\n\n**(2) [...] (computations) leading up to Equation (6) is relevant enough to be a Theorem or Proposition [...]**\n\n→ Thank you for your suggestion. We will summarize Equation (6) as a Proposition.\n\n**(3) [...] (weakness) writing and lack of clarity [...] (abstract) repetitive concepts and sentence structures that make reading this paper incredibly difficult [...] (in-display equations) crammed into the text [...] tables and figures (small) [...] giving more high-level insights [...]**\n\n→ We outline the key ideas of our proposed approaches in lines 52-81 and in the abstract (lines 1-25). We try to keep all important equations separated with explanatory text and define technical notions within both the equations and surrounding text.\n\n\nWe will follow your suggestions to incorporate additional text to clarify technical concepts, as well as expand figures and tables within the constraints of the main manuscript or supplement.\n\n---\n\n**Concluding remarks.** We would be grateful if you could confirm whether our clarifications and responses adequately address your concerns. If they do, we kindly ask that you consider increasing your rating. We are also happy to address any additional questions or concerns you might have.\n\n---\n\n*References*\n\n[R1] Indyk \\& Thaper, Fast Image Retrieval via Embeddings. IWSCTV, 2003\n\n[R2] Le et al., Tree-Sliced Variants of Wasserstein Distances. NeurIPS, 2019\n\n[R3] Tran et al., Distance-based Tree-Sliced Wasserstein Distance. ICLR, 2025\n\n[R4] Tran et al., Tree-Sliced Wasserstein Distance: A Geometric Perspective. ICML, 2025\n\n[R5] Rabin et al., Wasserstein Barycenter and its Application to Texture Mixing. SSVMCV, 2011\n\n[R6] Bonneel et al., Sliced and Radon Wasserstein Barycenters of Measures. JMIV, 2015"}, {"review_id": "OBQMjVvSty", "reviewer": "Reviewer_pFMB", "summary": "The paper presents a new framework for optimal transport (OT) between unbalanced measures on a graph based on two new distances: Orlicz-EPT and Orlicz-Sobolev Transport (OST). Orlicz-EPT extends entropy-regularized partial OT by adding Orlicz geometric structure and recasting it as a standard OT problem with a calibrated nonnegative cost, enabling computation via binary search. Then, OST leverages the dual of EPT and graph structure to present a regularized OT distance that can be computed efficiently using a univariate optimization problem. The paper shows that OST generalizes several known distances, including generalized Sobolev transport, standard Sobolev transport, and unbalanced Sobolev transport, and maintains desirable geometric properties such as being a divergence or a metric. Empirical results demonstrate that OST is significantly faster than Orlicz-EPT and is competitively running in document classification and topological data analysis, suggesting its scalability and practicality.", "questions": "1. While Orlicz-EPT is presented as a theoretically rich generalization, its application in practice is circumscribed by prohibitive computational cost. Can the authors say anything about operations or instances for which Orlicz-EPT would be preferable to use than OST, even with this penalty in terms of computation? Adding either empirical examples or a theoretical account with an explicit statement of under what conditions the additional expressiveness of Orlicz-EPT is valuable and worthwhile and justifies its use over OST\nwould be advantageous. If authors are able to detail compelling practical applications in which Orlicz-EPT is superior to OST (in quality or quantity), this would further strengthen the importance and applicability of the contribution.\n\n2. The experiments are largely limited to text files and persistence diagrams. Can the authors supplement, or at least mention, performance in other domains like biological graphs, social networks, or dynamic/temporal graphs? Include a single additional domain or application (even in a limited form) that tests OST in a very different setting in order to more evidently demonstrate its generality. A broader empirical range would offer evidence towards arguments of practical use and increase confidence that OST is a generally applicable tool for structured data.\n\n3. How sensitive is OST to the parameters such as the Orlicz function $\\phi$, the regularization weight $b$, and the $\\alpha$ range for critic functions? Did the author test this? Add a little sensitivity analysis or some pragmatic guidance on how to select such parameters in different settings. Even a graph of accuracy against $\\alpha$ or different $\\phi$ functions would be helpful. More interpretability and usability of OST would help in ease of use by practitioners and allow practitioners to adopt and experiment with the approach in their setting.\n\n4. The paper discusses scalability based on the number of transport calculations but would be useful to also describe how the performance grows if graph size and complexity are increased. The authors can provide a brief runtime or memory analysis that alters the size of the graph (nodes/edges) or density, especially since there are graphs of thousands of nodes in practice.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\nThe paper is a technically sound and well-presented contribution to the theory of optimal transport (OT) with a new pair of distances—Orlicz-EPT and Orlicz-Sobolev Transport (OST). The theoretical method is sound, basing itself on Caffarelli &amp; McCann&#39;s result to redefine entropy partial transport as a regular OT with calibrated nonnegative cost, making it possible to construct Orlicz-EPT. Subsequent to this, OST formulation via duality and a new regularization leads to an efficient computationally distance that can be calculated by way of a simple univariate optimization, much quicker than existing methods like Orlicz-EPT and UOT. The paper is nicely organized and clear in its exposition, with full definitions, proofs, and relation to existing work. OST generalizes various earlier transport distances (e.g., GST, ST, UST), and its strong theoretical guarantees are complemented with empirical behavior on document classification and topological data analysis, hinting at its viability for large-scale structured data.\n\nWeaknesses:\nDespite the theory being strong, empirical consideration is relatively narrow in scope and supported by document and topological data instead of more diverse or realistic contexts (e.g., biological or dynamic networks). Orlicz-EPT, while new, remains computationally expensive and less convenient despite theoretical innovation, and the paper fails to convincingly describe when it must be used instead of OST. Also, OST&#39;s behavior is still hyperparameter-sensitive (e.g., with respect to $\\alpha$, the choice of Orlicz function), though the paper has minimal suggestion or sensitivity analysis for making these selections. There are some technical subsections, notably the dual forms and cost calibration, that may benefit from a little more intuition or figures. Finally, certain parts of the work, particularly Orlicz-EPT, may arguably be seen as a modest extension of available forms like EPT, and experimental comparisons pretty much emphasize improvements over closely related previous work that may be extended.", "was_revised": true, "final_justification": "I greatly appreciate the efforts the authors have put in to address multiple (possibly difficult) technical questions. They do improve the quality of the paper if revised and I'm happy to raise my score. Regarding the author's question on suggesting datasets for biological, social network datasets, etc. there are plenty and it should be the responsibility of the author to justify their work - perhaps in a longer/extended format of this work.", "rebuttal": "Dear Reviewer pFMB,\n\nThank you for your valuable feedback. Below are the answers for your questions and comments.\n\n**(1) [...] under what conditions the additional expressiveness of Orlicz-EPT is valuable and worthwhile and justifies its use over OST would be advantageous (further strengthen the importance and applicability of the contribution) [...]**\n\n→ Following Proposition 5.2 (line 232), we can view OST as an extension of GST [36] for handling unbalanced measures, and Orlicz-EPT as an extension of OW [55] for unbalanced measures. Notably, when the input measures have equal mass (i.e., $\\mu(\\mathbb{G}) = \\nu(\\mathbb{G})$), and $b = 1$, Orlicz-EPT reduces to OW. Furthermore, Orlicz-EPT shares the same computational complexity as OW, as shown in Equation (7). It's worth noting that GST is a scalable variant of OW for balanced measures, in the same sense, OST can be seen as a scalable variant of Orlicz-EPT.\n\nAs a result, Orlicz-EPT is applicable for all applications of OW and extends OW to handle unbalanced input measures, whereas OST may not reserve all the properties of OW. \n\nLike OW, Orlicz-EPT involves a two-level optimization problem, limiting its applicability to small-scale domains. In contrast, OST, similar to GST, is scalable and can be applied to large-scale domains.\n\nWe appreciate the suggestion and agree that it is an interesting research direction for further exploration.\n\n**(2) [...] (experiments) limited to text files and persistence diagrams [...] (broader empirical range) biological graphs, social networks, or dynamic/temporal graphs? [...]**\n\n→ We would like to clarify that our work focuses on the OT problem with an Orlicz geometric structure for unbalanced measures supported on a graph metric space (lines 52-53). Specifically, our proposed approaches (Orlicz-EPT/OST) **compute the distance between two input measures** with potentially different total masses, where the measures are supported on the nodes of a graph with a metric based on shortest path lengths. Consequently, our approaches are suitable for applications that require measuring distances between measures on graph structures endowed with a graph metric.\nIn our experiments, we demonstrate the effectiveness of our approach in document classification on four real-world datasets and topological data analysis (TDA), including orbit recognition for linked twist maps (a discrete dynamical system modeling flows in DNA microarrays [R7]) and object shape recognition in MPEG7 dataset. These evaluations on document classification and TDA are often used for tasks involving comparing measures on a graph, see [35, 36]. We believe that such experimental coverage is rich and diverse enough. We will clarify it.\n\nRegarding the suggestion to explore broader empirical range, e.g., biological graphs, social networks, or dynamic/temporal graphs, could you please specify public datasets for the suggestion and confirm whether they involve comparing measures with potentially different total masses on a given graph? We appreciate your suggestion and would be happy to conduct additional experiments within the rebuttal period if feasible. Thank you very much.\n\n**(3) [...] (sensitivity analysis/pragmatic guidance) the Orlicz function $\\Phi$, the regularization weight $b$, and the $\\alpha$ range (ease of use by practitioners) [...]**\n\n→ We clarify that different Orlicz functions, such as the popular $N$-functions $\\Phi_1$, $\\Phi_2$, and the limit case $\\Phi_0$, are illustrated in Figures 2 and 3 of the main manuscript, as well as Figures A.3 and A.4 in the supplementary materials.\n\nThe performance of Orlicz-EPT/OST typically depends on the choice of the $N$-function $\\Phi$ (Equation (7) and Definition 4.1 respectively), similar to how kernel functions impact performance in kernel-dependent machine learning frameworks. In our experiments with $N$-functions $\\Phi_1$ and $\\Phi_2$ (Section 7), we observed slightly different performances. Similar findings have been reported for GST [36].\n\nWe agree that determining the optimal $N$-function $\\Phi$ for Orlicz-EPT/OST in a given task is an open problem that warrants further investigation. Given that the primary focus of our paper is on Orlicz-EPT/OST, we leave this topic for future work for a careful study. As an interim solution, cross-validation can be used to select $\\Phi$ from a set of candidate functions.\n\nRegarding the regularization weight $b$, we used $b=1$ in the experiments based on the results in Propositions 5.2 and 5.3, as well as for simplicity. This choice of $b$ is also supported by theoretical results on EPT on a graph [35] (Lemma A.6, Remark 4.8) and has been used in previous experiments for EPT [33, 35].\n\nFor $\\alpha$, from the result in Proposition 5.7 and for simplicity, we use $\\alpha=0$ for the experiments. Such value for $\\alpha$ is also supported by theoretical results of EPT on a graph [35] (Lemma 4.4, Proposition 5.2) and used in experiments for EPT [33, 35]. Additionally, when $\\alpha=0$, $\\mathcal{I}_{\\alpha}$ is the largest interval (line 197).\n\nFollowing your suggestion, we evaluate more additional experiments with different $b, \\alpha$. The average accuracy results are as follows:\n\n$\\star$ For document classification on TWITTER\n\n+ For graph $\\mathbb{G}$\\_Sqrt:\n\n|       | $\\Phi_0$     | $\\Phi_1$     | $\\Phi_2$     |\n|-------|:------------:|:------------:|:------------:|\n| $b=0.5$|71.66 $\\pm$ 0.63|72.03 $\\pm$ 0.56|72.12 $\\pm$ 0.57|\n| $b=2$|71.54 $\\pm$ 0.49|72.15 $\\pm$ 0.42|72.28 $\\pm$ 0.34|\n\n|              | $\\Phi_0$     | $\\Phi_1$     | $\\Phi_2$     |\n|--------------|--------------|--------------|--------------|\n|$\\alpha=0.1$|71.48 $\\pm$ 0.43|72.34 $\\pm$ 0.55|72.64 $\\pm$ 0.50|\n|$\\alpha=0.2$|71.64 $\\pm$ 0.50|72.12 $\\pm$ 0.36|72.27 $\\pm$ 0.30|\n\n+ For graph $\\mathbb{G}$\\_Log\n\n|       | $\\Phi_0$     | $\\Phi_1$     | $\\Phi_2$     |\n|-------|--------------|--------------|--------------|\n|$b=0.5$|70.97 $\\pm$ 0.29| 71.74 $\\pm$ 0.33|71.78 $\\pm$ 0.41|\n|$b=2$|71.58 $\\pm$ 0.41| 71.92 $\\pm$ 0.16|71.96 $\\pm$ 0.22|\n\n|              | $\\Phi_0$     | $\\Phi_1$     | $\\Phi_2$     |\n|--------------|--------------|--------------|--------------|\n|$\\alpha=0.1$|71.57 $\\pm$ 0.23|71.87 $\\pm$ 0.36|72.04 $\\pm$ 0.28|\n|$\\alpha=0.2$|71.59 $\\pm$ 0.35|71.74 $\\pm$ 0.22|71.95 $\\pm$ 0.19|\n\n$\\star$ For TDA on MPEG7\n\n+ For graph $\\mathbb{G}$\\_Sqrt\n\n|       | $\\Phi_0$     | $\\Phi_1$     | $\\Phi_2$     |\n|-------|--------------|--------------|--------------|\n|$b=0.5$|66.67 $\\pm$ 3.45|71.67 $\\pm$ 5.40|68.83 $\\pm$ 3.09|\n|$b=2$|65.00 $\\pm$ 3.58|69.13 $\\pm$ 3.87|67.33 $\\pm$ 3.55|\n\n|              | $\\Phi_0$     | $\\Phi_1$     | $\\Phi_2$     |\n|--------------|--------------|--------------|--------------|\n|$\\alpha=0.1$|66.43 $\\pm$ 4.81|70.47 $\\pm$ 4.51|68.50 $\\pm$ 4.54|\n|$\\alpha=0.2$|66.82 $\\pm$ 4.01|68.43 $\\pm$ 4.63|69.17 $\\pm$ 3.60|\n\n+ For graph $\\mathbb{G}$\\_Log\n\n|       | $\\Phi_0$     | $\\Phi_1$     | $\\Phi_2$     |\n|-------|--------------|--------------|--------------|\n|$b=0.5$|65.87 $\\pm$ 5.68|67.00 $\\pm$ 5.60|68.67 $\\pm$ 5.61|\n|$b=2$|65.93 $\\pm$ 5.11|68.91 $\\pm$ 6.00|66.17 $\\pm$ 4.60|\n\n|              | $\\Phi_0$     | $\\Phi_1$     | $\\Phi_2$     |\n|--------------|--------------|--------------|--------------|\n|$\\alpha=0.1$|65.94 $\\pm$ 4.19|67.83 $\\pm$ 5.83|66.46 $\\pm$ 4.58|\n|$\\alpha=0.2$|65.84 $\\pm$ 5.45|69.61 $\\pm$ 5.56|69.86 $\\pm$ 5.22|\n\nThese empirical results suggest that turning these hyperparameters (e.g., by cross-validation) may help to improve the performances further. We will clarify it.\n\n**(4) [...] (performance) alters the size of the graph (nodes/edges) or density (graphs of thousands of nodes) [...]**\n\n→ We clarify that our experiments (Section 7) utilize two graphs:  $\\mathbb{G}$\\_Sqrt and $\\mathbb{G}$\\_Log. For all datasets, except MPEG7 dataset, graph $\\mathbb{G}$\\_Sqrt consists of **10K nodes** and **1 million edges**, while graph $\\mathbb{G}$\\_Log comprises **10K nodes** and **100K edges**. Due to the smaller size of the MPEG7 dataset, we constructed graph $\\mathbb{G}$\\_Sqrt with **1K nodes** and **32K edges**, and graph $\\mathbb{G}$\\_Log  with **1K nodes** and **7K edges**. Additionally, the graph is assumed to be given in our experiments, see line 267-268. We will clarify it.\n\n**(5) [...] (dual forms and cost calibration) may benefit from a little more intuition or figures [...] (Orlicz-EPT) may arguably be seen as a modest extension of available forms like EPT [...]**\n\n→ We will follow your suggestions to add more text to further clarify dual forms and cost calibration within the constraints of the main manuscript or supplement.\n\nWe respectfully disagree that Orlicz-EPT is a modest extension of EPT. Below are the reasons:\n\n+ GST is recognized as a scalable variant of OW (see a review in Appendix B.1.5) [36]. However, unlike OT, extending GST to accommodate unbalanced measures on a graph with a mass constraint is nontrivial, as discussed in lines 57-60.\n\n+ We believe that it is **non-trivial to establish a connection between EPT on a graph [35] and a potential extension of GST [36] for unbalanced measures**.\n\n+ As noted in Remark 3.1 (lines 138-140), simply applying Caffarelli and McCann's (2010) observations without calibration would result in a new ground cost for standard OT that is **not guaranteed to be nonnegative**, similar to [12, 33, 35] (including EPT). We stress that our calibration is crucial for  the development involving Orlicz geometric structure, given that the $N$-function is defined on $\\mathbb{R}_{+}$ (see lines 98-100).\n\n---\n\n**Concluding remarks.** We would be grateful if you could confirm whether our clarifications and responses adequately address your concerns. If they do, we kindly ask that you consider increasing your rating. We are also happy to address any additional questions or concerns you might have.\n\n---\n\n*Reference*\n\n[R7] Hertzsch et al., DNA microarrays: design principles for maximizing ergodic, chaotic mixing. Small, 2007."}, {"review_id": "YRmqToTvIl", "reviewer": "Reviewer_uDto", "summary": "This paper addresses the problem of optimal transport for unbalanced measures on graph metric spaces. The key idea is to leverage insights from Caffarelli and McCann to reformulate the unbalanced optimal transport problem as a corresponding complete transport problem with a nonnegative ground cost. To further enhance this formulation, the Orlicz geometric structure is introduced. By defining measures on a graph, the solution to the reformulated transport problem can be reduced to solving a univariate optimization problem. Experimental results demonstrate that the proposed method outperforms existing approaches in both accuracy and computational efficiency.", "questions": "See the weakness part.", "limitations": "Yes.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The paper is well written and clearly structured.\n- The proposed method builds upon and integrates several well-established techniques. In particular:\n1. It reformulates problem (4), which incorporates Lagrangian multipliers for unbalanced measures, into a corresponding complete optimal transport (OT) problem (problem 6) with a nonnegative ground cost—an approach inspired by the insights of Caffarelli and McCann.\n2. Problem (6) is further enhanced using the Orlicz geometric structure, following the concept of Orlicz-Wasserstein distance.\n3. While the proposed Orlicz-Wasserstein formulation involves a two-level optimization—typically computationally expensive—this is efficiently addressed by defining measures on a graph (as in [35]), allowing the solution to be reduced to a univariate optimization problem (involving the variable t of the N-function).\n\nWeaknesses:\n- The method presents an incremental development of several well-established ideas. As such, the novelty of the approach may appear limited. However, I think that, this is the first work to explore Orlicz-Wasserstein distance for unbalanced measures specifically on graph structures, which is a meaningful contribution.\n- it remains unclear how to recover the solution to problem (3) (for a fixed m) from the solution to problem (4) (for a fixed \\lambda).", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer uDto,\n\nThank you for your valuable feedback. Below are the answers for your questions and comments.\n\n**(1) [...] The method presents an incremental development of several well-established ideas [...] the first work to explore Orlicz-Wasserstein distance for unbalanced measures specifically on graph structures, which is a meaningful contribution. [...]**\n\n→ We respectfully disagree that our proposed methods are incremental. Below are the reasons: \n\n+ GST is recognized as a scalable variant of OW (see a review in Appendix B.1.5) [36]. However, unlike OT, extending GST to accommodate unbalanced measures on a graph with a mass constraint is nontrivial, as discussed in lines 57-60.\n\n+ We believe that it is **non-trivial to establish a connection between EPT on a graph [35] and a potential extension of GST [36] for unbalanced measures**.\n\n+ As noted in Remark 3.1 (lines 138-140), simply applying Caffarelli and McCann's (2010) observations without calibration would result in a new ground cost for standard OT that is **not guaranteed to be nonnegative**, similar to [12, 33, 35]. We stress that our calibration is crucial for  the development involving Orlicz geometric structure, given that the $N$-function is defined on $\\mathbb{R}_{+}$ (see lines 98-100).\n\n+ We leverage insights from [35, 36] to develop a novel regularization for OST (Definition 4.1), which involves new tools to **control integral of gradient on shortest paths and its duality** with Orlicz geometry, as shown in Equation (12) and Appendix A.2.4.\n\nWe emphasize that we do not claim any new techniques for the theoretical proofs. We appreciate your evaluation that the proposed methods are meaningful contributions: our work is the **first** approach to efficiently extend OW/GST for unbalanced measures on a graph.\n\n**(2) [...] (unclear) recover the solution to Problem (3) (for a fixed m) from the solution to Problem (4) (for a fixed $\\lambda$). [...]**\n\n→ The relationship between Problem (3) and Problem (4) is established in [35], specifically through Theorem A.1 in Appendix A.1. To elaborate, Theorem A.1 in [35] demonstrates that a solution to Problem (4) directly yields a solution to Problem (3). We will provide further clarification on this connection.\n\n---\n\n**Concluding remarks.** We would be grateful if you could confirm whether our clarifications and responses adequately address your concerns. If they do, we kindly ask that you consider increasing your rating. We are also happy to address any additional questions or concerns you might have."}, {"review_id": "rlMK9qL6TE", "reviewer": "Reviewer_HNe3", "summary": "This paper addresses the challenge of computing optimal transport (OT) between unbalanced measures on a graph, which is common in tasks like comparing documents with different word counts. Traditional OT methods assume equal mass and often rely on $\\ell_p$-based cost functions, which limits their flexibility and scalability. The standard approaches that tackle unbalanced cases also have a higher complexity.\n\nTo overcome this, the authors introduce two contributions:\n\n* Orlicz-EPT: A new variant of entropy partial transport (EPT) that incorporates Orlicz geometry, which is a generalization of OT that uses convex functions instead of fixed powers like in $\\ell_p$. By reformulating EPT as a standard OT problem with a carefully calibrated, nonnegative ground cost, they enable the use of Orlicz-Wasserstein-like metrics even in unbalanced settings. This adds modeling flexibility, especially for data with noise or outliers, but remains computationally expensive due to its two-level optimization structure.\n\n* Orlicz-Sobolev Transport (OST): To overcome the higher complexity of Orlicz-EPT, the authors explore a dual formulation that is significantly more efficient. It defines a new transport distance using Orlicz-Sobolev spaces on graphs and simplifies the computation to a univariate optimization problem. The resulting distance has several desirable properties, such as divergence (nonnegative and zero iff measures match), being a metric under mild conditions, and generalizing several known distances like GST (Generalized Sobolev Transport), ST (Sobolev Transport), and UST (Unbalanced Sobolev Transport).\n\nThe authors demonstrate the effectiveness of OST on large-scale experiments in document classification and topological data analysis (TDA).", "questions": "* Can the authors explain the reason behind the choices in your experiments? While some of the settings are said to follow prior work, it’s not entirely clear that they are optimal for the current setup. In particular, could the authors provide more intuition behind the selection of the Orlicz functions $\\phi_0, \\phi_1$ , and $\\phi_2$ ? Additionally, I would appreciate an explanation for the specific form of the weight functions $w_1$ and $w_2$. Have the authors performed any ablation or sensitivity analysis to study the impact of these parameter choices on performance or efficiency?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n* The paper introduces a novel variant of optimal transport (OT) that extends existing formulations to the Orlicz geometry, providing a more flexible alternative to traditional $\\ell_p$-based distances for unbalanced measures.\n* It establishes strong theoretical foundations, including connections to several known OT variants (e.g., GST, ST, UST), demonstrating that the proposed distance is a meaningful generalization.\n* The effectiveness of the proposed distance is supported by empirical results on document classification and topological data analysis tasks.\n\n**Weaknesses**\n* Although the paper is mathematically rigorous, it is quite dense in places. Some sections (e.g., Section 3) would benefit from additional intuition or illustrative examples.", "was_revised": true, "final_justification": "The paper provides solid contributions to optimal transport theory, with strong theoretical results and valuable experimental evaluations. I maintain my positive score and vote for the acceptance of the paper.", "rebuttal": "Dear Reviewer HNe3,\n\nThank you for your valuable feedback. Below are the answers for your questions and comments.\n\n**(1) [...] (some of the settings follow prior work): (not entirely clear) optimal for the current setup [...] more intuition behind the selection of the Orlicz functions $\\Phi_0, \\Phi_1, \\Phi_2$? [...] (explanation) specific form of the weight functions $w_1$ and $w_2$ [...] (ablation or sensitivity analysis) parameter choices on performance or efficiency? [...]**\n\n→ $N$-functions $\\Phi_1, \\Phi_2$ and the limit case $\\Phi_0$ have been popularly utilized for Orlicz geometric structure in the literature [36, 17, 3, 49, 26, 4, 54, 13, 2, R8].\n\nThe performance of Orlicz-EPT/OST typically depends on the choice of the $N$-function $\\Phi$ (Equation (7) and Definition 4.1 respectively), similar to how kernel functions impact performance in kernel-dependent machine learning frameworks. In our experiments with $N$-functions $\\Phi_1$ and $\\Phi_2$ (Section 7), we observed slightly different performances. Similar findings have been reported for GST [36].\n\nWe agree that determining the optimal $N$-function $\\Phi$ for Orlicz-EPT/OST in a given task is an open problem that warrants further investigation. Given that the primary focus of our paper is on Orlicz-EPT/OST, we leave this topic for future work for a careful study. As an interim solution, cross-validation can be used to select $\\Phi$ from a set of candidate functions.\n\nFollowing the theoretical result in Proposition 5.7, and theoretical properties on the EPT on a graph [35] (Corollary 3.2, Corollary 4.6, Proposition 5.4), weight functions $w_1, w_2$ are $b$-Lipschitz, e.g., we simply choose $w_1(x) = w_2(x) = a_1 d_{\\mathbb{G}}(x, z_0) + a_0$ where $a_1 = b, a_0 =1$, see line 288-289.\n\nWe consider different graphs $\\mathbb{G}$\\_Sqrt, and $\\mathbb{G}$\\_Log. For all datasets, except MPEG7 dataset, graph $\\mathbb{G}$\\_Sqrt consists of **10K nodes** and **1 million edges**, while graph $\\mathbb{G}$\\_Log comprises **10K nodes** and **100K edges**. Due to the smaller size of the MPEG7 dataset, we constructed graph $\\mathbb{G}$\\_Sqrt with **1K nodes** and **32K edges**, and graph $\\mathbb{G}$\\_Log  with **1K nodes** and **7K edges**. We also consider different $N$-functions ($\\Phi_1, \\Phi_2, \\Phi_0$). Some other parameters, e.g., $b, \\alpha, w_1, w_2$, are set by following our derived theoretical results (Section 5) and theoretical properties of EPT [33, 35] used in their experiments.\n\nFurthermore, we carry out more additional experiments for different $b, \\alpha$. The average accuracy results are as follows:\n\n$\\star$ For document classification on TWITTER\n\n+ For graph $\\mathbb{G}$\\_Sqrt:\n\n|       | $\\Phi_0$     | $\\Phi_1$     | $\\Phi_2$     |\n|-------|:------------:|:------------:|:------------:|\n| $b=0.5$|71.66 $\\pm$ 0.63|72.03 $\\pm$ 0.56|72.12 $\\pm$ 0.57|\n| $b=2$|71.54 $\\pm$ 0.49|72.15 $\\pm$ 0.42|72.28 $\\pm$ 0.34|\n\n|              | $\\Phi_0$     | $\\Phi_1$     | $\\Phi_2$     |\n|--------------|--------------|--------------|--------------|\n|$\\alpha=0.1$|71.48 $\\pm$ 0.43|72.34 $\\pm$ 0.55|72.64 $\\pm$ 0.50|\n|$\\alpha=0.2$|71.64 $\\pm$ 0.50|72.12 $\\pm$ 0.36|72.27 $\\pm$ 0.30|\n\n+ For graph $\\mathbb{G}$\\_Log\n\n|       | $\\Phi_0$     | $\\Phi_1$     | $\\Phi_2$     |\n|-------|--------------|--------------|--------------|\n|$b=0.5$|70.97 $\\pm$ 0.29| 71.74 $\\pm$ 0.33|71.78 $\\pm$ 0.41|\n|$b=2$|71.58 $\\pm$ 0.41| 71.92 $\\pm$ 0.16|71.96 $\\pm$ 0.22|\n\n|              | $\\Phi_0$     | $\\Phi_1$     | $\\Phi_2$     |\n|--------------|--------------|--------------|--------------|\n|$\\alpha=0.1$|71.57 $\\pm$ 0.23|71.87 $\\pm$ 0.36|72.04 $\\pm$ 0.28|\n|$\\alpha=0.2$|71.59 $\\pm$ 0.35|71.74 $\\pm$ 0.22|71.95 $\\pm$ 0.19|\n\n$\\star$ For TDA on MPEG7\n\n+ For graph $\\mathbb{G}$\\_Sqrt\n\n|       | $\\Phi_0$     | $\\Phi_1$     | $\\Phi_2$     |\n|-------|--------------|--------------|--------------|\n|$b=0.5$|66.67 $\\pm$ 3.45|71.67 $\\pm$ 5.40|68.83 $\\pm$ 3.09|\n|$b=2$|65.00 $\\pm$ 3.58|69.13 $\\pm$ 3.87|67.33 $\\pm$ 3.55|\n\n|              | $\\Phi_0$     | $\\Phi_1$     | $\\Phi_2$     |\n|--------------|--------------|--------------|--------------|\n|$\\alpha=0.1$|66.43 $\\pm$ 4.81|70.47 $\\pm$ 4.51|68.50 $\\pm$ 4.54|\n|$\\alpha=0.2$|66.82 $\\pm$ 4.01|68.43 $\\pm$ 4.63|69.17 $\\pm$ 3.60|\n\n+ For graph $\\mathbb{G}$\\_Log\n\n|       | $\\Phi_0$     | $\\Phi_1$     | $\\Phi_2$     |\n|-------|--------------|--------------|--------------|\n|$b=0.5$|65.87 $\\pm$ 5.68|67.00 $\\pm$ 5.60|68.67 $\\pm$ 5.61|\n|$b=2$|65.93 $\\pm$ 5.11|68.91 $\\pm$ 6.00|66.17 $\\pm$ 4.60|\n\n|              | $\\Phi_0$     | $\\Phi_1$     | $\\Phi_2$     |\n|--------------|--------------|--------------|--------------|\n|$\\alpha=0.1$|65.94 $\\pm$ 4.19|67.83 $\\pm$ 5.83|66.46 $\\pm$ 4.58|\n|$\\alpha=0.2$|65.84 $\\pm$ 5.45|69.61 $\\pm$ 5.56|69.86 $\\pm$ 5.22|\n\nThese empirical results suggest that turning these hyperparameters (e.g., by cross-validation) may help to improve the performances further. We will clarify it.\n \n**(2) [...] (Section 3) would benefit from additional intuition or illustrative examples. [...]**\n\n→ Thank you for your suggestion. We will add more text and examples to further clarify technical concepts (Section 3) within the constraints of the main manuscript or supplement.\n\n---\n\n**Concluding remarks.** We would be grateful if you could let us know whether our clarifications and answers are satisfied to address the raised concerns. If so, we kindly ask that you consider increasing your rating. We are also pleased to discuss any other questions you may have.\n\n---\n\n*Reference*\n\n[R8] Vershynin, High-dimensional probability: An introduction with applications in data science. Cambridge university press, 2018"}]

Author rebuttal:

Meta-review: (a) Scientific claims and findings: The paper introduces two new formulations of optimal transport (OT) between unbalanced measures supported on graph metric spaces:

Orlicz-EPT – an extension of entropy-regularized partial transport (EPT) that incorporates Orlicz geometry. By calibrating the ground cost to ensure nonnegativity, the authors reformulate unbalanced OT into a standard OT problem that admits classical techniques. This provides greater modeling flexibility, especially when data exhibit heterogeneity, noise, or imbalanced supports.

Orlicz-Sobolev Transport (OST) – a dual formulation that regularizes the critic function in Orlicz-Sobolev spaces. Importantly, this reduces the computational burden to a univariate optimization problem, making OST highly efficient. The authors prove several properties of OST, including divergence and, under mild conditions, metric structure, and show that it generalizes known transport distances such as generalized Sobolev transport (GST), Sobolev transport (ST), and unbalanced Sobolev transport (UST).

Empirical evaluations on document classification and topological data analysis (TDA) show that OST is orders of magnitude faster than Orlicz-EPT, while maintaining competitive or superior accuracy.

(b) Strengths:
1. Conceptual novelty: First exploration of Orlicz-Wasserstein distances for unbalanced measures on graphs, extending classical OT theory to a flexible and practically important new regime.
2. Solid theoretical development: Builds on insights from Caffarelli & McCann (2010), rigorously establishes properties of OST, and carefully situates the work within the OT literature.
3. Computational efficiency: OST reduces a two-level optimization problem to a univariate optimization, yielding dramatic runtime gains without sacrificing theoretical guarantees.
4. Generality: OST unifies and generalizes multiple existing OT variants (GST, ST, UST), demonstrating both theoretical depth and practical breadth.
5. Empirical validation: Demonstrates strong results on real-world tasks (document classification, TDA) with scalability to large graphs (up to 10K nodes, 1M edges).
6. Clarity and completeness: Despite some density in presentation, the paper provides full definitions, proofs, and comparisons, making it a comprehensive and self-contained contribution.

(c) Weaknesses / Missing elements
1. Density of exposition: At times the paper is mathematically heavy and could benefit from additional intuition, illustrations, or higher-level summaries.
2. Experimental diversity: Evaluation is primarily on text-based and TDA benchmarks; extensions to other domains (e.g., biological or dynamic networks) would further strengthen claims of generality.
3. Parameter guidance: Sensitivity to the choice of Orlicz function and regularization weights is acknowledged, but more systematic guidance for practitioners remains open.

These weaknesses are relatively minor compared to the overall strength and novelty of the contribution.

(d) Reasons for acceptance and Spotlight recommendation
I recommend acceptance as a Spotlight. The paper stands out for several reasons:
1. Theoretical innovation – The introduction of Orlicz geometry into unbalanced OT on graphs is both novel and significant, opening new directions for research in transport distances.
2. Practical impact – OST provides a dramatic improvement in computational scalability while retaining strong theoretical guarantees. This makes it directly useful for real-world structured data tasks.
3. Breadth of contribution – The framework unifies and extends multiple existing OT distances, which is of broad interest across machine learning, optimization, and applied mathematics.
4. Balance of theory and practice – Few works succeed in combining nontrivial mathematical development with concrete, scalable algorithms and empirical validation. This paper achieves that balance convincingly.
Given these points, the paper represents a high-impact and well-rounded contribution that goes beyond incremental improvements, justifying its selection as a Spotlight.

(e) Rebuttal period discussion and resolution
1. Motivation and context: One reviewer asked for stronger motivation for OT on graphs. The authors clarified its connection to tree-sliced and sliced-Wasserstein methods, with references to prior work, and promised to elaborate further in the revision.
2. Theoretical formalization: Suggestions to state key derivations (e.g., Eq. 6) as a proposition were accepted; authors will adjust accordingly.
3. Use of Orlicz-EPT vs. OST: Reviewers asked under what conditions the more expensive Orlicz-EPT is useful. The authors clarified that Orlicz-EPT preserves full Orlicz-Wasserstein properties and is suitable for small-scale domains, while OST serves as its scalable counterpart.
4. Experimental scope: Concerns about limited domains were addressed by highlighting TDA applications (including DNA microarrays and shape recognition) and inviting reviewers to suggest additional datasets. Authors argued convincingly that their current experiments cover standard OT-on-graphs applications.
5. Parameter sensitivity: Authors provided new empirical results demonstrating modest performance variation across Orlicz functions and parameters, and suggested cross-validation as a practical selection method.
6. Scalability: Clarified that their experiments already include graphs with up to 10K nodes and 1M edges, demonstrating practical scalability.
7. Incrementality concerns: The authors strongly defended the nontriviality of their contributions, emphasizing the difficulty of extending OW/GST to unbalanced measures with nonnegative calibration.
8. Clarity issues: Authors committed to adding intuition, examples, and clearer figures/tables in the revision.

Overall, the rebuttal was thorough, addressed all reviewer concerns convincingly, and even included additional empirical results to back claims. Reviewers were satisfied, and consensus shifted to acceptance.

This paper combines novel theoretical insights, computational breakthroughs, and practical validation, representing a substantial and broadly relevant contribution to the optimal transport and machine learning communities.
Decision: Accept (spotlight)