論文の概要: Neural Algorithmic Reasoning for Graph Saddle Point Problems
- arxiv url: http://arxiv.org/abs/2610.07255v1
- Date: Mon, 05 Oct 2026 18:55:21 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-08 02:58:29.606775
- Title: Neural Algorithmic Reasoning for Graph Saddle Point Problems
- Title（参考訳）: グラフサドル点問題に対するニューラルネットワーク推論
- Abstract要約: 本稿では,Chambolle-Pock Primal-Dual Hybrid Gradient (PDHG) 法に基づく新しいメッセージパッシングフレームワークを提案する。
PDHGをシミュレートすることで,TextscGraphPDHGがグラフサドルポイントの問題を効率的に解決できることを示す。
また,ネットワークが高速化されたPDHGアルゴリズムを学習できることも示す。
- 参考スコア（独自算出の注目度）: 10.366901311631485
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Neural algorithmic reasoning, or aligning a neural network with an algorithmic paradigm, has emerged as an approach to solving polynomial-time-solvable and computationally harder combinatorial optimization problems. We propose a new message-passing framework based on the Chambolle-Pock Primal--Dual Hybrid Gradient (PDHG) method called \textsc{GraphPDHG} for solving general graph saddle-point problems. Theoretically, we show that \textsc{GraphPDHG} can efficiently solve a family of graph saddle-point problems by simulating PDHG. We also show that our network can learn an accelerated PDHG algorithm. Experimentally, we support our results on accelerated PDHG by evaluating the performance of our model as a learned warm start for second-order optimization techniques (SSNAL). We also show that alignment with PDHG leads to stronger size generalization than non-aligned graph neural network (GNN) baselines. Overall, we propose a novel architecture for solving a general family of optimization problems on graphs.
- Abstract（参考訳）: ニューラルネットワークをアルゴリズムパラダイムと整合させるニューラルネットワーク推論は、多項式時間分解可能で計算的に難しい組合せ最適化問題の解法として登場した。
本稿では,一般的なグラフサドル点問題の解法として,Chambolle-Pock Primal-Dual Hybrid Gradient (PDHG) 法を応用した新しいメッセージパッシングフレームワークである \textsc{GraphPDHG} を提案する。
理論的には、PDHGをシミュレートすることで、グラフサドルポイント問題の族を効率的に解くことができる。
また,ネットワークが高速化されたPDHGアルゴリズムを学習できることも示す。
実験では,2次最適化手法(SSNAL)の学習開始点としてモデルの性能を評価することにより,加速PDHGに関する結果を支持する。
また、PDHGとのアライメントは、非アライメントグラフニューラルネットワーク(GNN)のベースラインよりも大きなサイズ一般化をもたらすことを示す。
本稿では,グラフ上での最適化問題を解くための新しいアーキテクチャを提案する。
関連論文リスト
- AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network [50.69521065962045]
Anisotropic Graph Diffusion Network (AGDN) はトラベリングセールスマン問題(TSP)を解決するために設計された新しいグラフニューラルネットワークフレームワークである。
提案手法は,1) 完全連結TSPグラフにおける情報的トポロジ的事前の欠如,2) グラフスペーシフィケーション手法により最適解における接続ノードの喪失,の2つの問題に対処する。
AGDNは、競争力を維持しながら、既存の手法を一貫して上回る。
論文 参考訳（メタデータ） (2026-06-17T15:24:37Z) - On the Complexity of Optimal Graph Rewiring for Oversmoothing and Oversquashing in Graph Neural Networks [2.8427946758947304]
グラフニューラルネットワーク(GNN)は、ディープアーキテクチャへのスケールアップにおいて、2つの根本的な課題に直面している。
オーバースムーシングとオーバースキャッシングは、基礎となるグラフ構造と密接に結びついている。
本稿では,そのようなグラフ構造最適化の計算複雑性について理論的に考察する。
論文 参考訳（メタデータ） (2026-03-27T07:50:42Z) - Bootstrap Learning for Combinatorial Graph Alignment with Sequential GNNs [8.49454123392354]
グラフニューラルネットワーク(GNN)は、ニューラルネットワークの従来の最適化手法よりも優れており、その実践的影響を制限している。
本稿では,構造情報のみを用いて,グラフアライメント問題に対する新しい連鎖手法を提案する。
提案手法は,従来のネットワークが生成した類似度行列を反復的に洗練することを学ぶ,一連のGNNを訓練する。
各GNNは、以前のイテレーションからノードアライメントの品質に関する個別のランキング情報を組み込むことで、部分的なソリューションを改善する。
論文 参考訳（メタデータ） (2025-10-03T15:17:00Z) - Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
ノード分類タスクにおける大規模グラフの利用は、グラフニューラルネットワーク(GNN)の現実的な応用を妨げる
本稿では,GNNのグラフコアセットについて検討し,スペクトル埋め込みに基づくエゴグラフの選択により相互依存の問題を回避する。
我々のスペクトルグレディグラフコアセット(SGGC)は、数百万のノードを持つグラフにスケールし、モデル事前学習の必要性を排除し、低ホモフィリーグラフに適用する。
論文 参考訳（メタデータ） (2024-05-27T17:52:12Z) - Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
グラフマッチングはコンピュータビジョンやパターン認識において一般的に用いられる技法である。
最近のデータ駆動型アプローチは、グラフマッチングの精度を著しく改善した。
データ駆動手法と従来の手法の利点を組み合わせたグラフニューラルネットワーク(GNN)に基づくアプローチを提案する。
論文 参考訳（メタデータ） (2024-03-11T06:34:05Z) - A Graph Neural Network-Based QUBO-Formulated Hamiltonian-Inspired Loss
Function for Combinatorial Optimization using Reinforcement Learning [1.325953054381901]
グラフニューラルネットワーク(GNN)を用いた新しいモンティカルロ木探索手法を提案する。
PI-GNNに関連する行動パターンを特定し,その性能向上のための戦略を考案する。
また、RL法とQUBO法で定式化されたハミルトニアンとの橋渡しにも着目する。
論文 参考訳（メタデータ） (2023-11-27T19:33:14Z) - A Graph Neural Network-Based QUBO-Formulated Hamiltonian-Inspired Loss
Function for Combinatorial Optimization using Reinforcement Learning [1.566437882635872]
ハミルトニアン函数は、最適化の文脈において目的関数として使用されるQUBO問題を定式化するためにしばしば用いられる。
汎用的なスケーラブルなフレームワークであるPI-GNNは、単純なグラフニューラルネットワーク(GNN)アーキテクチャに基づいて、グラフ上の組合せ最適化(CO)問題に対処するために提案されている。
実験では,PI-GNN法と比較して最大44%改善した。
論文 参考訳（メタデータ） (2023-08-27T00:57:01Z) - The Neural-Prediction based Acceleration Algorithm of Column Generation
for Graph-Based Set Covering Problems [20.1479227701035]
グラフに基づく集合被覆問題の解法として,ニューラル予測(CG-P)を用いたカラム生成アルゴリズムを提案する。
グラフニューラルネットワークに基づくニューラル予測モデルを用いて,各エッジの最終解に含まれる確率を予測する。
鉄道員のスケジューリング問題に対するCG-Pアルゴリズムの評価を行い,ベースライン列生成アルゴリズムよりも優れていた。
論文 参考訳（メタデータ） (2022-07-04T13:46:59Z) - Learning Graph Structure from Convolutional Mixtures [119.45320143101381]
本稿では、観測されたグラフと潜伏グラフのグラフ畳み込み関係を提案し、グラフ学習タスクをネットワーク逆(デコンボリューション)問題として定式化する。
固有分解に基づくスペクトル法の代わりに、近似勾配反復をアンロール・トランケートして、グラフデコンボリューションネットワーク(GDN)と呼ばれるパラメータ化ニューラルネットワークアーキテクチャに到達させる。
GDNは、教師付き方式でグラフの分布を学習し、損失関数を適応させることでリンク予測やエッジウェイト回帰タスクを実行し、本質的に帰納的である。
論文 参考訳（メタデータ） (2022-05-19T14:08:15Z) - Unrolling of Deep Graph Total Variation for Image Denoising [106.93258903150702]
本稿では,従来のグラフ信号フィルタリングと深い特徴学習を併用して,競合するハイブリッド設計を提案する。
解釈可能な低パスグラフフィルタを用い、最先端のDL復調方式DnCNNよりも80%少ないネットワークパラメータを用いる。
論文 参考訳（メタデータ） (2020-10-21T20:04:22Z) - Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。
しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。
本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
論文 参考訳（メタデータ） (2020-01-18T09:14:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。