Robust Angular Synchronization via Directed Graph Neural Networks
Authors: Yixuan He
Gesine Reinert
David Wipf
Mihai Cucuringu
Venue: ICLR 2024 poster (2024)
Keywords: group synchronization
angular synchronization
neural networks
directed graphs
deep learning
cycle consistency
Primary area: learning on graphs and other geometries & topologies
TL;DR: We propose a neural network framework with novel loss functions to tackle the angular synchronization problem and its extension to k-synchronization.

Abstract: The angular synchronization problem aims to accurately estimate (up to a constant additive phase) a set of unknown angles $\theta_1, \dots, \theta_n\in[0, 2\pi)$ from $m$ noisy measurements of their offsets $\theta_i-\theta_j$ mod $2\pi.$ Applications include, for example, sensor network localization, phase retrieval, and distributed clock synchronization. 
An extension of the problem to the heterogeneous setting (dubbed $k$-synchronization) is to estimate $k$ groups of angles simultaneously, given noisy observations (with unknown group assignment) from each group. Existing methods for angular synchronization usually perform poorly in high-noise regimes, which are common in applications. In this paper, we leverage neural networks for the angular synchronization problem, and its heterogeneous extension, by proposing GNNSync, a theoretically-grounded end-to-end trainable framework using directed graph neural networks. In addition, new loss functions are devised to encode synchronization objectives. Experimental results on extensive data sets demonstrate that GNNSync attains competitive, and often superior, performance against a comprehensive set of baselines for the angular synchronization problem and its extension, validating the robustness of GNNSync even at high noise levels.

Published as a conference paper at ICLR 2024
ROBUST ANGULAR SYNCHRONIZATION VIA DIRECTED GRAPH NEURAL NETWORKS
Yixuan He & Gesine Reinert
David Wipf
Department of Statistics University of Oxford Oxford, United Kingdom
Amazon
Shanghai, China
daviwiipfaamzzon. com
(yixuan.her zeinert]astats ox. ac.
Mihai Cucuringu
Department of Statistics
University of Oxford
Oxford, United Kingdom mihai. cucuringuéstats ww.ac. uk
ABSTRACT
The angular synchronization problem aims accurately estimate (up to a constant additive phase) set of unknown angles .1.....,, 0x E [0, 2T) from m noisy mea- surements of their offsets 8--6; 0, mod 2n. Applications include, for example, sensor network localization, phase retrieval, and distributed clock synchronization. An extension of the problem to the heterogeneous setting (dubbed k-synchronization) is estimate & groups of angles simultaneously, given noisy observations (with unknown group assignment) from each group. Existing methods for angular syn- chronization usually perform poorly in high-noise regimes, which common in applications. In this paper, we leverage neural networks for the angular synchro- nization problem, and its heterogeneous extension, by proposing GNNSYNC, a aeoortiically-gounddee end-to-end trainable framework using directed graph neural networks. In addition, objectives. Experimental results on extensive data sets demonstrate that GNNSyne attains competitive, and often superior, performance against comprehensive set of baselines for the angular synchronization problem and its extension, validating the robustness of GNNSyne even high noise levels.
loss functions devised encode synchronization
INTRODUCTION
The group synchronization problem has received considerable attention in recent years, as a key building block of many computational problems. Group synchronization aims to estimate collection of group elements, given small subset of potentially noisy measurements of their pairwise ratios Trj = 9: 9y Some applications are over the group SO(3) of 3D rotations: rotation- averrgging in 3D computer vision (Arrigoni & Fusiello 2020 Janco & Bendory 2022) and the molecule problem
in structural biology (Cucuringu et al. 2012b) over the group E4 of the integers {0. 1,2, 3) with addition mod as the group operation: solving jigsaw puzzles (Huroyan al. 2020); over the group Z., resp., SO(2): recovering global ranking from pairwise comparisons (He et al. 2022a Cucuringu 2016), and, over the Euclidean group of rigid motions Euc(2) = Ee x SO(2) x R- sensor network localization (Cucuringu et al. 2012a).
An important special case is angular synchronization, also referred to as phase synchronization, which can be viewed as group synchronization over SO(2). The angular synchronization problem aims at obtaining accurate estimation (up to a constant additive phase) for of unknown angles 0,,... On E [0. 2T) from m noisy measurements of their pairwise offsets 0, 1--6, 0, mod 2x. This problem has a wide range
(b) High noise. Figure I: Sensor network localization map.
Low noise.
*his work partially done during internship Amazon.

---

Published as a conference paper at ICLR 2024
of applications, such as distributed clock synchronization over wireless networks GGiridhar & Kumar 2006). image reconstruction from pairwise intensity differences Yu 2009 2011), phase
retrieval (Forstner et al. 2020 Iwen et al. 2020), and sensor network localization (SNL) (Cucuringu et al. 2012a). In engineering, the SNL, problem seeks to reconstruct the 2D coordinates of a cloud of points from sparse set of pairwise noisy Euclidean distances; in typical hivide-and-conquer approaches that aid with scalability, one first computes a local embedding of nearby points (denoted as patches) and is left with the task of stitching the patches together in a globally consistent embedding (Cucuringu et al., 201 2a Fig. [ is an example of SNL on the U.S. map, where our method recovers city locations (in blue) and aims to match ground-trute -tuth locations (in red). Most works in the SNL literature that focus on the methodology development consider only purely synthetic data sets in their experiments; here we consider a real-world data set (actual 2D layout with different levels of densities of cities across the U.S. map), and add synthetic noise to perturb the local patch embeddings for testing the robustness to noise of the angular synchronization component.
An extension of angular synchronization to the heterogencous setting is k-synchronization, introduced in [Cucuringu& & Tyagi (2022), and motivated by real-world graph realization problems (GRP) and ranking. GRP aims to recover coordinates of a cloud of points in R from sparse subset (edges of a graph) graph) of noisy pairwise Euclidean distances (the case d = 2 is the above SNL problem). The motivation for k-synchronization arises in structural biology, where the distance measurements between pairs of atoms may correspond to l different configurations of the molecule, in the case of molecules with multiple conformations. In ranking applications, the k = 2 sets of disjoint pairwise measurements may correspond to two different judges, whose latent rankings we aim to recover.
A key limitation of existing methods for angular synchronization is their poor performance in the presence of considerable noise. High noise levels are not unusual; measurements in SO(3) can have large outliers in certain biological settings (cryo-EM and NMR spectroscopy), see for example Cucuringu et al. (0122)) Therefore, we need new methods to push the boundary of signal recovery when there is a high level of noise. While neural networks (NNs), in principle, could be trained to ad- dress high noise regimes, the angular synchronization problem is not directly amenable to a standard NN architecture due to the directed graph (digraph) structure of the underlying data measurement process and the underlying group structure; hence the need for customized graph neural network (GNN) architecture and loss function for this task. Here we propose a GNN method called GNNSync for angular synchronization, with a novel cycle loss function, which downweights noisy observations, and explicitly enforces cycle consistency as a quality measure. GNNSyne's 's novelty does not lie in simply applying data-driven NN to this task, but rather in proposing a framework for handling the pairwise comparisons encoded in a digraph, accounting for the underlying SO(2) group structure, and designing a loss function for increased robustness to noise and outliers, with theoretical support.
Our main contributions are summarized as follows.
We demonstrate how the angular synchronization problem can be recast as a theoretically-gronnde directed graph learning task by first incorporating the inductive biases of classical estimators within the design of a more robust GNN architecture, called GNNSyne, and then pairing with a novel training loss that exploits cycle consistency to help infer the unknown angles.
We perform extensive experiments comparing GNNSyne with existing mate-of-thheart algorithms from the angular synchronization and k-synchronization literature, across a variety of synthetic outlier models at various density and noise levels, and on a real-world application. GNNSyne attains leading performance, especially in high noise regimes, validating its robustness to noise.
RELATED WORK
2.1 ANGULAR SYNCHRONIZATION
The seminal work of Singer (01T) introduced spectral and semidefinite programming (SDP) relax- ations for angular synchronization. For the spectral relaxation, the estimated angles are given by the cigenvector corresponding to the largest cigenvalue of a Hermitian matrix H. whose entries are given by H. = exp(IA,,,) 1 (A,,; *t 0), where is the imaginary unit, and A., is the observed potentially noisy offset 0; f, mod 2x. [Singer (201T) also provided an SDP relaxation involving the same matrix H. and empirically demonstrated that the spectral and SDP relaxations yield similar experimental results. A row normalization was introduced to H prior to the eigenvector computation by Cucuringu et al. (2012a), which showed improved results. Cucuringu et al. (2012b) generalized this approach to the 3D setting Euc(3) = Zg SO(3) x R and incorporated into the optimization pipeline the ability to operate in a remi-supervisee
setting, where certain group elements are known a- a-priori. |Cucuringu & Tyagi (2022) extended the angular synchronization problem to heterogeneous setting, to the so-called
2

---

Published as a conference paper at ICLR 2024
k-symchronization problem, whose goal is to estimate l sets of angles simultaneously, given only the graph union of noisy pairwise offsets, which we also explore in our experiments. The key idea in their work is to estimate the k sets of angles from the top & eigenvectors of the angular embedding matrix H.
Boumal 2016) modeled the angular (phase) synchronization problem as a least-squares non-convex optimization problem, and proposed modified version of the power method called the Generalized Power Method (GPM), which is straightforward to implement and free of parameter tuning. GPM often attains leading performance among baselines in our experiments, and the iterative steps in the GPM method motivated the design of the projected gradient steps in our GNNSync architecture. How- ever, GPM is not directly applicable to k-synchronization with k > while GNNSyne is. For A: 1, GNNSyne tends to perform significantly better than GPM at high noise levels. Bandeira et al. (2017) studied the tightness of the maximum likelihood semidefinite relaxation for angular synchronization, where the maximum likelihood estimate is the solution to nonbipartite Grothendieck problem over the complex numbers. A truncated least-squares approach was proposed by Huang et al. (2017) that minimizes the discrepancy between the estimated angle differences and the observed differences under some constraints. Gao & Zhao (2019) tackled the angular synchronization problem with a multi-frrquencc approach. Liu et al. (2023) unified various group synchronization problems over subgroups of the orthogonal group. Filbir et al. (202I) provided recovery guarantees for eigenvector relaxation and semidefinite convex relaxation methods for weighted angular synchronization. Lerman & Shi (2022) applied a message-pan paasaagggg procedure based on eycle consistency information, to esti- mate the corruption levels of group ratios and consequently solve the synchronization problem, but the method is focused on the restrictive setting of adversarial or uniform corruption and sufficiently small noise. In addition, Lerman & Shi (022) requires post-processing based on the estimated corruption levels to obtain the group elements, while GNNSync is trained end-to-end. Maunu & Lerman (2023) utilized energy minimization ideas, with a variant converging linearly to the ground truth rotations.
2.2 DIRECTED GRAPH NEURAL NETWORKS
Digraph node embeddings can be effectively learned via directed graph neural networks (He et al. 2022c For learning such an embedding, Tong et al. (2020) constructed a GNN using higher- order proximity. Zhang et al. (202T) built a complex Hermitian Laplacian matrix and proposed a spectral digraph GNN. He et al. (2022b) introduced imbalance objectives for digraph clustering. Our GNNSync framework can readily incorporate any existing digraph neural network.
2.3 RELATIONSIIPP WITH OTHER GROUP SYNCIRONIZATION METHODS
Angular synchronization outputs can be used to obtain global rankings by using a -iedimensional ordering. To this end, recovering rankings of n objects from pairwise comparisons can be viewed as group synchronization over Zn,- To recover global rankings from pairwise comparisons, GN-
NRank (He et al.) 2022a) adopted an unfolding idea add an inductive bias from FFoeel et al. (2014) to the NN architecture. Inspired by He et al. (002a)), we adapt their framework to borrow strength from solving related problem. We adapt their "innerproduct" variant to k-synchronization, remove the 1D ordering at the end of the GNNRank framework, and rescale the estimated quantities to the range [0, 2x). We also borrow strength from the projected gradient steps in GPM (Boumall 2016) and add projected gradient steps to our GNNSync architecture. Another key novelty is that we devise novel objectives, which reflect the angular structure of the data, to serve as our training loss functions. The architectures are also very different: While in GNNRank the proximal gradient steps play vital role from an unrolling perspective, and the whole architecture could be viewed as an unrolling of the RerialRank algorithm, here, although we borrow strength from the GPM method, the whole ar- chitecture is different from merely unrolling GPM. Furthermore, the baselines serve as initial guesses for the "proximal baseline" variant in GNNRank, but serve as input node features in our approach.
Other methods have been introduced for group synchronization. but mostly in the context of SO(3). Shi & Lerman (2020) proposed an efficient algorithm for synchronization over SO(3) under high levels of corruption and noise. (hi et al.) (2022) provided novel quadratic programming formulation for estimating the corruption levels. but again its focus is on SO(3). Unrolled algorithms (which are NNs) were introduced for SO(3) in Janco & Bendory (202)). While an adaptation to SO(2) may be possible in principle, as its objective functions are based on the level of agreement between the estimated angles and ground-truth, its experiments require ground-truth -ruth during training, usually not available in practice. In contrast, our GNNSync framework can be trained without any known angles.
3 PROBLEM DEFINITION
The angular synchronization problem aims at obtaining an accurate estimation (up to a constant additive phase) for set of n unknown angles 0, .1.....3 O2 E [0,2
2n)) from m noisy measurements of
3

---

Published as a conference paper at ICLR 2024
their offsets 0₂ 03 mod 2Tt, for i,j E (1..... n). We encode the noisy measurements in a digraph g = (V.E), E), where each of the n elements of the node set V has as attribute an angle 02 E [0, 2 The edge set & represents pairwise measurements of the angular offsets (0; 8g) mod 2T. The weighted directed graph has a corresponding adjacency matrix A with Aij = (0; 02) mod 2Tr >= 0. Estimating the unknown angles from noisy offsets amounts assigning an estimate r; [0,2 to each node i E V. For computational complexity considerations, we randomly keep one of A and A as observed quantity and set the other of these zero. Thus, at most one of Ai, and A can be nonzero by construction; the other original entry can be inferred from Ai, + J = 0 mod 2n.
An extension of the above problem the heterogeneous setting is the k- k-syuchronization problem. which is defined as follows. We are given only the graph union of k digraphs G1.... Gk, with the same node set and disjoint edge sets, which encode noisy measurements of l sets (0.1- 0321) mod 2n, of angle differences modulo 2T. Its adjacency matrix is denoted by A. The problem is to estimate these it sets of unknown angles 0²2 E [0, 2Tr,, 4I E (1.... ........ k), i {I...., n.,, ",,,, simuitaneously. Note that we are given only 9 G Giu...G and the value of k. and each edge in G belongs to exactly one of .I....: Gg. To unify notations, we view the normal angular syn- chronization problem special case of the more general k-synchronization problem where k = 1.
for l E {1..... k j.j (1....n)) n).
LOSS AND EVALUATION
4.1 LOss AND EVALUATION FOR ANGULAR SAAAAASSYYHIIIAN SYNCHRONIZATION For a vector r [ri...., r with estimated angles as entries, we define T [(11]
Ir") mod 2x] E Raxx Then Tı₃ (r: - rj) mod 2T estimates Aij- We only compare T with A at locations where A has nonzero entries. We introduce the residual matrix M with entries
M min ((T Ai.) mod 2n,, (Aij) T mod 27)
if A. * O, and M = Of As, = 0. Then our upset loss is defined as
Lupaet || p /t,
where the subscript F means Frobenius norm, and is the number of nonzero elements in A. Despite the non-iifferentiabliity of the loss function, using the concept of a limiting subdifferential from Li al. (2020) we can give the following theoretical guarantee on the minimization of eq. ① its proof is in Appendix (App.) A.I where also the case of general k is discussed.
Proposition Every local minimum of eq. ① is a directional stationary point of eq. ①
For evaluation, we employ a Mean Square Error (MSE) function with angle corrections, considered in Singer & Shkolnisky (2011). As the offset measurements are unchanged if we shift all angles by constant, denoting the ground-truth angle vęctor as R. this evaluation function can be written as
(M,E(r,R) R) = min (0.20,
[min(6, mod 2m,, (-6,) mod 2T)]²
(2)
where 8, r 00 0g Vi 1....,n. n. Additional implementation details are provided in App. C.4
4.2 CYCLE CONSISTENCY RELATION
For noiseless observations, every cycle in the angular synchronization problem (k 1) or every cycle whose edges correspond to the same offset graph Gi (k: > 1) satisfy the cycle consistency relation that the angle sum mod 2 is O. For 3-cycles (i.j. q). such that Ai, Ajaa Ag.i 0, this leads to
(Ai. + Aj.- + Ag.)) mod 2 (0: f, + f, 6g + 0g 0.) mod 2x = 0,
as (a + mod m) = {(a mod m) + (b mod m) mod m]. Hence we obtain the 3-cycle condition
(Aij + Ajg + Ay.;) mod 2T = 0, Vi..j. g) such that Aij Ajg Ag. >00
(3)
With T ((i.j.g) : Aij Ajq Aq.á m E(.sg)er[(A., + Aj.g + Aq.) mod 2m We devise a loss function minimize the eycle inconsistency level with reweighted edges.
0}, define the cycle inconsistency level
4.3 LOss AND EVALUATION FOR GENERAL K- E-SYNCHRONIZATIOO
The upset loss for general l is defined similarly as in Sec. 4.1 Recall that the observed graph G has adjacency matrix A. Given groups of estimated angles (ri, Tnach = 1,... ki we define the matrix T with entries T (ri,1 TJ,)) mod 2T,, for i, j E {1...., n), (1...., k). We define
O by M min((T)) [ Ai.) mod 2n, (Ar, T()) mod 27) if Aij A O, and MD) 0 if
A O. Define M by M.j minte(.....))) ! The upset loss is in eq. 1 Lupert
|M]|
4

