Distance-based Learning of Hypertrees
This work addresses the challenge of efficiently reconstructing structures like evolutionary trees from distance-based queries, offering optimal algorithms for specific hypertree classes, though it is incremental in extending query-based learning to hypergraphs.
The paper tackles the problem of learning hypergraphs using shortest-path queries, presenting the first provably optimal online algorithm for orderly hypertrees, which are a broad class within the Fagin hierarchy, and also provides asymptotically tight complexity bounds for learning general hypertrees with bounded distance queries.
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.