Learning graph distances with message passing neural networks

Riba, Pau (Computer Vision Center, Computer Science Department, Universitàt Autònoma de Barcelona, Barcelona, Spain) ; Fischer, Andreas (School of Engineering and Architecture (HEIA-FR), HES-SO // University of Applied Sciences Western Switzerland ; DIVA group, University of Fribourg, Fribourg, Switzerland) ; Lladós, Josep (Computer Vision Center, Computer Science Department, Universitàt Autònoma de Barcelona, Barcelona, Spain) ; Fornés, Alicia (Computer Vision Center, Computer Science Department, Universitàt Autònoma de Barcelona, Barcelona, Spain)

Graph representations have been widely used in pattern recognition thanks to their powerful representation formalism and rich theoretical background. A number of errortolerant graph matching algorithms such as graph edit distance have been proposed for computing a distance between two labelled graphs. However, they typically suffer from a high computational complexity, which makes it difficult to apply these matching algorithms in a real scenario. In this paper, we propose an efficient graph distance based on the emerging field of geometric deep learning. Our method employs a message passing neural network to capture the graph structure and learns a metric with a siamese network approach. The performance of the proposed graph distance is validated in two application cases, graph classification and graph retrieval of handwritten words, and shows a promising performance when compared with (approximate) graph edit distance benchmarks.


Conference Type:
full paper
Faculty:
Ingénierie et Architecture
School:
HEIA-FR
Institute:
iCoSys - Institut des systèmes complexes
Subject(s):
Ingénierie
Publisher:
Beijing, China, 20-24 August 2018
Date:
2018-08
Beijing, China
20-24 August 2018
Pagination:
6 p.
Published in:
ICPR 2018, the 24th International Conference on Pattern Recognition, 20-24 August 2018, Beijing, China
Appears in Collection:

Note: The status of this file is: restricted


 Record created 2019-02-26, last modified 2019-03-05

Fulltext:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)