---

Published as a conference paper at ICLR 2024
In addition to Lupset. introduce another option loss function based the cycle consistency
relation from Sec. 4.2 which adds a regularization that helps in guiding the learning process for certain typically noisy,
challenging scenarios (c.g., with sparser & or larger k). Since measurements first estimate the corruption level by entries in M, and use them to construct confidence matrix C for edges in G. We define the unnormalized confidence matrix C by C.2 = 1+M., 1 (A * 0),
Ex.. then normalize the entries by C., = CiJ E... Eu.o Aur The normalization is chosen such that
Eny C - E.,- Au,e- Keeping the sum of edge weights constant is carried out in order to avoid reducing the cycle inconsistency level by only rescaling edge weights but not their relative magnitudes. Based on the confidence matrix C, we reweigh edges in G to obtain an updated input graph, whose adjacency matrix is the Hadamard product A O C. This graph attaches larger weights to edges A. for which T( is good estimate when the edge (i, belongs to graph Gt. As the graph assignment of an edge (i.j) not known during training, we estimate by
g(i.j) arg min le(1.....k)
M (!) and set g(j. i) = g(i.j),
thus obtaining our estimated graphs "1,..., Gr. minimize 3-cycle inconsistency of the updated input graph given our graph assignment estimates, we introduce a loss function denoted as the cycle inconsistency loss Leycks for simplicity, we only focus on 3-cycles (triangles). We interpret the matrix À (A C Č (A + C)T) mod 2nr as the adjacency matrix of another weighted directed graph G. The entry Å.,, of the new adjacency matrix approximates angular differences of reweighted graph, with noisy observations downweighted. Note that we only reweigh the adjacency matrix in the cycle loss definition, but do not update the input graph. The underlying idea is that this updated denoised graph may display higher cycle consistency than the original graph. From our graph assignment estimates, we obtain estimated adjacency matrices A (1) for I E (1,..., k), where A = ( j) = A) Let (
which are also edge disjoint. Next, aiming to
{(i,j, 4) (L) A A > 0}
denote the set of all triangles in G. and set $1.. A + A (1) j.g
A (1)
g. for (i,j.g) T(), We define
c()
min(s mod 2T,, ( (.j.)
(I) mod 2x)
(5)
T(
(K..))ETO)
and set Laycle 1/2 experiment section, also report the performance of variant based Lupset + Leyele-
* - eyyee The default training loss for k >/ 2 is Leyele Lupset alone; in the
For evaluation, we compute DMSE with eq. (2). for each of the sets of angles, and consider the average. As the ordering of the k sets be arbitrary, we consider all permutations of (1...., . R), denoted by perm(k). Denoting the ground-truth angle matrix as R. whose (i, 7) entry is the ground-truth angle 0g,,, and the 1-th entry of the permutation pe by pe()), the final MSE value is
min DMSE (r, R) peeperm(k)
Σ (risE((..pe0)) R.,))
(6)
Note that the MSE loss is not used during training as we do not have any ground-truth supervision; the MSE formulation in eq. (2) is only used for evaluation. The lack of ground truth information in the presence of noise is precisely what renders this problem very difficult. If any partial ground-trute information is available, then this can be incorporated into the loss function.
GNNSYNG ARCHITECTURE
Figure 2: GNNSync overview: starting from an adjacency matrix A encoding (noisy) pairwise offsets and an input feature matrix X, GNNSync first applies a directed GNN to learn node embeddings Z. It then calculates the inner product with a learnable vector (or ie learnable vectors for ls 1) to produce the initial estimated angles Til E [0, 2T) for / E {1,..., kj. after rescaling. It then applies several projected gradient steps to the initial angle estimates to obtain the final angle estimates, ri.ı [0, 2Tr). Let the ground-truth angle matrix be R T The loss function is applied to the output angle matrix r, given A, while the final evaluation is based on R and r. Orange frames indicate trainable vectors/matrices, green squares fixed inputs, the red square the final estimated angles (outputs), and the yellow circles the loss function and evaluation.
A Y pixda
Directed Graph Neural Network
Z E DN aob
Learnable Vector(s)
Initial (()) grink
Projected Gradlent Stops
R gank
E gook
Function
Evaluation
5

---

Published as a conference paper at ICLR 2024
5.1 OBTAINING DIRECTED GRAPH EMBEDDINGS
For obtaining digraph embeddings, any digraph GNN that outputs node embeddings can be applied,
e.g. DIMPA by He et al. (2022b), the inception block model by Tong et al. (2020), and MagNet by Zhang et al. (2021). Here we employ DIMPA; details are in A.2 Denoting the final node embedding matrix by 2a the embedding vector Z; for a node is Z; = (c.)) E RRd, the 7 row of Z.
5.2 OBTAINING INITIAL ESTIMATED ANGLES
To obtain the initial estimated angles for the angular synchronization problem, we introduce a trainable vector a with dimension equal to the embedding dimension, then calculate the unnormalized estimated angles by the inner product of z; with a. plus trainable bias b, followed by a sigmoid layer to force positive values, and finally rescale the angles to [0, 2T); in short: r. 2 sigmoid + b).
For general d-synchronization, we apply independent a. b values to obtain & different groups of initial angle estimates based on different columns of the node embedding matrix Z. In general, denote Zizer the (u + 1)-vector whose entries are from the i-th row and the u-th to u-th columns of the matrix Z. With trainable vector a for each E {1...., k} with dimension equal to d, we obtain the unnormalized estimated angles by the inner product of Z (1d(1-))d+1 1:dd with a plus trainable bias b,, followed by a sigmoid layer to force positive angle values, then rescale the angles to
[0, 2T); in short: i.
(0) 2 sigmoid Zi (1-1)d-1::d a a + bi).
5.3 PROJECTED GRADIENT STEPS FOR FINAL ANGLE ESTIMATES
Our final angle estimates are obtained after applying sev- eral (default: r 5) projected gradient steps to the initial angle estimates. In brief, projected gradient de- scent for constrained optimization problems first takes gradient step while ignoring the constraints, and then projects the result back onto the feasible set to incorpo- rate the constraints. Here the projected gradient steps are inspired by [Boumal (2016). We construct H by 0), and update the estimated
Algorithm Projected Gradient Steps
Initial angle estimates (0 Ro*k Hermitian matrix H Rax", number of steps 1' (default: 5).
Input:
Parameter: (Initial) parameter set fay >> 035ー1 that could either fixed trainable (default: fixed value 1).
Output: Updated angle estimates e m
H.j = exp(1A (A.,) I(A,) angles using Algo. [ where r., denotes the I-th column of r. In Algo. the the gradient step is line 6, while the projection step on line 7 projects the updated matrix to ele- mentwise angles. Fig. 2 shows the GNNSyne framework.
1: I 1;
2: for l
& k do 3: 7 1:y - rr..
(0).
4:
for 7 & do
5:
y -xxp(ry):
6:
y - o. + Hy;
If graph assignments can be estimated effectively right after the GNN, one can replace H with H()) for each = ,,. A separately, where H!)) exp(1A.)) 1 * 0), and A (g(i,) A), j is the estimated adja- cency matrix for graph Gj using network assignments from g(i,j) from eq. (4) applied the initial angle estimates r()) Yet, separate H may make the architecture sen- sitive to the accuracy of graph assignments after the GNN, and hence for robustness we simply choose a single H. We also find in Sec. 6.44 that the use of H instead of separate H('s is essential for satisfactory performance. Besides, is possible to make Algo. parameter-free by further fixing the {(.,) values (default: a, = 1, V7); we find that using fixed [ does not strongly affect performance in our experiments. GNNSyne executes the projected gradient descent steps at every training iteration as part of a unified end-to-end training process, but one could also use Algo. to post-process predicted angles without putting the steps in the end-to-end framework. We find that putting Algo. T in our end-to-end training framework is usually helpful.
7:
y - angle(ý) to obtain element-
wise angles in radians from com- plex numbers;
8:
-- 1. end for
9:
10:
y.
11:
1 1-1+1.
12:
end for
13:
return r.
5.4 ROBUSTNESS OF GNNSYNC
Measurement noise that perturbs the edge offsets can significantly impact the performance of group synchronization algorithms. To this end, we demonstrate the robustness of GNNSyne to such noise perturbations, with the following theoretical guarantee, proved and further discussed in App. A.2
Proposition 2. For adjacency matrices A, A, assume their nownoormalized variants A,, A. A A
satisfy A. A. < 6, and A
A, < Et, where subscripts 8, t denote source and target,

---

Published as a conference paper at ICLR 2024
resp. Assume further their input feature matrices X, X satisfy gles r(0), f( from trained GNNSyne using DIMPA satisfy ||r!0) -
x-x <eg. Then their initial an-
< BBes + Bie, + Bee for values Ba, Br, By that can be bounded by imposing constraints on model parameters and input.
6 EXPERIMENTS
Implementation details are in App. C and extended results in App. D
6.1 DATA SETS AND PROTOCOL
Previous works in angular synchronization typically only consider synthetic data sets in their ex- periments, and those applying synchronization to real-world data do not typically publish the data sets. To bridge the gap between synthetic experiments and the real world, we construct synthetic data sets with both correlated and uncorrelated ground tround-truth rotation angles, using various measurement graphs and noise levels. In addition, we conduct sensor network localization on two data sets.
For synthetic data, we perform experiments on graphs with n = 360 nodes for different measurement graphs, with edge density parameter p E (0.05, 0.1, 0.15), noise level 17 E {0, 0.1, 0.1...., 0.9} for l 1, and E {0, 0.1, ..... 0.7) for k e (,,3, 4}. The graph generation procedure is as follows (with further details in App. B.I:: : 1) Generate k group(s) of ground-truth angles. One option to generate each angle from the same Gamma distribution with shape 0.5 and scale 2x. We denote this option with subscript "1". As angles could be highly correlated in practical scenarios, we introduce a more realistic but challenging option "2", with multivariate normal ground-truth angles. The mean of the ground-trune -otun angles is т,, with covariance matrix for each E {1.....k; }} defined by ww where entries in are generated independently from standard normal distribution. We explore options in the SI. We then apply mod 2n to all angles. 2) Generate a noisy background adjacency matrix noise E I = 3) Construct a complete adjacency matrix where 1) portion of the entries are noisy and the rest represent true angular differences. 4) Generate a measurement graph and sparsify the complete adjacency matrix by only keeping the edges in the measurement graph.
more
We construct 3 types of measurement graphs from NetworkX (Hagberg et al. (0088) and use the following notations. where the subscript o É {1, 2, 3, 4) the option mentioned in step 1) above: Erdös-Rényí (ER) Outlier model: denoted by ER. k, 77), using as the measurement graph the ER model from NetworkX, where p is the edge density parameter for the ER measurement graph; Barabasi Albert (BA) Outlier model: denoted by BAO. k 17), where the measurement graph is a BA model with the number of edges to attach from a new node to existing nodes equal to /np/2]. using the standard implementation from NetworkX Hagberg et al. (2008); and Networkx[Hagberg Random Geometric Graph (RGG) Outlier model: denoted by RGGO. k n)), with NetworkX parameter "distance threshold value (radius)" 2p for the RGG measurement graph. For h = 1, omit the value A and subscript o in the notation, as the two options coincide in this special case.
For real-world data, we conduct sensor network localization the U.S. map and the PACM point cloud data set (Cucuringu et al.] 2012a 2a) with a focus on the SO(2) component, as follows, with data processing details provided in App. B.2 1) Starting with the ground-truth locations of 1097 U.S. cities (resp., n = 426 points), we construct patches using each city (resp., point) as a central node and add its 50 nearest neighbors to the corresponding patch. 2) For each patch, we add noise to each node's 's coordinates independently. +3) We then rotate the patches using random rotation angles (ground-trui) -tuth angles generated as in 1) for synthetic models). For each pair of patches that have at least 6 overlapping nodes, we apply Procrustes alignment (Gower) 1975) to estimate the rotation angle based on these overlapping nodes and add an edge to the observed measurement adjacency matrix. 44) We perform angular synchronization to obtain the initial estimated angles and update the estimated angles by shifting by the average pairwise differences between the estimated and ground-truth angles, to eliminate the degree of freedom of global rotation. .5) Finally, apply the estimated rotations to the noisy patches and estimate node coordinates by averaging the estimated locations for each node from all patches that contain this node.
6.2 BASELINES
In our numerical experiments for angular synchronization, we compare against 7 baselines, where results are averaged over 10 runs: Spectral Baseline (Spectral) by Singer 2011). * now-Normalized Spectral Baseline (SpectraL_RN) by Cucuringu et al. (202a)), Generalized Power Method (GPM) by Boumal (2016). e TranSyne by Huang et al. (2017). CEMP GCW, CEMP MST by Lerman &
Shi (2022). and Trimmed Averaging Synchronization (TAS) by Maunu & Lerman 2023).
7

---

