DHTAGK: Deep Hierarchical Transitive-Aligned Graph Kernels for Graph Classification

1 Introduction

Graph-based machine learning is a crucial research area in artificial intelligence, with wide applications in fields such as social network analysis, bioinformatics, and computer vision. However, the complexity and irregularity of graph data present significant challenges for traditional machine learning algorithms, which are usually designed for vectorial data rather than graph structures. Thus, there is a need for methods that can effectively learn numerical features from graphs.

One effective approach to learning numerical features from graphs is to employ graph kernels, that define a similarity measure between graphs. Graph kernels can map graphs into a high-dimensional Hilbert space, capturing their structural information more effectively. Currently, most existing graph kernels are developed based on the R-convolution framework proposed by [Haussler, 1999]. This framework defines graph kernels by decomposing graphs into substructures and counting the number of isomorphic substructures shared between pairwise graphs. Under this foundation, numerous graph kernels have been developed (see more details in Section 2.1). Despite their effectiveness, the R-convolution graph kernels still suffer from several challenges.

∗XinyaQin@mail.bnu.edu.cn, bailu@bnu.edu.cn

†Corresponding Author: mingli@zjnu.edu.cn

First, the R-convolution graph kernels ignore the positional correspondence information between isomorphic substructures, which leads to unreliable kernel measures between graphs. For instance, the Random Walk Graph Kernel (RWGK) [Gartner et al., 2003], which is an early typical work, only focuses on counting the number of random walks with same lengths, even many walks are not structurally aligned to each other in terms of the global graph structures. This drawback may influence the effectiveness of some applications, including graph-based bioinformatics, where isomorphic molecular motifs located in different regions may exhibit different trait expressions. In recent years, many studies have explored correspondence information in graphs, such as [Bai et al., 2015a; Bai et al., 2019; Bai et al., 2022; Cui et al., 2024]. Among them, [Bai et al., 2015a] have proposed an Aligned Subtree Kernel (ASK), that can effectively explore the node-based matching information between the rooted nodes of subtrees. Unfortunately, the node correspondences identified by this kernel are not transitive (i.e., for three nodes a, b and c, if a matches with b, and b matches with c, it does not guarantee that a matches with c). Thus, this kernel is not positive definite (pd).

Moreover, the R-convolution graph kernels mainly capture the local information from the substructures of small sizes, thereby neglecting the global topological information. For instance, the Graphlet Kernel (GK) [Shervashidze et al., 2009] only considers graphlets with 3-5 nodes, which may overlook important global topological features of graphs. To overcome this limitation, a family of global graph kernels have been developed to focus more on the global structural graph characteristics through the adjacency matrices. For instance, [Johansson et al., 2014] have developed a Global Geometric Embedding Kernel based on the Lov´asz numbers as well as their orthonormal representations, that are computed through the adjacency matrix. [Xu et al., 2018] have proposed a Global Reproducing Graph Kernel by measuring the similarity between the approximated von Neumann entropies based on the adjacency matrix. However, these kernels can only capture global similarities, lacking detailed structural information residing in the internal topological structure of graphs.

Finally, the R-convolution graph kernels only focus on the similarity measure between each individual pair of graphs, and thus cannot capture the common structural pattern information shared over all sample graphs. Overall, the above analysis indicates that developing effective graph kernels is still a challenging problem.

This work aims to overcome the above theoretical limitations of the existing R-convolution kernels by developing a family of novel Deep Hierarchical Transitive-Aligned Graph Kernels (DHTAGK). One key innovation of the new kernels is the construction of the Hierarchical Aligned Graph AutoEncoder (HA-GAE), which not only hierarchically extracts a series of transitive-aligned embedding graphs to capture both the global and local structure information, but also captures the common hierarchical structural pattern information over all graphs. Overall, our contributions are threefold.

First, we develop a new HA-GAE to hierarchically capture the transitive node-level matching information between graphs. Specifically, for each encoding layer, we use the node assignment to group the input nodes into clusters and then compress the nodes within a cluster into a coarsened node, hierarchically transforming the original input graph into an embedding graph. For each decoding layer, we apply the node assignment to reconstruct the original graph structure by expanding each coarsened node into all retrieved nodes probabilistically. Since the HA-GAE is defined by employing the same node assignment function for all original graphs, the adjacency matrices and the node feature matrices of the embedding graphs extracted through the encoding layers are naturally transitive aligned. Furthermore, the HA-GAE can effectively capture the common structural patterns shared over all original graphs through the deep learning architecture.

