Scalable Sobolev IPM for Probability Measures on a Graph
Authors: Tam Le
Truyen Nguyen
Hideitsu Hino
Kenji Fukumizu
Venue: ICML 2025 poster (2025)
Keywords: Sobolev IPM
probability measures on a graph
scalability
integral probability metrics (IPM)
Sobolev norm
weighted Lp norm
Primary area: general_machine_learning->everything_else
TL;DR: We propose a novel regularization for Sobolev IPM for measures on a graph, which yields a closed-form expression for fast computation. It addresses the long-standing computational challenge for Sobolev IPM, especially in large-scale settings.

Abstract: We investigate the Sobolev IPM problem for probability measures supported on a graph metric space. Sobolev IPM is an important instance  of integral probability metrics (IPM), and is obtained by constraining a critic function within a unit ball defined by the Sobolev norm. In particular, it has been used to compare probability measures and is crucial for several theoretical works in machine learning. However, to our knowledge, there are no efficient algorithmic approaches to compute Sobolev IPM effectively, which hinders its practical applications. In this work, we establish a relation between Sobolev norm and weighted $L^p$-norm, and leverage it to propose a *novel regularization* for Sobolev IPM. By exploiting the graph structure, we demonstrate that the regularized Sobolev IPM provides a *closed-form* expression for fast computation. This advancement addresses long-standing computational challenges, and paves the way to apply Sobolev IPM for practical applications, even in large-scale settings. Additionally, the regularized Sobolev IPM is negative definite. Utilizing this property, we design positive-definite kernels upon the regularized Sobolev IPM, and provide preliminary evidences of their advantages for comparing probability measures on a given graph for document classification and topological data analysis.

