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 H of hypertrees, we present bounds on the number of queries required to learn an unknown hypertree from 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