node labels from censored edge measurements: Phase transition and efficient recovery'
---

Introduction
============

A large variety of problems in information theory, machine learning, and image processing are concerned with inverse problems on graphs, i.e., problems where a graphical structure governs the dependencies between the variables that are observed and the variables that are unknown. In simple cases, the dependency model is captured by an undirected graph with the unknown variables attached at the vertices and the observed variables attached at the edges. Let $G=(V,E)$ be a graph with vertex set $V$ and edge set $E$, and let $x^V$ be the vertex- and $y^E$ the edge-variables. In many cases of interest (detailed below), the probabilistic model for the edge-variables [*conditionally*]{} on the vertex-variables has a simple structure: it factorizes as $$\begin{aligned}
P(y^E|x^V)=\prod_{e \in E} Q(y_e|x[e]), \label{gene}\end{aligned}$$ where $y_e$ denotes the variable attached to edge $e$, $x[e]$ denotes the two vertex-variables incident to edge $e$, and $Q$ is a local probability kernel. In this paper, we consider Boolean edge- and vertex-variables, and assume that the kernel $Q$ is symmetric and depends only on the XOR of the vertex-variables.[^1] The edge-variables can then be viewed as a random vector $Y^E$ that satisfies 