An extension of the angular synchronization problem to the heterogeneous setting

Figure 1.  An instance of the bi-synchronization problem. The measurement graph (bottom row) available to the user is a union of two edge disjoint graphs (top row) on the same vertex set. The top graphs each capture angle offsets for two different sets of angles: the top left graph encodes noise pairwise offsets between the angles $ \alpha_1, \ldots, \alpha_n $, while the top right graph contains similar information from the angles $ \beta_1, \ldots, \beta_n $

Figure 2.  An instance of the bi-synchronization problem in the context of ranking from pairwise comparisons with multiple voting systems. The red and blue judges each give a rating for pair of items $ {\left\{{{i, j}}\right\}} $. $ (\alpha_1, \ldots, \alpha_n ) $ denote the intrinsic strength/skill of the players as construed by the red judge, while $ ( \beta_1, \ldots, \beta_n) $ capture the strength/skill of the same set of $ n $ players as perceived by the blue judge

Figure 3.  An instance of the cluster-synchronization problem, closely related to the bi-synchronization problem we study in this paper. The collection of angles is partitioned into two clusters $ \mathcal{C}_1 = (\alpha_1, \alpha_2, \ldots, \alpha_{n_1}) $, $ \mathcal{C}_2 = (\beta_{n_1+1}, \beta_{n+2}, \ldots, \beta_{n_2}) $, of potentially unequal sizes $ n_1, n_2 $ (as is the case in this example, with $ n_1 = 5, n_2 = 4 $), such that when a pair of angles is chosen from the same cluster, we obtain a (potentially noisy) offset $ \alpha_i - \alpha_j $ or $ \beta_i - \beta_j $. However, when a pair $ (\alpha_i, \beta_j) $ of angles from two different clusters is compared, the measured offset $ \Theta_{ij} $ is completely random and contains no meaningful information

Figure 4.  Experimental Setup Ⅰ: Correlation of recovered angles with the ground truth for $ n = 500 $ (top), respectively $ n = 1000 $ (bottom), with $ k = 2 $ groups of angles, and various noise levels $ \eta \in \{ 0.50, 0.70, 0.85\} $ as a function of $ \lambda $ (sparsity of the measurement graph). Results are averaged over $ 20 \times 20 = 400 $ runs (i.e, over 20 random instances of groups of angles, and for each such a group of angles, we consider 20 random instances of the sampling graph according to $ p_1 $ and $ p_2 $)

Figure 5.  Experimental Setup Ⅰ: Correlation of recovered angles with the ground truth for $ n = 1000 $, with $ k = 3 $ (top) and $ k = 4 $ (bottom) collections of angles, and various noise levels $ \eta $, as a function of $ \lambda $ (sparsity of the measurement graph). Results are averaged over $ 20 \times 20 = 625 $ runs

Figure 6.  Experimental Setup Ⅱ: Correlation of recovered angles with the ground truth, where we keep constant the gap $ \gamma = 0.05 $ between consecutive sampling probabilities $ p_{l+1} - p_l = \gamma, l = 1, \ldots, k-1 $, of the subgraphs $ G_{l} $. We also fix the number of angles $ n = 500 $, and vary $ k \in \{2, 3, 4\} $ (indexing the rows), and the overall measurement graph sparsity $ \lambda \in \{ 0.2, 0.4, 0.8\} $ (indexing the columns). Each plot shows the correlation with the ground truth, as we vary the noise level $ \eta $. Results are averaged over $ 20 \times 20 = 400 $ runs

Figure 7.  Experimental Setup Ⅱ: Correlation of recovered angles with the ground truth in the second experimental setup where we compared the performance of the two spectral relaxations and the SDP relaxation. EIG-H denotes the relaxation that uses the top eigenvector of matrix $ H $ from (4.5); EIG-R employs the normalized matrix eq. (6.2), and SDP-BM denotes the SDP relaxation eq. (2.4) solved via the Burer-Monteiro approach. We keep constant the gap $ \gamma = 0.05 $ between consecutive sampling probabilities $ p_{l+1} - p_l = \gamma, l = 1, \ldots, k-1 $, of the subgraphs $ G_{l} $. The number of angles is kept fixed at $ n = 500 $, and we vary $ k \in \{2, 3, 4\} $ (indexing the rows), and the overall measurement graph sparsity $ \lambda \in \{ 0.2, 0.4, 0.8\} $ (indexing the columns). Each plot shows the correlation with ground truth, as we vary the noise level $ \eta $. Results are averaged over $ 20 \times 20 = 400 $ runs

