# Non-adaptive Learning of Random Hypergraphs with Queries

arXiv: https://arxiv.org/abs/2501.12771 · HTML: https://mlsanity.com/paper/2501.12771/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 28 references that are in the map.
- First posted on arXiv 22 Jan 2025.

## Builds on (most cited first, 7 of 7)

- [Networks beyond pairwise interactions: structure and dynamics](https://mlsanity.com/paper/2006.01764/) (2020)
- [Higher-order organization of complex networks](https://mlsanity.com/paper/1612.08447/) (2016)
- [On Learning Graphs with Edge-Detecting Queries](https://mlsanity.com/paper/1803.10639/) (2018)
- [On Exact Learning Monotone DNF from Membership Queries](https://mlsanity.com/paper/1405.0792/) (2014)
- [Higher-order motif analysis in hypergraphs](https://mlsanity.com/paper/2108.03192/) (2021)
- [Learning ErdHos-R'enyi Random Graphs via Edge Detecting Queries](https://mlsanity.com/paper/1905.03410/) (2019)
- [Learning Low Degree Hypergraphs](https://mlsanity.com/paper/2202.09989/) (2022)

## Built on by (most cited first, 3 of 3)

- [A Fast Binary Splitting Approach for Non-Adaptive Learning of ErdHos--R'enyi Graphs](https://mlsanity.com/paper/2511.17240/) (2025)
- [Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds](https://mlsanity.com/paper/2608.02176/) (2026)
- [Non-Adaptive Learning of Sparse ErdHos--R'enyi Graphs via Affine Splitting](https://mlsanity.com/paper/2609.33704/) (2026)

## Abstract (arXiv)

We study the problem of learning a hidden hypergraph G=(V,E) by making a single batch of queries (non-adaptively). We consider the hyperedge detection model, in which every query must be of the form: ``Does this set Ssubseteq V contain at least one full hyperedge?'' In this model, it is known that there is no algorithm that allows to non-adaptively learn arbitrary hypergraphs by making fewer than Omega(minm2log n, n2) even when the hypergraph is constrained to be 2-uniform (i.e. the hypergraph is simply a graph). Recently, Li et al. overcame this lower bound in the setting in which G is a graph by assuming that the graph learned is sampled from an ErdHos-R'enyi model. We generalize the result of Li et al. to the setting of random k-uniform hypergraphs. To achieve this result, we leverage a novel equivalence between the problem of learning a single hyperedge and the standard group testing problem. This latter result may also be of independent interest.