Graph node matching for edit distance

• Published in: Pattern recognition letters 2024-08, Vol.184, p.14-20
• Main Authors: Moscatelli, Aldo, Piquenot, Jason, Bérar, Maxime, Héroux, Pierre, Adam, Sébastien
• Format: Article
• Language: English
• Subjects: Computer Science; Graph Edit Distance; Graph Neural Network; Linear Sum Assignment; Metric learning; Node embedding; Siamese architectures
• ISSN: 0167-8655
• DOI: 10.1016/j.patrec.2024.05.020

Graphs are commonly used to model interactions between elements of a set, but computing the Graph Edit Distance between two graphs is an NP-complete problem that is particularly challenging for large graphs. To address this problem, we propose a supervised metric learning approach that combines Graph Neural Networks and optimal transport to learn an approximation of the GED in an end-to-end fashion. Our model consists of two siamese GNNs and a comparison block. Each graph pair’s nodes are augmented by positional encoding and embedded by multiple Graph Isomorphism Network layers. The obtained embeddings are then compared through a Multi-Layer Perceptron and Linear Sum Assignment Problem solver applied on a node-wise Euclidean metric defined in the embedding space. We show that our approach achieves state-of-the-art results on benchmark datasets and outperforms other similar works in the domain. Our approach also provides explainability through the extraction of an edit path from one graph to another and guarantees metric properties conservation during training and inference. [Display omitted] •GNOME is a deep neural architecture for the approximation of the graph edit distance.•Graph features are enriched by Random Walk descriptors to improve expressivity.•Embeddings are learned through GIN and matched through Linear Sum Assignment.•GNOME offers explainability but also metric properties warranties.•GNOME outperforms existing deep learning based models on three benchmark datasets.