An Exact Graph Edit Distance Algorithm for Solving Pattern Recognition Problems

By Zeina Abu-Aisheh, Romain Raveaux, Jean-Yves Ramel, Patrick Martineau. 2015

257 citations recorded by the source corpus.

Graph edit distance is an error tolerant matching technique emerged as a powerful and flexible graph matching paradigm that can be used to address different tasks in pattern recognition, machine learning and data mining; it represents the minimum-cost sequence of basic edit operations to transform one graph into another by means of insertion, deletion and substitution of vertices and/or edges. A widely used method for exact graph edit distance computation is based on the A* algorithm. To overcome its high memory load while traversing the search tree for storing pending solutions to be explored, we propose a depth-first graph edit distance algorithm which requires less memory and searching time. An evaluation of all possible solutions is performed without explicitly enumerating them all. Candidates are discarded using an upper and lower bounds strategy. A solid experimental study is proposed; experiments on a publicly available database empirically demonstrated that our approach is better than the A* graph edit distance computation in terms of speed, accuracy and classification rate.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Mohit Bansal
2. Graham Neubig
3. Yiming Yang
4. Uri Alon
5. Shuyan Zhou
6. Jianfeng Gao
7. Aman Madaan
8. Swarnadeep Saha

In Computer Vision and Pattern Recognition

1. Mohit Bansal
2. Luc Van Gool
3. Jitendra Malik
4. Dacheng Tao
5. Xiaogang Wang
6. Trevor Darrell
7. Ming-Hsuan Yang
8. Andrew Zisserman

In Signal Processing

1. Greg Mori
2. Mohit Bansal
3. Graham Neubig
4. Yasutaka Furukawa
5. Shuyan Zhou
6. Aman Madaan
7. Yiming Yang
8. Uri Alon

Citations in the corpus

• NAS-Bench-NLP: Neural Architecture Search Benchmark for Natural Language Processing (2020, methodology): “To calculate these values, we used consecutive GED approximations [2] (implemented in NetworkX package [15]) for the limited time.”
• ExplaGraphs: An Explanation Graph Generation Task for Structured Commonsense Reasoning (2021, methodology): “Furthermore, we propose graph-matching metrics like Graph Edit Distance (Abu-Aisheh et al., 2015) and ones that extend text-generation metrics for graphs (based on multiple test graphs in our dataset).”
• House-GAN: Relational Generative Adversarial Networks for Graph-constrained House Layout Generation (2020, methodology): “…0 .0/0.0 0 .0/0.0 0 .0/0.0 Unknown 0.0/0.0 0 .0/0.0 0 .0/0.0 0 .0/0.0 0 .0/0.0 0 .0/0.0 • The compatibility with the bubble diagram is a graph editing distance [2] between the input bubble diagram and the bubble diagram constructed from the output layout in the same way as the GT preparation above.”
• Language Models of Code are Few-Shot Commonsense Learners (2022, background): “…evaluation of generated scripts: • Graph edit distance ( GED ): the number of required edits (node/edge removal/additions) to transform ˆ G to G (Abu-Aisheh et al., 2015); • Graph isomorphism ( ISO ; Cordella et al., 2001): determines whether ˆ G and G are isomorphic based on their…”