The average mixing matrix signature

Luca Rossi*, Simone Severini, Andrea Torsello

*Corresponding author for this work

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

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

Fingerprint

Signature
Descriptors
Quantum Walk
Graph in graph theory
Continuous Time
Doubly Stochastic Matrix
Graph Matching
Wave propagation
Stopping Time
Local Structure
Heat Kernel
Vertex of a graph
Wave Propagation
Probe
Heat
kernel
Perturbation
Alternatives
Experiments
Range of data

Keywords

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

Cite this

Rossi, L., Severini, S., & Torsello, A. (2016). The average mixing matrix signature. In A. Robles-Kelly, M. Loog, B. Baggio, & et al (Eds.), Structural, syntactic, and statistical pattern recognition: Joint IAPR International Workshop, S+SSPR 2016, Mérida, Mexico, November 29 - December 2, 2016, Proceedings (pp. 474-484). (Image Processing, Computer Vision, Pattern Recognition, and Graphics (Lecture Notes in Computer Science); Vol. 10029). Cham (CH): Springer. https://doi.org/10.1007/978-3-319-49055-7_42
Rossi, Luca ; Severini, Simone ; Torsello, Andrea. / The average mixing matrix signature. Structural, syntactic, and statistical pattern recognition: Joint IAPR International Workshop, S+SSPR 2016, Mérida, Mexico, November 29 - December 2, 2016, Proceedings. editor / Antonio Robles-Kelly ; Marco Loog ; Battista Baggio ; et al. Cham (CH) : Springer, 2016. pp. 474-484 (Image Processing, Computer Vision, Pattern Recognition, and Graphics (Lecture Notes in Computer Science)).
@inproceedings{339ec33ae1a3489a8cfaa1876ffd316a,
title = "The average mixing matrix signature",
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.",
keywords = "graph characterisation, structural descriptor, quantum walks, average mixing matrix",
author = "Luca Rossi and Simone Severini and Andrea Torsello",
year = "2016",
month = "11",
day = "5",
doi = "10.1007/978-3-319-49055-7_42",
language = "English",
isbn = "978-3-319-49054-0",
series = "Image Processing, Computer Vision, Pattern Recognition, and Graphics (Lecture Notes in Computer Science)",
publisher = "Springer",
pages = "474--484",
editor = "Antonio Robles-Kelly and Marco Loog and Battista Baggio and {et al}",
booktitle = "Structural, syntactic, and statistical pattern recognition",
address = "Germany",

}

Rossi, L, Severini, S & Torsello, A 2016, The average mixing matrix signature. in A Robles-Kelly, M Loog, B Baggio & et al (eds), Structural, syntactic, and statistical pattern recognition: Joint IAPR International Workshop, S+SSPR 2016, Mérida, Mexico, November 29 - December 2, 2016, Proceedings. Image Processing, Computer Vision, Pattern Recognition, and Graphics (Lecture Notes in Computer Science), vol. 10029, Springer, Cham (CH), pp. 474-484, Joint IAPR International Workshops on Structural and Syntactic Pattern Recognition and Statistical Techniques in Pattern Recognition, Mérida, Mexico, 30/11/16. https://doi.org/10.1007/978-3-319-49055-7_42

The average mixing matrix signature. / Rossi, Luca; Severini, Simone; Torsello, Andrea.

Structural, syntactic, and statistical pattern recognition: Joint IAPR International Workshop, S+SSPR 2016, Mérida, Mexico, November 29 - December 2, 2016, Proceedings. ed. / Antonio Robles-Kelly; Marco Loog; Battista Baggio; et al. Cham (CH) : Springer, 2016. p. 474-484 (Image Processing, Computer Vision, Pattern Recognition, and Graphics (Lecture Notes in Computer Science); Vol. 10029).

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

TY - GEN

T1 - The average mixing matrix signature

AU - Rossi, Luca

AU - Severini, Simone

AU - Torsello, Andrea

PY - 2016/11/5

Y1 - 2016/11/5

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 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.

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 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.

KW - graph characterisation

KW - structural descriptor

KW - quantum walks

KW - average mixing matrix

UR - http://link.springer.com/chapter/10.1007/978-3-319-49055-7_42

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 contribution

AN - SCOPUS:84996836047

SN - 978-3-319-49054-0

T3 - Image Processing, Computer Vision, Pattern Recognition, and Graphics (Lecture Notes in Computer Science)

SP - 474

EP - 484

BT - Structural, syntactic, and statistical pattern recognition

A2 - Robles-Kelly, Antonio

A2 - Loog, Marco

A2 - Baggio, Battista

A2 - et al,

PB - Springer

CY - Cham (CH)

ER -

Rossi L, Severini S, Torsello A. The average mixing matrix signature. In Robles-Kelly A, Loog M, Baggio B, et al, editors, Structural, syntactic, and statistical pattern recognition: Joint IAPR International Workshop, S+SSPR 2016, Mérida, Mexico, November 29 - December 2, 2016, Proceedings. Cham (CH): Springer. 2016. p. 474-484. (Image Processing, Computer Vision, Pattern Recognition, and Graphics (Lecture Notes in Computer Science)). https://doi.org/10.1007/978-3-319-49055-7_42