Hierarchical Shortest-Path Graph Kernel Network
Authors: Jiaxin Wang
Wenxuan Tu
Jieren Cheng
Venue: NeurIPS 2025 spotlight ()
Keywords: Graph Kernel Neural Networks
Graph Classification
Primary area: general_machine_learning
TL;DR: We propose a simple yet effective framework that integrates graph similarity estimation with downstream tasks within a unified optimization framework.

Abstract: Graph kernels have emerged as a fundamental and widely adopted technique in graph machine learning. However, most existing graph kernel methods rely on fixed graph similarity estimation that cannot be directly optimized for task-specific objectives, leading to sub-optimal performance. To address this limitation, we propose a kernel-based learning framework called Hierarchical Shortest-Path Graph Kernel Network HSP-GKN, which seamlessly integrates graph similarity estimation with downstream tasks within a unified optimization framework. Specifically, we design a hierarchical shortest-path graph kernel that efficiently preserves both the semantic and structural information of a given graph by transforming it into hierarchical features used for subsequent neural network learning. Building upon this kernel, we develop a novel end-to-end learning framework that matches hierarchical graph features with learnable $hidden$ graph features to produce a similarity vector. This similarity vector subsequently serves as the graph embedding for end-to-end training, enabling the neural network to learn task-specific representations. Extensive experimental results demonstrate the effectiveness and superiority of the designed kernel and its corresponding learning framework compared to current competitors.

