# Distance-based Learning of Hypertrees

arXiv: https://arxiv.org/abs/2511.22014 · HTML: https://mlsanity.com/paper/2511.22014/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 15 references that are in the map.
- First posted on arXiv 27 Nov 2025.

## Builds on (most cited first, 1 of 1)

- [Optimal distance query reconstruction for graphs without long induced cycles](https://mlsanity.com/paper/2306.05979/) (2023)

## Abstract (arXiv)

We study the problem of learning hypergraphs with shortest-path queries (SP-queries), and present the first provably optimal online algorithm for a broad and natural class of hypertrees that 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 acyclic hypergraph (well-studied in database theory), and strictly encompass the broadest class in this hierarchy that is learnable with subquadratic SP-query complexity. Recognizing that in some contexts, such as evolutionary tree reconstruction, distance measurements can degrade with increased distance, we also consider a learning model that uses bounded distance queries. In this model, we demonstrate asymptotically tight complexity bounds for learning general hypertrees.