Non-Adaptive Learning of Sparse Erdős--Rényi Graphs via Affine Splitting

Hoang Ta

cs.ITSep 27, 2026

Non-Adaptive Learning of Sparse Erdős--Rényi Graphs via Affine Splitting

Authors: Hoang Ta

Organizations: Department of Computer Science, Hanoi University of Science and Technology, Vietnam

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.

Figures & tables

Reference	Queries	Decoding time	Sparsity regime
COMP/DD [ 17 ]	$\mathcal{O}(\bar{k}\log n)$	$\mathcal{O}(n^{2}\bar{k}\log n)$	$\bar{k}=\Theta(n^{2\theta})$
GROTESQUE-based [ 17 ]	$\mathcal{O}(\bar{k}\log\bar{k}\log^{2}n)$	$\mathcal{O}(\bar{k}\log^{2}\bar{k}+\bar{k}\log n)$	$\bar{k}=\Theta(n^{2\theta})$
Binary splitting [ 21 ]	$\mathcal{O}(\bar{k}\log n)$	$\mathcal{O}(\bar{k}^{1+\delta}\log n)$	$\bar{k}=\Theta(n^{2\theta})$
This work	$\mathcal{O}(\bar{k}\log n)$	$\mathcal{O}(\bar{k}\log n)$	$\bar{k}\to\infty$ , $\bar{k}=o(n^{2})$

Table 1: Comparison of non-adaptive recovery guarantees with vanishing error probability. The parameters

\theta\in(0,1)

and

\delta>0

are fixed.

Notation	Description
Graph and hierarchy
$n,q,\bar{k}$	Number of vertices, edge probability, and expected number of edges $\bar{k}=q\binom{n}{2}$ .
$g_{0},g_{j}$	Number of blocks at the base level and at level $j$ , where $g_{j}=2^{j}g_{0}$ .
$\mathcal{G}_{u}^{(j)}$	The $u$ -th block at level $j$ .
$H_{g}$	Number of edges whose two endpoints lie in the same block, at the level with $g$ blocks.
$G_{g},D_{g}$	Level graph induced on the $g$ blocks, and its number of edges, i.e., the number of defective block pairs.

Table 2: Notation.

Explore similar work

Nov 21, 2025cs.IT

A Fast Binary Splitting Approach for Non-Adaptive Learning of Erdős--Rényi Graphs

We study the problem of learning an unknown graph via group queries on node subsets, where each query reports whether at least one edge is present among the queried nodes. In general, learning arbitrary graphs with

n

nodes and

k

edges is hard in the non-adaptive setting, requiring

Ω\big(\min\{k^2\log n,\,n^2\}\big)

tests even when a small error probability is allowed. We focus on learning Erdős--Rényi (ER) graphs

G\sim\mathrm{ER}(n,q)

in the non-adaptive setting, where the expected number of edges is

\bar{k}=q\binom{n}{2}

, and we aim to design an efficient testing--decoding scheme, namely, a non-adaptive test design together with a decoding algorithm, achieving asymptotically vanishing error probability. Prior work (Li--Fresacher--Scarlett, NeurIPS 2019) presents a testing--decoding scheme that attains an order-optimal number of tests

O(\bar{k}\log n)

but incurs

Ω(n^2)

decoding time, whereas their proposed sublinear-time algorithm incurs an extra

(\log \bar{k})(\log n)

factor in the number of tests. We extend the binary splitting approach, recently developed for non-adaptive group testing, to the ER graph learning setting, and prove that the edge set can be recovered with high probability using

O(\bar{k}\log n)

tests while attaining decoding time

O(\bar{k}^{1+δ}\log n)

for any fixed

δ>0

Hoang Ta, Jonathan Scarlett

Department of Computer Science, School of Computing, National University of Singapore (NUS), Singapore 117417 · Department of Computer Science, Hanoi University of Science and Technology, Vietnam · Department of Computer Science, Department of Mathematics, and Institute of Data Science, NUS, Singapore 117417

O(\Bar{K}\Log N)$Inhomogeneous Random Graphs

Ask PDF

Jun 12, 2026math.ST

Recovery thresholds for hidden weighted sparse graphs

Recovering structural information from noisy high-dimensional data is a fundamental task in statistical inference. We investigate the recovery thresholds for a graph hidden in a randomly weighted complete graph. Specifically, an unknown graph

H^* \in H_n

is chosen uniformly at random, and hidden in a complete graph of

n

vertices as follows: the weight of an edge

e \in H

is distributed independently according to

P_n

; otherwise the weight is distributed independently according to

Q_n

. The goal is to recover almost all of

H

from these edge weights. Assuming a local Lipschitzness of the Rényi divergence between distributions

P_n

and

Q_n

, and a mild density condition for the graphs

H_n

, we give a unified characterization of the information-theoretic limit for recovering almost all of

H

(also known as almost exact recovery). Our characterization connects the KL divergence between

P_n

and

Q_n

to the logarithm of the first moment threshold of

H

in the Erdős-Rényi random graph model

G(n,p)

. Our lower bound also extends to the task of partial recovery, in which only a constant

λ

-fraction of

H

needs to be recovered. Last but not least, for certain Bernoulli and Exponential regimes, and for Gaussian distributions, we are able to show an All-or-Nothing (AoN) threshold phenomenon at the exponential scale.

Zhe Hou, Jingcheng Liu

State Key Laboratory for Novel Software Technology, Nanjing University

Inhomogeneous Random Graphs Information-Theoretic Limits O(\Bar{K}\Log N)$Kullback-Leibler Divergence

Ask PDF

Jun 1, 2026cs.IT

Query-Limited Community Recovery in Stochastic Block Models

We study exact community recovery in the two-community stochastic block model on

n

vertices under limited and noisy access to network data. The learner may query a noisy neighborhood oracle that reveals each true neighbor of a queried vertex independently with fixed probability and never returns non-neighbors, subject to a finite query budget. We consider both oracle-only access and a combined model where the learner also observes a single subsampled copy of the underlying graph. For oracle-only access, balanced uniform querying gives a sharp non-adaptive benchmark: when each vertex is queried the same integer number of times, the observations reduce to an SBM with attenuated edge probabilities and the Abbe-Bandeira-Hall exact-recovery threshold applies. We show that this benchmark is not adaptively optimal: a two-stage adaptive strategy succeeds with

n+o(n)

queries in a regime where balanced uniform querying requires

m n

queries for some

m>1

. With an additional subsampled graph, we prove a sublinear-query adaptivity gap: balanced data-independent uniform querying with a sublinear budget does not improve over the subsampled graph alone, whereas adaptive querying can target a small set of uncertain vertices and achieve exact recovery. Thus adaptive data acquisition can strictly improve the information-theoretic limits of exact recovery.

Sabyasachi Basu, Manuj Mukherjee, Lutz Oettershagen +1

1Microsoft Research, India · 2Indraprastha Institute of Information Technology, India · University of Liverpool, United Kingdom +1

O(\Bar{K}\Log N)$Subgraphs Information-Theoretic Limits

Ask PDF