Figure 8.  Experimental Setup Ⅱ: Performance comparison in the setting of a Barabási–Albert model, for $ n = 500 $, edge density $ \lambda = 0.20 $, gap $ \gamma = 0.05 $, $ k \in \{2, 3, 4\} $, as a function of the noise levels $ \eta $. Results are averaged over $ 20 \times 20 $ runs

Figure 9.  Top: ground truth good graph $ G_1, G_2 $ and the bad graph $ W $, all edge disjoint, of size $ n = 100 $, with corresponding probabilities $ p_1 = 0.45 $, $ p_2 = 0.35 $ and $ \eta = 0.20 $. Middle: the user observes an angle offset matrix $ \Theta $ whose underlying entangled measurement graph $ G = G_1 \cup G_2 \cup W $ is depicted. Bottom: final estimates of $ \widehat{G}_1, \widehat{G}_2, \widehat{W} $ from our recovery pipeline, with a visualization of the classification errors; the titles contain the two types of errors being made: the number of extra edges (+) and the number of missing edges (-) for each individual estimated graph

Figure 10.  Histogram of synchronization residuals given by the non-zero entries of the matrix $ \tilde{\Psi}_{l}, \; l = \{1, 2, 3\} $, as defined in (6.5), where the $ k = 3 $ underlying measurement graphs have edges densities $ (p_1, p_2, p_3) = (0.18, 0.15, 0.12) $, noise level $ \eta = 0.55 $, and sparsity $ \lambda = 0.3 $. The top (resp. bottom) row plots the non-zero residual entries after one iteration (resp., 20 iterations of Algorithm 2), with columns indexing the three groups of underlying angles. Note that for each column (i.e., group of angles), the residuals become significantly smaller after 20 iterations, for all three groups of angles, showcasing the effectiveness of the iterative procedure

Figure 11.  Correlation with ground truth for the first 20 iterations of Algorithm 2, for three problem instances with $ k = 2, 3, 4 $ and $ n = 500 $, at various noise levels $ \eta $ and sparsity levels $ \lambda $. In all three problem instances, and across all subsets of angles within each instance, the iterative procedure leads to an increase in the correlation with ground truth, especially for the groups of angles with the sparsest measurement graph

Figure 12.  Optimal alignment of two patch embeddings, that overlap in four (green) nodes [19]. This pairwise alignment provides a measurement for the ratio of the two corresponding group elements in Euc(2)

Figure 13.  The ASAP recovery process in $ d = 2 $ dimensions, considered in [19], for a patch in the US graph

Figure 14.  Alignment of frescos, as explored in [39]. The alignment of the pieces can be construed as an instance of the synchronization problem over the Euclidean group of rigid motions

Figure 15.  Clean data, two non-congruent embeddings of the US graph: (a) Original US map (b) Non-rigid transformation of the original data (shear transformation, followed by a rotation and scaling of the Midwest and East Coast). (c) Procrustes alignment of the point clouds in (a) and (b) showing the displacements between the two embeddings, making the point that the two embeddings that we aim to recover are indeed non-congruent

Figure 16.  (a) Adjacency matrix of the measurement graph $ G $, highlighting the decomposition $ G = G_1 $ (red) $ + G_2 $ (yellow). Plots (b) and (c) show the histogram of degrees in $ G_1 $ and $ G_2 $. The embeddings of $ X $ and $ Y $ are colored by their corresponding degree, i.e., each node $ i $ in the embedding (that lies at the center of patch $ P_i $) is colored by the number of other patches it overlaps with

Figure 17.  Recovery of the two estimated embeddings $ \hat{X} $ and $ \hat{Y} $ shown in the first and third columns, where the coloring is given by the longitude. The second column shows the Procrustes alignment between the recovered embedding $ \hat{X} $ (red) and the ground truth $ X $ (blue), together with the displacement error bars. The forth column shows a similar visualization for $ \hat{Y} $ and the ground truth $ Y $. We vary the noise level $ \sigma $ used in the perturbations of the local patch embeddings in both ensembles, across the following set of values $ \sigma \in \{ 0, 0.2, 0.4, 0.6, 0.8 \} $

Figure 18.  Left: classical angular synchronization; Right: an instance of the $ k $-list synchronization problem, where the goal is to recover a single group of $ n $ angles, from a small subset of pairwise noisy offsets $ \theta_i - \theta_j $; however, there are now multiple candidates for a given pairwise offset, only one of which is correct (or approximately correct)