Tree Structure for the Categorical Wasserstein Weisfeiler-Lehman Graph Kernel
Authors: Keishi Sando
Tam Le
Hideitsu Hino
Venue: Accepted by TMLR ()

Abstract: The Wasserstein Weisfeiler-Lehman~(WWL) graph kernel is a popular and efficient approach, utilized in various kernel-dependent machine learning frameworks for practical applications with graph data. It incorporates optimal transport geometry into the Weisfeiler-Lehman graph kernel, to mitigate the information loss inherent in aggregation strategies of graph kernels. While the WWL graph kernel demonstrates superior performance in many applications, it suffers a drawback in its computational complexity, i.e., at least $\mathcal{O}(n_{1} n_{2})$, where $n_{1}, n_{2}$ denote the number of vertices in the input graphs. Consequently, it hinders the practical applicability of the WWL graph kernel, especially in large-scale settings. In this paper, we propose the \emph{Tree Wasserstein Weisfeiler-Lehman}~(TWWL) algorithm, which leverages a \emph{tree structure} to scale up the exact computation of the WWL graph kernel for graph data with categorical node labels. In particular, the computational complexity of the TWWL algorithm is $\mathcal{O}(n_{1} + n_{2})$, which enables its application to large-scale graphs. Numerical experiments demonstrate that the performance of the proposed algorithm compares favorably with baseline kernels, while its computation is several orders of magnitude faster than the classic WWL graph kernel. This paves the way for applications in large-scale datasets where the WWL kernel is computationally prohibitive.

