Non-Adaptive Learning of Sparse Erdős--Rényi Graphs via Affine Splitting
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 Ω(min{k2log n,n2}) 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∼ ER(n,q), with expected edge count k̅=qbinomn2. Our scheme uses O(k̅log n) queries and achieves exact recovery in O(k̅log n) decoding time with probability tending to one throughout the regime k̅→∞ and k̅=o(n2). This improves the previous O(k̅1+δlog n) decoding guarantee for any fixed δ>0, while maintaining the same query order. The guarantee also extends beyond the previously studied regime k̅=Θ(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.
Related
- Minimax and Adaptive Transfer Learning for Sparse Canonical Correlation Analysis
- Learning Sparse Support under Differential Privacy: Adaptive Algorithms and Minimax Limits
- Splitting of projective modules over some affine algebras
- Solving Large-Scale Sparse Linear Complementarity Problems Using a Relaxed Shifted Matrix-Splitting Modulus-Based Iteration Method
- Hopf Algebra of Graphs for Operator Splitting Methods
BibTeX
@misc{ta2026nonadaptive,
title = {{Non-Adaptive Learning of Sparse Erdős--Rényi Graphs via Affine Splitting}},
author = {Hoang Ta},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.33704},
eprint = {2609.33704},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33704},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Non-Adaptive Learning of Sparse Erdős--Rényi Graphs via Affine Splitting
AU - Hoang Ta
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2609.33704
UR - https://arxiv.org/abs/2609.33704
AB - 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 Ω(min{k^2log 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∼ ER(n,q), with expected edge count k̅=qbinomn2. Our scheme uses O(k̅log n) queries and achieves exact recovery in O(k̅log n) decoding time with probability tending to one throughout the regime k̅→∞ and k̅=o(n^2). This improves the previous O(k̅^1+δlog n) decoding guarantee for any fixed δ>0, while maintaining the same query order. The guarantee also extends beyond the previously studied regime k̅=Θ(n^2θ) 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.
ER -