The Minimum Edit Arborescence Problem and Its Use in Compressing Graph Collections

Gnecco L, Boria N, Bougleux S, Yger F, Blumenthal DB (2021)

Publication Language: English

Publication Type: Conference contribution, Conference Contribution

Publication year: 2021

Publisher: Springer International Publishing

Series: Lecture Notes in Computer Science

City/Town: Cham

Book Volume: 13058

Pages Range: 337--351

Conference Proceedings Title: Proceedings of the 14th International Conference on Similarity Search and Applications (SISAP 2021)

Event location: Dortmund DE

ISBN: 978-3-030-89657-7

DOI: 10.1007/978-3-030-89657-7_25

Abstract

The inference of minimum spanning arborescences within a set of objects is a general problem which translates into numerous application-specific unsupervised learning tasks. We introduce a unified and generic structure called edit arborescence that relies on edit paths between data in a collection, as well as the Minimum Edit Arborescence Problem, which asks for an edit arborescence that minimizes the sum of costs of its inner edit paths. Through the use of suitable cost functions, this generic framework allows to model a variety of problems. In particular, we show that by introducing encoding size preserving edit costs, it can be used as an efficient method for compressing collections of labeled graphs. Experiments on various graph datasets, with comparisons to standard compression tools, show the potential of our method.

Authors with CRIS profile

David Blumenthal Professur für Biomedical Network Science

Involved external institutions

University of Paris 9 - Paris-Dauphine / Université Paris 9 Paris-Dauphine FR France (FR) Normandy University / Normandie Université FR France (FR)

How to cite

APA:

Gnecco, L., Boria, N., Bougleux, S., Yger, F., & Blumenthal, D.B. (2021). The Minimum Edit Arborescence Problem and Its Use in Compressing Graph Collections. In Reyes N, Connor R, Kriege N, Kazempour D, Bartolini I, Schubert E, Chen J (Eds.), Proceedings of the 14th International Conference on Similarity Search and Applications (SISAP 2021) (pp. 337--351). Dortmund, DE: Cham: Springer International Publishing.

MLA:

Gnecco, Lucas, et al. "The Minimum Edit Arborescence Problem and Its Use in Compressing Graph Collections." Proceedings of the 14th International Conference on Similarity Search and Applications (SISAP 2021), Dortmund Ed. Reyes N, Connor R, Kriege N, Kazempour D, Bartolini I, Schubert E, Chen J, Cham: Springer International Publishing, 2021. 337--351.

BibTeX: Download