acceptodds
Withdrawn from ICLR 2027

Hypergraph cycle enumeration for efficient inference of planted -XOR with smooth trade-off

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

We introduce hypergraph cycle enumeration (HCE), a simple spectral framework for detecting and recovering planted signals in noisy hypergraph inference problems. In this work, we focus on planted noisy -XOR, a canonical average-case constraint satisfaction problem (CSP) closely connected to tensor PCA, refutation of random CSPs, and computational-statistical gaps in high-dimensional inference. However, our algorithm can be applied to a broader category of tensor PCA problems. We show that HCE yields recovery with a hierachical threshold (determined by a parameter ), matching the Kikuchi spectral threshold up to -dependent constants while giving a direct cycle-counting interpretation of the mechanism. Both theoretically and empirically, HCE achieves comparable recovery behavior to Kikuchi methods while using a substantially smaller matrix representation, leading to significant runtime and memory improvements in the sparse regimes we test.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
PCA, tensor PCA, k-XOR, Hypergraph, Kikuchi

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_G6PTOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

This paper proposes Hypergraph Cycle Enumeration (HCE) for planted noisy k-XOR. The paper presents weak recovery results and empirical results verify that HCE matches Kikuchi's overlap with less memory and runtime in sparse regimes.

Critical strengths

HCE matches Kikuchi's overlap with less memory and runtime in sparse regimes.

Critical weaknesses
  1. The writing is dense and difficult to fully understand for someone without substantial background on this particular problem. Many symbols are also not defined before first use.

  2. The novelty seems to be limited compared to existing literature. The main HCE weak recovery result seems to be weaker than the state of the art [17].

  3. Some claims are not theoretically/empirically supported or not stated rigorously.

Questions for authors
  1. Table 1 shows HCE is worse than Kikuchi in time for some values of kk, e.g., k=4k=4. It seems the main claimed advantage is not supported asymptotically.

  2. HCE and Kikuchi should be compared using the same resource budget. To have a fair comparison, the paper should plot overlap against wall-clock/memory (Pareto frontier), not at equal level.

  3. All experiments use n≤180n ≤ 180 and kk = 4–6. The sizes too small to align with the asymptotic statements.

  4. [17] achieves log-free sharp thresholds for detection and weak recovery with the normalized Kikuchi matrix. What does HCE offer beyond the conceptual cycle interpretation and finite-size constants?

  5. ZlZ_l is as hard to compute as the matrix. Is there an efficient detection test that does not need exact counting?

  6. Can authors show an experiment where l≥6l ≥ 6 for odd kk, so that trimming actually matters?

  7. Please add confidence intervals/standard errors, more instances for runtime, and show the variance across seeds for the heatmaps at the transition boundary.

Reviewer_B5fpOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors propose Hypergraph Cycle Enumeration (HCE) for detection and recovery of planted noisy k-XOR. In the framework of the Kikuchi hierarchy, at level L, products of clauses supporting a pair {i,j} are summed into entry (i, j) of an n x n matrix. The top eigenvector is a noisy estimate of the planted assignment. The paper claims a smooth tradeoff between the number of clauses needed and level and present three results: 1) at fixed level, a log-free detection guarantee via counting even covers, 2) for even k, a weak-recovery guarantee, and 3) a meet-in-the-middle implementation with an exact overlap recurrence. The experiments (n=30 to 120) compare the proposal with Kikuchi spectral methods on recovery overlap, compute time and memory.

The paper's n x n representation is a real space saving over the n^L x n^L Kikuchi matrix. However, I recommend rejection because (see comments below): 1) the recovery theorem does not establish the smooth tradeoff the paper claims, 2) prior work with stronger results was not cited, and 3) the experiments are too small to demonstrate practicality.

Critical strengths
  1. A straightforward, interpretable n x n statistic at each level. The hypergraph cycles expose an explicit parity signal. Log-free detection.

  2. Competently developed theory that contributes 1) a non-trivial trace-moment bound in the i.i.d models, 2) a precise meet-in-the-middle recurrence, a parity result for even k with support-based trimming for odd k.

