Generalised median of graph correspondences.

Moreno-García, Carlos Francisco; Serratosa, Francesc

doi:10.1016/j.patrec.2019.05.015

Generalised median of graph correspondences.

Moreno-García, Carlos Francisco; Serratosa, Francesc

Authors

Dr Carlos Moreno-Garcia c.moreno-garcia@rgu.ac.uk
Associate Professor

Francesc Serratosa

Abstract

A graph correspondence is defined as a function that maps the elements of two attributed graphs. Due to the increasing availability of methods to perform graph matching, numerous graph correspondences can be deducted for a pair of attributed graphs. To obtain a representative prototype for a set of data structures, the concept of the median has been largely employed, as it has proven to deliver a robust sample. Nonetheless, the calculation of the exact (or generalised) median is known to be an NP-complete problem for most domains. In this paper, we present a method based on an optimisation function to calculate the generalised median graph correspondence. This method makes use of the Correspondence Edit Distance, which is a metric that considers the attributes and the local structures of the graphs to obtain more interesting and meaningful results. Experimental validation shows that this approach is capable of obtaining the generalised median in a comparable runtime with respect to state-of-the-art methods on artificial data, while maintaining the success rate for a real-application case.

Citation

MORENO-GARCÍA, C.F. and SERRATOSA, F. 2019. Generalised median of graph correspondences. Pattern recognition letters [online], 125, pages 389-395. Available from: https://doi.org/10.1016/j.patrec.2019.05.015

Journal Article Type	Article
Acceptance Date	May 19, 2019
Online Publication Date	May 21, 2019
Publication Date	Jul 1, 2019
Deposit Date	Jun 17, 2019
Publicly Available Date	May 22, 2020
Journal	Pattern Recognition Letters
Print ISSN	0167-8655
Electronic ISSN	1872-7344
Publisher	Elsevier
Peer Reviewed	Peer Reviewed
Volume	125
Pages	389-395
DOI	https://doi.org/10.1016/j.patrec.2019.05.015
Keywords	Signal processing; Software; Artificial intelligence; Computer vision and pattern recognition
Public URL	https://rgu-repository.worktribe.com/output/310334
Contract Date	Jun 17, 2019