PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Recovery of Latent Coordinate Structure from Sparse Observations of the Hypercube

Rares-Darius Buhai, Davide Mazzali, Weronika Wrzos-Kaminska

arXiv:2610.11741v1cs.DS

TL;DR

The paper asks whether hidden Boolean coordinates can be recovered from a sparse sample of edges in a percolated hypercube. It combines sum-of-squares methods with rounding and gives a polynomial-time algorithm that recovers almost all vectors, while showing a limitation of the degree-2 relaxation.

  • Problem

    The paper studies whether the hidden Boolean vectors assigned to vertices of a percolated hypercube can be recovered from only the arbitrarily renamed observed graph.

    Source: §1 · p. 3

  • Method

    The algorithm combines a degree-4 sum-of-squares certificate with polynomial-time rounding to recover coordinate cuts that determine the hidden vectors up to hypercube symmetries.

    Source: §1 · p. 4, §2.1 · p. 6, §2.2 · p. 8

  • Results

    For p≥C log d/d, a polynomial-time algorithm recovers the hidden vectors exactly on all but a 1/d^O(1) fraction of vertices with probability 1−o_d(1).

    Source: §1 · p. 4

  • Takeaways & Limitations

    The result answers the open question of achieving the prior recovery guarantee with a polynomial-time algorithm.

    Source: §1 · p. 4

    In the regime p=Θ(log d/d), the degree-2 relaxation does not provide the Fourier concentration needed by the analysis, and coordinate-cut error cannot be better than Ω(1/log d) using that relaxation.

    Source: §2.3 · pp. 14–15

Abstract

from arXiv · show

Recovering latent geometric structure from graph observations is a well-studied problem in statistical inference. Kapralov, Trevisan, and Wrzos-Kaminska (2026) introduced the problem of recovering the coordinate structure of the Boolean hypercube from a small random sample of its edges. More specifically, there are $n=2^d$ vertices, each corresponding to a distinct "feature" vector in $\{\pm 1\}^d$. Between each pair whose feature vectors are at Hamming distance one, an edge is observed independently with probability $p$. As long as the expected degree $pd$ is $\gtrsim \log d = \log \log n$, we give a polynomial-time algorithm that, given only the graph of observed edges, correctly recovers the entire feature vector of all but a vanishing fraction of vertices. This matches the information-theoretic guarantee of Kapralov, Trevisan, and Wrzos-Kaminska in polynomial rather than exponential time, resolving the algorithmic question left open by their work. Our algorithm combines a degree-$4$ sum-of-squares certificate for the structure of balanced near-minimum cuts with a rounding scheme originally developed for tensor decomposition by Ma, Shi, and Steurer (2016). The analysis relies on two novel ingredients: a sum-of-squares version of the Friedgut-Kalai-Naor theorem in Boolean Fourier analysis and a spectral concentration result for the observed subgraph of the hypercube. Finally, we provide a justification for why higher-degree sum-of-squares might be needed by showing a limitation of the basic SDP relaxation of this problem.

1 Introduction

The introduction frames recovery of latent structure from observed graphs through the problem of recovering hidden Boolean coordinates from a renamed, percolated hypercube. It presents a polynomial-time answer to the open question of whether the prior recovery guarantee can be achieved efficiently.

1 Introduction

  • The task is to recover each renamed vertex’s hidden Boolean vector from the observed graph, where an edge reveals a one-coordinate difference but not which coordinate.The hypercube has n=2^d vertices, and each edge is retained independently with probability p.Source: §1 · p. 3
  • For p≥C log d/d, a polynomial-time algorithm recovers the hidden vectors exactly on all but a 1/d^O(1) fraction of vertices with probability 1−o_d(1).Recovery is from an arbitrarily renamed sample of the percolated hypercube.Source: §1 · p. 4
  • The algorithm combines a degree-4 sum-of-squares certificate with polynomial-time rounding, supported by a sum-of-squares Friedgut-Kalai-Naor theorem and spectral concentration for the percolated hypercube.The challenge is retaining enough hidden coordinate structure in the relaxation for rounding to recover the Boolean vectors.Source: §1 · p. 4

