Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1007/s00778-019-00544-1 | The VLDB Journal |
Keywords | Field | DocType |
Graph edit distance, Graph databases, Similarity search, Empirical evaluation, 68R10, 68T10, 68P15, 92E10 | Data mining,Graph database,Computer science,Theoretical computer science,Error detection and correction,Assignment problem,Heuristics,Linear programming,Local search (optimization),Nearest neighbor search,Distance measures | Journal |
Volume | Issue | ISSN |
29 | 1 | 1066-8888 |
Citations | PageRank | References |
3 | 0.38 | 0 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| David Blumenthal | 1 | 24 | 6.26 |
| Nicolas Boria | 2 | 59 | 7.23 |
| Johann Gamper | 3 | 465 | 54.06 |
| Sébastien Bougleux | 4 | 395 | 27.05 |
| Luc Brun | 5 | 53 | 5.23 |