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)
ISBN: 978-3-030-89657-7
DOI: 10.1007/978-3-030-89657-7_25
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.
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