Deep Hierarchical Graph Alignment Kernels

1 Introduction

Over the past decades, more and more data in studies depicting relationships between objects cannot be simply interpreted as vectors or tables. Instead, they are naturally represented by graphs. In order to capture the inherent information from graph-structured data, many graph-based machine learning algorithms are gaining attraction.

Graph kernels (GKs) [Vishwanathan et al., 2010] are conventional methods for measuring the similarity of graphs by kernel method defined on graphs. Most graph kernels are instances of R-convolution theory [Haussler and others, 1999]. These methods decompose graphs into non-isomorphic substructures (e.g., paths or walks, subgraphs, subtrees) and compare them. Graph similarity is the sum of all the substructure similarities. However, the computation of the substructure similarity is strict, i.e., all non-isomorphic substructures are treated as dissimilar ones, which impedes the precise comparison of graphs. In addition, R-convolution graph kernels neglect the topological position information between substructures, which plays a crucial role in the characteristic of the whole graph, e.g., whether or not a drug molecule is effective on a disease.

∗ Corresponding author.

We show the 2D representations of three molecules in Figure 1 to explain the importance of precise substructure similarity comparison and their relative topological positions. Aspirin (Figure 1 (a)) and 3-Acetoxybenzoic acid (Figure 1 (b)) have the same benzoic and acetyloxy substructures, but the former is commonly used in drugs for the treatment of pain and fever, while the latter is not. The difference in the relative topological positions of these two substructures causes the different molecule characteristics. R-convolution graph kernels are difficult to distinguish the two molecules because they are unaware of the substructure topological position information. Aspirin and Acetaminophen (Figure 1 (c)) have similar substructures acetylamino and acetyloxy (only a little bit of difference in the atoms), they are both used for pain and fever. However, R-convolution graph kernels cannot precisely compute the similarity between these similar substructures from them.

Many graph kernels try to alleviate these problems in different ways. WWL [Togninalli et al., 2019] embeds graph substructures (WL [Shervashidze et al., 2011] subtree patterns) into continuous vectors and compares their distributions by leveraging the Wasserstein distance. The use of optimal transport in WWL implicitly aligns WL subtree patterns from different graphs, thus addressing the neglect of the topological position information between WL subtree patterns. But WWL has high computational overhead and is not positive semi-definite, since the optimal transport is not guaranteed to satisfy the transitivity. In other words, if σ is the alignment between substructures from graphs G1 and G2 and π is the alignment between substructures from graphs G2 and G3, the optimal transport cannot guarantee that the alignment between substructures from graphs G1 and G3 is σ ◦ π. GAWL [Nikolentzos and Vazirgiannis, 2023] is a positive semi-definite graph alignment kernel that explicitly aligns WL subtree patterns by comparing their labels refined by the Weisfeiler-Leman graph isomorphism test [Leman and Weisfeiler, 1968]. However, with more iterations of the WLrelabeling process, it is more difficult to align since all the WL subtree patterns tend to have different labels.

To mitigate the above problems, we propose a new graph kernel called Deep Hierarchical Graph Alignment Kernels (DHGAK). Specifically, we define a new graph substructure named b-width h-hop slice around a node to capture the structural information. Then, we embed each slice into a deep vector space by Natural Language Models (NLM) for precise comparison. In the deep embedding space, we propose a Deep Alignment Kernel (DAK) that aligns slices from the same or different graphs by computing the expectation of the cluster assignments of the adopted clustering methods. Slices from the same cluster are aligned while those from different clusters are unaligned. We prove that the alignment by clustering in DAK satisfies the transitivity. By assuming the feature maps of DAK in one graph are i.i.d. (independent and identically distributed) samples of an unknown distribution, we adopt the kernel mean embedding [Muandet et al., 2017] to construct Deep Graph Alignment Kernel (DGAK) from a distributional perspective. With the summation of DGAK on each hop of b-width slice, we exploit hierarchical graph structural information and finally get our Deep Hierarchical Graph Alignment Kernels (DHGAK). All the three kernels, i.e., DAK, DGAK, and DHGAK, are positive semi-definite. It is theoretically demonstrated that there exists a family of clustering methods derived from which the feature map of our proposed DHGAK is linearly separable for any dataset in the Reproducing Kernel Hilbert Space (RKHS).

Our contributions are summarized as follows:

• We propose a generalized graph alignment kernel DHGAK that can use any NLM to generate deep embeddings of substructures and any clustering methods to align substructures. DHGAK can more precisely compute graph similarity compared to conventional Rconvolution graph kernels by not only taking into account the distributions of substructures but also their topological position information in graphs.
• We prove that DHGAK is positive semi-definite and satisfies alignment transitivity. Theoretical analysis proves that the feature map of DHGAK produced by certain clustering methods is linearly separable in the RKHS.
• We compare DHGAK with state-of-the-art graph kernels on various benchmark datasets and the experimental results show that DHGAK has the best classification accuracy on most datasets.

2 RelatedWork

Weisfeiler-Lehman graph kernel (WL) [Shervashidze et al., 2011] quantifies graph similarity by calculating the number of common labels (subtree patterns) between two graphs at each iteration of the WL-relabeling process (WeisfeilerLehman graph isomorphism test [Leman and Weisfeiler, 1968]), which however diverges too fast and leads to coarse graph similarity. Wasserstein Weisfeiler-Lehman graph kernel (WWL) [Togninalli et al., 2019] extends WL to graphs with continuous node attributes. It uses Wasserstein distance to measure the distance between graphs but the cost of computation is very expensive. Gradual Weisfeiler-Lehman (GWL) [Bause and Kriege, 2022] introduces a framework that allows a slower divergence of the WL relabeling process. GAWL [Nikolentzos and Vazirgiannis, 2023] initiates the alignment of nodes across distinct graphs based on their shared labels, determined by the WL-relabeling process. It becomes difficult for node alignment if the iteration number of the WL-relabeling process increases.

Shortest Path graph kernels (SP) [Borgwardt and Kriegel, 2005] quantify graph similarity by evaluating the shortest paths that have the same labels of the source and sink nodes and the same length between all node pairs within two graphs. However, the shortest path representation is too simple and may lose information. Tree++ [Ye et al., 2019] and MWSP [Ye et al., 2023] extract the multi-scale shortest-path features in the BFS tree rooted at each node of graphs. RetGK [Zhang et al., 2018] represents each graph as a set of multidimensional vectors consisting of return probability resulting from random walks starting and ending at identical nodes. The embedding in the RKHS is achieved via Maximum Mean Discrepancy (MMD) [Gretton et al., 2012].

Beyond the graph kernels mentioned above, assignment kernels have attracted the attention of scholars. The main idea is to compute an optimal matching between the substructures of each graph pair, reflecting the graph similarity. WL-OA [Kriege et al., 2016] first designs some base kernels to generate hierarchies and then computes the optimal assignment kernels. Such kernels are guaranteed to be positive semi-definite. PM [Nikolentzos et al., 2017] adopts the Pyramid Match kernel [Lazebnik et al., 2006] to find an approximate correspondence between two graph embeddings (the eigenvectors of graph adjacency matrix). HTAK [Bai et al., 2022] computes the H-hierarchical prototype representations and hierarchically aligns the nodes of each graph to their different h-level (1 ≤ h ≤ H) prototypes. However, HTAK can only work for un-attributed graphs.

Other graph kernels are as follows. Graph Neural Tangent Kernels (GNTKs) [Du et al., 2019], which correspond to infinite-width multilayer Graph Neural Networks (GNNs) trained by gradient descent, have the same rich expressiveness as GNNs and inherit the advantages of graph kernels. Graph Quantum Neural Tangent Kernel (GraphQNTK) [Tang and Yan, 2022], a novel quantum graph learning model, is designed to capture structural information and exploit quantum parallelism for computational efficiency. The model approximates the underlying GNTKs by introducing a multi-head quantum attention mechanism. Although both GNTK and GraphQNTK exploit the high expressiveness of GNNs, they suffer from the overparameterization and overfitting issues of GNNs on small graphs.

3 The Model

DHGAK defines graph kernels by hierarchically aligning relational substructures to cluster distributions. The framework of DHGAK is presented in Figure 2. Specifically, Section 3.1 introduces the notations used in this paper; Section 3.2 describes how to encode a slice into a unique sequence and then embed it into a deep vector space via Natural Language Models (NLM); In Section 3.3, the Deep Alignment Kernel (DAK) is defined and the feature map of DHGAK is obtained in a distribution perspective; Section 3.4 gives the theoretical analysis of DHGAK.

3.1 Notation

The notations used in this paper are as follows. We consider undirected and labeled graphs. Given a graph dataset D = {G1, ..., GN}, graph Gi = (Vi, Ei, l), where Vi and Ei are the sets of nodes and edges of graph Gi, respectively. l : Vi →Σ is a function that assigns labels in the label alphabet Σ to nodes. For the graph classification problem, each graph Gi is assigned a class label yi ∈ {1, 2, . . . , c} (c is the number of classes).