Published in Transactions on Machine Learning Research (11/2025)
Tree Structure for the Categorical Wasserstein Weisfeiler- Lehman Graph Kernel
Keishi Sando
www.ppppaammmmttanaaaeeem ac.jp
Deportment of Statistical Science The Groduate Universily for Advanced Studies
Tam Le
tarn Sarm@hiimma.s. ac.jp
The Instibute of Statistical Mathematics
Hideitsu Hino
hino @ism.ac. ac.
The Institute of Statistical Mathematics
Waseda Universily
Reviewed OpenReview: https: https:// https://openrevvieu openreview........ net/ formff?m?? id= VuoSsFK22P
Abstract
The Wasserstein Weisfeiler-Lehman (WWL) graph kernel a popular and efficient approach, utilized in various kernel-dependent machine learning frameworks for practical applications with graph data. It incorporates optimal transport geometry into the Weisfeiler-Lehman graph kernel, to mitigate the information loss inherent in aggregation strategies of graph kernels. While the WWL graph kernel demonst rates superior performance in many appli- cations, it suffers a drawback in its computational complexity, i.e., at least ((nnn)), where n1, f2 denote the number of vertices in the input graphs. Consoquently, it hinders the prac- lical applicability of the WWL graph kernel, especially in large-scale settings. In this paper, we propose the Tree Wasserstein Weisfeiler-Lehmann (TWWL) algorithm, which leverages free structure to scale up the exact computation of the WWL graph kernel for graph data with categorical node labels. In particular, the computational complexity of the TWWL algorithm is (m1 n2), which enables its application to large-scale graphs. Numerical ex- periments demonstrate that the performance of the proposed algorithm compares favorably with bascline kernels, while its computation is several orders of magnitude faster than the classic WWL graph kernel. This paves the way for applications in large-scale datasets where the WWL kernel computationally prohibitive.
1
Introduction
Graph data are popular structure and play fundamental role in many applications
BBarabási & Olivai
2004
Pržulj
2007
Barabási & Pósfai
2016
Petric Maretic et al.] 2019 Xu et al. 2019 Nguyen et al.) 2021
Chen et al. 2022
incent-Cuaz et al. 2022 Le et al. 2022 Kong et al. 2023). To incorporate such structured
Borgwardt et al. Kriege al.] 2020 Nikolentzos et al. 2021) have been proposed in the literature, which measure similarity of input graphs by aggregating their local features, e.g.; histogram kernels (Nikolentzoo et al.
data into machine learning frameworks, several graph kernels (Vishwanathan et al. 2010
2020
2021
compare multisets counting on nodes edges, path-based kernels (Borgwardt & Kriegel 2005 Feragen
accumulate similarities along shortest paths, and graphlet kernels (Pržulj) 2007 Shervashidze evaluate the frequency of small subgraph structures. Despite their effectiveness, these kernels lace certain significant challenges. A primary limitation is poor scalability with the number of nodes in input graphs. For examples, the shortest path kernel relies on the pairwise shortest paths between all graph nodes, which typically requires O(n3), where is the number of nodes in graph. The k-node graphlet kernel requires about On**) induced subgraphs, forcing users either perform an exhaustive count approximate it by sampling; both approaches become prohibitive for moderate k.
et al.
2013)
ct al.
2009

---

Published in Transactions on Machine Learning Research (11/2025)
To overcome this challenge and to enhance the expressiveness of graph kernels, Shervashidze et al. (0011) proposed the Weisfeiler-Tshman (WL) kernels. By coupling iterative neighborhood aggregation with rela- beling, the WL kernel achieves neighborlood-aware representations while retaining computational efficiency. Morcover, Togninalli et al. (2019) leveraged optimal transport (Villani 2009) to enrich the representational
power of the WL kernel, and proposed the Wasserstein Weiseeiler-Lehmre (WWL) kernel. Notice that several traditional graph kernels, c.g., graphlet kernels, shortest-path kernels, and WL subtree kernel (Shervashidze eet al., ), , typically enumerate substructures and then aggregate them by frequency counting or averag- ing. Such a pooling approach collapses the empirical distribution of substructures to its first-order statistics, eliminating information about how different patterns co-occur or how their attributes are distributed. The WWL kernel overcomes this information loss by comparing the entire distributions of node embeddings via the Wasserstein distance (Peyré & Cuturi 2020), thus retaining intricale structural information.
Although the WWL graph kernel strengthens the ability to capture complex graph structures, the Wasser- stein distance within its computation process raises concerns about its scalability (i.c., supercubic computa- tional complexity). Since this challenge stems from the inherent difficulty in optimal transport theory, vari- ous acceleration strategies have been explored in many domains. There are two main acceleration strategies for the computation of the Wasserstein distance: (i) the sliced Wasserstein distance (SWD) (Bonneel et al. 2015), which relies on one- me-dimensional projections of the supports of input measures, and exploits the closed- form expression of univariate optimal transport; and (ii) an entropic regularization approach (Cuturi 2013 which can be solved efficiently by the celebrated Sinkhorn algorithm (Sinkhorul 1964). Extensive research has been conducted related to these approaches. Perez et al. (2024) proposed to utilize the SW approach to approzimate the WWT. kernel, to scale up its computation, which is applicable to large-scale datasets with continuous node attributes. In the Sinkhorn algorithm, various proposals have been introduced in the literature to further reduce its computational cost, including a greedy strategy (Altschuler et al.; 2017) kernel matrix sparsification (Li et al. 2023), and low-rank factorization of the coupling (Scetbon et al. 2021). Additionally, [Tang et al. (2024) proposed to consider a Newton-type method with sparse Hessian matrix to accelerate its convergence. In a complementary direction to SWD and Sinkhorn, a multiscale ap- proach (Mérigol 2011) solves the optimal transport problem on a coarse-to-fine hierarchy with warm starts, which results in reduced runtimes. Another line of work develops a proximal point method for computing the exact Wasserstein distance (Xie ct al. 2019). Using Bregman proximal point scheme with inexact Sinkhorn projections, this algorithm still converges to the exact solution, alleviating entropic bias.
In contrast to the above strategies, by restricting the space to a tree structure, it has been shown that the Wasserstein distance can be expressed in closed form (Indyk & Thaper 2003 Le et al., 2019b). This variant is commonly referred to as the Tree Wasserstein distance (TWD). The computational elliciency of the TWD has been leveraged various applications. Le et al. (2019b) considered the TWD as generalization of the univariate Wasserstein distance, and then proposed the tree-sliced Wasserstein distance as a variant of the SWD. As the choice of tree structure plays a crucial role in the TWD, Yamada et al. (2022) proposed an algorithmic approach for estimating the edge weights to approximate the Wasserstein distance. Lin et al. (2025) addressed the issuc of how to construct a tree by embedding fcatures into a multiscale hyperbolic space via diffusion geomelry, decoding the latent. feature hierarchy into an explicit tree, and defining the TWD on the learned tree. Acceleration algorithms leveraging the TWD have also been proposed for the Wasserstein baryeenter problem (Le et al., [2019a] Takezawa et al. 2022 and for metric learning using Wasserstein singular vectors (Düsterwald et al. 2025).
Following the original formulation of the WWL kernel, subsequent work has advanced both its computational efficiency and its performance. On the performance front, Titouan et al. (2019) proposed the Fused Gromov- Wasserstein distance, which jointly aligns node attributes and graph structure information within a single optimal transport objective. [Chn et al. (2022) introduced the Wasserstein--eehnal distance, a polynomial- time optimal transport metric between labeled Markov chains, that lifts WL iterations to a hierarchy of probability measures. This yields stronger discriminative power than WWL and provides a practical WL lower bound for tractability. [Schulz et al. (2022) proposed a relaxed Weisfeiler-Lehman subtree kernel that encodes WL labels as rooted trees and compares them via tree edit metric. This relaxes the hard 0/1 equality into flexible similarity. [Chuang & Jegelka| (2022) construct, for each graph, the multiset of compulation trees rooted at every vertex and, by defining hierarchical optimal transport between trees, introduced an optimal
2

---

Published in Transactions on Machine Learning Research (11/2025)
transport distance between these multisets graph metric. With respect to computational scalability, Perez et al. (2024) proposed an approximation method that accelerates the WWL kernel for graphs with continuous node attributes, and generic accelerations for Wasserstein computation are likewise applicable.
A challenge in graph- based machine learning is the trade-off between the expressive power of graph com- parison and their computational scalability. While advanced graph metrics can capture both global and local structure, they often demand substantial computational costs. Therefore, developing approaches that achieve effective balance is essential for tackling the large-scale datasets in modern applications. In this paper, we address the acceleration of the WWL graph kernel for datasets with categorical node labels by utilizing the TWD. Specifically, we first show that the labels generated by the WL. algorithm inherently ex- hibit a tree structure, and that the resulting path metric on the tree exactly preserves the Hamminn distance between the labels. This results in a closed-form expression to calculate the WWL kernel for categorical node labels. One notable advantage of our approach over the Sinkhorn approach is its predictable runtime. Whereas the Sinkhorn solver requires a quadratic complexity over the number of iterations to converge, the computational cost of our approach is fixed once the WL algorithm is completed.
Contribution. Our contribution is three-fold:
1. We present that the relationship among generated labels by the WL algorithm forms tree structure.
2. We show that the proposed algorithm, Tree Wasserstein Weisfeiler-Lehman algorithm, is an exact and accelerated method for computing the WWL graph kernel designed for graph datasets with categorical node labels.
3. Numerical experiments demonstrate that the computational complexity of the proposed algorithm outperforms the original WWL kernel algorithm without sacrificing its performances. Morcover, our algorithu makes it feasible to apply the WWL kernel to large-scale categorical-label graph dalasets that are computationally prohibited for the original WWI. graph kernel algorithm.
The paper is organized as follows: Section 2 devoted to notations in this paper. In Section 3 we review the related works that are necessary to construct our algorithum. Our algorithm and its properties are described in Section Section 5 presents the numerical experiments, and we conclude the paper in Section i
Organization.
2 Notations
In this section, we introduce the notations used in subsequent sections. Let g = EV, be an undirected graph; where V and F. denote the set of vertices and edges, respectively. We write the neighborhood of a vertex by Nr V. We denote a set of initial categorical labels by Mo, and say that a graph labeled if each of its vertices assigned label from Eo I Let g == (G1 = (Vi, E..,....Gr.. GN (Vv, Ex]} be set of graphs, N be the number of graphs, n, be the number of vertices in G,, n == Σi= n, be the total number of vertices in 9, and ñ n be the average number of vertices per graph. Throughout this paper, we assume that all graphs in G are labeled and share the same label set Eg. Furthermore, we write V = U V. A function 4o : V + En is used to denote the initial label of vertices.
A sequence of vertices (UI....,Uk) in a graph G is called a walk if an edge exists between every pair of consocutive vertices. If all vertices in the walk are distinct, the walk is called a path. A sequence (#1...., (i.....,yg vk) is called a cycle if its first and last vertices coincide, the vertices "2....,Ukk are distinct, and for every pair of consecutive vertices there exists an edge between them. A graph is connected if, for every pair of vertices there exists path. We denote an edge weight function by E + R20-
A connected graph without cycles is called a tree. We denote tree by T= ((T),,(T) rather than G. The vertices and edge sets of T are denoted ((T) and E(T), respectively. Note that for any pair of vertices
1 For graphs without node lahels, We assign dummy labels each vertex.
3

---

Published in Transactions on Machine Learning Research (11/2025)
in tree, there exists unique path connecting them. This is because the existence of two distinct paths would necessarily imply the presence of cycle, contradicting the definition of a tree.
We write P(u, v) as a set of edges that constitute the path between u, V(T). Given a tree T with a = EeEP(a,v) te where We = w(e). We denote a tree rooted at E (TT) by Tr,, and a set of nodes in a subtree rooted at a E (T,) by n = fo E ((T) ) u E r),, For an edge e E E(Tr), we write We E (T,) for the node closer to the root and 2/ E (T,) for the node farther away from the root node.
weight function w, the path metric between u, E (TT) is defined as d(T,
Figure illustrates the notations of path metric, subtree, and edge endpoints introducod above. The path metric between vertices y and z can be calculated as d(T..w) =) w1 w2 + wa, the subtree rooted al y is indicated by the region outlined in blue, and Fy denotes the set of vertices contained within the region. For the edge that joins vertices z and the endpoint closer to the root is 2, whereas the endpoint farther from the root is Ue 22
3 Related work
Our algorithmic approach accelerates the categorical WWL graph kernel, which combines the WL algorithm with the Wasserstein distance, by leveraging the tree structure over labels within the WL procodure. In this section, review the necessary background and related works that support our approach.
3.1 Wasserstein distance
The Wasserstein distance (Villnn 2009
Peyré & Cuturi 2020 is metrie between probability measures supported on a given metric space. Let (St, d) be a metric space and μ, y be probability measures supported Ω. The LP- Wasserstein distance for p 2 1 is defined as
(",,vv) = ( inf (Ell((..)
/ d(x,, ((x,)))((oo, dy)
1/P
where æ is a probability measure on x S whose marginals are l and v, called a coupling, and I v) is the set of couplings of μ and v. In this paper, we focus on the ---aasserstein distance, which we denote by Wa, i.e. optimal transport with ground cost d.
3.2 Weisfeile--Lehman algorithm
Shervashidze et al. 2011) proposed to incorporate the concept of the Weisfeiler-Tehhan test Weisfeiler & Leman 1968) into graph kernels. The WL test is a procedure for graph isomorphism problem that iteratively refines verlex labels based on their neighborhood structure. This approach yields features that are both highly expressive, by capturing latent graph structure, and computationally efficient, thereby addressing the scalability issues that hindered various graph kernels.
The WL algorithm iteratively assigns new label to each vertex, (reating the resulting sequence of labels the feature of the vertex. Let H E N denote the maximum number of iterations, Σn denote the set of all labels generated at the h-th itcration, and Σ = U Σn denote the set of all labels. At the h-th itcration in the WL algorithm, the new label for vertex is generated as follows, based on its previous label and the set of labels in its neighborhood:
l (v) = hash (1)
where we write Nr (1n-1(u) u e N.) and handle No 1 in its sorted form. The hash function (Cor- men et al. 2009) is defined function commonly used in computer science that returns the same output for identical inputs and returns the distinct value for different inputs. A general description of hash functions is provided in Appendix A Lemma ① immediately follows from the definition of the hash function.
Lemma 1. For every E En, there erists unique label sequence (oo....;hh-1) as E Eg that generates
4

---

Published in Transactions on Machine Learning Research (11/2025)
h
l. N.N
K.N41
A, A,B,,
D. (E.R.G)
T
(A.C)
(B)
y
Fyy
(ABBCC
A.
(R.)
[F.]
G. (P.]
1. 1.
Figure 1: An example of tree no- tations.
Figure 2: An example of the WL algorithm for given graphs with Eg = {A, C.
Figure 2 illustrates the iterative process of the WT. algorithm on labeled graphs g = (91. 92). In this figure, the new labels generated at each step are represented by Latin characters that are not used in the previous steps, reflecting the injectivity of the hash function. Vertices and vy start with identical labels and the same multiset of neighbor labels, meaning that they remain indistinguishable after the first iteration. However, as structural information from farther neighborhoods propagated, their local contexts diverge. This divergence leads to them being assigned distinet labels at = 2. This example demonstrates how the WL algorithm effectively propagates structural information to eventually differentiate vertices that initially appear identical from local viewpoint.
3.3
Weisfeller-Lhhman subtree kernel
The WL subtree kernel, introduced by Shervashidze et al. (2011) leverages the WL algorithm. Based on the label set E generated by the WL algorithm, let c(a, g) denotes the count of label a in G. Then, the WT. subtree feature for G is defined as
member of a graph kernel family that
(G =
We use (5.) to denote inner product, then the WL subtrce kernel two graphs G1, G2 is defined
Kww.subrree 92) (
The WL subtree kernel is positive semidefiiite and can be computed in O(H)), where m the total number of edges in Gi and G2.
3.4 Wasserstein Weisfeiler-Lhhman graph kernel
Most classical graph kernels aggregate substructures by a simple pooling approach, which reduces the empir- ical distribution to first-order statistics and discards information about pattern co-occurrence and attribute variation. To reflect this information in the comparison, Togninalli et al. (2019) proposed the WWL kernel. The key idea is to treat the multiset of WL node labels empirical distribution the label space and to compare the similarity between two graphs via the Wasserstein distance on that space for the WWL kernel.
For labeled graphs, the ground distance between each pair of vertices v Vn, w E Vg is defined by the Hamming distance between their WL label sequences:
Σ (la())) where p(a, b) = {1 + b, h=0
H
dHam (v, w)
(2)
otherwise.
In Togninalli et al. (0119). Equation 2 is normalized by H + 1. Since normalization by a constant does not affect the results, we omit this factor to simplify the discussion.
Due to the uniqueness of the label sequence that generates a label a E Eh and the definition of the hash function, the Hamming distance duam can be regarded metric En. Assigning uniform probability
5

---

Published in Transactions on Machine Learning Research (11/2025)
measure to each vertex induces empirical measures that label space. Let μl, be probability measures En for 91 and G2, respectively. The Wasserstein distance (2 is then computed by
/ dram (2,, (),,))))xx...r)))))))))))))))) (y),dd))) xell(u.v)
W G2) = Waiton (1,1)= =
inf
(3)
and the corresponding kernel is defined by
(9 (2) A
(4)
where is a positive hyperparamcter. Togninalli ct al. (0199) employed either the network simplex algo-
rithin Orlin 1997) to compute the Wasserslein distance or the Sinkhorn algorithm (Sinkhorn 2013 to approximate it.
1964 Culuri
3.5
Tree Wasserstein distance
The Tree Wasserstein distance was initially introduced by Indyk & Thaper (003), and implicitly utilized in UniFrae [ozupone & Knight 2005), which quantifies the similarity between two microbial communities on a reference phylogenetic tree, then was rigorously formalized by Evans & Matsen (2012). When the ground space is a weighted tree, the 1-order Wasserstein distance admits a closed form that can be evaluated in O(E)). In this section, we define the Wasserstein distance on tree and present prior work showing that it admits closed-form expression.
Given that dr is path-length metric on T and μ. are probability measures on T, refer to the L Wasserstein distance on T as the Tree Wasserstein distance and define it below:
inf / | (IT dy). meil(ae))
War (M,
Prior work has established that the Lasaasserttein distance on a tree admits the following closed-for foom expression.
Theorem follows:
Le et al. 2019b The Tree Wasserstein distance can written as (Evans & Matsen 2012
W (1,v)
Σ we -[T(v:))-v[(ie
cεB(T)
Computing this expression requires only a single post-order traversal of the tree. When the tree degenerates to a path, the formula reduces to the standard univariate Wasserstein distance, highlighting TWD a natural generalization. While not adopted in our setting, the closed-form representation in Theorem [ can be written in matrix notation. For further details, we refer the reader to Takezawa et al. (021).
4 Main Algorithm
We propose the Tree Wasserstein Weisman (TWWL) algorithm that enables us to calculate the Wasserstein distance based on the Hamming distance precisely and efficiently, without entropic regulariza- tion. In our algorithm, we focus on the relationship between (v) and 4-1(v)) in Equation 1
Definition 1 (Parent-Child relationship among labels). For Σn and 7 Es+1, if there exists label set. S C Σn such that hash(a, S), then is considered parent label of r, or equivalently, 7 is child label of a.
It is clear from the property of the hash function that the following holds.
Lemma 2. Let u, v be arbitrary vertices in V. If there exists ho H such that Ino (u) # (bo then Yh (ho....,HY, (u) & lu(v) holds.

---

Published in Transactions on Machine Learning Research (11/2025)
D
II
U1
101
M/g
V3. Wy
Figure An illustration of label tree based on graphs in Figure 2
The TWWL algorithm yiclds a tree structure for labels, called the Label Tree, and applics the Tree Wasser- slein distance. The label tree consists of nodes corresponding to the labels produced by the WL algorithm and preserves the relation Definition The steps for constructing a label tree are described in Algo- rithm The label tree is constructed to satisfy the following properties: (i) except for the root node, each node is in one-to-one correspondence with label in Σ; (ii) for every label in Eo, there is an edge connecting it to the root node; (iii) an edge exists between any two labels that satisfy the relation defined in Definition 1 (iv) each edge is assigned a weight of 1/2.
Figure 8 illustrates the label tree constructed from the example in Figure 2 Nodes at depth d in the label tree correspond to the labels generated at the (d-1)-th iteration the WT. algorithm. Taking the label tree properties into consideration, one can intuitively verify that the Hamming distance between Vn and wi, as defined in Equation 2 with H 2, coincides with the length of the shortest path on the tree. The following two lemmas provide formal justification for these claims.
Lemma 3. A label tree obtained by Algorithm a tree.
Proof. We begin by proving the connectivity of the label tree, i.e. that there exists a walk between any O, E E. By Lemma 1 and the property (iii) of the label tree, there exist label sequences (ou...., σ), (Tu...., T) that form a path the label tree. The property (ii) implies that there exist edges connecting the rool to on and To. Therefore, walk exists between o and T.
Next, show that the label tree contains cycle. Suppose, for the sake of contradiction, that there exists
cycle (a, .ı....,7k, a) in the label tree for some label E Σ. Without loss of generality, assume that is the deepest vertex in the cycle. Then, both Ti and тą must be parent nodes of a. By property of the hash
function, T holds. However, this equality contradicts the definition of cycle, which requires that the intermediate vertices are distinct. Therefore, no cycle exists the label tree.
Lemma 4. The mapping o Σn + T obtained by Algorithm 1 is distance-preserviie
Proof. We denote @()) simply as a. We show that for any dH, TH E ΣH, dHam(aH тB) = d(T,1/2) TH) holds. Lemma 1 implies that there exist label sequences (oo...., ,H),, (To. Th) that satisfy the parent- child relationship. From Lemma 2 we consider the following three cases:
Case 1: vh E (O....,H), on The Then, we have both dHam (o TH) and ((T, TH) 0.
Case 2: do * To. Then, it follows from Lemma 2 that dham (oH, TH) = H + 1. Additionally, Lemma 3 implies that the sequence (a....., rool, To: ,o....,TT) is the unique path between σн and TH- Thus, deT,1/2) TH) = H 1.
TH) = H + 1 ho Case 3: 3he E fl....,,HI H}, Th- - and Tho + Tho Then, by Lemma 2 dHam (o is satisfied and the sequence (on,.... Thg Tho 1 The 1, Tho .. TH) is unique path between i1 and TH. This implies (OT, тH) H + ho.
Therefore, Lemma holds for all cases.
The edge weight 1/2 in property (iv) ensures that the path-length metric on the label tree coincides with the Hamming distance on Σn- Along the unique path between two labels hn TH En,, each mismatch at
7

---

Published in Transactions on Machine Learning Research (11/2025)
Algorithm 1:
Tree Structure for TWWL
Input: 9: of graphs with the initial labels lo: H: the maximum number of the WL iterations
Output: Label tree T rooted root, and mapping Lz + V(T)
Struct NODE
// Data Structure for Tree Node
depth: INTEGER
T: VECTOR OF N DOUBLES
children: IASHMAP<LABEL.NODE. end
Function GETOOCREAAECHLL(DDOO label)
if Hnode children, label) then
return node. chwldren [label] [label
end child + wow.deephh-ooddedddeee 1epth+11, label=label, P=Ox, children=(]) InsERT(node. chinddrd key=label, value=child) return child end
root +- NODE(depth=-1, label="", T=0x, children=
que emply FIFO Queue(NODE, GRAPH ID, VERTEX) // process for h=0
for 9j in g do for e V/2 do
child GerOOCCEATTCHHDDOOO, lo(v) ENQUBUE(Que, (child, i, v))
end end
// process for h=1,...,H while lISEMPTY(QUE) do
10
(node, i, v) +- DEQUEUE(QUE) node. I, < Io 1/n,
12
if node. depth < Н then
13
h + node. dedth
child + GeTORCREATECHLLDDOd,, (+)( ENQUEUE(que, (child, i, v))
14
15
16
end
17 end
18
return root
level contributes two unit-length edges, so assigning length 1/2 to each edge yields a total path length equal the number of mismatched levels, i.c., dHam( TH) ( TH). Accordingly, the factor 1/2 in Equation reflects this result.
In lines 17 of Algorithm [ each dequeue operation trigger at most enqueue operation, during which the depth is incremented by one. Hence, the total number of operations in this part is bounded by the product of the initial queue size and the maximum depth H. Since the initial queue elements are inserted one per iteration in lines 3 3 their number is Σ n, = n. Morcover, the time complexity search and insertion in hash map ([1) on average. Therefore, the overall time complexity of Algorithm I is O(H)).
The above results imply that the Wasserstein distance for the categorical WWL graph kernel can be computed efficiently follows.
Proposition 1. Suppose that p.v are probability measures supported on Σg. Let (T, dr, 6) denote a label tree, poth-length metric, and mapping from En to T generated by Algorithm 7 respectively. Then, the

---

Published in Transactions on Machine Learning Research (11/2025)
Wasserstein distonce in Equation can be written
W dya (1,
Σ eEE(T) 2
(dyu(((va))) ddp((()))))
where we let Øyfi denote the push-forward measure of μ by Φ.
Proof. Since Wa (oru, ΦFv) = EREF(T) (=u((((v)) - (rv(T(r))) holds by Theorem | we show that Wdnam (H, = Wa (ØEHe, 0./).
First, let x be a coupling of μ and v. Note that ø is injective and mcasurable by Lemma 4 the mapping @ & is a measurable from E to T2, and (6 Φ) a push-forward measure on T that is also a coupling of dspt and @rV. Since the mapping ø is distance-preseriing, we have
/ xx,
d (2. ())((zz dy) = | d7(a,))((} x ()aa)
J dr(a, db) duv).
inf =Ell(A.) J23
daam (r. y) (dx, dy) z inf (El((((
Therefore, it follows that Wdna (1, 2 (op,, 01²).
Next, we show that W Wdnao (1, S War (dy @.v). Since the map ó restricted to its image ((En) is bijective, its inverse map Φ11 ((EH) + Σн exists, and 6- is distance peeenceepreerving..
Let y denotes a coupling of Φzue and dyy, then
J dr b),(a) db) 2
/ /S da b)y(b), db), since x1 is distance-preseevinng,
0(En)
f duam (2, () o x dy).
((0-1 x )-)) is a measure on Ei, and is a coupling of je and u. Consequently, it leads to
(Ell(ggnbbo)) I da b)r(da, db) 2 inf (
inf This means Way (dept, )yv)= 2 Wditam (n, v) holds.
=Ell(u.)) 133 d (z. y) dy) d (Ji, v).
The positive definiteness proof of the categorical WWL kernel in the original WWL paper (Togninalii et al. 2019) already hints at a hicrarchical structure of the Wasserstein computation. The proof shows that, under a Hamming ground cost, the Wasserstein distance between WL embeddings can decompose across the depth of the WT. iterations, and the optimal coupling at the final layer induces optimal couplings at earlier layers. In this sense, hierarchical structure is implicitly present. Proposition [ makes this structure explicit by identifying the label tree. By treating the WL embeddings probability measures on the tree, we show that applying Theorem derives closed-form expression for the Wasserstein distance.
This result shows that the TWWL algorithm exhibits lower time complexity than the approach described in Togninalli et al. (2019). Given two labeled graphs G1 and G2 with nı and ny vertices, respectively, the time complexity of the Sinkhorn algorithm for Equation 3 is O(ninz). The time complexity of the TWWT. algorithm is determined by the number of edges in the label troe and the computation of P. The number of edges is O(ni + n2) even in the worst case, and can be computed in O(ni + n2)) time beforehand. Consequently, the overall time complexity of our algorithm is O(n, 722). As the number of vertices in the given graphs increases, our algorithm becomes significantly faster than the existing approach.
Equation has been shown to be positive definite for every À > 0 by Togninalli el al. (2019). The alternative expression based on the Tree Wasserstein distance offers an independent verification. From Proposition in
Le et al. (2019b] Proposition 2), it follows that dma. (n, v), expressed in Equation nogative definite. Furthermore, Theorem 2.2 in Berg al. (1984) proves that the graph kernel given in Equation is positive definite.
9

---

Published in Transactions on Machine Learning Research (11/2025)
Table 1: Summary of datasets. We denote by N the number of graphs in the dataset, and by ñ and avg( the average number of vertices and edges per graph, respectively.
N
n
a
Agraphs per class
node labels
MUTAG
188
17.93
19.79
63/125
PTC-MR
344
14.29
14.69
192/153
ENZYMES
600
32.63
62.14
100/ (00/100/10
100010000
PROTEINS
1113
39.06
72.82
663/ 663/450
DD
1178
284.32
715.66
691 691 /487
NCII
4110
29.87
32.30
2053 2057
COLLAB
5000
74.49
2457.78
2600/ 775 2600/775// /162/
REDDIT-BINARY
2000
429.62
497.75
1000 1000
REDDIT-MULTI-5E
4999
508.51
594.87
1000/10000 1000, 1000/999
767 /2592/ 1000 1094 1094/902//200
REDDUT-MULTI-12K
11929
391.40
456.89
513/99 (1//999//// 1243 1092/522
DBLP-v1
19456
10.48
19.65
9530/9926 9926
github-stargazers
12725
113.79
234.64
5917 5917/6808 6808
5 Experiments
In this section, we conduct two numerical experiments to validate the scalability and performance of our approach. The experimental code is publicly available at https: wwt./eoiii//tittiine..eea
We benchmark our algorithm against the Wasserstein Weisfeiler-Lehman kernel with the Sinkhorn algo-
rithm (Togninalli et al., 2019] WWL), the Weisfelles-Lchman subtree kernel (Shervashidze et al. 2011 WL),
the Weisfeiler-Lehman Optimal Assignment kernel (Kriege et al. 2016 WL-OA), traditional kernels such as the Shortest Path kernel (Borgwardt & Kriegel 2005 SP), and Graphlet sampling kernel [Pržulj 2007
GL), and recent methods such as the Multiscale Laplacian graph kernel (Kondor & Pan 2016 ML.G), the Weisfeiler-Lchmann Lower Bound distance (Chen et al. 2022. W and the Relaxed Weisfeiler-Lehmal kernel (Schulz et al., 2022] R- J- For WI., WT.-OA, SP, GL and M..G, we utilize the graph kernel imple- mentations provided by Siigiddis et al. (2020). All experiments are conducted on an Ubuntu 22.04 machine equipped with Intel Xcon Gold 6354 CPU and 256GB of RAM. For runtime comparisons against WWL, both our method and the WWL kernel are implemented entirely in Julia to ensure fairness.
We evaluate the proposed methods on graph classification task using real-world datasets summarized in Table [ For datasets without node labels, we assign dogree-based dummy labels. Across basclines, node labels are used as follows. WL, WL-OA and WWL use them as inputs to the WL algorithm. R-WL represents WL. labels as unfolding trees and assesses their similarity via tree edit metric. SP incorporates them when comparing two shortest paths by taking into account the agreement of node labels at the endpoints of corresponding edges along the paths. In WLLB, node labels instantiate the ground label space from which the hierarchy of probability measures is built. ML. uses node label agreement as the base kernel over vertex features. GL ignores node labels and measures similarity via counts of graphlct patterns. All datascts are downloaded from Morris et al. (2020). The details on experiments are described in Appendix B
5.1 Runtime Comparison
In the first experiment, we benchmark the computation time required for calculating the pairwise Wasserstein distances on real-world datasets. For each combination of datasets and methods, we conduct 10 independent trials and report the average runtime (in seconds) and the corresponding standard deviation. We denote linear programming solver by LP, implemented by Huangfu & Hall (2018), and note that our algorithm provides the same calculated values with the solver. Furthermore, since the computation time of the Sinkhorn
https://github.. www./ooommmmaeeacceccccaaaaa bonn/ieiilnnn
10

---

Published in Transactions on Machine Learning Research (11/2025)
Table 2: Runtime performance (in seconds) of the Wasserstein distance computation fixed at H "NA (not-available)" indicates timcout (over 24h).
METROD
MUTAG
PTC-MR
ENZYMES
PROTEINS
DD
NCI
LP
33.89 1.68
85.98 = 5.73
882.56 + 69.52
4597.12 2 157.77
NA
31775.82 +: 337.00
WWL (0.01)
3.13 1 0.04
4.54 1 0.01
37.01 1 0.02
147.26
0.52
939061 1. 28.49
2116.45 1 6.92
WWL (1.00)
0.01
5.33
0.16
21.89
0.23
1283 13 9.48
229.97
0.59
TWWL
0.03 + 0.00
0.08
0.00
0.67 + 0.12
2.38 +
0.19
26.93 + 0.40
24.33 + 0.56
COLLAB
REDDIT-B
REDDIT-M5
REDDIT-MI2
DBLP
gichub-stargazers
LP
NA
NA
NA
NA
NA
NA
WWL (0.01)
7721.67 L 37.48
NA
NA
NA
1798. 1. 5.92
NA
WWL (1.00)
1653.68 = 27.69
8157.94 = 169.58
NA
913.74 + 8.84
25 82818988 + 65.90
TWWL
44.18
333.33
5515.76
25.07
89 0.56
algorithm varies depending on the entropic regularization term 7/ we assess the time for the Sinkhorn algorithm with both 0.01 and 1.0. The parameter H for the WL algorithm fixed at for simplicity. For further details, additional runtime results for the proposed method with varying values of H are placed in Appendix B3. We note that the runtime in Table 2 includes only the time laken to compute the pairwise distance matrix, excluding the preprocessing time for LP, WWL, and TWWL. This is because Algorithm [ used in TWWL as preprocessing is a slight modification of the WL algorithm used for preprocessing in LP and WWL, and its running time is comparable to, or at most slightly slower than that of the WL algorithm. Further runtime decomposition is described in Appendix B.4
Table shows that TWWL significantly reduces runtime compared to either the Sinkhorn algorithm or linear programming solver. Notably, TWWL completes computations within practical time limits even in challenging scenarios, such dataset with numerous graphs (e-g., DBLP-v1), dataset with high average vertex counts per graph (e.g., REDDIT-MULTI-5K3) and a dataset with both features (e.g., REDDIT- MULTI-12K). For some datasets, such as NCI1, DD, and larger datasets, it was frequently observed that the Sinkhorn algorithm failed to converge within the maximum number of iterations for any value of A koy advantage of our algorithmic approach is its reliability to produce stable solutions.
5.2 Performance Comparison
In this experiment, we evaluate the performance of TWWL on a graph classification task using 10-fold cross-validation with a support vector machine classifier (Cortes & Vapnik 1995). All hyperparameters are selected via grid search on the training folds only: the SVM regularization parameter, the number of WL iterations HI, the kernel scale X, and the Sinkhorn entropic regularization term in WWL. Additional details the hyperparameter settings given in Appendix[B2. Since the TWWL algorithm is specifically designed to accurately and efficiently compute the Wasserstein distance, it is expected that our algorithm achieves comparable performance to the WWL kernel. Our aim is to verify that the precise Wasscrstein distance does not adversely affect performance when compared to the Sinkhorn algorithm.
Table shows that our algorithm achieves classification accuracy competitive with the WWL kernel. Notably, TWWL can scale to large datascts for which the Sinkhorn algorithm is computationally prohibited due the runtime and/or memory requirements. This result suggests that our proposed approach can serve as drop-in replacement for the Sinkhorn algorithm in the WWL kernel in the context. of categorical node labels.
6 Conclusion
In this paper, we proposed exact and efficient algorithm to compute the Wasserstein Weisheiler-Lehman graph kernel for datascts with categorical node labels, especially for large-scale application domains. We revealed that. labels generated by the Weisfeiler-Lehmaan algorithm inherently yield a tree structure, and that the proposed algorithm provides the same result as the original WWL graph kernel. The computational complexity of the proposod algorithm scales lincarly with the number of vertices in a graph, which is consid- erably more efficient than the quadratic computational cost required by the Sinkhorn algorithmic approach. Numerical experiments demonstrate that our algorithm achieves performance comparable to the Sinkhorn
11

---

Published in Transactions on Machine Learning Research (11/2025)
Table 3: Classification accuracies on datasets. "NA" and "OOM" indicate timeout (over 24h) and out-of-
memory (over 256GB), respoctively.
METHOD
MUTAG
PTC-MR
ENZYMES
PROTEINS
DD
NC11
SP
81.81 8.62
61:01
6.75
20.67 - 6,51
75.74 2.75
79.80
+ 2.37
73.26 =: 1.95
GL
77.02 1 9.70
55.82
4.15
29.83 1 5.24
68.92 3:45
72.49 1 4.32
39.61 1: 2.35
WL
10.51
15.65
1.51
WT-OA
85.56 + 6.92
02.24 = 5.86
60.67 + 5.62
76.21 2.58
79.46
+ 2.29
86.16 + 1.35
WWL
87.72
6.91
65.12
7.27
60.00 1 5.50
74.38 2.54
86.37
1.40
MLG
R-WL
$7.69 1 8.07
54.88
7.88
45,31 1: 5.65
T4.67 1 3.89
NA
78.73 1: 1.34
WLLB
88.27 = 8.29
53.19
8.82
37,
6.76
NA
NA
NA
TWWL.
+
50.83
74.94 2.98
77.17 3.51
+ 1.27
COLLAB
REDDIT-B
ILEDDIT-M5
REDDIT-MI2
DBLP-e1
gitimb stargazuss
SP
81.34 + 2.47
88. 70 + 1.93
52.33 + 2.62
44.10 + 1.14
OOM
68.06 + 1.17
NA
NA 30.65 1,33
WT.
78.74
2.51
75.05
2.07
50.79 + 1.48
92.97 + 0.52
65.19 + 1.03
WL-OA
NA
88.60
2.33
NA
NA
NA
NA
WWL
NA
NA
NA
OOM
MLG
NA
NA
NA
OOM
OOM
NA
RAWL
NA
NA
NA
NA
COM
NA
WLLB
NA
NA
NA
NA
NA
TWWL
0.95
0.47
algorithm, and its efficient computation enables the WWL kernel to be applied to large-scale datasetss that were previously infeasible, thereby establishing as an alternative for datasets with categorical node labels.
As our goal was a faithful and scalable realization of WWL with the Hamming ground cost, we fixed all edge lengths in the label tree to 1/2. This choice uniquely preserves exact equivalence between the tree path metric and the Hamming metric over WL label sequences. Allowing heterogeneous per-edge weights would define a different ground metric over label sequences and thus a different kernel family. Exploring dala-dependent tree metrics is orthogonal to our focus here and constitutes promising future work.
Another promising direction for future work to extend the proposed approach to datasets with continuous node attributes, c.g., using a clustering approach, as in the sig-of-visnalwwrrd approach computer vision. Our method is based on the properly that the space formed by the label set and the Hamminn distance can tree structure while preserving its topological properties. However, this property does not generally hold for continuous data, necessitating approximations. One possible approach is to develop graph kernel based on the tree-sliced Wasserstein distance (Le et al.) 2019b). While existing work (Perez et al. 2024) accelerates the WWL kernel by leveraging the sliced Wasserstein distance, a systematic comparison of these strategies, focusing on both computational efficiency and performance, would be valuable. In addition, there have been numerous studies on approximating Euclidean structures with trees, an investigation inlo optimal tree construction strategies may yield informative insights and enhance the effectiveness of our approach for continuous data.
be represented
Acknowledgements
We thank anonymous reviewers for insightful comments and suggestions. Part of this work is supported by JSPS KAKENHI 23K24909 and 25H01494. TL gratefully acknowledges the support of JSPS KAKENHI Grant number 23K11243, and Mitsui Knowledge Industry Co., Ltd. grant.
References
Jason Altschuler, Jonathan Kiles-Weed and Philippe Rigollet. Near-lincan time approximation algorithms for optimal transport via sinkhorn iteration. In Proceedings of the 31 Internalional Conference on Newral Information Processing Systems, pp. 1961-1971, December 2017.
Albert-Lásppn Barabási and Zoltán N. Oltvai. Network biology: understanding the cell's functional organi- zation. Nature Reviews Genetics, 522)1101-113, February 2004. doi: 10. 10.1038/nrg1273
12

---

Published in Transactions on Machine Learning Research (11/2025)
Albert-László Barabási and Márton Pósfai. Network Science. Cambridge University Press, 2016.
Christian Berg, Jens Peter Reus Christensen, and Paul Ressel. Harmonic analysis semigroups: Theory of positive definite and related functions. Springer, June 1984. doi: 10.10077978-1146112 1128-0
Nicolas Bonneel, Julien Rabin, Gabriel Peyré, and Hanspeter Pfister. Sliced and radon wasserstein barycenters of measures. Journal of mathematical imaging and vision, 51(1))22-45, January 2015. doi:
10.1007//11055--014-00666
Karsten Borgwardt, Elisabetta Ghisu, Felipe Llinares-Lópen Leslie O'Bray, and Bastian Rieck. Graph kernels: State-of-tho-art and future challenges. Foundations and Trends& in Machine Learning, 13(5-6): 531 712, December 2020. doi: 00.151/220000000
Karsten M. Borgwardt and Mlans-Peter Kriegel. Shortest-path kernels on graphs. In Proceedings of the 5th IEEE International Conference on Data Mining, pp. 74-81, 2005. doi: 10.1109/1CDM.2005.12
Karsten M. Borgwardt, Cheng Soon Ong, Stefan Schönauer, S. N. Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(suppl_ 11:1_1))411101 June 2005. doi: 10.1093/biai /ioinformaaiicc//ti0000.
Samantha Chen, Sunhyuk Lim, Facundo Memoli, Zhengchao Wan, and Yusu Wang. Weisfeiler-lehman meets Soomov-wasserstenn In Proceedings of the 39th International Conference Machine Learning, volume 162, pp. 3371-3416, July 2022.
Ching- Yao Chuang and Stefanie Jegelka. Tree mover's distance: Bridging graph metrics and stability of graph neural networks. In Proceedings of the 36th International Conference on Neural Information Processing Systems, December 2022.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press, 3 edition, July 2009.
Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine learning, 20(3):273 297, September 1995. doi: 10.1007 10.1007/bf0099900 /00099900099408...
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In Proceedings of the 27th International Conference on Neural Information Processing Systems, volume 2, pp. 2292 2300, December 2013.
Asim Kumar Debnath, Ross L. Lopez de Compadre, Gargi Debnath, Alan J. Shusterman, and Corwin Han- sch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correla- tion with molecular orbital energies and hydrophobicity. Journal of Medicinal Chemistry, 34(2):786-779, February 1991. doi: 111001/jm0000a000e
Paul D. Dobson and Andrew J. Doig. Distinguishing enzyme structures from non-enzymes without align- ments. Journal of Molecular Biology, 330(4))771-783, July 2003. doi: 10.1016/S0022 20.106//80022228008)0022223 (830000)
Kira Michaela Düsterwald, Samo Hromadka, and Makoto Yamada. Fast unsupervised ground metric learning with tree- wassersssnntnnn distance. In Proceedings of the 13th International Conference on Learning Repre- sentations, 2025.
Steven N. Evans and Frederick A. Matson. The phylogenctic Kantorovich-Rubiiee metric for cnviron- mental sequence samples. Journal of the Royal Statistical Society. Series B, Statistical methodology, (3):569-590) 592, June 2012. doi: 10.1111/j.1467-9663 2001000000...11.111111..
Aasa Feragen, Niklas Kasenburg, Jens Petersen, Marleen de Bruijne, and Karsten Borgwardt. Scalable kernels for graphs with continuous attributes. In Proceedings of the 27th International Conference on Neural Information Processing Systems, pp. 216 224, December 2013.
13

---

Published in Transactions on Machine Learning Research (11/2025)
Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélic Boisbunon, Stanislas Cham- bon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Téo Gautheron, Nathalie T. H. Gayraud, Hicham Janati, Alain Rakotomamoniv, levgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica J. Sutherland, Romain Tavenard, Alexander Tong, and Titouan Vayer. POT: Python optimal transport. Journal of Machine Leurning Research, 22(78):1 8, 2021.
Tony Hansen and Donald E. Eastlake 3rd. US secure hash algorithms (SHA and SHA-based HMAC and HKDF). RFC 6234, May 2011.
Christoph Helma, Ross D. King, Stefan Kramer, and Ashwin Srinivasan. The predictive toxicology challenge 2000-2001. Bioinformatics, 17(1):107-108, January 2001. doi: 10. 1000//ioiiffrrmatiss/1777.
Qi Huangfu and Julian Hall. Parallelizing the dual revised simplex method. Mathematical programming computation, 10(1):119-142, March 2018. doi: 10.1007/412552-017-0111
Piotr Indyk and Nitin Thaper. Fast image retrieval via embeddings. In International workshop on statistical and computational theories of vision, 2003.
Risi Kondor and Horace Pan. The multiscale laplacian graph kernel. volume 29, December 2016.
Lemin Kong, Jiajin Li, Jianheng Tang, and Anthony Man-Cho So. Outlier-robust gromov-wasserstein for graph data. In Proceedings of the 37th International Conference Neurol Information Processing Systems, pp. 24781-24803, December 2023.
Nils M. Kriege, Pierre-Louis Giscard, and Richard Wilson. On valid optimal assignment kernels and appli- cations to graph classification. In Proceedings of the 30th International Conference Neural Information Processing Systems, pp. (623-1631, December 2016.
Nils M. Kriege, Fredrik D. Johansson, and Christopher Morris. A survey on graph kernels. Applied network science, 5(1):1-42, December 2020. doi: 10.1007 (11007//41100 000000//41109-01111 109-019--195-3.
Tam Le, Viet Huynh, Nhat Ho, Dinh Phung, and Makoto Yamada. wasserrssn barycenter for large-scale multilevel clustering and scalable bayes, October 2019a.
Tam Le, Makoto Yamada, Kenji Fukumizu, and Marco Cuturi. Tree-sliced variants of wasserstein distances. Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 12304- 12315, December 2019b.
Tam Le, Truyen Nguyen, Dinh Phung, and Viet Anh Nguyen. Sobolev transport: A scalable metric for probability measures with graph metrics. In Proceedings of the 25th International Conference on Arlificial Intelligence and Statistics, volume 151, pp. 9844 1868,, March 2022.
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diam- eters. ACM transactions on knowledge discovery from data, 1(1):2, March 2007. doi: 10.1145/1217299. 1217301.
Mengyu Li, Jun Yu, Tao Li, and Cheng Meng. Importance sparsification for sinkhorn algorithm. Journal of Machine Learning Research, 24(247):1-44, 2023.
Ya-Wei Eileen Lin, Ronald R. Coifman, Gal Mishne, and Ronen Talmon. Tree- wasserstee distance for high dimensional data with latent feature hierarchy. In Proceedings of the 13th International Conference Learning Representations, 2025.
Catherine Lozupone and Rob Knight. UniFrac: a new phylogenetic method for comparing micro- bial communties. Applied and Environmental Microbiology, 71(12):8228 8235, December 2005. doi:
10.1128/AEM.71.22.2222 110.:7771....222--22222200000
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. TUDataset: A collection of benchmark datasets for learning with graphs. In ICML Workshop on Graph Representation Learning and Beyond, July 2020.
14

---

Published in Transactions on Machine Learning Research (11/2025)
Quentin Mérigot. A multiscale approach to optimal transport. Computer graphics forum: journal of the European Associalion for Compuler Graphics, (0(5):1583-159) August 2011. doi: 10.1111/j.146--8653 2011.02032.x.
Vu Nguyen, Tam Le, Makoto Yamada, and Michael A. Osborne. Optimal transport kernels for sequential and parallel neural architecture search. Proceedings of the 38th International Conference on Machine Learning, volume 139, pp. 8084-8008 8095, July 2021.
Giannis Nikolentzos, Giannis Siglidis, and Michalis Vazirgiannis. Graph kernels: A survey. The journal of artificial intelligence research, 72:943 1027, November 2021. doi: 10.1613//jirr.11322
James B. Orlin. A polynomial time primal network simplex algorithm for minimum cost flows. Mathematical programming, 78(2):109 112,, August 1997. doi: 10.1007/bl026) 4365.
Shirui Pan, Xingquan Zhu, Chengqi Zhang, and Philip S. Yu. Graph stream classification using labeled and unlabeled graphs. In Proceedings of the 29th IEEE International Conference on Data Engineering, pp. 398-409 April 2013. doi: http://icc.2.1....66
Raphaäl Carpintero Perez, Sébastien Da Veiga, Josselin Garnier, and Brian Staber. Gaussian process re- gression with sliced wasserstein reisfeller-lhhmar graph kernels. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics, pp. 1297-1305, May 2024.
Hermina Petric Maretic, Mireille El Gheche, Giovanni Chierchia, and Pascal Frossard. GOT: An optimal transport framework for graph comparison. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 13899 13899-13910, December 2019.
Gabriel Peyré and Marco Cuturi. Computational optimal transport, 2020.
Nataša Pržulj- Biological network comparison using graphlet degree distribution. Bioinformatics, 23(2): e177 e183, January 2007. doi: 10.1093/ htta////ooonoomtics///aiia
Benedek Rozemberezki, Oliver Kiss, and Rik Sarkar. Karate club: An API oriented open-source python framework for unsupervised learning on graphs. In Proceedings of the 29th ACM International Conference on Information and Knowledge Management, pp.
October 2020.
Meyer Scetbon, Marco Cuturi, and Gabriel Peyré. Low-rank sinkhorn factorization. In Proceedings of the 38th International Conference on Machine Learning, volume 139, pp. 9344-9354, July 2021.
Till Hendrik Schulz, Tamás Horváth, Pascal Welke, and Stefan Wrobel. A generalized weisfeiler-lehman graph kernel. Machine learning, 111(():2601 2629, July 2022. doi: 10.1007 (1109940022006113
Nino Shervashidze, S. V. N. Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Efficient graphlet kernels for large graph comparison. In Proceedings of the 12th International Conference on Artificial Intelligence and Statistics, volume 5, pp. 488-495, April 2009.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt. Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(77):2539 2561, 2011. doi:
10.5555 /e////199304822275 2078187.
Giannis Siglidis, Giannis Nikolentzos, Stratis Limnios, Christos Giatsidis, Konstantinos Skianis, and Michalis Vazirgiannis. GraKeL: A graph kernel library in python. Journal of Machine Learning Research, 21 (54): 1 1-5, 2020.
Richard Sinkhorn. A relationship between arbitrary positive matrices and doubly stochastic matrices. The Annals of Mathematicul Statistics, (77: 879, June 1964.
Yuki Takezawa, Ryoma Sato, and Makoto Yamada. Supervised tres-sssser distance. Proceedings of the 38th International Conference Machine Learning, pp. 10086-10095, PMT.R, July 2021.
15

---

Published in Transactions on Machine Learning Research (11/2025)
Yuki Takezawa, Ryoma Sato, Zornitsa Kozareva, Sujith Ravi, and Makoto Yamada. Fixed support tree-sliced wasserstein barycenter. In Proceedings of the 25th International Conference Artificial Intelligence and Statistics, pp. 1120 1137, March 2022.
Xun Tang, Michael Shavlovsky, Holakou Rahmanian, Elisa Tardini, Kiran Koshy Thekumparampil, Tesi Xiao, and Lexing Ying. Accelerating sinkhorn algorithm with sparse newton iterations. In Proceedings of the 12th International Conference on Learning Represenlations, 2024.
Vayer Titouan, Nicolas Courty, Romain Tavenard, Chapel Lactitia, and Rémi Flamary. Optimal transport for structured data with application graphs. In Proceedings of the 36th International Conference Machine Learning, pp. 6275-6284. PMLR, May 2019.
Matteo Togninalli, Elisabetta Ghisu, Felipe Hiinares-López, Bastian Rieck, and Karsten Borgwardt. Wasser- stein woisfciler-chmman graph kernels. In Proceedings of the 33rd International Conference on Neural Informalion Processing Systems, pp. 6439 6449, December 2019.
Cedric Villani. Optimal Transport: Old and New. Springer, December 2009. doi: 10.1007/978-35540-700008
Cédric Vincent-Cuaz, Rémi Flamary, Marco Corneli, Titouan Vayer, and Nicolas Courty. Semi-relaxed gromov-wassersteii divergence and applications graphs. In Proceedings of the 10th International Con- ference on Learning Representations, 2022.
S. V. N. Vishwanathan, Nicol N. Schraudolph, Risi Kondor, and Karsten M. Borgwardt. Graph kernels. Journal of Machine Learning Research, 11 11440):1201-1222, 2010.
Nikil Wale, lan A. Watson, and George Karypis. Comparison descriptor spaces for chemical compound retrieval and classification. Knowledge and information systems, 14(3):347 375, March 2008. doi: 10.
1007/s10115-007--000335
Boris Weisfeiler and Andrei Leman. A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno- Teabiichsacn Informatsia, 2(9):12-11 16, 1968.
Yujia Xie, Xiangfeng Wang, Ruijia Wang, and Hongyuan Zha. A fast proximal point method for computing exact wasserstein distance. In Proceedings of the 35th Conference on Uncertoinly in Artificcaal Intelligence, pp. 433 453. PMLR, July 2019.
Hongteng Xu, Dixin Luo, and Lawrence Carin. Scalable grosov-wasserstein learning for graph partitioning and matching. In Proceedings of the 33rd International Conference Neural Information Processing Systems, pp. 3052 3062, December 2019.
Makoto Yamada, Yuki Takezawa, Ryoma Sato, Han Bao, Zornitsa Kozareva, and Sujith Ravi Approximating 1-wasserstein distance with trees. Transactions Machine Learning Research, September 2022.
Pinar Yanardag and S. V. N. Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1365-1374. Association for Com- puting Machinery, 2015. doi: 10.1145/2783258.278888 27834477.
16

---

Alternatively, Julia's built-in in Base. hash function is used in Published in Transactions on Machine Learning Research (11/2025)
A Hash Functions
In many areas of computer science, hash function is used to map arbitrary length data (e.g,, text data, image, or binary data) to a fixed length. This output, commonly called a hash value, serves as a compact representation of the original data. In general, hash functions are used for two main purposes. One is for data uniqueness verification and tamper detection in cryptographic security, and the other is as table keys for processing large volumes of data or for detecting differences between two data in non-cryptograhhic domains. SHA-2 (Hansen & 3rd 2011) is one of the well-known standards designed by the National Security Agency and standardized by the National Institute of Standards and Technology hash function for cryptographic security.
The properties required of hash function depend on its intended application, but to be considered good hash function, it must satisfy at least the following two properties:
Deterministic: for the same imput, the hash function always produces the same hash valuc.
Collision resistance: it should be computationally infeasible to find two different inputs that yield the same hash value.
The hash function in Equation is assumed to satisfy these two properties. A well-known SHA-256 imple- mentation can be used to compute Equation [ our implementation.
B Details on Experiments
B.1 Dataset Descriptions
Every graph dataset contains the adjacency information and graph-level label. Some datasets additionally provide optional information such as node labels/ / /attributes or edge tabels/attribut In our experiments, we exploited only the modeelabell information when it was available. For datasets without node labels (COLLAB, REDDIT-BINARY REDDIT-MULTI-5K, REDDIT-MULTI-22 github-stargazers), we assigned pseudo node labels based on its degree.
Datascts used in our experiments can be categorized into two types: chemoinformaties and bioinformatics datasets, and social nelwork datasels. The main characteristics of each dalaset are summarized as follows.
MUTAG: This is a chemoinformatics dataset consisting of 188 aromatic and heteroaromatic compounds (Deb- nath et al., 1991). Each graph models a compound, with nodes corresponding to atoms and edges to the chemical bonds between them. The lask is predict the mutagenic effect of the compound, calegorized inlo two classes.
PTC-MR: This datasct originates from the Predictive Toxicology Challenge (Helma et al., 2001 PTC), competition to promote the development of machine learning models for predicting chemical toxicity. The PTC-MR dataset contains chemical compounds tested for carcinogenicity in male rats (MR). Each compound is modeled as a graph, where nodes denote atoms and edges denote the chemical bonds connecting them. The task to predict compound carcinogenicity, which is a binary classification problem.
ENZYMES: This is bioinformatics datasct constructed from the BRENDA (Braunschweig Enzymes Database), comprehensive enzymes and metabolic information repository (Borgwardt et al. 2005). Each graph represents enzyme, where nodes are its secondary structure elements (SSEs), and edges created between nodes if they are neighbors along the amino acid sequence or are spatially close. The task is to classify enzymes into six classes based on their catalytic activity.
This dataset is used as a benchmark for graph classification task predicting whether a protein is an enzyme or not (Borgwardt al. (005). A protein represented by a graph as follows. Nodes in the graph correspond to SSEs, and they are connected by an edge if they are neighbors along the amino acid sequence spatially close.
PROTEINS:
17

---

Published in Transactions on Machine Learning Research (11/2025)
DD: This datasct consists of 1178 protein structures where the task is to classify them into enzymes and non-enzymes (Dobson & Doig 2003 Each graph represents protein, in which the nodes are amino acids and two nodes are connected by an edge if they are less than 6 Angstroms apart.
This dataset consists of chemical compounds screened for their effectiveness against non-small cell lung cancer, with the task being to classify each compound as active or not (Wale et al. 2008 Nodes each graph represent atoms, and edges represent chemical bonds between them.
NCI1:
This is scientific collaboration dataset of researchers (Leskovec et al. 2007 Each graph represents an ego-network of researcher. In the graph, nodes represent rescarchers and edges indicate co-authorship. This dataset is widely used as a benchmark for graph classification tasks of predicting the researcher's academic field among three classes: High Energy Physics, Condensed Matter Physics, and Astro Physics.
COLLAB:
REDDIT- REDDIT-BINARYY online discussion plat.orm where users participate in discussions within lopic-specific threads called subred- dits Yanardag & Vishwanathan 2015). Each graph represents the user interaction structure of single discussion thread. In cach graph, nodes represent users, and an edge connects two nodes if one user replied to another's comment. The collection includes three variants with different classification challenges:
These are social network datasct created from Reddit, an
REDDIT-BINARY is binary classification task to distinguish threads from QA-style subreddits versus discussion-style subreddits.
REDDIT-MULII-SK is a 5-class classification task among five subreddits: worldnews, videos, Ad- viceAnimals, aww and mildlyinteresting.
REDDIT-MUL.TI-1X expands the task to a larger set of subreddits: AskRed AdviceAnimals. atheism, aww, LAmA, mildlyinteresting, Showerthoughts, videos, todayilearned, worldnews, and ThollXChromosomes.
DBLP-v1: This is a scientific collaboration dataset derived from DBLP, a comprehensive bibliography database computer science publications (Pan et al., 2013).. Each graph represents a paper in DBLP, where nodes denote either a paper or keyword, and edges represent relationship between two papers, link between a paper and its corresponding keyword, or link between keywords from the same paper. The task is to classily each paper into one of two classes: database and data mining field or computer vision and pattern recognition field.
of three types of relationships: citation
github-staryazers: This is a social network dataset derived from GitHub, the software development plat- form (Rozemberzzki al., 2020). Tt. consists of social networks of developers who starred popular machine learning and web development repositories. Each graph represents the community of developers who starred repository, where nodes represent users, and edges denote follower relationships. The goal is to predict whether a social network belongs to machine learning web development repository.
B.2 Hyperparameter Settings
The following hyperparameter settings were used in the experiments of Section 5 For regularization parameter C in the support vector classifier, search over the range {10-3 10 of iterations H for the WI. algorithm is chosen from .1.....7). The paramcter À of the WWL and TWWL is selected from (10-4, 10-3 ..... 10²}. For the Sinkhorn algorithm, we select the entropic regularization parameter from (0.01, 0.05, 0.1, 0.2, 0.5, 1, 10} and fix the maximum number of iterations to 1000, which is the default sctting in the commonly used implementation (Flamary et al. (021). In the second experiment, hyperparameter optimization is performed on the training data via grid search over the predetermined range of values.
1033. The number
18

---

Published in Transactions on Machine Learning Research (11/2025)
Table 4: TWWL runtime performance of the Wasserstein distance computation the parameter H is
increased.
DATASET
H =1
H 2
H
H
H ==0 =
H
MUTAG
0.077 0.004
0.010
0.001
0.015
0.001
0.022
0.001
0,032 1 0.001
0.042 1 0.001
0.052
0.001
PTC-MR
0.036 0.066
0.010 0.057
0.138
0.00
0,056
0.011
0.076 = 0.001
0,096 + 0.001
0.181
0.213
ENZYMES
0.06 0.07
0.20
0.00
0.36
0.09
0.51
0.09
1.04
0.15
PROTEINS
0.24 0.09
0.64
+ 0.10
1.19
0.16
1.83
+ 0.14
2.37
+ 0.16
2.98
+ 0.23
3.47
0.18
DD
6:20 + 0.31
11.61
+ 0.47
16.67
0.433
21.74
+ 0.17
26.72
+ 0.18
31.83
+ 0.28
36.96
0.36
NCII
25.22
30:20
COLLAB
18.05 0.53
25.97 0.85
31.77
0.63
13.69
0.56
52.21
+ 0.68
60.90
0.71
69.66
0.58
REDDIT-B
5.50 0.14
13.55
0.14
22.36
0.32
30.62
+ 0.57
36.74
+ 0.45
47.08
+ 0.64
55.27
+ 0.49
REDDIT-MG
66.38 =
138.67
3.30
207.05
2.08
388.21
+ 551.52
686.86
= 2.78
817.82
1.12
REDDIT-MI2
326.64
1.28
835.47
1.06
1476.17
3.76
2155.87
6.07
5631.26
16.50
7246.46
32.74
8686.33
30.20
DBLP
139.52
0.85
187.52
0.69
236.0K
0.93
285.69
1 1.27
333.33
1 0.75
382.69
1 1.34
431.27
0.85
gidhubstarggeers
208.31 0.19
398.80
0.54
598.15
0.52
79132
1.12
987.71
+ 1.21
118101
= 1.37
1377.2 23
3.00
B.3
Further results on runtime comparison
To evaluate how the computational cost of our algorithm scales with the parameter H, we supplement the runtime study in Section 5.1 with additional experiments. Whereas the experiment in Section 5.1 fixed = Table 4 reports the runtime results of the TWWL algorithm for range of H values. In the TWWL algorithm, the extra cost caused by increasing H is proportional to the number of newly generated labels, whose maximum is bounded by the total number of vertices n in dataset. Consequently, the overall complexity grows approximately linearly in H, trend clearly confirmed by Table
B.4 Additional results on Runtime comparison
This appendix augments the runtime comparison in Section 5.1 by reporting not only preprocessing for WWL and TWWL but also, for reference, the end-to-end runtimes of existing methods. For categorical node labels, WWL uses the WL algorithm for preprocessing and then computes the Wasserstein distance in Equation In contrast, the TWWL algorithm first constructs a label tree according to Algorithm D preprocessing, and subsequently evaluates the Tree Wasserstein distance in Equation 5 based on that tree. Table 2 compares the rumning times of Equation 3 for WWL and Equation for TWWL, and does not include preprocessing times. In this appendix, we summarize the end-to-end runtimes for computing the Wasserstein distance for WWL and TWWL, and we also report, for reference, the time required to construct the Gram matrix for existing methods. We note that WWT. and TWWL are implemented in Julia. For the other methods, we use the authors' publicly available Python implementations on GitHub, so absolute runtimes are not strictly comparable and should be interpreted only as indicative.
In Table 5 we report the end-to-end time required to construct the Gram matrix. Algorithm makes only minor modifications to the WL algorithm and adds the steps required to construct the tree structure. As shown in Table 5 the preprocessing time of TWWL is al most twice that of WWL across dalasets.
We note that the entropic regularization parameter in WWL does not affect WL preprocessing, and the preprocessing required for the linear programming approach is identical to that of WWL. We therefore omitted these cases from Table 5
19

---

Published in Transactions on Machine Learning Research (11/2025)
Table 5: Runtime dccomposition of the WWL and TWWL algorithms fixed at H and end-to-end runtimes of comparison methods in seconds. "NA" and "OOM" indicate limeout (over 24h) and out-of- memory (over 256GB), respectively. Entries for WWL and TWWL are reported as a pair: the mean preprocessing time (left) and the mean main computation (right).
METHOD
MUTAG
PTC-MR
ENZYMES
PROTEINS
DD
NC11
WWL (1.00)
0.10/
0.27
0.02
0.47
0.12 /
5.33
0.24/
24.89
2.46
1283.43
0.75 /
229.97
TWWL
0.02/
0.03
0.03
0.08
0.16/ /
0.67
0.40/
2.38
4.42
26.93
1.15/
24.33
SP
0.15
0.24
1.69
8.32
715.17
11.71
WL
0.08
0.52
7.23
3.37
WL-OA
0.04
0.34
10.61
4.20
0.34
0.45
7.35
12.76
236.91
12.39
MLG
28.64
45.73
197.99
758.41
NA
1486.6 60
R-WL
6.69
14.39
893.46
3062.59 59
NA
161.08
WLLB
867.23
1599.38
19169.05
NA
NA
NA
COLLAB
REDDIT-B
REDDIT-MS
REDDIT-MI2
DBLP-v1
gichub-stargazers
WWL (1.00)
7.38
1653.68
6.30
8457.94
20.55 NA
45.90 /NA
1.44/
945.74
12.11/ / 25 820.90
TWWL
12.32
44.18
10.21
38.92
32.57
333.53
70.64
5535.76
2.71
328.89
20.59
952.02
SP
1019.29
4175.16
8598.40 40
14997-43
OOM
2464.72
WL
12.89
88.17
18.89
42.66
WL-OA
11.83
NA
GL.
NA
NA
MLG
NA
NA
NA
NA
NA
NA
R-WL
NA
NA
NA
NA
NA
NA
WLLB
NA
NA
NA
NA
NA
NA
20


Reviews:
[{"review_id": "0JQiAvM2kP", "reviewer": "Reviewer_M96X", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "**Summary**: Authors revisit the (categorical) Wasserstein Weisfeiler-Lehman (WWL) kernel between graphs with discrete node features by exposing a tree structure associated to the label set created by the WL procedure called the Label Tree. This structure allows authors to show the equivalence between WWL and the tree Wasserstein distance which admits closed form solutions, called TWWL, that can be computed with linear complexity in the numbers of nodes O(n1 + n2) instead of a cubic complexity for the generic Wasserstein distance. Then they show across a large range of graph datasets that their approach runs in about 3 orders of magnitude faster than a LP solver for the exact Wasserstein and 1 to 2 orders of magnitude for entropically regularized variants. Moreover they show that it achieves  competitive performances with 5 other graph kernels.\n\n**Strengths**:\n   - Overall the paper is well written and illustrated.\n   - Proofs were carefully checked and I could not find any mistake.\n   - Gains in terms of computation times compared to the WWL are significant.\n\n**Weaknesses**:\n   - **W1** Authors’ contributions focus on improving the speed of the categorical WWL kernel which has already been outperformed by many other kernels in the recent years such as [A, B, C, D, E, F]. Moreover it is not clear whether TWWL really provides a better trade-off in terms of runtime/performance than these competitors.\n   - **W2** The novelty of the method is arguable : The proof of Theorem 1 from the original WWL paper on its positive definiteness already exhibits a tree structure via the OT solution for this problem. Essentially, they show that an OT solution between the WL embeddings is given by an OT solution between embeddings computed at the last iteration. When endowed with a binary cost as done within the Hamming distance, this Wasserstein distance admits a closed form solution given by the L1 distance between masses supported by the finale label set $\\Sigma_H$, see Remark 2.25 in Peyré’s book. Therefore it seems that the large part of the theoretical contributions made by authors is a re-framing of a corollary of Theorem 1 of the WWL paper, even if it is nicely done. However, I admit that authors of WWL did not explicit this result, therefore it remains interesting to state it until the end as the current paper is doing.\n   - **W3** The method does not support continuous features which are often encountered in real-life applications.\n   - **W4** The presentation of Algorithm 1 could be improved with an explanation of the key steps for better readability. Moreover the analysis of the algorithm complexity is not so clear.\n   - **W5** Certain small points could be completed or clarified:\n       - a) (Intro, page 2) Quantization is also an alternative to approximate the Wasserstein distance with faster computation see e.g [G], note that [E] investigates such alternatives as well as other relaxations to the WWL kernel. Moreover there are also proximal point algorithms to estimate the exact Wasserstein distance which has similar theoretical complexity than Sinkhorn [H]. Finally, it could be beneficial to complete the analysis of the theoretical complexity associated to already mentioned methods to better set the context of the current contribution.\n      - b) Equation 2: why the scaling by H as defined in the WWL paper is missing ?\n     - c) Could you clarify why a weight ½ is set and not other variants were explored ?\n     - d) Proposition 1: It seems to me that you can directly state that $(\\Sigma_H, d_{ham})$ is a metric space, why do you formalize that as an assumption ?\n     - e)Table 1: Could you explicit notations used in the headers of the table e.g $N$, $\\overline{n}$ etc which are not defined nor really consistent.\n     - f) Section 5.1: what is the device used for the experiments ? \n     - g) Table 3: performances for WWL 0.01 and 1 should be reported.\n     - h) The work for Perez & al, 2024 is mentioned several times as a direct competitor and not benchmarked. It should be added to both Table 2 and 3.\n    - i) Could you clarify why common solvers for the Wasserstein distance such as the POT library one was not used in this experiment ? I wonder if there are algorithmic details for network flow solvers which make them better than the one used in the benchmark.\n \n[A] Titouan, V., Courty, N., Tavenard, R., & Flamary, R. (2019, May). Optimal transport for structured data with application on graphs. In International Conference on Machine Learning (pp. 6275-6284). PMLR.\n\n[B] Xu, B. C., Ting, K. M., & Jiang, Y. (2021, May). Isolation graph kernel. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 35, No. 12, pp. 10487-10495).\n\n[C] Chuang, C. Y., & Jegelka, S. (2022). Tree mover's distance: Bridging graph metrics and stability of graph neural networks. Advances in Neural Information Processing Systems, 35, 2944-2957.\n\n\n[D] Weisfeiler-lehman meets gromov-Wasserstein. In International Conference on Machine Learning (pp. 3371-3416). PMLR.\n\n[E] Schulz, T. H., Horváth, T., Welke, P., & Wrobel, S. (2022). A generalized weisfeiler-lehman graph kernel. Machine Learning, 111(7), 2601-2629.\n\n[F] Brugère, T., Wan, Z., & Wang, Y. (2024, March). Distances for Markov chains, and their differentiation. In International conference on algorithmic learning theory (pp. 282-336). PMLR.\n\n[G] Chowdhury, S., Miller, D., & Needham, T. (2021, September). Quantized gromov-wasserstein. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases (pp. 811-827). Cham: Springer International Publishing.\n\n[H] Xie, Y., Wang, X., Wang, R., & Zha, H. (2020, August). A fast proximal point method for computing exact wasserstein distance. In Uncertainty in artificial intelligence (pp. 433-453). PMLR.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Yes on the theoretical side, I checked all the proofs and they seem correct. Authors’ analysis is comprehensive on that matter. Then they also show that their approach indeed improves the computational efficiency of the WWL kernel as claimed in the contributions.", "audience_yn": "Yes", "audience_explanation": "The contributions seem relevant for the graph kernel community as the paper introduces an algorithm which seems competitive and able to process very large-scale graphs. However, it could be beneficial the expand the benchmark by including other methods which could operate on such graphs to see if the paper really presents an empirical interest.", "requested_changes": "I suggest to authors to address the weaknesses mentioned above. In particular W4 and W5 should be rather simple to address in order to improve the clarity and comprehensiveness of the paper.\nContributions mentioned in W1 should also be acknowledged in some ways to provide a better review of the literature in the paper and potentially clearly state that some graph kernels were already introduced that achieve better performance than WWL. Clearly many of them have higher computational complexity than TWWL but not all of them so these should be clearly discussed. \nFinally, W2 seems to me as a major concern on the necessity of the theoretical contributions to support their methodological contributions.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "iDgTfnWYeW", "reviewer": "Reviewer_yDmk", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes the Tree Wasserstein Weisfeiler-Lehman (TWWL) graph kernel, an exact and efficient method for computing the Wasserstein Weisfeiler-Lehman (WWL) kernel for graphs with categorical node labels. The key idea is that the iterative label refinement in the Weisfeiler-Lehman (WL) algorithm naturally produces a hierarchical tree structure over labels, where the path length on this label tree exactly preserves the Hamming distance between label sequences. By leveraging the closed-form formula of the Tree Wasserstein Distance (TWD) on this tree, TWWL reduces the computational complexity of WWL from at least quadratic in the number of nodes to linear, while producing the same kernel values without approximation. Experiments on various real-world graph classification datasets show that TWWL matches WWL’s accuracy but is orders of magnitude faster, enabling the application of Wasserstein-based kernels to large-scale categorical graph datasets that were previously computationally infeasible.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The submission backs its core claims with (i) clear theory—lemmas showing the WL labels form a tree and that the map from WL labels to the label tree is distance-preserving, which underpins the exact reduction to Tree Wasserstein distance and its closed form (Theorem 1)—and (ii) experiments showing large runtime wins with comparable accuracy to WWL. Theoretical pieces are explicit (Lemma 3, Lemma 4, Proposition 1) and connect the equivalence of the original Wasserstein on Hamming labels to TWD, then argue linear time in total nodes across the two graphs, O(n₁+n₂). Empirically, they describe setup (10 trials for runtimes; 10-fold CV with SVM for accuracy; common baselines) and report consistent order-of-magnitude speedups (e.g., NCI1: 24.33 s vs 229.97–2116.45 s) while matching WWL-style accuracy where WWL runs, and scaling where WWL times out or hits memory limits. Caveats: runtime fairness is partly influenced by fixing H=5 for that study, and while they note additional H sweeps in the appendix, more ablations/significance tests and comparisons to other accelerations (e.g., sliced WWL) would strengthen the evidence; still, for the paper’s stated scope (categorical labels), the evidence is accurate, convincing, and clearly presented.", "audience_yn": "Yes", "audience_explanation": "The paper proposes an efficient method for learning Wasserstein Weisfeiler-Lehman with linear time with regard to the number of nodes. It reduces the time complexity from quadratic time to linear time. I think some people will be interested in it.", "requested_changes": "1. The concept of tree structures is widely used in many graph learning domains, like [1,2]. What are the differences and correlations between the proposed method and the existing works? \n\n   [1] GFT: Graph Foundation Model with Transferable Tree Vocabulary, NeurIPS 24\n\n   [2] Towards Graph Foundation Models: Learning Generalities Across Graphs via Task-trees, ICML 25\n\n2. It's good to report the time consumption of the proposed method. But I recommend the authors to compare the empirical time consumption between the proposed methods and the existing works.", "broader_impact_concerns": "No ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "SrvT4ebTxU", "reviewer": "Reviewer_g9jw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this submission, the authors proposed a tree-structured Wasserstein Weisfeiler-Lehman (TWWL) graph kernel for transductive graph classification. In particular, instead of computing the Wasserstein distance between graphs based on their node-level Hamming distance, the proposed method first extracts a WL-label tree from graphs and then computes the Wasserstein distance equivalently based on the push-forward results derived from the label tree. As a result, the computational complexity is reduced from O(N^2) to O(N) for the graphs with N nodes.\n\nIn theory, the authors demonstrate the equivalence between the Wasserstein distance based on the underlying Hamming distance and the proposed TWWL distance. \n\nExperiments show that the proposed TWWL graph kernel method achieves competitive graph classification accuracy compared to existing graph kernel methods. Moreover, it reduces the runtime significantly, showing promising computational efficiency.", "claims_and_evidence_yn": "Yes", "claims_explanation": "1. Tree-structured Wasserstein distance (TWD) has been proposed for a long time and has been widely used as an efficient alternative to the classic Wasserstein distance (WD). The authors proposed a new variant of TWD in the scenario of WL label propagation and demonstrated the equivalence between the proposed TWWL distance and a special WD defined on the Hamming distance of graph nodes. \n\n2. Experimental results show that the proposed method achieves comparable performance with significant improvements in efficiency, verifying a) the theoretical equivalence between the proposed TWWL graph kernel and the WWL one, and b) the superiority of the TWWL graph kernel in computational efficiency.", "audience_yn": "Yes", "audience_explanation": "1. Graph learning is an important topic in the machine learning community. Among existing graph learning methods, the graph kernel method corresponds to an interesting and flexible transductive learning paradigm, which is different from the inductive learning paradigm corresponding to learning parametric graph neural networks. Currently, whether the graph kernel method can overcome its natural limitation in computational efficiency is the key problem in this direction. \n\n2. Tree-structured Wasserstein distances have been widely used in machine learning tasks. The proposed method provides a new variant of TWD and demonstrates its equivalence to a special Wasserstein distance, which may attract researchers studying optimal transport-driven machine learning techniques.", "requested_changes": "1. The differences between the proposed TWWL distance and the existing TWD in Theorem 1 are not explained clearly. I suggest the authors add a new subsection comparing the TWWL distance and the existing TWD methods systematically. \n\n2. In addition, some notations are used without clear definitions, e.g., the $\\Gamma$, $w_e$, and $E(\\mathcal{T})$ in Theorem 1. In fact, the introduction of TWD is important for understanding the proposed work, especially for readers without sufficient background. Please rewrite this part in detail.\n\n3. In Table 2, I am not sure whether the runtime includes the time of constructing the label tree or not. If the answer is yes, the authors can provide a more detailed runtime analysis, e.g., showing the runtime of different steps of the proposed method and visualizing the runtime as the graph size increases.\n\n4. At the end of section 4, the sentence \"The alternative expression based on the Tree Wasserstein distance offers an independent verification through Proposition 2 in Le et al. (2019b)\" is too brief. More detailed explanations are necessary.\n\n5. In the experiments, some graphs have node labels. How do the proposed method and baselines leverage the node labels?\n\n6. In the experiments, the baselines are not strong enough. Even if merely considering the graph kernel-based methods, SP and GL are not state-of-the-art, to my knowledge. Some representative and strong baselines, such as the multi-scale Laplacian graph kernel [a] and the fused Gromov-Wasserstein graph kernel [b] should be considered as baselines.\n\n[a] Kondor, Risi, and Horace Pan. \"The multiscale laplacian graph kernel.\" Advances in neural information processing systems 29 (2016).\n\n[b] Titouan, Vayer, et al. \"Optimal transport for structured data with application on graphs.\" International Conference on Machine Learning. PMLR, 2019.\n\n7. In Table 1, \"#Classes\" should be \"#Graphs per class\".", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)