AKBR: Learning Adaptive Kernel-based Representations for Graph Classification

1 Introduction

Graph-based representations are powerful tools for encapsulating structured data characterized by pairwise relationships among its components [Zambon et al., 2018], and have been widely employed in various research fields, such as the analysis of social networks [Bai et al., 2020b], financial transactions [Bai et al., 2020a] and biological networks [Gasteiger et al., 2021]. The main challenge arising in graph data analysis is how to learn representative numeric characteristics for discrete graph structures. One of the most effective methods for learning graph-structured data is to employ graph kernels.

∗Corresponding Author: Lixin Cui

Broadly speaking, graph kernels aim to describe the structural information in a high-dimension Hilbert space, typically defining a positive definite similarity measure between graphs. [Haussler and et al., 1999] proposed a generic way, namely the R-convolution framework, to define graph kernels. This is achieved by decomposing two graphs into substructures and evaluating the similarity between the pairs of substructures. Specifically, given two sample graphs Gp and Gq, assume S = {g1, ..., gM} is the set of their all possible substructures based on a specified graph decomposing approach, the R-convolution kernel KR between Gp and Gq is defined as

where the function k is defined as the Dirac kernel, and k( ⃗ gp, ⃗ gq) is equal to 1 if the substructures ⃗ gq and ⃗ gq are isomorphic to each other, and 0 otherwise.

In recent years, the R-convolution framework has proven to be an effective way to define novel graph kernels and most state-of-the-art R-convolution graph kernels can be categorized into three main categories, i.e., the R-convolution kernels based on the walks, paths, and subgraph or subtree structures. For instance, the RandomWalkGraphKernel (RWGK) is proposed by [G¨artner et al., 2003] based on the similarity measures between random walks. However, the random walks suffer from the notorious tottering problem and allow the repetitive visiting of vertices, leading to significant information redundancy for the RWGK kernel. [Borgwardt and Kriegel, 2005] have proposed a Shortest Path Graph Kernel (SPGK) by counting the pairs of shortest paths with the same length. Since the shortest paths are typically nonbacktrack paths and can be computed in a polynomial time, the SPGK kernel can significantly overcome the drawbacks of the RWGK kernel. To capture more structural information, thus some subgraph-based or subtree-based R-convolution graph kernels have been developed. For instance, [Shervashidze et al., 2009] have proposed a Graphlet Count Graph Kernel (GCGK) by counting the frequency of graphlet subgraphs of sizes 3, 4 and 5. Since the GCGK kernel cannot accommodate the vertex attributes, [Shervashidze et al., 2011] have further developed the Weisfeiler-Lehman Subtree Kernel (WLSK) based on subtree invariants. Specifically, the WLSK kernel is defined by counting the number of pairwise isomorphic subtrees through an iterative aggregation of node neighbor labels, effectively enabling labeled graph classification. Moreover, since the WLSK kernel can efficiently and gradually aggregate the local topological substructure information (i.e., the vertex labels corresponding to subtree invariants) between neighbor vertices to further extract subtrees of large sizes, this kernel not only has better computational efficiency but also has superior effectiveness for graph classification, being one of the most popular graph kernels by now. Other graph kernels based on the R-convolution also include (1) the Wasserstein Weisfeiler-Lehman Subtree Kernel [Togninalli et al., 2019], (2) the Subgraph Alignment Kernel [Kriege and Mutzel, 2012], (3) the Message Passing Graph Kernels [Nikolentzos and Vazirgiannis, 2018] etc.