Published as a conference paper at ICLR 2024
For more general k-synchronization, compare against two baselines from Cucuringu & Tyagi (2022), which are based on the top & cigenvectors the matrix H or its row-normin normoloaeeeed version. We names Spectral and Spectral RN to denote them before. To show that GNNSync (as well as the baselines) deviate from trivial or random solutions, we include an additional baseline denoted "Trivial" for each k, where all angles predicted equal (with value for simplicity).
6.3 MAIN EXPERIMENTAL RESULTS
R 0.15)
(b) 2GGO2 0.15)
(c) ERO (p 0.15)
(d) BAO
(p 0.15)
CNNSpse
Spectra
SpectraLRN
CPM
TanSrue
CEMP.GOW
CEMPAST
TAS
Trisil
Figure 3: MSE performance on angular synchronization (k 1). Error bars indicate one standard deviation. Dashed lines highlight GNNSync variants.
(a)
(b)
(c)
(d)
RGGO 0.15. 2) RGGOa(p 0.15, A 2)
RGGO. 0.05,
RGGO2 0.1,
(e)
(
g
(h)
RGGO,
0.15. k 3) RGGO, 0.15, A: 3)
RGGO, (p 0.05,
RGGO, 0.1, 3)
i
(k)
(I BAO (p
RGGO (p 0.15. & 1) RGGOz(p 0.15, A 1)
ERO: (p 0.15, & 1)
0.15, & 1)
GNNSyaoeycl
GNN9yno-mpeet
+ CNNSSmc-sum
Spectral
SpectraLRN
Trivial
Figure 4: MSE performance k-synchronization for A {2, 3, 4]. p is the network density and is the noise level. Error bars indicate one standard deviation. Dashed lines highlight GNNSyne variants.
By default, we use the output angles of the baseline "Spectral RN as input features for GNNSyne, and thus dn k. The main experimental results are shown in Fig 3 for i 1, and Fig. 4 for general l {2, 3, 4), with additional results reported in App. D For A > 1, we use "GNNSync-cycle", "GNNSyne-upset" and "GNNSyne-sum" denote GNNSync variants when considering the training loss function Leyete, Lupset. and Lupset Leydl. respectively.
From Fig. (with additional figures in App. Fig. & we conclude that GNNSyne produces generally the best performance compared to baselines, angular synchronization (k: 1). From Fig. (see also App. D Fig.
we again conclude that GNNSync variants attain leading performance for k 1. The first two columns of Fig. compare the performance of the two options of ground-trutt truth angles on RGGO models. In columns and 4, we show the effect of varying density parameter p, and different synthetic models under various measurement graphs.
8

---

Published as a conference paper at ICLR 2024
For A 1, GNNSyne-upset performs better than both baselines in most cases, with Cupset simple yet effective to train. GNNSync-cycle generally attains the best performance. As the problems become harder (with increasing 17, decreasing p. increasing k. more complex measurement graph RGG), GNNSync-cycle outperforms both baselines and other GNNSyne variants by a larger margin. The per- formance of GNNSync-sum lies between that of GNNSYnc-upset and GNNSyne-cycle, but is closer to that of GNNSync-upset, see App. D for more discussions on linear combinations of the two losses, We conclude that while GNNSync-upset generally attains satisfactory performance, GNNSyne-cycle is more robust to harder problems than other GNNSync variants and the baselines. Accounting for the performance of trivial guesses, we observe that GNNSyne variants are more robust to noise, and attain satisfactory performance even when the competitive baselines are outperformed by trivial guesses. We highlight that there is a clear advantage of using cycle consistency in the pipeline, especially when the problem is harder, thus reflecting the angular nature of the problem. For 3-cycle consistency and the cy- cle loss Leyete. gradient descent in principle drives down the (non-negative) values S of the sum of three predicted angular differences. To minimize the S values, we encourage reweighing process of the initial edge weights so that cycle consistency roughly holds. Unlike Lupses which explicitly encourages small M., values for all edges, Leyete only implicitly encourages small M,, values via the confidence matrix reweighing process for edges with relatively small noise. In an ideal case, we only have large M.j values on noisy edges. In this case, the reweighing process would downweight these noisy edges, which results in smaller value of the cycle loss function. This is also the underlying reason why Loyele more robust to noise than Lupset. For k > 1, we hence recommend using the more intricate Loyele function as the training loss function, and we will focus on GNNS in the ablation study.
From Fig. [ (see also App. Tab. and recover coordinates effectively, and is more robust to noise than baselines. GNNSyne attains competitive MSE values and Average Normalized Error (ANE) results, where ANE (defined explicitly in App.DD] measures the discrepancy between the predicted locations and the actual locations.
Fig. 18 27). p. we observe that GNNSyne is able to align patches
6.4 ABLATION STUDY AND DISCUSSION
In this subsection, we justify several model choices for all k: the use of the projected gradient steps; an end-to-end framework instead of training first without the projected gradient steps and then applying Algo. I as post-processing procedure; fixed instead of trainable {a,} values. For l > 1, we also justify the use of the H matrix in Algo. 1 instead of separate ( "s based on estimated graph assignments of the edges. To validate the ability of GNNSyne to borrow strength from baselines, we set the input feature matrix X set of angles that is estimated by one of the baselines (or k sets of angles estimated by one of the baselines for > 1) and report the performance.
Due to space considerations, results for the ablation study are reported in App. D For k = 1, Fig. 22- 24 report the MSE performance for different GNNSyne variants. Improvements over all possible base- lines when taking their output as input features for k 1 are reported in Fig. 34-36. For k 1, we re- port the results when using Laycle as the training loss function in Fig. 25-33. We conclude that Algo. indeed helpful in guiding GNNSyne to attain lower loss values (we omit loss results for space con- siderations) and better MSE performance, and that end-to-end training usually attains comparable or better performance than using Algo. for post-processing, even when there no trainable parameter in Algo. [ Moreover, the baselines are still outperformed by GNNSyne if we apply the same number of projected gradient steps as GNNSYc as fine-tuning post-processing to the baselines, as illustrated in Fig. 334 We observe across all data sets, that GNNSync usually improves on existing baselines when employing their outputs as input features, and never performs significantly worse than the corre- sponding bascline; hence. GNNSync can be used to enhance existing methods. Further, setting {a..) values to be trainable does not seem to boost performance much, and hence we stick to fixed (a.) val- ues. For k > 1, using separate H (0's 's instead of the whole H in Algo. I harms performance, which can be explained by the fact that learning graph assignments effectively via GNN outputs is challenging.
7 CONCLUSION AND OUTLOOK
This paper proposed general NN framework for angular synchronization and heterogeneous exten- sion. As the current framework is limited to SO(2), we believe that extending our GNN- frame- work to the setting of other more general groups is an exciting research direction to pursue, and consti- tutes ongoing work (for instance, for doing synchronization over the full Euclidean group Euc(2) = Zg x SO(2)* x R2 We also plan to optimize the loss functions under constraints, train our framework with supervision of ground-truth angles (anchor information). and explore the interplay with low-rank matrix completion. Another interesting direction is to extend our SNL example to explore the graph re- alization problem, of recovering point clouds from a sparse noisy set of pairwise Euclidean distances.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
Y.H. is supported by a Clarendon scholarship. G.R. is supported part by EPSRC grants EP/T018445// EP/W037211/1 and 0PPR018472/1 M.C. acknowledges support from the EPSRC grants EP/N510129/1 and EP/W037211/1 at The Alan Turing Institute.
REFERENCES
Federica Arrigoni and Andrea Fusiello. Synchronization problems in computer vision with closed- form solutions. International Journal of Computer Vision, 128(1):26 52, 2020.
Afonso S Bandeira, Nicolas Boumal, and Amit Singer. Tightness of the maximum likelihood semidefinite relaxation for angular synchronization. Mathematical Programming, 163(1):145-167, 2017.
Nicolas Boumal. Nonconvex phase synchronization. SIAM Journal Optimization, 26(4):2355- 2377, 2016.
Mihai Cucuringu. Sync-Rank: Robust ranking, constrained ranking and rank aggregation via eigenvector and SDP synchronization. IEEE Transactions Nenwork Science and Engineering, (1):58-79, 2016. ISSN 23274697. doi: 10.1 10110/9SE.2001.2222222
Mihai Cucuringu and Hemant Tyagi. An extension of the angular synchronization problem to the heterogeneous setting. Foundations of Data Science, 4(1):71-122, 2022. doi: 10.3934/fods. 2021036. /ttpa//cceeeeo/laaa0002022000000
Mihai Cucuringu, Yaron Lipman, and Amit Singer. Sensor network localization by eigenvector synchronization over the Euclidean group. ACM Transactions on Sensor Networks (TOSN), 8(3): 1-42, 2012a.
Mihai Cucuringu, Amit Singer, and David Cowburn. Eigenvector synchronization, graph rigidity and the molecule problem. Information and Inference: Journal the IMA, 1(1):21-67, 2012b.
Chandler Davis and William Morton Kahan. The rotation of eigenvectors by perturbation. iii. SIAM
Journal on Numerical Analysis, 7(1):1-46, 1970.
Frank Filbir, Felix Krahmer, and Oleh Melnyk. On recovery guarantees for angular synchronization. Journal of Fourier Analysis and Applications, 27(2):1-26, 2021.
Fajwel Fogel, Alexandre d' Aspremont, and Milan Vojnovic. SerialRank: Spectral ranking using seriation. Advances in Neural Information Processing Systems, 27:900-908, 2014.
Anton Forstner, Felix Krahmer, Oleh Melnyk, and Nada Sissouno. Well-conditioned ptychographic imaging via lost subspace completion. Inverse Problems, 36(10):105009, 2020.
Tingran Gao and Zhizhen Zhao. Multi-frequene phase synchronization. In International Conference on Machine Learning, pp. 2132-2141. PMLR, 2019.
Arvind Giridhar and Praveen R Kumar. Distributed clock synchronization over wireless networks: Algorithms and analysis. In Proceedings of the 45th IEEE Conference Decision and Control, pp. 4915-4920. IERE, 2006.
John Gower. Generalized Procrustes analysis. Psychometrika, 40:33-51, 1975.
Aric Hagberg, Pieter Swart, and Daniel Chult. Exploring network structure, dynamics, and function using NetworkX. Technical report, Los Alamos National Lab.(LANL), Los Alamos, NM (United States), 2008
Yixuan He, Quan Gan, David Wipf, Gesine D Reinert, Junchi Yan, and Mihai Cucuringu. GNNRank: Learning global rankings from pairwise comparisons via directed graph neural networks. In International Conference on Machine Learning, pp. 8581-8612. PMLR, 2022a.
Yixuan He, Gesine Reinert, and Mihai Cucuringu. DIGRAC: digraph clustering based on flow imbalance. In Learning Graphs Conference, pp. 21-1. PMLR, 2022b.
10

---

Published as a conference paper at ICLR 2024
Yixuan He, Xitong Zhang. Junjie Huang, Mihai Cucuringu. and Gesine Reinert. PyTorch Geometric Signed Directed: a survey and software on graph neural networks for signed and directed graphs arXiv preprint arXhv:2202.10799 2022c.
Xiangru Huang, Zhenxiao Liang, Chandrajit Bajaj, and Qixing Huang. Translation synchronization via truncated least squares. Advances in Neural Information Processing Systems, 30, 2017.
Vahan Huroyan, Gilad Lerman, and Hau-Tieng Wu. Solving jigsaw puzzles by the graph connection Laplacian. SIAM Journal on Imaging Sciences, 13(4):1717-1753, 2020.
Mark A Iwen, Brian Preskitt, Rayan Saab, and Aditya Viswanathan. Phase retrieval from local measurements: Improved robustness via digenvector-basee angular synchronization. Applied and Computational Harmonic Analysis, 48(1):415-444, 2020.
Noam Janco and Tamir Bendory. Unrolled algorithms for group synchronization. arXiv preprint arXiv:2207.0941 2022.
Gilad Lerman and Yumpeng Shi. Robust group synchronization via cycle-edge message passing. Foundations of Computational Mathematics, 2266):1665-1741, 2022.
Jiajin Li, Anthony Man-Cho So, and Wing-Kin Ma. Understanding notions of stationarity in nonsmooth optimization: A guided tour of various constructions of subdifferential for nonsmooth functions. IEEE Signal Processing Magazine, 37 2020.
Ren-Cang Li. Relative perturbation theory: li eigenspace and singular subspace variations. SIAM Journal on Matrix Analysis and Applications, 20(2):471-492, 1998.
Huikang Liu, Man-Chung Yue, and Anthony Man-Cho So. A unified approach synchronization problems over subgroups the orthogonal group. Applied and Computational Harmonic Analysis, 2023.
Alan Mainwaring, David Culler, Joseph Polastre, Robert Szewezyk, and John Anderson. Wireless sensor networks for habitat monitoring. In Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, pp. 88 97, 2002.
Tyler Maunu and Gilad Lerman. Depth descent synchronization in SO (d). International journal of computer vision, pp. 1- 2023.
Kurt Plarre and PR Kumar. Object tracking by scattered directional sensors. In Proceedings the 44th IEEE Conference on Decision and Control, pp. 3123-3128. IEEE, 2005.
R Tyrelll Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009.
Luana Ruiz, Fernando Gama, and Alejandro Ribeiro. Graph neural networks: Architectures, stability, and transferability. Proceedings of the IEEE, 109(5):660-66) 682,, 2021.
Yunpeng Shi and Gilad Lerman. Message passing least squares framework and its application to rotation synchronization. In International Conference on Machine Learning, pp. 3796-8806 PMLR, 2020.
Yunpeng Shi, Cole Wyeth, and Gilad Lerman. Robust group synchronization via quadratic programming. In International Conference Machine Learning, pp. 20095-20105. PMLR, 2022.
Amit Singer. Angular synchronization by eigenvectors and semidefinite programming. Applied and Computational Harmonic Analysis, 30(1):20-36, 2011.
Amit Singer and Yoel Shkolnisky.
structure determination from common lines in cryo-em by eigenvectors and semidefinite programming. SIAM journal on imaging sciences, 4(2): 543-572, 2011.
Zekun Tong, Yuxuan Liang, Changsheng Sun, Xinke Li, David Rosenblum, and Andrew Lim. Digraph inception convolutional networks. Advances in Neural Information Processing Systems, 33:17907-17918 2020.
11

---

Published as a conference paper at ICLR 2024
Stella X. Yu. Angular embeddingg from jarring intensity differences perceived luminance. In 2009 IEEE Conference on Computer Vision and Puttern Recognition, pp. 2302-2309. IEEE, 2009.
Stella X. Yu. Angular embedding: A robust quadratic criterion. IEEE Transactions on Pattern
Analysis and Machine Intelligence, 34(1):158-173, 2011.
Yi Yu, Tengyao Wang, and Richard Samworth. useful variant of the davis-kahan theorem for statisticians, Biometrika, 102(2):315-323, 2015.
Xitong Zhang, Yixuan He, Nathan Brugnone, Michael Perlmutter, and Matthew Hirn. MagNet: a neural network for directed graphs. Advances in Neural Information Processing Systems, 34: 27003-27015, 2021.
A ANALYTICAL DISCUSSIONS
A.1 PROPERTIES OF THE LOSS FUNCTIONS
In classical convex optimization of the type infx g(x), optimal values are achieved at stationary points; when the function is differentiable, then following Fermat's rule, stationary points points at which the gradient of vanishes. Such points are typically found via gradient descent methods. When the function g is not differentiable, then there weaker variants for differentiablity available such as the directional derivative. First we recall the notion of directional derivative and directional stationary point from Li et al. (2020). The directional derivative of function f at point x E R in the direction d E I!" is defined by
f(x + - f(x)
(' = lim 0
t
directional stationary point x R of the problem infxec g(x) for C R" and g R" R is point such that the directional derivatives in any direction d R" satisfy (g 1c) d) > 0. This notion broad enough to include functions such as the maximum which is not everywhere differentiable.
Moreover we say that a function f IRn - IR is locally Lipschitz if for any bounded set S c IR" there exists constant L 0 such that
( y) & L x y 1|2
for all x,y Note that locally Lipschitz function f is differentiable almost everywhere, see for example (Rockafellar & Wets 2009 Theorem 9.60) where also more background on directional derivatives and subdifferentials can be found.
Proof of Proposition it here.
Here we prove Proposition]] I from the main text; for convenience, we repeat
Proposition 3. Every local minimum of eq. 1 is directional stationary point of eq. 2
Proof. eq.
gives that
Lupect
M F /t
I Aij * 0,2r) (in Aig mod 2T,, Aij Tú, mod 2m))
VV
Σ I Arr * 0, min Aij mod 2m,, 2T (Ti,. Aig mod )x
where t is the number of nonzero elements in A. The function f (0,2 (0, 2T) given by f(x) = min(x?, (2T - 2)) is differentiable with derivative uniformly bounded by 4x (and is hence locally Lipschitz) except at the point x where it takes its maximum, ? Thus,
12

---

Published as a conference paper at ICLR 2024
this function is directionally differentiable Lipschitz function (which be seen by writing min(a.b) b) = (a b) L/1a bj and noting that f(z) = -|Ø| is a directionally differentiable Lipschitz function). Moreover optimization problem over the closed set C [0. 2n] representing sets(ri,
phrase the optimization problem for the upset loss
b.....n) which are
then used to obtain matrices 7 with entries Ti ri -r: ry mod 2x. Fact 6 in Li al. (020) then guarantees that every local minimum is directional stationary point of eq. 2
Discussion of the case of general k For general k-synchronization, we only require M M to be close to zero for one instead of all because each edge is assumed to belong to exactly one graph G₁-
Therefore in an ideal setting, for each edge (i.j) &, exactly of the entries M (.j: 1 l= 1...., is zero. If all entries are large then this indicates that the information for (i, is very noisy. Subsequently, the entry for (i, is downweighted in the updated graph for the cycle loss function. The rationale is that when edge information is very noisy, the cycle consistency will often be violated; violations for edge information that is not so noisy are more important for angular synchronization as they should contain a stronger signal.
In terms of the cycle loss function itself, the confidence matrix C for edges in G arises. First consider the optimization problem in which Č is omitted; taking A (A A mod 2n and we optimize the upset loss, the cycle loss, or both. For the upset loss, eq. (5) itself when considering fixed À (1) terms, can be analyzed similarly to the analysis of Lupset in Proposition 1, using that the minimum as appearing in M.j = (i...().....))) M.) is directionally differentiable Lipschitz function. For the cycle loss function, the expression of (!))
ccycle takes a constant (when we regard Á (1) as fixed) (.g.)) mod 2T. This minimum is equivalent to iiig mod 2x)|, which is again a directionally differentiable Lipschitz function. Arguing as for Proposition 1 thus shows that the statement of this proposition extends to this special treatment of the k-synchronization problem.
away from the minimum of s(() 1.j. mod 2n and (-S
IT (S
In our general treatment of the k-synchronization problem, the confidence matrix Č depends on the maximum M of the residual matrices and involves the expression 1+M., ((A..) # 0). While
the function fx) I+ is differentiable for 0, its composition with function such M may not be differentiable, as M only possesses very weak notion of differential, called limitiig subdifferential in Li et al. (2020). to which the chain rule does not apply. This complex dependence hinders rigorous analysis of the general treatment of the k-synchronization problem, where even the chain rule is not guaranteed to hold.
Non-differentiable points of the loss function Although the Frobenius norm, the min function, and modulo have non-differentiable points, these points have measure zero. Moreover, we use Py PoTch autograd [ for gradient calculation, even in the presence of non-differentiable points, backpropagation be carried out whenever an approximate gradient can be constructed. Note that the absolute value function is convex, and hence autograd will apply the sub-gradee bub-gradient of the minimum norm. There also exist differentiable approximations for the modulo, and hence backpropagation can still be executed. Finally, in our experiments, we do not empirically observe any issue of convergence.
Novelty While the design of the upset loss in isolation may be relatively straightforward for the k 1 case, we provide theoretical support well as a less obvious loss function extension to handle broader &o > 2 cases that rely on assigning edges to different graphs. The design of the cycle loss is not trivial and based on problem-specine insights.
A.2 ROBUSTNESS OF GNNSYNC
First review DIMPA (Directed Mixed Path Aggregation) from He et al. (022b) for obtaining a network embedding. DIMPA captures local network information by taking a weighted average of information from neighbors within h hops. Here we use h 2 hops throughout the paper. Let A E Rexn be an adjacency and A, its row-normalization. weighted self-loop is added to each
13

---

Published as a conference paper at ICLR 2024
node; then normalize by setting A, (D*)-1A*, where À = A + rl,, with D the diagonal matrix with entries D Σ3 A In the identity matrix, and is small value; as in He al. 2022b) take 7 0.5.
The ho- source matrix is given by (A.)*. The set of up-to-h-hop source neighborhood matrices is
denoted as A% = (In, ......, (A,)*1 "). Similarly, for aggregating information when each node is viewed as target node of a link, we carry out the same procedure for the transpose A T The set of up-to-h-hop target neighborhood matrices is denotes A (In, A....., (A,)"), where A, is
the row-normalized target adjacency matrix calculated from A
Let the input feature matrix be denoted by X E RRnxss The source embedding given by
Σ W W .N.N Q" Rnnd
Z.
(NEA
where for each N, wi is learnable scalar, d is the dimension of this embedding, and Q = ML.( Here, the hyperparameter L controls the number of layers in the multilayer perceptron (MLP) with ReLU activation but without the bias terms; as in He et al. (2022b) we fix = throughout. Each layer of the MLP has the same number d of hidden units. The target embedding Z, is defined similarly, with 8 replaced by i ineq. 77) After these two decoupled aggregations, the embeddings are concatenated to obtain the final node embedding as a (2d) matrix CONCAT (Z., Zz).
Proof of Proposition 2 Here we prove Proposition from the main text; for convenience, we repeat it here.
Proposition 4. For adjacency matrices A, Å, assume their row-normalized variants As, A. Ar, A. satisfy
A. A. 6, and A A F ce where subscripts s, t denote source and target,
X < Cj. Then their initial an- - B&cs Bic, + Bye for values Ba, Br, By that can be bounded by imposing constraints on model parameters and inpul.
resp. Assume further their feature matrices X, & satisfy X
gles p(0), f0(0) from trained GNNSyne using DIMPA satisfy ||=(0)-(((0)))
1(0)
Proof. Let assume the input feature matrices X. Raxd for A and Å, respectively.
The DIMPA procedures for the input row- now-normllized adjacency matrices A,, A, with 2 hops and hidden dimension d can be written concatenation of the source and target node embeddings Z, and Z, where
Z, (I, + u2 A, A ReLU an) WaI,
(8)
Z, = (I, + At + A ReLU W..
Here I, E R=** is the identity matrix, Gsl. 0,2; de1, a:2 E R, W Wa e Rddxd where d is the hidden dimension, and W.1 W. R4xh, Similarly, we have for A, and A,
Z, (I, + 2 A ReLU s0 W a1,
(9)
2. (I, + a. A, + R W...
After DIMPA, carry out the innerproduct procedure and sigmoid rescaling, obtain for k 2nsigmoidd Z,a, Z,a; + b), p(0) 2rsigmoid(Z,a, 2,a + b):
(10)
where a,, a e d and b is trained scalar.
For & 1, we have (before reshaping (0)) and (0) from shape nk x shape n x k which does not change the Frobenius norm)
Z.a, + b), (()) 2nsigmoid 2, + b), where a, a, E d and IR Indeed, we could view the scalar as a 1D vector, and consider eq. (10) special case of eq. [11
2rsigmoid
(11)
14

---

Published as a conference paper at ICLR 2024
Using eq. ( and eq. p
along with the triangle inequality, we have that
Z, Z
(In + 0zl A + ReLU .1 - (I, + A. + 02 A W
In + 0.1 A, + A
W. W (In 0.1 A, + + A.RLLUXXW W.i
(In 01 A, 4 ReIUU 40 W.: (I, + 0,5 A, a A. W
00 (A, A.) a.2( A ] ReLU
Usl A + A,2 A
|Wille ReLU .0) ReLU(X(W.)))
A, Ag F
[1st + a22 AA, (e.)ReLU((W.o))) +
I, + ael 00.1 A, + A
Wallp Wool x X-X
<e, B,0 + eg BB0
(12)
where B.0 [0a)] a,2 A. (ReL so) Ws By: = I, + aa. A. A
and
|Walll || W Woll.
Note that we also use the fact that the ReLU
function is Lipschitz with Lipschitz constant 1. Likewise, we have
Ze 2011 Beo + e BB
(13)
where Bi0
[an + (ra(A, + (.)]ReLU(XXW.))) eo W.1 and
P
By
I, + a. A, + 4,2 A
|Wall |[oll
With eq. (12 and eq.
13 noting that the sigmoid function is Lipschitz with Lipschitz constant 1, we
employ eq. (11) to obtain
(0) p(0)
F
2tsigmoid Z.a, + Z,a; + b) - 2rsigmoid + 2,a + b)
2T
Z, + Z,a, + +b) (Ž,a, + Z,a, + b)
-m
z, 2,)a, (Z. -Z.)a
22
(Z 2, |
|| p
+|(22: Ze )ae
-2T
||aolle
Zg 2,1
+ ||all/ 1|
1z - 2, (|,)
F
2T, + Bc + BBB + ej Byr)
B, +BB tBB
15

---

Published as a conference paper at ICLR 2024
with values
B₂ =2 = 2n |ao + a,2 + A.)]ReLU(XX.a) W
B. =2 2
|lan + a:2(A, + A/JReLU(XX.o)WW..
B (2/ + Byt)
(14)
=2x
In + A, A
[Walle |Wooll
+ 2T In + A, + ar A Walle W
If we in addition have
W soll r E ,, [ < 1, W < 1, [ & 1,
dsl + a.2 (A, + A.)
< 1, |a a: (A+ Ae)
< 1,
XW FF 1
In + ass A. uw2 A
1
In+ + a+ R. + a/2
11
F
F
then the bound becomes
||r(0] - |(00| < 2T(( + + 2es),
021 a.2 (A, A.) ReL so)
0al a.2 A. + A.)
|ReLU(XW .0)1 |Wallp
0sl aA2(A, + A.)
|XW Waill
and similarly for By. This completes the proof.
Discussion on GNNSync's robustness noise With the above proposition, we could consider Á as the ground-truth noiseless adjacency matrix whose nonzero entries encode (0; 02) mod 2n, and A as the actual noisy observed input graph. We then execute row normalization to obtain the source and target matrices A, and A, for the ground-truth and A, and A, for the observation, respectively. In a favourable noise regime, e, and e, would be small. The value Ey comes from the feature generation method. For Spectral RN baseline input feature generation method for example, this involves some eigensolver corresponding to complex Hermitian matrices, and hence the Davis-Kahan Theorem (Davis & Kahan 1970) one of its variants (Li 1998 Yu et al. 2015) could be applied to upper-bound e As for the values B., Br, and By. we could bound them by adding constraints to GNNSyne's 's model parameters. Employing a backpropagation procedure with our novel loss functions could further boost the robustness of GNNSync, with learnable procedures, as shown for example Ruiz al. (202T)
B
DATA SETS
B.1 RANDOM GRAPH OUTLIER MODELS
The detailed synthetic data generation process is as follows:
1. Given the number of nodes n., generate k group(s) of ground-truth angles {0,, (l....,n) for I (1....,k) One option is to generate each 0,, from the same Gamma distribution with shape 0.5 and scale 2T. We denote this option with subscript "1". Since angles could be highly correlated practical scenarios, we introduce a more realistic but challenging option "2", with multivariate normal ground-truth angles. For example, in the SNL application, angles correspond to patch rotations, and may well be that patches in similar geographic regions have corresponding rotations. The mean of the ground-truth angles is ,, with covariance matrix for each E {1...., k} defined by ww T, where entries in generated independently from standard normal distribution. We then apply mod 2m to all angles to ensure that they lie in [0, 2T). We thus obtain the ground-truth adjacency matrix (matrices) A Raxx, whose (i,j) element is given by (0.,- 0z4)) mod 2n.
16

---

Published as a conference paper at ICLR 2024
2. Generate noisy background adjacency matrix Aoose R whose entries are indepen- dently generated from a uniform distribution over [0,2 2T).
3. Generate selection matrix Age R=** whose entries are independently drawn from a Uniform(0.1) distribution. The (i entry of this selection matrix is used to assign whether or not the observation is noisy, and if not noisy, to which graph assigned, using for
[ ,....,k
Buoise (.. j:1) = 1 ((1 7) 1)/k & (e.)).)) (1-n)
and Bnoise (;, 1 (i, (1 -1-11 (1-n)), where 1(-) the indicator function.
4. Construct a complete (without self-loops) weighted adjaceney matrix Acomplete E RR" R by complete (1,5)) (I..).....) A (1) GT (1. Boosse (i, (i, ( Booise (i, (0).
5. Generate a measurement graph G with adjacency matrix G using standard random graph model, as introduced by Sec. 6.1
6. The edges in & are the edges on which we observe the noisy version Acomplete of the ground- truth adjacency matrix (matrices) A to obtain the temporary adjacency matrix T2 by T (i, (somplese (G(i)) * 0).
7. The true angle differences would yield skew-symmetric matrix before taking the entries mod 2n. We therefore construct a skew symmmetriiiic matrix T2 by setting T2(1, i) = 0 for all i, and for * j setting 5) T (i.j) < j) T (J, (() j).
8. In the skew-symmetric matrix, each entry appears twice, with different signs. For com- putational reasons, for the final adjacency matrix, we only keep the non-negative entries, except for evaluation. We obtain the final adjacency matrix A by At,j A(i,j) 1 > 0) mod 2n.
In addition the two options introduced in Sec. 6. we introduce two more options for the ground- truth angle generation process here, which are both multivariate normal distributions, but with different covariance matrices. For option "3", the covariance matrix is just the identity matrix. For option "4", we have block-diagonal covariance matrix, with six blocks, each of which is generated independently according to option "2" as stated in Sec. 6.I in the main text.
As methods could be applied to different connected components of disconnected graphs separately, we focus on weakly connected networks. We have checked that all generated networks our experiments are weakly connected.
The reason behind the naming convention "outlier" stems from the noisy offset entries in the adjacency matrix.
Steps 7 and 8 are to ensure that there does not exist an edge (i. such that (As, + A,.) mod 2T * O, as this would be confusing. In principle, could work with the upper-triangue part or the lower- triangular part of the adjacency matrix first, then obtain the skew-symmetric adjacency matrix T2 and apply step 8 again. The procedures mentioned in Sec. 6. are what implement in practice, which should take no more than twice the computational cost compared to working with half of the adjacency matrix the beginning. Note that data generation only happens once before running the actual experiments.
Our synthetic data settings are similar those in previous angular synchronization papers, such as Singer 2 Lerman & Shi (2022); Cucuringu & Tyagi (2022). to generate noisy samples from an outhier model (where each outlier measurement generated uniformly random), instead of using additive Gaussian noise in the so-called spike models. The choice of the number of nodes 360 could be changed to other numbers; we chose to relate to 360 possible integer degrees of an angle. Note that the initial work of Singer (2011) considered n random rotation angles uniformly distributed in [o, 2T). J. We do not observe a large difference in the performance of other sizes (we have also tried 300 and 500, for example).
The choice of synthetic data set construction is inspired by Singer (201 and Cucuringu & Tyagi (2022). They are noisy versions of standard random graph models. These random graph models were chosen as they can be used for comparison. Indeed, some previous works have only used ER measurement graphs in Lerman & Shi 2022), and [Singer (201T) theoretically analyzed and
17

---

Published as a conference paper at ICLR 2024
experimented with both sparse ER and complete measurement graphs; already have more thorough setup in our experiments. Furthermore, the addition of the RGG model stems from the very fact that this model is perhaps the most representative one, given the applications that have motivated the development of the group synchronization problem over the last decade. Indeed, in sensor network localization or the molecule problem in NMR structural biology, pairwise Fuclidean distance information is only available between nearby sensors or atoms (c.g.. certain sensors/atoms are connected if at most miles//ngstroom apart), hence leading an RGG (dise graph) model. In this setup, in order to recover the latent coordinates, the state-of soute-of-the-are -he methods rely on divide-and. conquer approaches that first divide the graph into overlapping subgraphs /patches, embed locally to take advantage of the higher edge density locally, and finally aim to stitch globally, which is where group synchronization comes into play. Therefore, any patch-based reconstruction method that leverages the local geometry is only able to pairwise align only nearby patches that have enough points in common; far away patches that do not overlap simply cannot be aligned. Thus, the choice of RGG resembles best the real- world applications. The ER model has been predominantly used in the literature as it is easier to analyze theoretically compared to RGG, in light of available tools from the random matrix theory literature.
B.2 SENSOR NETWORK LOCALIZATION
Previous works in the field of angular synchronization typically only consider synthetic data sets in their experiments, and those applying synchronization to real-world data do not typically publish the data sets. Concrete examples for such works include tracking the trajectory of a moving object using directional sensors (Plarre & Kumar 2005), and habitat monitoring in an infrastructure- less environment in which radios are turned on at designated times to save power on Great Duck Island (Mainwaring et al. 2002).
In this paper, we adapt the task on group synchronization over the Euclidean group of rigid motions Euc(2) 22 x SO(2) x I2 to real-world task, by focusing on the angular synchronization SO(2) component. This task on a real-world data set is a special case of the sensor network localization (SNL) task the plane (I2) mentioned in Cucuringu et al. (2012a), but we focus on synchronization over SO(2) only, as we do not consider any translations or reflections. Though we do not have purely real-world data sets that are employed in practice, localization (with a focus on rotation only) and conduct the localization task on the U.S. map as well as PACM point cloud. In detail, the task is conducted as follows, where Fig. provides an overview of the pipeline on the U.S. map with an illustrative example:
mimic the practical task of sensor network
1. Starting with the ground- -ruth locations of U.S. cities (we have 1097 cities, see red dots in Fig. (5), we construct patches using each city as a central node and add its kpatch = 50 nearest neighbors to the corresponding patch (see Fig. (]a)). We then obtain m n 1097 patches (see Fig. 5)b) for a two-patch example). This is to represent sensor patches in the real world.
2. For each patch, we add noise to each node's coordinates using independent normal dis- tributions for x and coordinates respectively, with mean zero and standard deviation times of x and y coordinates' standard deviation, respectively (see Fig. ((c)). Note that the noise added to the same node is independent for different patches. This is to represent noisy observations due to the lack of use of the expensive GPS service to estimate sensor coordinates.
3. We then rotate the patches based on some ground-truth rotation angles 01,...,,, On (see Fig. d()). Here we generate the angles using one of the options introduced in Sec. and and Sec. B.I This again is to represent noisy observations in the real world.
4. Then for each pair of the patches that have least kitres Procrustes alignment (Gower, 1975) to estimate the rotation angle based on these overlapping nodes (but with noisy coordinates) and add an edge with the weight the estimated rotation angle to the observed (measurement) adjacency matrix A. In other words, if two patches P,, P. that have at least kitess = 6 overlapping nodes, we have Ai,, the estimated rotation angle from Procrustes alignment to rotate P, to align with P.. This angle is estimation of f; f,. The threshold is set to represent the real-world scenario where only nearby sensors may communicate with each other.
overlapping nodes, we apply
18

---

Published as a conference paper at ICLR 2024
5. After that, perform angular synchronization the sparse adjacency matrix A (retaining only the upper triangular entries) obtain the initial estimated angles ri ,..., ,n for each patch.
(0) (0)
6. We then update the estimated angles by shifting by the average of pairwise differences between the estimated and ground-truth angles, in order to mod out the global degree of freedom from the synchronization step (see Fig. (e)) That is, we first calculate the average of pairwise differences by puriiise
1
0:) mod 2n], then set r;
(T:
pairwise) mod 2 I....,
7. Next, we apply the estimated rotations to the noisy patches.
8. Finally, we estimate the city coordinates by averaging the estimated locations for each city (node) across patches that contain this city (node) (see Fig. 5()).
Note that the noise in the observed adjacency matrix originates from the error by Procrustes alignment, with possible noise added to nodes' coordinates. Therefore, even when v = 0, the observed adjacency matrix may not align perfectly with ground-truth pairwise angular offsets. Besides, the observed adjacency matrix is sparse instead of complete due to the thresholding set up to only connect two nodes in the graph the patches have enough overlapping nodes. In our experiments, we vary 1) from [0, 0.05, 0.1, 0.15, 0.2, 0.25]
Our current experiment focused on group synchronization over the group SO(2), and in future work we plan to explore synchronization over the full Euclidean group Euc(2) = Ze SO(2) x R similar Cucuringu al. (2)12a), where in addition to rotations, both reflections and translations are considered and synchronized over.
C IMPLEMENTATION DETAILS
C.I SETUP
We the whole graph for training for most 1000 epochs, and stop early if the loss value does not decrease for 200 epochs. We use Stochastic Gradient Descend (SGD) as the optimizer and le regularization with weight decay 5 10 to avoid overfitting. We use as learning rate 0.005 throughout.
For each synthetic data set, we generate synthetic networks under the same setting, each with repeated runs.
The DIMPA model is inherited from He et al. (2022b). Indeed, other directed graph embedding neural network methods such as Tong et al. (2020) and Zhang et al. (202)) could be employed, and we pick DIMPA just for simplicity. our experiments, we did try out Tong et al. (2020), and we do not observe much difference in the performance as long as some directed graph embeddings could be produced.
C.2 CODES, DATA AND HARDWARE
To fully reproduce our results, anonymized code is available at /attps:/ com/ SheryllYX: CNN Sync| Experiments conducted on compute nodes, each with 8 Nvidia Tesla T4, 96 Intel Xeon Platinum 8259CL CPUs @ 2.50GHz and 378GB RAM. All experiments can be completed within several days, including all variants.
The data sets considered here are relatively small and the same applies to GNNSync's competitive papers. Although each individual task does require many resources (often 5min/run), for the
19

---

Published as a conference paper at ICLR 2024
196
(a) Construct patch in blue based on nearest neighbors.
(b) Construct another patch in yellow.
(c) Add noise to each node's s
coordinates in each patch.
(d) Rotate the patches based on ground-trun rotation angles. Then apply Procrustes analysis to estimate the rotation angle based on overlapping nodes (in green). Here use
(c) Perform angular synchronization the full adjacency matrix (keeping only upper triangular entries) to obtain estimated angles for each patch. Update the estimated angles by a global shift obtain final estimates. Apply estimated rotations to the noisy patches.
(f) Recovered central point locations (in blue) versus their ground-truth locations (in green) on the U.S. map (in red) for the two sampled patches. The estimated by taking the average recovered coordinates for each city (node) from patches that contain this node.
locations
Oblue 174" and Byellww 178 with ground-truth
Obtuc Oyellow 356
Figure 5: U.S. city patch localization pipeline with two patches as an example: Starting with the ground-truth locations of U.S. cities, we construct patches using each city as central node and add its Kpuchh- 50 nearest neighbors to the corresponding patch. We then add noise to each node's coordinates using independent normal distributions for and y coordinates respectively, with mean zero and standard deviation 7 0.05 times of and y coordinates' standard deviation, respectively. We then rotate the patches based on some ground-truth rotation angles from option "2" introduced in Sec. 4.1. Here we use Oblue = 174" and Byellow = 178 with ground-truth O yycllow = 356". The estimated rotation angle from the blue patch to the yellow one is Ablue, yellow 6.25 (i.e., 358"). Then we apply Procrustes analysis to estimate the rotation angle based on overlapping nodes (but with noisy coordinates). After that, perform angular synchronization only upper triangular entries) to obtain estimated angles for each patch. We then update the estimated angles by shifting by the average of pairwise differences between the estimated and ground-truth angles. Here we have estimates Tolue = 173" and ryellow = 175" with Pblue Tylllow = 358 Then we apply estimated rotations to the noisy patches. Finally, we obtain recovered central point locations for the two sampled patches. The locations are estimated by taking the average recovered coordinates for each city (node) from all patches that contain this node. The recovered points are colored blue, while their ground-truth locations are colored in green.
the full adjacency matrix A (keeping
synthetic data sets in this paper have
3 measurement graph styles for l = 1) 10(noise levels)
3( (sparsity levels) 4gground-trrth options)
3( number of larger k values) - 6(measurement graph options for k 1) 8(noise levels)
-sparsity levels) 4gground-truth options)
360 1, 728 2, 088
20

---

Published as a conference paper at ICLR 2024
synthetic data sets. Each data set requires 10 runs for each of the
1 (main results)
+ (ifffreett baselines as input features)
+ Inno Projected Gradient Steps)
+ 1traiinable ax)
variants for the regular angular synchronization (k = 1) and (main results)
2(differeet baselines as input features)
2ddifeerent baseline)
+ (trainabee {a,))
2nno Projected Gradient Steps)
2(separate )
+5 +(otherr linear combinations of the loss function)
18
=
variants for general k-synchroniization with k E (2,3.4). Therefore, the set of tasks in this paper requires total of 360 10 + 1, 728 10 32, 400 + 311, 040 343, 440 runs.
The baselines are typically faster, as they do not involve training, but GNNSyne is also pretty computationally friendly, not at a significantly higher computational expense. Indeed, the set of all cycles could be pre-computed before training. For k-synchronization, we only need to verify whether all edges a cycle are contained in an estimated graph, and to keep only these cycles for computation. There is loop that repeats k times, but for each loop, only matrix operations are involved, which can be done in parallel for all possible cycles. This would not be too expensive, as validated by our experiments. Besides, for the MSE function, in the first place. For evaluation, it does require computing all permutations of but the evaluation is only conducted once. Therefore, these computationally expensive operations (locating all possible cycles and permutations of k in the MSE computation) are not involved in training, but only before or after training, and hence our method still scalable with n and k.
do not use it for training, so it is not loss function
C.3 BASELINE IMPLEMENTATION
com/ yunpeng shi/ CEMP ree wwweeeaiinnieeeeeeeeeee hta///aiinn//e 802 to Python. For other baselines, we implement the approaches based on equations from the original papers. For TAS, we transform the MatLab codes from the authors of Maunu & Lerman (2023) Python. We set the number of epochs 50, and set the trimming parameter to zero due to the high sparsity level of our synthetic networks, otherwise, almost all predictions would be the same, just like the Trivial solution.
For CEMP GCC and CEMP MST, we adapt the MatLab code from
Besides, we do not compare GNNSync against the method in Gao & Zhao (2019) in our experiments, as there is no code available. Also, their algorithm involves integration and angular argmax each iteration, which seems to be computationally expensive.
Finally, we are aware of Semi-Definite Programming (SDP) baselines but have found them too time-consuming space-inefficient. Also, from (Singer (201I). we know that SDP and spectral methods have comparable performance. Therefore, in our experiments, we omit the SDP results.
C.4 MSE CALCULATION
As stated in eq. the MSE function calculates the mean square error using global angular rotation that minimizes the MSE value. The implementation of the MSE function, however, does not explicitly search for the lowest MSE value through grid search or gradient descent. Inspired by the implementation of the MSE in Singer & Shkolnisky (201T). we first map each of the predicted angles and the ground-truth angles R to rotation matrices by the mapping function
cos(() (0) - -sin ())
(o)
sin
cos 0
21

---

Published as a conference paper at ICLR 2024
Table Average MSE values (plus/minus one standard deviation) for the real-world experiments on the U.S. map over ten runs. The best is marked in bold red while the second best is in underline blue.
11
option
GNNSyn:
Spectral
Spectral RN
GPM
TranSync
CEMP,GCW GCW
CEMP MST
TAS
Trivial
01
0.000=0.000
0.000:0.000
0.000:0.000
0.000:0.000
0,009-0.000
0.000:0.000
0.009-0.000
2.358-100075
2
0
0.004=11.001
0.000:110000
0.000=0.000
0.000=11000
0.000-11000
0.000=11.000
0.000=0.000
1.56720.085
1.566t0..177
0
0.000.0.000 0.000
0.000.0.000
-0,000 0.000
-0,000
-0,000 0.000
-0,000 0.000
-0,000 0.000
0.138.10.174
0.138.00.14
0
0.002=00000
0.000:00.009
0.000:0.000
0.000:0.000
0.009-0.000
0.000:0.000
1.00000.000
0.651-0:277
11602--00
26625-00.25
0.05
0.004:00.006
00000
0,006 00001
0,006 0.000
0,036:0:027
00040
1162:00435
2.340-10.098
2.411
0.05
0.010=0.000
0.006:00.000
0.006:00000
0.005=00.00
0,026=0:006
0.072:0.006
1.559400003
1.55920.055
0.006
0.816.0.40
2.827
0.29310.488
0.294
0.05
0.006:00001
0,096-0..00
0.024
0.319:0.255
0.780=02273
0.759:00.372
0.805
0.07
0. 0.14 0.005:00.05
0.577
2.81200 293
2.368:00
0.1
0,025 0.002
1.000
DX02S 0.000
0 0.027 0.00
0.188 0.053
0.397 0.048
2. 874 0.315
1.558.00.00 10.000
1.564 0.023
0.1
0.009
0.024+000004 004
0.025 5000000
0.129-00045
1.775=11 104
3 00.2-0
0:13::001155
0.1 35:+2.1177
0.1
0.821 1.000
B.03620.00
0.021 00.000
0 0.001-0.000
0. 0.12
3. 100
0666-20.20 238
D. 6666200 0.2.222255
0.15
0.059: 0.00S
0,075 0.012
10.0130.013
0.002 1..00S
0 0.279
096-10.473
3 2,888 0.092
2.363-10.117
2. 2,596- 00.118
0.15
0.857
D.052+00000
00.003
0 122
193 252
3 5.50 00.501
566
1.506+-0.005
0.15
0.037 0.005
0.05210.000 0.011
0.048.0.000 909
O 0461 0.000
0.277 0.004
1,74100.54
3.67 0.222
0.1
0. 138 174
0.15
0.043 0.007
D 00.0000.000
1046-00.00
0.591
1.37=00.172 174
3.519:0,152
2.2
0.2
00,0177
0.14
1.00=002257
2.
3.711=0,1
077
2. 2.59920.009
0.101 0,006
0.163 00.017
0.159
DIPATO.0
1.05410.245
2,052 0,263
3.717.0,
00.00
0.003
0.012
0.756=00.222
3 3,699:0,111
0.335+00277
0,336+0. 380
0.3
0.006
0.006:000017
0.009
O. 0.07
0.717:0.258
2. 2,040:20,33 334
0.080
660:200
0.663:0
0.25
0.158 0.00S
0.244
0.263 00.039
0.164 0:011
1.80000.509
2,888 00,240
3.791 0.095
2.427:10.069
2.442 0.009
0.25
2
0,163 0.013
10.038
0.294 10.04
0.193 10.018
1,888 10.737
2,833 002294
3.782 0. 108
1.364100.037
1.566. 10,037
0.25
U.I0S-BB.KKS
0.143+-00018
0.242 1005
0.103--00011
3.050=00.552 1.205-01.533
0.138+0.174 0.765=00088
11113++-00 1-11444
0.25
0.138200074
D. 0.17000.079
D. 0.76200040
0.107:00011
1,20620.5300
2.76720.477
0.767
0660200236
0.66322.225
We then calculate the matrix
1
rot(R.) rro((r.).
1=1
The MSE value is given by
4 - 2 Σ sing, (Q),
where sing, Q) is the i-th singular value of Q during Singular Value Decomposition (SVD).
D EXTENDED EXPERIMENTAL RESULTS
This section reports extended experimental results mentioned in the main text.
D.1 EXTENDED MAIN RESULTS
Results on real-world data sets shown in Fig. 18 to 27, while other PACM results are omitted but with the same conclusion. To accommodate potential variability in different runs, we report the mean and standard deviation of ten runs (two repeated runs on five different sets of ground-truth angles) in Tab. and 3 We also compute the Average Normalized Error (ANE) for coordinate recovery similar to eq. (44) of
Full main synthetic experimental results are shown in Fig. to 17
Cucuringu et al. (2012a), and report mean and one standard deviation of the results in Tab. 2 and
4 Specifically, denote (.,, as the ground-truth coordinate for node i where i = I,..., n2 and (1e, (.) as the predicted coordinate, we define the Average Normalized Error (ANE) as
(z. - 22 (ys TT
ANE
(15)
[[; 20)² (3/ yo
where (Io, 30) = (1 24 - v (0,0) is the center of mass of the true coordinates. We conclude that GNNSyne is able effectively recover coordinates. We also observe that GNNSyne more robust to the noise of patch coordinates. We omit the visual plots for the "Trivial" baseline but report its performance in Tab.
and
22

---

Published as a conference paper at ICLR 2024
Table 2: Average ANE values (plus/minus one standard deviation) for the real-world experiments on the U.S. map over ten runs. The best is marked in bold red while the second best is in underline blue.
5
option
GNNSSnc
Spectral
Spectral RN
GPM
TranSyne
CEMP GCW
CEMP MST
TAS
Trivial
0
0.075-00028
0.000:00.000
0.000
0.000020.100
0.000:20.000
0.000:20.000
0.000:10.000
0.740:00003
1.973-0.261
0
2
0.01700.010
0.000:0.000
0.000 0,000
0,000 00000
0.000-00.000
0.000.10.000
0.000:10.00
0.225:0.015
0.423-00.044
0
3
0.001
0.000
0.000 0.000
0.000
6.00010.000
0,,000
0.000.10.000
0,000.10.000
00,00
0.050.0..41
0.01910.019
0.010:0.016
0.000:0.000
0.000:00.000
0.000:10.000
0.000:000000
0.000:0.000
0.213:0.075
0.219:0.078
0.074-0.027
6.022:0.010
0.032:0.011
0.360+0.591
0.121:0.969
0.009:00.95
0.725-00025
09941-0277
0.05
2
0.051 0.013
0.508
0.030 0.000
0.159
0.092100.00
0.146
0.638 10.238
0.421-0000
0,49
0.05
3
00009-0.0017
0.118:001600
0.005+0.005
0.039=00.008
0.469+0.765
0,708:20.55 558
0.900 178
0.089=0.124
0 124
0,05
4
0.259
0,404
0.001:00.00
0.032 0.02-00008
0.058:10.009
0.494:0.555
0.750:00.30
0.243-00122
0.250-0.122
0.1
0.078 0.01
0.070 0.024
0.20110.152
0,160.10 18181
0.164 10,050
0.568: 0..
1,068 10.135
0.733 00.028
0.987.0.28
0.1
0.017
0077=0.007
0.076+00.005
0,259 355
0.270+0.002
0.345+0.042
0.992
0.11-=0.016
0.11-00016
0.015
0.05
0.0/9
0.324-0..60
0.503+0.500
0.920=00229
1,019 100
0.053-0.047
0.1
0.77-00000
0.016
D:124::0:119
0-226:20.133 135
8288
0,964
0.715=0079
0.19=0078
0.15
0.313=00.44 449
02116=0.15 153
0.602
0.00::00022
0.315+0.0277
0.859=0.422
1.11
L101 0.755=00082
0.15
2
0.0761...00
0.573
0..002
76 L 000026
O. 0.000..304
0K933.0 460
0. 0.964
0.005100015
0.244100044
0.15
3
0.3347
O 0118:20:100 165
0. 0.220.0224
D. 1. 0.005
0.52410.527
0.787 145
0.979::0 105
0.845
0.045
0.10420.080 0.0052
0.929+0.522
0.947=00-400
0.215=00077
0,220-00078
0.2
0.131
0,247.00200
0.3355
0.876.0.144
1,07710.05
0.74910.027
10266
0.2
0.0912000018
0.312
0.43R 506
0.967-0-277
1. 0000
0.17
0024:00014
0.2
3
0 -00077
0.133 0.025
01.3000..028
0.032
0.96410.6499
0.889110.211
1.000
0.109-0.092
0.110
0.2
4
0.077 0.023
0,123 0.029
0.126 10.025
00.02
0.72410.484
10.211
0.999 10.03)
0.215 10.06
0.221 10.077
0122
0.197 0.066
0.101
0.337
0.478:0.418
0.656++0.188
0.978=00.13
0. 0.260=0.022 0.08
0.514=00.26 263
0.25
2
0.122 0.034
0.494: 0.399
0,229
0,546:0.701
0.912:10.215
0.805
0.425=0.00 L.000+0.025
0.425=00014
0.399
10.21
0.230
0.15730.033
1.19310.429
1.08510.153
1,009 10.052
0.041
0,067 0.041
0.25
0.134=0.109
0.513=0.662
0.089
0.288:0.3433
0.612:00.744
0.958=0.147
1.04240.048
0.217=0.074
0.222+0016
Table 3: Average MSE values (plus/minus one standard deviation) for the real-world experiments on the PACM point cloud over ten runs. The best is marked in bold red while the second best is in underline blue.
option
GNNSSnc
Spectral
Spectaa.RN
GPM
TranSync
CEMP,GCW
CHMP -SST
TAS
Trivial
0.010:00003
-0,000-0.000
-0.000=0.000
...000-0.000
-0.00000.000
-0,000-0.000
-0,000-0.000
2:249-00122
2.408-00.139
0.000
1.000:00.00
0.000:00.00
0.000:0.000
0.000:1.000
0.000:0.000
0.000=0.000
164010001
1.565
0,000 0.000
0.000
0,000 0.000
0,000
0,000:
1.221 10.779
1,160
0
0:000
0.000:0.000
0.000:0.800
0.000=0.800
0.000=0..00
0.000=0.000
0.000-0.000
1199:400400
1.176400.426
0.05
0.0051:0.011
0.003:00000
0.003:0.001
0.003:0.000
0.010:0:004
0.039:00008
0.002
2.46.10.1
2.468.00.11 130
0,08
0.000
00000-00.000
0.002:0.000
0.002-0.000
0.010
0.024-0.016
0.885 1.157
1.611 10011
1.543:0.051
0.03
0.004
1.00--11.000
0.003=00.000
0.003--0.000
0.009-0:004
0.05720.055
0.528 0.49
1182:07777
1. 1600200.5 753
0.05
0,003 0.001
0.0031 0.000
0,003 0.000
0,003 0.000
0.001
0.177
0.718 0.292
100 10.246
0.967 10,253
0.1
0.015-00:005
0.012:00.044
0.012:00.06
0.012:00.04
0.349-0:011
0.187=00. 1077
0.642
2. 1122+01150
2.546-+-0.1
0.1
0.010:00.001
2000100000
0.010:00.001
0.010:00.001
0.0440-011
0.145:20.00 031
0.490
00006
1. 1.56 0.042
0.1
0.012
0,010: 0.001
0,010 0.001
0,010: 0.001
0,055 0.005
0.298 103377
394 0.659
1.213
L 0.
0.1
0.010:00001
00001=000001
0.010=0..01
0.010=00.01
0.052
0.271
+3.431
L.77620.426
0.15
0.010:0.000
0.020:0.012
0.001:00.11
0.136.0.068
0.000
262:10.13 166
2,466 159
0.15
0.002
0.022 0.000
0.030:0.002
0,002
0,109:0:034
2,927 0,254
254
587 00064
0.5
0.15
0.321 00000
0.030 004
0.019:0.004
0.019:00004
O. 0.85
0. 116
2 2970=
0
0.524=0
0.13
0.000
1.002+-10001
0,000-0.001
0,030=00001
0. 01.34
2 2000 000
1.176200.426 427
0.2
0.012
0.00
0.51 20.018
10.19
0. 0.236220117 117
0. 546::2 167
2 1312
288 19
2.668.00.11 130
0.2
0.2
0.002=00000
0.037 0.07 0.003
0
0.032+000004
0,037 0.005
0.030-000003 0.003
0.030-00004
0.008:00.00
0.250:0.110
0.157=0845
0.872200 368
0.826 0.410
3 3.530+0224 0224
2.982 0,995
61000001
1100
1. 1.66-t L7170
1.565 1-0.44
0.2
0,030 0.002
0.03410.000 600
0.02100.002
0.33 10000
0.891100084
0. 0.6911002200 220
3.312 0295
0.957 0:99K100246
0.25
0,069-0.000 0.019
0,082-00.02
0.078- 0.125
0.389-001185
L.22500.224
0.513-0350
2.318+0.140
2.468-0.115
0.25
11.05
8.059-20.00
0.057
0.454:0 386
0.055
1.586
1.565
0.0501...00
8.05L10.00
0.005
0.049 0.009
0,005
34669 0,164
L 1.475
0.25
0.047:00.005
0.053-50.003
0.050
0.050:0.305
0.359:0.176
1.179:00442
0.238
1.181:40425
1.176:0.436
23

---

Published as a conference paper at ICLR 2024
Table 4: Average ANE values (plus/minus one standard deviation) for the real-world experiments on the PACM point cloud over ten runs. The best is marked in bold red while the second best is in underline blue.
option
GNNSSycc
Spectma
Spectral_RN
TranSync
CEMP_GCW
CEMP_MST
0.11810.05
0.000 0,000
0.000 0,000
0.000
0.000
0,000
10,00
0.000.00.00
0.000 0.000
_3.5700.000
1.655 10426
0
0.051 10.031
0.000:0.000
0.000:0.000
0,000
0.000000000
0.800110.000
0.0001100000
0.000:10.00
0.870=000099
0.785-10.020
0
3
0.048 00.034
0.000:0.000
0.000:0.000
0.000:0.000
0.000-10.000
0.000-0.000
0.000:0.000
0.645:0..96
0.590=003900
0
0.008 10.024
0.000 0.000
0.000 0.000
0.000 0.000
0,000 10,00
0.000:00000
0,000 00,000
0.657 00.23
0.631 20.233
0.1391000079
0:15410.066
1.65-1104426
0.055
0.71:11.288
0:102:00.488
0.121:00093
0.05
0.061:0.02
000031
0009900.000
0.026 0.007
0.028 0.0007
0.062 10.017
0.823
0.588: 10.310
0.540
0.597 309389
0.05
0.046-00021
0.02250.007
0.030=00.006
00:077
0.06
2291120.255
0.826+00422
0.699
0.671
0.1
1
0.116-0.027
0.072:0.039 0.039
0.04+00.039
0.661 1.19
0.220
0.896::1.22
1.326+0.710
1. 1.320=0.094
1684=00433
0.1
2
0.02-
0 0910220 375
0.053
0,088 0.063
0.210:00001
10077:1356
1 1,49920.55 537
0. 00.110
0.785
00000
0.144
0.1
0.016
0.1964000070
0401200320
1,470+055077
0.63220 391
0.597=0
0107-00014
000
0.05
0.010
0.220+0.185
0.639+0.383
1,41940.337
0.683-0
0.15
0006320063
0
01 1.59=00004
0.
0:301 230
0.51
1,31320.665
0
1655
0.15
2
0.002-0000
0
DJ 0. 382
0.232200078
0.789=0.458
2,096 523
01 043
0.
0.15
3
10.039 0.095
0.738 1.3 340
0.076 0,031
0.079
0.052
0.239 10.06
0.903.1 1.055
1 10.217
0.322 12222.222 0024
0.298 222
0.15
4
0.0022
0.094:0.016
0 0.060-000119
0.000
0.366-10.240
1,125 250
1,77510.355 338
D. 0:670:00200 237
0 223
0.2
0.189:0..00
0.096
0.199:0.000
0..9-00.77
0.937-11.219
1.52%=0.954
2.331 262
1.578=0.00
LA55
0.110100
10.313
0.2
0.036 4
0.84611 507
0.526-10875
0.336:10.124
0.87910.3338
1.852:101
0.633
10610
0.2
0000-0
0.016=0.020
0.807
DJ 0002-0.022
0.398:40.247
1.05940.303
1.952:0.435
0.6
0.672:20.279
0.25
0.29010.277
0.254 0.074
0.252 0.075
0,247 0.081
10.140
1.505 00.824
2,016 1006610.1110 10.194
1,391 10.09
1665 00426
(1.25
2
0.109
O. 0.142=00051
0.129 00,000
0.372=0.494
1.907=11.221
1.312=0.891
2.087=0.115
0.838=0.02 022
0.785-20.00
0.577=0.822 0.611
00,576
0,3133-0.26 268
0.871+00.06
1.213+0.728
1,941
0.779-0.55
0.782:0.560
0.102:0.002
0.35
0.888:00965
0.427::0.117
1.24810.662
1,923
0.648:02235
0.633-00222
(a) (R 0.05)
(b) (R 0.05)
(c) ERO (p 0.05)
(d) (RO. 0.05)
ERO, (p- 0.1)
(1) ERO. (p- 0.1)
(g) EROs (p 0.1)
(h) ERO 0.1)
ERO 0.15)
ii ERO2(p 0.15)
(k) EROs (p = 0.15)
(1 ERO = 0.15)
CNNN
Spectaa
SpectraLRN
GPM
TanSrue
CEMP.GOW
CEMPART
TAS
+
Trisial
Figure 6: MSE performance comparison on GNNSyne against baselines on angular synchronization (k 1) for ERO models. p is the network density and 17 is the noise level. Error bars indicate one standard deviation.
24

---

Published as a conference paper at ICLR 2024
(a) BAO (p 0.05)
(b) BAO2 0.05)
cc) BAOs (p 0.05)
(d BAO+ 0.05)
(e) BAO (p 0.1)
01 (AO= 0.1)
(g) (A 0.1)
(h) BAOa(p 0.1)
BAO: 0.15) Specttal
ii BAOx(p 0.15)
(k) BAOs (p 0.15)
() BAO+ (p 0.15)
GNNS
SpectraLR
CPM
TanSrue
CEMP GCW
MBM
TAS
Trisial
Figure 7: MSE performance comparison GNNSyne against baselines on angular synchronization (k = 1) for BAO models. p is the network density and v is the noise level. Error bars indicate one standard deviation.
(a) RGGO, (p = 0.05)
(b) RRGGG 0.05)
(c) RGGO: 0.05)
(d) RGGO. 0.05)
R 0.1)
RGGO2 0.1)
(g) RGGOs (p 0.1)
(h) RGGG. 0.1)
RGGO (p 0.15) Spectral
RGGO2 0.15)
(k) RGGO. 0.15)
(1) RGGO 0.15) Tisial
SpectraLRR
CPM
TrnSSrnc
CEMP.GOW
CEMPAT
TAS
Figure 8: MSE performance comparison GNNSync against baselines angular synchronization (k: = 1) for RGGO models. p is the network density and 1) is the noise level. Error bars indicate one standard deviation.
25