Second, for pairwise graphs, we develop a new family of DHTAGK kernels based on the transitive-aligned adjacency matrices and node feature matrices of their embedding graphs constructed through the HA-GAE. Due to the theoretical properties of the HA-GAE, the proposed DHTAGK kernels are not only transitive aligned but also capture rich deep hierarchical structural characteristics of graphs, guaranteeing the positive definiteness and explaining the effectiveness for the proposed kernels (see details in Section 3.5).

Third, we evaluate the classification performance of the proposed kernels on standard graph datasets using the C-Support Vector Machine(C-SVM). Experimental results show that the proposed kernels outperform state-of-the-art graph kernels and graph deep learning methods.

This paper is organized as follows. Section 2 reviews some related works. Section 3 provides the definition of the proposed kernels. Section 4 presents experiments. Finally, Section 5 concludes this work.

2 RelatedWorks

2.1 The Graph Kernels

The Graph kernels can provide an elegant way to map graphs into a high-dimensional Hilbert space, enabling linear algorithms to solve nonlinear problems in the original lowdimensional space. Most existing graph kernels are developed based on the R-convolution framework [Haussler, 1999], that decomposes graphs into substructures and counts the number of isomorphic substructures shared between pairwise graphs. This indicates that any graph decomposition method and substructure type can define a new graph kernel function. Under this principle scenario, the R-convolution graph kernels can be classified into the following three categories. a) Random walk-based: e.g., the RWGK [Gartner et al., 2003], the marginalized kernel [Kashima et al., 2003]; b) Path-based: e.g., the Shortest Path Graph Kernel (SPGK) [Borgwardt and Kriegel, 2005], the backtrackless kernel [Aziz et al., 2013]; c) Subtree/subgraphbased: e.g., the Weisfeiler-Lehman Subtree Graph Kernel (WLSK) [Shervashidze et al., 2011], the Graphlet Kernel (GK) [Shervashidze et al., 2009]. Other R-convolution kernels also include the Segmentation Graph Kernel [Harchaoui and Bach, 2007], the Pyramid Quantized Weisfeiler-Lehman Kernel [Gkirtzou and Blaschko, 2016], the Quantum-inspired Jensen-Shannon Kernel [Bai et al., 2020], etc.

Remark 1: Despite the performance of the R-convolution kernels for graph classification, they still suffer form several limitations. First, these kernels do not take the positional correspondence information between substructures into account. Second, these kernels tend to capture local information from small substructures, thereby neglecting the global topological information and thus overlooking important global topological features of graphs. Third, these kernels obtain kernel values through pairwise comparisons of graphs, lacking the ability to capture the common pattern information over all graph samples. In summary, these drawbacks limit the effectiveness of the existing R-convolution kernels.

2.2 The Graph Auto-encoders

Generally, the Graph Auto-Encoder (GAE) is developed by generalizing the classical Auto-Encoder into the graph domain [Kipf and Welling, 2016], and aims to learn a mapping function to convert node features into the deep latent space. Specifically, the encoder converts graphs into lowdimensional representations, while the decoder attempts to reconstruct the original graphs from the latent representations. Representative methods include a) the Adversarially Regularized Variational Graph Autoencoder (ARVGA) [Pan et al., 2020] that employs a trainable scheme based on the Generative Adversarial Networks (GANs) [Goodfellow et al., 2014], b) the Network Representations with Adversarially Regularized Autoencoders (NetRA) [Yu et al., 2018] where the encoder and decoder are the LSTM networks [Hochreiter and Schmidhuber, 1997] associated with random walks rooted at each node as inputs, etc. Although the existing GAEs have shown their superior performance in link prediction, most of them tend to only reconstruct the structure information (i.e., the adjacency matrix) of graphs and ignore the restoration of the node feature matrix. Thus, these GAEs usually have lower performance for graph classification.

3 The Proposed DHTAGKKernels

In this section, we provide the detailed definition of the proposed DHTAGK kernel associated with the newly developed HA-GAE model. Moreover, we highlight the theoretical advantages of the proposed kernels.

3.1 Preliminaries

We define a graph as G(A,X), where A ∈ {0, 1}n×n is the adjacency matrix, and X ∈ Rn×f is the node feature matrix. In this work, node features are represented either by the onehot encoding of node labels for attributed graphs or by node degrees for unattributed graphs.