Although state-of-the-art R-convolution graph kernels have demonstrated their performance on graph classification tasks, they still suffer from three common problems. First, these R-convolution graph kernels only focus on measuring the similarity or the isomorphism between all pairs of substructures, completely disregarding the importance of different substructures. As a result, some redundant structural information that is unsuitable for graph classification may also be considered. Second, these R-convolution graph kernels focus solely on the similarity between each pair of graphs, neglecting the common patterns shared among all sample graphs. Third, all these R-convolution graph kernels tend to employ the C-SVM classifier [Cortes and Vapnik, 1995] for classification, and the phase of training the classifier is entirely separated from that of the kernel construction. This limitation may restrict the performance of existing R-convolution graph kernels. To overcome the first shortcoming, [Aziz et al., 2020] have employed the feature selection method to discard redundant substructure patterns associated with zero for the GCGK kernel, significantly improving the classification performance. However, this kernel method requires manually enumerating all possible graphlet substructure sets to compute the mean and variance, and still cannot provide an endto-end learning framework to adaptively compute the kernelbased similarity. Overall, defining effective kernel-based approaches for graph classification remains challenging.

The objective of this work is to address the drawbacks of the aforementioned R-convolution graph kernels, by developing a novel framework to compute the Adaptive Kernel-based Representations (AKBR) for graph classification. One key innovation of the proposed AKBR model is that it can provide an end-to-end kernel-based learning framework to discriminate significant substructures and thus compute an adaptive kernel matrix between graphs. The main contributions are summarized as threefold.

First, to resolve the problem of ignoring the importance of different substructures that arise in existing R-convolution graph kernels, we propose to employ the attention mechanism as a means of feature selection to assign different weights to the substructures represented as features. We model the interdependency of different substructure-based features using the feature-channel attention mechanism to focus on the essential part of the substructure-based feature vectors of graphs.

Second, inspired by the graph dissimilarity or similarity embedding method presented by [Bunke and Riesen, 2008; Bai et al., 2013], the resulting kernel matrix can be seen as a kind of kernel-based similarity embedding vectors of all sample graphs. As a result, the proposed AKBR model can adaptively discriminate the structural importance of different substructures, and further compute the adaptive kernel-based representations for graph classification, significantly overcoming the three aforementioned theoretical drawbacks arising in existing R-convolution graph kernels.

Third, we evaluate the proposed AKBR model on graph classification tasks. The experimental results demonstrate that the proposed model can significantly outperform stateof-the-art graph kernels and graph deep learning methods.

2 RelatedWorks

In this section, we review some state-of-the-art R-convolution kernels and some classical Graph Neural Networks (GNNs). Besides, we theoretically analyze the drawbacks arising in these existing approaches, enlightening the proposed method.

2.1 Classical R-convolution Kernels

We briefly review two classical R-convolution kernels, including WLSK [Shervashidze et al., 2011] and the SPGK [Borgwardt and Kriegel, 2005]. We commence by introducing the definition of the WLSK kernel that focuses on aggregating the structural information from neighboring vertices iteratively to capture1 subtree invariants through the classical Weisfeiler-Lehman Subtree-Invariant (WL-SI) method [Weisfeiler and Lehman, 1968]. Given two sample graphs Gp and Gq, assume l0(u) represents the initial label of vertex u. Specifically, for unlabeled graphs, the degree of each vertex is considered as the initial label. Then, for each iteration i, the WLSK constructs the multi-set label LiN for each vertex u by aggregating and sorting the labels of u as well as its neighborhood vertices, i.e.,

where N(u) is the set of the neighborhood vertices of u. The WLSK kernel merges the multi-set label LiN of each vertex u and into a new label li(u) through a Hash function as

where Hash is the hash mapping function that relabels LiN as a new single positive integer, and each li(u) corresponds to a subtree rooted at u of height i. The iteration i ends when the number of iterations is met to the largest one (i.e., Imax). The WLSK kernel KWL(Gp, Gq) between the pair of graphs Gp and Gq can be defined by counting the number of shared pairwise isomorphic subtrees corresponding by li(u), i.e.,

where Imax denotes the maximum number of the iteration i, lj i ∈ Li is the j-th vertex label of Li , and N(Gp, lj i ) represents the number of the subtrees corresponded by the label lj i and appearing in Gp.

