IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 37, NO.

11, NOVEMBER 2025 6367

Distributional Shortest-Path Graph Kernels

Wei Ye , Member, IEEE, Wengang Guo, Shuhao Tang , Hao Tian , Xin Sun , Senior Member, IEEE,
Xiaofeng Cao , Member, IEEE, and Heng Tao Shen , Fellow, IEEE

Abstract—Traditional shortest-path graph kernels generate for protein-protein interaction networks [3]. Consequently, mining
each graph a histogram-like feature map, whose elements represent and analyzing graph-structured data have become a significant
the number of occurrences of non-isomorphic shortest paths in research focus. A prominent problem in graph machine learning
this graph. The histogram-like feature map does not contain the
distributions of the shortest paths within and across graphs, causing and data mining is graph classification. The conventional ap-
inaccurate graph similarities. To this end, we propose a novel proach to this problem involves comparing graph similarities,
graph kernel called the Distributional Shortest-Path (DSP) graph which can be realized by graph kernels. Mainstream graph
kernel to embrace both types of distribution information. Since kernels are built upon the R-convolution framework [4]. They
the distribution of substructures (e.g., the shortest paths) follows a decompose graphs into substructures (e.g., walks [5], [6] or
power law like that of words in natural language, we utilize neural
language models to learn each node’s distributional shortest-path paths [7], [8], [9], [10], subgraphs [11], [12], [13], subtree
feature map, encompassing the distributions and dependencies of patterns [14], [15], [16], [17], [18]) and compare non-isomorphic
the shortest paths in each graph. Moreover, we design the Partition substructures.
Kernel (PK) to capture the dataset-wide distribution information of Unfortunately, existing R-convolution graph kernels fail to
the shortest paths. PK projects similar (i.e., belonging to the same
capture two types of distribution information in graphs, leading
partition) distributional shortest-path node feature maps to the
same point in the Reproducing Kernel Hilbert Space. Finally, Ker- to inaccurate graph similarity. First, they independently count
nel Mean Embedding (KME) is applied to compute graph feature the frequencies of non-isomorphic substructures for graph/node
maps and efficiently construct the DSP graph kernel. Empirical feature map computation. Since non-isomorphic substructures
experiments demonstrate that DSP outperforms state-of-the-art can also be similar, graph/node feature map computation is inac-
graph kernels on most benchmark datasets. curate without taking into account their similarity. Furthermore,
Index Terms—Shortest path, graph kernels, partition kernel, accurate similarity computation needs to employ the distribu-
neural language models, transformer. tions and dependencies of substructures in each graph, which
are disregarded by R-convolution graph kernels. Second, they
I. INTRODUCTION use the simple aggregation of all non-isomorphic substructure
RAPHS can represent the characteristics and relationships similarity as graph similarity, which is inaccurate, while not
G of data and are widespread in numerous real-life scenar-
ios, including citation networks [1], social networks [2], and
exploiting the distribution information of substructures in the
whole graph dataset for computing graph similarity. Neglecting
the utilization of the above two types of distribution information
Received 10 November 2024; revised 5 August 2025; accepted 2 September of substructures prevents R-convolution graph kernels from
2025. Date of publication 4 September 2025; date of current version 9 October
2025. This work was supported in part by the National Natural Science Foun- accurately capturing the similarities between graphs and thus
dation of China under Grant 62176184, Grant 62476109, and Grant 62206108, degrades their performance.
in part by the Fundamental Research Funds for the Central Universities, and Recently, researchers have tried to integrate the distribution
in part by the Science and Technology Development Fund, Macao SAR, under
Grant 0006/2024/RIA1. Recommended for acceptance by R. Akbarinia. (Cor- information of substructures into graph kernels [9], [10], [16],
responding author: Xiaofeng Cao.) [19]. Deep Graph Kernel (DGK) [19] employs the word2vec [20]
Wei Ye is with the College of Electronic and Information Engineering, technique to learn the substructure representations, capturing the
Shanghai Institute of Intelligent Science and Technology, Shanghai Research In-
stitute for Intelligent Autonomous Systems, State Key Laboratory of Intelligent distributions and dependencies of substructures in each graph.
Autonomous Systems, Frontier Science Center for Intelligent Autonomous Sys- However, DGK does not utilize the dataset-wide distribution
tems, Tongji University, Shanghai 201804, China (e-mail: yew@[Link]). information of substructures. Wasserstein Weisfeiler-Lehman
Wengang Guo, Shuhao Tang, and Hao Tian are with the College
of Electronic and Information Engineering, Tongji University, Shanghai (WWL) graph kernel [16], Multi-scale Wasserstein Shortest-
201804, China (e-mail: guowg@[Link]; tangsh2022@[Link]; Path (MWSP) graph kernel [9], and Augmented Shortest-Path
2133036@[Link]). (ASP) graph kernel [10] compute the Wasserstein distance [21],
Xin Sun is with the Faculty of Data Science, City University of Macau, Taipa
999078, China (e-mail: sunxin1984@[Link]). [22] between the substructure feature maps of two graphs,
Xiaofeng Cao is with the School of Computer Science and Technology, Tongji accounting for the dataset-wide substructure distribution infor-
University, Shanghai 201804, China (e-mail: [Link]@[Link]). mation. Nevertheless, they overlook the distribution information
Heng Tao Shen is with the School of Computer Science and Technology,
Tongji University, Shanghai 201804, China, and also with the School of Com- of substructures and their dependencies in each graph. Moreover,
puter Science and Engineering, University of Electronic Science and Technology the Wasserstein distance has high computational complexity
of China, Chengdu 611731, China (e-mail: shenhengtao@[Link]). and is impractical for large datasets. There is little work that
This article has supplementary downloadable material available at [Link]
org/10.1109/TKDE.2025.3606566, provided by the authors. studies both types of distribution information of substructures
Digital Object Identifier 10.1109/TKDE.2025.3606566 for developing new graph kernels with high performance.

1041-4347 © 2025 IEEE. All rights reserved, including rights for text and data mining, and training of artificial intelligence and similar technologies.
Personal use is permitted, but republication/redistribution requires IEEE permission. See [Link] for more information.

Authorized licensed use limited to: Wuhan University. Downloaded on December 10,2025 at 07:30:21 UTC from IEEE Xplore. Restrictions apply.
6368 IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 37, NO. 11, NOVEMBER 2025

