QBER: Quantum-based Entropic Representations for un-attributed graphs

Lixin Cui

doi:10.1016/j.patcog.2023.109877

QBER: Quantum-based Entropic Representations for un-attributed graphs

2024-01-01

2

OA

AI

DOI：10.1016/j.patcog.2023.109877

原文链接

查看原文

摘要

En 中文

In this paper, we propose a novel framework of computing the Quantum-based Entropic Representations (QBER) for un-attributed graphs, through the Continuous-time Quantum Walk (CTQW). To achieve this, we commence by transforming each original graph into a family of k-level neighborhood graphs, where each k -level neighborhood graph encapsulates the connected information between each vertex and its k-hop neighbor vertices, providing a fine representation to reflect the multi-level topological information for the original global graph structure. To further capture the complicated structural characteristics of the original graph through its neighborhood graphs, we propose to characterize the structure of each neighborhood graph with the Average Mixing Matrix (AMM) of the CTQW, that encapsulates the time-averaged behavior of the CTQW evolved on the neighborhood graph. More specifically, we show how the AMM matrix allows us to compute a Quantum Shannon Entropy for each vertex, and thus compute an entropic signature for each neighborhood graph by measuring the averaged value or the Jensen-Shannon Divergence between the entropies of its vertices. For each original graph, the resulting QBER is defined by gauging how the entropic signat ures vary on its k-level neighborhood graphs with increasing k, reflecting the multi-dimensional entropy-based structure information of the original graph. Experiments on standard graph datasets demonstrate the effectiveness of the proposed QBER approach in terms of the classification accuracies. The proposed approach can significantly outperform state-of-the-art entropic complexity measuring methods, graph kernel methods, as well as graph deep learning methods.

Keyword:

Graph embedding

Graph entropy

Quantum walks

Entropic representations

QBER: Quantum-based Entropic Representations for un-attributed graphs

摘要

AI总结

期刊

机构