---

Published as a conference paper at ICLR 2024
(a) ERO: (p 0.05)
(b) EP = 0.05
(c) EROs (p = 0.05)
(d) ERO+ 0.05)
ERO (p 0.1)
(1) ERO, (p 0.1)
(g) EROs 0.1)
(h) ERO (p 0.1)
ii) (R 0.15) GNNSyac-cyde
ii (R 0.15)
(k) ERO: (p = 0.15)
() ERO. (p = 0.15)
GNNSync-upset
GNNSync-sum
Spectral
SpectraLRN
Trivial
Figure 9: MSE performance comparison on GNNSyne against baselines on sychroonnniaooonnn with A 2 for ERO models. p is the network density and rj is the noise level. Error bars indicate one standard deviation.
BAO: (p 0.05)
(b) BAO= (p 0.05)
(c) BAOs (p 0.05)
(d) BAO+ 0.05)
(e) BAO (p 0.1)
(0 BAO 0.1)
(g) (AOa(p = 0.1)
(h) BAO 0.1)
(i) Bp 0.15)
(i BAO2(P = 0.15)
(k) BAOa(p = 0.15)
()) BAO. = 0.15) Trivial
GNNSync-cyde
GNNSync-upeet
GNNSyne-sum
Spectral
SpectraLRNN
Figure 10: MSE performance comparison on GNNSync against baselines on k sychhronnizatoonn with k 2 for BAO models. p is the network density and 1) is the noise level. Error bars indicate one standard deviation.
26