Critical weaknesses
  1. Claim overstatement: The recovery theorem does not establish a "smooth trade-off" or a "third known hierarchy". The recovery threshold carries a factor of (log n)^{(k+1)l+3}, which gets worse quickly by level. This is the opposite of a smooth tradeoff. Also, the paper claims the "same threshold" while omitting the l-dependent polylog factor re: "succeeds at same threshold clause density"

  2. Novelty: Prior work (not cited in the paper), Mao (2026) "Near Optimal Algorithms for Noisy k-XOR under Low-Degree Heuristic", contributed a stronger result by proving a growing-level, log-free recovey tradeoff for essential the same sums. That paper (Theorem 1.4) claims recovery in time n^{D+O(1)} from m ≳ (2^k k^{k/2}/k!) · n^{k/2}/(δ² D^{k/2−1}) samples, allows the level to grow to 0.1 log n / log log n, includes all k >= 3, with no log loss and a matching low-degree lower bound for detection. If I understand it correctly, their construction is exactly the HCE's witnesses. This work, from April 2026, falls outside the "contemporaneous criterion" of the conference. Also, I couldn't follow the statement the Kikuchi methods do not apply to ood k. The authors cite Schmidhuber & Hastings, which covers every k>=3 (a contradiction that smooth tradeoff and odd k are HCE's distinctions).

Also missing from citations:

  • Gupta, He, O'Donnell and Singer (2025) (use birthday paradox collisions for even covers with detect under Kikuchi's runtime),

  • Basu, Hsieh, Lin and Manohar (solve planted CSPs below n^{k/2} with an n^{O(l)} trade-off)

  • Schmidhuber et al (2024) (quartic quantum speedups)

  • Kothari and Xu (2026) (a log-free smooth trade-off for Kikuchi spectral methods with growing level in tensor PCA)

  1. Experimental setup:
  • experiments are toy size, the smallest instances n=30 can be solved by brute force, largest is n=120. This matters because it does't demonstrate practicality.

  • Unfair comparison: HCE gets extra post-processing and Kikuchi gets a a weaker decoder. Also, the claim "60x faster" is based on HCE on 8 processors and Kikuchi on 1.

  • At small l it needs C >= 1.84, against tested C <= 0.25. So the experiments operate there the theorem doesn't give guarantees

Questions for authors
  • How does the work differ from Mao (2026)?
  • Kothari & Xu (tensor PCA) stand against "third known hierarchy". How would you justify this claim?
  • What are c_k and the runtime of the detection test?
  • Could you provide an evidence of experimental scaling (eg, n in the hundreds and with level >=4. HCE is costlier than Kikuchi in this case n^{l+2} )
  • Could you give a thread-count equivalent result for the "60x faster" claims?
Reviewer_vMScOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The authors introduce a hierarchical algorithmic approach similar to the SoS or Kikuchi hierarchies which they call “hypergraph cycle enumeration (HCE) hierarchy” and which is used to solve the k-XOR problem. For this hierarchy they provide detection and recovery guarantees. The HCE scheme enables to match the fixed level Kikuchi spectral threshold for weak recovery while using less memory and runtime.

Critical strengths

The approach is an interesting alternative to the SoS or Kikuchi hierarchies

Critical weaknesses

The improvement compared to the SoS and Kikuchi hierarchies is not clear.

Questions for authors

General questions:

Introduction

  • lines 36 - 41: what do you mean by “parity” ?
  • lines 55 I would recall the notation \tilde{\Theta}
  • lines 68 - 86. Some of the contributions are not clear. Especially the second item.
  • lines 79 - 86: You first mention that when comparing the complexity of HCE and the Kikuchi method, the asymptotic complexity is worse for HCE. Then you say

Preliminaries

  • Equation 2: The notation U,V \in {[n] \choose \ell} is not very clear. I understand that U and V are subsets of bits of size \ell.. but this does not align with the usual definition of the {n choose k} notation. Is this common notation in signal processing ?
  • line 116 - 117, I think you should clarify the definition of the \mathcal{K} hypergraph. At least specify the definition of the vertices. From what I understand, the vertices are the indices 1,2,3,… , n and the hyperedges are grouping k such indices. This should be clarified.
  • line 121: If I’m not wrong, the symmetric difference is usually defined between two sequences or two sets, i.e. A\Delta B. It is therefore not very clear what you mean by \Delta(S).. is it the set of all symmetric differences of any pair of two binary sequences ? or does the set \mathcal{S} never contain more than two sequences ? Also the definitions of the symmetric difference on line 121 and on line 127 do not seem to be the same. On line 121

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.