3.2 Hierarchical Neighborhood Structure Encoding

First, we define the b-width h-hop slice of a node as follows: Definition 1 (b-width h-hop Slice of Node). Given an undirected graph G = (V, E), rooted at each node v ∈ V, we build a truncated BFS tree Tv of depth r. All the nodes in Tv denoted as N r (v) and all the leaf nodes (nodes in the rth depth) in Tv denoted as Nr(v) are defined as the r-width and the r-hop neighbors of v, respectively. Then, the b-width h-hop slice of v can be defined as N bh (v) = ⋃u∈Nh(v) N b (u).

It is worth noting that when b = 0 the b-width neighbor of each node v ∈ V is the node itself, which is also equivalent to its b-hop neighbor, i.e., N 0 (v) = N0(v) = {v}. In Figure 3 (a), we set the slice width b as 0 and vary the slice hop h from 0 to 2. Then we get the 0-width 0-hop slice, 0-width 1hop slice and 0-width 2-hop slice of v1, i.e., N 0 0 (v1), N 0 1 (v1) and N 0 2 (v1), which capture the neighborhood structure information of v1 in different hierarchies. In Figure 3 (b), we show that the 1-width 1-hop slice N 1 1 (v1) of node v1 is the union set of N 1 (v2), N 1 (v3), and N 1 (v4).

Then, we encode each slice into a unique sequence Sbh (v). Given width b and hop h, for each node v in the graph, we find its h-hop neighbors Nh(v) and sort them by their eigenvector centrality (EC) [Bonacich, 1987] values in descending order. For each node u in the sorted Nh(v), we concatenate the nodes in its i-hop neighbors Ni(u), sorted by EC in descending order to get Si(u). Then, we concatenate Si(u) from i = 0 to b to obtain Sb (u). The encoding of slice Sbh (v) is the concatenation of Sb (u) for all the nodes u in Nh(v). Finally, each node in the encoding of the slice is assigned a label by applying l(·). For example, in Figure 3 (a), S0 1 (v1) = l([v4, v3, v2]); and in Figure 3 (b), S1 1 (v1) = l([v4, v9, v1, v10, v5] ∥ [v2, v1, v8, v7] ∥ [v3, v1, v5, v6]), where ∥ concatenates different Sb (u). The pseudo-code is given in Algorithm 1 in B.1 1 .

In R-convolution graph kernels, the similarity value between each pair of slices is one (if they have the same encoding) or zero (if they have different encodings even the difference is just a little bit). This strict comparison does not consider the fact that there exists some similarity even in two slices that have different encodings. Several studies [Perozzi et al., 2014; Yanardag and Vishwanathan, 2015a] have shown that the substructures in graphs follow a power-law distribution, just like the word distribution in natural language. Thus, to circumvent the above difficulty, we generate a deep embedding for each slice to soften the strict similarity comparison and to compute slice similarity more accurately by employing Natural Language Models (NLM).

More specifically, given a slice encoding, we consider each node label in the encoding as a word and the whole encoding as a sentence. Then an NLM can be trained to learn the embedding of each node label. We define the deep embedding of a slice as follows:

Definition 2 (Deep Slice Embedding). Given a label embedding function (learned by NLMs) g : Σ → Rd , where d is the dimension of the embedding. The embedding of a b-width h-hop slice of node v is defined as follows:

where xb0 (v) := g(l(v)), α is a decay coefficient of the (h - 1)-th hop's node label embedding and Sbh (v) is the encoding of the b-width h-hop slice of node v.

3.3 Deep Hierarchical Graph Alignment Kernels

To consider the topological position information of slices, we propose to align slices from different graphs by clustering in their deep embedding space. Slices within the same cluster are aligned and have the same feature map. This not only addresses the neglect of the topological position information of substructures in conventional R-convolution graph kernels but also reduces the computational overhead since comparison will only be carried out on slices from different clusters. We first define the Deep Alignment Kernel as follows:

1 All appendices can be found in the Arxiv version of this paper.