1.1 Related work

  • Unlike prior fixed-dimensional latent-geometry settings, this model has d=log2 n and can have expected degree Θ(log d); the guarantees are incomparable because the geometry, observations, and recovery criteria differ.The paper also notes that its recovery is exact on almost all vertices, up to a common hypercube symmetry.Source: §1.1 · p. 5

1.2 Organization

  • The paper proves the sum-of-squares Friedgut-Kalai-Naor result in Section 4, spectral concentration in Section 5, combines them for recovery in Section 6, and proves a degree-2 lower bound in Section 7.Source: §1.2 · pp. 5–6

2 Technical overview

The technical overview develops a recovery approach based on coordinate cuts, a degree-4 sum-of-squares certificate, and rounding. It presents the supporting cut-value concentration and FKN arguments, combines them to complete the proof outline, and explains why the degree-2 relaxation is insufficient.

2.1 Recovery via Coordinate Cuts

  • The d coordinate cuts determine the latent embedding up to coordinate permutations and sign flips; agreement of at least 1−ε per cut recovers at least 1−dε of vertices.The cuts are the latent coordinate functions represented on the observed graph.Source: §2.1 · p. 6
  • The algorithm constrains candidate cuts to be Boolean, balanced, and low-value, and each latent coordinate cut satisfies these constraints with high probability.These constraints define the system used to seek the unknown coordinate cuts.Source: §2.1 · p. 7
  • A degree-4 SoS quartic proxy feeds the [MSS16] rounding theorem, yielding polynomial-time cuts with inverse-polynomial agreement error.The rounded cuts recover the latent coordinates up to permutation and signs.Source: §2.1 · p. 8

2.2 From balanced low-value cut to the quartic proxy

  • A poly(n)-time certificate accepts only when every balanced near-minimum cut is close to a coordinate cut, and accepts random hypercube samples with high probability, unlike the exp(Õ(n))-time certification implicit in [KTW26].The algorithm may return “unsure”; its guarantee is soundness for every input graph and completeness for samples from Q_d(p).Source: §2.2 · p. 9

2.2.1 Proof outline of the quartic proxy lemma

  • For balanced Boolean functions, near-minimum full-hypercube cut value implies almost all Fourier mass is degree-1, so FKN gives a dictator; constant-ε bounds miss the needed inverse-polynomial error, motivating coordinate-cut comparison.Source: §2.2.1 · pp. 9–10

2.2.2 Cut value concentration

  • In the sparse regime p=Θ(log d/d), atypical-degree vertices make singleton cuts deviate from expected value; allowing additive error Z yields spectral concentration and a polynomial-time-checkable condition.The error is supported on vertices whose sampled degree is far from its expected degree.Source: §2.2.2 · p. 12
  • With probability 1−o_d(1), degree-2 sum-of-squares proofs certify cut-value concentration, including for each coordinate Laplacian.The spectral argument controls low Fourier degrees multiplicatively and high degrees up to additive O(log d) error after removing atypical-degree vertices; it applies when p≥C log d/d.Source: §2.2.2 · p. 13

2.2.3 FKN theorem

  • A degree-4 sum-of-squares FKN theorem certifies a quartic Fourier-mass proxy for concentration on a dictator.The proof manipulates the variance of the linear part using degree-2 or degree-4 inequalities, avoiding Paley–Zygmund; using the sum-of-squares Bonami–Beckner lemma would require degree higher than 4.Source: §2.2.3 · p. 14

2.2.4 Patching the proof outline with sum-of-squares proofs

  • The proof outline combines the spectral certificate with the sum-of-squares FKN theorem to obtain the desired inverse-polynomial bound.Weighting each coordinate-specific cut comparison by the squared coordinate correlation and summing yields a degree-4 inequality; the FKN theorem bounds its quartic deficit by excess cut value.Source: §2.2.4 · p. 14

2.3 Limitations of the degree-2 relaxation

  • At p=C log d/d, a degree-2 pseudoexpectation can satisfy the constraints while its coordinate-cut Fourier mass is at most 1−Ω(1/log d).By contrast, degree-4 pseudoexpectations satisfy a quartic Fourier-mass bound of 1−1/d^O(1); thus degree-2 cannot recover coordinate cuts with error better than Ω(1/log d), which gives no guarantee on correctly recovered vertices when error exceeds 1/d.Source: §2.3 · pp. 14–15

