The average mixing matrix signature

Luca Rossi*, Simone Severini, Andrea Torsello

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference publication

Abstract

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.
Original languageEnglish
Title of host publicationStructural, syntactic, and statistical pattern recognition
Subtitle of host publicationJoint IAPR International Workshop, S+SSPR 2016, Mérida, Mexico, November 29 - December 2, 2016, Proceedings
EditorsAntonio Robles-Kelly, Marco Loog, Battista Baggio, et al
Place of PublicationCham (CH)
PublisherSpringer
Pages474-484
Number of pages11
ISBN (Electronic)978-3-319-49055-7
ISBN (Print)978-3-319-49054-0
DOIs
Publication statusE-pub ahead of print - 5 Nov 2016
EventJoint IAPR International Workshops on Structural and Syntactic Pattern Recognition and Statistical Techniques in Pattern Recognition - Mérida, Mexico
Duration: 30 Nov 20162 Dec 2016

Publication series

NameImage Processing, Computer Vision, Pattern Recognition, and Graphics (Lecture Notes in Computer Science)
PublisherSpringer
Volume10029
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

WorkshopJoint IAPR International Workshops on Structural and Syntactic Pattern Recognition and Statistical Techniques in Pattern Recognition
Abbreviated titleS-SSSPR 2016
CountryMexico
CityMérida
Period30/11/162/12/16

Keywords

  • graph characterisation
  • structural descriptor
  • quantum walks
  • average mixing matrix

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

  • Edge centrality via the Holevo quantity

    Lockhart, J., Minello, G., Rossi, L., Severini, S. & Torsello, A., 5 Nov 2016, Structural, syntactic, and statistical pattern recognition: Joint IAPR International Workshop, S+SSPR 2016, Mérida, Mexico, November 29 - December 2, 2016, Proceedings. Robles-Kelly, A., Loog, M., Biggio, B. & et al (eds.). Cham (CH): Springer, p. 143-152 10 p. (Lecture Notes in Computer Science; vol. 10029).

    Research output: Chapter in Book/Report/Conference proceedingConference publication

    Open Access
    File

Cite this