Definition 3 (Deep Alignment Kernel (DAK)). Let Ψ ⊂ M be an arbitrary set of clustering methods chosen from all admissible clustering methods M. Let U(Ψ) denote a uniform distribution on Ψ. For any clustering method ψ : Xbh → Cψ in Ψ, it separates each point (b-width h-hop slice embedding) x ∈ Xbh into one of |Cψ| clusters, i.e., Cψ = {Cψ,1, Cψ,2, . . . , Cψ,|Cψ|}. The Deep Alignment Kernel quantifies the likelihood of assigning two points (slice embeddings), x, y ∈ Xbh , to the same cluster across all clustering methods in the set Ψ, which is defined as follows:

Given that many clustering methods (e.g., K-means [MacQueen and others, 1967]) heavily rely on the initialization points, we perform each clustering method T times to approximate the expectation. The approximation is defined as:

where I(a) is the indicator function that I(a) = 1 if a is true, otherwise I(a) = 0. C (t) ψ,i represents the i-th cluster at the t-th experiment under clustering method ψ.

Theorem 1. DAK is positive semi-definite.

With Theorem 1 (see A.1 for the proof), we can define explicit feature maps in the Reproducing Kernel Hilbert Space (RKHS) H for the DAK as follows:

Definition 4 (Feature Map of DAK). Given the embeddings Xbh of b-width h-hop slices, let 1(t) ψ : Xbh → {0, 1}|C(t) ψ | be a cluster indicator of clustering method ψ at the t-th experiment. For any x ∈ Xbh , 1(t) ψ (x)i = 1 if and only if x ∈ C (t) ψ,i ∈ C (t) ψ , otherwise 1(t) ψ (x)i = 0. Then, the feature map ϕbh of the DAK after T experiments is defined as:

where ∥ means concatenation, ϕbh (x) ∈ RT(∑ψ∈Ψ |Cψ|) represents the concatenation of all 1(t) ψ (x) for T experiments of ψ in the clustering method set Ψ.

Therefore, Equation 3 can be rewritten as:

Note that Equation 5 can directly compute the similarity between two slices extracted around two nodes residing in the same or different graphs. We extract the b-width h-hop slices around all the nodes in each graph. For the feature maps of DAK in each graph, we treat them as i.i.d. samples from an unknown distribution. Next, we utilize kernel mean embedding [Muandet et al., 2017] to construct the Deep Graph Alignment Kernel (DGAK) between two graphs G1 and G2 from the perspective of distribution as follows:

where Xbh and Ybh are the deep embeddings of b-width h-hop slices in graphs G1 and G2, respectively.

Finally, our Deep Hierarchical Graph Alignment Kernel (DHGAK) is defined as follows:

Since the sum of positive semi-definite kernels is also positive semi-definite, both DGAK and DHGAK are positive semi-definite.

3.4 Theoretical Analysis of DHGAK

We explicit the transitivity of alignment operation in DAK, DGAK, and DHGAK at first. Given the set of clustering method Ψ, experiment times T ∈ N and x, y ∈ Xbh . Let the Mb,t h,ψ : Xbh ×Xbh → {0, 1} be the alignment operation at the t-th experiment under ψ ∈ Ψ , which satisfies:

(8)

Therefore, DAK can be re-expressed as:

DGAK and DHGAK can also be re-expressed in the sum of alignment operations. The theorem (See A.2 for the proof) below shows the alignment operation is transitive.

Theorem 2. The alignment operationMb,t h,ψ in DAK, DGAK and DHGAK is transitive.

Secondly, we care about the feasibility of using kernel mean embedding in Equation 6. We treat the feature maps of DAK in each graph as i.i.d. samples from an unknown distribution G and take kernel mean embedding of them to construct DGAK and DHGAK. When considering distribution classification tasks, Distributional Risk Minimization (DRM) [Muandet et al., 2012] assures that any optimal solutions of any loss function can be expressed as a finite linear combination of the mean embedding of G1, . . . ,GN. DRM guarantees the feasibility of graph kernels derived by kernel mean embedding for graph classification problems.

Finally, Theorem 3 is introduced to assure that there exist some sets of clustering methods Ψo ⊂ M, derived from which the feature map of DHGAK is linearly separable in its RKHS for any dataset.

Theorem 3 (Linear Separation Property of DHGAK). Given a graph dataset D = {(Gi, yi)}Ni=1 , let Ψo denote the set of clustering method {ψj }|Ψo| j=1 , where ψj : Xbh → Cψj separates each point xbh (the embedding of a slice extracted around a node v) to the cluster Cψj,k if and only if v ∈ Vk belonging to Gk. For any H, T ∈ N, the feature map of DHGAK is linearly separable for one class graphs {(Gp, yp)} from the other class graphs {(Gq, yq) : yq ̸= yp}.