In this paper, we propose a new graph kernel framework that Return Probability Feature (RBF) and the inherent attributes
integrates both kinds of distribution information in graphs to (node labels or continuous attributes) of each node. Each graph is
circumvent the above two challenges related to R-convolution represented by a set of such feature vectors and projected into the
graph kernels. Our framework is generic and can be com- Reproducing Kernel Hilbert Space (RKHS) by Maximum Mean
bined with any type of substructure. However, recognizing that Discrepancy (MMD) [34]. NCW [35] groups random walks by
the small-world phenomenon [23] occurs in many real-world their starting nodes and generalizes the random walk graph ker-
graphs, i.e., the average shortest path length between any node nel [31]. Grouping significantly improves the expressive power
pair is relatively small, graph kernels [7] based on the short- of the random walk graph kernel.
est paths are suitable for measuring the similarities between Shortest Path (SP) graph kernel [7] compares the shortest
them. Therefore, one variant of our framework is called the paths between each node pair in two graphs. Every shortest
Distributional Shortest-Path (DSP) graph kernel. Specifically, path is represented by a triplet in the form of (the label of the
we extract the shortest paths of length at most k around each source node, the label of the sink node, the length), which is
node and store them in the bag of k-hop shortest paths. For each coarse and may lose graph structural information. Tree++ [8]
node, its distributional shortest-path node feature map can be exploits the truncated Breadth-First Search (BFS) tree of height
learned by any neural language model (e.g., Transformer [24] K rooted at each node to constrain the maximum length of the
or GloVe [25]) trained on the k-hop shortest-path sentence (con- shortest paths. Moreover, it extends the shortest path to the super
structed by the shortest paths in the bag of k-hop shortest paths of path whose elements are BFS trees that capture multiple scales
this node). The learned distributional shortest-path node feature of the graph structure. The graph similarity is the sum of all
map encompasses the distributions and dependencies of the graph similarities at different scales. Multi-scale Wasserstein
shortest paths in each graph. In addition, we propose the Partition Shortest-Path (MWSP) graph kernel [9] develops a multi-scale
Kernel (PK) to capture the distribution of the shortest paths shortest-path node feature map for each node and represents each
in the entire graph dataset. Given a space partitioning method graph as a set of node feature maps. The graph similarity is com-
(e.g., iForest [26], K-Means [27], or KNN [28]), PK measures puted by the Wasserstein distance, capturing the distributions
the expectation of separating two distributional shortest-path of multi-scale shortest-path node feature maps across graphs.
node feature maps into the same partition. Those feature maps Augmented Shortest-Path (ASP) graph kernel [10] enhances SP
belonging to the same partition are further projected into the via graph augmentation. Nodes are augmented by the variable
same point (which is called the PK feature map) in the Repro- depths of the shortest-path-induced trees rooted at them, and the
ducing Kernel Hilbert Space (RKHS). Finally, we employ the graph structure is augmented by the graph filtration [36]. The
Kernel Mean Embedding (KME) [29] to compute graph feature Wasserstein distance is also adopted to compute graph similarity.
maps, based on the assumption that all the PK feature maps in
each graph are independently and identically sampled from an B. Graph Kernels Based on Subgraphs
unknown distribution. Both PK and DSP are proven symmetric
Graphlet Kernel (GK) [11] quantifies graph similarities by
and positive semi-definite. Besides, we theoretically prove that
counting the frequencies of subgraphs with limited size, i.e.,
the feature map of DSP in the RKHS can be linearly separable
graphlets [37]. Since the exhaustive enumeration of all the
by a hyperplane.
graphlets of different sizes is time-consuming, the maximum
Our contributions can be summarized as follows:
r We propose a generic graph kernel framework that can use size of graphlets is fixed to five, limiting the performance
of GK. Neighborhood Subgraph Pairwise Distance Kernel
any neural language models to learn the embeddings of any
(NSPDK) [12] uses the neighborhood subgraphs of small radius
graph substructures.
r For an instance of the proposed generic graph kernel frame- at increasing distances as the graph substructure and com-
putes the kernel matrix with a fast graph invariant encoding,
work, DSP utilizes Transformer to learn the embeddings of
which may map non-isomorphic neighborhood subgraphs to the
the shortest paths, capturing the distribution of the shortest
same string, leading to inaccurate graph similarity. Multiscale
paths as well as their dependencies in each graph.
r DSP employs the proposed partition kernel (PK) to capture Laplacian Graph kernel (MLG) [13] designs a variant of Bhat-
tacharyya kernel [38] called the Feature space Laplacian Graph
the distribution of the shortest paths across graphs.
r Extensive experiments demonstrate that DSP outperforms kernel (FLG) to capture the topological information in graphs.
MLG is constructed by recursively applying FLG on subgraphs
state-of-the-art graph kernels on most benchmark datasets
with increasing sizes induced from each node so that it can
for graph classification and regression tasks.
compare graphs at multiple scales. MLG suffers from efficiency
issues, thus a randomized low-rank approximation is proposed
II. RELATED WORK to speed up MLG, which nevertheless leads to performance
A. Graph Kernels Based on Walks or Paths degradation.
Vishwanathan et al. [5] investigate a unified framework for the
graph kernels proposed in [30], [31], [32], [33]. The main idea is C. Graph Kernels Based on Subtree Patterns
to count the number of matching random walks on each pair of Weisfeiler-Lehman (WL) subtree kernel [14], [15] is derived
graphs. Although several algorithms are applied to accelerate the from the one-dimensional Weisfeiler-Lehman test of graph iso-
kernel computation, the time complexity is still high. RetGK [6] morphism [39], which iteratively aggregates the neighborhood
assigns each node a feature vector whose components are the information (subtree patterns) around each node and relabels
Authorized licensed use limited to: Wuhan University. Downloaded on December 10,2025 at 07:30:21 UTC from IEEE Xplore. Restrictions apply.
YE et al.: DISTRIBUTIONAL SHORTEST-PATH GRAPH KERNELS 6369

it. Owing to the powerful expressiveness of the WL, more E. Other Graph Kernels
and more graph kernels are proposed based on it. Wasserstein
Deep Graph Kernel (DGK) [19] gives the enhanced versions
Weisfeiler-Lehman (WWL) graph kernel [16] introduces a vari-
of three popular graph kernels, i.e., SP [7], GK [11], and
ant of WL suitable for graphs with continuous attributes. It
WL [14]. It learns the latent representations of substructures
makes use of the message-passing mechanism in graph con-
(the shortest paths, graphlets, and subtree patterns) with a neural
volutional networks [40] and transforms each graph into a set
language model word2vec [20] and calculates a similarity matrix
of node embeddings. The Graph Wasserstein Distance (GWD)
that encodes the substructure relationships. The similarity matrix
is adopted to capture the distribution information of subtrees
is integrated into the base graph kernels to improve their perfor-
and compute the similarities between graph pairs. However,
mance. Graph Neural Tangent Kernel (GNTK) [51] combines
GWD has a high computational complexity, which hinders
the advantages of Graph Neural Networks (GNNs) [52], [53],
its applications to large graphs. Weisfeiler-Lehman Filtration [54], [55], [56] and graph kernels. It transfers an infinitely
(FWL) kernel [17] creates a filtration graph (a sequence of nested GNN trained by gradient descent into a graph kernel inspired
graphs) for each graph according to the values of edge weights.
by the finding that an over-parameterized neural network is
The graph similarities are measured by comparing WL subtree equivalent to a kernel [57]. Graph Quantum Neural Tangent
feature occurrence distributions over the filtration graphs. In Kernel (GraphQNTK) [58] incorporates the multi-head attention
addition, FWL shows that it improves the expressiveness of
mechanism into GNTK and proposes a quantum algorithm to ap-
the original WL. Weisfeiler-Lehman Graph Alignment (GAWL) proximate it efficiently. However, both GNTK and GraphQNTK
kernel [18] adopts the WL test of graph isomorphism to align face the problems of over-parameterization and over-fitting
the nodes over a set of graphs and permutes the adjacency ma-
caused by GNNs on small graphs. Like RetGK, MMD-GK [59]
trices. Subsequently, it proposes an efficient method for kernel is also based on random walks and the Maximum Mean Dis-
computation and compares the aligned adjacency matrices to
crepancy (MMD). It computes graph kernels by applying MMD
construct the kernel matrix. R-WL* [41] is a generalization of
to the node representations generated by Laplacian smoothing
the WL subtree kernel by relaxing the strict subtree comparison. on graphs. The computed graph kernel does not contain the
It adopts the Wasserstein K-means clustering [42] to group
distribution information of random walks in each graph.
the WL subtrees, which are treated as equal if they belong to
the same cluster. However, the tree edit distance used for the
Wasserstein K-means clustering has low expressive power to III. PRELIMINARIES
accurately capture the distance between two WL subtrees. The notations used in this paper are given below. Let X =
{(Gi , yi )}N
i=1 denote a graph dataset, where Gi = (Vi , Ei , l) is
an undirected and labeled graph with label yi . Vi represents
D. Graph Kernels Based on Assignments
the node set and Ei represents the edge set of Gi , respectively.
In addition to the R-convolution graph kernels mentioned l : V → L is a label function that assigns a positive integer label
above, there is another family of graph kernels based on assign- to each node v ∈ V, where L contains a set of integer labels.
ments. The main idea is to find the optimal matching between Given the shortest path P u,v starting from node u and ending
the substructures that maximizes the graph similarities. Optimal at node v, we represent it with a label string, each element of
Assignment (OA) kernel [43] defines a class of base kernels which is the label of a node in it, i.e., P u,v =  l(u), . . . , l(v) .
called strong kernels, which are induced from graph hierarchies. Kernel functions are commonly used for similarity measure-
It guarantees that the optimal assignment kernels derived from ment. Let us define a function κ : X × X → R on a non-empty
the strong kernels are symmetric and positive semi-definite. set X (we abuse the notation here). κ is a symmetric and positive
Nikolentzos et al. [44] characterize each graph as a set of node semi-definite kernel if there exists a Reproducing Kernel Hilbert
vectors (the eigenvectors of its adjacency matrix) and propose Space (RKHS) H and a feature map φ : X → H such that for
two algorithms to calculate graph similarities, one of which is the any x, x ∈ X , κ(x, x ) = φ(x), φ(x ) is satisfied, where ·, ·
Earth Mover’s Distance [45] and the other of which is the Pyra- is the inner product in H.
mid Match kernel [46]. Hierarchical Transitive-Aligned Ker- Definition 1 (Graph Kernels): Let X be a non-empty set of
nel (HTAK) [47] first generates a collection of H-hierarchical graphs, then κ can be defined as a graph kernel between two
prototype representations with the K-means clustering method. graphs G and G in X as follows:
Then, it hierarchically aligns the nodes of each graph with  
its different H-level prototype representations and constructs  
κ (G, G ) = φ(G), φ (G ) = φ(v), φ (v  ) (1)
the kernel matrix by counting the number of aligned node
v∈V v  ∈V 
pairs. HAQJSK [48] is an extension of HTAK by combining
Quantum Jensen-Shannon Kernel (QJSK) [49] with HTAK. where φ(G) and φ(G ) are the graph feature maps; φ(v) and
Both HTAK and HAQJSK are proposed for unattributed graphs. φ(v  ) are the node feature maps.
DHGAK [50] exploits the utilization of neural language models Equation (1) shows that the graph similarity computation is
to embed substructures and the utilization of clustering methods strict. Only if two nodes having common substructures around
to align substructures. The alignment is proven to be transitive. them in two different graphs contribute to the graph similar-
Like HTAK, the performance of DHGAK is affected by the ity computation. Node feature map distribution across graphs,
chosen clustering method. which leads to more accurate similarity computation, is not

