# Practical and Performant Enhancements for Maximization of Algebraic Connectivity

arXiv: https://arxiv.org/abs/2511.08694 · HTML: https://mlsanity.com/paper/2511.08694/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 35 references that are in the map.
- First posted on arXiv 11 Nov 2025.

## Builds on (most cited first, 12 of 12)

- [The Replica Dataset: A Digital Replica of Indoor Spaces](https://mlsanity.com/paper/1906.05797/) (2019)
- [SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group](https://mlsanity.com/paper/1612.07386/) (2016)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Linearly Convergent Frank-Wolfe with Backtracking Line-Search](https://mlsanity.com/paper/1806.05123/) (2018)
- [Attention and Anticipation in Fast Visual-Inertial Navigation](https://mlsanity.com/paper/1610.03344/) (2016)
- [Geometry-based Graph Pruning for Lifelong SLAM](https://mlsanity.com/paper/2110.01286/) (2021)
- [Spectral Measurement Sparsification for Pose-Graph SLAM](https://mlsanity.com/paper/2203.13897/) (2022)
- [Submodular Optimization for Keyframe Selection & Usage in SLAM](https://mlsanity.com/paper/2410.05576/) (2024)
- [Accelerating Certifiable Estimation with Preconditioned Eigensolvers](https://mlsanity.com/paper/2207.05257/) (2022)
- [LiDAR Inertial Odometry And Mapping Using Learned Registration-Relevant Features](https://mlsanity.com/paper/2410.02961/) (2024)
- [Fusing Odometry, UWB Ranging, and Spatial Detections for Relative Multi-Robot Localization](https://mlsanity.com/paper/2304.06264/) (2023)
- [MAC: Graph Sparsification by Maximizing Algebraic Connectivity](https://mlsanity.com/paper/2403.19879/) (2024)

## Abstract (arXiv)

Long-term state estimation over graphs remains challenging as current graph estimation methods scale poorly on large, long-term graphs. To address this, our work advances a current state-of-the-art graph sparsification algorithm, maximizing algebraic connectivity (MAC). MAC is a sparsification method that preserves estimation performance by maximizing the algebraic connectivity, a spectral graph property that is directly connected to the estimation error. Unfortunately, MAC remains computationally prohibitive for online use and requires users to manually pre-specify a connectivity-preserving edge set. Our contributions close these gaps along three complementary fronts: we develop a specialized solver for algebraic connectivity that yields an average 2x runtime speedup; we investigate advanced step size strategies for MAC's optimization procedure to enhance both convergence speed and solution quality; and we propose automatic schemes that guarantee graph connectivity without requiring manual specification of edges. Together, these contributions make MAC more scalable, reliable, and suitable for real-time estimation applications.