An Efficient Algorithm for Exact Recovery of Vertex Variables from Edge Measurements

What do community detection in complex networks, structure from motion in computer vision, and multiple-image registration have in common? They can each be formulated as an inverse problem on a graph. More specifically, we can associate each data unit—such as a node label, photo, or rotated image—to a graph node, and each pairwise measurement to an edge connecting the two nodes. In doing so, the problem becomes one of estimating for each node an unknown variable, such as community membership or rotation, from relative information between pairs of such variables. It’s useful to think of node variables as taking values in a group G and relative measurements as revealing information about group ratios gi (gj) ∈ G. Although much literature proposes algorithmic approaches to this problem, we still don’t understand it from an information-theoretical or computational average-case-complexity viewpoint. In “Decoding Binary Node Labels from Censored Edge Measurements: Phase Transition and Efficient Recovery” (IEEE Trans. Network Science and Eng., vol. 1, no. 1, 2014, pp. 10–22), my colleagues and I moved toward a better understanding by treating a simple, yet crucial, instance of this issue—the setting in which node labels take only two different values (that is, G is the group of two elements).1 In this setting, it’s best to view the problem as community detection on an observation graph G = (V, E). The unknown vertex labels xV represent community memberships and the edge measurements yE are noisy indications of whether node pairs belong to the same cluster. More precisely, given a noise level e < 1/2, for each edge (i, j), yi,j indicates whether i and j belong to the same community or not, making an error with probability ∈ for each edge, and independently to errors in other edges. The goal is then to determine for which graphs G and values of e we can recover xV given yE, and whether this inverse problem can be solved efficiently. Note that xV can only be recovered up to a global flip, corresponding to a cluster relabeling. Indeed, because only relative information is available, the measurements are invariant to relabeling the clusters. This model is closely related to the popular stochastic block model for two communities. In that model, a random graph is drawn on vertices belonging to two or more communities from a distribution with independent edges and probability p if between two vertices of the same community and q if other wise. The objective is to recover the community memberships. The main difference between the models is that in the stochastic block model, every node pair provides information (the non existence of an edge is itself information), whereas in our model node pairs not connected in G don’t provide information. Despite the models’ differences, we’ve successfully adapted the techniques discussed in our paper1 to a stochastic block model setting.2 Our paper’s main contribution was demonstrating that, if we consider the observation graph an Erdos-Renyi graph (a random graph in which each node is connected by an edge, independently and with probability p), with average degree (n–1)p, exact recovery of xV is possible with high probability if and only if