The proof of Theorem 3 is given in A.3. It's worth noticing that Ψo is only utilized for theoretical derivations. In addition, the theorem offers a rough estimator for the number of clusters, denoted as |Cψ| ≃ |D|. This estimation is useful for the detailed implementations of DHGAK.

The worst-case time complexity of DHGAK is bounded by O(HN(n2+ne)×TNLM+HT |Ψ|×TC(Nn)), where TNLM is the inference time complexity of the NLM per token, n, e are the average number of nodes and edges in graphs, and TC(Nn) is the average time complexity of the clustering methods we select. Refer to Appendix B.3 for a more detailed analysis of the time complexity of DHGAK.

In short, DHGAK is proven to be alignment transitive, and theoretically, for any dataset, there exists a family of clustering methods derived from which DHGAK's feature maps are linearly separable in the RKHS.

4 Experimental Evaluation

In this section, we analyze the performance of DHGAK compared to some state-of-the-art graph kernels. First, we give the experimental setup and introduce two realizations of DHGAK. Next, we demonstrate the performance of DHGAK on graph classification, the parameter sensitivity analysis of DHGAK, and the ablation study to reveal the contribution of each component in DHGAK. Finally, we compare the running time of each graph kernel.

4.1 Experimental Setup

The generalization of DHGAK allows one to use any combination of Natural Language Models (NLM) for deep embedding and clustering methods for alignment to implement DHGAK. The NLMs we select are BERT [Devlin et al., 2018] and word2vec [Mikolov et al., 2013], and the clustering method we use is K-means. By doing so, we get two realizations of DHGAK: DHGAK-BERT and DHGAK-w2v. See C.2 and D.2 for more details of the NLMs and realizations.

We evaluate DHGAK on 16 real-world datasets downloaded from [Kersting et al., 2016]. For datasets without node labels, we use the degree of each node as its node label. More details about datasets are provided in C.1. All experiments were conducted on a server equipped with a dual-core Intel(R) Xeon(R) Gold 6226R CPU @ 2.90GHz, 256 GB memory, and Ubuntu 18.04.6 LTS with 6 RTX 3090 GPUs.

The parameters of DHGAK are set as follows. As discussed in Theorem 3, we set the number of clusters for different hops h as the same, around the size of the graph dataset, i.e., |Cψ| = |D| × clusters factor, where the clusters factor are searched as base-10 log scale. We fix the experiment times T to 3 and other parameters are gridsearched as shown in Table 2 via 10-fold cross-validation on the training data.

We compare DHGAK with 9 state-of-the-art graph kernels, i.e., PM [Nikolentzos et al., 2017], WL [Shervashidze et al., 2011], WWL [Togninalli et al., 2019], FWL [Schulz et al., 2022], RetGK [Zhang et al., 2018], WL-OA [Kriege et al., 2016], GWL [Bause and Kriege, 2022], GAWL [Nikolentzos and Vazirgiannis, 2023], and GraphQNTK [Tang and Yan, 2022]. The parameters of these methods are set according to their original papers and implementations. We use the implementation of PM, WL, and WL-OA from GraKeL library [Siglidis et al., 2020]. All kernel matrices are normalized as K(i, j) = K(i, j)/√K(i, i)K(j, j). We use 10-fold cross-validation with a binary C-SVM [Chang and Lin, 2011] to test the classification performance of each graph kernel. The parameter C for each fold is independently tuned from {10-3 , 10-2 , . . . , 104 } using the training data from that fold. We report the average classification accuracy and standard deviation over the 10-fold.

4.2 Classification Results

Classification Accuracy

The classification accuracy results of two realizations of DHGAK (DHGAK-BERT and DHGAK-w2v) are shown in Table 1. On 16 datasets, both DHGAK-BERT and DHGAKw2v show superior performance compared to all the competitors on 14 datasets except DD and NCI1. For small datasets (datasets above ENZYMES in Table 1), DHGAK-BERT and DHGAK-w2v outperform all the baselines on all the datasets. For large datasets (datasets below PROTEINS in Table 1), DHGAK-w2v shows a slight drop in classification accuracy and is comparable to GAWL; while DHGAK-BERT outperforms all baselines on these datasets except DD and NCI1, where it secures the second-best performance. More specifically, DHGAK significantly outperforms some baselines on some datasets. For example, on DHFR, PTC MM, PTC FR, and ENZYMES, DHGAK exhibits absolute improvements of 1.8%, 1.8%, 3.2%, and 4.9%, respectively, over other methods. Overall, DHGAK achieves the best performance on 14

