Learning Hypertrees From Shortest Path Queries

Shaun M Fallat, Valerii Maliuk, Seyed Ahmad Mojallal, Sandra Zilles
Proceedings of The 35th International Conference on Algorithmic Learning Theory, PMLR 237:574-589, 2024.

Abstract

We consider the problem of learning a labeled hypergraph from a given family of hypergraphs, using shortest path (SP) queries. An SP query specifies two vertices and asks for their distance in the target hypergraph. For various classes $\mathcal{H}$ of hypertrees, we present bounds on the number of queries required to learn an unknown hypertree from $\mathcal{H}$. Matching upper and lower asymptotic bounds are presented for learning hyperpaths and hyperstars, both in the adaptive and in the non-adaptive setting. Moreover, two non-trivial classes of hypertrees are shown to be efficiently learnable from adaptive SP queries, under certain conditions on structural parameters.

Cite this Paper

BibTeX
@InProceedings{pmlr-v237-fallat24a, title = {Learning Hypertrees From Shortest Path Queries}, author = {Fallat, Shaun M and Maliuk, Valerii and Mojallal, Seyed Ahmad and Zilles, Sandra}, booktitle = {Proceedings of The 35th International Conference on Algorithmic Learning Theory}, pages = {574--589}, year = {2024}, editor = {Vernade, Claire and Hsu, Daniel}, volume = {237}, series = {Proceedings of Machine Learning Research}, month = {25--28 Feb}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v237/fallat24a/fallat24a.pdf}, url = {https://proceedings.mlr.press/v237/fallat24a.html}, abstract = {We consider the problem of learning a labeled hypergraph from a given family of hypergraphs, using shortest path (SP) queries. An SP query specifies two vertices and asks for their distance in the target hypergraph. For various classes $\mathcal{H}$ of hypertrees, we present bounds on the number of queries required to learn an unknown hypertree from $\mathcal{H}$. Matching upper and lower asymptotic bounds are presented for learning hyperpaths and hyperstars, both in the adaptive and in the non-adaptive setting. Moreover, two non-trivial classes of hypertrees are shown to be efficiently learnable from adaptive SP queries, under certain conditions on structural parameters.} }
Endnote
%0 Conference Paper %T Learning Hypertrees From Shortest Path Queries %A Shaun M Fallat %A Valerii Maliuk %A Seyed Ahmad Mojallal %A Sandra Zilles %B Proceedings of The 35th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Claire Vernade %E Daniel Hsu %F pmlr-v237-fallat24a %I PMLR %P 574--589 %U https://proceedings.mlr.press/v237/fallat24a.html %V 237 %X We consider the problem of learning a labeled hypergraph from a given family of hypergraphs, using shortest path (SP) queries. An SP query specifies two vertices and asks for their distance in the target hypergraph. For various classes $\mathcal{H}$ of hypertrees, we present bounds on the number of queries required to learn an unknown hypertree from $\mathcal{H}$. Matching upper and lower asymptotic bounds are presented for learning hyperpaths and hyperstars, both in the adaptive and in the non-adaptive setting. Moreover, two non-trivial classes of hypertrees are shown to be efficiently learnable from adaptive SP queries, under certain conditions on structural parameters.
APA
Fallat, S.M., Maliuk, V., Mojallal, S.A. & Zilles, S.. (2024). Learning Hypertrees From Shortest Path Queries. Proceedings of The 35th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 237:574-589 Available from https://proceedings.mlr.press/v237/fallat24a.html.

Related Material