Eigenvector synchronization, graph rigidity and the molecule problem

DOI10.1093/IMAIAI/IAS002MaRDI QIDQ2869799zbMATH OpenOpenAlexWikidataFDO

Authors Mihai Cucuringu, A. Singer, David Cowburn

Publication date 6 January 2014

Published in Information and Inference (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.3304, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.387.6835

zbMATH Keywords

distance geometrydivide and conquereigenvectorsgraph realizationrigidity theorySDPspectral graph theorysynchronizationthe molecule problem

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10) Semidefinite programming (90C22) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10)

Abstract: The graph realization problem has received a great deal of attention in recent years, due to its importance in applications such as wireless sensor networks and structural biology. In this paper, we extend on previous work and propose the 3D-ASAP algorithm, for the graph realization problem in $mathbb{R}^3$, given a sparse and noisy set of distance measurements. 3D-ASAP is a divide and conquer, non-incremental and non-iterative algorithm, which integrates local distance information into a global structure determination. Our approach starts with identifying, for every node, a subgraph of its 1-hop neighborhood graph, which can be accurately embedded in its own coordinate system. In the noise-free case, the computed coordinates of the sensors in each patch must agree with their global positioning up to some unknown rigid motion, that is, up to translation, rotation and possibly reflection. In other words, to every patch there corresponds an element of the Euclidean group Euc(3) of rigid transformations in $mathbb{R}^3$, and the goal is to estimate the group elements that will properly align all the patches in a globally consistent way. Furthermore, 3D-ASAP successfully incorporates information specific to the molecule problem in structural biology, in particular information on known substructures and their orientation. In addition, we also propose 3D-SP-ASAP, a faster version of 3D-ASAP, which uses a spectral partitioning algorithm as a preprocessing step for dividing the initial graph into smaller subgraphs. Our extensive numerical simulations show that 3D-ASAP and 3D-SP-ASAP are very robust to high levels of noise in the measured distances and to sparse connectivity in the measurement graph, and compare favorably to similar state-of-the art localization algorithms.

Recommendations

• ASAP: an eigenvector synchronization algorithm for the graph realization problem
• A survey and evaluation of graph realization algorithms
• A Distributed SDP Approach for Large-Scale Noisy Anchor-Free Graph Realization with Applications to Molecular Conformation
• Localization from incomplete noisy distance measurements
• A remark on global positioning from local distances

Cited in

(28)

• Spectral conditions for graph rigidity in the Euclidean plane
• An extension of the angular synchronization problem to the heterogeneous setting
• Barvinok's naive algorithm in distance geometry
• Group synchronization on grids
• Diagonally dominant programming in distance geometry
• ASAP: an eigenvector synchronization algorithm for the graph realization problem
• Lagrangian duality in complex pose graph optimization
• A remark on global positioning from local distances
• Embedding Riemannian manifolds by the heat kernel of the connection Laplacian
• A survey of structure from motion
• Graph connection Laplacian and random matrices with random blocks
• Near-optimal bounds for phase synchronization
• Rigid graph compression: motif-based rigidity analysis for disordered fiber networks
• Concentration of the Kirchhoff index for Erdős-Rényi graphs
• Ranking and synchronization from pairwise measurements via SVD
• Rigidity percolation in disordered 3D rod systems
• A survey and evaluation of graph realization algorithms
• Global registration of multiple point clouds using semidefinite programming
• Orthogonal Trace-Sum Maximization: Tightness of the Semidefinite Relaxation and Guarantee of Locally Optimal Solutions
• Graph connection Laplacian methods can be made robust to noise
• Spectral radius conditions for the rigidity of graphs
• Local2global: a distributed approach for scaling representation learning on graphs
• A unified approach to synchronization problems over subgroups of the orthogonal group
• Multi-dimensional scaling from \(K\)-nearest neighbourhood distances
• Non-degenerate rigid alignment in a patch framework
• Nonconvex landscapes for \(\mathbf{Z}_2\) synchronization and graph clustering are benign near exact recovery thresholds
• Dynamic angular synchronization under smoothness constraints
• Sparsification of the regularized magnetic Laplacian with multi-type spanning forests

Describes a project that uses

Uses Software

• DISCO

This page was built for publication: Eigenvector synchronization, graph rigidity and the molecule problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2869799)