The idea of the SPGK kernel is to compare the similarity between a pair of graphs by counting the number of shared shortest paths with the same lengths. The first step of computing the SPGK kernel is to extract all shortest paths from each graph by using the classical Floyd algorithm [Floyd, 1962]. Given the pair of graphs Gp and Gq, the SPGK is defined as

where si ∈ S is the shortest path of length i, S is the set of all possible shortest paths appearing in all graphs, and N (Gp, si) represents the number of si appearing in Gp.

Remarks. Although the WLSK and SPGK kernels associated with the C-Support Vector Machine (C-SVM) [Chang and Lin, 2011] have effective performance for graph classification, they still suffer from the theoretical drawbacks we discussed in Section 1.

2.2 Classical Graph Neural Networks

One way to overcome the aforementioned problems of Rconvolution graph kernels is to adopt the GNN models, that are developed by generalizing the classical Neural Networks to the graph domain based on the spectral or spatial strategy [Bai et al., 2022b; Cui et al., 2024]. Since the spectralbased GNN models usually require that the graphs should have the same size, and are only suitable for node classification [Bruna et al., 2014]. The spatial-based GNN models are widely developed for graph classification. Under this scenario, the Graph Isomorphism Network (GIN) proposed by [Xu et al., 2019] exhibits the same expressive power with the WLSK kernel. The Diffusion Convolution Neural Network (DCNN) [Atwood and Towsley, 2016] uses different weights to propagate the neighborhood information from different hops to the center. The Graph Convolution Neural Network (PATCHY-SAN) [Niepert et al., 2016] extracts the features by converting the graph structure into fixedsized patches. The Deep Graph Convolution Neural Network (DGCNN) [Zhang et al., 2018] sorts the nodes based on the substructure information extracted from the last graph convolutional layer and preserves predetermined numbers of nodes, resulting in the fixed-sized grid structure for the traditional convolution operation.

Remarks. Although the above GNNs can naturally provide an end-to-end framework, it is not available for classical Rconvolution kernels. These GNNs still suffer from some similar drawbacks. First, the GIN and DCNN models tend to directly sum up the local vertex features as the global graph representation through the SumPool operation, discarding the importance of the different local structure information residing on different nodes. Second, the PATCHY-SAN and DCNN models only preserve the local structure information residing on the top-ranked nodes based on the SortPool operation, resulting in significant information loss. In fact, these drawbacks also appear in other alternative GNNs, influencing the performance of graph classification.

Several works have also explored the intersection between graph kernels and graph-based deep learning methods. Specifically, GNTK [Du et al., 2019] bridges graph kernels and graph neural networks (GNNs) by modeling smooth functions defined over graphs. KerGNN [Feng et al., 2022] introduces trainable hidden graphs as filters to refine node embeddings, while RWNN [Nikolentzos and Vazirgiannis, 2020] utilizes random walk kernels to measure similarities between input graphs and hidden structures. However, these approaches generally require increased parameters, thereby incurring higher computational costs.

3 The Proposed AKBRModel for Graphs

In this section, we develop a novel Adaptive Kernel-based Representations (AKBR) model. We introduce the detailed definition of the proposed AKBR model.

3.1 The Framework of the AKBRModel

We commence by defining the framework of the proposed AKBR model. Specifically, the computational architecture is shown in Figure 1, mainly consisting of three procedures. First, we construct the feature vector φ(Gi) for each sample graph Gi based on the substructure invariants extracted with a specific R-convolution graph kernel. In this work, we propose to adopt the classical WLSK and SPGK kernels for the proposed framework. This is because the subtree and shortest path substructures are effective in representing the structural characteristics of the original graphs. Second, we employ an attention layer to assign different weights to different substructures, and the critical features will be associated with larger weights through the attention mechanism. Third, the resulting kernel matrix between pairwise graphs can be computed as the dot product between their attention-based substructure feature vectors. Inspired by the graph dissimilarity or similarity embedding method presented by [Bunke and Riesen, 2008; Bai et al., 2013], we employ the resulting kernel matrix as the kernel-based similarity embedding vectors of all sample graphs.