Scalable Sobolev IPM for Probability Measures on a Graph
Tam Le" Truyen Nguyen 22 Hideitsu Hino
Kenji Fukumizu
Abstract
et al., 2003; Yurochkin al., 2019). In computer vision and graphics, 3D objects are often represented as point clouds, which are distributions of 3D data points (Achlioptas et al., 2018; Hua et al., 2018; Wang et al., 2019; Wu et al., 2019; Nguyen et al., 2021). In topological data analysis (TDA), persistence diagrams (PD) are used to represent complex structural objects (Le & Yamada, 2018; Rieck et al., 2019; Zhao & Wang, 2019; Divol & Lacombe, 2021). Specifically, PDs can be regarded as distributions of 2D data points, where each point characterizes the birth and death time of a particular topological feature (Edelsbrunner & Harer, 2008),
We investigate the Sobolev IPM problem for prob- ability measures supported space. Sobolev IPM is an important instance of integral probability metrics (IPM), and is obtained by constraining a critic function within unit ball defined by the Sobolev norm. In particular, it has been used to compare probability measures and is crucial for several theoretical works in ma- chine learning. However, to our knowledge, there are efficient algorithmic approaches to com- pute Sobolev IPM effectively, which hinders its practical applications. In this work, we establish a relation between Sobolev norm and weighted [--norm, and leverage to propose a novel reg- ularization for Sobolev IPM. By exploiting the graph structure, we demonstrate that the regular- ized Sobolev IPM provides closed-form expres- sion for fast computation. This advancement ad- dresses standing computational challenges, and paves the way to apply Sobolev IPM for prac- tical applications, even in large-scale settings. Ad- ditionally, the regularized Sobolev IPM is neg- ative definite. Utilizing this property, we de- sign positive-definite kernels upon the regular- ized Sobolev IPM, and provide preliminary evi- dences of their advantages for comparing prob- ability measures on a given graph for document classification and topological data analysis.
graph metric
Integral probability metrics (IPMs) are a powerful class of distances for comparing probability measures (Müller, 1997). Essentially. IPMs identify a critic function (or wit- ness function) that maximizes the discrimination between data points sampled from two input probability measures. IPMs have been applied in numerous theoretical studies and practical applications (Sriperumbudur et al., 2009; Gretton et al., 2012; Peyré& & Cuturi, 2019; Liang. 2019; Uppal et al., 2019; 2020; Nadjahi et al., 2020; Kolouri et al., 2020).
In this work, we study Sobolev IPM problem for proba- bility measures supported on graph. Sobolev IPM is an important instance of IPM, and is obtained by constraining the critic function within unit ball defined by the Sobolev norm (Adams & Fournier, 2003). Sobolev IPM plays a crucial role in several theoretical works, such as analyzing convergence rates of density estimation with generative ad- versarial networks (GANs) and studying error bounds for deep ReLU discriminator networks in GANs (Liang, 2017: 2021; Singh et al., 2018). However, to our knowledge, long-standing challenge for Sobolev IPM is that there are no efficient algorithmic approaches to compute it effectively which limits its applications in practice. To address this issue, we propose a novel regularization for the Sobolev IPM problem. By leveraging the graph structure, we demon- strate that the regularized Sobolev IPM yields a closed-form expression for fast computation, thereby paving the way for its application in various domains, even for large-scale settings.
1. Introduction
Probability measures are widely used to represent objects of interest across various research fields. For instance, in natural language processing, documents can be viewed as distributions over words (Sparck Jones, 1972; Kusner et al., 2015; Le et al., 2019), or distributions over topics (Blei
'qqual contribution 'Dpaarmeent of Advanced Data Science, The Institute of Statistical Mathematics (ISM), Tokyo, Japan 'The University Akron, Ohio, US. Correspondence to: Tam <tam appniss..c.jp..
Contribution. Our contributions are three-fold as follows:
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
We propose a novel regularization for Sobolev IPM that provides closed-form expression for fast computation,

---

Scalable Soboley IPM for Probability Measures on a Graph
overcoming the long-standing computational challenge
and facilitating its application, particularly in large- scale settings.
26
We prove that the regularized Sobolev IPM is metric and show its equivalence to the original Sobolev IPM. Additionally, we establish its connections to Sobolev transport (ST) which is a scalable variant of optimal transport (OT) for measures on a graph, and also its connection to the traditional OT on graph.
JP10
e11
-77
C15
C112
P14
63 F3
Figure I: A geodetic graph with 10 nodes {ø1, .2..... T10} and 15 edges {ci, ........ : C15 and each edge length equals to 1, i.e., Wey = 1, Vj. For any Zi, there is unique shortest path between them, with a length 2. Therefore, it satisfies the uniqueness property of the shortest paths. Let æ be the unique sattuueeepahhhheee root node (i.e., 20 = x1). and subgraph G containing 3 nodes {dT4, Jis v10) and edges (ea, e10), then we have A(rs) = 7(es) = G.
We demonstrate that the regularized Sobolev IPM is negative definite. We then design positive definite ker- nels based on the regularized Sobolev IPM and provide preliminary evidence of their advantages compare probability measures given graph in document classification and topological data analysis (TDA).
Organization. In $2, introduce the notations used throughout our proposals. We detail our novel regularization for Sobolev IPM in $3. In $4, we prove the metric property for the regularized Sobolev IPM and establish its connec- tion to the original Sobolev IPM, ST, and OT on a graph. Additionally, we demonstrate the negative definiteness for the regularized Sobolev IPM and propose positive definite kernels based on it. In $5, we discuss related works. In $6, we empirically illustrate the computational advantages of the regularized Sobolev IPM and provide preliminary evidence of its benefits in document classification and TDA. Finally, in $7, we offer concluding remarks. Proofs for the- oretical results and additional materials are deferred to the Appendices. Additionally, we have released code for our proposed approach.'
root node 2g E V such that the shortest path between 20 and æ is unique for any x E G, i.c. the uniqueness property of the shortest paths (Le et al., 2022).
Denote [ar, the shortest path between and in G. Then for given x E G and edge e E, we define the sets A(x) and Th as follows
A(z) = {y E G [20 y|}. Te Eye G S [20, y]}.
(I)
See Figure for an illustration of these graph notions.
Measures and functions on graph. Let P(G) (resp. ( G)) denote the set of all nonnegative Borel mea- sures on G (resp. G G) with a finite mass.
2. Preliminaries
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) stands for the set of all continuous functions on G. Similar notation is used for continuous functions on G x G.
In this section, we briefly review the graph setting for prob- ability measures. We also introduce some notations and functional spaces on the graph.
Graph. We follow the same graph setting in Le et al. (2022) for measures and functions. Precisely, let V, F de- note the sets of nodes and edges respectively. We consider connected, undirected, and physical graph G (V, E) with positive edge lengths { [we beeg. The continuous graph setting is adopted, i.e. G is regarded as the collection of all nodes V together with all points forming the edges in E. Additionally, G is equipped with the graph metric do v). which is defined as the length of the shortest path connecting x and y in G. We assume that there exists fixed
For a nonnegative Borel measure À on G and S p << oc. let IP [G, A) denote the space of all Borel measurable func- tions f G + R such that fc [xx)) (((()) < co. Then LP(G, A) is normed space with the norm being defined by
lIflle = - ((LO))))))) $
Additionally, let w be positive weight function C, i.e., ((x) > 0 for every E G. Consider the weighted I (G, A) as the space of all Borel measurable functions f G R such that f&g (zz)l < co. It is a
'The code repository is on https:: /ttts::/github... com/ lttaam/ SSoollee- IPM.
II the sense that V is subset of Euclidean space R": each edge E E the standard line segment in R" connecting the two vertices of the edge
"See Figure 1 for illustration of a geodetic graph which satisfies the uniqueness property the shortest paths.
2

---

Scalable Soboley IPM for Probability Measures on a Graph
normed space with the following weighted Le-norm
exponent S p S oo and its conjugate y/ the Sobolev
IPM between any probability measures μ4, E P(G) is
liflleg := ( ((())))())))())) "
defined
/. [())a(d))) ( SEBip')
Sp(u, v) sup
(4)
The spaces I"(G, A), [ (G, X) and their corresponding norms can also be defined for the case p - oc. Further details are placed in Appendix $B.1.
Notice that the quantity inside the absolute signs is un- changed if f is replaced by f-oo)) Thus, we can assume without loss of generality that f(zo) = This is the motiva- tion for our introduction of the Sobolev space W (G, A).
3. Regularized Sobolev IPM
In this section, we consider the Sobolev IPM problem for probability measures on a graph. We show that the Sobolev norm of f is equivalent to a weighted L -o-norm f' with a specific weight function. Then we propose to leverage the weighted L"-norm regularize the Sobolev IPM. It is also demonstrated that a closed-form expression can be derived for the regularized Soholev IPM.
To knowledge, there are no efficient algorithmic ap- proaches to compute the Sobolev IPM in Equation (4) effec- tively, especially for large-scale settings.
Weight function. tion, defined as
Hereafter, we consider the weight func-
w(x) == 1 ((A2)), Vz E G.
(5)
3.1. Sobolev IPM
We first introduce the graph- Sobolev space (Le et al., 2022) and its Sobolev norm (Adams & Fournier, 2003). Utilizing these, we then give the definition of Sobolev IPM for probability measures on graph.
where recall that A(x) is a subgraph (see Equation (I), and Figure 1), and X(-) is measure À on a set. For instance, when X is the length measure on graph G (Le et al., 2022)%, then X(A())) is the total length of A(z).
Definition 3.1 (Graph-based Sobolev space (Le et al., 2022)). Let X be nonnegative Borel measure on G, and let S S oc. A continuous function f: G -> IR is said to belong to the Sobolev space W A) if there exists a function h E [P(G, A) satisfying
The next result plays the key role in our approach.
Theorem 3.2 (Equivvaencee. For a nonnegative Borel mea-
sure X G and 1 S p < oc, let = min(1.A(G) 1+A(G)²
and c2 == [max(L, $, Then, we have
/ My))(dy) Var E G. [20,0e]
ci alll01 S I1 S S S0211511eg
(6)
Such function h is unique in (P( A) and is called the graph derivative of f w.r.t the measure A. The graph deriva- tive of f E WG- X) is denoted as f' (G,
for every function I
The proof is placed in Appendix $A.1.
Relation (6) implies that the Sobolev norm of a critic func- tion f E W. (G, A) is equivalent to the weighted L"-norm of its gradient f'. Moreover, the weight function is given explicitly by Equation (5).
Sobolev norm. WTG A) is a normed space with the Sobolev norm (Adams & Fournier, 2003, $3.1) being de- fined as
Il = (11SI2- 11
(3)
3.2. Regularized Sobolev IPM
Additionally, let W: A) be the subspace consisting of all functions f in W..P (G, X) satisfying f(20) Denote B(p) = { WG (G, A): [|flw S } as the unit ball in the Sobolev space.
Based on the equivalent relation given by Theorem 3.2, we propose to regularize the Sobolev IPM (Equation (4)) by relaxing the constraint on the critic function f in the graph- based Sobolev space W More precisely, instead of f belonging to the unit ball B(p') of the Sobolev space, we propose to constraint critic f within the unit ball B(p', w)
Sobolev IPM. Sobolev IPM for probability measures graph is an instance of the integral probability metric (IPM) where its critic function belongs to the graph- based Sobolev space, and is constrained within the unit ball of that space. More concretely, given nonnegative Borel measure À on G,
'p' E [1, oo) satisfying 1 + 3 = 1. If = 1, then p' = oc. 'Siiiarrly, Soholev space vanishing at the boundary is applied for the Sobolev GAN (Mrouch et al., 2018)
"See Appendix $B.2 for a review.
3

---

Scalable Soboley IPM for Probability Measures on a Graph
of the weighted IP'-norm of I' with weight function vi. Hereafter, B(p', w) is defined by
The proof placed in Appendix $A.3.
Remark 3.6 (Non-physical graph). We assumed that C is a physical graph in $2. Nevertheless, when input measures nodes V of graph G, and À is length measure of graph G, the regularized Sobolev IPM S, does not depend on this physical assumption as illustrated in Theorem 3.5, Indeed, it only depends on the graph structure (V, F) and edge weights We. Therefore, we can apply the regularized Sobolev IPM for non-physical graph G.
B(p', @) = { f w. 1f s1..
(7)
are supported
We now formally define the regularized Sobolev IPM be- tween two probability distributions on graph G.
Definition 3.3 (Regularized Sobolev IPM on graph). Let be a nonnegative Borel measure on G and Σ p S co. Then for any given probability measures μ, v E P(G), the regularized Sobolev IPM defined as
Preprocessing. For the computation of the regularized Sobolev IPM Sp in Equation (10), observe that the set Ye (see Equation (1)) and 8., (see Equation (11)) can be pre- computed for all edges in G. Notably, the preprocessing procedure is only involved graph G, and it is independent of the input probability measures. Consequently, we only need to perform this preprocessing procedure once, regardless of the number of input pairs of probability measures that are evaluated by the regularized Sobolev IPM Sp in applications. More precisely, we apply the Dijkstra algorithm to recom- pute the shortest paths from root node to all other input supports (or vertices) with complexity O(E) + [V log IVI) where we write |. for the set cardinality. Then, we can evaluate Ye and 3. for each edge in E.
I. (()))((s) - ((onvaaa) (8) FEB(D',O)
u)(1, sup
The following result shows that the regularized Sobolev IPM yields a closed-form expression.
Theorem 3.4 (Closed-form expression). Let be any non- negative Borel measure on G, and 1 S p < oo.? Then
Sylu, -//= (m(A(=) - -(A(x)) (uMA)) A(dx). (9)
The proof is placed in Appendix $A.2.
Notice that in identity (9), both the subgraph A(x) (Equa- tion (1)) and the weight function wxx) (Equation (5)) de- pend on input point æ under the integral over G.
Sparsity of subgraph %v in G. Denote supp(μ) as the set of supports of measure μ. For any E supp(u), its mass is accumulated into ((%)) if and only if S [zo, zi] (Le et al., 2022). Therefore, let define En, C E as follows
For practical applications, we next derive an explicit formula for the integral over graph G in Equation (9) when the input probability measures are supported on nodes V of graph G. This gives efficient method for computing the regularized Sobolev IPM Sp. Note that to achieve this result, we use the length measure on graph G (Le et al., 2022) for the nonnegative Borel measure X, i.e., we have A(xr, =l) = dg(x, 2). Vx, 2 E G. We summarize the result in the following theorem.
Fp feE F Ez E (supp(u) supp(v)), e S [Zo, =]]
Then, in fact, we can remove all edges e E E' \ En in the summation in Equation (10) for the computation of the regularized Sobolev IPM S,. As the result of this sparsity property, the computational complexity of S, is reduced to O( Fa
Following the preprocessing procedure and the sparsity of subgraph Ye for any edge e in G, we only need to check the precomputed shortest paths from root node 2p to each support of input measures μ,, v to respectively obtain ((%)). v((e) for all edges e E Ej..- in graph G. Addition- ally, 8g is also precomputed for all edge in G. Therefore, it is straightforward to implement the computation of Sp v) in Equation (10) with complexity O(E,,.)))
Theorem 3.5 (Discrete case). Let X be the length measure on G. and 1 S p < oo. Suppose that p. v E P(G) are supported on nodes V of graph G. Then we have
Sp(H,1)
-
Σ F
Ba (m(()) -(()))))
(10)
where for each edge E E of graph G. the scalar number Be is given by
4. Properties of Regularized Sobolev IPM
4.1. Metric and Its Relations
8e = log 1 T+\(36)
if =p=2.
(11)
Metrization.
We prove that the regularized Sobolev IPM
(1+2(70)+mm) (1+
otherwise.
is metric.
"See Appendix $C.1 for Soc- 'We discuss an extension for measures supported in graph G Appendix SC.3.
Theorem 4.1 (Metrization). For any 1 S < oo, the regularized Sobolev IPM S, is a metric on the space P(G) of probability measures on graph G.

---

Scalable Soboley IPM for Probability Measures on a Graph
The proof is placed in Appendix $A.4.
The proof is placed in Appendix $A.8.
We note that it is still open question for the exact rela- tionship between the regularized Sobolev IPM S, and the p- Wasserstein distance Wp when > 1. Nevertheless, we next illustrate that Sp is lower bounded by W1.
Connection to the original Sobolev IPM. We next show that the regularized Sobolev IPM is equivalent to the original Sobolev IPM.
Theorem 4.2 (Relation with original Sobolev IPM), For a nonnegative Borel measure on G, 1 s co, we have
Proposition 4.6 (Bounds). Suppose that graph G is a tree and X is the length measure on graph G. Then, for any S Oc, we have
(12) for every p. V.C. E P(G), where 01, C2 are constants defined in Theorem 3.2. Hence, the regularized Sobolev IPM is equivalent to the original Sobolev IPM.
cr Sp(p,, S Sp(u.v) S c2 Sp(,
Sp(un) IIG)L+ Wi(u.)).
The proof placed in Appendix $A.9.
The proof is placed in Appendix $A.5.
4.2. Regularized Sobolev IPM Kernels
Connection to the Sobolev transport (Le et al., 2022). For $ p < 00, let STp be the p-order Sobolev transport, which is scalable variant of optimal transport for measures on graph (Le et al., 2022). The next result provides the relation between our regularized Sobolev IPM Sp and the Sobolev transport STp p.
Negative definiteness."
Proposition 4.7 (Negative definiteness). Suppose that X is the length measure on graph G, and imput probability measures are supported on nodes V of graph G. Then Sp. and Sy are negative definite for every 1 s p 2
Proposition 4.3 (Relation with Sobolev transport). For a nonnegative Borel measure on G, 1 S p < 0o, we have
The proof is placed in Appendix $A.10.
VT, (13) (1+)(G)) 8 STp(H,)) S Sp(u,v)
Positive definite kernels. From Proposition 4.7 and fol- lowing Berg et al. (1984, Theorem 3.2.2, pp. 74), given > 0, 1 S p S 2 and probability measures μl, v/ supported on nodes of graph G, the kernels
for every p. P(G). Hence, the regularized Sobolev IPM is equivalent to the Sobolev transport.
The proof is placed in Appendix $A.6.
kss, (4. = exp(-ts,
(14)
Regularized Sobolev IPM with different orders. We es- tablish relation between different orders for the regularized Sobolev IPM.
k (xpp))=xx(((S
(15)
are positive definite.
Proposition 4.4 (Upper bound). Let X be any finite and nonnegative Borel measure on G. Then we have
Infinite divisibility for the regularized Sobolev IPM ker- nels. We show that the kemels kg, and kgg based on the regularized Sobolev IPM are infinitely divisible.
Sp(p.v) S (X(G) XG)) Sy(,,v) for any exponents p and q satisfying S < < CC.
Proposition 4.8 (Infinite divisibility). For 1 ssps 2, the kernels kis and kigg are infinitely divisible.
The proof is placed in Appendix $A.7.
Connection to the Wasserstein distance. We establish the following relation between the regularized Sobolev IPM and the Wasserstein distance.
The proof is placed in Appendix $A.12.
As for infinitely divisible kernels, regardless of their hyper- parameter f, it suffices to compute the Gram matrix of these kernels ks,, and ksg (1 S p I 2) for probability measures on a graph in the training set once.
Proposition 4.5 (Tree topology). Suppose that graph G is tree and X is the length measure on graph G. Then, for probability measures μ. PPG), we have
(1( W),
5. Related Works
where W1 is the 1- L-Wasserstein " with ground cost de (i.e., tree- Wasserstein distance (Le et al., 2019)).
In this section, discuss related works capitalizing on the Sobolev IPM and Sobolev geometric structure.
"We review Sobolev transport STp in Appendix $B.2. We review p- Wasserstein distance Wd in Appendix $B.3.
We follow the definition of negative definiteness in Berg al. (1984, pp. 66-67). We give review on kernels Appendix $B.4.
5

---

Scalable Soboley IPM for Probability Measures on a Graph
Liang (2017) leverages Sobolev IPM study the conver- gence rate for learning density with the GAN framework. This work shows how convergence rates depend on Sobolev smoothness restrictions within the Sobolev IPM. Liang (2017) also further exploits Sobolev geometry to derive gen- eralization bounds for deep ReLU discriminator networks in GAN. Additionally, Singh et al. (2018); Liang (2021) improve these results under Sobolev IPM by employing the adversarial framework for the analysis. More recently; Koz- doba et al. (2024) leverages Sobolev norm for unnormalized density estimation.
Sobolev transport (ST) (Le et al., 2022) is scalable variant of OT a graph, which constraints the Lipschitz condi- tion within the graph-based Sobolev space. Moreover, the p-order ST can be considered as a generalization of the Sobolev discrepancy, which constraints the critic function within a unit norm defined by the L*-norm of its gradient. Additionally, Le et al. (2023) extend ST for the unbalanced setting where input measures may have different total mass, while Le et al. (2024) leverage class of convex functions to extend ST to more general geometric structures which is beyond its original I.- -e-gemmtrricc structure.
Nickl & Pötscher (2007) study bracket metric entropy for Sobolev space, which plays a central role in many limit theorems for empirical processes (Dudley, 1978; Ossiander, 1987; Andersen al., 1988), and for studying convergence rates, lower risk bounds of statistical estimators (Birgé & Massart, 1993; Geer, 2000).
6. Experiments
In this section, we illustrate the fast computation for the reg- ularized Sobolev IPM, which is comparable the Sobolev transport (ST), and several-order faster than the standard optimal transport (OT) for measures on graph. We then show preliminary evidences on the advantages of the regular- ized Sobolev IPM kernels to compare probability measures on a given graph under the same settings for document classification and for TDA.
Sobolev GAN (Mrouch et al., 2018) exploits the so-called Sobolev discrepancy to compare probability measures for the GAN framework. More concretely, Sobolev GAN con- straints the critic function in IPM within a unit ball defined by the L of its gradient function with respect to dominant measure, which shares the same spirit the Sobolev Wasserstein GAN approach (Xu et al., 2020). On the other hand, Fisher GAN (Mroueh & Sercu, 2017) con- straints the critic function by the 1.2-norm of itself with respect to a dominant measure. Thus, the Sobolev norm (Equation (3)), which integrates information from both critic function and its gradient function, can be regarded unifi- cation for the approaches in Fisher GAN and Sobolev GAN within the Sobolev IPM problem.
Document classification. We consider 4 popular document datasets: TWI TWITTER, RECIPE, CLASSIC, AMAZON. The properties of these datasets are summarized in Figure 2. As in Le et al. (2022), we use word2vec word embedding (Mikolov et al., 2013) to map words into vectors in R-300 Thus, each document is represented as a probability measure where its supports are in 1g300, and their corresponding mass is the word frequency in the document.
Mrouch (2018) proposes the kernelized approach for the Sobolev discrepancy which constraints the critic function of the Sobolev discrepancy within a reproducing kernel Hilbert space. Then Mrouch et al. (2019a) leverages the kemnel Sobolev discrepancy to quantify kinetic energy to propose Sobolev descent, i.e., gradient flow that finds a path of distributions from source to target measures minimizing the kinetic energy. Additionally, Mrouch & Rigotti (2020) extend the kernelized approach to unbalanced settings where source and target measures may have different total mass.
TDA. We consider orbit recognition the synthesized Orbit t dataset (Adams et al., 2017), and object classifica- tion on 10-class subset of MPEG7 dataset (Latecki et al., 2000) as in Le et al. (2022). The properties of these datasets are shown in Figure 5. Objects of interest are represented by persistence diagrams (PD), extracted by algebraic topol- ogy methods (e.g., persistence homology) (Edelsbrunner & Harer, 2008). Therefore, each PD can be regarded as distribution of 2D topological feature data points with uniform mass.
Belkin et al. (2006) leverages Sobolev norm for manifold regularization in semi-supervised learning (SSL). Husain (2020) studies Sobolev IPM uncertainty set for the distri- butional robust optimization, and links the distributional robustness with the manifold regularization penalty (Belkin et al., 2006). Additionally, Mrouch et al. (2019b) uses Sobolev discrepancy to propose Sobolev independence cri- terion for nonlinear feature selection. Furthermore, Nietert et al. (2021) employs Sobolev IPM to analyze theoretical properties for Gaussian-smoothed p- Wasserstein distance.
Graph. We consider the graphs GLog and Gsyn (Le et al., 2022, $5) for experiments. Empirically, these graphs satisfy the assumptions in $2, similar to observations in Le et al. (2022). 12 We consider M 10?, 103 10 as the number of nodes for these graphs, but omit M = 10a in MPEG7 due to the small size of this dataset. Recall that graphs GLog and GSan have (M log M) and 3/3/2 edges respectively. 12We review these graphs in Appendix $C.3.
6

---

Scalable Sobolev IPM for Probability Measures on a Graph
TWITTER (3/3108/26)
RECIPE (15/4370:340)
CLASSIC (4:7093/197)
AMAZON (4:8000/884)
0.58
Average Accuracy
0.72
0.56
0.9
0.8
0.71
0.54
0.8
0.7
0.7
0.52
0.7
0.8
0.5
0.8
0.5
0.4
0.48
0.5
0.67
0.3
Time Consumption (s)
10
10a
10
104
107
108
10
Aey
Figure 2: SVM results and time consumption for kernel matrices with graph GLog. For each dataset, the numbers in the parenthesis are the number of classes; the number of documents; and the maximum number of unique words for each document respectively.
Table 1:
The number of pairs of probability measures on datasets for kernelized SVM.
We randomly split each dataset into 70%/30% for training and test respectively, with 10 repeats, and use 1-vs-1 strat- egy for SVM classification. Typically, hapem-parameters are chosen via cross validation. Concretely, SVM regu- larization is chosen from {0.01, 0.1, 10), and kernel hy- perparameter is chosen from {1/q., 1/(2g.). 1/(5g))) with = 10, 20, ... ,0, where we write qs for the s% quantile of a subset of corresponding distances on training set. The reported time consumption for kernel matrices includes all preprocessing procedures, c.g., computing shortest paths on graph for S, ST, or sampling tree from graph for TW.
Datasets
#pairs
TWITTER
4394432
RECIPE
8687560
CLASSIC
22890777
AMAZON
29117200
Orbit
11373250
MPEG7
18130
Root node 20- The regularized Sobolev IPM Š is defined on graph G with root node žy- Notice that 2g characterizes the graph derivative for functions on (Definition 3.1). Much as Sobolev transport (Le et al., 2022), we employ the sliced approach to weaken this dependency. More precisely, we uniformly average S over different choices of root nodes, i.e. sliced variant for S.
In Table 1, show the number of pairs requiring evaluate distance for SVM on each run. Especially, in AMAZON, there are more than 29 million pairs of probability measures.
SVM results and discussions. The reported results for all datasets are with M = 10 except for MPEG7 with M = 10ss due to the small size of this dataset. We illustrate SVM results and time consumption for kernel matrices on document classification for graphs GLog and GSy in Fig- ures 2 and respectively. For TDA, we show the results for Gtag and Gsgn in Figures 5 and 6 respectively.
Classification. We use kernelized support vector ma- chine (SVM) for document classification and TDA. Specif- ically, we evaluate regularized Sobolev IPM kernels ks, k.s.., kag; ST kernels (STTtgKkTTg 13, and kemnels exp(-td(..)) with t > where d is a distance (e.g., OT with ground cost de, tree- Wassersssernnn (TW) with tree sam- pled from graph GG as considered in Le et al. (2022). The kernels corresponding to the two choices of are respec- tively denoted as kor, krw. Note that kernel kor is empir- ically indefinite. We regularize its Gram matrices by adding sufficiently large diagonal term as in Cuturi (2013).
kgg
The computation of regularized Sobolev IPM S is several- order faster than the traditional OT with ground cost dg. Additionally, the computation of S comparable Sobolev transport ST, a.k.a., scalable variant of OT a graph. Especially, for Orbit t dataset, either with graph Gr.ng or GSgn it took more than 39 hours to evaluate the kernel Gram matrices for the OT kernel KOT, but less than 34 minutes for regularized Sobolev IPM kernels for all exponents p = 1, 1.5.
1 Note that KST, = kkz by Proposition 4.3.
7

---

Scalable Soboley IPM for Probability Measures on a Graph
TWITTER (3/3108/26)
RECIPE (15/4370:340)
CLASSIC (477093/197)
AMAZON (4/8000/884)
Average Accuracy
0.72
0.55
0.9
0.9
0.8
0.71
0.8
0.7
0.5
0.6
0.6
0.5
0.68
0.4
0.5
0.67
0.4
0.3
Time Consumption (9)
10
102
10
10
102
10
Figure SVM results and time consumption for kernel matrices with graph Gsqrt.
TWITTER
RECIPE
CLASSIC
AMAZON
Average Accuracy
0.72
0.56 0.71
0.94
0.7
0.52
0.93
0.69
0.92
0.48
0.85 20
10
15
20
Time Consumplion
10
105
10
10
10
10
15
20
20
slices
Agu
Reaz
Figure 4: SVM results and time consumption for kernel matrices of slice variants with graph GLog-
The performances regularized Sobolev IPM kernels com- pare favorably with those of ST, OT, TW kernels. Similar to observations in Le al. (2022), the infiniteness of kot may become hinder for its performances in certain applications. For examples, the performances of koT are affected in most of our experiments, except the ones in RECIPE with graph GL.ng and in Drbit with graph G Additionally, TW kernel krw uses partial graph information, but is posi- tive definite unlike its counterpart kor. Performances of krw are worse than its counterpart kot in RECIPE, but better than kor in CLASSIC, IC, AMAZON for both graphs GLoog and GSg which agrees with observations in Le al. (2022). For performances, similar to Sobolev transport, one may turn the exponent for the regularized Sobolev [PM in applications, e.g., via cross validation.
Additionally, we illustrate performance of sliced variants with graph GLog in Figures 4 and for document classifi- cation and TDA respectively. When the number of slices increases, their performances are improved but it comes with trade-off increasing the computational time linearly.
Further empirical results are placed in Appendix SC.2.
7. Conclusion
In this work, we propose a novel regularization for Sobolev IPM for probability measures graph. The regularized Sobolev IPM admits closed-form expression for fast com- putation. It paves the way for applying Sobolev IPM in applications, especially for large-scale settings. For future works, it interesting to extend the approach to unbalanced
8

---

Scalable Soboley IPM for Probability Measures on a Graph
Orbit (5000/300)
MPEG7 (200/80)
Orbit (5000/300)
MPEG7 (200/80)
Average Accuracy
Average Accuracy
0.7
0.35
0.5
0.3
0.5
0.8
0.25
0.5
0.3
0.15
0.4
0.1
10
105
Time Consumption
Time Consumption
100
109
104
10"
10
10
Prow
Avmr
Rurry
Figure 5: SVM results and time consumption for kernel matrices with graph Gog. For each dataset, the numbers in the parenthesis are respectively the number of PD; and the maximum number of points PD.
Figure 6: SVM results and time consumption for kernel matrices with graph Gsyt-
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.
setting where input measures may have different total mass, and to go beyond the Sobolev geometric structure, e.g. tack- ling more challenging geometric structure for IPM such as critic function within unit ball defined by Besov norm, i.c., Besoy IPM, for practical applications.
Impact Statement
The paper proposes novel regularization for Sobolev IPM for probability measures on a graph, which yields closed form expression for fast computation. Our work paves a way to use Sobolev IPM for practical applications, especially for large-scale settings. To our knowledge, there are no foresee potential societal consequences of our work.
0.5
0.75
Average Accuracy
0.45
0.50
0.4
0.00
0.8
3.40
10
References
10
Time Consumption
Achlioptas, P., Diamanti, O., Mitliagkas, I., and Guibas, L. Learning representations and generative models for 3D point clouds. In International conference machine learning, pp. 40-49, PMLR, 2018.
10"
100
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.
Number
Syp
Ag
Figure SVM results and time consumption for kernel matrices of slice variants with Grag-
Adams, R. A. and Fournier, J. J. Sobolev spaces. Elsevier, 2003.
Acknowledgements
We thank the area chairs and anonymous reviewers for their comments. KF has been supported in part by Grant-in- Aid for Transformative Research Areas (A) 22H05 106 and IST CREST JPMJCR2015. HH acknowledges the support
Andersen, N. T., Giné, E., Ossiander, M., and Zinn, J. The
central limit theorem and the law of iterated logarithm for empirical processes under local conditions. Probability theory and related fields, 77(2):271-33 --05, 1988.

---

Scalable Soboley IPM for Probability Measures on a Graph
Belkin, M., Niyogi, P., and Sindhwani, V. Manifold regular- ization: A geometrie framework for learning from labeled and unlabeled examples. Journal of machine learning research, 7(1 2006.
Kozdoba, M., Perets, B., and Mannor, S. Sobolev space reg- ularised pre density models. In Forty-first International Conference on Machine Learning, 2024.
Kriege, N. M., Johanssnn, D., and Morris, C. survey on graph kernels. Applied Network Science, 5:1-42, 2020.
Berg, C., Christensen, J. P. R., and Ressel, P. (eds.). Har- monic Analysis on Semigroups. Springer-Verglag, Verglag, New York, 1984.
Kusano, G., Fukumizu, K., and Hiraoka, Y. Kernel method for persistence diagrams via kernel embedding and weight factor. The Journal of Machine Learning Research, 18(1))6947-6987, 2017.
Birgé, L. and Massart, P. Rates of convergence for mini- mum contrast estimators. Probability Theory and Related Fields, 97:113-150, 1993.
Kusner, M., Sun, Y., Kolkin, N., and Weinberger, K. From word embeddings to document distances. In International conference on machine learning, pp. 957-966, 2015.
Blei, D. M., Ng, A. Y., and Jordan, M. I. Latent Dirichlet allocation, Journal of Machine Learning Research, 3: 993-1022, 2003.
Latecki, L. J., Lakamper, R., and Eckhardt, T. Shape descrip- tors 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.
Borgwardt, K., Ghisu, E., Llinares-Lóópzz, F., O'Bray, L.., Rieck, B., et al. Graph kernels: State-of-the-art and future challenges. Foundations and Trends@ in Machine Learning, 13(--6):511-712, 2020.
Cuturi, M. Sinkhorn distances:
Lightspeed computation of optimal transport. In Advances in Neural Information Processing Systems, pp. 2292-2300, 2013.
Le, T. and Nguyen, T. Entropy partial transport with tree metrics: Theory and practice. In International Confer- ence on Artificial Intelligence and Statistics, pp. 3835- 3843. PMLR, 2021.
Divol, V. and Lacombe, T. Estimation and quantization of expected persistence diagrams. In International confer- ence on machine learning. pp. 2760-2770. PMLR, 2021.
Le, T. and Yamada, M. Persistence Fisher kerne:: A Rie- mannian manifold kernel for persistence diagrams. In Advances in Neural Information Processing Systems, pp. 10007-10018, 2018
Dong, and Sawin, W. COPT: Coordinated optimal trans- port on graphs. Advances in Neural Information Process- ing Systems, 33: 19339937-,,3,, 2020.
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.
Dudley, R. M. Central limit theorems for empirical mea- sures. The Annals of Probability, pp. 899-929, 1978.
Edelsbrunner, H. and Harer, J. Persistent homology A survey. Contemporary Mathematics, 453:257-282, 2008.
Le, T., Ho, N., and Yamada, M. Flow-based alignment approaches for probability measures in different spaces. International conference on artificial intelligence and statistics, pp. 3934 3942, PMLR, 2021.
Geer, S. A. Empirical Processes M-estimation, volume Cambridge university press, 2000.
Gretton, A., Borgwardt, K. M., Rasch, M. J., Schölkopf, B., and Smola, A. A kemee two-sample test. The Journal of Machine Learning Research, 13(1):723-773, 2012.
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 Statistics, pp.
Hua, B.-S., Tran, M.-K., and Yeung, S.-K. Pointwise con- volutional neural networks. In Proceedings of the IEEE
PMLR, 2022.
conference on computer vision and pattern recognition, pp. 984-993, 2018.
Le, T., Nguyen, T., and Fukumizu, K. Scalable unbalanced Sobolev transport for measures on a graph. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 8521-8560. PMLR, 2023.
Husain, H. Distributional robustness with IPMs and links to regularization and GANs. Advances in Neural Informa- tion Processing Systems, 33:11816-11827, 2020.
Le, T., Nguyen, T., and Fukumizu, K. Generalized Sobolev transport for probability measures on graph. In Forty- first International Conference on Machine Learning, 2024.
Kolouri, S., Ketz, N. A., Soltoggio, A., and Pilly, P. K. Sliced Cramer synaptic consolidation for preserving deeply learned representations. In International Con- ference on Learning Representations, 2020.
10

---

Scalable Soboley IPM for Probability Measures on a Graph
Liang, T. How well can generative adversarial networks learn densities: A nonparametric view. arXiv preprint, 2017.
Nietert, S., Goldfeld, Z., and Kato, K. Smooth P Wasserstein distance: structure, empirical approximation, and statistical applications. In International Conference on Machine Learning, pp. 8172-811 -183. PMLR. 2021.
Liang, T. Estimating certain integral probability metric (IPM) is as hard as estimating under the IPM. arXiv preprint, 2019.
Nikolentzos, G., Siglidis, G., and Vazirgiannis, M. Graph kernels: A survey. Journal of Artificial Intelligence Re- search, 72:943-1027, 2021.
Liang, T. How well generative adversarial networks learn distributions, Journal of Machine Learning Research, 22 (228):1-41, 2021.
Ossiander, M. A central limit theorem under metric entropy with L2 bracketing. The Annals of Probability, pp. 897- 919, 1987.
Mikolov, T., Sutskever, I., Chen, K., Corrado, G. S., and Dean, J. Distributed representations of words and phrases and their compositionality. In Advances in Neural Infor- mation Processing Systems, pp. 31 11-3119, 2013.
Petric Maretic, H., El Gheche, M., Chierchia, G., and Frossard, P. GOT: An optimal transport framework for graph comparison. Advances Neural Information Pro- cessing Systems, 32, 2019.
Mroueh, Y. Regularized finite dimensional kernel Sobolev discrepancy. arXiv preprint, 2018.
Peyré, G. and Cuturi, M. Computational optimal transport. Foundations and Trends@ in Machine Learning, 11(5-6); 355-607, 2019.
Mroueh, Y. and Rigotti, M. Unbalanced Sobolev descent. Advances in Neural Information Processing Systems, 33: 17034-17043 2020.
Peyre, R. Comparison between W2 distance and H norm, and localization of Wasserstein distance. ESAIM: Con- trol, Optimisation and Calculus of Variations, 24(4):1489- 1501, 2018
Mroueh, and Sercu, T. Fisher GAN. Advances neural information processing systems, 30, 2017.
Mroueh, Y., Li, C.-L.., Sercu, T., Raj. A.. and Cheng, Y. Sobolev GAN. In International Conference on Learning Representations, pp. 5767-5777, 2018.
Rieck, B., Bock, C., and Borgwardt, K. A persistent Weisfeiler-Lehman procedure for graph classification. In International Conference on Machine Learning, pp. 5448- 5458. PMLR, 2019.
Mroueh, Y., Sercu, T., and Raj, A. Sobolev descent. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 2976-2985. PMLR, 2019a.
Singh, S., Uppal, A.,
Zaheer, M., and Póczos, B. Nonparametric density estimation under adver- sarial losses. Advances in Neural Information Processing Systems, 31, 2018.
Mroueh, Y., Sercu, T., Rigotti, M., Padhi, I., and Nogueira dos Santos, C. Sobolev independence criterion. Advances in Neural Information Processing Systems, 32, 2019b.
Sparck Jones, K. A statistical interpretation of term speci- ficity and its application in retrieval. Journal of documen- tation,
Müller, A. Integral probability metrics and their generating classes of functions. Advances in Applied Probability, 29 (2):429 443, 1997.
1972.
Sriperumbudur, B. K., Fukumizu, K., Gretton, A., Schölkopf, B., and Lanckriet, G. R. On integral prob- ability metrics, d-divergences and binary classification. arXiv preprint, 2009.
Nadjahi, K., Durmus. A., Chizat, L., Kolouri, S., Shahram- pour, S., and Simsekli, U. Statistical and topological properties of sliced probability divergences. Advances in Neural Information Processing Systems, 33:20802- 20812, 2020.
Tam, E. and Dunson, D. Multiscale graph comparison via the embedded laplacian discrepancy. wrXiv:2201.12064 2022.
Nguyen, T., Pham, Q-H., Le, T., Pham, T., Ho, N., and Hua, B.-S. Point-set distances for learning representations of 3d point clouds. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pp. 10478-10487, 2021.
Tran, H., Chu, T., Nguyen, K., Pham, T., Le, T., and Nguyen, T. Spherical tree-sliced Wasserstein distance. In The Thirteenth International Conference Learning Repre- sentations, 2025a
Nickl, R. and Pötscher, B. M. Bracketing metric entropy rates and empirical central limit theorems for function classes of Besov-and Sobolev-type. Journal of Theoreti- cal Probability, 20:177-199, 2007.

---

Scalable Soboley IPM for Probability Measures on a Graph
Tran, 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, 2025b.
Wang, Y., Sun, Y., Liu, Z., Sarma, S. E., Bronstein, M. M., and Solomon, J. M. Dynamic graph CNN for learning on point clouds. ACM Transactions Graphics (TOG), 38 (5):1-12, 2019.
Tran, H., Pham, T., Tran, T., Nguyen, K., Chu, T., Le, T., and Nguyen, T. Tree-sliced wasserstein distance: A geometric perspective. In Fecto- International Conference Machine Learning, 2025c.
Wu, W., Qi. Z., and Fuxin, L. Pointconv: Deep convolu- tional networks 3D point clouds. In Proceedings of the IEEE/CVF Conference computer vision and pattern recognition, pp. 9621 1921-, 2019.
Tran, T., Tran, 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, 2025d.
Xu, M., Zhou, Z., Lu, G., Tang, J., Zhang, W., and Yu, Y. Towards generalized implementation of Wasserstein distance in GANs. arXiv preprint, 2020.
Yurochkin, M., Claici, S., Chien, E., Mirzazadeh, F., and Solomon, M. Hierarchical optimal transport for doc- ument representation. Advances in neural information processing systems, 32, 2019.
Uppal, A., Singh, S., and Póczos, B. Nonparametric density estimation convergence rates for GANs under Besov IPM losses. Advances in neural information processing systems, 32, 2019.
Zhao, Q. and Wang, Y. Learning metries for persistence- based summaries and applications for graph classification. Advances neural information processing systems, 32, 2019.
Uppal. A., Singh, S., and Póczos, B. Robust density es- timation under Besov IPM losses, Advances in Neural Information Processing Systems, 1455345-33555 2020.
12

---

Scalable Soboley IPM for Probability Measures on a Graph
Supplement to "Scalable Sobolev IPM for Probability Measures on a Graph"
The supplementary is organized into three parts as follows:
In Section A, we provide the proofs for the theoretical results in the main manuscript.
In Section B, we briefly review related notions used our work.
In Section C, we provide further experimental results and discussions about our proposed approach.
Notations.
Let (x) be the indicator function, i.e.,
= {
1
i otherwise.
1x
For two points u, u E I2, let (u, u) be the line segment connecting the two points u, v, and denote (u, 2) for the same line segment but without its two end-points.
A. Proofs
In this section, we give the detailed proofs for the theoretical results in the main manuscript.
A.1. Proof for Theorem 3.2
Proof. Let f E W.P.P. We first derive an upper bound for [[ in terms of 2 Since f(zo) 0. we have
J [((z)1 ((dx))
|
[o [(20) J ('w))(d)) X(dx)
[
Se / [(2000)) (v) (v))(()))( M(dr)
= A(G))) / A(G)
1 | (w) A(dz).
Therefore, by applying Jensen's inequality, obtain
s MGGP / ((G)
(x1 / ( (x(d))) A(dx)
Il
= =\G) 1 ((to)))))))) A(dg))(dr).
By Fubini's theorem, can interchange the order of the integration. As consequence, we obtain
// S AGG)-1 [ | (x) ((dr))(dd)))
= =XGG)-- / (f ((11oo))W))((r)) ( (f
= / ('(1)) X(Al))))dv),
(16)
13

---

Scalable Soboley IPM for Probability Measures on a Graph
where we recall that A(y) (ar G y E [=) (see Equation (I)). Due estimate (16), have
||
(11S11T) + -
(XG))- / /1(6)) + / ( $
| + (/
|
(Je max(1, (1AM)))))
= C2 11
(17)
where we recall that (i(x)
((A())), Vo E G (see Equation (5)), and c2 = [max(11, (1))())))-1)
We next derive a lower bound for Il in terms of I1, follows
(IIIIE + +1
(18)
- (CLICO)PA(())
UL [+A(G))
[+GP|)(()))))))
1+ (
((G(L,
min(1,
I ++Aaa())) F())
1+ +CG))
|1
(19)
where we have used the fact that ||/ 2 to obtain the inequality (18), and recall that cj
min(1.A/G)
1+X(G))
Thus, we conclude from Equations (17) and (19) that
llf'llzg Iffllwr I e2 ll.
The proof is completed.
A.2. Proof for Theorem 3.4
Proof. Consider critic function f W., Then by Definition 3.1, have
(G, =x===(22) + ('y))(dy) for all x x G.
(20)
Using (20), leveraging the indicator function of the shortest path [20, æ],, and notice that ((G) = 1, we get
[ f()))(de)) [ f(zo)u((z)) f f (2nn)) ((y))(d)))(dd))
= f(()) + I (100=((0) I (d))(()))((d)).
14

