Source-linked AI summary
Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery
Emmanuel Abbe, Afonso S. Bandeira, Annina Bracher, Amit Singer
TL;DR
The paper asks how graph connectivity must scale to recover binary vertex labels exactly from noisy, censored pairwise measurements. It develops information-theoretic conditions and an efficient SDP-based recovery method. The results connect the low-SNR threshold to Shannon capacity and show that the SDP approaches the Erdős-Rényi threshold within a factor of 2.
Problem
The paper asks what graph connectivity is needed for exact recovery of binary vertex labels from noisy pairwise observations, since connectivity alone is not generally sufficient under noise.
Source: Y E = BGxV ⊕ZE, (2) · p. 2Method
The paper derives information-theoretic recovery conditions for random and general graphs and proposes an efficient semidefinite-programming recovery algorithm.
Source: Y E = BGxV ⊕ZE, (2) · p. 4, Y E = BGxV ⊕ZE, (4) · p. 6Results
The paper identifies Shannon capacity as the threshold in the low-SNR regime and reports that its SDP approaches the Erdős-Rényi threshold up to a factor of 2.
Source: Y E = BGxV ⊕ZE, (2) · p. 4, Y E = BGxV ⊕ZE, (4) · p. 6Takeaways & Limitations
For Erdős-Rényi graphs, the proposed SDP provides an efficient recovery guarantee within a factor of 2 of the threshold.
Source: Y E = BGxV ⊕ZE, (2) · p. 4The paper cannot derive a necessary condition that bounds the Cheeger constant away from zero, despite giving a sufficient condition that depends on it.
Source: Y E = BGxV ⊕ZE, (4) · p. 6, §4.2 · p. 13
Abstract
from arXiv · showhide
We consider the problem of clustering a graph $G$ into two communities by observing a subset of the vertex correlations. Specifically, we consider the inverse problem with observed variables $Y=B_G x \oplus Z$, where $B_G$ is the incidence matrix of a graph $G$, $x$ is the vector of unknown vertex variables (with a uniform prior) and $Z$ is a noise vector with Bernoulli$(\varepsilon)$ i.i.d. entries. All variables and operations are Boolean. This model is motivated by coding, synchronization, and community detection problems. In particular, it corresponds to a stochastic block model or a correlation clustering problem with two communities and censored edges. Without noise, exact recovery (up to global flip) of $x$ is possible if and only the graph $G$ is connected, with a sharp threshold at the edge probability $\log(n)/n$ for Erd\H{o}s-R\'enyi random graphs. The first goal of this paper is to determine how the edge probability $p$ needs to scale to allow exact recovery in the presence of noise. Defining the degree (oversampling) rate of the graph by $\alpha =np/\log(n)$, it is shown that exact recovery is possible if and only if $\alpha >2/(1-2\varepsilon)^2+ o(1/(1-2\varepsilon)^2)$. In other words, $2/(1-2\varepsilon)^2$ is the information theoretic threshold for exact recovery at low-SNR. In addition, an efficient recovery algorithm based on semidefinite programming is proposed and shown to succeed in the threshold regime up to twice the optimal rate. For a deterministic graph $G$, defining the degree rate as $\alpha=d/\log(n)$, where $d$ is the minimum degree of the graph, it is shown that the proposed method achieves the rate $\alpha> 4((1+\lambda)/(1-\lambda)^2)/(1-2\varepsilon)^2+ o(1/(1-2\varepsilon)^2)$, where $1-\lambda$ is the spectral gap of the graph $G$.
1. Introduction
The paper frames its subject as an inverse problem on a graph, where vertex variables and edge variables are linked by a probabilistic dependency model. It specializes this framework to Boolean variables and a symmetric kernel depending on the XOR of the incident vertex variables.
1. Introduction
- Graph inverse problems use a graphical structure to govern dependencies between observed and unknown variables.In the described setup, unknown variables attach to vertices and observed variables to edges.Source: §1 · p. 1
- The edge-variable model factorizes through a local probability kernel Q for each edge.Q is defined as a local probability kernel for the edge variable given the two incident vertex variables.Source: §1 · pp. 1–2
- The paper assumes Boolean edge and vertex variables and a symmetric kernel that depends only on the XOR of the vertex variables.The passage specifies that the kernel's symmetry means its probability depends on the XOR of the two incident variables.Source: §1 · p. 2
Y E = BGxV ⊕ZE, (2)
The paper studies exact recovery of Boolean vertex labels from noisy edge measurements on a graph, a setting connected to censored community observations. It focuses on how graph connectivity must be strengthened to recover the partition despite noise, and proposes an SDP-based approach alongside information-theoretic recovery conditions.
Y E = BGxV ⊕ZE, (2)
- Noisy pairwise parity observations reveal whether two vertices share a community, but only on edges present in the graph.The linear observation model is Y_E = B_G x_V ⊕ Z_E, where B_G is the graph incidence matrix and Z_E represents noise.Source: Y E = BGxV ⊕ZE, (2) · p. 2
- In the noiseless setting, a connected graph suffices to recover the partition, but noisy observations require stronger connectivity conditions.A global flip of all labels leaves the observations unchanged, so recovery is of the partition rather than the exact colors.Source: Y E = BGxV ⊕ZE, (2) · p. 2
- The model also has links to coding, planted constraint satisfaction, and synchronization, including one-dimensional synchronization.The coding interpretation is a 2-right-degree LDGM code; the synchronization equivalence holds when the dimension is one.Source: Y E = BGxV ⊕ZE, (2) · pp. 3–4
- The paper targets exact recovery for random Erdős-Rényi and deterministic graphs and proposes an efficient semidefinite-programming method that approaches the threshold within a factor of 2 in the Erdős-Rényi case.The model is also connected to planted correlation clustering with two clusters and censored, probabilistic measurements.Source: Y E = BGxV ⊕ZE, (2) · pp. 3–4
2. Related work
The related-work discussion contrasts prior exact-recovery guarantees with the paper's near-tight rates, and notes independently obtained information-theoretic results. It also identifies partial recovery as a related line of work.
2. Related work
- The discussion notes that [22] studies partial recovery for this model.Source: §2 · p. 4
- Prior work gave an SDP sufficient condition and exact-recovery guarantees, while the paper reports near-tight graph-size and edge-density bounds for noise arbitrarily close to 1/2, off by at most a factor of 2.The cited analysis of Chen, Huang, and Guibas is described as optimal only up to polylogarithmic factors in this setting.Source: §2 · p. 5
- Chen and Goldsmith independently obtained IT converse and direct guarantees for a more general problem, but their results were only optimal up to polylogarithmic factors.Source: §2 · p. 5
3. Model and results
The section introduces the paper's focus on the linear Boolean model.
3. Model and results
- The paper focuses on the linear Boolean model.Source: §3 · p. 5
Y E = BGxV ⊕ZE, (4)
For Boolean recovery under i.i.d. noise, the paper establishes information-theoretic exact-recovery conditions and an efficient SDP guarantee. The Erdős–Rényi bounds match, while the SDP guarantee is within a factor of 2 of the information-theoretic bound.
Y E = BGxV ⊕ZE, (4)
- The model uses Boolean vertex variables with modulo-2 addition and i.i.d. Bernoulli noise on Erdős–Rényi or deterministic d-regular graphs, with a uniform prior and ε in [0, 1/2].At ε = 0 there is no noise; at ε = 1/2, exact recovery is impossible regardless of graph connectivity.Source: Y E = BGxV ⊕ZE, (4) · p. 5
- For erasures, the Erdős–Rényi exact-recovery threshold is 1/(1−ε) in np/log(n); the paper seeks its counterpart when noise causes errors.The cited erasure threshold is stated for the exact-recovery problem with base graph ER(n, p).Source: Y E = BGxV ⊕ZE, (4) · p. 5
- In the low-SNR regime, the Shannon capacity provides the threshold for this inverse problem, although the problem is not a priori related to channel coding.The threshold expression is linked to the Shannon capacity of the BSC(ε).Source: Y E = BGxV ⊕ZE, (4) · pp. 5–6
- The paper gives an information-theoretic necessary condition for every graph, sufficient conditions for Erdős–Rényi and general graphs, and an efficient SDP recovery guarantee.The general-graph information-theoretic condition depends on the Cheeger constant, which is related to spectral gap by Cheeger’s inequality.Source: Y E = BGxV ⊕ZE, (4) · p. 6
- The necessary condition for general graphs and sufficient condition for Erdős–Rényi graphs match; the efficient SDP guarantee reaches exact recovery within a factor of 2 of the information-theoretic bound.The paper establishes information-theoretic and SDP recovery guarantees in Theorems 4.1–4.3 and 5.2–5.3.Source: Y E = BGxV ⊕ZE, (4) · p. 6
- d = Θ(log(n)) when noise stays bounded away from 0 and 1/2; as ε decreases toward 0, the necessary and sufficient bounds separate.The passage attributes the widening gap to D(1/2||ε) diverging; in the noiseless case, exact recovery is possible if and only if the graph is connected.Source: Y E = BGxV ⊕ZE, (4) · p. 6
4. Information Theoretic Bounds
The section establishes necessary and sufficient conditions for exact recovery up to an unavoidable global offset. It treats Erdős–Rényi graphs and arbitrary graphs separately, with the latter’s guarantee expressed through graph connectivity measures.
4.1. A Necessary Condition for Successful Recovery.
- For fixed ε in (0, 1/2), Theorem 4.1 requires average degree d=Ω(log n), strengthening an earlier necessary condition that implies only d=Ω(1).The theorem’s comparison is stated for ε independent of n.Source: §4.1 · p. 7
4.2. Sufficient Conditions for Successful Recovery.
- For Erdős–Rényi graphs with p>2 log n/n, ML exact recovery is sufficient when d>(log n+o(log n))/D(1/2||ε).The section notes that its Erdős–Rényi and Cheeger-based sufficient conditions exhibit the same scaling behavior.Source: §4.2 · pp. 10, 12, 13
- For arbitrary base graphs, a sufficient exact-recovery guarantee depends on the Cheeger constant and minimum degree, with a specialized condition for regular graphs.The guarantee is presented for every graph; the regular-graph case has its own sufficient condition.Source: §4.2 · pp. 12–13
- A necessary condition cannot require the Cheeger constant to stay bounded away from zero: a graph with two components linked by log n edges can remain recoverable as hG tends to zero.The example’s components have sufficient internal Cheeger constants and minimum degrees for the stated guarantee.Source: §4.2 · pp. 13–14
5. Computationally efficient recovery - the SDP
The paper analyzes SDP recovery for Erdős–Rényi and deterministic regular graphs, then compares it with a simpler 2-length path-voting method. The SDP’s recovery guarantees depend on noise and graph structure, while path voting requires substantially higher average degree.
5. Computationally efficient recovery - the SDP
- The tractable SDP relaxes an NP-hard maximum-likelihood formulation, and a PSD dual certificate with a nonzero second-smallest eigenvalue makes the planted rank-one solution unique.The certificate establishes optimality, while the eigenvalue condition supplies uniqueness.Source: §5 · pp. 14–15
5.1. Erd˝os-R´enyi Model.
- A factor of 2 separates the SDP sufficient condition from the maximum-likelihood sufficient condition as ε approaches 1/2.Under its theorem condition, the SDP achieves exact recovery with probability at least 1−n^-δ.Source: §5.1 · p. 16
5.2. Deterministic regular graph.
- For deterministic d-regular graphs, the SDP guarantee depends on the graph’s spectral eigenvalues and the noise level.The analysis relates the Laplacian’s minimum eigenvalue to d(1−λ2), and the theorem states a degree condition involving λ2 and λn.Source: §5.2 · pp. 17–18
5.3. An alternative method based on 2-length path voting.
- 2-length path voting assigns each node by majority vote over length-2 paths from a chosen center, but its sufficient condition forces average degree to be at least of order √n.The paper states that this condition is asymptotically worse than the SDP condition.Source: §5.3 · pp. 18–20
6. Directions and open problems
The authors identify open questions about the gap between information-theoretic and SDP recovery rates and suggest several extensions. Their simulation indicates that the dual certificate may not remain feasible down to the information-theoretic threshold, but infeasibility does not establish SDP failure.
6. Directions and open problems
- The authors propose studying non-binary variables, hyperedges, non-symmetric noise, partial recovery, community-size constraints, and other graph ensembles.They also identify deterministic-graph characteristics that could provide information-theoretic lower bounds as an open direction.Source: §6 · p. 20
- Simulation suggests the dual certificate is not feasible all the way down to the information-theoretic threshold, though its infeasibility does not imply that the SDP fails.The authors note that a sharper, specialized analysis of the random matrix might improve the SDP guarantees.Source: §6 · pp. 20–21, Figure 1 · p. 21
- Whether a polynomial-time algorithm can match maximum-likelihood recovery rates remains open.The authors note that a gap between maximum likelihood and the best polynomial-time algorithm would be interesting.Source: §6 · p. 21