Learning Graph Edit Distance By Graph Neural Networks

Abstract

The emergence of geometric deep learning as a novel framework to deal with graph-based representations has faded away traditional approaches in favor of completely new methodologies. In this paper, we propose a new framework able to combine the advances on deep metric learning with traditional approximations of the graph edit distance. Hence, we propose an efficient graph distance based on the novel field of geometric deep learning. Our method employs a message passing neural network to capture the graph structure, and thus, leveraging this information for its use on a distance computation. The performance of the proposed graph distance is validated on two different scenarios. On the one hand, in a graph retrieval of handwritten words~\ie~keyword spotting, showing its superior performance when compared with (approximate) graph edit distance benchmarks. On the other hand, demonstrating competitive results for graph similarity learning when compared with the current state-of-the-art on a

Stats

• citations27
• S2 citations—
• github stars0
• HF likes0
• heat score10.85
• arxiv keyriba2020learning

Related papers

• Deep Graph Similarity Learning: A Survey (2019)13.97
• Hierarchical Graph Matching Network For Graph Similarity Computation (2020)0.00
• Simgnn: A Neural Network Approach To Fast Graph Similarity Computation (2018)0.00
• MATA*: Combining Learnable Node Matching With A* Algorithm For Approximate Graph Edit Distance Computation (2023)6.34
• Representing Deep Neural Networks Latent Space Geometries With Graphs (2020)7.50
• Differential Geometric Retrieval Of Deep Features (2017)2.26
• Graph2region: Efficient Graph Similarity Learning With Structure And Scale Restoration (2025)0.00
• S\(^3\)GND: An Effective Learning-based Approach For Subgraph Similarity Search Under Generalized Neighbor Difference Semantics (technical Report) (2026)0.00