---

Scalable Sobolev IPM for Probability Measures on a Graph
Then, applying Fubini's theorem interchange the order of integration in the above last integral, we obtain
Je [(())(()==((()) [(00) Se ((sm))(()) (1 f'()) = + [ (// (() o (v))Add)).
Using the definition of Ayy) in Equation (1), we can rewrite it as
Le (w))m(a)) f(z0) / ('V))((N)) A(dv).
By exactly the same arguments, we also have
[ [(E)((d)== f((o) + / ('w))(((y)) X(dy).
Consequently, the regularized Sobolev IPM Equation (8)
can can reformulated as
V. ((AAA()) v(A(x)) X(dx)
Sp(H.v) = sup SEB(y' .d)
(21)
where we recall that Bly/, .) = { W/. 11f $1] (see Equation (7)). Observe that, we have on one hand
(' J E B w) c (g 12' (G, (G,A)) |1gl Lg $1}.
On the other hand, for any g E Lt (G, A), we have = f with f(x) = [ Alv) E It' (G, A).
Therefore, we conclude that
(f's B(p', m) fg E L (G. 109l Lg 1}.
(22)
Consequently, if we let f(x): = ((A()))-
for x E G, then Equation (21) can be recasted
((x)
l ((s)s(o))((
(p(p,)=
sup (G.2):
(23)
(E.) lisll Ep $1
(
(24)
( ((x)) (A()))
where Equation (24) is followed by the dual norm of the weighted L"(G,)) with the weighting function ú.
Hence, we have
Sp ( (xx))= (((())) - ((Ax)))
The proof is completed.
A.3. Proof for Theorem 3.5
Proof. We consider the length measure on graph G for X. Thus, we have X((x)) for all G.
15

---

Scalable Soboley IPM for Probability Measures on a Graph
Consequently, have
( c (M,B)E (M,DjE (u,e)
E
((x))*>Pll( - Xdda).
(25)
(u.e)
Additionally, we consider input probability measures μ. V supported on nodes of graph G. Thus, for all edge e = (u, u) E F., and any point x E (u, v), we have
m(A(=)) v(A())) = (((()) \ (u,u)) v(A(z) \ (u,
Hence, we can rewrite Equation (25) as
Sp
Σ
((x))~>\(AA(A)) \ (u, - -(((x) \ (u, X(xx).
(26)
EU (u,0)
Let consider edge e = (u, v) E. Then for any (u, v). have y E G \ (u, belongs A(x) if and only if y Te where we recall that A(x) and are defined in Equation (1). Thus, we have
Max) \ (u,u) = Yes
Vo E (u, v).
Using this fact, we can rewrite Equation (26) as
Sp(mv)p= EE(,,)EE
Σ
(m(1e) - v((e)l [ [(a..) (x(d))
(27)
We next want to compute the integral in (27) for each edge (u, v) E E. For this, recall that vd(x) = 1 + X(A(z)) (see Equation (5)). Without loss of generality, assume that (z u) S (z v), i... among two nodes u, v of the edge node v is farther away from the root node ž than node u.
Notice that for x E (u, v), we can write x = + t(u v) for t E (0, 1). With this change of variable, we have
[ [1 x-(=))) ((dx)= 1// [1 A(A(++ t(u-ttuuoo) "))) wedt
Moreover, have
(A(u+t(u - ((A()))))))))))))) + M(u,o+ -o
o)]) = M(Te) + wet.
Therefore,
[1+ +++AA)))²>>aaa> = S'¹ [1+ ((Te)) wat wedt.
(u.0)
The last integral can be computed easily depending on the case p = 2 or # 2. As consequence, we obtain
Ju 1 X(A(()))
log 1 +
T+x(Ta) (1+A(%)+ ++ 2--
uc
p=2
(1+
otherwise.
2-p
Thus, we have f(a.o) [1 + (-A( Ba (see Equation (11)). This together with Equation (27) yields
Sp(1,D= = Σ
Belu(re) -Bll((e))-p(71))
(28)
EEE
Hence, the proof is completed.
16

---

Scalable Soboley IPM for Probability Measures on a Graph
A.4. Proof for Theorem 4.1
Proof. For 1 p oo, we will prove that the regularized Sobolev IPM (,)) satisfies: (i) nonnegativity, (ii) indisceriibil ity, (iii) symmetry, and (iv) triangle inequality.
(i) Nonnegativity. By choosing f = 0 in Definition 3.3, we see that Sp(u, v) 2 0 for every measures (1, in P(G)xP(G),
Therefore, the regularized Sobolev IPM Sp is nonnegative.
(ii) Indiscernibility. Assume that Sp(H,, 2) 0. Then we must have
[ [(x))(d))) - Je [(x)v(dx)
(29)
for all / E Wor (G, A) satisfying the constraint || og 1. Indeed, if by contradiction that (29) is not true, then due to (p, v) = there exists a function g E W/ (G, A) such that ll llgl'l I 1, and Ss g(z))(dx)) - Sa g(z))(dx) < O. Then, by choosing critic function f - in Definition 3.3, we see that Sp, > 0. This contradicts the assumption Sp(H, v) = O.
Therefore, Equation (29) holds true. Consequently, we have
Jo [())p(da)= [ (())(dxx)
for every f Wi (G with |lf 1. This gives μ desired.
(iii) Symmetry. Observe that if f E W (G, A) with 1f og I 1, then we have (-f) E Wo (G, with || -1 f'll [1 < 1. As consequence, we have
u) Sp(u,
(iv) Triangle inequality. Let u,v,a a be probability measures in P(G). Then, for any critic function f wo (G, satisfying |1''l1g' S we have
(G,
Vg f(z))(dz) - 1( f(x)u(da))
= ( (x)) - / f(x)o(dr)) + (L (((a)o(aa))) - f(z))(d)))
< 1. f(z))(dxx) / f())o(dx) + 1 f(x)o(dx)) - / f(z))(dx)
(p(u,)) + u),o,
By taking the supremum over critic function f. this implies that Sp(n,)) s (p(, + Sp(a,v).
Hence, from these above properties, we conclude that the regularized Sobolev IPM Sp(,, v) is metric for probability measures on the space P(G).
The proof is completed.
A.5. Proof for Theorem 4.2
Proof. Given positive number > let us consider B(p, w. c) {s ( S { We define the IPM
distance w.r.t. B(p, úi, e) as follows
sup fEBip (0,c) 1 (())p(d)) - fs M()u(da))
v)
(30)
17

---

Scalable Soboley IPM for Probability Measures on a Graph
By exploiting the graph structure for the IPM objective function and applying similar reasoning in the proof of identity (21) in $A.2, rewrite Equation (30)
1e ['<x)(((A())) - A(dx)
(p)(
sup JeB de,c)
(31)
Additionally, by using similar reasoning in the proof of (22) in $A.2, we have
{s': B(p { g 12 (G, llollng s c
(32)
Let f(x) = ((A()) cσ(()
for x E G. Then by using (32), Equation (31) can be recasted as
Ule
S =
sup gELP (G,A): Iill
S
Lg
1 ((00)())((0)1(1
sup getP' (G,A):llo11 S1
(J [()))F(()PP(()
#
(33)
(1e 1 - (MM)))
(34)
Sp(p.)).
(35)
where the Equation (33) is followed by the dual norm of the weighted L I,'(G, A) with weighting function vē; and Equation (35)
followed by the closed-form expression of the regularized Sobolev IPM in Theorem 3.4.
Notice that for 1 S p < oc, from Theorem 3.2, we have
Ilf 2g S Ilfllwor Scal1f'l
This implies that
Bip wi 01) 2 B(y)) 2 Blyl, 02)
Therefore, for probability measures μ, v E P(G), we have
Sp.c (H,v) 2 Sp(,vv) 2 (H,VV.
(36)
follows from Equations (35) and (36) that
1 $,(,, 2 Sp(n,v) 2 2
1 Sp(u,2),
Ci
which gives
e S, S s, s c2 Sp
The proof is complete.
18

---

Scalable Soboley IPM for Probability Measures on a Graph
A.6. Proof for Proposition 4.3
Proof. Observe that 0 - A(A(=)) & A(G) for all G. Consequently, we have
1
1 1 1+ XA())) =151+ V
Therefore, for 1 S < cc, we have
(1 +1+ (0))
((x)² E.G.G
(37)
Additionally, recall that the Sobolev transport STp for μ. P admits closed-form expression (Le al., 2022, Proposition 3.5)
STM(H,)) (L. - ((Arz))
-((A))) A(dr)
(38)
By combining the closed-form expression of the regularized Sobolev IPM (Equation (9) in Theorem 3.4) with Equations (37) and (38), we obtain
S (1+ ( - Sp(,,))
It follows that
(1 (1+A(G)) "' ST,(H, S v)(u,) S ST)(
(39)
The proof is complete.
A.7. Proof for Proposition 4.4
and of I-I are respectively the Proof. For convenience, let h(x) = ((A(z))~ -(Ax))). Recall also that p' p conjugate of p and 9. Then it follows from Theorem 3.4 that
p-1
f( (1(x)) 50) (w(x)) 7 [h(x)))) A(dx).
P0-a)
We can apply Hölder inequality with 1 = p
1> 1 and l'
2 to obtain q-p
U)( v)P < 1/ (1( 2 (+) -
((xx)
[((mie)
pi1-o k(x)P) $ x(dx))
= [
In addition, it follow directly from the definition in Equation (5) that
(<x) s 1 X(G).
for every x E G. Therefore, we further deduce from above estimate and Theorem 3.4 that
Sp(,DDP < J (1L+X()) (dx)
[ (0())>-9h(>)\(
[)G)) " S,(uNDp.
Hence, we obtain
Sp(m, (1G) (()) S,
This completes the proof of the proposition.
19

---

Scalable Soboley IPM for Probability Measures on a Graph
A.8. Proof for Proposition 4.5
Proof. From Proposition 4.3, we have
V) - -Tiu) (),
Additionally, following Le et al. (2022, Corollary 4.3), when graph G is tree and À is the length measure G, we have
ST Wi
where the 1-Wasserstein distance Wi is defined w.r.t. the ground cost de.
Hence, we obtain
v), = (i,
The proof is complete.
A.9. Proof for Proposition 4.6 Proof. From Proposition 4.5, we have
(1(1,)) Wi(..v).
Additionally, Proposition 4.4 gives
S1(AV)) & (A ((G))(+((G)) - Sp(m.)) Ss((u,))
Therefore, we obtain
Wi(ue) & (AG))1 = Sp(u.v).
It then follows that
(p(1,) 2 (A(G)(L + A()))) Wi(uv).
The proof is complete.
A.10. Proof for Proposition 4.7
Proof. For I, E R"", consider the following function
1/v
m
(z(2,2) = || - =11,- =
Σ
[(()) 2(0)1"
where 20()) is the 4th coordinate of æ. We will prove that for S p S the functions E, and ez are negative definite.
For a, b E R. it is obvious that the function (a, b) + (a b)² is negative definite. For 1 S p S 2, following Berg et al. (1984, Corollary 2.10, 78.78), the function (a, b) + la 6/P is also negative definite.
Consequently, the function Øg negative definite since is sum of negative definite functions. Moreover, following Berg al. (1984, Corollary 2.10, 78), we also have that the function l, is negative definite.
Let m be the number of edges in the graph G, i.e., E = m. Following Theorem 3.5, we regard (8a) (((e)) for each edge E E' of graph G as feature map for probability measure onto RT. Therefore, S, is equal to the function É, between these feature maps.
Hence, S, and S3 are negative definite for S p S The proof complete.
20

---

Scalable Soboley IPM for Probability Measures on a Graph
A.11. Proof for Proposition 4.8
Proof. For probability measures μl, supported on nodes in V of graph C, S p 2, and integer N", define the following kernels
Splune)
k3, (1, = exp
(40)
T
Splu
kg v) = exp
(41)
Observe that K3, (1, = Kis, (H,, v) and K3p (1, v) = kigg (1,
Furthermore, both kernels k3s, and kg are positive definite.
Hence, following Berg al. (1984, $3, Definition 2.6, pp. 76), the kernels ks, and ksp are infinitely divisible. The proof is complete.
B. Reviews
In this section, we give a review for related notions used in the development our proposed approach.
B.1. A Review on Functional Spaces
We give a review on the L space, the weighted L space, and Sobolev norm including the case the exponent p = cc.
L space. For a nonnegative Borel measure À on G, denote LP(G, A) the space of all Borel measurable functions I G + such that Se (Xdy)) co. For p co, instead assume that f is bounded X-a.e. Functions f1 E LP(G, A) are considered to be the same if fi() f2(z) for X-ae. x G.
Then, L?(G, X) is normed space with the norm defined by
$
lffler = (L11 ((
for <p<cos
On the other hand, for = oo we have
|f inf :: [f(x)) st for X-a.e G}.
LP space. For nonnegative Borel measure À G, and a positive weight function on ie., u(x) > 0, G. is denote L (G, A) as the space of all Borel measurable functions G - R such that Ss (() co. For p = 0o, instead assume that is bounded d-.e.. Then, I. (G, >) is normed space with the norm defined by
Mf = ( (()))(())> for <p<
For the case p oo, as w())) 0 for every G have
|| = inf (t E R: [f(x)) & t for (i))-ae x reG)
= inf (t (RE:: [f(x) < t for X-ee x x G)
= =Ifflr..
Sobolev norm. For oo and function f e W A), its Sobolev norm (Adams & Fournier, 2003, $3.1) is
11/1wr..> = [[]111+++1(1))))) #
(42)
When oo, its norm is defined as follows:
Il = 11 + 115'
(43)
21

---

Scalable Soboley IPM for Probability Measures on a Graph
B.2. A Review Soholey Transport
We give review on the Sobolev transport for probability measures on graph, and the length measure on graph.
Sobolev transport. For μ. E P(G), and < p the p-order Sobolev transport (ST) (Le et al., 2022, Definition 3.2) is defined as
sup Je (()))(d))) fa ((x)v(d)))
ST 2Tp( =
(44)
s.t. f e WL. A), IIf (G.A) (G.)) 1
where we write for the generalized graph derivative of f. and w A) for the graph-based Sobolev space on G. Proposition B.1 (Closed-form expression of Sobolev transport (Le et al., 2022)), Let be any nonnegative Borel measure on G, and let 1 S p < oo. Then, we have
(T = ( A(x))
where A(x) the subset of defined by Equation (1).
Definition B.2 (Length measure (Le et al., 2022)). Let X be the unique Borel measure on G such that the restriction of X on any edge is the length measure of that edge. That is, X satisfies:
i) For any edge e connecting two nodes u and v, we have ((x,,) y)) (t s)w, whenever (1 s)u se and y t)u + tu for s, E [0, with S t. Here, recall that (x.y) is the line segment in connecting x: and y-
ii) For any Borel set F C G, we have
X²FF) = Σ Ex(Fne). CE
Lemma B.3 (X* is the length measure on graph (Le al., 2022)). Suppose that G has no short cuts, namely, any edge is shortest path connecting two end- end-points. Then, X* is length measure in the sense that
(1=, v)) = dc(x,1) y)
for any shortest path [z. y] connecting x, Particularty, X has no atom in the sense that ((xx)) everr every x E G.
B.3. A Review on IPM and Wasserstein Distance
We give review on IPM and Wasserstein distance for probability measures.
IPM. Integral probability metrics (IPM) for probability measures μ,, v are defined as follows:
I s(x))(dr)) sclruaan) fer
(5(,,)) sup
(45)
Special case: 1-Wasserstein distance (dual formulation).
The 1-Wasserstein distance is special case of IPM. In particular, for F = Fw : If() f()) s dz y)} where recall that de is the graph metric on graph G, then IPM equal to the 1-Wasserstein distance with ground cost dç
- I f(x))((d)) - S. f(o)
W(GP) sup JEFw
(46)
Besides Sobolev IPM, and 1-Wasserstein distance, some other popular instances of IPM include: (i) Besov IPM, (ii) Dudley metric, (iii) total variation metric, (iv) Kolmogorov metric, (v) maximum mean discrepancies (MMD) (Müller, 1997; Sriperumbudur et al., 2009).
22

---

Scalable Soboley IPM for Probability Measures on a Graph
y- Wasserstein distance (primal formulation). Let p oc, suppose that and are two nonnegative Borel measures on @ satisfying (MG) v(G) Then, the p- D-Wasserstein distance between j and is defined as follows:
/
Wp(u, u)
inf =eI((a.e) GxG (a () ((dx, dd),
where IT(, v) = TT E a1 = M4 n2 J mi m2 are the first and second marginals of respectively.
Tree topology. When graph G is a tree, the 1- I-Wasserstein distance yields closed- expression for fast computa- tion (Le et al., 2019) (i.e., tree- Wasserstein (TW)). Le & Nguyen (2021) extend it for unbalanced input measures (i.e., which may have different total masses), and propose novel regularization approach, named regularized entropy partial transport which also admits a closed-form formula for a fast computation. Furthermore, Tran et al. (2025a;b;c;d) have recently developed ire-sliicd-Waaserseeenn on tree-structured systems of lines (i.e., tree systems) to extend TW for applications with dynamic-support measures including generative models, and diffusion models.
B.4. A Review on Kernels
We review definitions and theorems about kernels used in our work.
Positive Definite Kernels (Berg al., 1984, pp. 66-67). A kernel function k S2 x Ω -> R is positive definite if for every positive integer m 2 2 and every points 21, 32, Ima I2 we have
m
2c)
Vei,..., Cm R.
Negative Definite Kernels (Berg al., 1984, pp. 66-67)
kernel function :: Ω x Ω
R is negative definite if for
every integer 2 2 and every points Iı, #2, .... Im Ω we have
2c)k(1) 0,
Ye ... Gr
E RR s.t. Σ =0
Theorem 3.2.2 in Berg al. (1984, pp. 74). Let Te negative definite kernel function. Then, for every / 0, the kernel
k(x,2) A exp (-tk(x, 2))
is positive definite.
Definition 2.6 Berg et al. (1984, pp. 76). exists a positive definite kernel h., such that
positive definite kernel & is infinitely divisible for each n N there
k (k.,)
Corollary 2.10 in Berg et al. (1984, pp. 78).
Let le be negative definite kernel function. Then, for 0 < l < 1, the kernel
k(x,2) & [kxx 2)]*
is negative definite.
B.5. Persistence Diagrams
We refer the readers Kusano et al. (2017, $2) for the review on mathematical framework for persistence diagrams (e.g.. persistence diagrams, filtrations, persistent homology).
C. Further Results and Discussions
In this section, we give further experimental results and further discussions for the regularized Soboley IPM.
23

---

Scalable Soboley IPM for Probability Measures on a Graph
C.I. Further Results
For the case p oo.
The closed-form expression of regularized Sobolev IPM for p 00 is
(u, inf { E R: [(A(x)) ((A())) t for (wx)-ac. x G
w(x))
Proof. We follow the same reasoning for the proof of Theorem 3.4. We recall Equation (23)
/ (x)=)((())(())((()))
Sp(u, = sup
(47)
lall, Lg" 31
Therefore, for p co, by using the dual norm, and let f(x) (((()))-(A(())) for all G, we have (()))
S (M,
(48)
which is the weighted T, (G, X)-norm with the weighting function v..
Hence, we obtain
(x, inf infIIER R
((M=))-P(A(()) w(xx)
1 for (wX))ae reG
The proof is completed.
C.2. Further Experimental Results
We present further results for the regularized Sobolev IPM for document classification and TDA for both graphs Can and GLog with different numbers of nodes M.
For document classification.
Figures 8 and 9 illustrate SVM results and time consumption for kernel matrices on graphs GSqnt and GLog respectively where the number of nodes M = 1000.
Figures 10 and 11 illustrate SVM results and time consumption for kernel matrices on graphs Gsqt and GLog respectively where the number of nodes M = 100.
For TDA.
Figures 12 and 13 illustrate SVM results and time consumption for kernel matrices on graphs Gsyn and GLog respectively where the number of nodes M = 1000.
Figures 14 and 15 illustrate SVM results and time consumption for kernel matrices on graphs Gsyn and GLog respectively where the number of nodes M = 100.
We next provide further results for the regularized Sobolev IPM when varying the number of slices on both graphs Gsyn and Gr.ng for document classification and TDA.
For document classification.
Figure 16 illustrates SVM results and time consumption for kernel matrices on graph Gsy where the number of nodes M 10
Figures 17 and 18 illustrate SVM results and time consumption for kernel matrices on graphs Gsga and GLog respectively where the number of nodes M 1000.
Figures 19 and 20 illustrate SVM results and time consumption for kernel matrices on graphs Gsga and GLog respectively where the number of nodes M 100.
24

---

Scalable Soboley IPM for Probability Measures on a Graph
For TDA.
Figure 21 illustrates SVM results and time consumption for kernel matrices on graph Gsgn where the number of nodes M 10 for Orbit and M = 10 for MPEG7.
Figures 22a and 23a illustrate SVM results and time consumption for kernel matrices on graphs Ggt and GLog respectively where the number of nodes M = 1000.
Figures 22b and 23b illustrate SVM results and time consumption for kernel matrices on graphs Gsyn and GLog respectively where the number of nodes M 100.
TWITTER (3/3108/26)
RECIPE (15/4300/40)
CLASSIC (4/7093/197)
AMAZON (4/8000/884)
0.9
Avorage Accuracy
0.7
0.9
0.8
0.4
0.7
0.08
0.35
0.8
0.6
0.3
0.5
0.25
0.4
0.3
0.08
0.3
10
Time Consumption (8)
10
1
10a
10
10
10P
Movra
Figure 8: SVM results and time consumption for kernel matrices in document classification with Gsgn and M = 1000.
TWITTER (3/3108
RECIPE (15/4370/340)
CLASSIC (47093/997)
AMAZON (4/8000/884)
Average Accuracy
0.7
0.5
0.9
0.98
0.7
0.6
0.8
0.6
0.4
0.50
0.4
0.2
0.3
0.2
10
Time Consumption (b)
10a
102
10
10a
10a
Rangs
Figure 9: SVM results and time consumption for kernel matrices in document classification with GLog and M 1000.
C.3. Further Discussions
For completeness, we recall important discussions on the underlying graph for Sobolev transport in Le et al. (2022), since they are also applied or adapted for the (regularized) Sobolev IPM in our work.
Measures on a graph. In this work, we consider the (regularized) Sobolev IPM between two input probability measures supported on the same graph, which has the same setting as the Sobolev transport (Le et al., 2022).
25

---

Scalable Soboley IPM for Probability Measures on a Graph
TWITTER (3/3108/26)
RECIPE (15/4370/340)
CLASSIC (477093/17))
AMAZON (4/8000/884)
0:45
0.7
Accuracy
0.4
0.8
0.9
0.7
0.35
0.6
0.6
0.5
0.5
0.55
0.3
0.5
0.15
0.2
Time Consumption (s)
108
10?:
10a
10a
10!
10
10a
10
10
10
10
10
few
Figure 10: SVM results and time consumption for kernel matrices in document classification with Gsyt and M = 100.
TWITTER (3/3108/26)
RECIPE (15:4370/340)
CLASSIC (4/7093/197)
AMAZON (4/8000/884)
0.45
Average Accuracy
0.8
0.68
0.7
0.35
0.7
0.8
0.8
0.5
0.65
0.25
0.4
0.5
0.2
0.3
0.3
0.15
0.2
Time Consumption (8)
10P
10a
10a
10a
10a
10*
10a
102
10
10
100
Rsugg
Figure 11: SVM results and time consumption for kernel matrices in document classification with GLog and M 1000
The proposed kernels upon regularized Sobolev IPM are for input probability measures, i.c., to compute similarity between two probability measures, on the same graph. We distinguish our line of research to the following related problems:
Compute distance between two (different) input graphs. For examples, Petric Maretic et al. (2019); Dong & Sawin (2020); Le al. (2021); Tam & Dunson (2022) compute OT problem (i.e., a specific instance of IPM) between two (different) input graphs, where their goals considered problem which computes distance (i.e., regularized Sobolev IPM) between two inpul probubility measures supported on the same graph.
compute distance between two input graphs. They are essentially different to
Graph kernels between two (different) input graphs. Graph kernels are kernel functions between two input graphs to assess their similarity. comprehensive review on graph kernels can be found in Borgwardt et al. (2020); Kriege et al. (2020); Nikolentzos et al. (2021). Essentially, this line of research is different to our proposed kernels, i.e., regularized Sobolev IPM kernels measures similarity between two input probability measures on the same graph.
Path length for points in graph G (Le et al., 2022). We can canonically measure a path length connecting any two points J. y E G where these two points x, y are not necessary to be nodes in V of graph G.
26

---

Scalable Soboley IPM for Probability Measures on a Graph
(5000/300)
MPEG7 (200/80)
Average Accuracy
Time Consumption
10a
10"
Figure 12: SVM results and time consumption for kernel matrices in TDA with Gsy and M 1000.
Orbit (5000:300)
MPEG7 (200/80)
Average Accuracy
0.5
0.4
0.3
0.4
0.1
0.3
0
0.2
Time Consumption
101
10
107
102
10
Ar
Figure 13: SVM results and time consumption for kernel matrices in TDA with GLog and M = 1000.
Consider the edge (u, v)) connecting two nodes u, V. for x, y E R" and x, y E e, we have
8)u sv,
(1 t)u tu,
for some scalars t, E [0, 1]. Thus, the length of the path connecting x, y along the edge e (i.e., the line segment (I, 3)) is equal to |t. 8 we. Consequently, the length for an arbitrary path in can he similarly defined by breaking down into pieces over edges and summing over their corresponding lengths (Le et al., 2022).
Extension to measures supported on G. Much as Sobolev transport (Le et al., 2022), the discrete case of the regularzed Sobolev IPM in Equation (10) can be easily extended for measures with finite supports on G (i.e., supports of the input measures may not be nodes in V. but possibly points edges in E) by using the same strategy measure path length for support data points in graph G. More precisely, we break down edges containing supports into pieces and over their corresponding values instead of the sum over edges.
About the assumption of uniqueness property of the shortest paths on G. As discussed in Le et al. (2022) for Sobolev transport, note that w. E R, for any edge e E E' in graph G., it is 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 are different.
Additionally, for some special graph, e.g., grid nodes, there is no unique-path root node for such graph. However, by
27

---

Scalable Soboley IPM for Probability Measures on a Graph
(5000/300)
MPEG7 (200/80)
0.9
0.8
Average Accurecy
0.6
0.6
0.2
0.5
Time Comsumptio
1.0
10'
Auu
Rortt
Figure 14: SVM results and time consumption for kernel matrices in TDA with GSar and M = 100.
Orbit (5000:300)
MPEG7 (200/80)
Average Accuracy
0.6
0.4
0.0
0.5
Consumption
102
101
Figure 15: SVM results and time consumption for kernel matrices in TDA with GLog and M 100.
perturbing each node, and/or perturbing lengths of edges if G is non-physical graph, with small deviation, can obtain graph satisfying the unique-pati caqque-pathhaee root node assumption.
Besides that, for input probability measures with full supports in graph G, or at least full supports in any cycle in graph G then it exists special support data point where there are multiple shortest paths from the root node to it. In this case, we simply choose one fixed shortest path among them for this support data point (or we can add virtual edge from the root node this support data point where the edge length is deducted by small deviation). In many practical applications (e.g.. document classification and TDA in experiments), can neglect this special case since input probability measures have a finite number of supports.
About the regularized Sobolev IPM. Much as Sobolev transport (Le et al., 2022), we assume that the graph metric space (i.e., the graph structure) is given. We leave the question to learn an optimal graph metric structure adaptively from data for future work.
About the graphs Gr.og and GSqr (Le et al., 2022). For fast computation, we use the farthest-point clustering method to partition supports of measures into at most M clusters." Then, let the set of vertices V be the set of centroids of these clusters, i.c., graph vertices. For edges, in graph GLog, we randomly choose (M log M) edges; and 3/2 edges for graph
14 M the input number clusters used for the clustering method. Thus, we obtain at most clusters, depending on input data points.
28

---

Scalable Soboley IPM for Probability Measures on a Graph
TWITTER
RECIPE
CLASSIC
AMAZON
0.73
0.96
0.96
0.58
Average Accuracy
0.97
0.72
0.58
0.96
0.71
0.54
0.96
0.9
0.52
0.94
0.7
0.5
0.93
0.48
0.92
0.68
0.85
10
Time Consumption (5)
10
105
105
10
10a
10
10
10a
10
15
20
0
10
0
5
10
15
20
5
10
15
20
Number of eliics
Paw
Figure 16: SVM results and time consumption for kernel matrices of slice variants with Gsqnt and M 10
TWITTER
RECIPE
CLASSIC
AMAZON
Average Accurscy
0.78
0.52
0.96
0.92
0.96
0.9
0.71
0.94
0.48
0.7
0.98
0.69
0.90
0.44
0.88
10
15
10
20
5
10
16
10
15
20
Time Consumption (6)
10
10a
10
10a
102
102
10a
10"
10"
Keyg
Figure 17: SVM results and time consumption for kernel matrices of slice variants with Gsyx and M 1000.
Gsgn- We further denote the set of those randomly sampled edges as E.
For each edge e, its corresponding edge length (i.e., edge weight) we is computed by the Euclidean distance between the two corresponding nodes of edge Let n. be the number of connected components in the graph (V, É). Then, we randomly add (n. 1) more edges between these connected components to construct connected graph G from G. Let E, be the set of these (n. added edges and denote set E E U Ec, then G(V, E) is the constructed graph.
Datasets and Computational Devices. For the datasets in our experiments (i.c., TWITTER, RECIPE, CLASSIC, AMAZON for document datasets, and Orbit, MPEG7 for TDA), one can contact the authors of Sobolev transport (Le et al., 2022) to access to them. For computational devices, we run of our experiments on commodity hardware.
Hy Hyperparamter validation. For validation, we further randomly split the training set into 70%/30% for validation- training and validation with repeats to choose hyyper-paramett our experiments.
The number of pairs in training and test for kernel SVM (Le et al., 2024). Let No., Noe be the number of measures used for training and test respectively. For the kernel SVM training, the number of pairs which we compute the distances
29

---

Scalable Soboley IPM for Probability Measures on a Graph
TWITTER
RECIPE
CLASSIC
AMAZON
0.73
0.97
Average Accuracy
0.96
0.72
0.9
0.71
0.94
0.80
0.93
0.92
0.88
10
15
20
10
20
5
10
15
15
20
Time Consumption (6)
10
10"
103
102
10
102
10
10a
5
10
15
20
10
20
0
5
10
15
5
10
15
20
Number Bilices
Kgp
Figure 18: SVM results and time consumption for kernel matrices of slice variants with GLog and M 1000.
TWITTER
RECIPE
CLASSIC
AMAZON
0.44
0.93
Average Accuracy
0.71
0.48
0.92
0.705
0.42
0.91
0.686
0.34
0.69
0.89
0.58
0.685
0.58
0.88
0.80
10a
Time Consumption
10a
102
10a
10P
10'
5
10
15
20
10
15
20
10
15
20
10
15
20
Number of slices
Jaryy Keryy
Royg
Figure 19: SVM results and time consumption for kernel matrices slice variants with Gsgn and M = 100.
(N,, ()) No. run, the number of pairs which we compute the distances for both training and test is totally No, ( (Mu-- + Nie). For examples, in Table 1, we list these number of pairs for kernel SVM for all datasets used in our experiments.
2. For the test phase, the number of pairs which we compute the distances is No. x Nie. Therefore, for each
Distinguish to the approach in Peyre (2018). We study the Sobolev IPM for probability measures supported on a given graph. The Sobolev IPM (Equation (4)) constrains critic function within unit ball defined by the Sobolev norm (Equation (3)) involving both the critic function and its gradient, while Peyre (2018) considers the weighted homogeneous Sobolev norm which constraints critic function in semi-norm involving only gradient of the critic function Peyre (2018, Equations (3) and (4)). Peyre (2018)'s approach shares the same spirit the 2-order Sobolev transport (Le et al., 2022).
The proposed regularized Sobolev IPM may share some spirit with the weighted homogeneous Sobolev norm and the Sobolev transport (i.e., constraint on gradient of a critic function). However, we clarify that the weight function (Equation (5)) plays the key role to establish the equivalence between Sobolev norm and weighted norm (Theorem 3.2) for our novel regularization for Sobolev IPM.
30

---

Scalable Soboley IPM for Probability Measures on a Graph
TWITTER
RECIPE
CLASSIC
AMAZON
0.715
Average Accuracy
0.46
0.92
0.87
0.45
0.68
0.605
0.43
0.84
0.42
0.83
0.685
0.4
6
10
16
10
15
10
15
20
10
Consumption
109
10
10
10¹
10
Number slices
kpw
Kory -
Eeyp
Figure 20: SVM results and time consumption for kernel matrices of slice variants with GLog and M = 100.
Orbit
MPEG7
Avenage Accuracy
0.0
Consumptian
10
15
20
siloes
Figure 21: SVM results and time consumption for kernel matrices of slice variants with graph GSyn where the number of nodes M = 10 for Orbit, and M = 10 for MP EG7,
Further discussions on the research problem and appreach. We emphasize that our approach aims neither derive tight bound for the gap original Sobolev IPM. Our purpose is in different direction. More precisely, instead propose novel regularization for Sobolev IPM which yields equivalent metric to the original Sobolev IPM, and a closed-form expression for a fast computation. Note that, to our knowledge, there are no efficient algoritims to compute Sobolev IPM effectively. We believe that deriving tight bound or providing sharp approximation for the Sobolev IPM interesting research direction, and left for future investigation.
provide sharp approximation for the challenging optimization problem (Equation (4)) of the
31

---

Scalable Soboley IPM for Probability Measures on a Graph
MPE07
O1bR
3.65
Amerage Accrecy
0.5
13
8
0.
Time Consumptten 99
Time Consummption (4)
000
stices
- Rye
Pagi
Payy
Part -
(a) With M 1000.
(b) With 100.
Figure 22: SVM results and time consumption for kernel matrices of slice variants with graph Gsgn-
MPEE7
Orbit
Acsruge Accumcy
86
0:00
Time Consumptton 84
19'
10
Number
Any 20g
With M 1000.
(b) With 100.
Figure 23: SVM results and time consumption for kernel matrices of slice variants with graph GL.g.
32


Reviews:
[{"review_id": "xNzLeOSDTD", "reviewer": "Reviewer_XuWp", "summary": "The paper proposes an equivalent form for the Sobolev IPM on graphs which they call \"Regularized Sobolev IPM\", this form has the advantage to be computable in closed form. \n\nAuthors show that this proposed IPM is equivalent to the original Sobolev IPM and they provide bounds relating it to previous work on Sobolev Transport , and optimal transport on Graphs. \n\nAuthors show that the proposed IPM is negative definite and hence can be used in defining kernels, that are later used in experiments in document classification and TDA.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer XuWp,\n\nThank you for your valuable feedback. Below are the answers for your questions and comments.\n\n**(1) [...]pseudo algorithm (Theorem 3.5)[...] (compute in practice)[...] (preprocessing) is dense and not too informative[...]**\n\n→ We respectfully clarify that the preprocessing is necessary to compute the regularized Sobolev IPM efficiently (i.e., precompute $\\gamma_e$ and $\\beta_e$ for each edge $e$ in graph $\\mathbb{G}$).\n\nAs in line 206-208, following Le et al., 2022, each support $x$ in measure $\\mu$ contributes its mass to $\\mu(\\gamma_e)$ if and only if edge $e$ is in the shortest path between root $z_0$ and $x$. Therefore, for each edge $e$, it is simple to obtain $\\mu(\\gamma_e)$,  $\\nu(\\gamma_e)$ by checking the **precomputed** shortest paths between root $z_0$ and each support in $\\mu$, $\\nu$ respectively. Additionally, $\\beta_e$ is **precomputed**. Hence, it is **straightforward** to implement Equ. (10) in Theorem 3.5. We will clarify it.\n\nWe will follow your suggestion to add the pseudo-code for the computation in Equ. (10).\n\n**(2) [...]example where you can validate (Theorem 4.2)[...]**\n\n→ We respectfully clarify that the findings in Theorem 4.2 are **theoretically and rigorously proved** in Appendix A.5. As in Theorem 4.2, for any nonnegative Borel measure $\\lambda$ on graph $\\mathbb{G}$ and for $1 \\le p < \\infty$, the $p$-order regularized Sobolev IPM is equivalent to the original $p$-order Sobolev IPM.\n\nTo our knowledge, **there are no efficient algorithmic approaches to compute Sobolev IPM (Equ. (4), line 140-142) effectively yet**.\n\n**(3) [...]Theorem 4.2 and other derivations seem related to the weighted sobolev norm and the analysis (Peyre, 2018)[...]** \n\n→ To our knowledge, our theoretical findings are essentially different from the results in Peyre (2018).\n\nWe study the Sobolev IPM for probability measures supported on a given graph. The Sobolev IPM (Equ. (4)) constrains a critic function within the unit ball defined by **the Sobolev norm (Equ. (3), line 124) involving both the critic function and its gradient**, while Peyre (2018) considers the weighted homogeneous Sobolev norm which constraints a critic function in **a semi-norm involving only gradient of the critic function (see Equ. (3) and (4) in Peyre (2018))**. Peyre's approach shares the same spirit as the $2$-order Sobolev transport (Le et al., 2022). We will clarify it.\n\nThe proposed regularized Sobolev IPM may share some spirit with the weighted homogeneous Sobolev norm and the Sobolev transport (i.e., constraint on gradient of a critic function). However, we clarify that **the weight function $\\hat{w}$ (Equ. (5)) plays the key role to establish the equivalence between Sobolev norm and weighted $L_p$ norm (Theorem 3.2)** for our novel regularization for Sobolev IPM.\n\n**(4) [...] (example) quantity (Equ. 1)[...]**\n\n→ We clarify that Equ. (1) is reviewed from Le et al., 2022. Please see **Fig. 1 in Le et al. (2022)** for such illustration.\n\nWe will follow your suggestion to quote more texts and figures from Le et al. (2022) for the review within the limited space in the main manuscript (or placed in the supplementary).\n\n**(5) [...] (define) quantities such as $\\lambda(\\Gamma(x)), \\lambda(\\gamma_e)$ (how to compute them)[...]**\n\n→ $\\lambda$ is a nonnegative Borel measure on graph $\\mathbb{G}$ (**line 70**); $\\Gamma(x)$, $\\gamma_e$ are subgraphs defined in Equ. (1) (**line 57-59**); $\\lambda(\\Gamma(x))$, $\\lambda(\\gamma_e)$ are standard notions of measures on sets.\n\nFor a specific instance, as in Theorem 3.5, we consider $\\lambda$ to be the **length measure on graph $\\mathbb{G}$** (see a review in Def. B.2 and Lemma B.3 in line 1117-1133 (Appendix B.2)), and hence **$\\lambda(\\gamma_e)$ is the total length of $\\gamma_e$**.\n\n**(6) [...]regularized IPM (not make sense)[...]Weighted Sobolev IPM[...]**\n\n→ Following Theorem 3.2, we propose to relax the set of feasible critic functions $\\mathcal{B}(p’)$ (line 128) by $\\mathcal{B}(p’, \\hat{w})$ (Equ. (7), line 128). Therefore, we call it regularized Sobolev IPM. \n\nFor “weighted Sobolev IPM”, it may confuse with IPM where a critic function is constrained within the unit ball w.r.t. weighted Sobolev norm (e.g., some weighted versions of the Sobolev norm in Equ. (3)), which are essentially different to our proposed regularized Sobolev IPM.\n\nWe will consider your suggestion. Thank you.\n\n**(7) [...] (not) introducing these concepts in a clear way[... ]address the clarity issues[...]**\n\n→ We respectfully clarify that all definitions, theoretical findings, and corresponding proofs are **elaborated rigorously in mathematics**. We will follow your suggestions to add more explanation within the limited space.\n\n---\n**Concluding remarks.** We would be grateful if you could let us know whether our clarifications and answers 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.", "claims_and_evidence": "The claims in the paper are sensible and all proofs are provided in the appendix, and the proofs seem correct.", "methods_and_evaluation_criteria": "The evaluation is reasonable and compares accuracy to compute time.", "theoretical_claims": "I checked overall the proofs but did not read the details, the method is sensible.", "experimental_designs_or_analyses": "experiments are on basic classification tasks and show a good accuracy/ compute time tradeoffs.", "relation_to_broader_scientific_literature": "The paper provides a nice contribution in terms of an IPM that is computable in closed form on graphs.", "essential_references_not_discussed": "Authors cite appropriate relevant literature.", "other_strengths_and_weaknesses": "The works is solid and sound theoretically nevertheless is not written in a way that is accessible to other machine learning researchers that have no familiarity with this line of work.\n\n This a  big weakness of the work as it is not didactic in terms of introducing these concepts in a clear way that is easy to grasp. and after the theorems little discussion is made to explain the results.  The notations are heavy and are not conveyed in an easy way to grasp.\n\nsome suggestions to improve the presentation and clarity:\n\n* please introduce a simple graph example and two distributions mu and nu on it in Section 2 as a running example through out the paper and give for the quantity defined in equation 1 \n\nPlease define well quantities such as  $\\lambda(\\Lambda(x))$ how they would be computed and also $\\lambda(\\gamma_e)$ etc... for a unfamiliar reader that is a lot to unpack.\n\n* after Theorem 3.5 give a **pseudo algorithm** that helps understand how this is computed in practice, the preprocessing section  you have in section 4 is dense and not too informative . I checked the code provided to follow what you do in practice the code is in matlab and it will be nice to provide a python code or a pseudo code of how computations are done. Please provide a pseudo code after Theorem 3.5 and show how equation 10 is computed on the running example above. \n\n* After Theorem 4.2 maybe interesting if you can find an example where you can validate this on a small synthetic example.", "other_comments_or_suggestions": "I think calling the proposed method as regularized IPM does not make sense , I would call this \"weighted sobolev IPM\", since it is not just a regularization to the original Sobolev IPM.  I would encourage the authors to call it **Weighted Sobolev IPM on Graphs**.  \n\nTheorem 4.2 and other derivations seem related to the weighted sobolev norm and the analysis in Peyre https://arxiv.org/pdf/1104.4631", "questions_for_authors": "Please address the clarity issues in your revision to help the reader follow and understand.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "NA"}}, {"review_id": "f6xyUAnCTY", "reviewer": "Reviewer_FFqa", "summary": "This paper studies the Sobolev Integral Probability Metric (IPM) for probability measures supported on graph-structured spaces. The authors introduce a regularized version of Sobolev IPM, which allows for a closed-form solution and efficient computation, making it more scalable for large-scale applications. The key contributions include:\n\n- A proof that the regularized Sobolev IPM is equivalent to the original Sobolev IPM and related to Sobolev transport (ST) and optimal transport (OT).\n- Demonstration that the regularized Sobolev IPM is negative definite, allowing for the construction of positive definite kernels.\n- Experimental validation showing that the proposed method is computationally much faster than traditional OT and comparable to ST, with promising performance in document classification and topological data analysis (TDA).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer FFqa,\n\nThank you for your valuable feedback. Below are the answers for your questions and comments.\n\n**(1) [...]Limited Justification for General Graphs[...]claimed to work on graphs, its theoretical analysis and experiments are only carried out on trees[...] (not for) general graphs, where the shortest-path structure may not be unique[...]**\n\n**[...]discuss the potential applications of TW/ST or regularized ST to general graphs?[...]**\n\n→  We respectfully disagree. We clarify that the regularized Sobolev transport can be applied for probability measures on **any given graph $\\mathbb{G}$ such that $\\mathbb{G}$ is connected, undirected, physical graph with positive edge length, and graph $\\mathbb{G}$ satisfies the uniqueness property of the shortest paths (as in line 90-103)**. We emphasize that **there is no requirement that the given graph $\\mathbb{G}$ is a tree**. Furthermore, as in Remark 3.6 (181-189), the regularized Sobolev IPM can be also applied for non-physical graph $\\mathbb{G}$ for the discrete case as in Theorem 3.5 (line 165-179).\n\nFor the uniqueness property of the shortest paths, we clarify that **it does NOT require that there is only one path connecting between two nodes $x, y \\in \\mathbb{G}$ (or the given graph should be a tree)**. In fact, there may exist **multiple different paths with various path lengths**, connecting these two nodes. The uniqueness property of the shortest paths only requires that the shortest path between root node $z_0$ and arbitrary node $x$ to be unique (i.e., **no multiple shortest paths** between them; and there is no problem for **existing multiple different paths** connecting them). Please see line 1467-1480 (Appendix C.3) for the further discussion.\n\nNote that a graph is called geodetic if for every pair of nodes the shortest path between them is unique. Thus, geodetic graphs are special examples satisfying the uniqueness property of the shortest paths (i.e., geodetic graphs are not necessarily trees). Please see **Fig. 1 in Le et al. (2022)** for an example of such geodetic graphs. Moreover, in our experiments, graph $\\mathbb{G}$_Log has $M$ nodes and at least $(M \\log M)$ edges; and graph $\\mathbb{G}$_Sqrt has $M$ nodes and at least $M^{3/2}$ edges. Thus, these graphs are obviously **not trees**. We will clarify it.\n\n**(2) [...]Scalability Claim Relative to Existing Closed-Form Solutions[...]highlights scalability (key advantage), but (TW/ST) already have closed-form solutions[...] (unclear) significant computational benefits beyond[...]**\n\n→ We clarify that **our goal is NOT to scale up the computation of either TW or ST, but the Sobolev IPM** for probability measures on a given graph.\n\nIn this work, we study Sobolev IPM for probability measures supported in a given graph (line 10-13). To our knowledge, **there are no efficient algorithmic approaches to compute Sobolev IPM effectively**, which hinders its practical applications (line 19-22). Please see Equ. (4) for the challenging optimization problem of the Sobolev IPM.\n\nWe propose a novel regularization for Sobolev IPM in Equ. (8) in Def. 3.3 (line 131-139), which yields a closed-form for a fast computation (Theorem 3.5, line 165-179). This paves a way for applying Sobolev IPM in applications, especially large-scale settings.\n\nIn our experiments, **the performances of regularized Sobolev IPM kernels compare favorably with those of ST, OT, TW kernels** (line 371-375). Furthermore, note that TW can only use a partial graph information (line 292-294), i.e., tree information sampled from the given graph.\n\n**(3) [...]Evaluation on Embeddings Instead of Direct Graph Metrics[...]designed for probability measures on graphs[...] (experiments) relies on embedding-based representations (e.g., word embeddings for documents, persistence diagrams for TDA)[...]whether the metric truly captures graph-based probability measure discrepancies or if the improvement is due to embeddings[...]**\n\n→ We agree that there are many different approaches for document classification and TDA tasks. However, it is **not** the goal of our empirical studies. \n\nWe clarify that as in line 299-306, our experiments aim to illustrate the fast computation of the regularized Sobolev IPM, and show preliminary evidences on its advantages compared to other popular transport approaches (e.g., OT, ST) **for probability measures on a given graph under the same settings**.\n\nMore concretely, in our experiments, we consider graphs $\\mathbb{G}$_Log, $\\mathbb{G}$_Sqrt as in Le et al. (2022) (line 326–327), and evaluate for regularized Sobolev IPM, OT, ST to compare probability measures supported on these given graphs under the same settings.\n\n---\n**Concluding remarks.** We would be grateful if you could let us know whether our clarifications and answers 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.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "No. I didn't check the proof line by line, unfortunately.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "No.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "I am confused with the following potential weakness, besides the contribution I mentioned in the summary part.\n\n\n- Limited Justification for General Graphs\n\nWhile the proposed metric is claimed to work on graphs, its theoretical analysis and experiments are only carried out on trees (special cases of graphs). The paper does not provide strong theoretical or empirical justifications for general graphs, where the shortest-path structure may not be unique.\n\n- Evaluation on Embeddings Instead of Direct Graph Metrics\n\nThe method is designed for probability measures on graphs, but its empirical evaluation relies on embedding-based representations (e.g., word embeddings for documents, persistence diagrams for TDA). This raises questions about whether the metric truly captures graph-based probability measure discrepancies or if the improvement is due to embeddings.\n\n- Scalability Claim Relative to Existing Closed-Form Solutions\n\nThe paper highlights scalability as a key advantage, but tree-Wasserstein (TW) and Sobolev transport (ST) already have closed-form solutions. It is unclear whether the new method provides significant computational benefits beyond these existing approaches.", "other_comments_or_suggestions": "NA", "questions_for_authors": "Could the authors discuss the potential applications of TW/ST or regularized ST to general graphs?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xZKJImaafW", "reviewer": "Reviewer_Qz8Z", "summary": "This paper introduces a Scalable Sobolev Integral Probability Metric (IPM) for probability measures defined on graph metric spaces. The key focus is on improving computational efficiency while maintaining mathematical rigor for applications in machine learning, topological data analysis (TDA), and document classification. The contributions include\n1.Introducing a weighted L_p-norm formulation that enables fast closed-form computation, overcomes long-standing computational barriers in Sobolev IPM and extending Sobolev IPM to graph-based metric spaces.\n2.Proving that the regularized Sobolev IPM is a proper metric and showing equivalence to the original Sobolev IPM, ensuring the regularized form preserves theoretical properties.\n3.Moreover, the paper makes some connections Sobolev transport, classical optimal transport (OT) on graphs and Wasserstein distances, particularly for tree-structured graphs. This provides more potential applications of this paper.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer Qz8Z,\n\nThank you for your valuable feedback. Below are the answers for your questions and comments.\n\n**(1) [...]choice of graph structure (not justified)[...]not explain why these specific graph structures were chosen. Different graph structures (e.g., random geometric graphs, small-world graphs) may impact computational performance[...]**\n\n**[...]over-reliance on fixed graph structures [...]choice of graph structure seems not justified[...]not explain why these specific graph structures were chosen and has no discussion on how graph structure impacts Sobolev IPM performance[...]crucial to (Sobolev IPM)[...]**\n\n→ In this work, we study Sobolev IPM for probability measures supported on **a given graph** (line 11–13). As in line 1481–1284 (Appendix C.3), much as Sobolev transport (Le et al., 2022), we assume that **the graph metric space (i.e., the graph structure) is given**. We will clarify it.\n\nOur proposed regularized Sobolev IPM can be applied for probability measures supported on **any given graph $\\mathbb{G}$ such that $\\mathbb{G}$ is connected, undirected, physical graph with positive edge length, and $\\mathbb{G}$ satisfies the uniqueness property of the shortest paths (as in line 90-103)**. Furthermore, as in Remark 3.6 (181-189), the regularized Sobolev IPM can be also applied for non-physical graph $\\mathbb{G}$ for the discrete case as in Theorem 3.5 (line 165-179).\n\nIn our experiments, we consider graphs $\\mathbb{G}$_Log, $\\mathbb{G}$_Sqrt as in Le et al. (2022) (line 326–327). We agree that there are many different approaches for document classification and TDA tasks. However, it is **not** the goal of our empirical studies. As in line 299-306, our experiments aim to illustrate the fast computation of the regularized Sobolev IPM, and show preliminary evidences on its advantages compared to other popular transport approaches (e.g., optimal transport and Sobolev transport) **for probability measures on a given graph under the same settings**.\n\n**(2) [...] (advantages) on fast closed-form computation, the paper presents empirical runtime comparisons, but does not provide a theoretical complexity analysis of its method, for example, on graph size $|V|$ and $|E|$[...]**\n\n→ Besides the preprocessing with computational complexity $\\mathcal{O}(|E| + |V| \\log |V|)$ (line 262-267), from Equ. (10) in Theorem 3.5, the computational complexity of the regularized Sobolev IPM is **trivially linear to the number of edges in $E$ of graph $\\mathbb{G}$, i.e., $\\mathcal{O}(|E|)$**. \n\nMoreover, by exploiting the sparsity property, we **further reduce its computational complexity into $\\mathcal{O}(|E_{\\mu, \\nu}|)$** (line 205-216). We will clarify it.\n\n**(3) [...]proves equivalence with the $1$-Wasserstein distance when the graph is a tree[...]not fully explore relations for $p>1$. No theoretical guarantees on whether the regularized Sobolev IPM behaves similarly to higher-order Wasserstein distances.[...]**\n\n→ We do acknowledge it (line 233-243). For $p=1$, regularized Sobolev IPM is equal to $1$-Wasserstein (**Prop. 4.5**). For $p > 1$, to our knowledge, their relation is an open problem (line 233-235), but $p$-order regularized Sobolev IPM is lower bounded by $1$-Wasserstein (**Prop. 4.6**).\n\nWe respectfully clarify that **our goal for the behavior of the regularized Sobolev IPM is similar to the original Sobolev IPM (Theorem 2), but NOT the $p$-Wasserstein**. We agree that for $p>1$, the regularized Sobolev IPM and $p$-Wasserstein can behave differently. We believe that it **should not be considered as the weakness** for the regularized Sobolev IPM.\n\n**(4) [...]equivalence result (Theorem 4.2) only provides upper and lower bounds[...]not analyze the gap between standard Sobolev IPM and the regularized version[...]**\n\n→ We agree that in Theorem 4.2, we show that the regularized Sobolev IPM is equivalent to the original Sobolev IPM, but not their gap. However, from Theorem 4.2, one can obtain the upper/lower bounds on the **ratio** between regularized Sobolev IPM and original Sobolev IPM.\n\nWe further emphasize that our approach aims neither to derive a **tight bound** for the gap nor to provide a **sharp approximation** for the challenging optimization problem (Equ. (4)) of the original Sobolev IPM. Our purpose is in a different direction. More precisely, we instead propose a **novel regularization for Sobolev IPM** which yields an **equivalent metric** to the original Sobolev IPM, and a **closed-form expression** for a fast computation. Note that, to our knowledge, **there are no efficient algorithms to compute Sobolev IPM effectively yet**. We believe that each approach has its own merits.\n\n---\n**Concluding remarks.** We would be grateful if you could let us know whether our clarifications and answers 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.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "The paper proposes a Scalable Sobolev Integral Probability Metric (IPM) for probability measures defined on graph metric spaces. This makes sense.", "theoretical_claims": "Yes. It looks correct to me overall.", "experimental_designs_or_analyses": "Yes, all experiments look valid to me while I wonder one issue about them: the choice of graph structure seems not justified. The paper does not explain why these specific graph structures were chosen. Different graph structures (e.g., random geometric graphs, small-world graphs) may impact computational performance.", "relation_to_broader_scientific_literature": "The paper contributes to the field of probability metrics, optimal transport, and machine learning on graphs by improving the computational efficiency and applicability of Sobolev Integral Probability Metrics (IPM). These are commonly studied in machine learning community.", "essential_references_not_discussed": "The paper has cited a sufficient amount of related papers to essentially understand their contributions.", "other_strengths_and_weaknesses": "The strengths are listed in \"Summary\".\n\nAs for their weakness, \n1. The paper has over-reliance on fixed graph structures. As mentioned in \"Experimental Designs Or Analyses\": the choice of graph structure seems not justified. The paper does not explain why these specific graph structures were chosen and has no discussion on how graph structure impacts Sobolev IPM performance. I think this question is very crucial to the Sobolev Integral Probability Metric (IPM) proposed in this paper.\n2. The equivalence result (Theorem 4.2) only provides upper and lower bounds, but does not analyze the gap between standard Sobolev IPM and the regularized version.\n3. Moreover, the paper proves equivalence with the 1-Wasserstein distance when the graph is a tree but does not fully explore relations for p>1. No theoretical guarantees on whether the regularized Sobolev IPM behaves similarly to higher-order Wasserstein distances.\n4. As one of the advantages of this paper focusing on fast closed-form computation, the paper presents empirical runtime comparisons, but does not provide a theoretical complexity analysis of its method, for example, on graph size |V| and |E|, etc.", "other_comments_or_suggestions": "Please see the four questions in \"Other Strengths And Weaknesses\".", "questions_for_authors": "Please see the four questions in \"Other Strengths And Weaknesses\".", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "NA"}}]

Author rebuttal:

Meta-review: The paper studies the Sobolev Integral Probability Metric (IPM) for probability measures supported on graph-structured spaces. The authors introduce a regularized version of Sobolev IPM, which allows for a closed-form solution and efficient computation. It includes both theoretical (equivalence between regularized Sobolev IPM is equivalent to the original Sobolev IPM, negative definitess of the regularized SIPM) and experimental contributions. 

This paper was reviewed by three reviewers with the following scores: 3/5,3/5,3/5. Two of the reviewers increased their ratings by 1 point after the rebutal. 
I think the paper is studying an interesting topic and the results are relevant to NeurIPS community. Yet, the following concerns were brought up by the reviewers:
* lack of clarity/ presentation that is not accessible to a broad audience
* role of the graph structure

In its current form the paper may reach only to a niche of readers and it can be further improved in terms of the writing and added explanations and clarifications. It is borderline. 
Authors should carefully go over reviewers' suggestions and address any remaining concerns in their final revision. 
Based on the reviewers' comments, as well as my own assessment of the paper, I recommend acceptance.
Decision: Accept (poster)