論文の概要: Going with the Flow: Approximating Banzhaf Values via Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2510.13391v1
• Date: Wed, 15 Oct 2025 10:40:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-16 20:13:28.624144
• Title: Going with the Flow: Approximating Banzhaf Values via Graph Neural Networks
• Title（参考訳）: フローで進む - グラフニューラルネットワークによるBanzhaf値の近似
• Authors: Benjamin Kempinski, Tal Kachman,
• Abstract要約: ネットワークフローゲームにおいて,グラフニューラルネットワーク(GNN)を用いてBanzhafの値を近似する新しい学習手法を提案する。 トレーニングされたGNNモデルは,高忠実度Banzhaf値近似を実現し,次数化の高速化を実現する。 この研究は、複雑なネットワークシステムのスケーラブルな協調ゲーム理論解析のための実用的なツールとして、GNNを確立している。
• 参考スコア（独自算出の注目度）: 1.8047694351309207
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Computing the Banzhaf value in network flow games is fundamental for quantifying agent influence in multi-agent systems, with applications ranging from cybersecurity to infrastructure planning. However, exact computation is intractable for systems with more than $\sim20$ agents due to exponential complexity $\mathcal{O}(2^m)$. While Monte Carlo sampling methods provide statistical estimates, they suffer from high sample complexity and cannot transfer knowledge across different network configurations, making them impractical for large-scale or dynamic systems. We present a novel learning-based approach using Graph Neural Networks (GNNs) to approximate Banzhaf values in cardinal network flow games. By framing the problem as a graph-level prediction task, our method learns generalisable patterns of agent influence directly from network topology and control structure. We conduct a comprehensive empirical study comparing three state-of-the-art GNN architectures-Graph Attention Networks (GAT), Graph Isomorphism Networks with Edge features (GINE), and EdgeConv-on a large-scale synthetic dataset of 200,000 graphs per configuration, varying in size (20-100 nodes), agent count (5-20), and edge probability (0.5-1.0). Our results demonstrate that trained GNN models achieve high-fidelity Banzhaf value approximation with order-of-magnitude speedups compared to exact and sampling-based methods. Most significantly, we show strong zero-shot generalisation: models trained on graphs of a specific size and topology accurately predict Banzhaf values for entirely new networks with different structural properties, without requiring retraining. This work establishes GNNs as a practical tool for scalable cooperative game-theoretic analysis of complex networked systems.
• Abstract（参考訳）: ネットワークフローゲームにおけるBanzhafの価値の計算は、サイバーセキュリティからインフラ計画に至るまで、マルチエージェントシステムにおけるエージェントの影響を定量化するための基本となる。 しかし、指数複雑性$\mathcal{O}(2^m)$のため、$\sim20$エージェント以上のシステムでは正確な計算が難解である。 モンテカルロサンプリング法は統計的な推定を提供するが、それらは高いサンプルの複雑さに悩まされており、異なるネットワーク構成で知識を伝達できないため、大規模なシステムや動的システムでは実用的ではない。 ネットワークフローゲームにおいて,グラフニューラルネットワーク(GNN)を用いてBanzhafの値を近似する新しい学習手法を提案する。 グラフレベルの予測タスクとして問題をフレーミングすることにより,ネットワークトポロジや制御構造から直接,エージェントの影響の一般化可能なパターンを学習する。 我々は,3つの最先端GNNアーキテクチャであるグラフアテンションネットワーク(GAT),エッジ特徴付きグラフアイソモーフィズムネットワーク(GINE),EdgeConv-onの大規模合成データセットを,サイズ(20～100ノード),エージェント数(5～20ノード),エッジ確率(0.5～1.0ノード)で比較した総合的研究を行った。 以上の結果から,訓練されたGNNモデルにより,精度の高いBanzhaf値近似が得られた。 より顕著に、我々は強いゼロショットの一般化を示す: 特定の大きさのグラフとトポロジーで訓練されたモデルが、再トレーニングを必要とせず、全く異なる構造特性を持つネットワークに対して、バンジャフの値を正確に予測する。 この研究は、複雑なネットワークシステムのスケーラブルな協調ゲーム理論解析のための実用的なツールとして、GNNを確立している。

関連論文リスト

• Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks [53.10674067060148]
  共有インタラクション(SI)は、複数のノード間のノードのコントリビューションとインタラクションを定量化する。 GNNアーキテクチャを利用して、ノード埋め込みにおける相互作用の構造がグラフ予測のために保存されていることを示す。 任意の順序SIを正確に計算するための効率的なアプローチであるGraphSHAP-IQを導入する。
  論文  参考訳（メタデータ） (2025-01-28T13:37:44Z)
