Non-Adaptive Learning of Sparse Erd s--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 Ω(k squared n,n 2) queries in the worst case, even when a small error probability is allowed. In this paper, we consider Erdős--Rényi (ER) graphs G about ER(n,q), with expected edge count =q 2. Our scheme uses O(n) queries and achieves exact recovery in O(n) decoding time with probability tending to one throughout the regime to infinity and =o(n 2). This improves the previous O(1+δ n) decoding guarantee for any fixed δ>0, while maintaining the same query order. The guarantee also extends beyond the previously studied regime =Θ(n 2θ) with fixed θ in(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.