論文の概要: Practical and Performant Enhancements for Maximization of Algebraic Connectivity
- arxiv url: http://arxiv.org/abs/2511.08694v1
- Date: Thu, 13 Nov 2025 01:02:22 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-13 22:34:54.195763
- Title: Practical and Performant Enhancements for Maximization of Algebraic Connectivity
- Title（参考訳）: 代数接続性の最大化のための実用的・高性能化
- Authors: Leonard Jung, Alan Papalia, Kevin Doherty, Michael Everett,
- Abstract要約: 我々は,平均2倍のランタイム高速化を実現する,代数接続のための特殊解法を開発した。
エッジを手動で指定することなくグラフ接続を保証する自動スキームを提案する。
- 参考スコア（独自算出の注目度）: 7.054572089717147
- License: http://creativecommons.org/licenses/by/4.0/
- 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, 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.
- Abstract（参考訳）: グラフ上での長期状態推定は、現在のグラフ推定手法が大規模な長期グラフ上では不十分であるため、依然として困難である。
これを解決するために、我々は現在最先端のグラフスペーシフィケーションアルゴリズムを推進し、代数接続性(MAC)を最大化する。
MACは、推定誤差に直接接続するスペクトルグラフ特性である代数接続を最大化することにより、推定性能を維持するスペーシフィケーション法である。
残念ながら、MACはオンライン利用には計算的に禁止されており、ユーザーは手動で接続性を保存するエッジセットを指定する必要がある。
我々は,平均2倍のランタイム高速化をもたらす代数接続のための特別な解法を開発し,MACの最適化手順の高度なステップサイズ戦略を調査して収束速度と解品質を両立させるとともに,エッジのマニュアル仕様を必要とせずにグラフ接続を保証する自動スキームを提案する。
これらの貢献によりMACはよりスケーラブルで信頼性が高く、リアルタイムな推定アプリケーションに適している。
関連論文リスト
- MAC: An Efficient Gradient Preconditioning using Mean Activation Approximated Curvature [7.512116180634991]
KFACのようなニューラルネットワークをトレーニングするための2次最適化手法は、損失ランドスケープの曲率情報を活用することにより、優れた収束性を示す。
我々は、KFACで使用される階層式フィッシャー情報行列(FIM)を構成する2つの成分について分析する。
そこで我々は, MAC という計算効率のよい最適化手法を提案する。
我々の知る限り、MACは、トランスフォーマーで使用される注目層のFIMにクロネッカー分解を適用し、注意スコアを事前条件に明示的に統合する最初のアルゴリズムである。
論文 参考訳（メタデータ） (2025-06-10T05:38:04Z) - A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
提案手法では,Groverをベースとした進化的枠組みと分割・分散原理を用いた量子遺伝的アルゴリズム(QGA)を提案する。
完全グラフ上では、提案手法は真に最適なMaxCut値を一貫して達成し、セミデフィニティプログラミング(SDP)アプローチより優れている。
ErdHos-R'enyiランダムグラフでは、QGAは競合性能を示し、SDP結果の92-96%で中央値の解が得られる。
論文 参考訳（メタデータ） (2025-01-02T05:06:16Z) - Graph-Mamba: Towards Long-Range Graph Sequence Modeling with Selective
State Spaces [4.928791850200171]
グラフネットワークにおける長期コンテキストモデリングを強化する最初の試みであるGraph-Mambaを紹介する。
グラフ中心のノード優先順位付けと置換戦略を定式化し、文脈認識推論を強化する。
10のベンチマークデータセットの実験により、Graph-Mambaは長距離グラフ予測タスクにおいて最先端の手法より優れていることが示された。
論文 参考訳（メタデータ） (2024-02-01T17:21:53Z) - Scalable Bayesian Structure Learning for Gaussian Graphical Models Using Marginal Pseudo-likelihood [2.312692134587988]
連続時間(生死)および離散時間(可逆ジャンプ)マルコフ連鎖モンテカルロ(MCMC)アルゴリズムを開発し、グラフ空間の後方を効率的に探索する。
アルゴリズムは巨大なグラフ空間にスケールし、1000以上のノードを持つグラフの並列探索を可能にする。
論文 参考訳（メタデータ） (2023-06-30T20:37:40Z) - Efficiently Learning the Graph for Semi-supervised Learning [4.518012967046983]
共役勾配法を用いてスパース族から最良のグラフを効率的に学習する方法を示す。
我々の手法は、軽度な滑らかさの仮定の下で、オンラインのサブ線形後悔でグラフを効率的に学習するためにも利用できる。
提案手法を実装し,ベンチマークデータセット上の学習グラフを用いた半教師付き学習の先行研究に対して,大幅な(sim$10-100x)スピードアップを示す。
論文 参考訳（メタデータ） (2023-06-12T13:22:06Z) - Extending Compositional Attention Networks for Social Reasoning in
Videos [84.12658971655253]
ビデオにおけるソーシャルインタラクションを推論するタスクのための,新しいディープアーキテクチャを提案する。
構成注意ネットワーク(MAC)の多段階推論機能を活用し,マルチモーダル拡張(MAC-X)を提案する。
論文 参考訳（メタデータ） (2022-10-03T19:03:01Z) - CSGO: Constrained-Softassign Gradient Optimization For Large Graph Matching [0.7456521449098222]
本稿では,よく知られたグラフマッチングアルゴリズムを,制約付き勾配法というフレームワークに統合する。
属性付きグラフマッチングタスクでは、CSGOは現在の制約付き勾配アルゴリズムに比べて10倍以上の速度向上を達成する。
論文 参考訳（メタデータ） (2022-08-17T11:25:03Z) - Data-heterogeneity-aware Mixing for Decentralized Learning [63.83913592085953]
グラフの混合重みとノード間のデータ不均一性の関係に収束の依存性を特徴付ける。
グラフが現在の勾配を混合する能力を定量化する計量法を提案する。
そこで本研究では,パラメータを周期的かつ効率的に最適化する手法を提案する。
論文 参考訳（メタデータ） (2022-04-13T15:54:35Z) - GraphCoCo: Graph Complementary Contrastive Learning [65.89743197355722]
グラフコントラスト学習(GCL)は、手作業によるアノテーションの監督なしに、グラフ表現学習(GRL)において有望な性能を示した。
本稿では,この課題に対処するため,グラフココというグラフ補完型コントラスト学習手法を提案する。
論文 参考訳（メタデータ） (2022-03-24T02:58:36Z) - MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical
Models [96.1052289276254]
この研究は、人気のあるDual Block-Coordinate Ascent原則に基づく新しいMAP-solverを導入している。
驚いたことに、性能の低い解法に小さな変更を加えることで、既存の解法を大きなマージンで大幅に上回る新しい解法MPLP++を導出します。
論文 参考訳（メタデータ） (2020-04-16T16:20:53Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。