Authorized licensed use limited to: Wuhan University. Downloaded on December 10,2025 at 07:30:21 UTC from IEEE Xplore. Restrictions apply.
6370 IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 37, NO. 11, NOVEMBER 2025

Fig. 1. The overview of the proposed DSP graph kernel. We briefly describe DSP with two graphs G1 and G2 . In step 1, we extract the bag of k-hop (k = 1)
shortest paths around each node and construct the 1-hop shortest-path sentence. For example, the bag of 1-hop shortest paths starting from node v1 in G1
is B (1) (v1 ) = {P v1 ,v1 , P v1 ,v3 , P v1 ,v4 } and the corresponding 1-hop shortest-path sentence is S (1) (v1 ) = “P v1 ,v1 P v1 ,v3 P v1 ,v4 ”. Then, we learn the
embeddings of the shortest paths with the neural language models, which capture the distribution information of the shortest paths as well as their dependencies
in each graph. We calculate the distributional shortest-path feature map of each node by aggregating the embeddings of the shortest paths starting from this node.
In step 2, we consider all the distributional shortest-path node feature maps in G1 and G2 as a dataset and compute their PK feature maps in the RKHS under t
different partitionings, capturing the dataset-wide distribution information of the shortest paths. In this figure, each partitioning has 4 partitions, i.e., c = 4. We
compute the mean of the PK node feature maps in G1 and G2 as their graph feature maps φ(G1 ) and φ(G2 ), respectively. The graph kernel between G1 and G2
is the inner product of their graph feature maps, i.e., κ(G1 , G2 ) = φ(G1 ), φ(G2 ).

utilized in (1). If the used graph substructure is the shortest path, information of the shortest paths in a graph; 2) Constructing
the shortest-path node feature map of each node can be defined the kernel matrix from graph feature maps that consist of the
as: distribution information of the shortest paths in the entire graph
Definition 2 (Shortest-Path Node Feature Map): Let X be a dataset. Each step is articulated in the following sections.
non-empty set of graphs, G = (V, E, l) ∈ X be an undirected
and labeled graph, and P = {P1 , P2 , . . . , P|P| } be a set of non- A. Distributional Shortest-Path Node Feature Map
isomorphic shortest paths extracted from all the graphs in X .
We propose to learn the embeddings of all non-isomorphic
Define a map ψ : V × L → N such that ψ(v, Pi ) (v ∈ V, 1 ≤
shortest paths, capturing their dependencies and distributions
i ≤ |P|) denotes the number of occurrences of the shortest path
in each graph. Previous studies [19], [60] have demonstrated
Pi with starting node v in graph G. Then, the shortest-path node
that the distribution of graph substructures follows a power
feature map of node v is defined as:
law, which is consistent with the distribution pattern of words
  
φ(v) = ψ(v, P1 ), ψ(v, P2 ), . . . , ψ v, P|P| (2) in natural language. Therefore, it is reasonable to capture the
distribution of the shortest paths and their dependencies by
From Definition 2, we observe that the shortest-path node learning their embeddings with neural language models (such
feature map cannot reveal the distributions and dependencies as Transformer [24] and GloVe [25]).
of the non-isomorphic shortest paths starting from each node, First, we extract the shortest paths of finite length (k-hop)
since it just independently counts the number of occurrences of around each node and define the bag of the k-hop shortest paths
them. Thus, the shortest-path node feature map is less expressive of each node as follows:
in capturing the graph structural information around each node Definition 3 (Bag of the k-hop Shortest Paths): For graph
within each graph, leading to inaccurate graph similarity. G = (V, E, l), we construct a Breadth-First Search (BFS) tree
(k)
In summary, not utilizing the distributions of substructures Tv = (V  , E  , l) of depth k (k ≥ 1) rooted at each node v ∈ V,
within and across graphs causes inaccurate graph similarity where V  ⊆ V and E  ⊆ E. ∀v  ∈ V  , there exists the shortest
and suboptimal performance of traditional R-convolution graph 
path P v,v =  l(v), . . . , l(v  ) starting from the root node v and
kernels. ending at v  . The bag of the k-hop shortest paths starting from
(k)
node v contains all the shortest paths in Tv , i.e., B (k) (v) =

IV. METHOD: DSP (k) P
v,v
.
v  ∈Tv
In this section, we describe the technical details of the pro- For each shortest path P ∈ B (k) (v), we calculate the Eigen-
posed DSP graph kernel. The overview of DSP is depicted in vector Centrality (EC) values of all the nodes in P and sum
Fig. 1. DSP has two major steps: 1) Generating distributional them up as the EC value of P , which reflects the importance of
shortest-path node feature maps that capture the distribution P around node v. Subsequently, we sort all the shortest paths in

Authorized licensed use limited to: Wuhan University. Downloaded on December 10,2025 at 07:30:21 UTC from IEEE Xplore. Restrictions apply.
YE et al.: DISTRIBUTIONAL SHORTEST-PATH GRAPH KERNELS 6371

Definition 4 (Distributional Shortest-Path Node Feature

Map): Let g : P → Rd (d is the embedding dimension) be the
shortest-path embedding function learned by the neural language
model trained on the k-hop shortest-path sentences extracted
from graph G = (V, E, l), the distributional shortest-path node
feature map of each node v ∈ V is defined as follows:

x(k) (v) = x(k−1) (v) g(P ) (3)
P ∈B (k) (v)

where is the concatenation operation, B (k) (v) is the bag of

the k-hop shortest paths starting from node v and x(1) (v) :=
P ∈B (1) (v) g(P ).

B. Kernel Construction
In the above section, we learn the distributional shortest-path
node feature maps by the neural language models, capturing
the dependencies and distributions of the shortest paths in each
(2)
graph. In this section, we design the Partition Kernel (PK) to
Fig. 2. (a) The graph G, the BFS tree Tv2 of depth 2 with root node v2 , capture the dataset-wide distribution information of the shortest
(2)
Tv2 .
and all the shortest paths in The shortest path with the same starting and paths. PK projects similar (i.e., belonging to the same partition)
ending node is also demonstrated. (b) The labeled version of (a).
distributional shortest-path node feature maps to the same point
(PK feature map) in the RKHS. After that, we compute the graph
feature map as the mean of the PK feature maps of all the nodes
B (k) (v) by their EC values in ascending order. If two shortest in each graph. The DSP graph kernel is constructed by the inner
paths have the same EC value, we sort them again according to product of each pair of graph feature maps, avoiding the high
the lexicographical order of their string representations. After time complexity of the Wasserstein distance computation.
that, we concatenate all the shortest paths in the sorted B (k) (v) We define PK as follows:
as the k-hop shortest-path sentence of v (denoted by S (k) (v)). Definition 5 (Partition Kernel): Given a graph dataset
Each shortest path in S (k) (v) is treated as a word. X = {(Gi , yi )}N i=1 , where yi is the label of Gi , let X =
We set k = 2 and take Fig. 2 as an example to explain v∈Vi ,i∈[1,N ] x(v) be the union matrix of the distributional
the k-hop shortest-path sentence. For graph G, we construct shortest-path node feature maps of all graphs Gi (i ∈ [1, N ])
(2)
the BFS tree Tv2 of depth 2 rooted at node v2 and store in X , ξ : X → θ be a partitioning method that separates X
all the shortest paths into B (2) (v2 ). All the shortest paths in into c partitions, i.e., θ = {ϑ1 , ϑ2 , . . . , ϑc }, and Θξ (X) be the
B (2) (v2 ) are P v2 ,v2 =  2 , P v2 ,v1 =  2, 4 , P v2 ,v6 =  2, 1 , set of all admissible θ produced by ξ under X. For any two
P v2 ,v3 =  2, 4, 2 , P v2 ,v5 =  2, 4, 4 and P v2 ,v4 =  2, 4, 3 . points x, y ∈ X,1 the Partition Kernel of x and y is defined as
Therefore, the 2-hop shortest-path sentence of v2 after sorting the expectation that both x and y are separated into the same
is S (2) (v2 ) =  2 2, 1 2, 4 2, 4, 2 2, 4, 3 2, 4, 4 . All the shortest partition ϑ ∈ θ across all partitionings θ ∈ Θξ (X):
paths in S (2) (v2 ) are separated by spaces. κP K (x, y) = Eθ∼Θξ (X) [I(x, y ∈ ϑ | ϑ ∈ θ)] (4)
Given a graph dataset, we construct the k-hop shortest-path
sentence for every node in every graph. If the used neural where I(·) is the indicator function, whose value is 1 or 0,
language model is Transformer, we can select next-word predic- depending on whether or not the input is true.
tion [61] as the pretraining task for training the model. Suppose Assume Θξ (X) contains a finite number of partitionings, i.e.,
the model can continuously predict the next shortest path and Θξ (X) = {θ1 , θ2 , . . . , θt }, and the partition which x belongs to
ultimately reconstruct the entire k-hop shortest-path sentence. does not depend on the partition which y belongs to, expectation
In that case, it indicates that the model has effectively captured in (4) can be approximated as follows:
the distribution information of the shortest paths and also their
1
t
dependencies in each graph. κP K (x, y) = I (x, y ∈ ϑ | ϑ ∈ θi )
(k−1) (k) t i=1
Note that Tv is a subtree of Tv , which means the
(k)
bag of the k-hop shortest paths B (v) of node v includes
1
t
the bag of the (k − 1)-hop shortest paths B (k−1) (v). There- = I (x ∈ ϑ) I (y ∈ ϑ) (5)
fore, we can get the embeddings of all the shortest paths in t i=1
ϑ∈θi
B (1) (v), B (2) (v), . . . , B (k) (v) via the neural language model
trained on the k-hop shortest-path sentences. 1 For convenience, we use x to denote x(v) and y to denote x(v  ), where
Finally, the distributional shortest-path feature map of each x(v) and x(v  ) are the distributional shortest-path node feature maps of two
node can be defined as follows: nodes v and v  from {Gi }Ni=1 .

