The average mixing matrix signature

Rossi, Luca, Severini, Simone and Torsello, Andrea (2016). The average mixing matrix signature. IN: Structural, syntactic, and statistical pattern recognition. Robles-Kelly, Antonio; Loog, Marco; Baggio, Battista and et al (eds) Image Processing, Computer Vision, Pattern Recognition, and Graphics (Lecture Notes in Computer Science) . MEX: Springer.


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 di↵usion 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 continuoustime 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.

Publication DOI:
Divisions: Engineering & Applied Sciences
Engineering & Applied Sciences > Systems analytics research institute (SARI)
Event Title: Joint IAPR International Workshops on Structural and Syntactic Pattern Recognition and Statistical Techniques in Pattern Recognition
Event Type: Other
Event Dates: 2016-11-30 - 2016-12-02
Uncontrolled Keywords: graph characterisation,structural descriptor,quantum walks,average mixing matrix,Theoretical Computer Science,Computer Science(all)
Full Text Link:
Related URLs: http://www.scop ... tnerID=8YFLogxK (Scopus URL)
Published Date: 2016
Published Online Date: 2016-11-05
Authors: Rossi, Luca ( 0000-0002-6116-9761)
Severini, Simone
Torsello, Andrea



Version: Accepted Version

Export / Share Citation


Additional statistics for this record