提升图估计性能的快速连通性优化方法
Practical and Performant Enhancements for Maximization of Algebraic Connectivity
- 设计专用求解器，使算法平均提速2倍
- 改进步长策略，加速收敛并提高解质量
- 实现无需人工指定边的自动连通保障
长期图上的状态估计算法因现有图稀疏化方法在大规模、长时间图上扩展性差而面临挑战。本文针对当前最先进的最大化代数连通性（MAC）稀疏化方法进行改进，该方法通过最大化代数连通性这一与估计误差直接相关的谱图特性来保持估计性能。然而，MAC在在线应用中仍计算开销大，且需手动预设连通性保持边集。为此，本文从三个互补方向推进：开发专用求解器，实现平均2倍的运行速度提升；研究先进的步长策略，增强优化过程的收敛速度与解质量；提出无需人工指定边的自动连通保障机制。这些改进使MAC更具可扩展性、可靠性，适用于实时估计场景。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。