As a result, the framework of the proposed AKBR model can provide an end-to-end learning architecture between the kernel computation as well as the classifier, i.e., the proposed AKBR model can adaptively compute the kernel matrix associated with the most effective substructure invariants.

3.2 The Definition of the AKBRModel

In this subsection, we provide a detailed explanation of the computation process for each step.

The Construction of Substructure Invariants

We employ the classical WLSK and SPGK kernels to extract the subtrees and the shortest paths as the substructure invariants. For the WLSK kernel, the subtree-based feature vector φWL(G) of a sample graph G is defined as

where li is the vertex label defined by Eq.(3) and corresponds to a subtree invariant, each element n(G, li) is the number of the corresponding subtree invariants appearing in G, and |L| is a positive integer and refers to the number of all distinct subtree invariant labels. Similarly, for the SPGK kernel, the feature vector φSP(G) of the graph G is defined as

where each element n(G, si) is the number of the shortest paths with the length si in the graph G, and |S| denotes the greatest length of the shortest paths over all graphs. With the substructure-based feature vectors of all graphs in G = {G1, . . . , GN} to hand, we can derive the feature matrix X ∈ RN×L for the entire graph dataset G, i.e.,

where N denotes the number of graphs, L denotes the dimension of each feature vector φ(Gj) for the graph Gj ∈ G, and (·) corresponds to either the WLSK or the SPGK kernel.

Attention Mechanism for Feature Selection

As we have stated previously, some substructure-based features may be more prevalent in some graphs. These features naturally encapsulate more significant and discriminative structural information for classification. Thus, assigning a more substantial weight to these features is preferred. As a result, it is necessary to perform a thorough examination to evaluate the importance of different features across all graphs. To this end, we propose to employ the attention mechanism as a means of feature selection, and adaptively identify the most effective features of the feature matrix X(·) ∈ RN×L.

There have been various types of attention mechanisms, including the self-attention [Vaswani et al., 2017], the external attention [Guo et al., 2022], and channel attention [Hu et al., 2018]. Inspired by the recent attention-based work [Hu et al., 2018] that proposes to squeeze the global spatial information into a channel descriptor, we commence by using the SumPooling operation to aggregate the information of all graphs and squeeze them into a feature channel. Given the feature matrix X(·) ∈ RN×L of all graphs in G, the aggregation information h ∈ R1×L can be calculated as

where hl is the l-th element of h. With h to hand, we use three fully connected linear layers associated with the nonlinear activation function to calculate the attention scores. Specifically, we use W1 ∈ RL×C to denote the weight of the first fully connected layer and W2 ∈ RC×L to represent the weight of the second dense layer, where C denotes the hidden feature dimension.

The resulting attention-based scoring matrix α ∈ RN×L for the feature matrix X(·) ∈ RN×L can be computed as

where σ is the ReLU function, and α is the attention score.

With attention-based scoring matrix α that encapsulates adaptive weights for the different features of each graph, the substructure-based feature matrix X(·) can be updated as the weighted substructure-based feature matrix X′ (·) by multiplying the attention scores, i.e.,

where ⊗ refers to the feature-wise multiplication. An instance of the attention mechanism for feature selection is shown in Figure2. In summary, the attention mechanism can assign substructures of each graph with different weights according to their importance.

The Kernel-based Graph Embedding Vectors

Based on the definition provided in [Shervashidze et al., 2011], any R-convolution graph kernel can be computed as the dot product between the substructure-based feature vectors of pairwise graphs. For an instance, the WLSK kernel KWL defined by Eq.(4) between a pair of graphs Gp and Gq can be rewritten as

where each φWL(Gp) is the substructure-based feature vector defined by Eq.(6). With the attention score computed by Eq.(11) to hand, we can compute the kernel value between weighted substructures as

