Practical and Performant Enhancements for Maximization of Algebraic Connectivity
Leonard Jung, Alan Papalia, Kevin Doherty, Michael Everett
AI summary
Problem
Long-term robotic state estimation suffers from computationally intractable graph growth, and the state-of-the-art MAC sparsification algorithm is too slow for online use while requiring manual pre-specification of a connectivity-preserving edge set.
Approach
The authors develop a numerically conditioned solver for the Fiedler value using shift-invert Krylov methods, evaluate Frank-Wolfe optimization step sizes, and introduce automatic heuristics to guarantee graph connectivity without manual edge specification.
Key results
- Specialized Fiedler value solver reduces computation time by up to 96% compared to general-purpose methods
- Decaying step size strategy for Frank-Wolfe optimization achieves the best convergence speed and solution quality
- Automatic backbone specification and connectivity-preserving rounding eliminate manual edge pre-specification
- Demonstrated scalability and improved algebraic connectivity across synthetic and real-world PGO, SNL, and SfM datasets
Why it matters
Enables scalable, real-time graph sparsification for long-term autonomous robotics, SLAM, and pose graph optimization applications.
Abstract
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, max- imizing 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. Code: https://github.com/neu-autonomy/MACpp