To effectively process the graph data, Graph Neural Networks (GNNs) have been widely adopted. GNNs are deep learning models that generate node embeddings by integrating both node features and graph structure. These models typically aggregate the feature information from neighboring nodes to learn meaningful node representations. In this work, we employ the Graph Convolutional Network (GCN) layer [Kipf and Welling, 2017], which is defined as

where ˆ A = IN + D- 12AD- 12 , ˆ A is the adjacency matrix with self-loops, W is the trainable weight matrix, and σ is a non-linear activation function.

3.2 Frameworks of the DHTAGKKernels

This subsection introduces the computational framework of the proposed DHTAGK, shown in Figure 1, consisting of three main computational steps. First, we propose a new HAGAE model (see Section 3.3 for details), which is trained on all sample graphs and achieves the transitive-aligned nodelevel alignment. During the encoding, we hierarchically extract embedding graphs. Second, for pairwise graphs, we extract the transitive-aligned adjacency and node feature matrices of their embedding graphs through the HA-GAE. The DHTAGK kernels (kernel based on the adjacency Matrices (GK-A), kernel based on the node features (GK-X), and the composite kernel (GK-C)) are defined by measuring the kernel-based similarity between the embedding graphs (see Section 3.4 for details). Third, the kernel matrix is input into the C-SVM for graph classification.

3.3 The HA-GAEModel

The proposed HA-GAE model consists of an encoder and a decoder, which hierarchically reduces and restores the graph size. This process enables the capture of both local and global information across subgraphs of different sizes, addressing the limitations of the existing R-convolution graph kernels. Moreover, we train the HA-GAE model on a specific dataset, ensuring that all graphs in the dataset share the same trained node assignment function.

For an original sample graph, the encoder maps the node feature matrix and adjacency matrix to latent representations. Each encoder layer consists of two steps: AssignmentE and Compression. The Assignment-E step clusters nodes with similar latent semantics, while the Compression step combines nodes within the same cluster into a single coarsened node. The decoder mirrors the encoder's structure but the focus is on recovering the original node feature and adjacency matrices. Each decoder layer also involves two steps: Assignment-D and Reconstruction. This selfsupervised learning approach maps the node feature and adjacency matrices into an embedding space, where effective structure representations are learned by minimizing reconstruction errors. Below, we provide a detailed definition of the encoder and the decoder for the HA-GAE model.

The Encoder of the HA-GAE

The architecture of the encoder is shown in Figure 2. The encoder maps input graphs into an embedding space, hierarchically generating a series of transitive-aligned embedding graphs. It consists of K layers. The original sample graph G(A,X) serves as the input at the 0-th layer, represented as G(0) (A(0) ,X(0) ). At the l-th layer (l ∈ {0, . . . ,K - 1}), the encoder transforms the embedding graph G(l) (A(l) ,X(l) ) into the (l + 1)-th layer embedding graph G(l+1) (A(l+1) , X(l+1) ), where A(l) ∈ Rnl×nl , X(l) ∈ Rnl×dl , A(l+1) ∈ Rnl+1×nl+1 , X(l+1) ∈ Rnl+1×dl+1 . Here, n(·) represents the number of nodes, and d(·) represents the dimension of node features at each layer. Each encoder layer involves two operations: Assignment-E and Compression.

Assignment-E: In this step, nodes are assigned to different clusters. We compute the node assignment matrix S(l) ∈ Rnl×nl+1 using a GNN model GNNassign with input (A(l) , X(l) ) followed by a Softmax function. The element S(l) i,j represents the probability that node i at layer l is assigned to cluster j at layer l + 1. The computation is defined as

Compression: In this step, nodes belonging to the same cluster are compressed into a new coarsened node. First, we compute the node embedding matrix Z (l) ∈ Rnl×dl+1 by a GNN layer GNNembed, defined as

Next, using the assignment matrix S(l) , we compress the nodes by performing similar operations to the DiffPool [Ying et al., 2018], i.e.,

After K layers, the embedding graph G(K) (A(K) ,X(K) ) from the final layer is passed to the decoder. By gradually reducing the number of clusters at each layer, the encoder helps abstract and aggregate node information into fewer nodes, thereby achieving a hierarchical transition from local to global information.

The Decoder of the HA-GAE

