Fugu-MT 論文翻訳(概要): Graph Neural Network-Informed Predictive Flows for Faster Ford-Fulkerson and PAC-Learnability

論文の概要: Graph Neural Network-Informed Predictive Flows for Faster Ford-Fulkerson and PAC-Learnability

arxiv url: http://arxiv.org/abs/2604.21175v1
Date: Thu, 23 Apr 2026 00:45:32 GMT
ステータス: 翻訳完了
システム内更新日: 2026-04-24 14:40:06.2229
Title: Graph Neural Network-Informed Predictive Flows for Faster Ford-Fulkerson and PAC-Learnability
Title（参考訳）: 高速Ford-FulkersonとPAC-Learnabilityのためのグラフニューラルネットワークインフォームド予測フロー
Authors: Eleanor Wiesler, Trace Baxley,
Abstract要約: 本稿では,グラフニューラルネットワーク(GNN)とFord-Fulkersonアルゴリズムを統合することにより,最大フローと画像セグメンテーションを高速化する学習フレームワークを提案する。本稿では,ノードとエッジの埋め込みを共同で学習するMPGNN(Message Passing GNN)を提案する。また、フローウォームスタートとエッジプライオリティ予測を組み合わせたハイブリッド拡張を概説し、画像セグメンテーションにおける学習誘導最適化の基礎を確立した。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We propose a learning-augmented framework for accelerating max-flow computation and image segmentation by integrating Graph Neural Networks (GNNs) with the Ford-Fulkerson algorithm. Rather than predicting initial flows, our method learns edge importance probabilities to guide augmenting path selection. We introduce a Message Passing GNN (MPGNN) that jointly learns node and edge embeddings through coupled updates, capturing both global structure and local flow dynamics such as residual capacity and bottlenecks. Given an input image, we propose a method to construct a grid-based flow network with source and sink nodes, extract features, and perform a single GNN inference to assign edge probabilities reflecting their likelihood of belonging to high-capacity cuts. These probabilities are stored in a priority queue and used to guide a modified Ford-Fulkerson procedure, prioritizing augmenting paths via an Edmonds-Karp-style search with bottleneck-aware tie-breaking. This avoids repeated inference over residual graphs while leveraging learned structure throughout optimization. We further introduce a bidirectional path construction strategy centered on high-probability edges and provide a theoretical framework relating prediction quality to efficiency via a weighted permutation distance metric. Our method preserves max-flow/min-cut optimality while reducing the number of augmentations in practice. We also outline a hybrid extension combining flow warm-starting with edge-priority prediction, establishing a foundation for learning-guided combinatorial optimization in image segmentation.
Abstract（参考訳）: 本稿では,グラフニューラルネットワーク(GNN)とFord-Fulkersonアルゴリズムを統合することにより,最大フロー計算と画像セグメンテーションを高速化する学習フレームワークを提案する。本手法は,初期流れを予測するのではなく,経路選択をガイドするエッジ重要度を学習する。メッセージパッシングGNN(MPGNN)を導入し、ノードとエッジの埋め込みを連携して学習し、残容量やボトルネックなどのグローバル構造と局所フローのダイナミクスをキャプチャする。入力画像が与えられた場合、ソースノードとシンクノードを備えたグリッドベースのフローネットワークを構築し、特徴を抽出し、1つのGNN推論を行い、高容量カットに属する可能性のあるエッジ確率を割り当てる手法を提案する。これらの確率は優先順位待ち行列に格納され、フォード・フルカーソンの修正手順を導くのに使われ、ボトルネック対応のタイブレーク付きエドモンズ・カルプスタイルの探索によって増大経路を優先する。これにより、残差グラフに対する繰り返しの推論を回避し、最適化全体を通して学習された構造を活用する。さらに,高確率エッジに着目した双方向経路構築戦略を導入し,重み付き置換距離測定による予測品質と効率性に関する理論的枠組みを提供する。提案手法は, 最大流量/最小カットの最適性を保ちながら, 実際の拡張回数を削減できる。また、フローウォームスタートとエッジプライオリティ予測を組み合わせたハイブリッド拡張を概説し、画像セグメンテーションにおける学習誘導組合せ最適化の基礎を確立した。