Authorized licensed use limited to: Wuhan University. Downloaded on December 10,2025 at 07:30:21 UTC from IEEE Xplore. Restrictions apply.
6372 IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 37, NO. 11, NOVEMBER 2025

Theorem 1: PK is symmetric and positive semi-definite. Algorithm 1: DSP.

Proof: See the proof in the appendix. 
Since PK is a valid (symmetric and positive semi-definite)
kernel, it has explicit feature maps in the RKHS, which can be
defined as follows:
Definition 6 (PK Feature Map): For each point (distributional
shortest-path node feature map) x ∈ X, let φi : x → {0, 1}c be
the PK feature map of x under θi ∈ Θξ (X) (1 ≤ i ≤ t). φi (x)
is a c-dimensional binary vector whose jth (1 ≤ j ≤ c) element
equals one, i.e., φi (x)j = I(x ∈ ϑj | ϑj ∈ θi ), which means x
belongs to the jth partition ϑj ∈ θi . Then, the PK feature map of
x under all t partitionings θ ∈ Θξ (X) can be defined as follows:
φ(x) = φ1 (x) φ2 (x) ··· φt (x) (6)
Then, (5) can be rewritten as:
1
κP K (x, y) = φ(x), φ (y) (7)
t
We observe that (7) slackens the strict comparison of node
feature maps in (1) and computes the similarity between any
pair of nodes within or across graphs, using the dataset-wide
distribution information of the shortest paths, i.e., whether two
distributional shortest-path node feature maps belong to the
same partition or not over t different partitionings.
By assuming that all the PK feature maps in each graph
are independently and identically sampled from an unknown
distribution G, the mean of the PK feature maps in each
graph can be used to represent that graph, which is the
idea of the Kernel Mean Embedding (KME) [29]. For graph
G = (V, E, l), its graph feature map can be computed as
follows:
1 
φ(G) = φ (x(v)) (8)
|V|
v∈V

For each pair of graphs G and G , we construct the proposed

respectively. Lines 1–10 generate distributional shortest-path
DSP graph kernel as:
node feature maps for the nodes in all the graphs. For each
κDSP (G, G ) = φ(G), φ (G ) (9) node v ∈ V which belongs to graph G = (V, E, l), we construct
the BFS tree of depth i (1 ≤ i ≤ k) rooted at it and derive its
Theorem 2: DSP is symmetric and positive semi-definite.
bag of the i-hop shortest paths B (i) (v) (lines 4–8). The BFS
Proof: See the proof in the appendix. 
traversal has a time complexity of O(n + e). Therefore, the
Theorem 3: Given a graph dataset X = {(Gi , yi )}N i=1 , where
time complexity of computing distributional shortest-path node
yi is the label of Gi , let X = v∈Vi ,i∈[1,N ] x(v) be the union
feature maps for all the nodes in the graph dataset X is bounded
matrix of the distributional shortest-path node feature maps of
by O(N kTg (n(n + e))), where O(Tg ) is the time complexity
all graphs Gi (i ∈ [1, N ]) in X , Θξ (X) be a set containing a
of the shortest-path embedding function g (i.e., neural language
finite number of partitionings, i.e., Θξ (X) = {θ1 , θ2 , . . . , θt },
models).
where θi = {ϑi,1 , ϑi,2 , . . . , ϑi,c } (1 ≤ i ≤ t), each point x(v) ∈
Lines 11–15 construct the kernel matrix of DSP. We first
X is assigned to the partition ϑi,j if and only if v ∈ Vj of Gj .
project all the distributional shortest-path node feature maps
∀t ∈ N, the feature maps generated by DSP for one class of
to the RKHS and compute their PK feature maps (line 12).
graphs {(Gp , yp )} can be linearly separated from those of the
The above process has a time complexity of O(N ntTp ), where
other class of graphs {(Gq , yq ) : yq = yp }.
O(Tp ) is the time complexity of performing the selected parti-
Proof: See the proof in the appendix. 
tioning method once. Lines 13–15 compute the graph feature
map and the DSP graph kernel with a time complexity of
C. Time Complexity Analysis
O(N 2 tc). Thus, the time complexity of kernel construction is
The pseudo-code of DSP is given in Algorithm 1. For the O(N tc(Tp + N )).
convenience of analysis, we assume that all the graphs have Totally, the time complexity of DSP is bounded by
the same number of nodes and edges, denoted by n and e, O(N kTg (n(n + e)) + N tc(Tp + N )).

Authorized licensed use limited to: Wuhan University. Downloaded on December 10,2025 at 07:30:21 UTC from IEEE Xplore. Restrictions apply.
YE et al.: DISTRIBUTIONAL SHORTEST-PATH GRAPH KERNELS 6373

TABLE I TABLE II
STATISTICS OF THE BENCHMARK DATASETS USED IN THIS PAPER. N/A MEANS SEARCH RANGES OF 3 PARAMETERS IN DSP. N DENOTES THE NUMBER OF
GRAPHS IN THE DATASET DO NOT HAVE NODE LABELS. GRAPHS IN EACH BENCHMARK DATASET. k CONTROLS THE SIZE OF THE BAG
OF THE k-HOP SHORTEST PATHS. t IS THE PARTITIONING TIME OF THE
DATASET-WIDE FEATURE MAP SPACE. c IS THE NUMBER OF PARTITIONS EACH
TIME.

and DSP-KNN have different characteristics, we have three

groups of search ranges, which are given in Table II. Specifically,
for the NCI1 and NCI109 datasets, the search range of c in
DSP-I is expanded to {22 , 23 , . . . , 211 }, the search range of c
in DSP-KNN is expanded to {23 , 24 , . . . , 29 }, and the search
range of t in DSP-KNN is expanded to {25, 50, . . . , 200}.
All the parameters for each implementation of DSP are grid
searched by cross-validation on the training data. For baseline
V. EXPERIMENTAL EVALUATION methods, we adopt the default parameter settings in their original
A. Experimental Setup implementations.
Training Details: For each benchmark dataset, we generate
Since any partitioning method can be used to construct PK all the k-hop (k = 7) shortest-path sentences as the inputs and
and generate PK feature maps, for ease of implementation, we train the Transformer [24] model for 200 epochs with a batch
use three simple ones, i.e., iForest [26], K-Means [27], and size of 1024 and a learning rate of 0.001. Due to the limited
KNN [28], and have three corresponding implementations of memory capacity of the used Nvidia GeForce RTX 3090 GPU,
DSP: DSP-I, DSP-KM, and DSP-KNN. Other advanced par- the output dimension of the encoder is set to 16, i.e., the em-
titioning methods, such as spectral clustering [62] and kernel bedding dimension of the shortest paths is d = 16, the number
clustering [63] can also be used here. We adopt Transformer [24] of attention heads in the multi-head attention module is set to 4,
as the neural language model to learn the embeddings of the the number of encoder/decoder layers is set to 3, the number of
shortest paths, capturing their distributions and dependencies the feed-forward network neurons is set to 256, and the dropout
in each graph. Transformer is a deep neural language model rate is set to 0.1.
that can catch long-range dependencies with the self-attention Evaluation Metric: For each method, we choose a binary C-
mechanism, which means it can effectively capture the depen- SVM [73] (or a KSVM [74] for WWL, FWL, and MWSP) as
dencies of the shortest paths around each node and thus is more the classifier and evaluate the kernel matrix of each method. We
expressive than shallow models such as GloVe [25]. report the average classification accuracy and standard deviation
Baselines: We select 10 state-of-the-art graph kernels as the over the 10-fold cross-validation.
baseline methods: SP [7], WL [14], [15], DGK [19], WWL [16], Experimental Environment: All three implementations of
FWL [17], GraphQNTK [58], GAWL [18], MWSP [9], DSP are written in Python, and all the experiments are performed
ASP [10], and MMD-GK [59]. For SP and WL, we implement on a server with a dual-core Intel(R) Xeon(R) Gold 6226R CPU
them with GraKeL [64]. For other baseline methods, their im- @ 2.90 GHz, 256 GB, an Nvidia GeForce RTX 3090 GPU,
plementations are available from their official websites. 24 GB, and an Ubuntu 18.04.6 LTS operating system. The code
Benchmark Datasets: We compare our DSP with the base- of DSP is publicly available at Github.2
line methods on 15 benchmark datasets for graph clas-
sification, including 6 chemical compound datasets (MU- B. Graph Classification Results
TAG [65], BZR [65], COX2 [65], DHFR [66], NCI1 [67],
and NCI109 [67]), 6 molecular compound datasets (4 variants The classification results of the three implementations of DSP
of PTC [68], ENZYMES [69], and PROTEINS [69]), and 3 (DSP-I, DSP-KM, and DSP-KNN) on the benchmark datasets
social network datasets (IMDB-B [19], IMDB-M [19], and are shown in Table III. The partitioning methods affect the
DBLP_v1 [70]). All the benchmark datasets are downloaded performance of DSP. DSP-I performs the best on 12 out of 15
from [71]. The statistics of the benchmark datasets are given datasets while DSP-KM and DSP-KNN only achieve the best
in Table I. For the three datasets IMDB-B, IMDB-M, and performance on two and one dataset, respectively. DSP-KNN
DBLP_v1 that have no node labels, node degrees are used as has the second best performance on 9 datasets whereas DSP-KM
node labels, following the strategy adopted by [72]. has the second best performance on 3 datasets. In conclusion,
Parameter Settings: Our DSP involves 3 major parameters: DSP-I is more promising compared with the other two imple-
the hop k used to generate distributional shortest-path node mentations.
feature maps and the t, c parameters used to compute PK feature
maps. Since the partitioning methods used in DSP-I, DSP-KM, 2 [Link]