The architecture of the decoder is shown in Figure 3. The decoder reconstructs the original graph structure by probabilistically expanding each coarsened node into its corresponding nodes. The decoder also consists of K layers. At the l-th layer, it reconstructs the l-th embedding graph ˆG(l) ( ˆ A(l) , ˆX(l) ) from the (l + 1)-th layer's graph ˆG(l+1) ( ˆ A(l+1) , ˆX(l+1) ). Here, ˆ A and ˆX represent the reconstructed adjacency and node feature matrices. To maintain a consistent layer index, the layer indices in the decoder decrease sequentially. Similar to the encoder, each layer consists of two steps: Assignment-D and Reconstruction.

Assignment-D: A GNN layer GNNr assign is used to compute the reconstructed assignment matrix ˆ S(l) ∈ Rnl×nl+1 as

Reconstruction: We compute the reconstructed node embedding matrix ˆ Z (l) ∈ Rnl×dl+1 as

Based on ˆ Z (l) , we perform the matrix computations to obtain the reconstructed embedding graph ˆG(l) ( ˆ A(l) , ˆX(l) ) as

After K decoding layers, we obtain the resulting reconstructed graph of the original sample graph ˆG(0) ( ˆ A(0) , ˆX(0) ) that is first input to the encoder of the HA-GAE.

The Loss Function of the HA-GAE

We train the HA-GAE model by minimizing its reconstruction error, and the loss function is defined as

Here, MSE denotes the mean squared error function. Since we cannot directly generate binary values using graph convolution operations, we use this loss function to ensure that the reconstructed graph structures closely approximate the structures of the original graphs.

Remark 2: Each layer of the HA-GAE model uses the same node assignment information computed by Eq.(2) and Eq.(5). Therefore, the nodes at the same layer of the embedding graphs are transitive-aligned to each other, meaning that the j-th node in graph G naturally corresponds to the jth node in graph G′ . This alignment naturally facilitates the definition of the transitive-aligned graph kernels by measuring the similarity between graphs.

3.4 Construction of the DHTAGKKernels

In this subsection, we define the proposed DHTAGK kernels. During the HA-GAE training, for each original graph G, we hierarchically generate a series of transitive-aligned embedding graphs {G(l) (A(l) , X(l) ), l ∈ {0, ..., K - 1}} in the encoder. For a pair of original graphs G and G′ with different numbers of nodes, their embedding graphs G(l) and G′(l) not only have the same number of nodes but are also transitivealigned in terms of node correspondences. Using the adjacency and node feature matrices of these embedding graphs, we define three DHTAGK kernels.

The DHTAGK based on Adjacency Matrices (GK-A)

Inspired by [Bai et al., 2015b], we define the GK-A kernel by measuring the similarity between the adjacency matrices of the embedding graphs using the Jensen-Shannon Divergence (JSD). Specifically, for each l-th layer embedding graph G(l) , we compute the node probabilities as

Here, P (l) (vi) represents the probability of node vi at layer l, and d(l) (vi) represents the degree of node vi at layer l. For graphs G(l) and G′(l) , the GK-A kernel kA is defined as

where each k(l) A (G(l) ,G′(l) ) is the kernel measure between their l-layer embedding graphs G(l) and G′(l) defined as

Here D(l) JS (G(l) , G′(l) ) is the JSD measure defined as

where H(·) represents Shannon entropy associated with the node distribution P (l) (vi).

Remark 3: Unlike other similarity measures such as Euclidean distance and cosine similarity, the JSD offers an information-theoretic perspective by quantifying the probability of Steady-State RandomWalks visiting nodes, thus capturing the structural information content of graphs. Since the alignment property allows the node indices to naturally correspond to each other, we can directly use JSD to measure the differences between the probabilities of pairwise graphs, effectively capturing structural discrepancies between graphs.

The DHTAGK based on Node Feature Matrices (GK-X)

We define the GK-X kernel by measuring the Gaussian kernel-based similarity between the node feature matrices of the embedding graphs. For the pair of sample graphs G and G′ , the GK-X kernel kX is defined as

where each k(l) X (G(l) ,G′(l) ) is the Gaussian kernel between the node feature matrices X(l) and X′(l) , which is defined as

Here, ∥X(l) -X′(l) ∥ is the Euclidean distance between the node feature matrices X(l) and X′(l) . σ is a parameter to control the width of the Gaussian graph kernel.

The Composite DHTAGK (GK-C)

We define the GK-C kernel by summing the kernels GK-A and GK-X. For the pair of sample graphs G and G′ , the GKC kernel kC is defined as

Clearly, unlike the proposed GK-A and GK-X kernels, the GK-C kernel can simultaneously capture the structural information through either the adjacency matrix or the node feature matrix, preserving richer structural characteristics.