---

Published as a conference paper at ICLR 2024
(a) RGGO (p 0.05)
(b) RGGO2 0.05)
(c) RGGGs 0.05)
(d) RGGO. 0.05)
(e) RGGO (p 0.1)
(1 (G 0.1)
RGGOss = 0.1)
(h) RGGO 0.1)
RGGO (p- = 0.15)
(i) RGGO2 = 0.15)
(k) RGGOs 0.15) Spectral
(1) RGGG. = 0.15) Trivial
GNNSyac-cyde
GNNSync-upeet
GNNSync-sum
SpectraLRN
Figure 11: MSE performance comparison on GNNSync against baselines on k sy-chrooonizttonnn with k 2 for RGGO models. is the network density and is the noise level. Error bars indicate one standard deviation.
(a) ERO: (p 0.05)
(b) ER 0.05
(c) ERO (p 0.05)
(d) ERO (p 0.05)
(e) ERO, (p 0.1)
(1) EROx (p 0.1)
(g) EROa(p (p = 0.1)
(h) ERO (p 0.1)
(i) ERO,(p 0.15)
(i ERO2(p = 0.15)
(k) ER = 0.15)
()) ERO.(p = 0.15)
GNNSync-cyde
GNNSync-upeet
GNNSync-sum
Spectral
SpectraLRN
Trivial
Figure 12: MSE performance comparison on GNNSync against baselines on k s-schrronizattinn with
k 3 for ERO models. p is the network density and is the noise level. is the network density and ? is the noise level. Error bars indicate one standard deviation.
27

