AEGK: Aligned Entropic Graph Kernels Through Continuous-Time Quantum Walks

被引:0
作者
Bai, Lu [1 ,2 ]
Cui, Lixin [3 ]
Li, Ming [4 ,5 ]
Ren, Peng [6 ]
Wang, Yue [3 ]
Zhang, Lichi [7 ]
Yu, Philip S. [8 ]
Hancock, Edwin R. [9 ]
机构
[1] Beijing Normal Univ, Sch Artificial Intelligence, Beijing 100875, Peoples R China
[2] Beijing Normal Univ, Engn Res Ctr Intelligent Technol & Educ Applicat, Minist Educ, Beijing 100875, Peoples R China
[3] Cent Univ Finance & Econ, Sch Informat, Beijing 102206, Peoples R China
[4] Zhejiang Inst Optoelect, Jinhua 321004, Peoples R China
[5] Zhejiang Normal Univ, Zhejiang Key Lab Intelligent Educ Technol & Applic, Jinhua 321004, Peoples R China
[6] China Univ Petr East China, Coll Oceanog & Space Informat, Shandong 257099, Peoples R China
[7] Shanghai Jiao Tong Univ, Sch Biomed Engn, Shanghai 200240, Peoples R China
[8] Univ Illinois, Dept Comp Sci, Chicago, IL 60607 USA
[9] Univ York, Dept Comp Sci, York YO10 5DD, England
基金
中国国家自然科学基金;
关键词
Kernel; Entropy; Quantum computing; Q measurement; Technological innovation; Size measurement; Periodic structures; Hilbert space; Hands; Finance; Graph kernels; quantum walks; graph entropy measures; graph classification;
D O I
10.1109/TKDE.2024.3512181
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
In this work, we develop a family of Aligned Entropic Graph Kernels (AEGK) for graph classification. We commence by performing the Continuous-time Quantum Walk (CTQW) on each graph structure, and compute the Averaged Mixing Matrix (AMM) to describe how the CTQW visits all vertices from a starting vertex. More specifically, we show how this AMM matrix allows us to compute a quantum Shannon entropy of each vertex for either un-attributed or attributed graphs. For pairwise graphs, the proposed AEGK kernels are defined by computing the kernel-based similarity between the quantum Shannon entropies of their pairwise aligned vertices. The analysis of theoretical properties reveals that the proposed AEGK kernels cannot only address the shortcoming of neglecting the structural correspondence information between graphs arising in most existing R-convolution graph kernels, but also overcome the problems of neglecting the structural differences and vertex-attributed information arising in existing vertex-based matching kernels. Moreover, unlike most existing classical graph kernels that only focus on the global or local structural information of graphs, the proposed AEGK kernels can simultaneously capture both global and local structural characteristics through the quantum Shannon entropies, reflecting more precise kernel-based similarity measures between pairwise graphs. The above theoretical properties explain the effectiveness of the proposed AEGK kernels. Experimental evaluations demonstrate that the proposed kernels can outperform state-of-the-art graph kernels and deep learning models for graph classification.
引用
收藏
页码:1064 / 1078
页数:15
相关论文
共 61 条
[1]  
[Anonymous], 2000, Quantum Computation and Quantum Information
[2]  
Azaïs R, 2020, J MACH LEARN RES, V21
[3]   Backtrackless Walks on a Graph [J].
Aziz, Furqan ;
Wilson, Richard C. ;
Hancock, Edwin R. .
IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS, 2013, 24 (06) :977-989
[4]   Learning Aligned-Spatial Graph Convolutional Networks for Graph Classification [J].
Bai, Lu ;
Jiao, Yuhang ;
Cui, Lixin ;
Hancock, Edwin R. .
MACHINE LEARNING AND KNOWLEDGE DISCOVERY IN DATABASES, ECML PKDD 2019, PT I, 2020, 11906 :464-482
[5]  
Bai L, 2015, PR MACH LEARN RES, V37, P30
[6]   Fast depth-based subgraph kernels for unattributed graphs [J].
Bai, Lu ;
Hancock, Edwin R. .
PATTERN RECOGNITION, 2016, 50 :233-245
[7]  
Bai L, 2014, LECT NOTES COMPUT SC, V8621, P1, DOI 10.1007/978-3-662-44415-3_1
[8]   A quantum Jensen-Shannon graph kernel for unattributed graphs [J].
Bai, Lu ;
Rossi, Luca ;
Torsello, Andrea ;
Hancock, Edwin R. .
PATTERN RECOGNITION, 2015, 48 (02) :344-355
[9]   Depth-based complexity traces of graphs [J].
Bai, Lu ;
Hancock, Edwin R. .
PATTERN RECOGNITION, 2014, 47 (03) :1172-1186
[10]   Graph Kernels from the Jensen-Shannon Divergence [J].
Bai, Lu ;
Hancock, Edwin R. .
JOURNAL OF MATHEMATICAL IMAGING AND VISION, 2013, 47 (1-2) :60-69