Remark 4: As stated in Remark 2, for any pair of sample graphs, the adjacency matrices and the node feature matrices of their embedding graphs extracted from the HA-GAE are transitively aligned. Since the exponentiation of the negative JSD-based measure for the GK-A kernel as well as the Gaussian kernel-based measure for the GK-X kernel are both positive definite (pd) measures, the resulting GK-A and GK-X kernels based on the transitive aligned structure representations are naturally pd. Thus, the GK-C kernel, as the sum of pd kernels, is also pd.

3.5 Properties of the DHTAGKKernels

In this subsection, we discuss the theoretical properties of the proposed DHTAGK kernels, explaining the effectiveness.

First, unlike the R-convolution kernels, which focus on small substructures, the proposed DHTAGK kernels are defined based on embedding graphs that progressively shrink in size, from the larger original global graph to the smaller coarsened embedding graph. This gradual reduction in the size of the embedding graphs helps us abstract graph information layer by layer, enabling the capture of both global and local structural information simultaneously. Since the HAGAE can use all sample graphs for training, the DHTAGK kernels can capture the common structural patterns shared across all graphs. In contrast, the R-convolution kernels only capture information between individual graph pairs.

Second, unlike the R-convolution graph kernels that overlook the structural correspondence information between graphs, the proposed DHTAGK kernels are computed by measuring the similarity between the aligned adjacency matrices and the aligned node feature matrices of the embedding graphs that are constructed by the HA-GAE through the node assignment operation. Thus, the proposed DHTAGK kernels can naturally encapsulate the structural correspondence information through the aligned structure matrices.

Third, most existing matching-based graph kernels suffer from the non-transitive alignment relationships and cannot guarantee the positive definiteness. By contrast, the associated HA-GAE utilizes the same node alignment function to identify the correspondence between nodes of all graphs, and only the nodes assigned to the same cluster can be considered aligned. Thus, the DHTAGK kernels defined based on the transitive-aligned embedding graphs of HA-GAE are transitive-aligned and naturally pd.

4 Experiments

In this section, we evaluate the proposed DHTAGK kernels on eight benchmark graph classification datasets from the domains of bioinformatics (Bio) and social networks (SN). Details of these datasets are shown in Table 1.

Experimental Settings 1 : We set the number of layers for both the HA-GAE encoder and decoder to 3-5. In each layer, the number of nodes in the embedding graph decreases layer by layer according to an assignment ratio 0.5. The feature dimension of the embedding graph is fixed at 32 dimensions. After training the HA-GAE, we input the graph data into the trained HA-GAE to obtain hierarchically aligned embedding graphs, and then compute the GK-A, GK-X, and GK-C graph kernel matrices. Finally, we use the C-SVM implemented by LIBSVM for 10-fold cross-validation and calculate the classification accuracy. We repeat the experiment 10 times and report the average classification accuracy and standard error.

To evaluate the capability on graph classification tasks, we compare our graph kernels with several advanced graph kernels and GNNs. Specifically, the graph kernels include: 1) the RWGK [Gartner et al., 2003], 2) GK [Shervashidze et al., 2009], 3) WLSK [Shervashidze et al., 2011], 4) JTQK [Bai et al., 2014] (with q = 2), 5) ASK [Bai et al., 2015a], 6) CORE WL & CORE SP [Nikolentzos et al., 2018], 7) EDBMK [Xu et al., 2021], and 8) QBMK [Bai et al., 2024]. The deep learning methods include five baselines: 1) the DGCNN [Zhang et al., 2018], 2) DiffPool [Ying et al., 2018], 3) ECC [Simonovsky and Komodakis, 2017], 4) GIN [Xu et al., 2019], and 5) GraphSAGE [Hamilton et al., 2017]; and six advanced GNNs: 1) the DGK [Yanardag and Vishwanathan, 2015], 2) p-RWNN [Nikolentzos and Vazirgiannis, 2020] (with p = 1, 2, 3), and 3) GKNN WL & GKNN GL [Cosmo et al., 2024].

The classification accuracy and standard error for each graph kernel method are reported in Table 2, since the alternative kernels are evaluated with the same setup, we directly use the accuracies from the corresponding literature. The results for each deep learning method are shown in Table 3. For the baseline deep learning methods, we adapt the results from the fair comparison [Errica et al., 2020]. For other GNNs, we report the best results from original papers. The Rank column in Table 2 and Table 3 shows the mean rank of each method.

