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.

We consider the problem of graph searching with prediction recently introduced by Banerjee et al. (2022). In this problem, an agent, starting at some vertex $r$ has to traverse a (potentially unknown) graph $G$ to find a hidden goal node $g$ while minimizing the total distance travelled. We study a setting in which at any node $v$, the agent receives a noisy estimate of the distance from $v$ to $g$. We design algorithms for this search task on unknown graphs. We establish the first formal guarantees on unknown weighted graphs and provide lower bounds showing that the algorithms we propose have optimal or nearly-optimal dependence on the prediction error. Further, we perform numerical experiments demonstrating that in addition to being robust to adversarial error, our algorithms perform well in typical instances in which the error is stochastic. Finally, we provide alternative simpler performance bounds on the algorithms of Banerjee et al. (2022) for the case of searching on a known graph, and establish new lower bounds for this setting.

This paper initiates the study of active learning for exact recovery of partitions exclusively through access to a same-cluster oracle in the presence of bounded adversarial error. We first highlight a novel connection between learning partitions and correlation clustering. Then we use this connection to build a R\'enyi-Ulam style analytical framework for this problem, and prove upper and lower bounds on its worst-case query complexity. Further, we bound the expected performance of a relevant randomized algorithm. Finally, we study the relationship between adaptivity and query complexity for this problem and related variants.