Authorized licensed use limited to: Wuhan University. Downloaded on December 10,2025 at 07:30:21 UTC from IEEE Xplore. Restrictions apply.
6374 IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 37, NO. 11, NOVEMBER 2025

TABLE III
AVERAGE CLASSIFICATION ACCURACIES ± STANDARD DEVIATIONS (%) OF
THE THREE IMPLEMENTATIONS OF DSP (DSP-I, DSP-KM, AND DSP-KNN) ON
BENCHMARK DATASETS. THE BEST RESULTS ARE HIGHLIGHTED IN BOLD AND
THE RUNNER-UP RESULTS ARE HIGHLIGHTED AS UNDERLINED.

Fig. 3. Average classification accuracies (%) of DSP-I with different k values

on 2 benchmark datasets (PROTEINS and NCI1), where k controls the size of
the bag of the k-hop shortest paths, which are used to generate distributional
shortest-path node feature maps.

Table IV shows the classification accuracy of DSP (the best

results in Table III) and baseline methods on benchmark datasets.
DSP outperforms all the baselines on 12 out of 15 datasets.
On the ENZYMES and PROTEINS datasets, DSP achieves the
Fig. 4. Average classification accuracies (%) of DSP-I under all the combina-
second-best results, with tiny gaps from the best results (0.9% tions of t and c on 2 benchmark datasets (PROTEINS and NCI1), where t and
lower than GAWL on ENZYMES and 0.2% lower than ASP on c are the parameters used to compute PK feature maps, i.e., t is the partitioning
PROTEINS). Compared to the baselines, DSP gains significant time of the dataset-wide feature map space and c is the number of partitions
each time.
improvements on some datasets. For example, the average clas-
sification accuracies of DSP are 2.1%, 1.9%, and 1.7% higher
than those of the best baseline methods (GAWL, WWL, and
MWSP) on BZR, COX2, and PTC_FR, respectively. For all the k = 2 do not fully capture the distributions and dependencies of
R-convolution graph kernels, they only consider at most one the shortest paths, which affects the performance of DSP-I. For
type of distribution information (WWL and MWSP consider NCI1, DSP-I gains a significant improvement of classification
the dataset-wide distribution information of substructures). DSP accuracy (about 10%) when k steps to 2. To sum up, the perfor-
is only outperformed by GAWL and ASP on 3 datasets, i.e., mance of DSP-I benefits from the increase of k, as distributional
ENZYMES, PROTEINS, and NCI1. MWSP performs the best shortest-path node feature maps capture more graph structural
on the dataset NCI109 and is the runner-up on 6 datasets, information around each node.
showcasing its very competitive performance. ASP performs the Then, we come to the sensitivity analysis of t and c. We
best on 3 datasets and is the runner-up on 3 datasets. DGK and fix k = 7 and calculate the average classification accuracies of
GraphQNTK are deep graph kernels that adopt neural techniques DSP-I under all the combinations of t ∈ {50, 100, . . . , 250} and
to improve their performance. However, DSP outperforms them c ∈ {22 , 23 , . . . , 28 }. Fig. 4 displays the heatmaps of classifica-
on all datasets. MMD-GK uses the MMD to compute the dis- tion accuracies on 2 benchmark datasets PROTEINS and NCI1.
tance between the node representations of graphs, capturing the It is evident that high values of t lead to better performance
distributions of random walks with different hops on each graph. on both datasets. For PROTEINS, the classification accuracies
It is outperformed by DSP by a large margin. In conclusion, DSP are relatively stable when the value of c changes, which means
exhibits superior performance on all the benchmark datasets the performance of DSP is slightly affected by parameter c on
compared with state-of-the-art graph kernels. PROTEINS. For NCI1, the performance of DSP continuously
improves when the value of c increases. Overall, the robustness
of DSP with respect to the parameters t and c changes in different
C. Parameter Sensitivity patterns on different datasets, which may be due to the different
We analyze the parameter sensitivity of DSP-I. We first an- properties of the datasets. As a starting point, t and c can be set
alyze the parameter sensitivity of k. With t and c fixed (their to large values.
values are shown in the legends in Fig. 3), we vary k from 1 to To sum up, the variant DSP-I tends to have better performance
7 and report the average classification accuracies of DSP-I on when the values of k, t, and c are large. However, for a new
2 benchmark datasets PROTEINS and NCI1. For PROTEINS, dataset in real-world applications, the starting value for k can be
the classification accuracy first drops when k changes from 1 to set to the ceiling value of the average length of all the shortest
2, then rises continuously when k ≥ 2. The possible reason is paths in a graph dataset. Nevertheless, k should not be greater
that the distributional shortest-path node feature maps at scale than the maximum length of all the shortest paths, since this can

Authorized licensed use limited to: Wuhan University. Downloaded on December 10,2025 at 07:30:21 UTC from IEEE Xplore. Restrictions apply.
YE et al.: DISTRIBUTIONAL SHORTEST-PATH GRAPH KERNELS 6375

TABLE IV
AVERAGE CLASSIFICATION ACCURACIES ± STANDARD DEVIATIONS (%) OF DSP AND BASELINE METHODS ON THE BENCHMARK DATASETS. THE BEST RESULTS
ARE HIGHLIGHTED IN BOLD AND THE RUNNER-UP RESULTS ARE HIGHLIGHTED AS UNDERLINED. RESULTS MARKED WITH † ARE OBTAINED FROM THE ORIGINAL
PAPERS. N/A MEANS THE RESULTS ARE UNAVAILABLE WITHIN THE RUNNING TIME QUOTA OF 24 HOURS.

TABLE V the performance of DSP-I. Compared to DSP-I w/ W, DSP-I