• DeltaGNN: Graph Neural Network with Information Flow Control [5.563171090433323]
  グラフニューラルネットワーク(GNN)は、メッセージパッシングプロセスの近傍集約を通じてグラフ構造化データを処理するように設計されている。 メッセージパッシングにより、GNNは短距離空間的相互作用を理解できるだけでなく、過度なスムーシングや過度なスカッシングに悩まされる。 本稿では,線形計算オーバーヘッドを伴うオーバー・スムーシングとオーバー・スキャッシングに対処するための,emph情報フロー制御機構を提案する。 さまざまなサイズ、トポロジ、密度、ホモフィリック比のグラフを含む10の実世界のデータセットを対象に、我々のモデルをベンチマークし、優れたパフォーマンスを示す。
  論文  参考訳（メタデータ） (2025-01-10T14:34:20Z)
• BLIS-Net: Classifying and Analyzing Signals on Graphs [20.345611294709244]
  グラフニューラルネットワーク(GNN)は、ノード分類やグラフ分類といったタスクのための強力なツールとして登場した。 我々は以前に導入された幾何散乱変換に基づいて構築された新しいGNNであるBLIS-Net(Bi-Lipschitz Scattering Net)を紹介する。 BLIS-Netは,交通流とfMRIデータに基づいて,合成データと実世界のデータの両方において優れた性能を発揮することを示す。
  論文  参考訳（メタデータ） (2023-10-26T17:03:14Z)
• Dynamic Graph Message Passing Networks for Visual Recognition [112.49513303433606]
  長距離依存のモデリングは、コンピュータビジョンにおけるシーン理解タスクに不可欠である。 完全連結グラフはそのようなモデリングには有益であるが、計算オーバーヘッドは禁じられている。 本稿では,計算複雑性を大幅に低減する動的グラフメッセージパッシングネットワークを提案する。
  論文  参考訳（メタデータ） (2022-09-20T14:41:37Z)
• Lipschitz Bound Analysis of Neural Networks [0.0]
  リプシッツ境界推定は、ディープニューラルネットワークを正則化し、敵の攻撃に対して堅牢にする効果的な方法である。 本稿では、畳み込みニューラルネットワーク(CNN)のための非自明なリプシッツ境界証明書を得る際の大きなギャップについて述べる。 また,畳み込みニューラルネットワーク(CNN)を完全連結ネットワークに変換するために,畳み込み層やToeplitz行列の展開も可能であることを示す。
  論文  参考訳（メタデータ） (2022-07-14T23:40:22Z)
• Deep Architecture Connectivity Matters for Its Convergence: A Fine-Grained Analysis [94.64007376939735]
  我々は、勾配降下訓練におけるディープニューラルネットワーク(DNN)の収束に対する接続パターンの影響を理論的に特徴づける。 接続パターンの単純なフィルタリングによって、評価対象のモデルの数を削減できることが示される。
  論文  参考訳（メタデータ） (2022-05-11T17:43:54Z)
• Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patterns [19.346133577539394]
  グラフニューラルネットワーク(GNN)は、複数のグラフベースの学習タスクで大きな成功を収めています。 入力グラフを近接情報と構造情報の両方を含む計算グラフに変換することに集中する。 構造と近接度を適応的に選択することで,様々な混合条件下での性能が向上することを示す。
  論文  参考訳（メタデータ） (2021-06-11T19:18:34Z)
• Analyzing the Performance of Graph Neural Networks with Pipe Parallelism [2.269587850533721]
  ノードやエッジの分類やリンクの予測といったタスクで大きな成功を収めたグラフニューラルネットワーク(GNN)に注目した。 グラフ技術の進歩には,大規模ネットワーク処理のための新たなアプローチが必要である。 私たちは、ディープラーニングコミュニティで成功したと知られている既存のツールとフレームワークを使用して、GNNを並列化する方法を研究します。
  論文  参考訳（メタデータ） (2020-12-20T04:20:38Z)
• Dynamic Graph: Learning Instance-aware Connectivity for Neural Networks [78.65792427542672]
  動的グラフネットワーク(DG-Net)は完全な有向非巡回グラフであり、ノードは畳み込みブロックを表し、エッジは接続経路を表す。 ネットワークの同じパスを使用する代わりに、DG-Netは各ノードの機能を動的に集約する。
  論文  参考訳（メタデータ） (2020-10-02T16:50:26Z)
• Graphs, Convolutions, and Neural Networks: From Graph Filters to Graph Neural Networks [183.97265247061847]
  我々はグラフ信号処理を活用してグラフニューラルネットワーク(GNN)の表現空間を特徴付ける。 GNNにおけるグラフ畳み込みフィルタの役割について議論し、そのようなフィルタで構築されたアーキテクチャは、置換同値の基本的な性質と位相変化に対する安定性を持つことを示す。 また,ロボット群に対するリコメンデータシステムや分散型コントローラの学習におけるGNNの利用について検討した。
  論文  参考訳（メタデータ） (2020-03-08T13:02:15Z)

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

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