Learning a Hidden Hypergraph

Dana Angluin; Jiang Chen

We consider the problem of learning a hypergraph using edge-detecting queries. In this model, the learner may query whether a set of vertices induces an edge of the hidden hypergraph or not. We show that an r-uniform hypergraph with m edges and n vertices is learnable with O(2^4rm · poly(r,logn)) queries with high probability. The queries can be made in O(min(2^r (log m+r)², (log m+r)³)) rounds. We also give an algorithm that learns an almost uniform hypergraph of dimension r using O(2^O((1+Δ/2)r) · m^1+Δ/2 · poly(log n)) queries with high probability, where Δ is the difference between the maximum and the minimum edge sizes. This upper bound matches our lower bound of Ω((m/(1+Δ/2))^1+Δ/2) for this class of hypergraphs in terms of dependence on m. The queries can also be made in O((1+Δ) · min(2^r (log m+r)², (log m+r)³)) rounds.

Learning a Hidden Hypergraph

Abstract