Thus, the attention-based kernel matrix can be computed. Specifically, [Bunke and Riesen, 2008] has proposed a (dis)similarity graph embedding method that can embed or convert each graph structure into a vector, so that any standard machine learning and pattern recognition for vectors can be directly employed. In this paper, we propose to employ all sample graphs as the prototype graphs and use the graph kernel as the means of the similarity between each sample graph G and each prototype graph Gpq ∈ G (including G itself). Thus, the kernel-based embedding vector ϕ(·)(G) of G can be defined as

where each element K(·)(G,Gpq ) represents the kernel value between G and the prototype graph Gpq , and (·) indicates that Eq.(14) can be computed with either the WLSK kernel or the SPGK kernel. Clearly, if G ∈ G is the j-th sample graph Gj ∈ G (i.e., G = Gj), the kernel-based embedding vector ϕ(·)(G) is essentially the j-th row of the kernel matrix K(·). As a result, the kernel matrix K(·) can be theoretically seen as the kernel-based embedding vectors over all graphs fromG.

An instance of the kernel-based graph embedding is shown in Figure 3, where Gpi denotes the i-th prototype graph.

Since the attention-based weights for computing the kernel matrix and the trainable parameter matrix for the classifier can be adaptively updated when the loss is backpropagated, the computational framework of the proposed AKBR model can naturally provide an end-to-end learning mechanism.

3.3 Complexity Analysis

With |V | and |E| as the average number of nodes and edges, N is the number of graphs, Tmax is the number of iterations in WLSK, d is the largest feature dimension. For the SPGK, we can extract all shortest paths in O(|V |2 log |V | + |V ||E|) time by using Johnson's algorithm. Since 0 < |E| ≤ |V |(|V | - 1)/2, this approach only reaches cubic complexity for fully connected graphs. For WLSK, the time complexities of computing explicit feature vector and feature attention are O(Tmax|E|) and O(Nd+d2 ). Moreover, the time complexity of the classifier is O(N 2d). Thus, the total time complexities of AKBR(SP) and AKBR(WL) are O(N(|V |2 log |V | + |V ||E|) + N 2d) and O(Tmax|E| + d2 + N 2d).

4 Experiments

In this section, we evaluate the performance of the proposed AKBR model against state-of-the-art graph kernels and deep learning methods. We use ten standard graph datasets extracted from bioinformatics (Bio), social networks (SN), and computer vision (CV). The OGBG-MOLBACE and OGBGMOLBBBP datasets are selected from Open Graph Benchmark [Hu et al., 2020]. The Shock dataset can be obtained from [Siddiqi et al., 1999]. Other datasets from bioinformatics and social networks can be directly downloaded from [Morris et al., 2020]. We provide the graph number and the average graph size of each dataset in Table 1. Our code is publicly available 1 .

4.1 Comparisons with Graph Kernels Experimental Settings

We compare the performance of the proposed AKBR model with several state-of-the-art graph kernels for graph classification tasks as Table 2: the Graphlet Count Graph Kernel (GCGK) with graphlet of size 3 [Shervashidze et al., 2009], the RandomWalk Graph Kernel (RWGK) [G¨artner et al., 2003], the Shortest Path Graph Kernel (SPGK) [Borgwardt and Kriegel, 2005], the Shortest Path Kernel based on Core Variants (CORE SP) [Nikolentzos et al., 2018a], the Weisfeiler-Lehman Subtree Kernel (WLSK) [Shervashidze et al., 2011], the WLSK kernel associated with Core Variants (CORE WL) [Nikolentzos et al., 2018b], the Valid Optimal Assignment Kernel (WL-OA) [Kriege et al., 2016], the Graph Alignment Kernels using Weisfeiler and Leman Hierarchies (GAWL) [Nikolentzos and Vazirgiannis, 2023], a new graph kernel that aligns vertices transitively between graph pairs (HTAK) [Bai et al., 2022a] and the Deep Hierarchical Graph Alignment Kernels (DHGAK) leveraging natural language embeddings [Tang et al., 2024]. We perform a 10-fold cross-validation and repeat the experiments ten times, and the average accuracy is reported in Table 2. Since some methods are not evaluated by the original paper on some datasets, we do not provide these results. We use the AKBR(SP) and AKBR(WL) to represent the AKBR model based on the SPGK and the WLSK.