AVERAGE CLASSIFICATION ACCURACIES ± STANDARD DEVIATIONS (%) OF
DSP-I AND ITS 4 VARIANTS ON BENCHMARK DATASETS. THE BEST RESULTS
performs the best on 14 out of 15 datasets. On ENZYMES,
ARE HIGHLIGHTED IN BOLD AND THE RUNNER-UP RESULTS ARE the classification accuracy of DSP-I is only 0.8% lower than
HIGHLIGHTED AS UNDERLINED. that of DSP-I w/ W. Therefore, considering the dataset-wide
distribution information of the shortest paths is crucial for mea-
suring graph similarities, and our PK considers the dataset-wide
distribution information better than the Wasserstein distance. As
expected, DSP-I w/o T&P has the worst classification results on
all datasets, manifesting the effectiveness of capturing both types
of distribution information on the performance improvements
of R-convolution graph kernels. Compared with the other 3
variants, DSP-I GloVe achieves the best results on 3 datasets
and the second-best results on 9 datasets, showcasing the effect
of GloVe. On the PTC_FM and PTC_FR datasets, DSP-I GloVe
has the same performance as DSP-I. On the PTC_MR dataset,
DSP-I GloVe outperforms DSP-I by 1.1%. On the remaining
datasets, DSP-I GloVe is outperformed by DSP-I due to the
utilization of the more powerful Transformer in the latter DSP
variant.
bring about redundant information. t and c can be set to large
values, such as 250 and 256, respectively. E. Running Time
Table VI shows the running time for kernel matrix computa-
D. Ablation Study
tion of DSP-I and baseline methods on benchmark datasets. SP
We compare DSP-I with its 4 variants: DSP-I w/o T, DSP- and WL run faster than DSP-I. The reason is that they do not need
I w/ W, DSP-I w/o T&P, and DSP-I GloVe. DSP-I w/o T to include both types of distribution information in the compu-
constructs node feature maps by using the number of occurrences tation of the kernel matrix. DSP-I achieves comparable running
of the shortest paths around nodes instead of learning their time to DGK and GAWL on most benchmark datasets. For two
embeddings with the Transformer. DSP-I w/ W uses the Wasser- IMDB datasets, DSP-I is slower because it spends more time on
stein distance to compute graph similarities. DSP-I w/o T&P Transformer inference. Compared to other methods, DSP-I runs
is a variant without using either Transformer or PK. Instead, faster because it uses the simple and efficient KME, while the
it employs the number of occurrences of the shortest paths comparison methods adopt some time-consuming techniques
to construct graph feature maps and uses the inner product to such as the Maximum Mean Discrepancy (used by MMD-GK),
compute graph similarities. It is a R-convolution graph kernel. Wasserstein distance (used by WWL, FWL, MWSP, and ASP),
DSP-I GloVe is a variant that adopts GloVe [25] as the neural and the multi-head attention mechanism (used by GraphQNTK)
language model to learn the embeddings of the shortest paths to measure graph similarities. Moreover, the speed-up of DSP-
instead of using the Transformer. I is significant on large datasets. Although DSP-I uses the
Table V shows the classification results of DSP-I and its 4 vari- shortest-path embeddings generated by the cumbersome model
ants on benchmark datasets. DSP-I outperforms DSP-I w/o T on Transformer, its running time is not affected much because of the
all the datasets, which indicates that capturing the distributions parallel computation by GPUs. Thus, we conclude that DSP-I is
and dependencies of the shortest paths in each graph can improve efficient.

Authorized licensed use limited to: Wuhan University. Downloaded on December 10,2025 at 07:30:21 UTC from IEEE Xplore. Restrictions apply.
6376 IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 37, NO. 11, NOVEMBER 2025

TABLE VI
RUNNING TIME (IN SECONDS) FOR KERNEL MATRIX COMPUTATION OF DSP-I AND BASELINE METHODS ON BENCHMARK DATASETS. N/A MEANS THE RUNNING
TIME EXCEEDS THE TIME QUOTA OF 24 HOURS.

TABLE VII shortest-path-based graph kernels (SP and MWSP). However,

THE MEAN ABSOLUTE ERROR (MAE) RESULT OF EACH METHOD ON THE
DATASET ZINC-12 K. THE BEST RESULT IS HIGHLIGHTED IN BOLD AND THE
the shortest-path-based graph kernel ASP is better than the
RUNNER-UP RESULT IS HIGHLIGHTED AS UNDERLINED. N/A MEANS THE subtree-based graph kernels WL and WWL. GraphQNTK still
RUNNING TIMES EXCEED THE TIME QUOTA OF 24 HOURS. cannot get the result within the running time quota of 24 hours.
Even though DSP is proposed for graph classification, it can also
be transferred for graph regression and has the best performance,
signifying that the strategies for capturing the shortest-path
distribution information within and across graphs are effective
and generalizable.

VI. CONCLUSION
For more accurate graph similarity computation, we have
proposed a novel graph kernel called DSP that realizes both
the graph-wide and dataset-wide distribution information of the
shortest paths in this paper. First, we utilize the neural language
F. Graph Regression models to learn the distributional shortest-path node feature
map of each node, capturing the distribution information of the
Except for the graph classification task, we compare DSP-I shortest paths as well as their dependencies in each graph. Then,
and the baselines on the graph regression task. We use a subset we design the Partition Kernel (PK) to capture the dataset-wide
(ZINC-12K [75]) of ZINC molecular graphs (250 K) dataset [76] distribution information of the shortest paths. PK projects similar
for regressing a molecular property called “constrained solu- (i.e., belonging to the same partition) distributional shortest-path
bility”, i.e., log P -SA-cycle, where log P is the octanol-water node feature maps to the same point (PK feature map) in the
partition coefficients, SA stands for the synthetic accessibility RKHS, and hence the Kernel Mean Embedding (KME) can be
score, and cycle stands for the number of long cycles in the applied to construct the proposed DSP graph kernel efficiently.
molecules. For each molecular graph, nodes denote atoms and Extensive experiments on benchmark datasets demonstrate the
edges denote chemical bonds between atoms. ZINC-12K is effectiveness and efficiency of DSP compared with state-of-the-
divided into training, validation, and test sets in a 10:1:1 ratio. art graph kernels. In the future, we would like to use the Large
Support Vector Regression (SVR) is applied to the kernel matrix Language Models (LLMs) to learn the embeddings of the graph
for graph regression. The parameter ranges for DSP-I are defined substructures.
as k ∈ {1, 2, . . . , 7}, t ∈ {100, 200}, and c ∈ {22 , 23 , . . . , 211 }.
We perform a grid search over these parameters on the validation
set to select the best value and report the Mean Absolute Error ACKNOWLEDGMENT
(MAE) between the predicted and the ground-truth constrained We thank the anonymous reviewers for their valuable and
solubility for each molecular graph in the test set. constructive comments.
The results presented in Table VII indicate that DSP-I per-
forms the best on the graph regression task. DSP-I outperforms
SP, MWSP, and ASP by a large margin and defeats DGK REFERENCES
and MMD-GK significantly. Generally, the subtree-based graph [1] V. Batagelj, “Efficient algorithms for citation network analysis,”
kernels (WL, WWL, FWL, and GAWL) perform better than the 2003, arXiv:cs/0309023.

Authorized licensed use limited to: Wuhan University. Downloaded on December 10,2025 at 07:30:21 UTC from IEEE Xplore. Restrictions apply.
YE et al.: DISTRIBUTIONAL SHORTEST-PATH GRAPH KERNELS 6377

