論文の概要: On the Ability of Graph Neural Networks to Model Interactions Between Vertices

• arxiv url: http://arxiv.org/abs/2211.16494v5
• Date: Mon, 23 Oct 2023 12:02:34 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-25 14:15:14.314937
• Title: On the Ability of Graph Neural Networks to Model Interactions Between Vertices
• Title（参考訳）: 頂点間の相互作用をモデル化するグラフニューラルネットワークの能力について
• Authors: Noam Razin, Tom Verbin, Nadav Cohen
• Abstract要約: グラフニューラルネットワーク(GNN)は、グラフの頂点として表されるエンティティ間の複雑な相互作用をモデル化するために広く使われている。 近年のGNNの表現力を理論的に分析する試みにもかかわらず、相互作用をモデル化する能力の形式的特徴は欠如している。
• 参考スコア（独自算出の注目度）: 14.909298522361306
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph neural networks (GNNs) are widely used for modeling complex interactions between entities represented as vertices of a graph. Despite recent efforts to theoretically analyze the expressive power of GNNs, a formal characterization of their ability to model interactions is lacking. The current paper aims to address this gap. Formalizing strength of interactions through an established measure known as separation rank, we quantify the ability of certain GNNs to model interaction between a given subset of vertices and its complement, i.e. between the sides of a given partition of input vertices. Our results reveal that the ability to model interaction is primarily determined by the partition's walk index -- a graph-theoretical characteristic defined by the number of walks originating from the boundary of the partition. Experiments with common GNN architectures corroborate this finding. As a practical application of our theory, we design an edge sparsification algorithm named Walk Index Sparsification (WIS), which preserves the ability of a GNN to model interactions when input edges are removed. WIS is simple, computationally efficient, and in our experiments has markedly outperformed alternative methods in terms of induced prediction accuracy. More broadly, it showcases the potential of improving GNNs by theoretically analyzing the interactions they can model.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)は、グラフの頂点として表されるエンティティ間の複雑な相互作用をモデル化するために広く使われている。 近年のGNNの表現力を理論的に分析する試みにもかかわらず、相互作用をモデル化する能力の形式的特徴は欠如している。 現在の論文は、このギャップに対処することを目的としている。 分離ランクと呼ばれる確立された尺度による相互作用の形式化強度は、与えられた頂点の部分集合とその補集合の間の相互作用をモデル化する特定のGNNの能力を定量化する。 この結果から, 相互作用をモデル化する能力は, 分割の境界から得られるウォーク数によって定義されるグラフ理論特性であるウォーク指数によって決定されることがわかった。 一般的なgnnアーキテクチャを用いた実験はこの発見を裏付ける。 本理論の実用的応用として,入力エッジの除去時にGNNが相互作用をモデル化する能力を保持するWIS(Walk Index Sparsification)というエッジスペーシフィケーションアルゴリズムを設計する。 wisは単純で計算効率が良く,本実験では誘導予測の精度で代替手法を著しく上回っている。 より広義には、モデリング可能な相互作用を理論的に分析することで、GNNを改善する可能性を示している。

関連論文リスト

• GraphGI:A GNN Explanation Method using Game Interaction [5.149896909638598]
  グラフニューラルネットワーク(GNN)は、様々な領域で広く利用されている。 現在のグラフ説明技術は、キーノードやエッジの識別に重点を置いており、モデル予測を駆動する重要なデータ機能に寄与している。 本稿では,対話力の高い連立関係を識別し,説明文として提示する新しい説明法GraphGIを提案する。
  論文  参考訳（メタデータ） (2024-09-24T03:24:31Z)
• Learning Coarse-Grained Dynamics on Graph [4.692217705215042]
  グラフ上の粗粒度動的システムを特定するために,グラフニューラルネットワーク(GNN)非マルコフモデリングフレームワークを検討する。 本研究の主目的は, グラフトポロジを符号化する粗粒度相互作用係数に, モリ・ズワンチのメモリ項の先頭項がどのように依存するかを検査することによって, GNNアーキテクチャを体系的に決定することである。
  論文  参考訳（メタデータ） (2024-05-15T13:25:34Z)
