# Learning ErdHos-R'enyi Random Graphs via Edge Detecting Queries

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 May 2019.

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

- [Non-adaptive Learning of Random Hypergraphs with Queries](https://mlsanity.com/paper/2501.12771/) (2025)
- [A Fast Binary Splitting Approach for Non-Adaptive Learning of ErdHos--R'enyi Graphs](https://mlsanity.com/paper/2511.17240/) (2025)
- [Non-Adaptive Learning of Sparse ErdHos--R'enyi Graphs via Affine Splitting](https://mlsanity.com/paper/2609.33704/) (2026)

## Abstract (arXiv)

In this paper, we consider the problem of learning an unknown graph via queries on groups of nodes, with the result indicating whether or not at least one edge is present among those nodes. While learning arbitrary graphs with n nodes and k edges is known to be hard in the sense of requiring Omega( min k2 log n, n2) tests (even when a small probability of error is allowed), we show that learning an ErdHos-R'enyi random graph with an average of bark edges is much easier; namely, one can attain asymptotically vanishing error probability with only O(barklog n) tests. We establish such bounds for a variety of algorithms inspired by the group testing problem, with explicit constant factors indicating a near-optimal number of tests, and in some cases asymptotic optimality including constant factors. In addition, we present an alternative design that permits a near-optimal sublinear decoding time of O(bark log2 bark + bark log n).