[2] R. Kumar, J. Novak, and A. Tomkins, “Structure and evolution of online [30] C. Cortes, P. Haffner, and M. Mohri, “Rational kernels,” in Proc. Adv.
social networks,” in Proc. 12th ACM SIGKDD Int. Conf. Knowl. Discov. Neural Inf. Process. Syst., 2002, pp. 617–624.
Data Mining, 2006, pp. 611–617. [31] T. Gärtner, P. Flach, and S. Wrobel, “On graph kernels: Hardness results
[3] G. C. Koh, P. Porras, B. Aranda, H. Hermjakob, and S. E. Orchard, ”An- and efficient alternatives,” in Proc. Learn. Theory Kernel Mach.: 16th
alyzing protein–protein interaction networks,” J. proteome Res., vol. 11, Annu. Conf. Learn. Theory 7th Kernel Workshop, Washington, DC, USA,
no. 4, pp. 2014–2031, 2012. 2003, pp. 129–143.
[4] D. Haussler et al., “Convolution kernels on discrete structures,” Technical [32] H. Kashima, K. Tsuda, and A. Inokuchi, “Marginalized kernels between
report, Department of Computer Science, University of California, Tech. labeled graphs,” in Proc. 20th Int. Conf. Mach. Learn., 2003, pp. 321–328.
Rep. UCSC-CRL-99-10, 1999. [33] R. Kondor and K. M. Borgwardt, “The skew spectrum of graphs,” in Proc.
[5] S. V. N. Vishwanathan, N. N. Schraudolph, R. Kondor, and K. M. Borg- 25th Int. Conf. Mach. Learn., 2008, pp. 496–503.
wardt, “Graph kernels,” J. Mach. Learn. Res., vol. 11, pp. 1201–1242, [34] A. Gretton, K. M. Borgwardt, M. J. Rasch, B. Schölkopf, and A. Smola, “A
2010. kernel two-sample test,” J. Mach. Learn. Res., vol. 13, no. 1, pp. 723–773,
[6] Z. Zhang, M. Wang, Y. Xiang, Y. Huang, and A. Nehorai, “RetGK: Graph 2012.
kernels based on return probabilities of random walks,” in Proc. Adv. [35] N. M. Kriege, “Weisfeiler and Leman go walking: Random walk kernels
Neural Inf. Process. Syst., 2018, pp. 3968–3978. revisited,” in Proc. Adv. Neural Inf. Process. Syst., 2022, pp. 20119–20132.
[7] K. M. Borgwardt and H.-P. Kriegel, “Shortest-path kernels on graphs,” in [36] L. O’Bray, B. Rieck, and K. Borgwardt, “Filtration curves for graph
Proc. IEEE Int. Conf. Data Mining, 2005, pp. 8. representation,” in Proc. 27th ACM SIGKDD Conf. Knowl. Discov. Data
[8] W. Ye, Z. Wang, R. Redberg, and A. Singh, “Tree++: Truncated tree based Mining, 2021, pp. 1267–1275.
graph kernels,” IEEE Trans. Knowl. Data Eng., vol. 33, no. 4, pp. 1778– [37] N. Pržulj, D. G. Corneil, and I. Jurisica, “Modeling interactome: Scale-free
1789, Apr. 2021. or geometric,” Bioinformatics, vol. 20, no. 18, pp. 3508–3515, 2004.
[9] W. Ye, H. Tian, and Q. Chen, “Multiscale Wasserstein shortest-path graph [38] R. Kondor and T. Jebara, “A kernel between sets of vectors,” in Proc. 20th
kernels for graph classification,” IEEE Trans. Artif. Intell., vol. 5, no. 6, Int. Conf. Mach. Learn., 2003, pp. 361–368.
pp. 2973–2984, Jun. 2024. [39] A. Leman and B. Weisfeiler, “A reduction of a graph to a canonical form
[10] W. Ye, H. Tian, S. Tang, and X. Sun, “Enhancing shortest-path graph and an algebra arising during this reduction,” Nauchno-Technicheskaya
kernels via graph augmentation,” in Proc. Joint Eur. Conf. Mach. Learn. Informatsiya, vol. 2, no. 9, pp. 12–16, 1968.
Knowl. Discov. Databases, 2024, pp. 180–198. [40] T. N. Kipf and M. Welling, “Semi-supervised classification with graph
[11] N. Shervashidze, S. Vishwanathan, T. Petri, K. Mehlhorn, and K. Borg- convolutional networks,” in Proc. Int. Conf. Learn. Representations, 2017.
wardt, “Efficient graphlet kernels for large graph comparison,” in Proc. [41] T. H. Schulz, T. Horváth, P. Welke, and S. Wrobel, “A generalized
Artif. Intell. Statist., 2009, pp. 488–495. Weisfeiler-Lehman graph kernel,” Mach. Learn., vol. 111, no. 7, pp. 2601–
[12] F. Costa and K. De Grave, “Fast neighborhood subgraph pairwise distance 2629, 2022.
kernel,” in Proc. 26th Int. Conf. Mach. Learn., Omnipress; Madison, WI, [42] A. Irpino, R. Verde, and F. d. A. De Carvalho, “Dynamic clustering of
USA, 2010, pp. 255–262. histogram data based on adaptive squared wasserstein distances,” Expert
[13] R. Kondor and H. Pan, “The multiscale laplacian graph kernel,” in Proc. Syst. Appl., vol. 41, no. 7, pp. 3351–3366, 2014.
Adv. Neural Inf. Process. Syst., 2016, pp. 2990–2998. [43] N. M. Kriege, P.-L. Giscard, and R. Wilson, “On valid optimal assignment
[14] N. Shervashidze and K. Borgwardt, “Fast subtree kernels on graphs,” in kernels and applications to graph classification,” in Proc. Adv. Neural Inf.
Proc. Adv. Neural Inf. Process. Syst., 2009, pp. 1660–1668. Process. Syst., 2016, pp. 1623–1631.
[15] N. Shervashidze, P. Schweitzer, E. J. Van Leeuwen, K. Mehlhorn, and K. [44] G. Nikolentzos, P. Meladianos, and M. Vazirgiannis, “Matching node
M. Borgwardt, “Weisfeiler-Lehman graph kernels,” J. Mach. Learn. Res., embeddings for graph similarity,” in Proc. AAAI Conf. Artif. Intell., 2017,
vol. 12, no. 9, pp. 2539–2561, 2011. pp. 729–733.
[16] M. Togninalli, E. Ghisu, F. Llinares-López, B. Rieck, and K. Borgwardt, [45] Y. Rubner, C. Tomasi, and L. J. Guibas, “The earth mover’s distance as a
“Wasserstein Weisfeiler-Lehman graph kernels,” in Proc. Adv. Neural Inf. metric for image retrieval,” Int. J. Comput. Vis., vol. 40, pp. 99–121, 2000.
Process. Syst., 2019, pp. 6439–6449. [46] K. Grauman and T. Darrell, “The pyramid match kernel: Efficient learning
[17] T. Schulz, P. Welke, and S. Wrobel, “Graph filtration kernels,” in Proc. with sets of features,” J. Mach. Learn. Res., vol. 8, no. 4, pp. 725–760,
AAAI Conf. Artif. Intell., 2022, pp. 8196–8203. 2007.
[18] G. Nikolentzos and M. Vazirgiannis, “Graph alignment kernels using [47] L. Bai, L. Cui, and H. Edwin, “A hierarchical transitive-aligned graph
Weisfeiler and Leman hierarchies,” in Proc. Int. Conf. Artif. Intell. Statist., kernel for un-attributed graphs,” in Proc. Int. Conf. Mach. Learn., 2022,
2023, pp. 2019–2034. pp. 1327–1336.
[19] P. Yanardag and S. Vishwanathan, “Deep graph kernels,” in Proc. 21th [48] L. Bai et al., “HAQJSK: Hierarchical-aligned quantum Jensen-Shannon
ACM SIGKDD Int. Conf. Knowl. Discov. Data Mining, 2015, pp. 1365– kernels for graph classification,” IEEE Trans. Knowl. Data Eng., vol. 36,
1374. no. 11, pp. 6370–6384, Nov. 2024.
[20] T. Mikolov, K. Chen, G. Corrado, and J. Dean, “Efficient estimation of [49] L. Bai, L. Rossi, A. Torsello, and E. R. Hancock, “A quantum Jensen–
word representations in vector space,” in Proc. Int. Conf. Learn. Repre- Shannon graph kernel for unattributed graphs,” Pattern Recognit., vol. 48,
sentations, 2013. no. 2, pp. 344–355, 2015.
[21] M. Cuturi, “Sinkhorn distances: Lightspeed computation of optimal trans- [50] S. Tang, H. Tian, X. Cao, and W. Ye, “Deep hierarchical graph alignment
port,” in Proc. Adv. Neural Inf. Process. Syst., 2013, pp. 2292–2300. kernels,” in Proc. Int. Joint Conf. Artif. Intell., 2024, pp. 4964–4972.
[22] J. Altschuler, J. Niles-Weed, and P. Rigollet, “Near-linear time approxi- [51] S. S. Du, K. Hou, R. R. Salakhutdinov, B. Poczos, R. Wang, and
mation algorithms for optimal transport via Sinkhorn iteration,” in Proc. K. Xu, “Graph neural tangent kernel: Fusing graph neural networks
Adv. Neural Inf. Process. Syst., 2017, pp. 1961–1971. with graph kernels,” in Proc. Adv. Neural Inf. Process. Syst., 2019,
[23] D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’ pp. 5723–5733.
networks,” Nature, vol. 393, no. 6684, pp. 440–442, 1998. [52] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini,
[24] A. Vaswani et al., “Attention is all you need,” in Proc. Adv. Neural Inf. “The graph neural network model,” IEEE Trans. Neural Netw., vol. 20,
Process. Syst., 2017, pp. 6000–6010. no. 1, pp. 61–80, Jan. 2009.
[25] J. Pennington, R. Socher, and C. D. Manning, “GloVe: Global vectors [53] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and S. Y. Philip, “A com-
for word representation,” in Proc. 2014 Conf. Empirical Methods Natural prehensive survey on graph neural networks,” IEEE Trans. Neural Netw.
Lang. Process., 2014, pp. 1532–1543. Learn. Syst., vol. 32, no. 1, pp. 4–24, Jan. 2021.
[26] F. T. Liu, K. M. Ting, and Z.-H. Zhou, “Isolation forest,” in Proc. 18th [54] J. Zhou et al., “Graph neural networks: A review of methods and applica-
IEEE Int. Conf. Data Mining, 2008, pp. 413–422. tions,” AI Open, vol. 1, pp. 57–81, 2020.
[27] S. Lloyd, “Least squares quantization in PCM,” IEEE Trans. Inf. Theory, [55] Z. Zhang, P. Cui, and W. Zhu, “Deep learning on graphs: A survey,” IEEE
vol. 28, no. 2, pp. 129–137, Mar. 1982. Trans. Knowl. Data Eng., vol. 34, no. 1, pp. 249–270, Jan. 2022.
[28] E. Fix, Discriminatory Analysis: Nonparametric Discrimination, Con- [56] J. Yang, S. Medya, and W. Ye, “Incorporating heterophily into graph neural
sistency Properties, vol. 1. Dayton, OH, USA: USAF School Aviation networks for graph classification,” in Proc. 2024 IEEE Int. Conf. Syst.,
Medicine, 1985. Man, Cybern., 2024, pp. 1544–1551.
[29] A. Smola, A. Gretton, L. Song, and B. Schölkopf, “A Hilbert space em- [57] A. Jacot, F. Gabriel, and C. Hongler, “Neural tangent kernel: Convergence
bedding for distributions,” in Proc. Int. Conf. Algorithmic Learn. Theory. and generalization in neural networks,” in Proc. Adv. Neural Inf. Process.
Berlin, Germany: Springer, 2007, pp. 13–31. Syst., 2018, pp. 8580–8589.

