The Algebraic Path Problem for Graph Metrics

Enrique Fita Sanmartı́n, Sebastian Damrich, Fred Hamprecht
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:19178-19204, 2022.

Abstract

Finding paths with optimal properties is a foundational problem in computer science. The notions of shortest paths (minimal sum of edge costs), minimax paths (minimal maximum edge weight), reliability of a path and many others all arise as special cases of the "algebraic path problem" (APP). Indeed, the APP formalizes the relation between different semirings such as min-plus, min-max and the distances they induce. We here clarify, for the first time, the relation between the potential distance and the log-semiring. We also define a new unifying family of algebraic structures that include all above-mentioned path problems as well as the commute cost and others as special or limiting cases. The family comprises not only semirings but also strong bimonoids (that is, semirings without distributivity). We call this new and very general distance the "log-norm distance". Finally, we derive some sufficient conditions which ensure that the APP associated with a semiring defines a metric over an arbitrary graph.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-sanmarti-n22a, title = {The Algebraic Path Problem for Graph Metrics}, author = {Sanmart\'{\i}n, Enrique Fita and Damrich, Sebastian and Hamprecht, Fred}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {19178--19204}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/sanmarti-n22a/sanmarti-n22a.pdf}, url = {https://proceedings.mlr.press/v162/sanmarti-n22a.html}, abstract = {Finding paths with optimal properties is a foundational problem in computer science. The notions of shortest paths (minimal sum of edge costs), minimax paths (minimal maximum edge weight), reliability of a path and many others all arise as special cases of the "algebraic path problem" (APP). Indeed, the APP formalizes the relation between different semirings such as min-plus, min-max and the distances they induce. We here clarify, for the first time, the relation between the potential distance and the log-semiring. We also define a new unifying family of algebraic structures that include all above-mentioned path problems as well as the commute cost and others as special or limiting cases. The family comprises not only semirings but also strong bimonoids (that is, semirings without distributivity). We call this new and very general distance the "log-norm distance". Finally, we derive some sufficient conditions which ensure that the APP associated with a semiring defines a metric over an arbitrary graph.} }
Endnote
%0 Conference Paper %T The Algebraic Path Problem for Graph Metrics %A Enrique Fita Sanmartı́n %A Sebastian Damrich %A Fred Hamprecht %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-sanmarti-n22a %I PMLR %P 19178--19204 %U https://proceedings.mlr.press/v162/sanmarti-n22a.html %V 162 %X Finding paths with optimal properties is a foundational problem in computer science. The notions of shortest paths (minimal sum of edge costs), minimax paths (minimal maximum edge weight), reliability of a path and many others all arise as special cases of the "algebraic path problem" (APP). Indeed, the APP formalizes the relation between different semirings such as min-plus, min-max and the distances they induce. We here clarify, for the first time, the relation between the potential distance and the log-semiring. We also define a new unifying family of algebraic structures that include all above-mentioned path problems as well as the commute cost and others as special or limiting cases. The family comprises not only semirings but also strong bimonoids (that is, semirings without distributivity). We call this new and very general distance the "log-norm distance". Finally, we derive some sufficient conditions which ensure that the APP associated with a semiring defines a metric over an arbitrary graph.
APA
Sanmartı́n, E.F., Damrich, S. & Hamprecht, F.. (2022). The Algebraic Path Problem for Graph Metrics. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:19178-19204 Available from https://proceedings.mlr.press/v162/sanmarti-n22a.html.

Related Material