関連論文リスト

Unrolled Neural Networks for Constrained Optimization [83.29547301151177]
我々のフレームワークは、ラグランジアンのサドル点を共同で近似する2つの結合ニューラルネットワークで構成されている。混合整数二次プログラムと無線ネットワークにおける電力配分に関する枠組みを数値的に評価する。
論文参考訳（メタデータ） (2026-01-24T03:12:41Z)
Unrolled Graph Neural Networks for Constrained Optimization [83.29547301151177]
2つの結合グラフニューラルネットワーク(GNN)における双対昇降アルゴリズムのダイナミクスについて検討する。予備的ネットワークと二重ネットワークの更新を交互に行う共同学習手法を提案する。我々の数値実験は、我々のアプローチがほぼ最適に近いほぼ実現可能な解をもたらすことを示す。
論文参考訳（メタデータ） (2025-09-21T16:55:41Z)
Sparse Decomposition of Graph Neural Networks [20.768412002413843]
本稿では,集約中に含まれるノード数を削減する手法を提案する。線形変換された特徴の重み付け和を用いてノード表現の近似を学習し、スパース分解によりこれを実現できる。提案手法は推論高速化のために設計された他のベースラインよりも優れていることを示す。
論文参考訳（メタデータ） (2024-10-25T17:52:16Z)
Scalable Graph Compressed Convolutions [68.85227170390864]
ユークリッド畳み込みのための入力グラフのキャリブレーションに置換を適用する微分可能手法を提案する。グラフキャリブレーションに基づいて,階層型グラフ表現学習のための圧縮畳み込みネットワーク(CoCN)を提案する。
論文参考訳（メタデータ） (2024-07-26T03:14:13Z)
Stochastic Unrolled Federated Learning [85.6993263983062]
本稿では,UnRolled Federated Learning (SURF)を導入する。提案手法は,この拡張における2つの課題,すなわち,非学習者へのデータセット全体の供給の必要性と,フェデレート学習の分散的性質に対処する。
論文参考訳（メタデータ） (2023-05-24T17:26:22Z)
DAG Matters! GFlowNets Enhanced Explainer For Graph Neural Networks [30.19635147123557]
我々はGFlowNetsベースのGNN Explainer(GFlowExplainer)という生成構造を提案する。我々のGFlowExplainerは、サブグラフの確率がその報酬に比例するサブグラフの分布を生成するポリシーを学習することを目的としています。我々は合成データと実データの両方について広範な実験を行い、質的および定量的な結果はGFlowExplainerの優位性を示している。
論文参考訳（メタデータ） (2023-03-04T16:15:25Z)
EGRC-Net: Embedding-induced Graph Refinement Clustering Network [66.44293190793294]
埋め込みによるグラフリファインメントクラスタリングネットワーク (EGRC-Net) という新しいグラフクラスタリングネットワークを提案する。 EGRC-Netは学習した埋め込みを利用して初期グラフを適応的に洗練し、クラスタリング性能を向上させる。提案手法はいくつかの最先端手法より一貫して優れている。
論文参考訳（メタデータ） (2022-11-19T09:08:43Z)
Graph-based Algorithm Unfolding for Energy-aware Power Allocation in Wireless Networks [27.600081147252155]
我々は,無線通信網におけるエネルギー効率を最大化する新しいグラフ要約フレームワークを開発した。無線ネットワークデータのモデルに望ましい特性である置換訓練について述べる。結果は、異なるネットワークトポロジにまたがる一般化可能性を示している。
論文参考訳（メタデータ） (2022-01-27T20:23:24Z)
Generalizable Cross-Graph Embedding for GNN-based Congestion Prediction [22.974348682859322]
我々は,ノード機能の品質を高めるために,与えられたネットリストの埋め込みを直接学習できるフレームワークを提案する。ネットリスト上に学習した埋め込みとGNNを組み合わせることで、予測性能を改善し、新しい回路ラインに一般化し、トレーニングの効率化を実現し、実行時に90 %以上節約できる可能性がある。
論文参考訳（メタデータ） (2021-11-10T20:56:29Z)
Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
論文参考訳（メタデータ） (2020-05-05T18:08:23Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。