of 16 datasets and the second best performance on DD and NCI1.

Parameter Sensitivity

In this section, we study the parameter sensitivity of DHGAK. The parameters are: the number of clusters |Cψ| = |D| × cluster factor, the maximum hop H, the slice width b, decay weight α ∈ [0, 1] and experiment times T (See D.1). We run DHGAK-BERT with 3 fine-tuned epochs on four datasets DHFR, PTC FR, KKI, and IMDB-B from different categories.

With b fixed to the best parameter in each dataset, and α fixed to 0.6, we draw the heatmap of average classification accuracy over the 10 folds for all combinations of H ∈ {1, 3, . . . , 9} and cluster factor varying from 0.1 to 2 in base 10 log scale. In Figure 4, We can observe that DHGAKBERT behaves stably across various parameter combinations, consistently achieving high performance.

Then we fix H and |Cψ| to the best parameter, and vary b ∈ {0, 1, 2, 3} and α ∈ {0, 0.2, 0.4, 0.6, 0.8, 1}. Figure 5 shows the heatmap for all combinations of b and α. As can be seen, the best classification accuracy may be achieved when using values from the set {0, 1, 2} for b, with α approximately around 0.6. For the IMDB-B dataset, when α is fixed, increasing b beyond 2 does not improve the performance. The reason is that, for datasets with a large number of edges in the graph, the encoding of slice can easily exceed the input sentence length limit (the token size) of BERT, leading to a truncation of encoding. Exploiting Large Language Models (LLM) such as GPT4 is left for future work.

4.3 Ablation Study

In this section, we compare DHGAK-BERT to its three variants: HGAK-label, DGAK-BERT, and DHW-BERT. HGAKlabel is a graph kernel whose label embedding function g defined in Definition 2 is one-hot node label mapping. DGAKBERT is a graph kernel whose deep embeddings are learned from the nodes' (H + b)-depth truncated BFS trees, not from hierarchical slices. DHW-BERT uses the 1-Wasserstein distance instead of using DAK and DGAK, whose kernel matrix is computed by summing the Laplacian kernel of 1Wasserstein distances between graphs for each hop. The average classification accuracy via 10-fold cross-validation of them is given in Table 3.

The effectiveness of each component in DHGAK is demonstrated in the table. Comparisons between the performance of the three ablation variants show that HGAKlabel ranks the first, indicating that the deep embedding captures the neighborhood information of slice better than direct one-hot encoding. DHW-BERT ranks the second, indicating that DAK has a better ability to capture the inherent connections of slices compared to the Wasserstein distance. Finally, DGAK-BERT exhibits the lowest performance, suggesting that the slice structure we introduced significantly contributes to the model performance of DHGAK compared to the common BFS trees.

4.4 Running Time

In Table 4, we demonstrate the running time (in seconds) of two realizations of DHGAK compared with some baselines on four datasets. The datasets are sorted by their sizes. As shown in the table, the fastest GKs are R-convolution graph kernels WL and GAWL. The running time of DHGAK-w2v is comparable to PM. DHGAK-BERT is much slower than DHGAK-w2v, but it is still faster thanWWL, WL-OA, FWL, and GraphQNTK on large datasets such as COLLAB. We also find that the efficiency of DHGAK behaves better on large datasets. It is evident that time bottleneck of DHGAKBERT lies in the inference process of BERT.

5 Conclusion

In this paper, we introduce Deep Hierarchical Graph Alignment Kernels (DHGAK), a novel framework to address the prevalent issue of neglecting relations among substructures in existing R-convolution graph kernels. We propose a positive semi-definite kernel called Deep Alignment Kernel (DAK), which efficiently aligns relational graph substructures using clustering methods on the deep embeddings of substructures learned by Natural Language Models. Then, the Deep Graph Alignment Kernel (DGAK) is constructed by applying kernel mean embedding on the feature maps of DAK. Finally, DHGAK is constructed by the summation of DGAK on slices of different hierarchies. The theoretical analysis demonstrates the effectiveness of our approach, and experimental results indicate that the two realizations of DHGAK outperform the state-of-the-art graph kernels on most datasets.

Acknowledgments

We thank the anonymous reviewers for their valuable and constructive comments. This work was supported partially by the National Natural Science Foundation of China (grants # 62176184 and 62206108), the National Key Research and Development Program of China (grant # 2020AAA0108100), and the Fundamental Research Funds for the Central Universities of China.