order to maximize the number of agreeing edges (having a $+$ label within a cluster and a $-$ label otherwise). Another variant is proposed in [@nicolo]. The original motivation behind correlation clustering is to let the number of clusters be a design parameter, although the case of constraining the number of clusters has also been considered [@corr_cluster_k]. In our setting, the number of clusters is fixed and assumed to be 2. More importantly, our goal is to understand how sparse the measurement graph can be in order to still be able to recover the original clustering, which is planted. In that regard, we are proposing a planted correlation clustering problem with a fixed number of clusters, censored measurements, and with a probabilistic model.

-   [**Coding:**]{} Equation provides the output on a binary symmetric channel of a code whose generator matrix is the adjacency matrix of the graph $G$. More precisely, since here $G$ is assumed to be a graph and not a hyper-graph, this is a very simple code, namely a 2-right-degree LDGM code. While this is not a particularly interesting code by itself (e.g., at any fixed rate, it has a constant fraction of isolated vertices), it is a 