Authorized licensed use limited to: Wuhan University. Downloaded on December 10,2025 at 07:30:21 UTC from IEEE Xplore. Restrictions apply.
6378 IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 37, NO. 11, NOVEMBER 2025

[58] Y. Tang and J. Yan, “GraphQNTK: Quantum neural tangent kernel for Wengang Guo received the bachelor’s degree in au-
graph data,” in Proc. Adv. Neural Inf. Process. Syst., 2022, pp. 6104–6118. tomation from Shanghai Dianji University, Shanghai,
[59] Y. Sun and J. Fan, “MMD graph kernel: Effective metric learning for China, in 2020. He is currently working toward the
graphs via maximum mean discrepancy,” in Proc. 12th Int. Conf. Learn. PhD degree with the College of Electronic and In-
Representations, 2024. formation Engineering, Tongji University, Shanghai,
[60] B. Perozzi, R. Al-Rfou, and S. Skiena, “Deepwalk: Online learning of China. He was also a visiting PhD student with the
social representations,” in Proc. 20th ACM SIGKDD Int. Conf. Knowl. Faculty of Computer Science, University of Vienna,
Discov. Data Mining, 2014, pp. 701–710. Austria, from 2023 to 2024. His research interests pri-
[61] M. Soam and S. Thakur, “Next word prediction using deep learning: A marily focus on unsupervised representation learning,
comparative study,” in Proc. 12th Int. Conf. Cloud Comput., Data Sci. clustering, and computer vision.
Eng., 2022, pp. 653–658.
[62] W. Ye, S. Goebl, C. Plant, and C. Böhm, “FUSE: Full spectral clustering,” Shuhao Tang received the BE degree in automation
in Proc. 22nd ACM SIGKDD Int. Conf. Knowl. Discov. Data Mining, 2016, from Xiamen University, Xiamen, China, in 2022.
pp. 1985–1994. He is currently working toward the master’s degree
[63] Z. Ren and Q. Sun, “Simultaneous global and local graph structure pre- with the College of Electronic and Information En-
serving for multiple kernel clustering,” IEEE Trans. Neural Netw. Learn. gineering, Tongji University, Shanghai, China, ma-
Syst., vol. 32, no. 5, pp. 1839–1851, May 2021. joring in electronic information. His research focuses
[64] G. Siglidis, G. Nikolentzos, S. Limnios, C. Giatsidis, K. Skianis, and M. on graph kernels, representation learning, and graph
Vazirgiannis, “GraKeL: A graph kernel library in Python,” J. Mach. Learn. deep learning.
Res., vol. 21, no. 54, pp. 1–5, 2020.
[65] A. K. Debnath, R. L. Lopez de Compadre, G. Debnath, A. J. Shusterman,
and C. Hansch, “Structure-activity relationship of mutagenic aromatic Hao Tian received the master’s degree in electronic
and heteroaromatic nitro compounds. correlation with molecular orbital information from the College of Electronic and Infor-
energies and hydrophobicity,” J. Med. Chem., vol. 34, no. 2, pp. 786–797, mation Engineering from Tongji University, Shang-
1991. hai, China, in 2024, and the BE degree in electrical
[66] J. J. Sutherland, L. A. O’brien, and D. F. Weaver, “Spline-fitting with a ge- engineering and automation from the East China Uni-
netic algorithm: A method for developing classification structure- activity versity of Science and Technology, Shanghai, China,
relationships,” J. Chem. Inf. Comput. Sci., vol. 43, no. 6, pp. 1906–1915, in 2020. His research interests include graph repre-
2003. sentation learning, graph kernels, and graph neural
[67] N. Wale, I. A. Watson, and G. Karypis, “Comparison of descriptor spaces networks.
for chemical compound retrieval and classification,” Knowl. Inf. Syst.,
vol. 14, pp. 347–375, 2008.
[68] N. Kriege and P. Mutzel, “Subgraph matching kernels for attributed Xin Sun (Senior Member, IEEE) received the PhD
graphs,” in Proc. Int. Conf. Mach. Learn., 2012, pp. 291–298. degree from the College of Computer Science and
[69] K. M. Borgwardt, C. S. Ong, S. Schönauer, S. Vishwanathan, A. J. Technology, Jilin University, Changchun, China, in
Smola, and H.-P. Kriegel, “Protein function prediction via graph kernels,” 2013. He is currently a full professor with the Faculty
Bioinformatics, vol. 21, no. suppl_1, pp. i47–i56, 2005. of Data Science, City University of Macau, Taipa,
[70] S. Pan, X. Zhu, C. Zhang, and S. Y. Philip, “Graph stream classification Macau, China. Before that, he was an Experienced
using labeled and unlabeled graphs,” in Proc. IEEE 29th Int. Conf. Data Humboldt Researcher with the Technical Univer-
Eng., 2013, pp. 398–409. sity of Munich, Munich, Germany. He was a post-
[71] K. Kersting, N. M. Kriege, C. Morris, P. Mutzel, and M. Neumann, doctoral researcher with the Institut für Informatik,
“Benchmark data sets for graph kernels,” 2016. [Online]. Available: Ludwig-Maximilians-Universität München, Munich,
[Link] Germany. His research interests include machine
[72] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “How powerful are graph neural learning, data mining, and computer vision.
networks,” in Proc. Int. Conf. Learn. Representations, 2019.
[73] C.-C. Chang and C.-J. Lin, “LIBSVM: A library for support vector ma- Xiaofeng Cao (Member, IEEE) received the PhD de-
chines,” ACM Trans. Intell. Syst. Technol., vol. 2, no. 3, 2011, Art. no. 27. gree from Australian Artificial Intelligence Institute,
[74] G. Loosli, S. Canu, and C. S. Ong, “Learning SVM in kreı̆n spaces,” IEEE University of Technology Sydney, Australia, and was
Trans. Pattern Anal. Mach. Intell., vol. 38, no. 6, pp. 1204–1216, Jun. 2015. a visiting scholar with the Hong Kong University of
[75] V. P. Dwivedi, C. K. Joshi, A. T. Luu, T. Laurent, Y. Bengio, and X. Science and Technology, and the Centre for Frontier
Bresson, “Benchmarking graph neural networks,” J. Mach. Learn. Res., AI Research (CFAR), A*STAR, Singapore. He is
vol. 24, no. 43, pp. 1–48, 2023. currently an associate professor with the School of
[76] J. J. Irwin, T. Sterling, M. M. Mysinger, E. S. Bolstad, and R. G. Coleman, Computer Science and Technology, Tongji Univer-
“ZINC: A free tool to discover chemistry for biology,” J. Chem. Inf. Model., sity, Shanghai, China. He has more than 40 academic
vol. 52, no. 7, pp. 1757–1768, 2012. works published in IEEE Transactions on Pattern
[77] C. Cortes, “Support-vector networks,” Proc. Mach. Learn., vol. 20, Analysis and Machine Intelligence, IEEE Transac-
pp. 273–297, 1995. tions on Knowledge and Data Engineering, IEEE Transactions on Neural
Networks and Learning Systems, ICML, NeurIPS, ICLR, ECML, etc, and
served as the PC members/reviewers. His research interests include the PAC
learning theory, convex optimization/non-convex approximation, and hyperbolic
Wei Ye (Member, IEEE) received the PhD degree (non-euclidean) geometry.
in computer science from Institut für Informatik,
Ludwig-Maximilians-Universität München, Munich, Heng Tao Shen (Fellow, IEEE) received the BSc de-
Germany, in 2018. He is now a Tenure-Track profes- gree with 1st class honours and PhD degrees from the
sor with the College of Electronic and Information Department of Computer Science, National Univer-
Engineering, Shanghai Institute of Intelligent Sci- sity of Singapore, in 2000 and 2004 respectively. He is
ence and Technology, Shanghai Research Institute a professor with the School of Computer Science and
for Intelligent Autonomous Systems, the State Key Technology, Tongji University, Shanghai, China. His
Laboratory of Intelligent Autonomous Systems, and research interests mainly include multimedia search,
Frontier Science Center for Intelligent Autonomous computer vision, artificial intelligence, and Big Data
Systems, Tongji University. From 2018 to 2020, he management. He is/was an associate editor of ACM
was a postdoctoral Researcher in the Department of Computer Science at the Transactions on Data Science, IEEE Transactions on
University of California, Santa Barbara. Before that, he worked as a researcher Image Processing, IEEE Transactions on Multime-
with the Department of AI Platform, Tencent, China. His research interests in- dia, and IEEE Transactions on Knowledge and Data Engineering. He is also an
clude data mining, graph machine learning, deep learning, and network science. OSA fellow and ACM fellow.

Authorized licensed use limited to: Wuhan University. Downloaded on December 10,2025 at 07:30:21 UTC from IEEE Xplore. Restrictions apply.