QESK: Quantum-based Entropic Subtree Kernels for Graph Classification
In this paper, we propose a novel graph kernel, namely the Quantum-based Entropic Subtree Kernel (QESK), for Graph Classification. To this end, we commence by computing the Average Mixing Matrix (AMM) of the Continuous-time Quantum Walk (CTQW) evolved on each graph structure. Moreover, we show how this AMM matrix can be employed to compute a series of entropic subtree representations associated with the classical Weisfeiler-Lehman (WL) algorithm. For a pair of graphs, the QESK kernel is defined by computing the exponentiation of the negative Euclidean distance between their entropic subtree representations, theoretically resulting in a positive definite graph kernel. We show that the proposed QESK kernel not only encapsulates complicated intrinsic quantum-based structural characteristics of graph structures through the CTQW, but also theoretically addresses the shortcoming of ignoring the effects of unshared substructures arising in state-of-the-art R-convolution graph kernels. Moreover, unlike the classical R-convolution kernels, the proposed QESK can discriminate the distinctions of isomorphic subtrees in terms of the global graph structures, theoretically explaining the effectiveness. Experiments indicate that the proposed QESK kernel can significantly outperform state-of-the-art graph kernels and graph deep learning methods for graph classification problems.
Code (0)
등록된 구현이 없습니다.
Tasks
ClassificationGraph ClassificationSimilar Papers 제목 키워드 기반
AERK: Aligned Entropic Reproducing Kernels through Continuous-time Quantum Walks
In this work, we develop an Aligned Entropic Reproducing Kernel (AERK) for graph classification. We commence by performing the Continuous-time Quantum Walk (CTQW) on each graph structure, and computing the Averaged Mixin…
Graph ClassificationLearning subtree pattern importance for Weisfeiler-Lehmanbased graph kernels
Graph is an usual representation of relational data, which are ubiquitous in manydomains such as molecules, biological and social networks. A popular approach to learningwith graph structured data is to make use of graph…
Graph ClassificationExploring Consistency in Graph Representations:from Graph Kernels to Graph Neural Networks
Graph Neural Networks (GNNs) have emerged as a dominant approach in graph representation learning, yet they often struggle to capture consistent similarity relationships among graphs. While graph kernel methods such as t…
Graph ClassificationGraph Representation LearningRepresentation LearningFast, Accurate and Interpretable Graph Classification with Topological Kernels
We introduce a novel class of explicit feature maps based on topological indices that represent each graph by a compact feature vector, enabling fast and interpretable graph classification. Using radial basis function ke…
Graph ClassificationGraph LearningBeyond holography: the entropic quantum gravity foundations of image processing
Recently, thanks to the development of artificial intelligence (AI) there is increasing scientific attention to establishing the connections between theoretical physics and AI. Traditionally, these connections have been …