The Average Mixing Matrix Signature
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. W
- PDF / 1,759,938 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 14 Downloads / 228 Views
School of Engineering and Applied Science, Aston University, Birmingham, UK [email protected] 2 Department of Computer Science, University College London, London, UK 3 DAIS, Universit` a Ca’ Foscari Venezia, Venice, Italy
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 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.
Keywords: Graph characterisation walks · Average mixing matrix
1
· Structural descriptor · Quantum
Introduction
Graph-based representations have been used with considerable success in computer vision in the abstraction and recognition of object shape and scene structure [4,8,13]. A fundamental problem in graph-based pattern recognition is that of recovering the set of correspondences (matching) between the vertices of two graphs. In computer vision, graph matching has been applied to a wide range of problems, from object categorisation [1,4] to action recognition [14,15]. More formally, in the graph matching problem the goal is to find a mapping between the nodes of two graphs such that the edge structure is preserved. While there exists a wide range of methods to solve this problem, many graph matching algorithms greatly benefit from the use of local structural descriptors to maximise their performance. To this end, a structural descriptor or signature is assigned to each node of the graphs, effectively embedding the graphs nodes onto c Springer International Publishing AG 2016 A. Robles-Kelly et al. (Eds.): S+SSPR 2016, LNCS 10029, pp. 474–484, 2016. DOI: 10.1007/978-3-319-49055-7 42
The Average Mixing Matrix Signature
475
a vectorial space. Given an underlying correspondence between the node sets of the graphs, the assumption underpinning these approaches is that corresponding nodes will be mapped to points that are close in the signature space. Two structural signatures that have proven to be particularly successful are the Heat Kernel Signature (HKS) [12] and the Wave Kernel Signature (WKS) [2]. Both signatures belong to the family of Laplacian-
Data Loading...
