グラフニューラルネットワークに基づく予測フロー：より高速なフォード＝ファルカーソンとPAC学習可能性

要旨: Graph Neural Networks（GNN）をFord-Fulkersonアルゴリズムに統合することで、最大流計算と画像セグメンテーションを加速するための学習補助型フレームワークを提案します。初期フローを予測するのではなく、本手法は、増加路（augmenting path）の選択を導くために辺の重要度確率を学習します。我々は、結合した更新によってノードと辺の埋め込みを同時に学習するMessage Passing GNN（MPGNN）を導入し、残余容量やボトルネックといった局所的なフロー動態と、グローバルな構造の両方を捉えます。

入力画像が与えられたとき、我々は、ソースノードとシンクノードを備えた格子ベースのフロー・ネットワークを構築する方法を提案し、特徴を抽出したうえで、1回のGNN推論を行い、高容量カットに属する可能性を反映する辺の確率を割り当てます。これらの確率は優先度付きキューに保存され、ボトルネックを考慮した同点解決（tie-breaking）により、Edmonds-Karp型の探索で増加路を優先していく、修正されたFord-Fulkerson手続きのガイドに用いられます。残余グラフに対する推論を繰り返すことを回避しつつ、最適化全体を通して学習された構造を活用します。

さらに、確率の高い辺を中心とした双方向の経路構築戦略を導入し、重み付き置換距離（weighted permutation distance）指標を介して予測品質と効率の関係を結び付ける理論的枠組みも提示します。本手法は最大流/最小カットの最適性を維持しつつ、実際には増加（augmentation）の回数を削減します。また、フローのウォームスタートと辺優先の予測を組み合わせたハイブリッド拡張についても概説し、画像セグメンテーションにおける学習ガイド付き組合せ最適化の基盤を確立します。