3 Preliminaries

This section establishes notation and background for the paper’s sum-of-squares analysis, Boolean Fourier arguments, rounding, and concentration bounds.

3 Preliminaries

  • The paper’s Fourier notation uses normalized inner products, character functions, coordinate flips, and projections onto Fourier levels.The characters are indexed by subsets of coordinates, with χ_i denoting the singleton character.Source: §3 · p. 15

3.1 Sum-of-squares proofs

  • A sum-of-squares proof derives polynomial nonnegativity from a system of polynomial inequalities, with proof chains allowing successive bounds to be combined.The section introduces this proof framework before describing pseudo-distributions and pseudo-expectations.Source: §3.1 · pp. 15–16

3.1.1 Pseudo-distributions and pseudo-expectations

  • Degree-t pseudo-distributions are finitely supported functions nonnegative on squares of sufficiently low degree, and their weighted sums define pseudo-expectations.Constrained pseudo-distributions satisfy positivity conditions incorporating the system’s inequalities; such distributions inherit inequalities proved by sum of squares.Source: §3.1.1 · p. 16

3.1.2 Sum-of-squares proofs for basic inequalities

  • The section records sum-of-squares versions of basic inequalities, including the almost triangle inequality, Cauchy–Schwarz, and Jensen’s inequality for squares.It also notes that feasible, explicitly bounded systems admit an algorithm for computing an approximately satisfying pseudo-distribution in time (n + m)^O(t).Source: §3.1.2 · p. 17, §3.1.1 · p. 17

3.1.3 Sum-of-squares proofs for basic analysis of Boolean functions

  • The Boolean-function toolkit includes sum-of-squares Fourier expansion and Parseval identities, including a version for Boolean-valued functions.These claims are used to reason about Fourier coefficients within the proof system.Source: §3.1.3 · pp. 18–19

3.2 Sum-of-squares rounding

  • The rounding background provides an algorithmic guarantee from Ma, Shi, and Steurer for vectors transformed by a low-degree polynomial under stated norm and constraint conditions.The cited algorithm runs in time (n + d + d′)^O(ℓ).Source: §3.2 · p. 19

3.3 Concentration inequalities

  • The concentration toolkit includes scalar Bernstein, matrix Bernstein, and Bernstein bounds for random variables with bounded dependency.The bounds are stated for mean-zero variables or matrices with bounded magnitude or norm, with the dependent case specifying a maximum dependency-graph degree.Source: §3.3 · p. 20

4 Sum-of-squares FKN theorem

The section establishes a degree-4 sum-of-squares version of the Friedgut-Kalai-Naor theorem [FKN02]. Its proof uses low-degree Fourier projections and controls the variance of the squared projection.

4 Sum-of-squares FKN theorem

  • The section presents a degree-4 sum-of-squares proof of the Friedgut-Kalai-Naor theorem [FKN02].The proof follows the outline of the Boolean FKN proof in O’Donnell’s treatment.Source: §4 · p. 20
  • The proof projects f onto low Fourier levels and uses that the square of a degree-1 projection has degree at most 2.It invokes sum-of-squares Fourier expansion, Parseval, and the triangle inequality in this argument.Source: §4 · pp. 20–22
  • After showing that ℓ² is close to the constant function 1, the proof bounds the variance of ℓ² to complete its argument.It compares the variance with the expression obtained by replacing the mean by 1, then concludes by rearranging.Source: §4 · pp. 21, 23

5 Spectral concentration

This section establishes high-probability spectral bounds for randomly sampled hypercubes, showing that at sampling probability at least C log d/d the sampled and expected Laplacians are close after excluding a small set of vertices and that Mσ is positive semidefinite for both signs when p is sufficiently large. A Schur complement argument combines the bounds to prove the conclusion.