1 https://github.com/Sophia0830BNU/AKBR

Experimental Results and Analysis

Compared to the classical graph kernels, the family of the proposed AKBR models achieves highly competitive accuracies in Table 2. Specifically, we observe that the family of the proposed AKBR(WL) can outperform state-of-the-art graph kernels on all datasets. On the other hand, the proposed AKBR(SP) also significantly outperforms the original SPGK and Core SP kernels. These observations demonstrate that the theoretical advantages of the proposed AKBR model, i.e., adaptively identifying the importance of different substructures and computing the adaptive kernel matrix through an end-to-end learning framework can tremendously improve the classification performance.

4.2 Comparisons with Deep Learning

Experimental Settings

We further compare the family of our proposed AKBR models with some state-of-the-art graph deep learning methods as Table 4, including the Deep Graph Convolution Neural Network (DGCNN) [Zhang et al., 2018], the Diffusion Convolution Neural Network (DCNN) [Atwood and Towsley, 2016], the PATCHY-SAN based Graph Convolution Neural Network (PATCHY-SAN) [Niepert et al., 2016], the Deep Graphlet Kernel (DGK) [Yanardag and Vishwanathan, 2015], the Random Walk Graph Neural Networks (RWNN) [Nikolentzos and Vazirgiannis, 2020], the Graph Isomorphism Network (GIN) [Xu et al., 2019], the WL-based GNNs (3WL-GNN) [Morris et al., 2019], an instantiation of generalized message-passing framework (GraphSNN) [Wijesinghe and Wang, 2022], the GNNs with positional encoding (GatedGCN-LSPE) [Dwivedi et al., 2022], the Graph Convolution Network (GCN) [Kipf and Welling, 2017], the Union Subgraph Neural Networks (UnionSNN) [Xu et al., 2024] and the the masked-attention ML-model using softmax kernel (GKAT) [Choromanski et al., 2022]. For these baseline methods, they are also evaluated using the same 10fold cross-validation strategy as ours, thus we directly report the results from the original papers. We also evaluate the performance of the proposed AKBR method on the OGBGMOLBACE and OGBG-MOLBBBP datasets. The results are reported in Table 3.

Experimental Results and Analysis

Table 4 demonstrates that the proposed AKBR(WL) model consistently outperforms alternative graph deep learning methods across seven TUDatasets. Furthermore, we also evaluate the proposed AKBR(WL) method on OGBGMOLBACE and OGBG-MOLBBBP datasets. The results are shown in Table 3. We can observe that the proposed AKBR(WL) model achieves the highest ROC-AUC scores on the ogbg-molbace and ogbg-molbbbp datasets, reinforcing its effectiveness. In fact, similar to our methods, all these alternative graph deep learning methods can also provide an end-to-end learning framework, but typically stack more layers than our model does. However, the proposed method still has better classification performance than these graph deep learning methods, again demonstrating the effectiveness of the kernel-based framework.

4.3 In-depth Discussions of the AKBRModel

To better analyze the advantages of the proposed AKBR model beyond standard benchmarks, we conduct an in-depth discussion focusing on its internal mechanisms and performance sensitivity.

Q: How sensitive is the model to the number of iterations? We explore how the classification accuracies of the proposed AKBR(WL) vary with different iterations ranging from 1 to 5 on the PROTEINS and MUTAG datasets, and the results are shown in Figure 4. Each model has been trained for 500 epochs on the first fold. We report curves with standard error computed on 40 runs for each iteration. Specifically, we find that AKBR(WL) with iteration 1 has the optimal performance. This is due to the fact that as the number of iterations increases, the number of substructures grows exponentially, resulting in a large amount of redundant information. To illustrate this conclusion more intuitively, we count the number of substructures generated by AKBR(WL) across iterations 1 to 10 as shown in Table 5.