---

Published as a conference paper at ICLR 2024
(a) BAO (p = 0.05)
(b) BAO2 (p 0.05)
(c) BAOs (p = 0.05)
(d) BAO+ 0.05)
(e) BAO (p 0.1)
(1 BAO (p 0.1)
(g) (A = 0.1)
(h) BAO (p 0.1)
(i) BAO: (p- 0.15)
i BP = 0.15)
(k) BAO= = 0.15)
() BAO+ = 0.15)
GNNSyac-cyde
GNNSync-upset
GNNSync-sum
Spectral
SpectraLRN
Trivial
Figure 13: MSE performance comparison on GNNSync against baselines on k s--ynchronnzationn with A 3 for BAO models. p is the network density and 17 is the noise level. Error bars indicate one standard deviation.
(a) RRGGO 0.05)
(b) RGGO2 0.05)
(c) RGGOs 0.05)
(d) RGGO. 0.05)
(e) RGGO (p- = 0.1)
(1) RGGO2 = 0.1)
RGGOs = 0.1)
(h) RGGG 0.1)
RGGO, = 0.15)
ii RGGOz = 0.15) (k) RGGO& 0.15)
(1) RGGG = 0.15) Trivial
GNNSync-cyde
GNNSync-upee
GNNSync-sum
Spectral
SpectraLRN
Figure 14: MSE performance comparison on GNNSync against baselines on k syshhhoonizatiion with
k = 3 for RGGO models. is the network density and is the noise level. Error bars indicate one standard deviation.
28