Hierarchical Shortest-Path Graph Kernel Network
Jiaxin Wang' Wenxuan Tu Jieren Cheng" 1.2-
School of Cyberspace Security, Hainan University School of Computer Science and Technology, Hainan University (twx,992730)0haae Chainanu edu.
Abstract
Graph kemnels have emerged as a fundamental and widely adopted technique in graph machine learning. However, most existing graph kernel methods rely on fixed graph similarity estimation that cannot be directly optimized for task-specific objectives, leading to sub-optimal performance. To address this limitation, we pro- pose kernel-based learning framework called Hierarchical Shortest-Path Graph Kernel Network (HSP-GKN), which seamlessly integrates graph similarity estima- tion with downstream tasks within unified optimization framework. Specifically, we design hierarchical thortest-patle graph kernel that efficiently preserves both the semantic and structural information of given graph by transforming it into hierarchical features used for subsequent neural network learning. Building upon this kernel, develop novel end-to-end learning framework that matches hierar- chical graph features with learnable hidden graph features to produce a similarity vector. This similarity vector subsequently serves the graph embedding for end- to-end training, enabling the neural network to learn task-specific representations. Extensive experimental results demonstrate the effectiveness and superiority of the designed kernel and its corresponding learning framework compared to current com- petitors. Code is available at sattps://githin com/ Jomm/XXWAGG-TM GRAPH/HSPPSSSS HHPHHHHSSKIKI
Introduction
Graph neural networks (GNNs) have become prominent approach in graph machine learning 22
9]. Most GNN models belong to the family of message paagge--psinggggg neural networks, where node representations are updated by passing messages and aggregating information from neighboring nodes [10 IT
14 [5]. However, existing GNNs typically use permutation invariant readout functions aggregate the node representations into a graph embedding. Recent studies have shown that their expressive power is constrained by the --Weisfeiler-Lemmee (1-WL. test [7]. which limits their ability capture complex graph structures and affects their performance on graph-level tasks [18] 20).
Thanks to the ability to model complex relationships, graph kernel methods have been powerful tools for analyzing and learning from graph-structured data (21] By employing mechanisms such substructure matching and topological feature extraction, these graph kernels have been able to effectively capture the structural information of graphs (22). Despite their great successes, graph kernels rely on handcrafted kernel functions, which pose challenges in adapting flexibly to diverse task requirements. On the one hand, most graph kernel methods measure graph similarity in an implicit manner, thereby limiting their ability to incorporate with neural networks for learning task- relevant representations. On the other hand, certain kernel methods, such as the Neighborhood Hash Kerne [23 and Graphlet (24, employ the approach of explicit feature mappings. However, these methods typically represent graphs using the frequency of substructure occurrences or symbolic
"Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

labels, ignoring the semantic information crucial for accurate graph similarity matching 225. Unlike kernel methods, neural networks are capable of extracting task-relevant features from the data driven by the objective function. Moreover, the high computational complexity of kernel methods renders them impractical for large-scale datasets. Consequently, is critically important to develop a novel framework that combines the structural feature-capturing advantages of graph kernels with the representation learning capabilities of neural networks.
An intuitive solution is to design a framework that facilitates the negotiation between the graph kernel learning and neural network optimization processes. Within this framework, kernel serves as a measure- ment of graph similarity, while the neural network is incorporated to integrate this process with the task objective for task-specific representation learning. To fulfill this, there are two key challenges to be ad- dressed, i... 1) the selected kernel should capture both the semantic and structural information of the graph; and 2) the similarity measurement process driven by the kernel is supposed to be differentiable, enabling the network to be end-to-end trainable. For the first challenge. inspired by the findings from pre- vious work [26] 27] that distance encoding is more expressive than the 1- algorithm, we attempt to design the kernel based on the shortest paths. Since the nodes the shortest paths provide rich semantic information, the positions of different nodes on the shortest path reflect the topological information of the path, For the second challenge, we explicitly map the graph into vector space where similarity can be measured using the vector inner product. Since the vector inner product is differentiable, it facilitates the joint learning between kernel-induced features and the neural network to obtain more useful representations for specific tasks (28]
Mapped features in H
Similarity mensurement
SVM
Tosk dbjective
Existing graph lernnl paradign
Mapped features in
Similarity measurement
MLP
Took *abjentive
Hidden features
(b) Propoeed HSP-GKN paradigm
Figure I: Optimization pipeline comparison of existing graph kernel methods and pro- posed HSP-GKN framework.
In this paper, we propose simple yet effective kernel-based graph learning framework, termed Hicrarchical Shortest-Path Graph Kernel Network (HSP-GKN). Specifically, we first design a com- putationally efficient graph kernel based on the shortest paths in the graph, which constructs an explicit feature mapping that transforms the graph into hierarchical features to preserve both the semantic and structural information of the given graph. Next, we integrate task objective and similar- ity measurement into a unified optimization framework. In this framework, we first define a set of trainable hidden graph features and then use the designed kernel to measure their similarity with the hierarchical features. The resultant similarity vector serves as the graph embedding that is fed into a multilayer perceptron (MLP) for training. Unlike previous graph kernel methods that isolate the learning processes of graph representations and objective optimization [29], the proposed HSP-GKN integrates them into a unified framework to learn representations that are more relevant to specific tasks, as illustrated in Figure [ The dashed lines represent the optimization process of the task objective, with the blue borders indicating trainable components and H denoting a Hilbert space.
Our contributions include: (1) We design a computationally efficient kernel based on the shortest paths. It can be flexibly integrated with neural networks while preserving both the semantic and structural information of a given graph. (2) We develop a novel framework termed HSP-GKN which integrates the kernel we proposed with neural networks, enabling objective-driven learning of representations beneficial for specific tasks. (3) Experimental results on graph classification datasets across various domains demonstrate the proposed kernel and framework outperform traditional graph kernel methods and state-of-the-ee models in terms of both performance and computational efficiency.
2 Related Work
Graph kernels. Most graph kernels follow the R-convolution framework (30], which decomposes graphs into substructures and computes similarities via kernel functions, aggregating them to yield the overall graph similarity. Different graph kernels are computed in distinct ways, we categorize them into explicitly and implicitly computed graph kernels in this work. The idea of explicitly computing graph kernels involves mapping graph into feature vector and measuring the similarity

---

between the feature vectors of two graphs [23 24 31 32 These methods typically map graphs into feature vectors composed of the frequency substructure occurrences, focusing mainly on graph topology while neglecting node semantic information. Unlike these methods, implicit computed kernels measure similarity between substructures that are hard to represent explicitly. The RW kernel [3 is one of the first methods that implicitly measures graph similarity based on the number of common walks between two graphs. Unlike random walks, shortest paths capture both local and global structures, while node attributes along paths provide rich semanties, motivating various shortest-path- kernels [ 36] Despite their success, the implicit similarity computation limits the ability to integrate neural networks for learning task- misk-specific representations. Moreover, the high computational complexity (e.g.. SP kernel 33 has a complexity of Onx*) with respect to the sample size n) restricts their upplicabilitty to large-scate scale datasets. In this paper, design graph kernel with a computational complexity of Onn² log n). It employs explicit computation, allowing the similarity measurement process to be optimized end-to-end, facilitating both model efficiency and task-specific learning.
Graph kernel neural networks (GKNNs). Recent research has explored the integration of graph kernels and neural networks, leading to notable performance improvements [37
38
39
40]. For
example, RWNN (37 introduces random walk-based mechanisms to capture higher-order dependen- cies and improve node representation by incorporating both local and global structural information. GNN-lofi [39] leverages localized feature-based histogram intersection enhance the representation learning of graph by focusing on local feature distribution matching. The success of GKNNs lies in their ability to combine the complementary strengths of graph kernels and neural networks [38 41). Kernel functions allow GKNNs to effectively capture structural similarities between graphs, while neural networks provide the capacity to learn complex and abstract graph representations. Despite their success, GKNNs still face several challenges. Scalability remains a major concern, particularly when applied large-scale graph datasets. Moreover, existing methods either rely on implicitly computed kernels, which prevent the model from learning task-relevant representations, or focus solely on substructures while overlooking rich semantic information in graphs. In this paper, we construct an computationally efficient explicit feature mapping that incorporates both structural and semantic information, mapping graphs into vector space amenable to neural network processing.
3 Methodology
In this section, we first introduce key notations employed throughout the paper. Next, we describe the proposed Hierarchical Shortest-Path (HSP) graph kernel, which serves as the theoretical foundation of our framework. Finally, we present the end-to-end learning framework, i.e., Hierarchical Shortest-Path Graph Kernel Networks (HSP-GKN).
3.1 Notations
Let G = E, be an undirected graph, where V is the vertex set and is the edge set, and a: V + Σ is a function that assigns attributes, either discrete or continuous, from set Σ to nodes in the graph. Given two nodes Va, U/ E V. a path x of length n from E, to Ub in G is defined as sequence of nodes π [Vi, u2,.... vnl. where
Va, Vna rhe and [v,, 11+1] E E for all i = 1,.... n 1. Let (1) v; denote the i-th node encountered while traversing along the path. In particular, we denote by ((r) the concatenation of node attributes along this path. Let |r| be the discrete length of x, and the diameter 5G) of G is the maximum length of the shortest path between any two nodes in the graph. We use X E x to denote the node attribute matrix of graph, where n is the number of nodes and d is the dimension of node attribute. The attribute of a given node U; corresponds to the i-th row of X.
3.2 Hierarchical Shortest-Path Graph Kernel
In this subsection, we introduce the Hierarchical Shortest Path- Graph Kernel, which encodes both the semantic and topological information of graphs into explicit features and describes an efficient method for its computation.
Definition 3.1. GraphHopper (GH) kernel 36 Given two graphs, G and G', let SP, (G) and SP; (G') denote the set of all shortest paths of length in graph G and G'. We can then define the
3

---

GH kernel as:
1 (G,
Σ
E
kpact (T, xt)
(1)
(ESPi(G) x'ESPI(G))
where I. denotes the results of min (G) 5 (G') ). and kpath the sum of the kernel over all nodes along the shortest paths.
However, all shortest paths need to be compared in GH kernel, and a graph can have most [V] shortest paths, the computational complexity of k(G, G") results in ((V))))))) This makes computation infeasible for large graphs. Moreover, like other kernels based on shortest paths, the GH kernel performs implicit computation, resulting in computational complexity that is quadratic in relation to the number of graphs. Consequently, design a computationally efficient instance of the GH kernel, referred to as the Hierarchical Shortest-Path (HSP) Graph Kernel.
In the HSP kernel, we restrict the node-level kernel knode to linear kernel, that is:
Kpath (TT x===
Σ
kinode (TT (1), n (i)), with knodo v/) (a),
Since the linear kernel is positive definite and the of linear kernels is still a linear kernel, Rpath remains a linear kernel and also positive definite. By exploiting the linear additivity property of the linear kernel, we construct hierarchical feature mapping that aggregates the set of shortest paths of the same length into a cohesive shortest-path.
3.3 Hierarchical Graph Feature Mapping
Differing from previous graph feature mapping, which maps the graph to fixedddimeniooal feature, we transform the graph into feature set organized by the shortest-path length. The hierarchical graph feature mapping steps are grouping all shortest paths of the same length and aggregating the node attributes at the corresponding indices along the shortest paths, therefore preserving the semantic information of nodes and their relative positions along the shortest-path.
Definition 3.2. Given a graph G, let (G) denote the set of shortest paths of length I G. We define the hierarchical graph feature mapping
(G) = (Gr = 1,2, 1,,, (2...,,(GG),, with (G) =
Σ
a(T)-
(3)
RESP.(G)
This formula aggregates the shortest paths of the same length into single cohesive shortest-pate and we can view the graph G as one that contains only 5(G) shortest paths. This approach eliminates the need to compare each pair of shortest paths of the same length between the two graphs, thereby significantly reducing computational cost. We can now simplify Eq. ( as follows:
ks (G. G')
Σ (or (G), 00 (G')).
(4)
where L denotes the results of min (8 (G) 5 (G') The derivation Eq. see Appendix A.1 In
this case, the computational complexity of ls (G, G') is ( where 5(G) is the diameter of graph G, in real-world graphs 8(G) typically much smaller than [V]. However, computing (G) requires at most |V|2 addition operations a(T). which remains high-complexity operation. In the following, we further discuss how to compute (G) efficiently.
Given the node attribute matrix X and the set of all shortest paths of length / in the graph G, denoted as (P) di (G) essentially represents the weighted sum of all nodes on the shortest paths length 1. Therefore, when searching for the shortest paths in the graph, we simultaneously maintain matrix M, E g=x((+1), where the entry [Mrl counts how many times node i appears at the j-th coordinate of the shortest paths in iPi(G) To avoid confusion, it is worth noting that M, is different from M(v) as defined in the GH kernel, where [M)k,, represents the number of times v appears as the tth node on a shortest path of discrete length j. From this, it is straightforward to derive that:
Φ (G)) vec( M,),
(5)

---

(G)
(G)
(z(
(a(G)
Input graph G
Similarity measurement
+
(G)
(
(g(G)
Similarity voctor las
MLP
Hidden graph G
LiG
Figure 2: An overview of HSP-GKN. (-)) is the hierarchical graph feature mapping.
where voc(.) denotes the vectorization operator, which transforms a matrix into vector by stacking the columns of the matrix one after another. Now, computing ((G) only need to perform 8(G) x [V] multiplication and addition operations, which is much smaller than the V additions required.
Explicit feature mapping. It is known that if a positive definite kernel ((;;,) is defined on X' x X, there exists a mapping Φ X -> H that maps the set into Hilbert space H with inner product (, ),, such that for Vx, 2j E X, it holds that:
k (I,, 24) = (2,) (2)))
(6)
Therefore, for positive definite kernel, there exists a feature space where similarity can be computed using an inner product. However, the hierarchical feature mapping that we define represents graphs in the form of sets, which cannot be computed using standard inner products. Therefore, the set-based representation does not constitute the feature space associated with our kernel.
Since our goal is to construct explicit feature mapping that transforms graphs into vector represen- tations suitable for neural network processing, we next explore how to explicitly map this set into vector space corresponding the HSP kernel.
Lemma 3.1. The hierarchical shortest-path graph kernel positive definite.
Lemma 3.2. Ifa a graph contains the shortest path of length 1, then the shortest paths of length 1, , must also exist.
The proof of Lemma 3.1 and Lemma 3.2 can be found in Appendix A.2
According to Lemma 3.2 we can conclude that although some graphs have different diameters, sorting the shortest paths of two graphs in ascending order of length allows their path lengths to overlap partially within certain range. Now, we arrange (G) into an ordered set by sorting according to the corresponding shortest-pan path length in ascending order. Subsequently, by applying concatenation operation, we obtain the feature vector representation of G:
T (G) CONCAT(e (G), 0115 (G)).
where CONCAT(-) is the vertical concatenation of vectors. It follows that (G) and (G') have corresponding positions in (G) and (G'). Let @ denote the aligned inner product of vectors of possibly different lengths, e.g.
[a. c 2 [d. = [a, 6] [d.
(8)
Referring to Eq.
we obtain:
k (G, ( O
(9)
We now further discuss the feature vector representation of G. we zero-extend (G) sufficiently large dimension that exceeds the dimension of any possible graph, Eq. (9) can be extended to the standard inner product computation. Therefore, the extended vector is essentially the mapped feature vector induced by the HSP kernel in the feature space H.
5

---

3.4 Graph Kernel Network Based on HSP
In this subsection, we present our proposed learning framework, HSP-GKN, and explain how to integrate the similarity measurement of the HSP kernel with objective optimization into unified framework. An overview of HSP-GKN is illustrated in Figure
As defined previously, hierarchical graph feature mapping transforms a graph into a set of graph features, referred as hierarchical features. The main steps of HSP-GKN begin with defining set of learnable hidden graph features. Then, a similarity vector obtained by measuring the similarity between these learnable features and the hierarchical features. Finally, we feed this similarity vector as the graph embedding into MLP and optimize the framework via an objective function.
Hidden graph features. From Eq. L9) we know that the similarity measurement process in HSP kernels is non-learnable, as each graph is mapped to a fixed vector representation. Inspired by RWNN [37]. extend the concept of hidden graph features, i..,, parameterized graph features into paths. Specifically, the set hidden graph features is defined as:
1 (G) 1, l....,,..,,,. ng 1= LJ. with 11 + 12 + nu = N.
(10)
Here, L and N are hyperparameters adjust the hierarchy and number of hidden graph features, ny and the number of shortest paths of length I in all the graphs of the training set are proportional. It worth noting that G not an actual graph; instead, was introduced to facilitate the definition. We can consider this set as consisting of features derived from N learnable graphs, each obtained through the feature mapping.
End-to-end optimization framework. After defining the hidden graph features, we use the linear kernel used by the HSP kernel measure the similarity between graph G and these features, resulting in similarity vector:
hg (f l...., 1= L..
(11)
In what follows, we provide more details about the implementation of the proposed HSP-GKN framework.
Given an input graph G, we first obtain the hierarchical feature vector representations set of the graph {dr(G) | [ - .,,,...d 8(G) through Eq. (5). Then, we define a of trainable parameters that correspond to the set of hidden graph features:
W [W1, W Wz).
(12)
where Wi E IR (1+1)xdxx and d is the dimension of the node attributes. The i-th column of W represents the vector representation oj (6) (G). Subsequently, we can obtain the similarity vector between the graph G and the feature vectors:
b = | (G) W1, (G) W..... Vy.....,,.GG)) Ww,,
with
G 0 0 if 1> 8G).
(13)
This similarity vector is then used as the graph embedding and fed into the MLP for learning. Since the inner product calculation of vectors is differentiable, the entire framework can be trained end- to-end. Under the guidance of the objective function, HSP-GKN can learn hidden graph features that are better aligned with downstream tasks, achieving improved performance compared to fixed similarity measurements.
3.5
Computational Complexity Analysis
For feature mapping, we use Dijkstra's algorithm to compute the all-pairs shortest paths for each graph, with a time complexity of O (n² log n + nm). where n is the number of vertices and m the number of edges in the graph. When generating the hierarchical feature vector representa- tion, matrix multiplication x (M, My...,, M is required, where the time complexity is O (6 + 1) nd)) ), where 5 is the graph diameter and d is the dimension of node attributes. Similarity computation uses the inner product of vectors with time complexity of O( + 1)8d). Therefore,

---

Table 1: Classification aceuracy (# standard deviation) of our HSP, HSP-GKN and the baselines the TuDatsses.. Best performance highlighted in bold. The second-best performance is indicated with underline. OOT means cannot completed within 24 hours. We use indicate the best performance among kernel methods.
MUTAG
NCTI
PTC MR
DD
BZR
PROTEINS
SP
82.4 5.5
2.0 72.5
60.2 9.4
77.9 + 4.5
83.7 4.5 0OT
74.9 3.6
WL-SP
$1.4
60.8 2.4
54.5 9.8
76.0
72.1
GII
82.5 5.8
71.0 2.3
60.2 1 9.4
OOT
82.3 d:
74.8
2.4
CORE-SP
85.1 6.8
73.8 1.4 1.4
9.7
79.3 3.8
00T
76.5 3.9
GraphSAGE
9.6
76.0
61.7
72.9 2.0
81.2 4.2
74.3 3.8
DifiPool
6.7
76.9 1.9
61.1 1.1+55.0 61.1
75.0
84.5
72.5
DGCNN
8..
76.4 1.7
59.5
76.6 4.3
81.8 =
73.2
GIN
81.7 6.7
80.0 10.01.1 1.4
59.1 7.0
75.3 + 2.9
85.4 5.1
72.8 =
KerGNN
84.2
82.8 1.8
2.74
78.9 19,900 3.5
81.8 3.9
76.5 1000:00 3.9
PathNN
87.3 6.1
81.1 1.2 1.2
65.6 1 2.4
77.0 3.
86.6 4.2
75.2 1
MMD
91.5 + 6.5
58.4 + 2.6
62.8 1.6
60.2 2 2.0
91.0
77.6 2.5
GPN
79.3 5.7
80.8 0.5
67.7 + 1.2
77.0
$1. 1.1
75.6 0.8
60.1
75.3
DHAKR
89.9
77.3 1.3 1.3
68.8 0.9
74.6 14.6+10 1.7
87.2 2.8
77.5 0.6
HSP
85.8 $5.8
1.5"
62.1 7.2"
78.3
HSP-GKN
97.5 2.2
83.6 + 1.9
76.3 + 3.4
84.2 + 2.6
98.4 + 3.6
79.5 + 1.7
ENZYMES
COLLAB
IMDB-B
IMDB-M
REDDIT-B
REDDIT-M-SK
SP
37.3 8.7
58.8 d:
58.2 1 4.7
39.2 2.3
81.7 d: 2.5
47.9 1.9 OOT
WL-SP
27.3 7.4
58.8 1.2
58.2 4.7
39.2 2 2.3
OOT
67.7
3.4
39.5 2.6
OOT 54.35 + 0.1
CORE-SP
39.5 9.3
OOT
68.5 + 3.9
49.4 + 0.5
91.0 1.8
GraphSAGE
6.0
73.9
68.8 4.5
47 17.6333
50.0 + 1.3
DifiPool
5.6
68.9 2.0
68.4 3.3
15.6 1166::3 3.4
89.1 = 1.6
53.8 1.4
DGCNN
GIN
59.6 4.5
75.6
2.3
71.2 + 3.9
48.5 3.3
89.9 = 1.9
56.1 + 1.7
KerGNN
6.5
75.1
74.4 + 4.3
6166 1L66#30
89.5
52.7 1.2
PathNN
73.0 5.2
76.9 3.4
72.6 + 3.3
4.5 50.8
89.2 1.1
53.9 -
37
GPN
65.6 1.3
83.6 + 0.5
75.1 1 2.2
49.4 1 0.9
82.7 1.4
46.9 0.9
Cosmo'
66.4
73.6
69.9
45.6 1.2
42.6
DHAKR
61.
73.8 1.7
75.2
2.6
52.1 2.5
87.4 1.3
19.2 = 1.6
54.6
2.7'
4.9 78.5
3.1"
HSP-GKN
70.4 3.1
80.1 + 1.8
2.8
55.4 1.7
91.7 + 1.2
56.7 1.3
the overall time complexity for computing the similarity is O log nm (8+ + 1) + n)d). Since real-world graphs are typically sparse (i.e., m < n²) and the graph diameter 8 usually much smaller than n [42], the computational cost of the HSP kernel primarily depends on the number of nodes in the graph. Furthermore, since each graph requires feature mapping computation only once, the computational complexity of average similarity calculation is significantly lower than the aforementioned complexity. Our experiments show a linear in the number graphs and quadratic in the number of nodes.
4 Experiments
In this section, we first evaluate the performance of the HSP kernel and its corresponding HSP-GKN framework on graph classification datasets. Next, we study the runtime behaviour of proposed methods synthetic graphs and real-world datasets. Finally, we conduct ablation experiments and hyperparameter analysis on HSP-GKN.
4.1 Graph Classification
Datasets. We evaluate the proposed kernel and framework on 12 datasets from different domains and of varying scales, all included the TUDatasets collection 43]. These datasets are categorized as follows: small molecule datasets (BZR, MUTAG, NCII, PTC MR), bioinformaties datascts (DD,

---

ENZYMES, PROTEINS), and social network datasets (COLLAB, IMDB-B, B, IMDB-M, REDDIT-B, REDDIT-M-SKI More details about these datasets can be found the Appendix B
In the HSP-GKN framework, each graph is transformed into a vector of dimension (T. + 1)Ld/2 before being fed into the model for training, which is much more compact than the original graph. Although additional preprocessing time is required, the HSP avoids processing the entire graph at each iteration. Therefore, it is comparable with GNNs in terms of overall training time.
Baselines. We compare the proposed kernel and model against the following graph kernels based on shortest path: shortest path kernel (SP) [4], Weisfeiler-Lehman shortest path kernel (WL-SP) B1. graphHopper kernel (GH) [36] and core shortest path kernel (CORE-SP) [35]. We also compare
model against various GNNs, including (1) classical GNNs such as GraphSAGE 44 DiffPool
45]. DGCNN [46] and GIN [6]; (2) state-of-the-art GNNs such as PathNN 47 MMD [41] and
GPN [ Furthermore, we compare method against recently GKNNs including kerGNN
38
Cosmo' 2024 40) and DHAKR 49
20smo'2004200
Table 2: Running time of different graph kernels on TUDatasets (seconds). OOT: timeout over 24 hours.
Runtime in soconds
Runtine secmmb
7.5-
6.0-
ENZYMES
NCII
REDDIT-M-5K
toc-
7,92
16.33
12944.24
WL-SP
49.47
367.21
OOT
(00)
GH
356.80
2935.79
OOT
graphs
Graph size
CORE-SP
26.48
49.87
31779.70
in seconds
1.71
12.70
3869.14
Runtime in
8.30-
6.6-
Table One-epoch running time of different GNNs on TUDatasets (seconds).
0.00
250
(00
730
1000
0.25
0.70
ENZYMES
NCH1
REDDIT-M-SK
Node attribute dimensicnality d
Groph density c
GraphSAGF
0.326
0.902
5,420
DiftPool
2.195
13.785
26.427
DGCNN
0.292
0.974
4.093
Figure 3: Dependence of runtime on N, n, d and e on synthetic graphs
GIN
0.412
2.322
5.193
HSP HSPNGKN GKN
0.013
0.009
0.011
Configurations. We follow 50 and evaluate TUDatasets using 10-fold cross-validation using their provided data splits for fair comparison. For datasets without predefined splits, we adopt the splitting method provided in (50) and apply the same split across all baseline models. We run each experiment 10 times to obtain the average accuracy and standard deviation. For the HSP-GKN model configuration, we use two-layer MLP, where each layer's dimension is half of the previous layer's dimension. For the selection of hyperparameters, we use Optuna [51 to tune the hyperparameters through an automated search process.
Result analysis. Table illustrates average prediction accuracies and standard deviations. We observe that the proposed HSP-GNN framework outperforms the baselines on 9 out of the 12 datasets while it provides the second- best accuracy on the remaining datasets. On the MUTAG, PTC MR, and DD datasets, our framework achieves absolute accuracy improvements of 6.0%, 7.5%, and 5.3%, respectively. over the second- best accuracy. It is worth noting that, although we restrict the node kernel of HSP to a linear kernel, it still outperforms the shortest-path-basee kernel baselines on 7 out of the 12 datasets. Furthermore, HSP-GKN achieves significantly higher classification accuracy than HSP across all datasets, demonstrating the effectiveness of our end-to-end framework. Overall, our results show that HSP-GKN achieves high performance levels on the TUDatasets.
4.2 Runtime Behaviour Study
Here, we experimentally examine the runtime performance of the HSP kernel and HSP-GKN framework.
Datasets. We assessed the behaviour on randomly generated graphs with respect to four parameters: datasct size N, graph size node attribute dimensionality d, and graph density For read-world
8

---

Table 4: Classification accuracy improvement over the HSP kernel. HSP-MLP refers to removing hidden graph features and directly inputting the graph feature vectors into the MLP for training.
ENZYMES
NCI
REDDIT-M-SK
PROTEINS
HSP-MLP HSP-GKN
7.5 15.8 T
2.14
0.3
2.8
8.4
4.47
6.2 T
datasets, selected 3 datasets from the TUDatasets. These datasets include large-scale dataset COLLAB, large graph dataset REDDIT-M-5K, and continuous attribute dataset ENZYMES.
Baselines. We compared the runtime with other graph kernel methods on real-world datasets, including SP, WL-SP, GH and CORE-SP kernel. We also evaluate the runtime in comparison to classical GNNs, including GraphSAGE, DiffPool, DGCNN and GIN.
Configurations. For randomly generated graphs, we kept out of 4 parameters fixed at their default values and varied the fourth parameter. The default values we used were 100 for N, 100 for n, 100 for d. and 0.3 for the graph density c. All experiments were conducted on system equipped with an 8-core Intel Xeon E5-2667v4@ @ 2GHz with 256 GB of RAM and an NVIDIA 3090 GPU. For the graph kernel methods used for comparison, we utilized the library provided by [52] to measure the runtime. All graph kernel methods were executed on the CPU using single core.
Results analysis. On synthetic graphs, shown in Figure linearly with dataset size N. When varying the number of nodes n per graph, we observe that the runtime of the HSP kernel scales quadratically with n, mentioned in the complexity analysis. We also observe that changing the dimension of node attributes d does not significantly increase the computation time. However, when varying the graph density c, the computation time peaks at density of 0.1 and 0.9. This is because, at low density, the graph diameter becomes large, while at high density, the number of edges m significantly higher than n.
observe that the HSP kernel scales
With real-world datasets, as shown in Table 2 our kernel shows significantly lower computation time across all datasets. particularly graphs, with average node counts of 508. Some kernels even fail to complete computation within 24 hours. Since the HSP kernel is insensitive to the dimension of node attributes, it exhibits high scalability on ENZYMES datasets. In the comparison with GNNs, as shown in Table [3] Even though our method requires preprocessing, which takes slightly less time than computing the kernel matrix (see Table the overall training time is significantly lower than other models on the ENZYMES and NCI1 datasets. Although preprocessing takes longer the REDDIT-M-5K dataset due the larger average node count, it can be parallelized to reduced preprocessing time.
large graphs. For example, REDDIT-M-5K contains 4,999
4.3 Ablation Study
To validate the effectiveness of the proposed hidden graph features, we removed the hidden graph fea- tures and directly input the graph feature vectors into the MLP for training. As shown in Table 4 HSP- GKN achieves a more significant performance im- provement over the HSP kernel. This underscores the importance of employing a trainable similarity mea- surement and confirms that integrating the HSP with hidden graph features facilitates learning task-specific graph representations that offer better performance.
BZR
PROTEINS
ROC T (90)
=VV
=.V
DD
REDDIT-B
4.4 Analysis of Hyperparameter L and N
FACUIO (9)
As can be seen in Eq. TO HSP- introduces two hyperparameterss L and N. We conduct experiments to show the effect of this parameter on four datasets. Figure illlsttaae the performance variation of HSP- GKN when L. and N varies. From these figures, we observe that 1) as the size of dataset increases, the performance of the method becomes less sensitive to
m0
1
Figure 4: The sensitivity of HSP-GKN with the variation of and N on four datasets.

---

hyperparamettes: 2) the performance of the method overall stable across a wide range of L and N.
Conclusion and Future Discussion
We propose the Hierarchical Shortest-Paths Graph Kernel Network (HSP-GKN). In our method, we introduce the hidden graph features to integrate the HSP kernel similarity measurement and downstream tasks into unified framework. Moreover, our proposed HSP kernel simultaneously preserves both the semantic and structural information of the graphs. Extensive experimental results demonstrate the effectiveness and superiority of the HSP kernel and HSP-GKN framework compared to state-of-the-ar methods. In the future, we plan to extend our methods to graph regression and other tasks.
Limitations and broader impacts. HSP incorporates the node attribute while ignoring the edge features in graphs. We mainly focus on leveraging node features and graph topology in this work, making broadly applicable across a wide range of datasets. However, the framework flexible and can be extended to support edge attributes in several ways. One possible extension is concatenating the edge attributes along the shortest path with the corresponding node attributes into unified vector representation. Since the shortest paths are already computed as part of the kernel, this concatenation would introduce minimal additional computational overhead. Alternatively, we can define separate kernel for edge features to measure the similarity between two shortest paths based on their edge attributes. This edge-based similarity can then be combined with node-based similarity to provide more comprehensive comparison between shortest paths. We leave this as promising direction for future work and believe that such an extension can further enhance the model's expressiveness on attributed graphs with rich edge information. The end-to-ent manner in graph kernel methods is inspiring for the community.
Acknowledgements
This work was supported by the National Natural Science Foundation of China (NSFC) (Grant No. 62506102, 62562026), the Key Research and Development Program of Hainan Province (Grant No. ZDYF2024GXISO144 ZDYF2023GXIS1633. and the Natural Science Foundation of Hainan University (No. X12400009401).
References
[1] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip Yu. comprehensive survey on graph neural networks. IEFE Trans. Neural Networks Learn. Syst., 32(1):4-24, 2021.
[2] Jingxin Liu, Renda Han, Wenxuan Tu, Haotian Wang, Junlong Wu, and Jieren Cheng. Feder- ated node-level clustering network with cross-subgraph link mending. In Proceedings of the International Conference on Machine Learning, 2025.
[3] Lele Fu, Bowen Deng. Sheng Huang, Tianchi Liao, Shirui Pan, and Chuan Chen. Less more: Federated graph learning with alleviating topology heterogeneity from a causal perspective. In Proceedings of the Forty-second International Conference on Machine Learning, 2025.
[4] Sheng Huang, Lele Fu, Tianchi Liao, Bowen Deng, Chuanfu Zhang, and Chuan Chen. Fedbg: Proactively mitigating bias in cross-domain graph federated learning using background data. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 5408-5416. 2025.
[5] Wenxuan Tu, Renxiang Guan, Sihang Zhou, Chuan Ma, Xin Peng, Zhiping Cai, Zhe Liu, Jieren Cheng, and Xinwang Liu. Attribute-missing graph clustering network. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 15392-15401, 2024.
[6] Wenxuan Tu, Sihang Zhou, Xinwang Liu, Xifeng Guo, Zhiping Cai, En Zhu, and Jieren Cheng. Deep fusion clustering network. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 9978-999 9778-9977, 2021.
10

---

[7] Wenxuan Tu, Sihang Zhou, Xinwang Liu, Yue Liu, Zhiping Cai, En Zhu, Changwang Zhang, and Jieren Cheng. Initializing then refining: A simple graph attribute imputation network. In Proceedings of the International Joint Conference on Artificial Intelligence, pages -300,, 2022.
[8] Renxiang Guan, Wenxuan Tu, Siwei Wang, Jiyuan Liu, Dayu Hu, Chang Tang. Yu Feng, Junhong Li, Baili Xiao, and Xinwang Liu. Structure-adaptive multi-view graph clustering for remote sensing data. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 16933-16941, 2025.
[9] Yaowen Hu, Wenxuan Tu, Yue Liu, Miaomiao Li, Wenpeng Lu, Zhigang Luo, Xinwang Liu, and Ping Chen. divide-then-rus A cluster-driver hierarchical interpolator for attribute-mising graphs. In Proceedings of the ACM International Conference on Multimedia, 2025.
[10] Zhao Kang, Chong Peng, Qiang Cheng, Xinwang Liu, Xi Peng, Zenglin Xu, and Ling Tian. Structured graph learning for clustering and semi-supervised classification. Pattern Recognition, 110:10 2021.
[11] Luca Cosmo, Anees Kazi, Seyed-Ahmade Ahmadi, Nassir Navab, and Michael M. Bronstein. Latent-graph learning for disease prediction. In Medical Image Computing and Computer Assisted Intervention, pages 643-653, 2020.
[12] Wenxuan Tu, Sihang Zhou, Xinwang Liu, Zhiping Cai, Yawei Zhao, Yue Liu, and Kunlun He. Wage: Weight-sharing attribute- graph autoencoder. IEEE Transactions Pattern Analysis and Machine Intelligence, 47(7):5760-5777, 2025.
[13] Wenxuan Tu, Sihang Zhou, Xinwang Liu, Chumpeng Ge, Zhiping Cai, and Yue Liu. Hierarchi- cally contrastive hard sample mining for graph self-supervised pre-training. IEEE Transactions on Neural Networks and Learning Systems, 35(11):16748-1677) 2024.
[14] Yaowen Hu, Wenxuan Tu, Yue Liu, Xinhang Wan, Junyi Yan, Taichun Zhou, and Xinwang Liu. Scalable attribute-missing graph clustering via neighborhood differentiation. In Proceedings of the International Conference on Machine Learning, 2025.
[15] Wenxuan Tu, Bin Xiao, Xinwang Liu, Sihang Zhou, Zhiping Cai, and Jieren Cheng. Revis- iting initializing then refining: An incomplete and missing graph imputation network. IEEE Transactions on Neural Networks and Learning Systems, 36(3):3244-3257, 2025.
[16] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Proceedings of the International Conference on Learning Representations, 2019.
[17] Jiarui Feng, Lecheng Kong, Hao Liu, Dacheng Tao, Fuhai Li, Muhan Zhang, and Yixin Chen. Extending the design space of graph neural networks by rethinking folklore weisfeiler-Ichman In Advances in Neural Information Processing Systems, pages 9029-9064, 2023.
[18] Kamilia Zaripova, Luca Cosmo, Anees Kazi, Seyed-Ahmad Ahmadi, Michael M Bronstein, and Nassir Navab. Graph-in-gren (gig): Learning interpretable latent graphs in non-cuclidean domain for biological and healthcare applications. Medical Image Anal., 18:102839, 2023.
[19] Jingxin Liu, Jieren Cheng, Renda Han, Wenxuan Tu, Jiaxin Wang, and Xin Peng. Federated graph-level clustering network. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 18870-18878, 2025.
[20] Peng Zhou, Xinwang Liu, Liang Du, and Xuejun Li. Self-paced adaptive bipartite graph learning for consensus clustering. ACM Transactions on Knowledge Discovery from Data, 17(5):1-35, 2023.
[21] Wei Ju, Zheng Fang, Yiyang Gu, Zequn Liu, Qingqing Long, Ziyue Qiao, Yifang Qin, Jianhao Shen, Fang Sun, Zhiping Xiao, Junwei Yang, Jingyang Yuan, Yusheng Zhao, Yifan Wang, Xiao Luo, and Ming Zhang. comprehensive survey on deep graph representation learning. Neural Networks, 173: 106207, 2024.
11

---

[22] Zhengyang Mao, Wei Ju, Siyu Yi, Yifan Wang, Zhiping Xiao, Qingqing Long, Nan Yin, Xinwang Liu, and Ming Zhang. Learning nowledge-diversse experts for long-tailed graph classification. ACM Transactions on Knowledge Discovery from Data, 19(2):1-24, 2025.
[23] Shohei Hido and Hisashi Kashima. A linear-time graph kernel. In IEEE International Confer- ence on Data Mining, pages 179-188, 2009.
[24] Nino Shervashidze, S. V. N. Vishwanathan, Tobias Petri, Kurt Mchlhorn, and Karsten M. Borgwardt. Efficient graphlet kernels for large graph comparison. In Proceedings of the International Conference on Artificial Intelligence and Statistics, pages 488-495, 2009.
[25] Yaxu Xie, Alain Pagani, and Didier Stricker. SG-PGM: partial graph matching network with semantic geometric fusion for 3d scene graph alignment and its downstream tasks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 28401-28411, 2024.
[26] Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, pages 4465-4478, 2020.
[27] Caterina Graziani, Tamara Drucks, Fabian Jogl. Monica Bianchini, Franco Scarselli, and Thomas Gärtner. The expressive power of path-based graph neural networks. In Proceedings of the International Conference on Machine Learning, 2024.
[28] Wei Ju, Siyu Yi, Yifan Wang, Zhiping Xiao, Zhengyang Mao, Hourun Li, Yiyang Gu, Yifang Qin, Nan Yin, Senzhang Wang. Xinwang Liu, Xiao Luo, Philip S. Yu, and Ming Zhang. A survey of graph neural networks in real world: Imbalance, noise, privacy and OOD challenges. CoRR, abs/2403.04468, 2024.
[29] Zhenyu Yang, Ge Zhang, Jia Wu, Jian Yang, Quan Z. Sheng, Shan Xue, Chuan Zhou, Charu Aggarwal, Hao Peng, Wenbin Hu, Edwin R. Hancock, and Pietro Liò. State of the art and potentialities of graph-level learning. ACM Comput. Surv., 57:2))28:1128:44, 2025.
[30] David Haussler et al. Convolution kernels on discrete structures. Technical report, Citeseer 1999.
[31] Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mchlhorn, and Karsten M. Borgwardt. Weisfeiler-lehman graph kernels. J. Mach. Learn. Res., 12(9):253922561 201 I.
[32] Xinwang Liu, Jianping Yin, Lei Wang. Lingqiao Liu, Jun Liu, Chenping Hou, and Jian Zhang. An adaptive approach to learning optimal neighborhood kernlss. IEEE transactions on cyber- neties, 4333:337,3 2012.
[33] Hisashi Kashima, Koji Tsuda, and Akihiro Inokuchi. Marginalized kernels between labeled graphs. In Proceedings of the international conference machine learning, pages 321-328, 2003.
[34] Karsten M Borgwardt and Hans-Peter Kriegel. Shortest-pant kernels on graphs. In Proceedings of the IEEE international conference data mining, pages 8 8-pp, 2005.
[35] Giannis Nikolentzos, Polykarpos Meladianos, Stratis Limnios, and Michalis Vazirgiannis. A degeneracy framework for graph similarity. In Proceedings of the International Joint Conference on Artificial Intelligence. pages 2595-2601, 2018
[36] Aasa Feragen, Niklas Kasenburg, Jens Petersen, Marleen de Bruijne, and Karsten M. Borg- wardt. Scalable kernels for graphs with continuous attributes. Advances in neural information processing systems, pages 216-224, 2013.
[37] Giannis Nikolentzos and Michalis Vazirgiannis. Random walk graph neural networks. Advances in Neural Information Processing Systems, pages 16211-16222 2020.
[38] Aosong Feng, Chenyu You, Shiqiang Wang, and Leandros Tassiulas. Kergnns: Interpretable graph neural networks with graph kernels. Proceedings of the AAAI Conference on Artificial Intelligence, pages 6614-6622, 2022.
12

---

[39] Alessandro Bicciato, Luca Cosmo, Giorgia Minello, Luca Rossi, and Andrea Torsello. Gnn-lofi: novel graph neural network through localized feature-based histogram intersection. Pattern Recognit., 148:1 10210, 2024.
[40] Luca Cosmo, Giorgia Minello, Alessandro Bicciato, Michael M. Bronstein, Emanuele Rodolà, Luca Rossi, and Andrea Torsello. Graph kernel neural networks. IEEE Trans. Neural Networks Learn. Syst., 36(4):6257-6270) 2025.
[41] Yan Sun and Jicong Fan. MMD graph kernel: Effective metric learning for graphs via maximum mean discrepancy. In Proceedings of the International Conference on Learning Representations, 2024.
[42] Maximilien Danisch, Oana Balalau, and Mauro Sozio. Listing k-cliques in sparse real-world graphs. In Proceedings of the World Wide Web Conference on World Wide Web, pages 589-598, 2018.
[43] Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. CoRR, 2020.
[44] William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances neural information processing systems, pages 1024-1034, 2017.
[45] Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In Advances in Neural Information Processing Systems, 2018.
[46] Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Proceedings of the AAAI conference artificial intelligence, pages 1438-4444 2018
[47] Gaspard Michel, Giannis Nikolentzos, Johannes F. Lutzeyer, and Michalis Vazirgiannis. Path neural networks: Expressive and accurate graph neural networks. In Proceedings of the International Conference on Machine Learning, pages 11737-24755, 2023.
[48] Yunchong Song, Siyuan Huang, Xinbing Wang, Chenghu Zhou, and Zhouhan Lin. Graph parsing networks. In Proceedings of the International Conference on Learning Representations, 2024.
[49] Feifei Qian, Lu Bai, Lixin Cui, Ming Li, Ziyu Lyu, Hangyuan Du, and Edwin R. Hancock. DHAKR: learning deep hierarchical attention based kernelized representations for graph classi- fication. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 19995-20003, 2025.
[50] Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. In Proceedings of the International Conference Learning Representations, 2020.
[51] Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna:
A next-generation hyperparameter optimization framework. In Proceedings of the International Conference on Knowledge Discovery & Data Mining, pages 2623-2631. 2019.
[52] Giannis Siglidis, Giamnis 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-5, 2020.
13

---

A Proof of the Statements in Section 3.2
A.1 Derivation of Eq.
Given two shortest path कं [V1, v2..... 1++1] and oं. = 104, sq....., o/-11- As mentioned in ...,,
preliminary work, we have a(ι)) = concat (a(vi). (V,)), ((v++)) From Eq. 2 we know
|+|+1
kpath (T,, x²) =
Σ (a a
(14)
==1
Now we have
kipth (T,, x²) a())))
(15)
By substituting into Eq.
(
we can get
Kag GG, G. Σ Σ E
(a(T),
(ESPP(G)
N'ESP(C)
a(T), E a(T))
(ESP:(()
T'ESP(G")
(16)
Eq. has been derived.
A.2 Proof of Lemma 3.1
Definition A.1. (Positive definite kernel) Let k X be set. hs X x X R is a positive definite Cn. E R
kernel k(x; y) k(y, x) and for any n E N, #1,..., In E X' and .
cech(1n 2 0.
(17)
In Eq. 9 we mentioned that
(G,, Gj) (G.) @ (G,))
Now we zero-extend (G,) and (G,) to a sufficiently large dimension that exceeds the dimen- sion of any possible graph, that is, 2 pead G) (G), 0] e RD, this operation does not change the process of feature mapping. Now we have
Io (G, Gj) = (apad (G:). $ (G)
(18)
First, k(G Gg) is obviously symmetric. Given any N. non-empty of graphs (G1, G....., G and CI,...,,,
Cn E R. We first define the quadratic form:
Geck(G,,
With refernce to Eq.
18 we have:
Gii ( pue)) T paal (Gj))
n
72
Σ C pdd Paa(GG (G,),
Σ
C, $ padt (G,)
jml
Σ pad
(.),
Σ
padl (G,)
(19)
mm
2m
14

---

Table 5: Dataset statistics and properties of TUDatascts.
Dataset
Properties Aug graphs
Avg edges
MUTAG
188
17.93
19.79
NCTI
4110
29.87
32.30
PTC MR
344
14.29
14.60
PROTEINS
1113
39.00
72.82
ENZYMES
600
32.6
62.11
COLLAB
5000
74.49
3457 737.78
IMDE-BINARY
BADDIT-BINARY
2000
429.63
497.75
REDDIT MULTI 5K
6999
508.52
594.87
Let Ei= G (aa) now we have Q = () = ||0|12 Clearly, Q 2 0, therefore k(G,, G₃) positive definite.
A.3 Proof of Lemma
Assume there is a shortest-path of length from vertex U1 to U1+1, denoted as [V1, 22, 2[+1| Then, there exists path length not the shortest-patt paate in graph G, meaning there is shorter shortest-path from to then there must exist a shortest-path from d1 to ut41 with length less than I, which contradicts the assumption. Therefore, Th-1 is the shortest-path of length - from vertex to 2/. The proof for other lengths similar.
from vertex Vi ey, T--1 [U1, ......, 2r). If T
B Dataset statisties.
We evaluated the proposed methods on 12 publicly available graph classification datasets including 4 small molecule datasets: BZR, MUTAG, NCII and PTC_MR, bioinformatics datasets: DD, ENZYMES and PROTEINS, well social network datasets: COLLAB, IMDB-B B, IMDB-M, REDDIT-B, REDDIT-M-5K).
A summary of the 12 datasets is given in Table 5
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our contributions include: (1) We design computationally efficient kernel based on the shortest paths. It can be flexibly integrated with neural networks while preserving both the semantic and structural information of given graph; (2) We develop novel framework termed HSP-GKN which integrates the kernel we proposed with neural networks, enabling objective-driver learning of representations beneficial for specific tasks. These contributions are covered in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss the limitations of our work in terms of applicability on graphs with edge attributes in Section 5
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specifiiattin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
16

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer:
[Yes]
Justification: All proofs are provided in the Appendix.
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proof' can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented
by formal proof's provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide all the details of our method in Section 3 and Section 4. Further- more, we provide the code of our proposed method in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers have some path reproducing verifying the results.
17

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We include the code of our proposed method in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. ec/
sublic/guidess http://guuieee/eeeubibieeeeee
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.co ccpps.cc//pp httpppullllllppiee http://oooeeuuaassssooooooo.11
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The complete hyperparameter configurations can be found in our code.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: To ensure statistical reliability, we provide variance measurements for all reported results. All experimental results were obtained from 10 independent runs with variance calculated.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
18

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide the compute workers in Section 4. Time of execution is also reported in Section 4.2.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer:
[Yes]
Justification:
We conduct the research with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We provide the broader impacts of our work in Section
Guidelines:
The answer NA means that there is no societal impact of the work performed.
19

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work does not pose such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
All datasets, models, and code involved in our paper are open source.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
20

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve participants.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
21

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: This research does not involve LLMs any important, original, or non- standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy hbtp:://horrpss.ccooooorrrrre//p for what should or should not be described.
22


Reviews:
[{"review_id": "AXhkOHL4LK", "reviewer": "Reviewer_y3Cv", "summary": "This paper presents the Hierarchical Shortest-Path Graph Kernel Network (HSP-GKN), which seamlessly combines graph kernel similarity estimation with neural network optimization in an end-to-end fashion. The key idea is that the authors designed the hierarchical feature mapping by degenerating the GH kernel. This feature mapping decreases the computational time and renders its combination with neural networks more straightforward. Based on this kernel, the paper proposes the concept of hidden graph features, which empowers neural networks to capture discriminative representations for downstream tasks. The authors further present comprehensive experimental analyses and results that demonstrate the promising performance of HSP-GKN across diverse benchmarks.", "questions": "1. How does HSP-GKN perform on other large-scale datasets (e.g., OGB)?  \n2. How do the hidden graph features contribute to improved model performance? It seems that it merely transforms the graph into a vector. \n3. HSP only compares paths of the same length. Compared to the SP kernel, does this reduce the expressive power of the kernel?", "limitations": "Yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths \n1. This paper challenges conventional graph kernel methodologies by examining the importance of graph-to-vector conversion from a feature mapping perspective. The proposed approach is simple yet offers meaningful insights.\n2. The concept of HSP-GKN is both novel and well-justified. The authors offer a thorough analysis highlighting the need to unify kernel-based similarity measurement with objective optimization within a single integrated framework.\n3. The graph classification and runtime results of the proposed HSP and HSP-GKN are convincing, demonstrating their strong performance and efficiency. \n\nWeaknesses\n1. A minor shortcoming is the absence of a detailed discussion on how the proposed HSP kernel differs from prior approaches, such as the Core-SP kernel. The authors are encouraged to discuss the difference between the HSP and prior kernel methods.\n2. To reduce computational complexity, HSP restricts the node kernel to a linear kernel. It would be better to discuss the potential drawbacks of this design choice. \n3. It is recommended that the authors provide a more detailed description of the datasets in Appendix B to enhance the clarity and reproducibility of the experiments.\n4. An in-depth analysis of how the learned hidden graph features contribute to the improved model performance gains would strengthen the paper. \n5. In the related work section, the authors should further clarify the differences between the proposed approach and existing GKNNs methods, such as RWNN [1] and KerGNN [2].\n6. The authors should analyze the expressiveness of the HSP kernel since HSP only compares paths of the same length, which can be done in the revision.\n\n[1] Random walk graph neural networks. NeurIPS, 2020.\n\n[2] Kergnns: Interpretable graph neural networks with graph kernels. AAAI, 2022.", "was_revised": true, "final_justification": "I appreciate the authors' thoughtful rebuttal. Their responses have addressed my concerns. Accordingly, I recommend accepting the paper.", "rebuttal": "**Question 1:** Thanks for the comment. We have added OGBG-molhiv and REDDIT-M-12K datasets. The summary of dataset is shown in Table 1. The performance comparison is shown in Table 3,4, the runtime comparison is shown in Table 2. Experimental results show that our method achieves outstanding performance. The results will be added to the revision. \n\n## Table 1 Dataset statistics\n|              | Number of graphs | Avg number of vertices | Avg number of edges |\n| ------------ | :--------------: | :--------------------: | :-----------------: |\n| OGBG-molhiv  |      41127       |         25           |         27          |\n| REDDIT-M-12K |      11929       |        391           |         456         |\n\n## Table 2 Runtime (seconds)\n|              | SP    | CORE-SP | WL-SP | GH   | Ours |\n| ------------ | ----- | ------- | ----- | ---- | ---- |\n| REDDIT-M-12K | 22777 | OOT     | OOT   | OOT  | 6845 |\n\n## Table 3 Performance Comparison\n|  | **SP** |**GraphSAGE** |**DiffPool** |**DGCNN** |**GIN**|**RWNN**|**KerGNN**|**PathNN**|**MMD**|**GPN** |**HSP** |**HSP-GKN** |\n| --- | --- |---|---|---|---|---|---|---|---|---|---|---|\n| **REDDIT-M-12K** | 35.79±1.9 | 43.5 ± 1.0 | 44.4±1.4 | 43.9±1.8 | `46.7±1.6` | 45.2±1.1 |43.8±1.0 |45.9±1.5 |43.1±1.7 |45.7±1.2 |39.2±1.5|**47.8±1.7**|\n\n ## Table 4 Performance Comparison\n|  | **GIN** | **GCN** | **pathNN** |**AgentNet[1]** |**HSP-GKN** |\n| --- | --- | --- | ---|---|---|\n| **OGBG-molhiv** | 75.6±1.4 | 76.0±0.9 | 79.2±1.9 | 78.3±0.7 | **79.7±1.3** |\n\n**Question 2:** Thanks for the comment. The proposed hidden graph features are learned hierarchical representations that jointly capture both structural and attribute information in a unified embedding space. By computing kernel-based similarities between input graphs and a set of trainable anchor graphs across multiple hierarchical levels, HSP-GKN encodes more task-relevant graph semantics in a soft and adaptive manner. Specifically, for each input graph, a similarity vector is constructed by measuring the similarity between its hierarchical features $\\phi_l(G)$ and the learned features of the anchors at each level $l$. Each element of this vector reflects the similarity at a specific level of abstraction. The resulting vector serves as the final graph-level representation for downstream tasks, enabling the model to explicitly preserve and utilize structural and attribute information from multiple levels of hierarchy.\n\n**Question 3:** **Comparison with SP kernel** Thanks for the comment. SP kernel compares each pair of shortest paths of the same and different lengths between two graphs. Consider two shortest paths $\\pi_a$ and $\\pi_b$ with lengths $l$ and $l+1$ respectively. Their overlapping nodes share identical labels, the endpoint label of $\\pi_a$ differ from those of $\\pi_b$. In this case, the SP kernel produces counterintuitively low similarity scores between the paths. Therefore, although the shortest-path kernel allows for comparisons between paths of different lengths, such comparisons often fail to accurately reflect the true similarity between the paths in most cases. Furthermore, by restricting comparisons to paths of equal length, we enable the construction of explicit feature mappings, which significantly reduces the overall time complexity. This also lays the foundation for designing an end-to-end trainable framework.\n\n**Weaknesses 1&5** Thanks for your comment. Existing GKNN methods typically rely on predefined graph kernels and perform downstream optimization based on the resulting similarity measures. However, these approaches generally do not modify the original kernel computation, and their scalability is inherently limited by the chosen kernel. In this paper, we propose a computationally efficient explicit feature mapping that integrates both structural and semantic information, enabling graphs to be mapped into a vector space suitable for neural network processing. We will give more discussion about the differences between the proposed approach and existing GKNNs and kernel methods in the revision.\n\n**Weaknesses 2** Thanks for your comment. Indeed, using a linear kernel makes HSP less flexible. However, restricting the path kernel to a linear kernel brings additional benefits. On the one hand, it significantly reduces the computation time of the kernel. On the other hand, it allows for the construction of explicit feature mapping, making it easier to integrate downstream tasks into an end-to-end framework. Furthermore, with explicit features, an MLP can be used to capture nonlinear relationships. We will discuss this further in the revision.\n\n**Weaknesses 3** **Datasets details** Thanks for your comment. Following your suggestions, we will add more detailed description of the datasets in the final paper. \n\n[1] Agent-based graph neural networks. ICLR, 2023."}, {"review_id": "nylGR1PtgC", "reviewer": "Reviewer_QL9x", "summary": "The authors propose a new method called hierarchical shortest-path graph kernel network. First they propose the hierarchical shortest path kernel, a kernel based on the graphHopper kernel, that can be computed efficiently. They then use the similarity of the resulting feature vectors to a hidden (learnable) graph to learn solving downstream tasks. Experimental results show that the proposed kernel is efficiently computable also in practice and the framework reaches the highest accuracy in almost all cases (and the second-best in the others).", "questions": "**Q1** Why do you not compare to [26] and [27] (references from paper) in the experimental evaluation?\n\n**Q2** Why are there no regression tasks in the experiments?\n\n**Q3** Why are edge labels not considered? And for the experiments: Were the edge labels removed in preprocessing or did some methods use them (or do the datasets not have edge labels)?\n\nIn order to improve the paper, please consider comparing also to the more recent graph kernels mentioned above.", "limitations": "The limitation section is a bit short. Limitations should not only be stated, but also discussed.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I really like the idea and think that combining graph kernels with neural methods is an important research direction. The experimental results are very good; the proposed method improves accuracy on most datasets. However, the datasets used are rather old and outdated. The authors should consider running experiments on more recent datasets. \nFor the graph kernels, there are newer (and/or better) methods available, for example the WLOA [1], WWL [2] or GWL [3] kernel. The proposed method should also be compared to them. \n\n[1] On Valid Optimal Assignment Kernels and Applications to Graph Classification, Kriege et al., 2016\n\n[2] Wasserstein Weisfeiler-Lehman Graph Kernels, Togninalli et al., 2022\n\n[3] A generalized Weisfeiler-Lehman graph kernel, Schulz et al., 2022\n\n\n# Other comments\n\nIt might be a good idea to use a shorter acronym for the method.\n\nThe font size in Figure 1 is too small.\n\nl121 *a* is missing in the definition of G=(V,E)\n\nl137 How is $k_{path}$ defined in the original graphHopper kernel?\n\nFigure 2: Similartiry -> Similarity\n\nl208 . missing\n\nFigure 3: font size is too small.\n\nl294 Please explain what read-word datasets are (or change to real-world if that is just a typo).\n\nl306ff/Figure3: The plots regarding N and n, look the same, so it is not clear how the desscription fits them. Please make all plots have the same axis labels (runtime instead of sqrt of runtime for the one with n), then it can be seen with one glance.\n\nl344 \"Hierarchical\" missing before Shortest-Path\n\nl351 Please rephrase the last sentence.", "was_revised": true, "final_justification": "The authors have addressed my concerns and provided additional results. Having also read the other reviews, I tend more towards acceptance.", "rebuttal": "**Question 1:** Thank you for the suggestion. We have conducted experiments with the suggested method in Table 1 and Table 2, and will include the results in the experiments section in the revised version. Experimental results show that our method achieves outstanding performance, even when compared to more advanced state-of-the-art approaches. We appreciate the insightful comment and believe that including this comparison will further strengthen our experimental analysis.\n\n## Table 1 Performance Comparison\n|          |  MUTAG  |   PTC-MR   |    NCI1    | PROTEINS | IMDB-B |   IMDB-M    |\n| :------: | :--------: | :--------: | :--------: | :---------: | :--------: | :---------: |\n| GNN-LoFI[4] | 86.7±2.0 | 65.7±5.2 | 79.4±0.4 | 75.1±1.0  | 76.5±2.1 | 48.8±1.2  |\n| Baseline[5] | 85.2±2.2 | 60.1±1.9 | 71.5±1.2 | 75.3±1.1  | 69.9±1.4 | 45.6±1.2 |\n| HSP-GKN  |  **97.5±2.2**  | **76.3±3.4** |  **83.6±1.9**  | **79.5±1.7** |     **78.5±2.8**     | **78.5±2.8** |\n\n## Table 2 Newer graph kernels\n|         |  MUTAG  |   PTC-MR   |    NCI1    | PROTEINS |    D&D     |  ENZYMES   |   IMDB-B    |     BZR     |\n| :-----: | :--------: | :---------: | :--------: | :---------: | :--------: | :--------: | :---------: | :---------: |\n|  WL-OA[1]  |  84.5±1.7  |  63.6±1.5   |  **86.1±0.2**  |      76.4±0.4      |  79.2±0.4  |  59.9±1.1  |      72.6±5.5      |      86.5±0.5      |\n|   WWL[2]   | 87.2±1.5 | 66.3±1.2 | 85.7±0.2 | 74.2±0.5  | 79.6±0.5 | 59.1±0.8 | 74.3±0.8 | 84.4±2.0 |\n| R-WL[6] | 89.5±5.3 | 57.0±2.6 | 80.4±0.8 | 75.1±4.5 | OOT | 49.2±5.9 | 71.9±2.4 | 87.8±2.6 |\n| HSP-GKN |  **97.5±2.2**  |      **76.3±3.4**      |  83.6±1.9  | **79.5±1.7** |     **84.2±2.6**     |  **70.4±3.1**  | **78.5±2.8** | **93.4±3.6** |\n\n**Question 2:** Thanks for the comment. Unlike the graph classification task, most widely used datasets in the graph classification task do not have edge attributes. However, in graph regression datasets such as ZINC and QM9, which have discrete or continuous edge attributes. The main reason why there is no regression task is the lack of full utilization of edge information in the graphs. Furthermore, the prediction target in graph regression tasks lies in a continuous space, which may require designing models that are more sensitive to the predicted values. We agree that extending this approach to the regression task is a promising direction, and we plan to explore it in future work. \n\n**Question 3:** Thanks for the comment. Most commonly used graph classification benchmarks do not contain edge attributes, which limits the feasibility of incorporating them into a kernel design that aims to be generally applicable. Among the 12 datasets in this paper, only 2 provide edge attribute information; the other 10 datasets do not include edge attributes. In addition, most existing graph kernels—such as SP, WL-SP, GH, and CORE-SP—are primarily designed to capture structural patterns and generally disregard edge attributes. Therefore, we mainly focus on leveraging node features and graph topology in this work, making it broadly applicable across a wide range of datasets. However, our method can be extended to incorporate edge attributes when available. In future work, we plan to explore variants of the proposed kernel that can explicitly encode edge information for tasks or datasets where edge features play a crucial role.\n\n**Other comments:** We sincerely appreciate your thorough review. 1. There are indeed some typos—for example, “read-word” should be “real-world”. We will check the manuscript’s content, correct errors as per your comments, and carefully double-check the writing. 2. **The definition of $k_{path}$** in the original graphHopper (GH) kernel is the sum of node kernels. The difference is the choice of the node kernel $k_{node}$: while the GH kernel allows for arbitrary kernels, our proposed HSP kernel restricts $k_{node}$ to a linear kernel. This choice enables a fundamentally different and more efficient computation strategy, significantly reducing kernel computation time, as shown in Table 2 of the paper. Furthermore, using a linear kernel allows for an explicit mapping of graphs into a vector space, which serves as the foundation for the subsequent end-to-end HSP-GKN framework. 3. **Figure3** was intended to illustrate that the computation time grows quadratically with the number of nodes in the graph. Following your suggestions, we will make all plots have the same axis labels in the revision.\n\n**Limitations:** Thanks for the comment. Following your suggestions, we will add more discussion about the limitations of the exclusion of edge features in the final paper, including but not limited to how our method can be extended to handle graphs with edge attributes, as well as the importance of edge information in specific domains such as molecular property prediction.\n\n[1] On Valid Optimal Assignment Kernels and Applications to Graph Classification, Kriege et al., 2016\n\n[2] Wasserstein Weisfeiler-Lehman Graph Kernels, Togninalli et al., 2022\n\n[3] A generalized Weisfeiler-Lehman graph kernel, Schulz et al., 2022\n\n[4] Gnn-lofi: a novel graph neural network through localized feature-based histogram intersection. 2024\n\n[5] Graph kernel neural networks. 2024\n\n[6] A generalized Weisfeiler-Lehman graph kernel, Schulz et al., 2022"}, {"review_id": "f10PlWoDSi", "reviewer": "Reviewer_wTHL", "summary": "This paper proposes the Hierarchical Shortest-Path Graph Kernel (HSP) and a corresponding Graph Kernel Network (HSP-GKN) framework, aiming to combine the benefits of graph kernels and neural networks. The HSP kernel encodes graph structure and semantics through shortest-path-based hierarchical feature mappings. HSP-GKN further introduces trainable hidden graph features to produce similarity vectors for downstream learning. The method is theoretically justified and evaluated on 12 graph classification benchmarks, showing favorable performance compared to classical kernels and GNNs.", "questions": "1. The integration of shortest-path kernels and neural networks seems incremental. Can the authors clarify what is technically novel compared to prior works using similar ideas [1]?\n\n2. The method is only tested on small datasets. Can the authors provide results on large-scale benchmarks to support scalability claims?\n\n3. The method does not support edge features. Is it possible to extend HSP-GKN to incorporate edge attributes?\n\n4. Performance trends in Figure 4 are hard to read. Would the authors consider using a heatmap with a color bar to better illustrate sensitivity to L and N?\n\n[1] DHAKR: Learning Deep Hierarchical Attention-Based Kernelized Representations for Graph Classification. AAAI 2025", "limitations": "The limitations section correctly acknowledges the exclusion of edge features. However, implications of this on domains like molecular property prediction are not deeply discussed.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n\n1. This paper studies an important problem of  integrating graph kernels and neural networks.\n\n2. This paper is well organized. The technical details are also easy to follow.\n\nWeaknesses\n1. The novelty of the proposed framework in this paper is incremental. Integrating shortest-path kernels and neural networks hierarchically is not a novel idea, which has been studied in prior works [1].\n\n2. Datasets used in the paper are relatively small. To convincingly demonstrate scalability, it would be valuable to evaluate HSP-GKN on large-scale graph datasets.\n\n3. The method does not support edge attributes, which are vital in many practical graphs (e.g., molecular graphs).\n\n4. In Figure 4, it's difficult to discern the exact performance trends. Using a heatmap with a color bar could improve readability.\n\n[1] DHAKR: Learning Deep Hierarchical Attention-Based Kernelized Representations for Graph Classification. AAAI 2025", "was_revised": true, "final_justification": "The rebuttal clarifies technical differences from prior work and outlines potential extensions. However, the core contribution remains incremental, and the lack of edge attribute support limits practical scope such as molecular property prediction. These concerns are not fully addressed in the current version. I therefore maintain my original scores.", "rebuttal": "**Question 1:** **Technical contribution:** We appreciate the reviewer’s concern regarding the novelty of our approach relative to existing methods such as DHAKR [1]. While both HSP-GKN and DHAKR aim to integrate shortest-path kernels with deep architectures, there are significant differences which we summarize below: **(1) Substructure Encoding: Count-based vs. Similarity-based:** DHAKR encodes substructures by explicitly counting occurrences of patterns (e.g., shortest path length or WL subtrees), resulting in discrete, sparse frequency vectors. Moreover, these counts are based purely on structure and do not incorporate node attributes. This approach inevitably leads to the loss of node semantics, thereby negatively impacting the model's performance. In contrast, HSP-GKN encodes topological information implicitly by introducing hierarchical feature mapping that maps graphs into vector representations. These vector representations are then used to measure similarity with learnable graph anchors. **(2) End-to-End Learning Objective: Attention weighting vs. Representation learning:** DHAKR aims to learn attention weights over predefined substructures, identifying which substructure counts are more relevant to the task. However, this approach inherently relies on a fixed set of symbolic patterns, which may limit its capacity to generalize beyond the predefined structures. In contrast, HSP-GKN is designed to learn hidden graph representations in a kernel-induced space directly. Through hierarchical feature mapping and anchor-based similarity computation, the model learns a task-adaptive, continuous graph embedding that implicitly captures structural and attribute-level semantics, rather than weighting fixed symbolic patterns. This enables more flexible and expressive representations, without being constrained by manually selected substructures. **(3) Computational Complexity:**            Specifically, the computational cost of DHAKR is $\\mathcal{O}(N^2)$ in the number of graphs $N$ and $\\mathcal{O}(n^3)$ in the number of nodes per graph $n$. In contrast, HSP-GKN scales more efficiently with $\\mathcal{O}(N)$ and $\\mathcal{O}(n^2)$, respectively. From a model complexity perspective, HSP-GKN introduces a significantly more compact and scalable framework, DHAKR constructs multiple kernel matrices across layers and aggregates them via attention mechanisms. Therefore, HSP-GKN has fewer parameters than attention-based aggregation in DHAKR, and achieves superior scalability with linear complexity in the number of graphs.\n\nIn summary, HSP-GKN differs from DHAKR in three fundamental ways: it learns similarity-based representations rather than relying on lossy count-based encodings, allowing it to retain both structural and attribute information; it operates in a continuous embedding space instead of weighting fixed symbolic patterns, enabling greater expressiveness and generalization; and it offers improved scalability with lower computational complexity and fewer model parameters. We will add more discussion in the related work in the revision.\n\n**Question 2:** Thanks for the comment. We have added OGBG-molhiv and REDDIT-M-12K datasets. The summary of the dataset is shown in Table 1. The performance comparison is shown in Table 3,4, the runtime comparison is shown in Table 2. The results show that our method consistently outperforms existing approaches across all datasets, demonstrating the effectiveness of our proposed framework against its competitors. The results will be added to the revision. \n\n## Table 1 Dataset statistics\n|              | Number of graphs | Avg number of vertices | Avg number of edges |\n| ------------ | :--------------: | :--------------------: | :-----------------: |\n| OGBG-molhiv  |      41127       |         25           |         27          |\n| REDDIT-M-12K |      11929       |        391           |         456         |\n\n## Table 2 Runtime (seconds)\n|              | SP    | CORE-SP | WL-SP | GH   | Ours |\n| ------------ | ----- | ------- | ----- | ---- | ---- |\n| REDDIT-M-12K | 22777 | OOT     | OOT   | OOT  | 6845 |\n\n## Table 3 Performance Comparison\n|  | **SP** |**GraphSAGE** |**DiffPool** |**DGCNN** |**GIN**|**RWNN**|**KerGNN**|**PathNN**|**MMD**|**GPN** |**HSP** |**HSP-GKN** |\n| --- | --- |---|---|---|---|---|---|---|---|---|---|---|\n| **REDDIT-M-12K** | 35.79±1.9 | 43.5 ± 1.0 | 44.4±1.4 | 43.9±1.8 | `46.7±1.6` | 45.2±1.1 |43.8±1.0 |45.9±1.5 |43.1±1.7 |45.7±1.2 |39.2±1.5|**47.8±1.7**|\n\n ## Table 4 Performance Comparison\n|  | **GIN** | **GCN** | **pathNN** |**AgentNet[2]** |**HSP-GKN** |\n| --- | --- | --- | ---|---|---|\n| **OGBG-molhiv** | 75.6±1.4 | 76.0±0.9 | 79.2±1.9 | 78.3±0.7 | **79.7±1.3** |\n\n**Question 3:** We thank the reviewer for pointing this out. Indeed, the current version of HSP-GKN focuses on node attributes and graph topology. Most commonly used graph classification benchmarks do not contain edge attributes. Among the 12 datasets in this paper, only 2 provide edge attribute information; the other 10 datasets do not include edge attributes. However, the framework is flexible and can be extended to support edge attributes in several ways.\n\nOne possible extension is concatenating the edge attributes along the shortest path with the corresponding node attributes into a unified vector representation. Since the shortest paths are already computed as part of the kernel, this concatenation would introduce minimal additional computational overhead. Alternatively, we can define a separate kernel for edge features to measure the similarity between two shortest paths based on their edge attributes. This edge-based similarity can then be combined with node-based similarity to provide a more comprehensive comparison between shortest paths. We leave this as a promising direction for future work and believe that such an extension can further enhance the model’s expressiveness on attributed graphs with rich edge information.\n\n**Question 4:** Thanks for the comment. Due to the rebuttal policy limits, we are unable to submit figures. Following your suggestions, we will add a heatmap to improve readability in the revised manuscript.\n\n**Limitations:** Thanks for your suggestion about the limitations section. We appreciate the reviewer’s observation that while we have acknowledged the exclusion of edge features, the implications of this limitation on specific domains, such as molecular property prediction, have not been deeply discussed. We agree that this is an important point, as edge features (e.g., bond types or interaction strengths in molecular graphs) can significantly influence model performance in such applications. We will also discuss in the revision how to extend the method to graphs with edge attributes, as discussed in our response to Question 3. We hope this addition provides a clearer understanding of the implications. \n\n[1] DHAKR: Learning Deep Hierarchical Attention-Based Kernelized Representations for Graph Classification. AAAI 2025\n\n[2] Agent-based graph neural networks. ICLR, 2023."}, {"review_id": "cuGMgDMkLx", "reviewer": "Reviewer_3EPr", "summary": "This paper proposes a graph learning framework, HSP-GKN. The framework first introduces a shortest-path-based graph kernel that captures graph structure and semantics via an explicit feature mapping, which aggregates all shortest paths of the same length. Subsequently, the authors embed this HSP kernel into an end-to-end network. The network generates graph embeddings for downstream tasks by computing the similarity between the input graph's HSP features and a set of learnable hidden graph features. This design allows the graph representation to be optimized in a task-driven manner.", "questions": "See above.\n\nAdditionally, I am curious about the performance of HSP-GKN on other tasks, such as graph regression.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. The paper is well-written and clearly structured. The motivation, methodology, and experiments are presented logically. \n\n2. The introduction of learnable hidden graph features that are matched against the graph's HSP features is an interesting design. Introducing flexibility into a traditionally fixed kernel approach.\n\n3. The experimental evaluation is quite thorough, covering 12 public datasets from various domains.\n\n**Weaknesses**\n\n1. The term \"Hierarchical\" may be imprecise. The method groups features by path length rather than constructing a true multi-scale or coarse-to-fine representation.\n\n2. According to my understanding, there should be a missing symbol $l$ in Eq. (1). Additionally, certain equations, such as Eq. (10), would benefit from more detailed explanations to enhance clarity.\n\n3. Loss of structural information. By collapsing all same-length shortest paths into one vector, the model might not distinguish between graphs with different path topologies but similar aggregated node features.\n\n4. In the ablation study, more detailed explanations are needed to clarify the distinctions between HSP-MLP and HSP-GKN. Given their seemingly similar architectures, it would be helpful for the authors to elaborate on the specific design differences and provide insights into why HSP-GKN yields superior performance.", "was_revised": true, "final_justification": "I have checked the comments from the other reviewers and the corresponding replies from the author. Regarding the novelty concern, I believe the major contribution of this paper lies in the computationally efficient shortest-path kernel and the end-to-end optimization framework. I confirm my recommendation to accept the paper.", "rebuttal": "**Weaknesses 1:** We appreciate the reviewer’s insightful comment regarding the use of the term “Hierarchical”. While it is true that our method does not construct a multi-scale or coarse-to-fine representation, we use the term to emphasize the multi-level structural abstraction captured by varying shortest-path lengths. Each path length corresponds to a distinct level of structural granularity: short paths capture local neighborhood patterns, whereas longer paths reflect broader graph topology. We acknowledge that “multi-level” or “multi-scale path-based representation” might be alternative terms, and we are open to refining the terminology in the revised version to improve clarity.\n\n**Weaknesses 2:** Thanks for the comment. We will check the manuscript’s content, correct errors as per your comments, and carefully double-check the writing. The expression in Eq. (10) defines the set of hidden graph features as a collection of learnable, hierarchical representations. Specifically, $\\phi_{l}^{(i)}(\\mathcal{G})$ denotes the $i$-th feature corresponding to paths of length $l$, and $n_l$ indicates the number of such features at level $l$. These features capture structural patterns at different levels of granularity, enabling the model to learn multi-scale representations of the graph. \n\n**Weaknesses 3:** We thank the reviewer for pointing out the concern regarding potential loss of structural information when aggregating same-length paths. We would like to clarify that our similarity vector construction is fundamentally different from naive feature collapsing. While typical GNN pooling compresses node representations using operations such as max or mean—often at the risk of discarding fine-grained structural distinctions—our method explicitly preserves multi-level structural information by aggregating node features within shortest paths of each specific length. These aggregated features are then compared with trainable anchors to form a similarity vector, where each dimension corresponds to a distinct level of structural abstraction. This design allows the model to retain path-level topological characteristics, offering a more structured and semantically aligned representation than standard pooling techniques.\n\n\n**Weaknesses 4:** Thanks for the comment. For HSP-MLP, let $\\Phi(G)$ denote the vectorial representation of a graph, defined as $\\Phi(G) = $CONCAT$(\\phi_1(G), \\ldots, \\phi_L(G))$. This representation is directly fed into an MLP for training. However, the hierarchical characteristics of the graph are not explicitly considered in this process. In contrast, HSP-GKN computes a similarity vector by measuring the similarity between the learnable anchor features and the hierarchical features $\\phi_l(G)$ of a given graph. In this case, each element of the similarity vector corresponds to a different level of hierarchy. This vector is then used as the input to the MLP for downstream training.\n\n**Other comment:** **Other tasks** Thanks for the comment. Unlike the graph classification task, most widely used datasets in the graph classification task do not have edge attributes. However, in graph regression datasets such as ZINC and QM9, which have discrete or continuous edge attributes. The main reason why there is no regression task is the lack of full utilization of edge information in the graphs. Furthermore, the prediction target in graph regression tasks lies in a continuous space, which may require designing models that are more sensitive to the predicted values. We agree that extending this approach to the regression task is a promising direction, and we plan to explore it in future work."}]

Author rebuttal:

Meta-review: The paper introduces a novel Graph Kernel, the Hierarchical Shortest-Path Graph Kernel, designed to be used as a convolutional layer within a graph neural network in an end-to-end optimization framework. Building on prior work on kernelized GNNs, the main contribution lies in a computationally efficient shortest-path kernel that allows for practical scalability. The experimental evaluation demonstrates strong performance and runtime improvements across a range of benchmarks.

One reviewer raised concerns about the contribution being incremental and about the lack of edge attribute support, which could limit applicability in certain domains. However, the authors pointed out that this limitation is common to many kernel-based methods, which still offer an alternative and interesting perspective on graph convolutions. Furthermore, the introduction of a differentiable and efficient kernel, combined with favorable empirical results, represents a meaningful advance in this line of research. Most reviewers acknowledged the novelty and technical soundness of the approach and considered it a valuable contribution.
Decision: Accept (spotlight)