Q: How does the Channel Attention affect the performance of the proposed model? We first conduct the ablation study of the AKBR with or without channel attention on four representative datasets. Figure 5 shows the accuracy and standard deviation across ten runs of ten-fold crossvalidation. When the Channel Attention is removed, the accuracy of the AKBR significantly decreases, demonstrating the importance of channel attention.

Furthermore, to more intuitively demonstrate the effectiveness of the channel attention mechanism, we incorporate Self-Attention and Multi-Head Self-Attention [Vaswani et al., 2017] (with the number of heads set to 4) to the experiment, as shown in Table 6. To more intuitively demonstrate the effect of the attention mechanism, we also visualize the top four substructures with the highest attention scores in Figure 6. These substructures are representative of graph labels, indicating that our proposed channel attention effectively selects critical features, thereby enhancing the classification performance of the model.

Moreover, Table 5 shows that as the number of iterations increases, the number of substructures grows exponentially. Consequently, the weight assigned to each substructure in-

(d) FRANK

Figure 5: The ablation study of AKBR with or without channel attention. w/o CA(WL) denotes AKBR(WL) without channel attention, w/o CA(SP) denotes AKBR(SP) without channel attention.

variant becomes smaller. This further explains why the performance of AKBR(WL) declines with additional iterations.

Q: Whether our proposed model can integrate other Rconvolution graph kernels? Our proposed method is compatible with any R-convolution graph kernel. We choose the WLSK and SPGK because their associated subtree and shortest path substructures can be efficiently extracted and are known to represent meaningful structural information. To verify that our method is indeed applicable to other Rconvolution graph kernels, we evaluate the AKBR model with the Random Walk Graph Kernel (RWGK), i.e., the AKBR (RW). As shown in Table 7, AKBR(RW) also achieves superior performance compared to the original RWGK, demonstrating that the proposed AKBR framework can be seamlessly integrated with various R-convolution kernels and consistently enhance their effectiveness.

Q: Whether the number of prototype graphs impacts the performance of the model? We conduct an experiment to evaluate the impact of the number of prototype graphs. The experimental results are shown as 8, the performance remains stable as the number of prototype graphs increases from 200 to 800 across all datasets. Note that, we select the graph with the highest Shannon entropy as the prototype graph [Bai et al., 2013]. For example, on the DD dataset, the accuracy varies from 74.12% to 74.57%. These minimal variations indicate that the proposed method is robust to changes in the number of prototype graphs and maintains consistent performance, demonstrating strong generalization capability.

Q: Whether the AKBR(s) deliver superior efficiency compared with existing deep learning methods? We conduct an experiment to compare the total time cost of AKBR(WL) with that of deep learning methods. The results are shown in Table 9. For large-scale datasets, e.g., DD, our proposed AKBR model runs over 6.17 times faster than UnionSNN. This is because AKBR does not require a large number of network layers, further proving that our proposed model structure is simple yet effective.

5 Conclusion

In this paper, we have proposed a novel AKBR model that can extract more effective substructure-based features and adaptively compute the kernel matrix for graph classification through an end-to-end learning framework. Thus, the proposed AKBR model can significantly address the shortcomings arising in existing R-convolution graph kernels. Experimental results show that our proposed AKBR model outperforms the existing state-of-the-art graph kernels and graph deep learning methods. In future work, we plan to extend our framework to incorporate a broader range of graph kernels, such as quantum walk-based kernels [Bai et al., 2025; Bai et al., 2024; Bai et al., 2023], further enhancing its applicability and effectiveness. In addition, we will explore the hybrid graph kernels, to better capture complementary structural information from diverse perspectives.

Acknowledgements

This work is supported by the National Natural Science Foundation of China under Grants T2122020, 61602535, U21A20473, and 62172370. This work is also supported in part by the Humanity and Social Science Foundation of Ministry of Education (24YJAZH022), and the Program for Innovation Research in the Central University of Finance and Economics.