5 Spectral concentration

  • For p ≥ C log d/d, with probability at least 1 − 1/d^C1, removing a set of at most n/d^C2 vertices yields spectral concentration of the sampled Laplacian around pL.The constants depend on the stated accuracy and failure-probability parameters; the removed vertices are those with atypical degrees.Source: §5 · p. 24
  • For a subgraph G=(V_d,E) of Q_d, let R={x∈V_d: |deg_G(x)−pd|>γpd}; with probability at least 1−1/d^(C1+10) over sampling Q′_d, |R|≤n/d^C2.Source: §5 · p. 24
  • After excluding bad-degree vertices, the proof establishes concentration of Laplacian bilinear forms on disjoint good-vertex sets, then converts it to spectral-norm closeness.The cut concentration holds simultaneously for every such pair with probability at least 1 − 1/d^(C1+10); the conversion uses a converse expander mixing lemma.Source: §5 · pp. 25, 29
  • The low Fourier-degree subspace has small dimension, so matrix concentration shows L′ is well-approximated by pL; the proof also handles cross terms between low and high Fourier degrees.Source: §5 · pp. 30, 33
  • For nonempty Fourier supports, the proof bounds the relevant coefficient by Bernstein’s inequality using a dependency graph of maximum degree d.The coefficient is rewritten as a sum of bounded random variables whose dependencies arise only between neighboring hypercube vertices.Source: §5 · p. 36
  • With probability at least 1−1/d^C1, the degree-outlier set R has size at most n/d^C2, with additional bounds for both σ∈{±1}.The simultaneous estimates include 1/d^C2 + 1/n^1/20 ≤ 1/d^10.Source: §5 · p. 37
  • With probability at least 1−5/d^(C1+9), the simultaneous bounds imply M_σ ⪰ 0 for both σ∈{±1} when p ≥ C log d/d.The argument uses γ=ε/1000 and assumes d is sufficiently large; positive semidefiniteness follows through a Schur complement.Source: §5 · pp. 37–38

6 Coordinate cut recovery with sum-of-squares

The section gives a polynomial-time method for recovering the hypercube’s latent coordinate cuts from a sparse percolated sample. Its degree-4 sum-of-squares analysis shows that near-minimum cuts in the sample retain enough structure for rounding to recover those coordinates.

6 Coordinate cut recovery with sum-of-squares

  • At p ≥ C log d/d, a polynomial-time algorithm recovers each latent coordinate cut with average squared error at most d^-10, with high probability.The algorithm’s output coordinates agree exactly with the hidden vectors on all but a vanishing fraction of vertices.Source: §6 · p. 39, §6.2 · p. 49
  • A degree-4 sum-of-squares proof shows that balanced cuts with small sampled cut value also have small value in the original hypercube.Near-minimal balanced cuts in the original cube are close to coordinate cuts by Fourier analysis and the FKN theorem.Source: §6 · p. 39

6.1 Cut approximation (proof of Lemma 6.3)

  • With high probability, all coordinate cuts have values in the subsampled hypercube close to their expected values.This concentration result is used alongside the cut-approximation argument.Source: §6 · p. 40

6.2 Proof of Theorem 6.1

  • The proof combines cut approximation and the sum-of-squares FKN theorem with the rounding algorithm of Ma, Shi, and Steurer (2016) to recover the coordinate cuts.The resulting rounded functions have average squared error at most d^-10 from the hidden coordinate cuts.Source: §6.2 · pp. 47, 49

7 Degree-2 lower bound

The section exhibits a limitation of the degree-2 sum-of-squares relaxation in the sparse regime. Its relaxation can fail to certify the Fourier concentration required by the paper’s recovery argument, motivating higher-degree certificates without proving that degree-2-based algorithms are impossible.

7 Degree-2 lower bound

  • The degree-2 lower bound is not a formal proof that no algorithm based on degree-2 sum-of-squares can recover the latent feature vectors.The authors conclude only that their approach needs higher-degree certificates.Source: §7 · pp. 49–50
  • In the sparse regime, a degree-2 pseudoexpectation can leave coordinate Fourier mass at most 1 - Ω(1/log d), rather than the 1 - 1/poly(d) concentration required by the recovery argument.Thus this relaxation does not provide the Fourier concentration needed for the FKN-based recovery argument.Source: §7 · pp. 49–50
  • The construction uses an odd unit vector q(x) orthogonal to x in building feasible vectors for the degree-2 SDP.The text defines the SDP matrix through inner products of vectors F(x).Source: §7 · pp. 50, 52

Related papers

Loading 2610.11741v1…