Robust Angular Synchronization via Directed Graph Neural Networks

• URL: http://arxiv.org/abs/2310.05842v2
• Date: Mon, 12 Feb 2024 18:40:40 GMT
• Title: Robust Angular Synchronization via Directed Graph Neural Networks
• Authors: Yixuan He, Gesine Reinert, David Wipf, Mihai Cucuringu
• Abstract summary: GNNSync is a theoretically-grounded end-to-end trainable framework using directed graph neural networks. GNNSync attains competitive, and often superior, performance against a comprehensive set of baselines for the angular synchronization problem.
• Score: 22.343880231555463
• License: http://creativecommons.org/licenses/by/4.0/
• 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 \;\mbox{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.

Related papers

• Higher-Order Group Synchronization [3.376269351435396]
  Group synchronization is the problem of determining reliable global estimates from noisy local measurements on networks.<n>We introduce a novel higher-order group synchronization problem which operates on a hypergraph.<n>We show potential advantages of our method through numerical experiments.
  arXiv  Detail & Related papers  (2025-05-28T03:37:10Z)
• Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity [92.1840862558718]
  Ringmaster ASGD achieves optimal time complexity under arbitrarily heterogeneous computation times. This makes it the first Asynchronous SGD method to meet the theoretical lower bounds for time complexity in such scenarios.
  arXiv  Detail & Related papers  (2025-01-27T16:07:26Z)
• Dual-Frequency Filtering Self-aware Graph Neural Networks for Homophilic and Heterophilic Graphs [60.82508765185161]
  We propose Dual-Frequency Filtering Self-aware Graph Neural Networks (DFGNN) DFGNN integrates low-pass and high-pass filters to extract smooth and detailed topological features. It dynamically adjusts filtering ratios to accommodate both homophilic and heterophilic graphs.
  arXiv  Detail & Related papers  (2024-11-18T04:57:05Z)
• Federated Contextual Cascading Bandits with Asynchronous Communication and Heterogeneous Users [95.77678166036561]
  We propose a UCB-type algorithm with delicate communication protocols. We give sub-linear regret bounds on par with those achieved in the synchronous framework. Empirical evaluation on synthetic and real-world datasets validates our algorithm's superior performance in terms of regrets and communication costs.
  arXiv  Detail & Related papers  (2024-02-26T05:31:14Z)
• Towards Understanding the Generalizability of Delayed Stochastic Gradient Descent [63.43247232708004]
  A gradient descent performed in an asynchronous manner plays a crucial role in training large-scale machine learning models. Existing generalization error bounds are rather pessimistic and cannot reveal the correlation between asynchronous delays and generalization. Our theoretical results indicate that asynchronous delays reduce the generalization error of the delayed SGD algorithm.
  arXiv  Detail & Related papers  (2023-08-18T10:00:27Z)
• Neural Inverse Kinematics [72.85330210991508]
  Inverse kinematic (IK) methods recover the parameters of the joints, given the desired position of selected elements in the kinematic chain. We propose a neural IK method that employs the hierarchical structure of the problem to sequentially sample valid joint angles conditioned on the desired position.
  arXiv  Detail & Related papers  (2022-05-22T14:44:07Z)
• AEGNN: Asynchronous Event-based Graph Neural Networks [54.528926463775946]
  Event-based Graph Neural Networks generalize standard GNNs to process events as "evolving"-temporal graphs. AEGNNs are easily trained on synchronous inputs and can be converted to efficient, "asynchronous" networks at test time.
  arXiv  Detail & Related papers  (2022-03-31T16:21:12Z)
• Learning Iterative Robust Transformation Synchronization [71.73273007900717]
  We propose to use graph neural networks (GNNs) to learn transformation synchronization. In this work, we avoid handcrafting robust loss functions, and propose to use graph neural networks (GNNs) to learn transformation synchronization.
  arXiv  Detail & Related papers  (2021-11-01T07:03:14Z)
• Decentralized Optimization with Heterogeneous Delays: a Continuous-Time Approach [6.187780920448871]
  We propose a novel continuous-time framework to analyze asynchronous algorithms. We describe a fully asynchronous decentralized algorithm to minimize the sum of smooth and strongly convex functions.
  arXiv  Detail & Related papers  (2021-06-07T13:09:25Z)
• An extension of the angular synchronization problem to the heterogeneous setting [8.391320712953553]
  We find a generalization to the setting where there exist $k$ unknown groups of angles $theta_l,1, dots,theta_l,n$, for $l=1,dots,k$. This problem arises in a variety of applications, including computer vision, time synchronization of distributed networks, and ranking from preference relationships.
  arXiv  Detail & Related papers  (2020-12-29T20:29:10Z)
• DS-Sync: Addressing Network Bottlenecks with Divide-and-Shuffle Synchronization for Distributed DNN Training [15.246142393381488]
  We present a novel divide-and-shuffle synchronization (DS-Sync) to realize communication efficiency without sacrificing convergence accuracy for distributed DNN training. We show that DS-Sync can achieve up to $94%$ improvements on the end-to-end training time with existing solutions while maintaining the same accuracy.
  arXiv  Detail & Related papers  (2020-07-07T09:29:01Z)
• Event-based Asynchronous Sparse Convolutional Networks [54.094244806123235]
  Event cameras are bio-inspired sensors that respond to per-pixel brightness changes in the form of asynchronous and sparse "events" We present a general framework for converting models trained on synchronous image-like event representations into asynchronous models with identical output. We show both theoretically and experimentally that this drastically reduces the computational complexity and latency of high-capacity, synchronous neural networks.
  arXiv  Detail & Related papers  (2020-03-20T08:39:49Z)
• Fully Asynchronous Policy Evaluation in Distributed Reinforcement Learning over Networks [14.636457985379746]
  This paper proposes a emphfully asynchronous scheme for the policy evaluation problem of distributed reinforcement learning (DisRL) over directed peer-to-peer networks. Without waiting for any other node of the network, each node can locally update its value function at any time by using (possibly delayed) information from its neighbors.
  arXiv  Detail & Related papers  (2020-03-01T08:12:08Z)
• Synchronization in 5G: a Bayesian Approach [0.0]
  We propose a hybrid approach to synchronize large scale networks. In particular, we draw on Kalman Filtering (KF) along with time-stamps generated by the Precision Time Protocol (PTP) for pairwise node synchronization.
  arXiv  Detail & Related papers  (2020-02-28T11:27:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.