Spectral Graph Theoretic Methods for Enhancing Network Robustness in Robot Localization
This paper addresses the optimization of edge-weighted networks by maximizing algebraic connectivity to enhance network robustness. Motivated by the need for precise robot position estimation in cooperative localization and pose-graph sparsification in Simultaneous Localization and Mapping (SLAM), the algebraic connectivity maximization problem is formulated as a Mixed Integer Semi-Definite Program (MISDP), which is NP-hard. Leveraging spectral graph theoretic methods, specifically Cheeger's inequality, this work introduces novel "Cheeger cuts" to strengthen and efficiently solve medium-scale MISDPs. Further, a new Mixed Integer Linear Program (MILP) is developed for efficiently computing Cheeger cuts, implemented within an outer-approximation algorithm for solving the MISDP. A greedy k-opt heuristic is also presented, producing high-quality solutions that serve as valid lower bounds for Cheeger cuts. Comprehensive numerical analyses demonstrate the efficacy of strengthened cuts via substantial improvements in run times on synthetic and realistic robot localization datasets.
Code (0)
등록된 구현이 없습니다.
Tasks
Simultaneous Localization and MappingvalidSimilar Papers 제목 키워드 기반
Masked Spatial-Spectral Autoencoders Are Excellent Hyperspectral Defenders
Deep learning methodology contributes a lot to the development of hyperspectral image (HSI) analysis community. However, it also makes HSI analysis systems vulnerable to adversarial attacks. To this end, we propose a mas…
Adversarial DefenseLearning TheorySelf-Supervised LearningGARNET: A Spectral Approach to Robust and Scalable Graph Neural Networks
Graph neural networks (GNNs) have been increasingly deployed in various applications that involve learning on non-Euclidean data. However, recent studies show that GNNs are vulnerable to graph adversarial attacks. Althou…
Adversarial RobustnessGraph EmbeddingRobust spectral clustering using LASSO regularization
Cluster structure detection is a fundamental task for the analysis of graphs, in order to understand and to visualize their functional characteristics. Among the different cluster structure detection methods, spectral cl…
ClusteringStochastic Block ModelEvenNet: Ignoring Odd-Hop Neighbors Improves Robustness of Graph Neural Networks
Graph Neural Networks (GNNs) have received extensive research attention for their promising performance in graph machine learning. Despite their extraordinary predictive accuracy, existing approaches, such as GCN and GPR…
Node ClassificationDesign Your Own Universe: A Physics-Informed Agnostic Method for Enhancing Graph Neural Networks
Physics-informed Graph Neural Networks have achieved remarkable performance in learning through graph-structured data by mitigating common GNN challenges such as over-smoothing, over-squashing, and heterophily adaption. …