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

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.