Non-adaptive queries reconstruct sparse random graphs efficiently
Non-Adaptive Learning of Sparse Erdős--Rényi Graphs via Affine Splitting
Information TheoryMachine Learning
Summary
This paper studies how to figure out the connections (edges) in a large network when you can only ask simple yes-or-no questions about groups of points (vertices). The authors focus on random graphs where edges appear with some probability, and design a method that decides on all questions in advance and can quickly identify all connections. Their new approach uses clever mathematical tools to speed up the process and requires fewer questions than before, especially for graphs with a moderate number of edges. This means it is easier and faster to map out such networks exactly without checking every pair individually.
What this means in practice
- •For network administrators: Recover the exact structure of large sparse communication networks efficiently without iterative probing.
- •For data engineers: Speed up graph reconstruction tasks in massive datasets by using fixed, simple queries and fast decoding algorithms.
Authors
Hoang Ta
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\{k^2\log 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 ($\mathrm{ER}$) graphs $G\sim \mathrm{ER}(n,q)$, with expected edge count $\bar{k}=q\binom{n}{2}$. Our scheme uses $O(\bar{k}\log n)$ queries and achieves exact recovery in $O(\bar{k}\log n)$ decoding time with probability tending to one throughout the regime $\bar{k}\to\infty$ and $\bar{k}=o(n^2)$. This improves the previous $O(\bar{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 $\bar{k}=Θ(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.