TY - GEN
T1 - The average mixing matrix signature
AU - Rossi, Luca
AU - Severini, Simone
AU - Torsello, Andrea
N1 - Funding Information:
Simone Severini was supported by the Royal Society and EPSRC.
Publisher Copyright:
© Springer International Publishing AG 2016.
PY - 2016/11
Y1 - 2016/11
N2 - Laplacian-based descriptors, such as the Heat Kernel Signature and the Wave Kernel Signature, allow one to embed the vertices of a graph onto a vectorial space, and have been successfully used to find the optimal matching between a pair of input graphs. While the HKS uses a heat diffusion process to probe the local structure of a graph, the WKS attempts to do the same through wave propagation. In this paper, we propose an alternative structural descriptor that is based on continuous-time quantum walks. More specifically, we characterise the structure of a graph using its average mixing matrix. The average mixing matrix is a doubly-stochastic matrix that encodes the time-averaged behaviour of a continuous-time quantum walk on the graph. We propose to use the rows of the average mixing matrix for increasing stopping times to develop a novel signature, the Average Mixing Matrix Signature (AMMS). We perform an extensive range of experiments and we show that the proposed signature is robust under structural perturbations of the original graphs and it outperforms both the HKS and WKS when used as a node descriptor in a graph matching task.
AB - Laplacian-based descriptors, such as the Heat Kernel Signature and the Wave Kernel Signature, allow one to embed the vertices of a graph onto a vectorial space, and have been successfully used to find the optimal matching between a pair of input graphs. While the HKS uses a heat diffusion process to probe the local structure of a graph, the WKS attempts to do the same through wave propagation. In this paper, we propose an alternative structural descriptor that is based on continuous-time quantum walks. More specifically, we characterise the structure of a graph using its average mixing matrix. The average mixing matrix is a doubly-stochastic matrix that encodes the time-averaged behaviour of a continuous-time quantum walk on the graph. We propose to use the rows of the average mixing matrix for increasing stopping times to develop a novel signature, the Average Mixing Matrix Signature (AMMS). We perform an extensive range of experiments and we show that the proposed signature is robust under structural perturbations of the original graphs and it outperforms both the HKS and WKS when used as a node descriptor in a graph matching task.
KW - Average mixing matrix
KW - Graph characterisation
KW - Quantum walks
KW - Structural descriptor
UR - http://www.scopus.com/inward/record.url?scp=84996836047&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-49055-7_42
DO - 10.1007/978-3-319-49055-7_42
M3 - Conference article published in proceeding or book
AN - SCOPUS:84996836047
SN - 9783319490540
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 474
EP - 484
BT - Structural, Syntactic, and Statistical Pattern Recognition - Joint IAPR International Workshop S+SSPR 2016, Proceedings
A2 - Biggio, Battista
A2 - Wilson, Richard
A2 - Loog, Marco
A2 - Escolano, Francisco
A2 - Robles-Kelly, Antonio
PB - Springer Verlag
T2 - Joint IAPR International Workshops on Structural and Syntactic Pattern Recognition, SSPR 2016
Y2 - 29 November 2016 through 2 December 2016
ER -