The average mixing matrix signature

Luca Rossi, Simone Severini, Andrea Torsello

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

2 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationStructural, Syntactic, and Statistical Pattern Recognition - Joint IAPR International Workshop S+SSPR 2016, Proceedings
EditorsBattista Biggio, Richard Wilson, Marco Loog, Francisco Escolano, Antonio Robles-Kelly
PublisherSpringer Verlag
Number of pages11
ISBN (Print)9783319490540
Publication statusPublished - Nov 2016
Externally publishedYes
EventJoint IAPR International Workshops on Structural and Syntactic Pattern Recognition, SSPR 2016 - Merida, Mexico
Duration: 29 Nov 20162 Dec 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10029 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceJoint IAPR International Workshops on Structural and Syntactic Pattern Recognition, SSPR 2016


  • Average mixing matrix
  • Graph characterisation
  • Quantum walks
  • Structural descriptor

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'The average mixing matrix signature'. Together they form a unique fingerprint.

Cite this