Generalizing Weisfeiler-Lehman Kernels to Subgraphs
Authors: Dongkwan Kim
Alice Oh
Venue: ICLR 2025 Poster (2025)
Keywords: Graph Neural Networks
Graph Kernels
Subgraphs
Primary area: learning on graphs and other geometries & topologies
TL;DR: We propose WLKS that extends the WL graph kernel to subgraphs, captures high-order structural similarities in k-hop neighborhoods, efficiently outperforming state-of-the-art GNNs.

Abstract: Subgraph representation learning has been effective in solving various real-world problems. However, current graph neural networks (GNNs) produce suboptimal results for subgraph-level tasks due to their inability to capture complex interactions within and between subgraphs. To provide a more expressive and efficient alternative, we propose WLKS, a Weisfeiler-Lehman (WL) kernel generalized for subgraphs by applying the WL algorithm on induced $k$-hop neighborhoods. We combine kernels across different $k$-hop levels to capture richer structural information that is not fully encoded in existing models. Our approach can balance expressiveness and efficiency by eliminating the need for neighborhood sampling. In experiments on eight real-world and synthetic benchmarks, WLKS significantly outperforms leading approaches on five datasets while reducing training time, ranging from 0.01x to 0.25x compared to the state-of-the-art.

Published as a conference paper at ICLR 2025
GENERALIZING WEISFEILER-LEMMAN KERNELS TO SUBGRAPHS
Dongkwan Kim & Alice Oh KAIST, Republic of Korea dongkwan. cim@kaist.as
ABSTRACT
Subgraph representation learning has been effective in solving various real-world problems. However, current graph neural networks (GNNs) produce suboptimal results for subgraph-level tasks due to their inability to capture complex interac- tions within and between subgraphs. To provide a more expressive and efficient alternative, we propose WLKS, a Weisfeiler-Lehmal (WL) kernel generalized for subgraphs by applying the WL algorithm on induced k-hop neighborhoods. We combine kernels across different k-hop levels to capture richer structural infor- mation that is not fully encoded in existing models. Our approach can balance expressiveness and efficiency by eliminating the need for neighborhood sampling. In experiments on eight real-world and synthetic benchmarks, WLKS signifi- cantly outperforms leading approaches on five datasets while reducing training time, ranging from 0.01x to 0.25x compared to the state-of-the-art
INTRODUCTION
Subgraph representation learning has effectively tackled various real-world problems (Bordes et al, 2014 Luo 2022 Hamidi Rad al. 2022 Maheshwari et al. 2024). However, existing graph neural networks (GNNs) still produce suboptimal representations for subgraph-level tasks since they fail to capture arbitrary interactions between and within subgraph structures. These GNNs cannot cap- ture high-order interactions beyond and even in their receptive fields. Thus, state-of-the-art models for subgraphs have to employ hand-crafted channels (Alsentzer et al.) 2020), node labeling (Wang & Zhang 2022), and structure approximations (Kim & Oh 2024) to encode subgraphs' complex internal and border structures.
As elegant and efficient alternative, we generalize graph kernels to subgraphs, which measure the structural similarity between pairs of graphs. We propose WLKS, the Weisfeiler-Lehman (WL) Kernel for Subgraphs based on WL graph kemnel (Shervashidze & Borgwardt (209)). Specifically, we apply the WL. algorithm (Leman & Weisfeiler) 1968) on induced k-hop subgraphs around the target subgraph for all possible ks. The WL. algorithm's output (i.e., the color histogram) for each k encodes structures in the receptive field of the k-layer GNNs; thus, the corresponding kernel matrix can represent the similarity of k-hop subgraph pairs. classifier using this kernel can be trained without GPUs in computationally efficient way compared to deep GNNs.
To enhance the expressive power, we linearly combine kernel matrices of different k-hops. The motivation is that simply using larger hops for WL histograms does not necessarily lead to more expressive representations. We theoretically demonstrate that WL histograms of the (k + 1)p are not strictly more expressive than those of k--hop in distinguishing isomorphic structures, while (I: + hop structures include entire k-hop structures. Therefore, combining kernel matrices across multiple k-hop levels can capture richer structural information around subgraphs.
However, sampling k-hop subgraphs can increase the time and space complexity, as the number of nodes in the k-hop neighborhoods grows exponentially (Hamilton et al.) 2017). To mitigate this issue, we choose only two values of k: 0 and the diameter D of the global graph. No neighborhood sampling is required for the case where to the diameter D, the expanded subgraph encompasses the entire global graph, making the k-hop neighborhood identical for all subgraphs. Consequently, there is no need for explicit neighhorhood
since it only uses the internal structure. When &: is set

---

