## Learning a Hidden Hypergraph

** Dana Angluin, Jiang Chen**; 7(79):2215−2236, 2006.

### Abstract

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^{4r}*m* ·
*poly*(*r*,log*n*)) queries with high probability.
The queries can be made in *O*(min(2^{r}
(log *m+r*)^{2}, (log *m+r*)^{3})) 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*)^{2},
(log *m+r*)^{3})) rounds.

© JMLR 2006. (edit, beta) |