Comparing heuristics for graph edit distance computation

Because of its flexibility, intuitiveness, and expressivity, the graph edit distance (GED) is one of the most widely used distance measures for labeled graphs. Since exactly computing GED is NP -hard, over the past years, various heuristics have been proposed. They use techniques such as transformat...

Full description

Saved in:
Bibliographic Details
Published in:The VLDB journal 2020, Vol.29 (1), p.419-458
Main Authors: Blumenthal, David B., Boria, Nicolas, Gamper, Johann, Bougleux, Sébastien, Brun, Luc
Format: Article
Language:English
Subjects:
Computer Science
Computer Vision and Pattern Recognition
Data Structures and Algorithms
Database Management
Distance measurement
Error correction
Heuristic
Linear programming
Lower bounds
Special Issue Paper
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Because of its flexibility, intuitiveness, and expressivity, the graph edit distance (GED) is one of the most widely used distance measures for labeled graphs. Since exactly computing GED is NP -hard, over the past years, various heuristics have been proposed. They use techniques such as transformations to the linear sum assignment problem with error correction, local search, and linear programming to approximate GED via upper or lower bounds. In this paper, we provide a systematic overview of the most important heuristics. Moreover, we empirically evaluate all compared heuristics within an integrated implementation.
ISSN:1066-8888
0949-877X
DOI:10.1007/s00778-019-00544-1