GEDLIB: A C++ Library for Graph Edit Distance Computation

GEDLIB: Une bibliothèque C++ pour le calcul de la distance d'édition sur graphes

David Blumenthal (1) , Sébastien Bougleux (2) , Luc Brun (2) , Johann Gamper (3)

1 Faculty of Computer Science, Free University of Bozen-Bolzano,
2 Equipe Image - Laboratoire GREYC - UMR6072
3 Free University of Bozen-Bolzano

The graph edit distance (GED) is a flexible graph dissimilarity measure widely used within the structural pattern recognition field. In this paper, we present GEDLIB, a C++ library for exactly or approximately computing GED. Many existing algorithms for GED are already implemented in GEDLIB. Moreover, GEDLIB is designed to be easily extensible: for implementing new edit cost functions and GED algorithms, it suffices to implement abstract classes contained in the library. For implementing these extensions, the user has access to a wide range of utilities, such as deep neural networks, support vector machines, mixed integer linear programming solvers, a blackbox optimizer, and solvers for the linear sum assignment problem with and without error-correction.

Mots clés: Graph Edit Distance · Open Source Library · C++.

Domaines: Vision par ordinateur et reconnaissance de formes [cs.CV]; Bio-informatique [q-bio.QM]; Mathématique discrète [cs.DM]

David Blumenthal, Sébastien Bougleux, Luc Brun, Johann Gamper. GEDLIB: A C++ Library for Graph Edit Distance Computation. 12th IAPR TC15 Workshop on Graph-Based Representation in Pattern Recognition (GbR), 2019, Jun 2019, Tours, France. ⟨hal-02162839⟩