---

Published as a conference paper at ICLR 2024
(a) ERO: (p 0.05)
(b) (R 0.05
(c) EROs (p = 0.05)
(d) ERO (p 0.05)
(e) ERO (p 0.1)
(1) 2RO2 (p 0.1)
(g) EROs 0.1)
(h) ERO (P 0.1)
(i) ERO, 0.15) GNNSyac-cyde
ii) (R 0.15)
(k) ERO: = 0.15)
() ERO. (p = 0.15)
GNNSync-upeet
GNNSync-sum
Spectral
SpectraLRN
Trivial
Figure 15: MSE performance comparison on GNNSync against baselines on k sychhroroninnon with A 4 for ERO models. p is the network density and rj is the noise level. Error bars indicate one standard deviation.
(a) BAO: (p 0.05)
(b) BAO (p 0.05)
(c) BAOs (p 0.05)
(d) BAO (P 0.05)
(e) BAO (p- 0.1)
( BAO (p 0.1)
(g) (AOx(p = 0.1)
(h) BAO (P 0.1)
(i) BAO: (p 0.15)
(i BAO2(P = 0.15)
(k) BAO. = 0.15)
()) BAO. = 0.15) Trivial
GNNSync-cyde
GNNSync-upeet
GNNSyne-sun
Spectral
SpectraLRNN
Figure 16: MSE performance comparison on GNNSync against baselines on k s-nhhroonizztoonn with k 4 for BAO models. p is the network density and 1) is the noise level. Error bars indicate one standard deviation.
29

---

Published as a conference paper at ICLR 2024
(a) RGGO (p- 0.05)
(b) RGGG (p 0.05)
(c) RGGG (p 0.05)
(d) RGGO 0.05)
RGGO 0.1)
(1 RG 0.1)
RGGOs (p 0.1)
(h) RGGO. 0.1)
RGGG (p = 0.15)
RGGO2 = 0.15) (k) RGGOsssp 0.15)
(1) RRGGG+4p (p 0.15)
GNNSyne-cyde
GNNSync-upeet
GNNSyne-sum
Spectral
SpectraLRN
Trivial
Figure 17: MSE performance comparison GNNSyne against baselines on syncroonnnizaionnn with for RGGO models. p is the network density and r is the noise level. Error bars indicate one standard deviation.
30

---

Published as a conference paper at ICLR 2024
(a) GNNSyne, 77 =
(b) Spectral, 77 =
(c) Spectral_ RR,, 17
(d) GPM, =
(e) TranSync, fj = 0
(1) CEMP.GCW, 77
(g) CEMP.MST, 7)
(h) TAS. 17 =
(i) GNNSync, 1 = 0.05
( Spectral, n = 0.05
(k) Spectral_RN RN, n = 0.05
1) GPM, = 0.05
(m) TranSyne, 7 = 0.05 (n) CEMP GCW, 1 = 0.05 (o) CEMP MST, rj = 0.05
(p) TAS, 7 = 0.05
(q) GNNSyne, 7 =
(r) Spectral, 17 0.1
(8) Spectral = 0.1
(1) GPM. 7 =
(u) TranSyne, (v) CEMP.GCW... 7) = (w) CEMP CEMP.MST. 7
(x) TAS, 7
Figure 18: Result visualization for the Sensor Network Localization task on the U.S map using option "1" as ground-truth angles for low-noise input data. Red dots indicate ground truth locations and blue dots estimated city locations.
31

---

Published as a conference paper at ICLR 2024
(a) GNNSync, 7 = 0.15
(b) Spectral, 17 = 0.15
(c) Spectral_ RN, 7 = 0.15
(d) GPM, 7 0.15
(e) TranSyne, 7 = 0.15
(f) CEMP.GCW, 1) = 0.15 (g) CEMPLMST, 1j = 0.15
(h) TAS = 0.15
(i) GNNSyne, 1) 0.2
() Spectral, = 0.2
(k) Spectral RN, 17 = 0.2
(1) GPM, 7 = 0.2
(m) TranSync, 7 = 0.2
(n) CEMP GCW, 1) = 0.2 (0) CEMP MST, 17 = 0.2
(p) TAS, 7 = 0.2
(q) GNNSyne, 7 = 0.25
(r) Spectral, 17 = 0.25
(s) Spectral_Ra LRN, 1 = 0.25
(1 GPM, 7 = 0.25
(u) TranSyne, 7) 0.25 (v) CEMP GCW, 7 0.25 (w) CEMP MST, 7) = 0.25 (x) TAS, 7 0.25
Figure 19: Result visualization for the Sensor Network Localization task on the U.S map using option "I" as ground-truth angles for high-noise input data. Red dots indicate ground-truti locations and blue dots estimated city locations.
32

---

Published as a conference paper at ICLR 2024
(a) GNNSyne, 77 =
(b) Spectral, 77 =
(c) Spectral_ RR,, 17
(d) GPM, =
(e) TranSync, fj = 0
(1) CEMP.GCW, 7)
(g) CEMP CEMPLMST, 7)
(h) TAS. 17 =
(i) GNNSync, 1 = 0.05
( Spectral, n = 0.05
(k) Spectral n = 0.05
1) GPM, = 0.05
(m) TranSyne, 7 = 0.05 (n) CEMP GCW, 1 = 0.05 (o) CEMP MST, 17 = 0.05
(p) TAS, 77 = 0.05
(q) GNNSyne, 7 =
(r) Spectral, 7 0.1
(8) Spectral = 0.1
(1) GPM, 7 =
(u) TranSync, (v) CEMP.GCW....... 7/ = (w) CEMP MST, 7 =
(x) TAS, 7
Figure 20: Result visualization for the Sensor Network Localization task on the U.S map using option "2" as ground-truth angles for low-noise input data. Red dots indicate ground truth locations and blue dots estimated city locations.
33

---

Published as a conference paper at ICLR 2024
(a) GNNSyne, 7 = 0.15
(b) Spectral, 17 = 0.15
(c) Spectral_Ry 7 = 0.15
(d) GPM, 7 0.15
(e) TranSyne, 7 = 0.15 (f) CEMP .CWW, 1) = 0.15 (g) CEMP SSMP,MST,,, 1j = 0.15
(h) TAS, = 0.15
(i) GNNSyne, 7) 0.2
() Spectral, 0.2
(k) Spectral RN, 0.2
(1 GPM, 7 = 0.2
(m) TranSync, 7 = 0.2
(n) CEMP GCW, 1 = 0.2 (o) CEMP MST, 17 = 0.2
(p) TAS, 7 = 0.2
(q) GNNSyne, 7 = 0.25
(r) Spectral, 17 = 0.25
(s) Spectral 1 = 0.25
(1 GPM, 0.25
(u) TranSyne, 7) 0.25 (V) CEMP HCW.P.GWWW1. 7 0.25 (w) CEMP MST, 7 = 0.25
(x) TAS, 7 0.25
Figure 21: Result visualization for the Sensor Network Localization task on the U.S map using option "2" as ground-truth angles for high-noise input data. Red dots indicate ground-truti locations and blue dots estimated city locations.
34

---

Published as a conference paper at ICLR 2024
(a) GNNSyne, 77 =
(b) Spectral, 77 =
(c) Spectral_ RR,, 1j
(d) GPM, 7
(e) TranSync, fj = 0
(1) CEMP.GCW, 7)
(g) CEMP CEMP.MST, 7)
(h) TAS, 17 =
(i) GNNSync, 1 = 0.05
( Spectral, n = 0.05
(k) Spectral RN, n = 0.05
() GPM, = 0.05
(m) TranSyne, 7 = 0.05 (n) CEMP GCW, 1 = 0.05 (o) CEMP MST, 1 = 0.05
(p) TAS, 7 = 0.05
(q) GNNSyne, 7 =
(r) Spectral, 17 0.1
(8) Spectral = 0.1
(1) GPM, 7 = 0.1
(u) TranSyne, 0.1 (v) CEMP GCW, 7) = (w) CEMP CEMP_MST,1 7 =
(x) TAS, 7
Figure 22: Result visualization for the Sensor Network Localization task on the U.S map using option "3" as ground-truth angles for low-noise input data. Red dots indicate ground truth locations and blue dots estimated city locations.
35

---

Published as a conference paper at ICLR 2024
(a) GNNSyne, 7 = 0.15
(b) Spectral, 17 = 0.15
(c) Spectral_ RN, 7 0.15
(d) GPM, 7 = 0.15
(e) TranSyne, 7 = 0.15
(f) CEMP.GCW, 1) = 0.15 (g) CEMPLMST, 1j = 0.15
(h) TAS 7 = 0.15
(i) GNNSync, 1) 0.2
() Spectral, = 0.2
(k) Spectral RN, 17 = 0.2
(1) GPM, 7 = 0.2
(m) TranSync, 7 = 0.2
(n) CEMP GCW, 1 = 0.2 (0) CEMP MST, 17 = 0.2
(p) TAS, 7 = 0.2
(q) GNNSyne, 7 = 0.25
(r) Spectral, 17 = 0.25
(s) Spectral JRniaal_NN,,,, r = 0.25
(1 GPM, 0.25
(w) TranSyne, 7) 0.25 (V) CEMP MCM.P.GWW111 7j 0.25 (w) CEMP MST, 7) = 0.25 (x) TAS, 7 0.25
Figure 23: Result visualization for the Sensor Network Localization task on the U.S map using option "3" as ground-truth angles for high-noise input data. Red dots indicate ground-truti locations and blue dots estimated city locations.
36

---

Published as a conference paper at ICLR 2024
(a) GNNSyne, 77 =
(b) Spectral, 77 =
(c) Spectral_ RR,, 17 0
(d) GPM, =
(e) TranSync, fj 0
(1) CEMP.GCW, 7)
(g) CEMP CEMP.MST, 7)
(h) TAS. 17 =
(i) GNNSync, 1 = 0.05
( Spectral, n = 0.05
(k) Spectral_RN, n = 0.05
1) GPM, = 0.05
(m) TranSync, 7 = 0.05 (n) CEMP GCW, 1 = 0.05 (o) CEMP MST, r7 = 0.05
(p) TAS, 7 = 0.05
(q) GNNSyne, 7 =
(r) Spectral, 1) = 0.1
(8) Spectral_ = 0.1
(1 GPM, 7 = 0.1
(u) TranSync, (v) CEMP GCW, 7) (w) CEMP MST, 7 = (x) TAS, 7
Figure 24: Result visualization for the Sensor Network Localization task on the U.S map using option "4" as ground-truth angles for low-noise input data. Red dots indicate ground truth locations and blue dots estimated city locations.
37

---

Published as a conference paper at ICLR 2024
GNNSyne, 7 = 0.15
(b) Spectral, 17 = 0.15
(c) Spectral_Ra RN, 7 0.15
(d) GPM, 7 0.15
(e) TranSyne, 7 = 0.15
(f) CEMP.GCW, 1) = 0.15 (g) CEMP MSS. 1j = 0.15
(h) TAS = 0.15
(i) GNNSyne, 1) 0.2
( Spectral, 0.2
(k) Spectral RN, = 0.2
(1 GPM, 7 = 0.2
(m) TranSync, 7 = 0.2
(n) CEMP GCW, 1) = 0.2 (o) CEMP MST, 17 = 0.2
(p) TAS, 7 = 0.2
(q) GNNSyne, 7 = 0.25
(r) Spectral, 17 = 0.25
(s) Spectral_RN. RN, 1 0.25
(1 GPM, 0.25
(u) TranSyne, 7) 0.25 (v) CEMP GCW, 1) 0.25 (w) CEMP MST, 7) = 0.25 (x) TAS, 7 0.25
Figure 25: Result visualization for the Sensor Network Localization task on the U.S map using option "4" as ground-truth angles for high-noise input data. Red dots indicate ground-truti locations and blue dots estimated city locations.
38

---

