代数連結性最大化のための実用的かつ高性能な拡張
Practical and Performant Enhancements for Maximization of Algebraic Connectivity
グラフ推定のためのスペクトラルグラフ疎化手法MACを高速化し、自動エッジ選択を可能にすることで、リアルタイム推定への適用を容易にした。
詳しい要約
1. どんなもの？
2. 先行研究と比べてどこがすごい？
3. 技術・手法の肝は？
4. どうやって有効だと検証した？
5. 議論はある？
6. 次に読むべき論文は？
※ AIが要旨から生成した要約です。正確性は原文をご確認ください。
著者: Leonard Jung, Alan Papalia, Kevin Doherty, Michael Everett
分類: cs.RO, cs.LG
原文アブストラクト
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.
関連論文
- Δ探索を用いた部分グラフ抽出問題の解法グラフ最適化