Published as a conference paper at ICLR 2025
sampling in this case; only perform the WL algorithm the global graph once. This approach balances expressiveness and efficiency, providing a practical solution for subgraph-level tasks.
We evaluate WLKS's classification performance and efficiency with four real-world and four syn- thetic benchmarks (Alsentzer et al. 2020). Our model outperforms the best-performed methods across five of the eight datasets. Remarkably, this performance is achieved with x0.01 to x0.53 training time compared to the state-of-the models. Moreover, unlike existing models, WLKS does require pre-computation, pre-training embeddings, utilizing GPUs, and searching large hyperparameter space.
The main contributions of our paper are summarized follows. First, propose WLKS, a gen- cralization of graph kemnlss to subgraphs. Second, we theoretically show that combining WLKS matrices from multiple k-hop neighborhoods can increase the expressiveness. Third, we evaluate our method on real-world and synthetic benchmarks and demonstrate superior performance in significantly efficient way. We make our code available for future research
2 RELATED WORK
WLKS is a 'graph kerne'' method designed for 'subgraph representation learning.' This section explains both of these areas and their relationship to our model.
Subgraph Representation Learning Subgraph representation learning can address various real-
world challenges by capturing higher-order interactions that nodes, edges, or entire graphs cannot model. For example, subgraphs can formulate discases and patients in gene networks (Luo 2022).
teams in collaboration networks (Hamidi Rad et al. 2022), and communities in mobile game user networks (Zhang al., 2023). Existing methods are often domain-specific (Zhang al. 2023 Li
ct al. 2023; Trümper et al. 2023: Ouyang et al. 20244 Maheshwari et al. 2024) or rely on strong
assumptions about the subgraph (Meng et al. [0188] Hamidi Rad et al. 2022 Kim al. 2022 Luo
2022
Liu el. 2023), limiting their generalizabilitg
Recent deep graph neural networks designed for subgraph-level tasks apply any subgraph type without specific assumptions. However, they often generate suboptimal representations due to their inability to capture arbitrary interactions between and within subgraph structures. They strug- gle to account for high-order interactions beyond their limited receptive fields; thus, they should incorporate additional techniques including hand-crafted channels (Alsentzer et al., (2020), node labeling (Wang& & Zhang 2022), random-walk sampling (Jacob et al. (023), and structural approx- imations (Kim Ohl 2024). In contrast, we design kernels that can capture local and global inter- actions of subgraphs, respectively, to enable simple but strong subgraph prediction. We formally compare our proposed WLKS with representative prior models in Appendix
Graph Kernels Graph kernels are algorithms to measure the similarity between graphs to enable the kernel methods, such as Support Vector Machines (SVMs) to graph-structured data (Vishwanathan et al.) 2010). Early examples measure the graph similarity based on random walks (Kashima et al.) 2003) or shorted paths (Borgwardt & Kriegel| (2005). One of the most in- fluential graph kernels is the Seasfeiler-ehhmar (WL) kernel (Shervashidze & Borgwardt 2009), which leverages the WL isomorphism test to refine node labels iteratively, improving the expres- siveness of the graph structure comparison. While the WL test is designed for graph isomorphism, WI. kernels capture structural similarities using the WI. test's outcomes even when graphs are not strictly isomorphic (See Appendix B for detailed comparison). Kernels for graph-level prediction by counting, matching, and embedding subgraphs have been deeply explored (Shervashidze et al.) 2009 Kriege & Mutzel [012]] Yanardag & Vishwanathan 2015 Narayanan et al. 2016). However, there has been no research on kernels to solve subgraph-level tasks by computing the similarity of subgraphs and their surroundings. To the best of our knowledge, our paper is the first investigate this approach.
2

---

Published as a conference paper at ICLR 2025
3 WL GRAPH KERNELS FOR SUBGRAPH-LEVEL TASKS
This section introduces WLKS, the WL graph kernels generalized for subgraphs. We first describe the original WL algorithm and its extension for subgraphs, which is a foundation of WLKS. Then, suggest WLKS and its enhancement of expressiveness and efficiency. Finally, we introduce how to integrate continuous features with WLKS models.
3.1 SUBGRAPII REPRESENTATION LEARNING
We first formalize subgraph representation learning as classification task. Let (V, represent global graph, where V denotes a of nodes (with |V| = N) and A C V represents set of edges (with | = E). A subgraph S = (Vrub, A.ub) is graph formed by subsets of nodes and edges Es There exists set of M subgraphs, S. In a subgraph classification task, the model learns
in the global graph G (with | N and | |A with M < N, denoted as (S1, representation h, IR and the logit vector yı E RC for S; where F and C the dimension size and the number of classes, respectively.
3.2 1-WL ALGORITIM FOR --HOP SUBGRAPHS
1-WL for Graphs We briefly introduce the I-dimensional Weisfeiler-Lemman (1-WL) algorithm. As illustrated in Algorithm [ the 1-WL is iterative node-color refinement by updating node colors based on a multiset of neighboring node colors. This process produces a histogram refined coloring that captures graph structure, which can distinguish non-isomorphic graphs in the WI. isomorphism test.
Algorithm 1: 1-WL Algorithm
Input: Graph G (V,A) A) and T'' iterations
Output: Refined node coloring (cT ......, .Ty) for nodes in V after T iterations
Initialize cQ for all v for i + 1 to T do
for node u E V do
M, multiset of labels {ct-1 u E (()))
concatenate et- and sorted M.
end
Use a bijective function to map each unique o to new color dt
end
return
(of Tv)
1-WL for Subgraphs (WLS) We then propose the WLS, the 1-WL algorithm generalized for subgraphs. Since surrounding structures are the core difference between graphs and subgraphs, the main contribution of the WLS lies in encoding the k-hop neighborhoods of the subgraph. Here, will be denoted in superscript as WLS* if specific & is given.
Formally, for a subgraph the refined colors of nodes in Vrsub, where each color represents a unique subtree in k-hop neigh- borhoods. As the Algorithm 2 we first extract the k-hop subgraph S of S, which contains all nodes in S as well any nodes in G that are reachable from the nodes in S within & hops. The 1-WL algorithm is then run on this induced k-hop subgraph to generate the colors of the nodes in Sk The WLS returns the node coloring belonging to the original S, not in Sk In general, k- k-hop neighborhoods are much larger than the original subgraph, so using all the colors in S will likely produce coloring irreverent to the target subgraph.
(37sub A.bb) in a global graph g = (V, the WLS*'s goal is to get

---

Published as a conference paper at ICLR 2025
k=1
k=2
X
k=1
Color
k=0
Histogram
Figure I: An example of WLS* algorithm (Algorithm 2 for & E 20) Left: A subgraph (red
shade) and k-hop neighborhoods (dashed lines). Right: The outputs of WLS* algorithm as colors and histograms for the left subgraph. We visualize each iteration of the algorithm in Appendix C
The WLKS kernel matrix for each is constructed by an inner product of histogram pairs.
Algorithm 2: V Algorithm: 1-WL for subgraphs with their k-hop neighborhoods
Input: A subgraph S (Yyuu Auu),, global graph G (V, A). and I' iterations
Output: Refined node coloring (cT ci .... (yas) for nodes in 1/suh after iterations
Sample 5 = (z/bb, , A.ub.)), which is the induced k-hop subgraph of g around all nodes in S reachable within & hops
Run 1-WL (Algorithm on (S* to get node colors in Vsab,
return (cT, yy yob Note that this coloring is about nodes in S, not S
After WS color refinement, we can get a feature vector (or color histogram) Ø #colors which is the aggregation of the refined colors in S. Each element <5(c) is the number of occurrences of the color in the output of WLS* We illustrate example of subgraph and its WLs* outputs for different ks in Figure
WL Kernels for Subgraphs (WLKS) Now, we suggest WLKS, the corresponding kernel matrix WLs E IR M xM of which is defined as the number of common subtree patterns of two subgraphs in their h-hop neighborhoods. That is, each element can formulated as an inner product of pair of d: This WLKS is a valid kernel since K is positive semi-definite for all non-negative ks, as Ris
demonstrated in Proposition 3.1
Proposition 3.1. vk 2 0, WLS is positive semi-definite (p.s.d.).
Proof. Each element in Kits is defined as an inner product of two feature vectors Φ. This leads M E/ (o Φb) I c Ene (/ D 12 > 0 for any real c. Thus,
K is positive semi-definite.
3.3 EXPRESSIVENESS DIFFERENCE OF THE WLS BETWEEN & AND + 1
How do we choose k? Intuitively, selecting one large k seems reasonable since the k-hop neighbor- hoods include the k k'hhop structures of all smaller k's. Against this intuition, we present theoretical analysis that the WLS*+1 histogram is not strictly more expressive than the WLs* histogram.
In Proposition 3.2 we show that con-equivalent colorings of two subgraphs in WLS*+1 do not guar- antee non-equivalent colorings in W This is also true for the inverse: equivalent colorings in WLs*+1 do not guarantee equivalent colorings in * We obtain the same conclusion as Proposi- tion 3.2 for GNNs powerful as the WL test (e.g., Wang & Zhang 2022 ) and some recent models
are based on even less powerful GNNs than the WL test (e.g., Kim & Oh (2024)..
Proposition 3.2. Given two subgraphs S and S₂ of global graph & and T iterations,
* ++1 (Si) # WLS (S2) # WLS* (S,) * WLS (S2),
(1)
WLS 6++1 (S1) = WLS +++ (S2) # WLS (St) WLS* (S2).
(2)
for any where WLs* (S) := WLs* (S, T) and '=' denotes the equivalence of colorings.
Proof. We will prove both statements by contradiction.
4

---

Published as a conference paper at ICLR 2025
Two Subgraphs in a Graph
k=0
k=1
0:1
Figure 2: Example pairs of subgraphs that WLS produces equivalent colorings while WLS*+1 does not, and vice versa (where k = 0). The gray area represents the subgraph.
Proof of Equation 1 For the sake of contradiction, assume that whenever (LS*+1(Ss)) 전 WLs*+1(S, (S2). must follow that (SI) # NLS*(Ss), Consider two subgraphs Si and S2 of global graph such that their k-hop neighborhoods
isomorphic, i.e., St = St. but their (A: + 1J-hop neighborhoods have non-identical subtree patterns height-T rooted at sub- graphs. That is, within the k-hop radius, S and S2 have identical structures, but beyond that, their structures are distinguishable by the 1-WI. algorithm (i.e., distinct colorings). This implies that WLS* (Si) WLS* but WLS*+1 (Si) # WLS*+1(S) (S2) (e.g., the top part in Figure 2 This contradicts assumption that W (S,) W (S2) implies WLS"(() * WLS (S2).
Proof of Equation 2 For the sake of contradiction, assume that whenever WLS*+1(S)) =
W (S2), it must follow that WLS*(s)
WLS (S2). Let G be a global graph, and consider its two subgraphs S₁ and S2. Suppose that in G. (k: + 1)-hop neighborhoods of S and S2 are iden- = (Ss)+ However, within the k-hop neighborhoods, the local structures can differ such that the rooted subtree patterns of S and S2 up height T i not identical, WLS" (S,) & WLS* (S²) (e.g., the bottom part in Figure 2 This contradicts our assumption that
tical, WLS*+1(C
WLs*+1 (S)) = WLS * (S2) implies WLS* (L))(S)) = WLS* (S2).
Proposition 3.2 demonstrates that WLS* cannot represent all the structural information of smaller k k'hopp structure (K'' < k) from the perspective of graph isomorphism. This limitation suggests that relying solely on a single for WLS may insufficient for encoding comprehensive information from various levels of structures. To address this, propose combining WLS* for multiple values of k, allowing the representation to capture both local and global structures effectively. Building on this insight, we design WLKS-K, mixture of WLKS for multiple hops k IK where its kernel matrix K K is a linear combination of K WLs.
K TaaKK=EAER ag K where d&k E RR+
(3)
Note that WLKS-K be defined even when only k is used (e.g., (0) og K-0 WLS for (LKs-(O)) WLKS-K is a valid kernel since a positive linear combination of p.s.d. kernels is
p.s.d. (Shervashidze al. 201T).
3.4 SELECTING FOR MINIMAL COMPLEXITY
In WLKS, selecting appropriate values of &s during the k-hop subgraph sampling is crucial for bal- ancing expressive power and complexity. As the number of nodes in the k-hop neighborhood grows exponentially with increasing k (Hamilton et al., 2017).. an unbounded increase in is can result in substantial computation and memory overhead. To mitigate this, we strategically limit the choice of to two specific values:
a
and D, where D is the diameter of the global graph G.
When h: 0, the WLKS consumes the least computation and memory by using only the internal structure of the subgraph without neighborhood sampling. In contrast, when is set to diameter D, every subgraph has the same k-hop neighborhood, which is the global graph G: thus, the WLS is performed just once on G without per-subgraph computations. By using 0 and D, WLKS- D} capture both the local and the largest global structure of subgraphs. This approach offers practical model that balances expressive power and efficiency, avoiding excessive computation and memory consumption from intermediate h values.
5

---

Published as a conference paper at ICLR 2025
3.5 COMPUTATIONAL COMPLEXITY
The original WL Kernel has computational complexity of O ETE, E, Eith + MTE, Nyahh for M subgraphs. T iterations, and the number of nodes N and edges Lith of the subgraph (Sher- vashidze & Borgwardt 2009). When is O, set of subgraphs identical to set of individ- ual graphs, its complexity is the same the original's. When & is D, after performing the WL algorithm on the global graph once (i.e., O(TE)), the coloring of each subgraph is aggre- gated histogram (i.e., O N.ub)). Thus, the computational complexity of WLKS-(O, D} is O (T E; Figuu) MT) Σ; Nrub).
We note that WLKS-10, (0, D} do not perform k-hop neighborhood sampling, which adds complexity of O ((Nuub. + Ezub,,) per subgraph from a breadth-first search from Yuuu Learning SVM with pre- computed kernels has complexity of ((M2) dependent the number of subgraphs M, but this step is typically secondary to the WLS in practice.
4 INCORPORATING CONTINUOUS FEATURES FOR WLKS
WLKS designed capture structural information but can be simply integrated with continuous features. This section introduces four methods to incorporate continuous features for WLKS.
4.1 COMBINATION WITH KERNELS ON CONTINUOUS FEATURES
WLKS can be linearly combined with kernel matrices Kx derived from continuous features as in Equation 4 This combination enables the model to account for structure and feature similarities between subgraphs. One straightforward way is to directly compute a kernel on features, which mea- sures the similarity between subgraphs based on their feature vectors. Another approach involves applying the Continuous Weisfeiler- Lehman operator (Togninalli al. 2019) to features, generating a kernel matrix. This operator extends the original WL framework to continuously attributed graphs.
Orstructure KuLS-KK Oeeeuuure
Kx where R
In both cases, the kernel matrix from continuous features tends be denser and has different scale compared to those from the WL histogram. To address this, we standardize the features before creating kernels and use the RBF and linear kernels.
4.2 GNNS WITH THE WLKS KERNEL MATRIX AS ADIACENCY MATRIX
Another way to integrate features with WLKS is to use the kernel matrix as an adjacency matrix. Specifically, consider the WLKS kernel matrix KILS the adjacency matrix of weighted graph where subgraphs S serve as nodes. The rationale for this approach is that a kernel represents the similarity between data points.
In this graph, the edge weight between subgraphs and j corresponds to ji] By applying deep GNNs this graph, we can leverage the expressive power of WILKS for structural information and the capabilities of GNNs for feature representation. For this paper, we adopt state-of-the-art GNN-based models, S2N+0 and S2N+A (Kim & Oh 2024), for the graph created by WLKKS-(0, D} as instantiation of this approach.
Given the original feature X E Nx features S2N+0, the hidden feature E RM features is sum of original features in the subgraph, and then GNN on K E RRM is applied to get the logit matrix Y E M x# classss for the prediction. S2N+A first encodes each subgraph as an individual graph with GNN, readout its output get the hidden feature H, then the other GNN on KALS is applied for the prediction. Formally,
WLKS for S2N+0:
H [i, :] = J X (aruh :], Y = GNN(H. H, KuLS).
(5)
WLKS for S2N+A:
H [ Nun GNN, X [Vuub :], A.uu). Y = GNN2(H, Kuts),
(6)
where 1, E gnx1 a vector of ones. Since the kernel matrix dense for GPUs, we sparsify and normalize it using the same method in the S2N's paper.

---

Published as a conference paper at ICLR 2025
Table Statistics of real-world and synthetic datasets.
PPI-PP
HPO-Nauro
HPO-Metab
EM-User
Density
Cut-Ratio
Coreness
Component
nodes in G
17,080
14,587
14,587
57,333
5,000
5,000
5,000
19,555
# edges in 9
316,951
3,238,174
3,238,174
4,573,417
29,521
83,969
118,785
43,701
subgraphs (S)
1,591
2,400
4,000
324
250
250
221
250
nodes S
10.2
14.4
14. 14.8
155.4
20.0
20.0g0.o
20.0go.0
74.2
# components/ / S
7.0
1.610.7
1.5
15.1
3.8
1.0gu.o
1,0go.
4,9
Density (9)
0.0022
0.0304
0.0304
0.0028
0.0024
0.0067
0.0095
0.0002
Avg. density (S)
0.216
0.757
0.767
0.010
0.232
0.945
0.219
0.150
classes
10
2
3
3
3
Lahels
Single
Multi
Single
Single
Single
Single
Single
Single
Datuset splits
80/10/10
80/10/10
80/10/10
70/15/15
80/10/10
80/10/10
80/10/10
80/10/10
EXPERIMENTS
This section outlines the experimental setup. covering the datasets, training details, and baselines.
Datasets We employ four real-world datasets (PPI-BP, HPO-Neuro, HPO-Metab, and EM-User) and four synthetic datasets (Density, Cut-Ratio, Coreness, and Component) introduced by Alsentzer et al. 2020 Given the global graph G and subgraphs S, the goal of the real-world benchmark is subgraph classification on various domains: (HPO-Neuro and HPO-Metab), and social networks (EM-User). For synthetic benchmarks, the goal is to determine the structural properties (density, cut ratio, the average core number, and the number of components) formulated as a classification. Note that WLKS does not need pretrained embeddings. We summarize dataset statistics in Table [
interactions (PPI-BP), medical knowledge graphs
Models We experiment with five WLKS-K where is (0), (1), (2), (D), (0. D). Coefficients a set to when one is selected, and tap for WLKS- D). We do grid search of five hy- perparameters: the number of iterations 2,1,2, 3, 4, 5))) whether to combine kernels of all iterations, whether normalize histograms, 1.2 regularization ((23) /100/10020200 22/100, ..., 2,,24 10-2/111000 /100))) and the coeffi cient ao ((0.999, 0.99, 0.9, 0.5, 0.1, 0.01, 0.001)). When combining with kernels on continuous fea- tures (Equation we tune O'feature from the space of {0.0001, 0.001, 0.01, 0.05, 0.1, 0.1,, 0.2, 0.25) 1/(1 + Of For fusing WLKS-(O, D} to S2N, we follow the GCNII- based (Chen al. 2020) architecture and settings presented in Kim & Oh 2024).
and set Ostrrucuure
Baselines We use state-of-the-art GNN-based models for subgraph classification tasks base- lines: Subgraph Neural Network (SubGNN; Alssntzer et al.] 2020). GNN with LAbeling trickS for Subgraph (GLASS; WWan & Zhang] 2022). Variational Subgraph Autoencoder (VSubGAE: Liu
ct al. 2023), Stochastic Subgraph Neighborhood Pooling (SSNP; Jacob et al.) 2023) and Subgraph-
To-Node Translation (S2N: Kim & Oh 2024). Baseline results are taken from the corresponding
research papers.
Efficiency Measurement When measuring the complete training time, we run models of the best hyperparameters from each model's original code, including batch sizes and total epochs, using Intel(() Xeon(R) CPU E5-2640 v4 and a single GeForce GTX 1080 (for deep GNNs).
Implementation All models are implemented with PyTorch (Paskee al. 2019 and Py PyTorch Geometric (Fey & Lenssen (019). We use the implementation of Support Vector Machines (SVMs) in Scikit-lear (Pedregosa et al. 2011).
RESULTS AND DISCUSSIONS
In this section, we compare the classification performance and efficiency of WLKS and baselines. In addition, the performance of WLKS according to K is demonstrated to exhibit the usefulness of the kernel combination. Finally, we investigate how integrating structures and features across subgraph datasets affects downstream performance.
7

---

Published as a conference paper at ICLR 2025
Table Mean performance in micro Fi-score on real-world and synthetic datasets over 10 runs. A subscript indicates the standard deviation. The higher the performance, the darker the blue color. The results of baselines are reprinted from respective papers.
Model
PPI-BP
HPO-Neuro
HPO-Metal
RM-User
Density
Cut Ratio
Coreness
Component
SubGNN
59.9
63.2
33.7
81.4
91.9
62.9
65.9
95.8
GLASS
61.9.0.7
08.510.s
61.4
88.8 88.8
93.0
93.5
84.0
100.0
VSabGAR
65.2
56.320.9
85.0=3.5
SSNP-NN
63 03.6
68, 08.240..
58.7+1.0
88, 8go.5
S2N+0
63.5 63.5+2.4
66.4+1.1
6+1.7
86, 86.52332
67.2=2.4
56. 56.0ga.o
57 37.094..
100. ==no
S2N+A ocNn
63.7
68.411.0
63 12.7
19.0
93.2
56.010.0
85.7
100.0.o.
WLKS- D)
64.8 64.8+0.0
65.3+a.0
37.9+0.0
91. 91.8ga.0
96. 96.0=u.0
60.0
91.3+0.0
100.0=m.o
Table 3: Runtime in seconds of our model and baselines for the entire training stage and 1 1-epoch inference (validation set) for real-world datasets.
Stage
Entire Training
Inference epoch)
Model
PPI-BP
HPO-Neuro
HPO-Metab
EM-User
PPI-BP
HPO-Neuro
HPO-Metab
EM-User
SubGNN
N/A
1798.2
1082.1
108.1
N/A
432.9
257.1
35.8
GLASS
1009.6
2462.6
1397.0
4597.4
8.2
27.0
26.4
39.0
S2N+0
16.7
36.7
37.1
31.0
9.9
9.3
8.3
14.6
S2N+A GCNU
14.9
78.0
72.2
39.0
8.4
11.1
9.6
13.4
WI.KS-(O,D)
3.5
25.2
10.9
11.7
2.7
1.8
Performance and Efficiency In Table 2 the classification performance of WIKSS (O, D} and baselines on eight datasets is summarized. Our results show that our model outperforms the best- performing bascline in five out of eight datasets. Specifically, WLKS-(0, D} achieves the highest micro F1- Fi-score on PPI-BP, EM-User, Density, Coreness, and Component. For HPO-Neuro, HPO-Metab, model shows similar performance to SubGNN but relatively lower performance
and Cut-Ratio, than the state-of-the ofatt--r--r--t model.
In terms of efficiency, present the training and inference time of our model and four representative baselines on real-world datasets in Table 3 Specifically, we measure the runtime for the entire training stage (including data and model loading, training steps, validation steps, and logging) and I-epoch inference on the validation set. Note that an experiment on PPI-BP with SubGNN cannot be conducted since takes more than 48 hours in pre-computation. WLKS-(0, D) demonstrates significantly faster training and inference times across all real- woald datasets compared to other models (e.g., the shorter training time of x0.01 x0.25 and inference time of x0.12 x0.43). This metric does not include the pre-computation or embedding pretraining required in baselines, so the actual training of WLKS more efficient. Additionally, WLKS does not require a GPU in training and inference, unlike other GNN baselines.
Our results highlight the balance between efficiency and representation quality of WL histograms. Despite the loss of structural information from algorithmic simplicity, the empirical evidence under- scores the task-relevant nature the retained information in WLKS-(0, D}. This reflected the superior performance of WLKS- (0, D} with significantly smaller computational requirements five out of eight datasets. However, the WL histogram lacks expressiveness in some subgraph tasks. In these cases, the expressiveness tricks) (Zhang & Chen 2018 Li et al. 2020 /Zhag et al. 2021 Dwivedi et al. (002).. For example, on the Cut-Ratio dataset, where the performance of WLKS low compared the state-of-the-art, a linear combination with the inner product kernel of Random Walk Structural Encoding (Dwivedi al. 2022) significantly improves the performance from 60.0 to 96.0. However, this improvement not observed on other datasets. Detailed discussions are in Appendix D
be enhanced by using the structural encoding (or labeling
Performance of WLKS-K by K We highlight the importance of selecting the appropriate in Table 4 Specifically, the performance of WLKS-K varies significantly depending on the choice of K. WLKS-((0, D), which combines kernels of 0 and D, consistently delivers strong results across datasets. WILKS-()) and WIKS-(D) perform well independently in certain datasets, but their com-
8

---

Published as a conference paper at ICLR 2025
Table Mean performance WLKS-K in miero Fl-score by K: (0). {1}. (2), {D), and {0, D). The standard deviations are omitted (all 0). The higher the performance, the darker the blue color.
Model
PPI-PP
HPO-Neuro
HPO Metab
EM User
Density
Cut-Ratio
Coreness
Component
WLKS-(O. (0.
64.8
65.3
57.9
91.8
96.0
60.0
91.3
100.0
WLKS-(00)
34.0
31.4
26.4
67.3
96.0
36.0
87.0
100.0
WLKS--11]
39.0
OOM
OOM
79.6
68.0
56.0
39.1
100.0
(LKS-(2)
64.2
OOM
OOM
89.8
68.0
56.0
39.1
100.0
WLKS-(D)
64.2
65.1
57.9
89.8
68.0
56.0
39.1
100.0
Table 5: Mean performance in micro Fl-score of WLKS variants integrated with continuous fea-
tures over 10 runs. Used S2N models are based on GCNII (Chen et al. 2020p. The higher the performance, the darker the blue color.
Model
PPI-BP
HPO-Neuro
HPO-Metab
EMAUser
Dereity
Cut-Fatio
Coreness
Component
WLKS-(0,D)
61.8jo.
65.3
57.9_m.a
91.8
96.01o.
60.0
91.310.
100.00
WIKS-(O, D) Kernel on X
64.8
65 65.920.0
50. 50.120.0
91 8.0.0
96.02a.0
64.02n.0
91 320,0
100.0.0.0
WLKS- (o. D) + Coni. WL Kemel on X
64.820.0
66.2 66.220.0
50.6_..0
93.0
96.0200
64.0_..0
91 11.30
100.0.o.0
WLKS-(0, Dj for S2N+0
61.8;1.5
66 1,0.
62.4_
86. 56.5
92.0
51.2_ax.
69 (0......
100.0.0.a
W1.KS-(0, D) for S2N+A
65.422.
68.4
62.9-1.9
90.0
96.8+2a
48.0=n.0
87.4+4.1
100.040.p
bination makes the better performance. This is clearly demonstrated in the Coreness experiment for predicting the average core number of nodes within a subgraph. This benchmark requires modeling internal structures, global structures, and subgraph positions. A significant improvement by com- bining kernels on Coreness aligns with our research motivation of capturing arbitrary interactions between and within subgraph structures. This ability is necessary when multiple k-hop neighbor- hoods are associated with the labels of the subgraph, and the performance can be improved from the complementary nature WLKS capturing different k-hop structures.
The selection of k is analogous to determining the number of layers in GNNs and can be treated as a hyperparameter optimized for specific tasks. Intermediate values of i may capture important substructures in datasets with large diameters. However, the model empirically performs well even when & is substantially smaller than the graph's 's diameter D. For instance, PPI-BP's largest compo- nent has a diameter of 8, yet A: = 2 performs as well as k D. In addition, our empirical results showed no clear relation between the size of the graph, its global density, or the average density of subgraphs (as presented in Table I and task performance with different & values. This suggests that such structural properties are not key factors in determining the optimal k. Instead, the nature of the task and its structural requirements should guide the selection of k.
Performance of WLKS Variants Integrated with Continuous Features Table 5 presents the results of WLKS variants combining WLKS- (0. D} and continuous features. The performance of WLKSS-O, D) for S2N improves over vanilla WLKS- D} PPI-BP, HPO-Neuro, and HPO- Metab. However, performance decreases on EM-User, Density, Cut-Ratio, and Coreness. Applying GNNs to the WLKS kernel matrix requires kernel sparsification, which leads additional loss of structural information. The enhanced features provided by deep neural networks can mitigate this trade-off. We interpret that the former set of benchmarks prioritizes features over structure, while the latter relies more on structural information. Using kernels on continuous features improves performance on HPO-Neuro, HPO-Metab, EM-User, and Cut- Ratio. Notably, on EM-User, it achieves the best performance of 93.9 among all methods. For other datasets, no changes in performance are observed. Unlike the combination of GNN-based models, which can leverage the feature processing of neural networks, kernels on features provide limited performance gains from features.
Sensitivity Analysis of Hyperparameters Figures 3 and ( demonstrate the performance sensitiv- ity of the WLKS-(0. D} with respect to the number iterations T and the kernel mixing coefficient 0g. The best performance is achieved at iterations of T' 2 or T = 3, beyond which the WL color- ing stabilizes and no further improvement is observed. For cu, the WLKS-(0, D) is best perffrerforme between 10 and 10 while performance drops sharply au approaches 1. Since ap 1 oo larger than ag in this range. this suggests that the subgraph labels rely more on global structures
(k D) than internal ones (k 0) for these datasets.

---

Published as a conference paper at ICLR 2025
0.58
Pufammnn
2.6
beffrrannce
0.65
0.57
Ber Informance
0.85
0.64
0.56
0.5
0.55
0.43
0.75
Iterations
Iterations
Iberations
Iterations
(a) PPI-BP
(b) HPO-Neuro
(c) HPO-Metab
(d) EM- Useur
Figure 3: Performance of WLKS-(O, (0, D} by the number iterations T.
0.6
Nrformanc
Performance
0.5
Derformnnce
0.4
0.4
0.4
0.2
0.3
alha_0
(a) PPI-BP
(b) HPO-Neuro
(c) HPO-Metab
(d) EM-User
Figure 4: Performance of WLKS- D} by the coefficient dg og K
+ (1 0kg K.
WL.
7 CONCLUSION
We proposed WLKS, a simple but powerful model for subgraph-level tasks that generalizes the Weisfeiler-Lehman (WL) kernel on induced k-hopp neighborhoods. WLKS can enhance expressive- ness by linearly combining kernel matrices from multiple k-hop levels, capturing richer structural information without redundant neighborhood sampling- Through extensive experiments on eight real-world and synthetic benchmarks, WLKS outperformed state-of-the-arr GNN- models on five datasets with reduced training times timeinnanging ranging from x0.01 to x0.25 compared existing mod- els. Furthermore, WLKS does not need pre-computation, pre-training, GPUs, or extensive hyperpa- rameter tuning.
Our method offers promising and accessible alternative to GNN-based approaches for subgraph representation learning, but some tasks can still benefit from incorporating continuous features. We leave as future work the seamless integration of WLKS with Graph Neural Networks to leverage the expressive power of both structures and features.
ACKNOWLEDGMENTS
This work was supported by Institute of Information communications Technology Planning & Evaluation (IIT)) grant funded by the Korea government (MSIT) -0..8-2222-1122011. 84, Develop- ment and Study of AI Technologies Inexpensively Conform Evolving Policy on Ethics)
REFERENCES
Emily Alsentzer, Samuel G Finlayson, Michelle M Li, and Marinka Zitnik. Subgraph neural net- works. Proceedings of Neural Information Processing Systems, NewrlPS, 2020.
Antoine Bordes, Sumit Chopra, and Jason Weston. Question answering with subgraph embeddings. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 615-620. 2014.
Karsten M Borgwardt and Hans- Peter Kriegel. Shortest-path kernels graphs. In Fifth IEEE international conference on data mining (ICDM 005) pp. 8 pp. IEEE, 2005.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph con- volutional networks. In International Conference on Machine Learning, pp. 1725-1735. PMLR, 2020.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference Learning Representations, 2022.
10

---

Published as a conference paper at ICLR 2025
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In International Conference on Learning Representations Workshop on Representation Learning on Graphs and Manifolds, 2019.
Radin Hamidi Rad, Ebrahim Bagheri, Mehdi Kargar, Divesh Srivastava, and Jaroslaw Szlichta. Subgraph representation learning for team mining. In Proceedings of the 14th ACM Web Science Conference 2022, pp. 148-133, 2022.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference Neural Information Processing Systems, pp. 1035, 2017.
Shweta Ann Jacob, Paul Louis, and Amirali Salehi-Abari. Stochastic subgraph neighborhood pool- ing for subgraph classification. In Proceedings of the 32nd ACM international conference on information and knowledge management, pp. 3963-39661 2023.
Hisashi Kashima, Koji Tsuda, and Akihiro Inokuchi. Marginalized kernels between labeled graphs. In Proceedings of the 20th international conference on machine learning (ICML-03), pp. 321- 328, 2003.
Dongkwan Kim and Alice Oh. Translating subgraphs to nodes makes simple GNNs strong and efficient for subgraph representation learning. In Forty-first International Conference on Machine Learning, 2024. URL
net forum? fttp://iwwwweeeeouuuuuummam (e=e:
Dongkwan Kim, Jiho Jin, Jaimeen Ahn, and Alice Oh. Models and benchmarks for representation learning partially observed subgraphs. Proceedings of the 31 ACM International Confer- on Information & Knowledge Management, pp. 4118 4122, 2022.
Nils Kriege and Petra Mutzel. Subgraph matching kernels for attributed graphs. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pp. 291-298, 2012.
Andrei Leman and Boris Weisfeiler. A reduction a graph to a canonical form and an algebra arising during this reduction. Nauchno--Technicheskavv Informatsiya, 2(9):12-16, 1968.
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, 33:4465-44788 2020.
Shufei Li, Pai Zheng, Shibao Pang. Xi Vincent Wang, and Lihui Wang. Self-organising multiple human-robot collaboration: temporal subgraph reasoning- method. Journal of Manufac- turing Systems, 68:304 312, 2023.
Chang Liu, Yuwen Yang, Zhe Xie, Hongtao Lu, and Yue Ding. Position-aware subgraph neural net- works with data-efficient learning. In Proceedings of the sixteenth ACM international conference web search and data mining, pp. 643-651, 2023.
Yuan Luo. Shine: Subhypergraph inductive neural network. Advances Neural Information Pro- cessing Systems, 35:18779-18792, 2022.
Paridhi Maheshwari, Hongyu Ren, Yanan Wang, Rok Sosic, and Jure Leskovee. Timegraphs: Graph- based temporal reasoning. arXiv preprint arXiv:2401.03134, 2024.
Changping Meng, S Chandra Mouli, Bruno Ribeiro, and Jennifer Neville. Subgraph pattern neural networks for high-order graph evolution prediction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018
Annamalai Narayanan, Mahinthan Chandramohan, Lihui Chen, Yang Liu, and Santhoshkumar Sam- inathan. subgraph2vec: Learning distributed representations of rooted sub-graphs from large graphs. arXiv preprint arXiv: /0166666662220 2016.
Shiyu Ouyang, Qianlan Bai, Hui Feng, and Bo Hu. Bitcoin money laundering detection via subgraph contrastive learning. Entropy, 26(3):211, 2024.

---

Published as a conference paper at ICLR 2025
Adam Paszke, Sam Gross, Francisco Massa, Adam Lever, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. In Advances in neural information processing systems, pp- 8026-8037, 2019.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, Vanderplas, A. Passos, D. Coumapeau. M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2886 2011.
Nino Shervashidze and Karsten Borgwardt. Fast subtree kernels on graphs. Advances neural information processing systems, 22, 2009.
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Ef- ficient graphlet kernels for large graph comparison. In Artificial intelligence and statistics, pp. 488-495. PMLR, 2009.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borg- wardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
Matteo Togninalli, Elisabetta Ghisu, Felipe Llinares-López. Bastian Rieck, and Karsten Borgwardt. Wasserstein weisfeiler- graph kernels, Advances in neural information processing systems, 32, 2019.
Lukas Trümper, Tal Ben-Nun, Philipp Schaad, Alexandru Calotoiu, and Torsten Hoefler. Perfor- mance embeddings: A similarity-based transfer tuning approach to performance optimization. In Proceedings of the 37th International Conference on Supercomputing, pp. 50-62, 2023.
Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten Borgwardt. Graph kernels. The Journal of Machine Learning Research, 11:1201-1242, 2010.
Xiyuan Wang and Muhan Zhang. GLASS: GNN with labeling tricks for subgraph representation
learning. In International Conference on Learning Representations, 2022. URL https://
openreview net/ htt///orrmmideeee xx [KNbX
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1365-1374, 2015.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in neural information processing systems, 31, 2018.
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang. and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. Advances in Neural Information Processing Systems, 34:9061-9073, 2021.
Xingyi Zhang, Shuliang Xu, Wenging Lin, and Sibo Wang. Constrained social community recom- mendation. In Proceedings of the 29th ACM SIGKDD conference on knowledge discovery and data mining, pp.
2023.
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any GNN with local structure awareness. In International Conference Learning Representations, 2022. U httpe//efooruuaaaaaaaaaa_oo.OOOn WYKoEH.
12

---

Published as a conference paper at ICLR 2025
A FORMAL COMPARISON WITH REPRESENTATIVE RELATED WORK
In this section, we compare WLKS with highly related prior work including Subgraph Neural Net- work (SubGNN: Alsentzer (Ausnte,/ilsenzzer et al. 2020), GNN with LAbeling trickS for Subgraph (GLASS; Wang & Zhang 2022). Subgraph- To-Node Translation S52N:Kim & Oh 2024). and GNN As Kernel (GNN- AK: Zhao et al. 2022).
While SubGNN employs message-passing within subgraphs, its reliance on ad hoc patch sampling and its separation of hand-crafted channels (e.g., position, neighborhood, structure) introduces com- plexity and potential sub-optimality in information aggregation. Without requiring hand-crafted patch designs or sampling strategies, WLKS captures unified and expressive structural representa- tion based on the theoretical rationale that structures at multiple levels are important.
GLASS uses separate message- passing for node labels that distinguish internal and global struc- tures. This can enhance expressiveness by mixing representations from local and global structures similar WLKS. However, GLASS has a limited ability to handle multiple labels in batched sub- graphs; thus, a small batch size is required for GLASS. WLKS provides a generalized framework to represent fine- tine-grained levels of structures around subgraphs, which can process multiple subgraphs efficiently by leveraging kernel methods.
S2N efficiently learns subgraph representations by compressing the global graph. However, this compression results in a loss of structural information and expressiveness in tasks where the global structure is important. In particular, since the approximation bound of S2N depends on how many subgraphs are spread out in the global graph, we cannot always expect a robust approximation. In contrast, WL.SS does not rely on lossy compression and can yield informative representations using efficient kernel methods.
GNN-AK generates graph representation by aggregating the information of each node's locally in- duced encompassing subgraph. Although there are local and global interactions, there are fundamen- tal differences between WLKS. First, GNN-AK is designed for graph-level tasks, so the interactions between the graph itself and its local subgraphs are modeled. However, dealing with subgraph- tasks is more challenging since modeling both the inside and the outside of the subgraph is required. WLKS encodes them by using multiple h-hop kernels. Second, GNN-AK has a large complexity that depends on the total number of neighbors and the sum of edges between neighbors, so it cannot be applied to a large global graph, unlike WIKS. In fact, the average number of nodes covered by the GNN-AK paper is much smaller, ranging from 25 to 430. In these perspectives, our study takes a complementary approach GNN-AK, addressing aspects not covered in their work.
B DISCUSSION ON RELATIONS BETWEEN WL ISOMORPHISM TEST AND WL KERNELS
In this section, we provide detailed discussion clarify the distinctions between Weisfeiler- Lehman (WL) isomorphism test and WL kernels, elaborating on how our work builds upon these foundational concepts.
The WL algorithm is recognized for testing graph isomorphism by iteratively refining node labels capture the structural similarity between graphs. Its ability distinguish non-isomorphic graphs is often considered a benchmark for evaluating the expressiveness of graph representation methods. While isomorphism distinguishability is theoretically significant, can be overly restrictive in prac- tical applications where the exact topological equivalence of graphs is not the primary concern. For example, many real-world tasks involve identifying structural similarities between graphs that may not be strictly isomorphic but share functional or semantic similarities.
Our work aligns more closely with the WL kernel framework (Shervashidze & Borgwardi 2009; Shervashidze et al.) (011), which extends the application of the WL algorithm beyond isomorphism testing. WL kernels compute graph similarity based on histogram representations of subtree patterns generated by the WL algorithm. These histograms serve compact summaries of graph structure, allowing for the comparison of graphs even when they are not isomorphic. In this context, WL kernels prioritize capturing similarities between graphs over distinguishing isomorphic structures.
13

---

Published as a conference paper at ICLR 2025
k-0
k=
X-2
X
k=0
Hatogram
00..00
K-O
Stabilized
K=1
Stabilzed
k-2
(e. (9, 0))
Stabilzed
(e, (e,
(e. (e.(
A step-by-step visualization of WLsk algorithm (Algorithm) 2 for t: E {0, 10, using an example in Figure
Figure 5:
This broader perspective makes WL kernels particularly suitable for various graph-structured data, where the goal is quantify structural resemblance rather than to test for isomorphism.
Building upon the WL kernel framework, our work introduces the WLKS method, which leverages WL histograms as measures of subgraph similarity. The key insight here is that WI. histograms provide rich representation of subtree patterns within graphs, enabling nuanced comparison of internal and external structures of subgraphs.
C STEP-BY-STEP VISUALIZATION OF WLS* ALGORITHM
Figure 5
we visualize each iteration of the wLs* algorithm using an example of Figure
D USING KERNELS OF DISTANCE OR STRUCTURAL ENCODING
It is well-known that additional structural features (often called labeling tricks, distance encoding, or structural encoding) can enhance the expressiveness of message-passinng passing mechanisms under certain
conditions (Zhang & Chen 2018 Li al. 2020 Zhang et al. 2021 Dwivedi al., 2022 Wang & Zhang 2022).
We argue that these approaches can have different effectiveness for subgraph-level tasks and kemel- based methods:
Zero-one labeling (Zhang et al. 2021 Wang Zhang 2022 : This binary labeling (as-
signing internal nodes and external nodes) shows limited expressiveness when aggregating labels to histograms as kernel inputs. Its histogram is represented as a length-2 vector or 1), which only counts the number of nodes inside and outside the subgraph, thereby omitting finer structural details.
SEAL's Double-radius node labeling (Zhang & Chen 2018): SEAL computes distances
with respect target structures (e.g., links) and can be applicable to k-hop neighborhoods
14

---

Published as a conference paper at ICLR 2025
of subgraphs but computationally challenging. While efficient for link prediction tasks due to the smaller size enclosing subgraphs, extending this approach to general subgraphs becomes infeasible due to the computational overhead of calculating all pairwise distances.
Distance Encoding (DE) (Li et al. 2020) and Random Walk Structural Encoding (RWSE) (Dwivedi al. y022): DE uses landing probabilities of random walks from nodes in the node set to given node, and RWSE uses diagonal elements of random walk matrices. In this line of work, random walk matrices are shown to encode structures in an expressive way, on large-scale graphs.
We linearly combine WLKS-(O. D} with an inner product kernel of RWSE (the walk length of 1 64) aan-aggreatted per subgraph, yielding significant performance boost on the Cut-Ratio dataset (from 60.0 to 96.0). However, this improvement is not shown across the other seven benchmarks we tested. leave investigating which specific node labeling methods are effective, which aggrega- tions of node labels are effective, and which kernels (e.g.. linear, polynomial, RBF) best complement the specific node labeling as future work.
15


Reviews:
[{"review_id": "InkVtXczo0", "reviewer": "Reviewer_ZP6Y", "summary": "The authors tackle the problem of subgraph representation learning, and propose an simple, yet effective method based on Weisfeiler-Leman Kernels. The ideas is quite straightforward: that is, to run the WL algorithm over k-hop neighbourhoods around subgraphs of interest, to collect the output colour histograms, and to define kernels based on those. The authors show that choosing different ks together is beneficial from a discriminative point of view, and propose to consider a specific choice that guarantees a good trade-off between complexity and performance. Experiments validate the effectiveness of such trade-off and discuss additional analyses on the choice of k values and additional hyper-parameters. The authors additionally discuss hybrid approaches that combine their kernel with Graph Neural Network architectures, showing these can be beneficial depending on the relative importance of feature information w.r.t. structure.", "questions": "- What does the “Total training time” refer to exactly for WLKS? what does this term include?\n- What about inference run-time? Can the authors provide some figures on that and discuss this in comparison to other approaches?\n- Line “418”: what does “[…], which are universal for subgraphs […]” mean exactly?\n\nAlso, see “Weaknesses”. I am willing to improve my score after insightful clarifications / additions by the authors.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well written.\n- The method is simple: it is easy to understand while offering a compelling trade-off between complexity and performance.\n- Different aspects of the method are empirically analysed, while a couple of theoretical insights are offered.\n- The combination of the approach with GNN models feels slightly arbitrary, but nonetheless it can already provide initial insights on the relative importance of feature information, and shows how the approach is compatible with other methods.", "weaknesses": "- The manuscript would benefit from a preliminary section that would more formally describe the problem setting of subgraph representation learning, and the shortcomings of state-of-the-art approaches which the authors seek to overcome.\n- The paper lacks a more detailed, *formal* comparison with other state-of-the-art approaches. From a methodological standpoint, beyond experimental results, how is the method different than other approaches such as SubGNN? Is it capturing some information that this last cannot? What are, reasonably, the methodological components and technical features that lead WLKS to outperform them? A better contextualisation in terms of technical components and whether they are captured or not by other methods would also help readers chart a landscape of subgraph representation methods. Expanding Section 5 would go in this direction.\n- The manuscript lacks a more direct discussion on the kind of information WLKS is employing. Is the method completely structural? How can features be included? Is the approach in subsection 2.5 the only way to do so?\n- The proof for Proposition 2.2 does not seem complete. Essentially, it builds upon assumptions that are, themselves, proving most of the claim already (see “Assume that we have […]”, line 181 and similarly in line 187).\n    - I believe that part of the proof should consist in showing these assumption effectively hold. The examples exhibited in Figure 2 already make a step in this direction, but the authors should better and fully formalise this. For example, technically, the subgraphs should be in the same graph.\n    - Related to the above, I believe it would also help if the authors were more explicit in how quantification is made over $k$. Is the claim for any possible $k$? In that case, for example, one should show the existence of counterexamples for any possible $k$, perhaps with an inductive construction. Incidentally, exemplary pairs beyond $k=0$ could be more informative for readers.\n    - Like 189 requires checks: the equation seems to be specific for $k=0$? Is this wanted?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "y8ixoGh4d1", "reviewer": "Reviewer_iDGm", "summary": "The paper addresses the challenge of effectively representing subgraphs in learning tasks by proposing a new approach called the Weisfeiler-Lehman Kernel for Subgraphs (WLKS), which adapts the classic WL algorithm for graph-level tasks to handle subgraph-level tasks by utilizing induced k-hop neighborhoods. By combining kernel matrices from different k-hop levels, WLKS captures complex subgraph interactions without relying on neighborhood sampling. The model achieves similar or better classification performance while reducing training time significantly on various datasets.", "questions": "1.\tCould you provide further discussion on the selection of k? Specifically, does the optimal k value depend on the size or sparsity of the graph/subgraph?\n\n2.\tThe paper does not employ labeling tricks, such as those used in GLASS. Could you clarify the reasoning behind this choice, particularly since distance-based labeling could be effectively integrated with WL kernels?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1.\tWLKS improves subgraph-level task performance by encoding both internal subgraph structures and their k-hop neighborhoods, offering a more expressive alternative to traditional GNNs.\n\n2.\tWLKS achieves superior performance with reduced training times, outperforming several state-of-the-art models by less training time, without requiring GPUs, pre-training, complex hyperparameter tuning, or extensive pre-computation.\n\n3.\tWLKS can be integrated into GNN frameworks (like S2N) as an adjacency matrix, allowing users to benefit from both the structural expressiveness of kernels and the feature-rich nature of GNNs.\n\n4.\tThe paper is generally well-written and easy to follow.", "weaknesses": "1.\tWLKS depends on the node coloring algorithm, making it less suitable for datasets where nodes or edges have continuous feature values, which are challenging to map to discrete color values. It would be beneficial for the authors to discuss potential adaptations of WLKS for handling continuous node and edge features, or to clarify if existing techniques could address this limitation.\n\n2.\tThe selection of k in WLKS is somewhat limited, focusing solely on the original subgraph and the entire global graph, which may be insufficient for larger, more complex datasets where intermediate k values could capture essential substructures. This is especially relevant given that most datasets in the study are not large (as shown in Table 1), raising concerns about how well this approach will generalize to larger graphs. It would be beneficial for the authors to provide theoretical or empirical justification for why using only k=0 and k=D is sufficient. Additionally, the authors could include experiments on larger graphs to demonstrate the scalability of this approach.\n\n3.\tWLKS leverages a basic WL color histogram on subgraphs and a similar histogram within the global graph. This approach, while efficient, may result in a loss of structural information (e.g., datasets requiring detailed interactions between subgraphs).\n\n4.\tThe paper lacks a comprehensive discussion comparing WLKS to baseline models. For instance, although WLKS outperforms baselines such as SubGNN and GLASS on several benchmarks (Table 2), the paper does not explain clearly why WLKS might be more expressive in specific contexts (e.g., powerful in terms of distinguishing isomorphic graphs). It would be beneficial for the authors to provide a detailed analysis of key examples where WLKS outperforms the baselines, highlighting the structural properties that WLKS captures more effectively in these cases.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MoYjgj9ij2", "reviewer": "Reviewer_UnAb", "summary": "This work focuses on addressing challenges related to capturing arbitrary interactions both within and between subgraph structures.  To provide a more expressive and efficient alternative, this work proposes WLKS, a Weisfeiler-Lehman (WL) kernel generalized for subgraphs by applying the WL algorithm on induced k-hop neighborhoods.", "questions": "Q1. What is the purpose of the discussion and analysis in Sec. 2.2? The main content of Sec. 2.2 is the proof of Proposition 2.2, which shows that the expressiveness of $WL{S^{k + 1}}$ is not strictly greater than $WL{S^{k }}$. However, in the subsequent analysis, the authors do not seem to propose a method for designing $k$ based on this insight.\n\nQ2. I am puzzled as to whether the design of $ k=0, D $ actually addresses the goal of capturing arbitrary interactions between and within subgraph structures, which is the stated research motivation of this work.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "W1. The research significance of subgraph learning in graph representation learning is undoubtedly valuable.\n\nW2. The research in this manuscript is interesting, and the proposed framework of both efficiency and effectiveness is exciting.", "weaknesses": "W1. The analysis of existing challenges is unconvincing, and this manuscript lacks an analysis of existing works.  The author identifies the main challenge as capturing arbitrary interactions between and within subgraph structures. However, the local-global interactive learning strategy has been well studied by GNN-AK[1]. \n\nW2. This manuscript lacks sufficient interpretability analysis of the proposed method. For instance, the right panel of Figure 1 only shows the final coloring result, leaving us without an understanding of the iterative process of color refinement.\n\nW3. I argue this work lacks a fundamental understanding: the goal of using WL-based deep learning methods or traditional machine learning methods is to improve the distinguishability of isomorphisms that would otherwise be indistinguishable. However, I do not see this insight or explanation reflected in the work.\n\n[1] From stars to subgraphs: Uplifting any GNN with local structure awareness, iclr 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)