• DEGREE: Decomposition Based Explanation For Graph Neural Networks [55.38873296761104]
  我々は,GNN予測に対する忠実な説明を提供するためにDGREEを提案する。 GNNの情報生成と集約機構を分解することにより、DECREEは入力グラフの特定のコンポーネントのコントリビューションを最終的な予測に追跡することができる。 また,従来の手法で見過ごされるグラフノード間の複雑な相互作用を明らかにするために,サブグラフレベルの解釈アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2023-05-22T10:29:52Z)
• Relation Embedding based Graph Neural Networks for Handling Heterogeneous Graph [58.99478502486377]
  我々は、同種GNNが不均一グラフを扱うのに十分な能力を持つように、シンプルで効率的なフレームワークを提案する。 具体的には、エッジ型関係と自己ループ接続の重要性を埋め込むために、関係1つのパラメータのみを使用する関係埋め込みベースのグラフニューラルネットワーク(RE-GNN)を提案する。
  論文  参考訳（メタデータ） (2022-09-23T05:24:18Z)
• Discovering the Representation Bottleneck of Graph Neural Networks from Multi-order Interactions [51.597480162777074]
  グラフニューラルネットワーク(GNN)は、ノード機能を伝搬し、インタラクションを構築するためにメッセージパッシングパラダイムに依存している。 最近の研究は、異なるグラフ学習タスクはノード間の異なる範囲の相互作用を必要とすることを指摘している。 科学領域における2つの共通グラフ構築法、すなわち、emphK-nearest neighbor(KNN)グラフとemphfully-connected(FC)グラフについて検討する。
  論文  参考訳（メタデータ） (2022-05-15T11:38:14Z)
• Edge-Level Explanations for Graph Neural Networks by Extending Explainability Methods for Convolutional Neural Networks [33.20913249848369]
  グラフニューラルネットワーク(GNN)は、グラフデータを入力として扱うディープラーニングモデルであり、トラフィック予測や分子特性予測といった様々なタスクに適用される。 本稿では,CNNに対する説明可能性の手法として,LIME(Local Interpretable Model-Agnostic Explanations)やGradient-Based Saliency Maps,Gradient-Weighted Class Activation Mapping(Grad-CAM)をGNNに拡張する。 実験結果から,LIMEに基づくアプローチは実環境における複数のタスクに対する最も効率的な説明可能性手法であり,その状態においても優れていたことが示唆された。
  論文  参考訳（メタデータ） (2021-11-01T06:27:29Z)
• Explicit Pairwise Factorized Graph Neural Network for Semi-Supervised Node Classification [59.06717774425588]
  本稿では,グラフ全体を部分的に観測されたマルコフ確率場としてモデル化するEPFGNN(Explicit Pairwise Factorized Graph Neural Network)を提案する。 出力-出力関係をモデル化するための明示的なペアワイズ要素を含み、入力-出力関係をモデル化するためにGNNバックボーンを使用する。 本研究では,グラフ上での半教師付きノード分類の性能を効果的に向上できることを示す。
  論文  参考訳（メタデータ） (2021-07-27T19:47:53Z)
• Permutation-equivariant and Proximity-aware Graph Neural Networks with Stochastic Message Passing [88.30867628592112]
  グラフニューラルネットワーク(GNN)は、グラフ上の新たな機械学習モデルである。 置換等価性と近接認識性は、GNNにとって非常に望ましい2つの重要な特性である。 既存のGNNは、主にメッセージパッシング機構に基づいており、同時に2つの特性を保存できないことを示す。 ノードの近さを保つため,既存のGNNをノード表現で拡張する。
  論文  参考訳（メタデータ） (2020-09-05T16:46:56Z)
• Binarized Graph Neural Network [65.20589262811677]
  我々は二項化グラフニューラルネットワークを開発し、二項化ネットワークパラメータを用いてノードのバイナリ表現を学習する。 提案手法は既存のGNNベースの埋め込み手法にシームレスに統合できる。 実験により、提案された二項化グラフニューラルネットワーク、すなわちBGNは、時間と空間の両方の観点から、桁違いに効率的であることが示されている。
  論文  参考訳（メタデータ） (2020-04-19T09:43:14Z)

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

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