Online and Offline Learning of Orderly Hypergraphs Using Queries

Shaun Fallat, Kamyar Khodamoradi, David G. Kirkpatrick, Valerii Maliuk, Seyed Ahmad Mojallal, Sandra Zilles
Proceedings of The 37th International Conference on Algorithmic Learning Theory, PMLR 313:1-21, 2026.

Abstract

In the context of learning hypergraphs with shortest-path queries (SP-queries), we present the first provably optimal online algorithm for learning a broad and natural class of hypertrees which we call orderly hypertrees. Our online algorithm can be transformed into a provably optimal offline algorithm. Orderly hypertrees can be positioned within the Fagin hierarchy of hypergraph acyclicity (studied in database theory), and strictly encompass the broadest class in this hierarchy that is learnable with subquadratic SP-query complexity. Our results also motivate the study of a new type of query, called dependency query (D-query), which is weaker than an SP-query. Positive and negative results on D-queries shed light on the structural properties of classes of hypertrees for which efficient learning requires the full information provided by SP-queries.

Cite this Paper

BibTeX
@InProceedings{pmlr-v313-fallat26a, title = {Online and Offline Learning of Orderly Hypergraphs Using Queries}, author = {Fallat, Shaun and Khodamoradi, Kamyar and Kirkpatrick, David G. and Maliuk, Valerii and Mojallal, Seyed Ahmad and Zilles, Sandra}, booktitle = {Proceedings of The 37th International Conference on Algorithmic Learning Theory}, pages = {1--21}, year = {2026}, editor = {Telgarsky, Matus and Ullman, Jonathan}, volume = {313}, series = {Proceedings of Machine Learning Research}, month = {23--26 Feb}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v313/main/assets/fallat26a/fallat26a.pdf}, url = {https://proceedings.mlr.press/v313/fallat26a.html}, abstract = {In the context of learning hypergraphs with shortest-path queries (SP-queries), we present the first provably optimal online algorithm for learning a broad and natural class of hypertrees which we call orderly hypertrees. Our online algorithm can be transformed into a provably optimal offline algorithm. Orderly hypertrees can be positioned within the Fagin hierarchy of hypergraph acyclicity (studied in database theory), and strictly encompass the broadest class in this hierarchy that is learnable with subquadratic SP-query complexity. Our results also motivate the study of a new type of query, called dependency query (D-query), which is weaker than an SP-query. Positive and negative results on D-queries shed light on the structural properties of classes of hypertrees for which efficient learning requires the full information provided by SP-queries.} }
Endnote
%0 Conference Paper %T Online and Offline Learning of Orderly Hypergraphs Using Queries %A Shaun Fallat %A Kamyar Khodamoradi %A David G. Kirkpatrick %A Valerii Maliuk %A Seyed Ahmad Mojallal %A Sandra Zilles %B Proceedings of The 37th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Matus Telgarsky %E Jonathan Ullman %F pmlr-v313-fallat26a %I PMLR %P 1--21 %U https://proceedings.mlr.press/v313/fallat26a.html %V 313 %X In the context of learning hypergraphs with shortest-path queries (SP-queries), we present the first provably optimal online algorithm for learning a broad and natural class of hypertrees which we call orderly hypertrees. Our online algorithm can be transformed into a provably optimal offline algorithm. Orderly hypertrees can be positioned within the Fagin hierarchy of hypergraph acyclicity (studied in database theory), and strictly encompass the broadest class in this hierarchy that is learnable with subquadratic SP-query complexity. Our results also motivate the study of a new type of query, called dependency query (D-query), which is weaker than an SP-query. Positive and negative results on D-queries shed light on the structural properties of classes of hypertrees for which efficient learning requires the full information provided by SP-queries.
APA
Fallat, S., Khodamoradi, K., Kirkpatrick, D.G., Maliuk, V., Mojallal, S.A. & Zilles, S.. (2026). Online and Offline Learning of Orderly Hypergraphs Using Queries. Proceedings of The 37th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 313:1-21 Available from https://proceedings.mlr.press/v313/fallat26a.html.

Related Material