# A Fast Binary Splitting Approach for Non-Adaptive Learning of ErdHos--R'enyi Graphs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 36 references that are in the map.
- First posted on arXiv 21 Nov 2025.

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

- [On Learning Graphs with Edge-Detecting Queries](https://mlsanity.com/paper/1803.10639/) (2018)
- [A Fast Binary Splitting Approach to Non-Adaptive Group Testing](https://mlsanity.com/paper/2006.10268/) (2020)
- [Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time](https://mlsanity.com/paper/2006.08420/) (2020)
- [Learning ErdHos-R'enyi Random Graphs via Edge Detecting Queries](https://mlsanity.com/paper/1905.03410/) (2019)
- [Fast Splitting Algorithms for Sparsity-Constrained and Noisy Group Testing](https://mlsanity.com/paper/2106.00308/) (2021)
- [Noisy Nonadaptive Group Testing with Binary Splitting: New Test Design and Improvement on Price-Scarlett-Tan's Scheme](https://mlsanity.com/paper/2410.14566/) (2024)
- [Non-adaptive Learning of Random Hypergraphs with Queries](https://mlsanity.com/paper/2501.12771/) (2025)
- [Non-adaptive Group Testing on Graphs](https://mlsanity.com/paper/1511.09196/) (2015)

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

- [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 an unknown graph via group queries on node subsets, where each query reports whether at least one edge is present among the queried nodes. In general, learning arbitrary graphs with n nodes and k edges is hard in the non-adaptive setting, requiring Omegabig(mink2log n,,n2big) tests even when a small error probability is allowed. We focus on learning ErdHos--R'enyi (ER) graphs G~ER(n,q) in the non-adaptive setting, where the expected number of edges is bark=qbinomn2, and we aim to design an efficient testing--decoding scheme, namely, a non-adaptive test design together with a decoding algorithm, achieving asymptotically vanishing error probability. Prior work (Li--Fresacher--Scarlett, NeurIPS 2019) presents a testing--decoding scheme that attains an order-optimal number of tests O(barklog n) but incurs Omega(n2) decoding time, whereas their proposed sublinear-time algorithm incurs an extra (log bark)(log n) factor in the number of tests. We extend the binary splitting approach, recently developed for non-adaptive group testing, to the ER graph learning setting, and prove that the edge set can be recovered with high probability using O(barklog n) tests while attaining decoding time O(bark1+δlog n) for any fixed δ>0.