jmlr jmlr2006 jmlr2006-53 jmlr2006-53-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Dana Angluin, Jiang Chen
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(2O((1+ 2 )r) · m1+ 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 ) for this class of hypergraphs in terms of dependence on m. The 1+ 2 queries can also be made in O((1 + ∆) · min(2r (log m + r)2 , (log m + r)3 )) rounds. Keywords: query learning, hypergraph, multiple round algorithm, sampling, chemical reaction network
Noga Alon and Vera Asodi. Learning a hidden subgraph. SIAM Journal on Discrete Mathematics, 18(4):697–712, 2005. Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, and Benny Sudakov. Learning a hidden matching. SIAM Journal of Computing, 33(2):487–501, 2004. Dana Angluin and Jiang Chen. Learning a hidden graph using O(log n) queries per edge. In Conference on Learning Theory, pages 210–223. Springer, 2004. Dana Angluin and Jiang Chen. Learning a hidden hypergraph. In Conference on Learning Theory, pages 561–575. Springer, 2005. Richard Beigel, Noga Alon, Simon Kasif, Mehmet Serkan Apaydin, and Lance Fortnow. An optimal procedure for gap closing in whole genome shotgun sequencing. In RECOMB, pages 22–30, 2001. Peter Damaschke. Adaptive versus nonadaptive attribute-efficient learning. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pages 590–596. ACM Press, 1998. Vladimir Grebinski and Gregory Kucherov. Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping. Discrete Applied Mathematics, 88(1-3):147–165, 1998. Vladimir Grebinski and Gregory Kucherov. Optimal reconstruction of graphs under the additive model. Algorithmica, 28(1):104–124, 2000. 2236