Abstract
Typical R-convolution graph kernels invoke the kernel functions that decompose graphs into non-isomorphic substructures and compare them. However, overlooking implicit similarities and topological position information between those substructures limits their performances. In this paper, we introduce Deep Hierarchical Graph Alignment Kernels (DHGAK) to resolve this problem. Specifically, the relational substructures are hierarchically aligned to cluster distributions in their deep embedding space. The substructures belonging to the same cluster are assigned the same feature map in the Reproducing Kernel Hilbert Space (RKHS), where graph feature maps are derived by kernel mean embedding. Theoretical analysis guarantees that DHGAK is positive semi-definite and has linear separability in the RKHS. Comparison with state-of-the-art graph kernels on various benchmark datasets demonstrates the effectiveness and efficiency of DHGAK.
Introduction
Traditional graph kernels, specifically those based on $\mathcal{R}$-convolution, measure similarity by decomposing graphs into substructures (like paths or subtrees) and checking for isomorphism. This approach faces two major challenges: strictness and topological blindness.
Strictness refers to the "all-or-nothing" matching problem: if two substructures differ slightly, they are treated as completely dissimilar, ignoring implicit similarities. Topological blindness occurs when kernels fail to capture the relative positions of substructures. For instance, as shown in Figure 1, Aspirin and 3-Acetoxybenzoic acid contain identical chemical groups but arranged differently; one is a medicine, the other is not. Traditional kernels often struggle to distinguish such isomers because they do not capture these relative positions effectively.
While modern methods like Optimal Transport (e.g., Wasserstein distance) attempt to align substructures, they are often computationally expensive and may lack the mathematical property of positive semi-definiteness (PSD) required for many machine learning algorithms.
Methodology
The Deep Hierarchical Graph Alignment Kernel (DHGAK) framework addresses these issues through a four-step pipeline that treats graph structures as "sentences" for deep learning models.
- Hierarchical Neighborhood Encoding: For each node, the algorithm extracts a "$b$-width $h$-hop slice"—a structured neighborhood. To ensure a canonical representation, neighbors are ordered by Eigenvector Centrality (EC).
- Deep Slice Embedding: These neighborhood sequences are treated as "sentences" and projected into a continuous vector space using Natural Language Models (NLMs) like BERT or word2vec. This allows the model to capture semantic similarities between different-looking neighborhoods.
- Deep Alignment Kernel (DAK): Instead of costly point-to-point matching, DHGAK aligns substructures by clustering them in the embedding space. Substructures in the same cluster are considered aligned. This approach is proven to be positive semi-definite (PSD) and satisfies transitivity.
- Hierarchical Summation: The final kernel value is the sum of alignments across different neighborhood scales (hops), capturing both local and global graph topology.
Experimental Results
DHGAK was evaluated on 16 real-world benchmark datasets from the TUDataset repository, including bioinformatics (e.g., MUTAG, PROTEINS, ENZYMES) and social network datasets (e.g., IMDB, COLLAB).
Key findings include:
- Superior Accuracy: The BERT-based version of DHGAK achieved state-of-the-art (SOTA) accuracy on 14 out of 16 datasets.
- Significant Gains: On the ENZYMES and PTC FR datasets, DHGAK improved absolute accuracy by 4.9% and 3.2%, respectively, over previous SOTA methods.
- Efficiency: The word2vec variant (DHGAK-w2v) provides a high-performance alternative that is significantly faster than Wasserstein-based kernels (WWL) on large-scale datasets like COLLAB.
Conclusion
DHGAK bridges the gap between traditional graph kernels and deep learning by leveraging NLMs for structural embedding and clustering for efficient alignment. While the inference time of large models like BERT can be a bottleneck, the framework's theoretical guarantees of PSD and linear separability in the RKHS make it a robust tool for graph classification. Future work may explore the integration of even larger language models to further capture complex structural nuances.
Summary updated