Quantum Rényi α-Entropies for Graph Characterization.
TL;DR
This article proposes novel graph kernels based on quantum Rényi $\alpha $ -entropies of different orders, computed from both the unnormalized and normalized Laplacian matrices, and demonstrates that these methods achieve competitive or superior performance compared with state-of-the-art techniques, including deep learning approaches, while remaining computationally efficient.
Abstract
Comparing graphs for structural similarity is one of the most important problems in graph analytics. However, due to the nonlinear nature of graphs, this problem is not straightforward to solve. Most existing graph comparison methods either lack expressiveness, do not provide interpretable measures of similarity, or incur high computational costs, limiting their applicability to large graphs. In this article, we propose novel graph kernels based on quantum Rényi $\alpha $ -entropies of different orders, computed from both the unnormalized and normalized Laplacian matrices. We investigate the properties of these entropies and show that they are determined by the frequencies and degree statistics of substructures of different types and sizes, such as simple paths and cycles ofdifferentlengths. By utilizing quantum Rényi $\alpha $ -entropies of different orders, our approach defines efficient, theoretically grounded, and interpretable graph kernels capable of characterizing the structure of unlabeled graphs. Through extensive experiments on benchmark datasets, we demonstrate that our methods achieve competitive or superior performance compared with state-of-the-art techniques, including deep learning approaches, while remaining computationally efficient.