Published as a conference paper at ICLR 2024
PX01
(a) GNNSync, 77 =
(b) Spectral, 77 =
(c) Spectral_ RN, 17 =
(d) GPM, 7=
(e) TranSync, fj = 0
(1) CEMP.GCW, 77 =
(g) DEMP.MST.1. 17 =
(h) TAS, 17 =
(i GNNSync, 7 = 0.05
① Spectral, 1 = 0.05
(k) Spectral_RN, n = 0.05
() GPM, = 0.05
PX11
PRO
PrO
(m) TranSync, 77 = 0.05
(n) CEMP GCW, 7 = 0.05 (o) CEMP MST, 1 = 0.05
(p) TAS, 77 = 0.05
PROM
PRO
PROM
(q) GNNSyne, 7 =
(r) Spectral, n = 0.1
(8) Spectral_RN 17 0.1
(1) GPM, = 0.1
(u) TranSyne, 7 = 0.1 (v) CEMP GCW, 7 (w) CEMP CEMP_MST, 7 = (x) TAS, 7 =
Figure 26: Result visualization for the Sensor Network Localization task on the PACM point cloud using option "1" as ground-truth angles for low-noise input data. Red dots indicate ground-truth locations and blue dots are estimated city locations.
39

---

Published as a conference paper at ICLR 2024
PAO
PROM
(a) GNNSymc, 7 = 0.15
(b) Spectral, 17 = 0.15
(c) Spectral_ RN, 7 0.15
(d) GPM, 7 0.15
HM
(e) TranSyne, 7 = 0.15 (f) CEMP_GCW, 1) = 0.15 (g) CEMP_MSTE 1j = 0.15
(h) TAS, = 0.15
PRO!
PR11
(i) GNNSyne, 1) 0.2
() Spectral, 0.2
(k) Spectral RN, 0.2
(1) GPM, 7 = 0.2
POOM
(m) TranSync, 7 = 0.2
(n) CEMP GCW, 1) = 0.2 (0) CEMP MST, 1 = 0.2
(p) TAS, 77 = 0.2
(q) GNNSyne, 7 = 0.25
(r) Spectral, 17 = 0.25
(s) Spectral_ RN, n 0.25
() GPM, = 0.25
(u) TranSyne, 7) 0.25 (v) CEMP GCW, 7 0.25 (w) CEMP DEMP.MST,1 7 = 0.25
(x) TAS, 7 = 0.25
Figure 27: Result visualization for the Sensor Network Localization task on the PACM point cloud using option "1" as ground-truth angles for high-noise input data. Red dots indicate ground-truth locations and blue dots estimated city locations.
40

---

Published as a conference paper at ICLR 2024
D.2 EXTENDED ABLATION STUDY RESULTS
Ablation study results are reported in Fig. 28 and 29 while the rest are omitted but could lead to the same conclusion. Note that for k 1, ablation study results are based using Leycle as the training loss function.
Improvements over all possible baselines when taking their output as input features for are reported in Fig. 30 31 and
32 where we omit results for 17 = 0.9 as in general all methods fall behind the trivial solution 1 0.9. We find that in most cases GNNSync could improve over baselines, and could do worse often only when all methods fall behind the trivial baseline.
To show the effect of linear combination of Leyele and Lupset. we empirically test Leyele + - with varying from O to 0.9; see Fig. (3 (the others are omitted but could lead to the same conclusion) for details. The performance for different choices of r do not vary significantly, providing further evidence that it suffices to simply pay attention to either of the two loss functions instead of their linear combination. The experiments also show that as the problem becomes harder (c.g. as the noise level increases and the network becomes sparser), smaller coefficient of Lupset (even zero) is preferred, which indicates that Leyele plays a more essential role the more challenging scenarios.
To assess the effect of fine-tuning (via projected gradient steps) over the baselines, we apply the same number of projected gradient descent steps as GNNSync to the comparative basclines and report the performance in Figures and 35| We observe that even when applying these fine-tuning steps, the baselines are usually beaten by our end-to-end trainable GNNSync pipeline.
(a) ERO, 0.05)
(b) (R 0.05
(c) EROg (p 0.05
(d) ERO. 0.05)
ERO: (p- 0.1)
ERO2 0.1)
(g) EROs (p 0.1)
(h) ERO.(p 0.1)
(i) ERO, (p- 0.15)
(i) ERO:(p = 0.15)
(k) EROs (p = 0.15)
(1 ERO, = 0.15)
Default
No Projected Gradient Steps
Not End-to-
Trainable {a.
Trivial
Figure 28: MSE performance comparison on GNNSyne variants on angular synchronization (A: 1) for ERO models. is the network density and is the noise level. Error bars indicate one standard deviation.
41

---

Published as a conference paper at ICLR 2024
(a) E (p 0.05)
(b) (p = 0.05
(c) EROa (p = 0.05)
(d) ERO. = 0.05)
(e) ERO (p- 0.1)
(f) ERO2 (p 0.1)
(g) EROs 0.1)
(h) ERO 0.1)
(i) ERO: (p- 0.15)
(i EROa(p 0.15)
(k) EROs 0.15)
()) ERO (p 0.15) Trivial
Default
Not End-to-Ean End
Trainable (a,)
No Projected Gradient Steps
Separate (H
"Spectral" for Input Features
Figure 29: MSE performance comparison on GNNSyne variants on s-synchronizationn with k 2 for ERO models. p is the network density and 1j the noise level. Error bars indicate one standard deviation.
(a) ERO, (p 0.05)
(b) ER 0.05
ERO. (p 0.05
(d) ERO. 0.05)
ERO (p- 0.1)
( ERO2(p 0.1)
EROx 0.1)
(h) ERO. 0.1)
(i) ERO: (p
0.15)
(i) ERO2(p 0.15)
(k) ERO: (p 0.15)
(1 ERO. (p 0.15) CEMP
Spectral
SpectraLRN
GPM
TranSync
CEMP .CWW
TAS
Figure 30: MSE performance improvement on GNNSync over variants on angular synchronization (k 1) for ERO models. p is the network density and r7 is the noise level. Error bars indicate one standard deviation.
42

---

Published as a conference paper at ICLR 2024
BAO (p 0.05)
bb) 2A0 (p 0.05
(c) BAA0 (p 0.05)
BAO+ 0.05)
BAO (p 0.1)
1 BAO (p- = 0.1)
g BAO = 0.1)
(h) BAO+ = 0.1)
(i) BAO (p- 0.15)
(i) BAO2(P 0.15)
(k) BAOs (p = 0.15)
() BAO. = 0.15) CEMPMST
Spectral
SpectraLRN
GPM
TranSync
CEMP .CCW
TAS
Figure 31: MSE performance improvement on GNNSyne over variants on angular synchronization (k: 1) for BAO models. is the network density and v is the noise level. Error bars indicate one standard deviation.
RGGO, (p- 0.05)
(b) ( 0.05)
(c) RGGGo 0.05
(d) RGGO. 0.05)
(c) RGGG (p 0.1)
( 2GG02 0.1)
g RGGG3 = 0.1)
(h) RGGG 0.1)
RGGO (p = 0.15) SpectraLRN
(i) RGGO2 = 0.15)
(k) RGGOs = 0.15)
(1) RGGO = 0.15)
Spectral
GPM
TranSync
CEMP _GCW
CEMP MST
TAS
Figure 32: MSE performance improvement on GNNSyne over variants on angular synchronization (k: 1) for RGGO models. is the network density and is the noise level. Error bars indicate one standard deviation.
43

---

Published as a conference paper at ICLR 2024
(a) ERO: (p- 0.05)
(b) (P 0.05
(c) EROs (p 0.05)
(d) ERO 0.05)
(e) ERO (p 0.1)
(f) ERO2 (p 0.1)
g FRO0s = 0.1)
(h) ERO. = 0.1)
ii ERO, (p- 0.15)
(i) ERO2(D 0.15)
(k) ERO, (p = 0.15)
(1 ERO. (p = 0.15)
7 0.0 (GNNSynC-cycee
== 0.3
0.7
GNNSync-upset
r 0.1
T= 0.5
7= 0.9
Trivial
Figure 33: MSE comparison on GNNSync variants using as loss Lupset + Leyele with different coefficients т. on sycyyooooniittionn with for ERO models. is the network density and is the noise level. Error bars indicate one standard deviation.
(a) ERO, (p- 0.05)
(b) (R 0.05
(c) EROs (p 0.05
(d) ERO. 0.05)
ERO, (p- 0.1)
ERO. (p 0.1)
(g) ERO 0.1)
(h) ERO.(P 0.1)
EROi( 0.15) Spectra
(i) ERO2(p (p = 0.15)
(k) EROs(p = 0.15)
(1) ERO,(p = 0.15)
CNN
SpectraLRN
GPM
TanSrue
CEMP.GOW
CEMPABT
TAS
Trisial
Figure 34: MSE performance comparison on GNNSync against fine-tuned baselines on angular synchronization (k 1) for ERO models. p the network density and r is the noise level. Error bars indicate one standard deviation.
44

---

Published as a conference paper at ICLR 2024
(a) ERO, (p 0.05)
(b) (R 0.05
(c) ERO, (p 0.05
(d) ERO, 0.05)
(c) ERO, (p- 0.1)
(1) ERO2 0.1)
g ERO: (p = 0.1)
(h) ERO+ (p 0.1)
ii ERO, (p 0.15)
ii) ERO2(p 0.15)
(k) ERO (p 0.15) Spectral
(1 ERO. (p 0.15) Trivial
GNNSync-cyde
GNNSync-upset
GNNSync-sum
SpectraLRN
Figure 35: MSE performance comparison on GNNSync against fine-tuned baselines on k -y-ychrooizzaionn with k = 2 for ERO models. is the network density and is the noise level. Error bars indicate one standard deviation.
45


Reviews:
[{"review_id": "lW3PXmJBqC", "reviewer": "Reviewer_BzAL", "summary": "This paper considers the problem of angular synchronization, in which the goal is to compute one or multiple sets of angles given noisy measurements of their differences , which are given as a weighted directed graph.  The output is given mod $2\\pi$ and up to an additive constant angle. The main contribution is in the case that the measurements are noisy. These errors lead to inconsistencies in the sum of angles that belong to directed cycles of the graph, which can have non-zero due to the noise. The loos function that is used to apply a projected gradient descent algorithm encodes these inconsistencies and thus the gradient descent algorithm is trying to minimize them. Furthermore, the authors have implemented the algorithm and run experiments on synthetic data and under various noise models to demonstrate the algorithm’s accuracy and robustness to noise in comparison with prior work.", "questions": "In the problem definition, the phrase “at most one of $A_{i,j}$ $A_{j,i}$ can be non-zero by construction” does not seem to be consistent with the definition above. Can you clarify?", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The proposed algorithms outperform existing ones in the literature for high levels of noise.", "weaknesses": "The paper doesn’t seem to have a lot of technical novelty and depth.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uzvOLI73hx", "reviewer": "Reviewer_UofK", "summary": "This paper proposes a training framework (GNNSYNC) that incorporates directed graph neural networks to address the classical angular synchronization problem and its extended k-synchronization variant. Specifically, a directed GNN is first applied to learn \nnode embeddings which are used to generate an initial guess.  Then, projected gradient steps are applied to refine the solution. \nFinally, the additional hyper parameters such as the feature matrix are learned by minimizing loss functions based on estimation error and cycle consistency. The proposed methods are evaluated by numerical experiments on synthetic and real datasets.", "questions": "1. It seems GNNSYNC itself is a complicated framework with many components. I am wondering if every component is necessary for it to solve the concise angular synchronization problem. Could you please also illustrate why the proposed method works well in high noise regimes while the other methods do not?\n\n2. I would appreciate it if the authors could justify that the proposed method is exactly better than the standard method with fine-tuning (by using either the standard log-likelihood function or the newly designed loss functions.)", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper claims that the proposed method is robust to the high noise level. \n2. The paper devises new loss functions (upset/cycle) that allow to apply GNN techniques.\n3. The paper extends the method to a more challenging heterogeneous setting.", "weaknesses": "1. While the paper claims that GNNSYNC is a theoretically grounded trainable framework. No theory is provided under any noise assumptions regarding 1) Can this method converge? 2) What kind of guarantee do we have (e.g. How close the solution provided by the algorithm is to the ground truth). While for standard algorithms such as GPM, we have well-established theoretical guarantees for certain types of noise.\n\n2. While the paper performs extensive experiments, the comparison with the baseline under high noise level seems not convincing. When we have a certain noise level, the standard way is to first provide an initial guess by solving a generalized eigenvalue problem, then projecting to the SO(2) space and aligning with anchors (if they exist). Finally, Riemannian/projected gradient descent is used to finetune the solution by minimizing a loss function (which can be adjusted based on the noise level). It seems GNNSYNC consists of multiple stages while there is no further fine-tuning steps for the baseline methods. \n\nMinors\n* The paper mentions that the motivation for k-synchronization is practically interesting because of some applications in structural biology, but it seems no experiments are conducted on biological applications. Also, even the 'real-world' dataset is perturbed artificially, which makes it not easy to see if the method can generalize well.\n* As mentioned by the authors, GNNSYNC shares many similarities with the GNNRank framework.\n* Currently, GNNSYNC is limited to SO(2) group.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NXzdYu8D9j", "reviewer": "Reviewer_LD2r", "summary": "This paper studies the angular synchronization problem. It proposes GNNSync, which is a trainable framework using directed graph neural networks, to solve the problem. It also comes up with a new loss function to encode synchronization objectives. Numerical experiments are conducted to validate the superiority and robustness of GNNSync.", "questions": "1. The loss function (5) incorporates mod and min operation inside. Could the authors please clarify how to calculate the gradient of this loss?\n\n2. Please clarify how to conduct projection in line 7 of Algorithm 1. Does the projection have a closed-form? How expensive is this projection step?\n\n3. Why do you need to conduct several steps of projection per round?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. It incorporates the inductive biases of classical estimators within the design of GNNSync and casts the angular synchronization problem as a theoretically-grounded directed graph learning task.\n\n2. It proposes a novel training loss that exploits cycle consistency to help disambiguate unknown angles.", "weaknesses": "It is unclear how to train GNNSync since the uncommon loss function in (5) is not smooth.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oxxPnNLCDG", "reviewer": "Reviewer_tjS3", "summary": "The paper addresses the problem of angular synchronization, which involves estimating a set of unknown angles from noisy measurements of their pairwise offsets. This problem appears in various applications, such as sensor network localization, phase retrieval, and distributed clock synchronization. The paper also extends the problem to a heterogeneous setting, named $k$-synchronization, where the goal is to estimate multiple groups of angles simultaneously from noisy observations.\n\nTo overcome the poor performance of existing methods in high-noise regimes, the authors propose GNNSync, a novel framework based on directed GNNs. The framework is end-to-end trainable and incorporates theoretically-grounded techniques to improve robustness to noise.", "questions": "The authors mentioned that extending the current GNN-based framework from SO(2) to more general groups may introduce several challenges and complexities. I would like the authors to elaborate a bit on the potential difficulties in generalizing the current method.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The authors introduced GNNSync, a GNN-based method designed specifically for the angular synchronization problem and its heterogeneous extension, $k$-synchronization.\n- I believe the main contribution of this paper resides in the proposal of new loss functions that encode synchronization objectives, with a particular focus on a cycle loss function that downweights noisy observations and enforces cycle consistency.\n- There is extensive experimental validation for the proposed method, demonstrating that GNNSync outperforms existing state-of-the-art algorithms, especially in high noise scenarios, across various synthetic and real-world datasets.", "weaknesses": "I do not see significant weakness in this paper. In some cases regarding the performance of the proposed method, particularly in the case of BAO, where its performance does not significantly outperform the baseline methods. Would the authors be able to elaborate a bit on that?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)