A Fast Hierarchical Splitting Approach for Non-Adaptive Learning of Random Hypergraphs

Technical Summary: A Fast Hierarchical Splitting Approach for Non-Adaptive Learning of Random Hypergraphs

Problem Statement
This work addresses the problem of learning an unknown 3-uniform hypergraph $H = (V, E)$ using edge-detecting queries. In this setting, the learner does not have direct access to the hyperedge set $E$. Instead, the learner issues non-adaptive queries on subsets of vertices $S \subseteq V$. A query returns a positive outcome if and only if $S$ contains at least one hyperedge entirely within it. The objective is to design a querying strategy that recovers the exact set of hyperedges with high probability using the minimum number of tests, while also minimizing the computational time required for decoding.

The paper focuses specifically on random hypergraphs generated under the Erdős–Rényi (ER) model, denoted as $ER(n, q)$. In this model, each potential hyperedge appears independently with probability $q = \Theta(n^{-3(1-\theta)})$ for $\theta \in (0, 1)$. The expected number of hyperedges is $m = q \binom{n}{3} = \Theta(n^{3\theta})$.

Context and Motivation
While graph learning (recovering pairwise edges) has been extensively studied, extending these techniques to hypergraphs (recovering multi-way interactions) presents significant challenges. Prior work by Austhof, Reyzin, and Tani [ART25] proposed a scheme for 3-uniform random hypergraphs that achieves $O(m \log n)$ query complexity but suffers from a decoding time of $\Omega(n^3)$, which is cubic in the number of vertices. This high decoding complexity limits the practicality of existing non-adaptive approaches for large-scale hypergraphs. The authors note that while the binary splitting framework has been successfully adapted for graph learning [TS25], extending it to 3-uniform hypergraphs introduces substantial new difficulties due to the richer combinatorial structure of hyperedges.

Methodology: Hierarchical Splitting Framework
The authors propose a new testing and decoding scheme that extends the binary splitting framework to a non-adaptive setting for 3-uniform hypergraphs. The approach relies on a ternary hierarchical partitioning of the vertex set.

1. Hierarchical Partitioning:
   The vertex set $V$ is recursively partitioned into blocks across levels $\ell = \lceil \log_3 m^{1/3} \rceil, \dots, \log_3 n$. At level $\ell$, there are $g = 3^\ell$ blocks, each containing $n/g$ vertices. This forms a ternary tree structure where each block at level $\ell$ is subdivided into three child blocks at level $\ell+1$.

2. Testing Procedure:
   The testing is randomized and non-adaptive. For each level $\ell$, the algorithm performs $C_2 m^{2/3}$ independent repetitions. In each repetition, every block is assigned uniformly at random to one of $C_1 m^{1/3}$ tests. A test includes all vertices belonging to the blocks assigned to it.

   • At the final level ($\ell = \log_3 n$), where blocks are singletons, the process is repeated $C' \log n$ times to ensure high-probability recovery.
   • The total number of tests across all levels is $O(m \log n)$.

3. Decoding Procedure:
   The decoder operates deterministically in a coarse-to-fine manner, maintaining a set of "possibly defective" (PD) triples of blocks.

   • Initialization: At the coarsest level, all block triples are considered candidates.
   • Refinement: For each level, if a triple of blocks $(H_i, H_j, H_k)$ is not eliminated by any negative test (i.e., no test containing all three blocks returned 0), it is refined. Each block is split into three children, generating $\binom{9}{3} = 84$ child triples.
   • Elimination: If a test containing a triple returns negative, that triple and all its descendants are discarded.
   • Termination: At the final level (singleton vertices), any surviving triple is declared a hyperedge.

Key Technical Challenges and Solutions
The authors identify three primary obstacles in extending binary splitting from graphs to 3-uniform hypergraphs:

1. Complex Recursive Structure: Unlike graphs where an edge lies within one block or connects two, a 3-uniform hyperedge can lie within one block, span two blocks, or involve three distinct blocks. This leads to a significantly richer family of descendants after splitting.
2. Candidate Growth: Managing the number of candidate triples that survive negative tests is more intricate than in the graph case.
3. Decoding Efficiency: Ensuring the number of surviving candidates remains manageable to achieve sub-cubic decoding time.

To address these, the authors introduce a "typical set" of hypergraphs where structural properties (number of defective blocks, defective pairs, and degrees of non-defective nodes) are tightly concentrated around their expectations. They prove that random ER hypergraphs fall into this typical set with high probability. By bounding the number of defective configurations and applying concentration inequalities (Chernoff and Chebyshev), they demonstrate that the number of surviving candidate triples at each level remains bounded, preventing exponential blow-up in the decoding process.

Results
The paper establishes the following theoretical guarantees (Theorem 1) for a random 3-uniform hypergraph with expected $m$ edges:

• Query Complexity: The scheme uses $O(m \log n)$ tests, matching the optimal order of query complexity established by prior work.
• Decoding Time:
  • For $\theta > 2/3$: The decoding time is $O(m^{5/3} \log n)$.
  • For $\theta \le 2/3$: The decoding time is $O(m^{5/3} \log^2 m \log n)$.
• Correctness: The algorithm recovers the exact hyperedge set with probability $1 - o(1)$ as $n \to \infty$.

These results represent a significant improvement over the $\Omega(n^3)$ decoding time of the COMP scheme [ART25], reducing the complexity to a function that is sub-cubic in $n$ and polynomial in $m$.

Significance and Limitations
The authors claim that their work significantly improves the decoding complexity of non-adaptive hypergraph learning while maintaining optimal query complexity. This bridges the gap between theoretical query efficiency and practical computational feasibility for random hypergraphs.

The paper explicitly notes limitations regarding generalization:

• k-Uniform Extension: While the framework can be formally extended to $k$-uniform hypergraphs, the number of candidate tuples generated during refinement grows as $\binom{k^2}{k}$, which is exponential in $k$. Consequently, the decoding time incurs an exponential dependence on $k$, making the direct extension inefficient for large $k$. The current work focuses on the 3-uniform case.
• Permutation Techniques: The authors discuss the possibility of further accelerating decoding using permutation-based amplification (similar to techniques in graph learning) but note that this requires the existence of specific families of almost 3-wise independent permutations with near-constant evaluation time, which is currently an open and non-trivial construction problem.

In conclusion, this work provides a fast, non-adaptive algorithm for learning random 3-uniform hypergraphs, offering a substantial reduction in decoding time compared to previous state-of-the-art methods without sacrificing query efficiency.