Non-adaptive Learning of Random Hypergraphs with Queries

The problem of learning graphs through edge-detecting queries has been extensively studied due to its many applications, ranging from learning pairwise chemical reactions to genome sequencing problems (Alon and Asodi, 2005; Alon et al., 2004; Angluin and Chen, 2008; Grebinski and Kucherov, 1998; Reyzin and Srivastava, 2007). While significant progress has been made in this area, less is known about efficiently learning hypergraphs, which have now become the de facto standard to model higher-order network interactions (Battiston et al., 2020; Benson et al., 2016; Lotito et al., 2022). In this paper, we take another step toward bridging this gap in the literature. We study the problem of learning a hypergraph by making hyperedge-detecting queries. In particular, we focus on the non-adaptive setting (in which every query needs to be submitted in advance), that is more suited for bioinformatics applications. A lower bound of Abasi and Nader (2019) shows that it is impossible in general to design algorithms that achieve a query complexity nearly linear in the number of (hyper)edges, even for graphs. A recent paper by Li et al. (2019) shows that this lower bound can be beaten for graphs that are generated from a known Erdős-Rényi model. We extend their results by providing algorithms for learning random hypergraphs that have nearly linear query complexity in the number of hyperedges.