🤖 machine learning

A Fast Binary Splitting Approach for Non-Adaptive Learning of Erd\H{o}s--Rényi Graphs

This paper proposes a fast non-adaptive testing-decoding scheme for learning Erdős–Rényi graphs that achieves order-optimal $O(\bar{k}\log n)$ test complexity while significantly improving decoding time to $O(\bar{k}^{1+\delta}\log n)$ by extending the binary splitting approach.

Original authors: Hoang Ta, Jonathan Scarlett

Published 2026-07-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hoang Ta, Jonathan Scarlett

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Finding Hidden Connections

Imagine you have a massive party with $n$ guests. You know that some of these guests are "connected" (they are friends, or in the paper's terms, they have an "edge" between them), but you don't know who is connected to whom. There are $k$ connections in total.

Your goal is to figure out exactly who is friends with whom. However, you can't just ask, "Are you friends with Bob?" You have a special, limited tool: The Group Test.

You can pick a group of people, put them in a room, and ask a single question: "Is there at least one friendship happening in this room?"

If the answer is YES, you know there is at least one pair of friends in there, but you don't know who.
If the answer is NO, you know for a fact that no one in that room is friends with anyone else in that room.

The challenge is to design a set of these group tests (all planned in advance, without changing your mind based on previous answers) so that you can reconstruct the entire friendship map using as few tests as possible and as little computer time as possible.

The Problem: The "Worst-Case" vs. The "Average"

In the past, researchers found that if the friendships were arranged in the absolute worst possible way (a "worst-case" scenario), you would need a huge number of tests to find them all. It was like trying to find a needle in a haystack where the haystack is made of other needles.

However, the authors of this paper say: "Let's stop worrying about the worst-case nightmare. Let's assume the friendships are random, like in a typical social network." They use a mathematical model called an Erdős–Rényi graph, which basically means every pair of people has a small, random chance of being friends.

In this "random" world, previous methods had a trade-off:

Method A: Used a very efficient number of tests, but took forever to figure out the answer (like having a super-fast scanner but a slow brain).
Method B: Was fast to process, but required way too many tests (like using a million flashlights to find a single firefly).

The Solution: The "Binary Splitting" Strategy

The authors propose a new method that gets the best of both worlds: it uses the minimum number of tests and is very fast to decode. They do this by adapting a technique called Binary Splitting.

The Analogy: The Russian Nesting Dolls
Imagine the guests are organized into a giant tree of groups, like Russian nesting dolls or a family tree.

Level 1: You divide everyone into two big halves.
Level 2: You split those halves into quarters.
Level 3: You split those into eighths, and so on, until you get down to individual people.

The algorithm works like a detective narrowing down a suspect list:

The Test: You run tests on these groups. If a test comes back "Negative" (no friendships found), you know that none of the people in that group are friends with anyone else in that group. You can cross out millions of potential friendships instantly.
The Refinement: If a test is "Positive," you know there is a friendship there, but you don't know where. So, you move to the next level of the tree (splitting the groups in half) and test the smaller pieces.

By doing this recursively, you quickly eliminate the "empty" areas and zoom in on the "active" areas where the friendships actually exist.

The Innovation: Breaking the Bottleneck

The authors realized that even with this smart splitting, there was a bottleneck. To be sure a friendship didn't exist, the computer had to check a huge number of test results for every single pair of people it was still suspicious of. This made the computer slow (specifically, the time grew with $k^{1.5}$ , where $k$ is the number of friendships).

The Fix: The "Permutation Party"
To speed this up, they introduced a clever trick involving random shuffling (permutations).

Imagine you have a messy room (the graph) and you want to find the hidden toys (friendships).

The Old Way: You look at the whole messy room. It's hard to see patterns.
The New Way: You take the toys, shuffle them around randomly into different boxes, and then look at the boxes.
- Sometimes, the shuffling accidentally puts all the "toys" (friendships) into separate boxes where they don't interfere with each other.
- When this happens, the "Binary Splitting" detective can work super fast because the groups are "clean."
- If one shuffle doesn't work, they just try another random shuffle. Because they try many shuffles, they are guaranteed to find at least one "clean" arrangement where the detective can work efficiently.

This "shuffling" allows them to break the problem into many smaller, easier puzzles. Solving many small puzzles is much faster than solving one giant, messy one.

The Results

By combining Binary Splitting (the tree structure) with Random Shuffling (the permutations), the authors achieved:

Efficiency: They use the theoretical minimum number of tests ( $O(k \log n)$ ).
Speed: They decode the answer incredibly fast ( $O(k^{1+\delta} \log n)$ ), which is nearly as fast as the number of tests itself.

In short, they figured out how to find all the hidden connections in a random network using the fewest possible questions and the least amount of computer time, beating previous methods that were either too slow or required too many questions.

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

Problem Statement
The paper addresses the problem of learning an unknown undirected graph $G = (V, E)$ with $n$ vertices via non-adaptive group queries. In this setting, a query consists of a subset of vertices $S \subseteq V$ , and the outcome is a single bit indicating whether at least one edge exists entirely within $S$ . The goal is to design a testing-decoding scheme that minimizes the number of queries while ensuring efficient reconstruction of the edge set $E$ .

While learning arbitrary graphs with $k$ edges in the non-adaptive setting requires $\Omega(\min\{k^2 \log n, n^2\})$ tests, the authors focus on the Erdős–Rényi (ER) model $G \sim \text{ER}(n, q)$ , where edges appear independently with probability $q$ . The expected number of edges is $k = q \binom{n}{2}$ . The specific challenge is to achieve an order-optimal number of tests, $O(k \log n)$ , while simultaneously attaining a sublinear (or near-linear in $k$ ) decoding time. Prior work achieved $O(k \log n)$ tests but required $\Omega(n^2)$ decoding time, or achieved sublinear decoding time at the cost of an extra $\log k \cdot \log n$ factor in the number of tests.

Methodology
The authors propose a testing-decoding scheme that extends the binary splitting approach, recently developed for non-adaptive group testing, to the graph learning setting. The methodology is presented in two stages: a baseline algorithm and an improved algorithm utilizing partitioning and permutations.

Binary Splitting Hierarchy:
- The algorithm organizes vertices into a binary hierarchy of blocks across levels $\ell = \lceil \log_2 \sqrt{k} \rceil, \dots, \log_2 n$ .
- At each level, the vertex set is partitioned into $g = 2^\ell$ blocks. The algorithm performs randomized testing where blocks are assigned to tests.
- Test Design: The design uses $O(\sqrt{k})$ repetitions, each containing $O(\sqrt{k})$ tests. This $\sqrt{k} \times \sqrt{k}$ structure ensures that non-defective pairs (pairs of blocks with no internal edges) are likely to be placed together in a negative test, while keeping the probability of a positive test bounded away from 1 to prevent "drowning out" non-defective pairs.
- Decoding: The decoder proceeds from coarse levels to fine levels. It maintains a set of "possibly defective" (PD) block pairs. If a pair is not ruled out by a negative test, it is refined into child pairs at the next level. The process relies on the property that non-defective pairs are eliminated with high probability, keeping the size of the PD set under control (modeled as a subcritical branching process).
Addressing the Decoding Bottleneck (Partitioning and Permutations):
- The baseline binary splitting approach results in a decoding time of $O(k^{1.5} \log n)$ because the decoder must check $O(\sqrt{k})$ tests for each of the $O(k)$ candidate pairs.
- To improve this, the authors partition the vertex set $V$ into $m = k^{(1-\gamma)/2}$ balanced subsets $S_1, \dots, S_m$ .
- The problem is decomposed into subproblems defined by the induced subgraphs $G_{ij} = G[S_i \cup S_j]$ . Each subgraph has an expected edge count of $O(k^\gamma)$ , significantly smaller than $k$ .
- Permutation Amplification: A key difficulty is ensuring that the blocks within these subgraphs are "favorable" (i.e., contain no internal edges at the base level of the recursion). The authors introduce a permutation amplification step: they sample $c$ independent random permutations from a pairwise independent family. For each subgraph, they apply these permutations to the vertex labels.
- This ensures that with high probability, at least one permutation yields a block structure where no block contains an internal edge. This allows the binary splitting decoder to be applied to smaller subproblems with a reduced per-pair checking cost.

Key Contributions and Results

Baseline Scheme (Theorem 1):
- The authors first establish a scheme using the binary splitting approach directly on the full graph.
- Tests: $O(k \log n)$ , which is order-optimal.
- Decoding Time: $O(k^{1.5} \log n)$ (or $O(k^{1.5} \log^2 k \log n)$ depending on the sparsity parameter $\theta$ ).
- This improves upon prior work that required $\Omega(n^2)$ decoding time for the same test complexity.
Improved Scheme (Theorem 2):
- By integrating partitioning and permutation amplification, the authors achieve a further reduction in decoding time.
- Tests: Remains $O(k \log n)$ .
- Decoding Time: $O(k^{1+\delta} \log n)$ for any fixed $\delta > 0$ .
- The hidden constant in the decoding time depends on $\delta$ .
- The scheme guarantees asymptotically vanishing error probability ( $P_e \to 0$ as $n \to \infty$ ).

Significance and Claims
The paper claims to achieve "(nearly) the best of both objectives" in terms of the number of tests and decoding time for non-adaptive learning of Erdős–Rényi graphs. Specifically:

It matches the information-theoretically optimal scaling for the number of tests, $O(k \log n)$ .
It significantly improves the decoding complexity from quadratic in $n$ (or $k^{1.5}$ ) to nearly linear in $k$ ( $k^{1+\delta}$ ).
The authors note that while the binary splitting concept is similar to that in standard group testing, the graph learning setting introduces unique challenges, such as the fact that a negative test only rules out non-edge pairs (not individual vertices) and that internal edges within a block can render all tests containing that block positive, providing no information about non-edges. The proposed partitioning and permutation techniques are specifically designed to mitigate these issues.

The work is presented as a theoretical advancement in combinatorial inference, focusing on the trade-off between query complexity and computational complexity in the non-adaptive setting. The authors conclude by suggesting future directions, such as reducing the decoding time to $O(k \log n)$ , improving test constants, extending the approach to random hypergraphs, and considering noisy settings.