$\{x_j\}_{j \in [n]}$ in $O(r)$ given the relative measurements $\{Z_{ij} x_i^{-1} x_j\}_{i,j \in [n]}$, where $Z_{ij}$ is randomly drawn in $O(r)$ if the vertices $i$ and $j$ are adjacent and all-zero otherwise.[^3] When $r=1$, we have $O(1)=\{-1,+1\}$ and the synchronization problem is equivalent to .

While the above mentioned problems are all concerned with related inverse problems on graphs, there are various recovery goals that can be considered. This paper focuses on [*exact recovery*]{}, which requires all vertex-variables to be recovered simultaneously with high probability as the number of vertices diverges. The probability measure may depend on the graph ensemble or simply on the kernel $Q$ if the graph is deterministic. Note, as mentioned previously, that exact recovery of all variables in the model is not quite possible: the vertex-variables $x^V$ and $1^V \oplus x^V$ produce the same output $Y^E$. Exact recovery is meant “up to a global flipping of the variables”. For [*partial recovery,*]{} only a strictly dominant constant fraction of the vertex-variables are to be recovered correctly with high probability as the number of vertices diverges. Put differently, the true assignment need only be positively correlated with the reconstruction.[^4] The recovery requirements vary with the applications, e.g., exact 