Non-Adaptive Learning of Sparse Erdos--Renyi Graphs via Affine Splitting

arXiv:2609.33704v1 Announce Type: cross Abstract: 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(min{k^2log n,n^2}) queries in the worst case, even when a small error probability is allowed. In this paper, we consider Erdos--Renyi (ER) graphs Gsim ER(n,q), with expected edge count ar{k}=qinom{n}{2}. Our scheme uses O(ar{k}log n) queries and achieves exact recovery in O(ar{k}log n) decoding time with probability tending to one throughout the regime ar{k}oinfty and ar{k}=o(n^2). This improves the previous O(ar{k}^{1+elta}log n) decoding guarantee for any fixed elta>0, while maintaining the same query order. The guarantee also extends beyond the previously studied regime ar{k}=Theta(n^{2heta}) with fixed hetain(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.

Source: arXiv cs.LG | 2026-09-29