1 Code is available at our GitHub repository: https://github.com/Xiaoqin0421/DHTAGK

Experimental Analysis: The experimental results show that the DHTAGK kernels outperform most graph kernel methods and achieve classification performance comparable to deep learning approaches. While the WLSK and JTQK kernels, as well as deep learning methods, utilize nodelabel information during training, our method adopts a selfsupervised learning strategy for training the HA-GAE. Despite using a shallow learning framework via the C-SVM, the DHTAGK kernels achieve superior performance across most datasets compared to the end-to-end models. This indicates that the autoencoding process effectively captures more informative topological features compared to other approaches. The effectiveness of the DHTAGK kernels is fourfold.

First, unlike the traditional R-convolution kernels, the DHTAGK kernels leverage a hierarchical approach to simultaneously capture both local and global structural information, resulting in superior expressive power. Second, unlike the traditional R-convolution kernels and deep learning approaches, the DHTAGK kernels ensure precise node correspondences at various levels through their hierarchical alignment mechanism. This allows for a more comprehensive capture of the structural features. In contrast, other models often struggle to accurately identify substructure correspondences within complex graphs, leading to suboptimal performance. Third, compared to the ASK kernel, the correspondence information identified by the DHTAGK kernels is transitive. By contrast, the ASK kernel cannot guarantee the transitivity. Fourth, the DHTAGK kernels excel in extracting shared structural information across graph samples. Unlike other classical graph kernel methods, which typically focus on pairwise similarities, our kernels aggregate information from all samples, capturing a broader range of structural patterns. This comprehensive feature extraction results in a more detailed representation of the graph structure, making the DHTAGK particularly effective for complex datasets.

Ablation Study. We compare the performance of the GKA, GK-X, and GK-C, and attribute the differences to the distinct types of graph information they capture. Specifically, the GK-A emphasizes global structural information through adjacency matrices, yielding better results on datasets with prominent structural characteristics, such as the MUTAG. However, the GK-A does not consistently achieve optimal performance, as it fails to incorporate node attribute information. In contrast, the GK-X focuses on node features and performs better on datasets rich in attribute information, such as the PTC MR. Finally, the GK-C integrates both structural and feature information, enabling it to capture graph characteristics more comprehensively.

Hyperparameter Analysis. We investigate the impact of the number of auto-encoder layers and the embedding graph assignment ratio using the PROTEINS dataset. Figure 4 and Figure 5 show the classification accuracy of the GK-A, GKX, and GK-C at different layers and assignment ratios.

Impact of the Layers. As the number of layers increases, the classification accuracy of the GK-A, GK-X, and GK-C improves. The GK-A performs better with fewer layers, due to its ability to capture local node and neighborhood information at shallow levels. When the model reaches three layers, the GK-C outperforms the GK-A, as it offers a more comprehensive representation in both structure and features.

Impact of the Ratio. It can be seen in Figure 5 that an assignment ratio of 0.5 ensures that the size of the embedding graph is moderate, balancing local and global information. Specifically, a smaller assignment ratio leads to small embedding graphs, causing over-squashing and information loss. A larger assignment ratio may cause the graph kernel to focus more on large-scale structures, potentially neglecting fine-grained local information, and the slower reduction in the size of the embedding graph decreases computational efficiency. Therefore, choosing a moderate assignment ratio of 0.5 achieves a good balance between local and global information, and enhances computational efficiency.

Visualization. Figure 6 shows several molecular graphs from the MUTAG dataset, where nodes with the same color are aligned to the same cluster. The experimental results demonstrate that the HA-GAE effectively captures meaningful node correspondence information, such as ring structures and functional groups commonly found in molecular graphs.

5 Conclusion

In this paper, we have proposed a novel family of DHTAGK kernels for graph classification. The DHTAGK kernels are defined based on the transitive-aligned adjacency and node feature matrices of the hierarchical embedding graphs extracted from the newly developed HA-GAE model. These kernels not only overcome the issue of ignoring structural correspondences between substructures in the existing Rconvolution kernels, but also address the non-positive definiteness problem in node-based alignment kernels. Furthermore, we reflect both local and global graph characteristics, and capture the structural patterns across all graphs, through the HA-GAE. Experiments demonstrate the effectiveness of the proposed kernels. In future work, we plan to explore additional forms of transitive alignment information produced by the HA-GAE to design new graph kernels. We also intend to develop a mechanism for adaptively computing the weights of the GK-A and GK-X kernels.

Acknowledgments

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.