On the exact computation of the graph edit distance

By David B. Blumenthal, Johann Gamper. 2020

114 citations recorded by the source corpus.

Abstract The graph edit distance is a widely used distance measure for labelled graph. However, A ★ − GED , the standard approach for its exact computation, suffers from huge runtime and memory requirements. Recently, three better performing algorithms have been proposed: The general algorithms DF − GED and BIP − GED , and the algorithm CSI − GED , which only works for uniform edit costs. All newly proposed algorithms outperform the standard approach A ★ − GED . However, cross-comparisons are lacking. This paper consolidates and extends these recent advances. To this purpose, we present all existing algorithms in a unified way and show that the slightly different definitions of the graph edit distance underlying A ★ − GED and DF − GED , on the one side, and CSI − GED , on the other side, can be harmonised. This harmonisation allows us to develop a generalisation of CSI − GED to non-uniform edit cost. Moreover, we present a speed-up of A ★ − GED and DF − GED for uniform edit costs, which build upon the fact that, in the uniform case, a continuously used subroutine can be implemented to run in linear rather than cubic time. We also suggest an algorithm MIP − GED which builds upon a very compact new mixed integer linear programming formulation. Finally, we carry out a thorough empirical evaluation, which, for the first time, compares all existing exact algorithms.

Subfields: Artificial Intelligence, Computer Networks and Communications, Computer Vision and Pattern Recognition

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. Ting-Li Chen
2. Yizhou Sun
3. Tingting Chen
4. Yang Qiao
5. Song Bian
6. Wei Wang
7. Haoyang Ding
8. Yunsheng Bai

In Computer Networks and Communications

1. Ting-Li Chen
2. Yizhou Sun
3. Tingting Chen
4. Yang Qiao
5. Song Bian
6. Wei Wang
7. Haoyang Ding
8. Yunsheng Bai

In Computer Vision and Pattern Recognition

1. Yizhou Sun
2. Ting-Li Chen
3. Tingting Chen
4. Yang Qiao
5. Song Bian
6. Wei Wang
7. Haoyang Ding
8. Yunsheng Bai

Citations in the corpus

• Unsupervised Inductive Whole-Graph Embedding by Preserving Graph Proximity (2019, background): “What is worse, a recent study shows that no currently available algorithm can reliably compute GED within reasonable time between graphs with more than 16 nodes (Blumenthal & Gamper, 2018).”
• SimGNN: A Neural Network Approach to Fast Graph Similarity Computation (2018, methodology): “For GED, even the state-of-the-art algorithms cannot reliably compute the exact GED within reasonable time between graphs with more than 16 nodes [1].”