# Non-Adaptive Learning of Sparse ErdHos--R'enyi Graphs via Affine Splitting

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 27 references that are in the map.
- First posted on arXiv 27 Sep 2026.

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

- [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)
- [Sublinear-Time Non-Adaptive Group Testing with O(k log n) Tests via Bit-Mixing Coding](https://mlsanity.com/paper/1904.10102/) (2019)
- [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)
- [A Fast Binary Splitting Approach for Non-Adaptive Learning of ErdHos--R'enyi Graphs](https://mlsanity.com/paper/2511.17240/) (2025)

## Abstract (arXiv)

Graph learning from edge-detecting queries concerns the reconstruction of an unknown edge set on a known vertex set. Each query reports whether a specified vertex subset contains at least one edge. We study non-adaptive schemes, in which all queries are fixed before any outcomes are observed, with the goal of achieving exact recovery using few queries and fast decoding. For general graphs on n vertices with at most k edges, non-adaptive recovery requires Omega(mink2log n,n2) queries in the worst case, even when a small error probability is allowed. In this paper, we consider ErdHos--R'enyi (ER) graphs G~ ER(n,q), with expected edge count bark=qbinomn2. Our scheme uses O(barklog n) queries and achieves exact recovery in O(barklog n) decoding time with probability tending to one throughout the regime bark→∞ and bark=o(n2). This improves the previous O(bark1+δlog n) decoding guarantee for any fixed δ>0, while maintaining the same query order. The guarantee also extends beyond the previously studied regime bark=Theta(n2θ) with fixed θ∈(0,1). Our approach builds on the binary splitting method used in prior work, which organizes vertices into a hierarchy of successively smaller groups. We introduce three main changes: (i) we use random affine hash functions over a finite field to process each candidate pair in constant time; (ii) we apply the splitting procedure directly to the full graph, avoiding the need to combine solutions to multiple smaller graph-learning subproblems; and (iii) we bound the total decoding workload directly rather than deriving separate high-probability bounds on candidate counts at each level.