論文の概要: The expressive power of pooling in Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2304.01575v2
• Date: Wed, 26 Apr 2023 16:41:42 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-27 17:20:17.986854
• Title: The expressive power of pooling in Graph Neural Networks
• Title（参考訳）: グラフニューラルネットワークにおけるプールの表現力
• Authors: Filippo Maria Bianchi, Veronica Lachi
• Abstract要約: 階層的なプーリング演算子は、グラフ構造と特徴を粗くすることで、データの局所的な要約を生成する。 本研究では, プール演算子がMP層の表現力を完全に維持するために必要な条件を導出する。 本稿では,グラフアイソモーフィズムテストの実行能力の観点から,プール層を備えたGNNの表現力を実証的に検証する実験装置を提案する。
• 参考スコア（独自算出の注目度）: 5.571369922847262
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In Graph Neural Networks (GNNs), hierarchical pooling operators generate local summaries of the data by coarsening the graph structure and the vertex features. Considerable attention has been devoted to analyzing the expressive power of message-passing (MP) layers in GNNs, while a study on how graph pooling affects the expressiveness of a GNN is still lacking. Additionally, despite the recent advances in the design of pooling operators, there is not a principled criterion to compare them. In this work, we derive sufficient conditions for a pooling operator to fully preserve the expressive power of the MP layers before it. These conditions serve as a universal and theoretically-grounded criterion for choosing among existing pooling operators or designing new ones. Based on our theoretical findings, we analyze several existing pooling operators and identify those that fail to satisfy the expressiveness conditions. Finally, we introduce an experimental setup to verify empirically the expressive power of a GNN equipped with pooling layers, in terms of its capability to perform a graph isomorphism test.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)では、階層的なプーリング演算子は、グラフ構造と頂点の特徴を粗くすることで、データの局所的な要約を生成する。 GNNにおけるメッセージパッシング(MP)層の表現力の分析に注目が集まる一方で、グラフプーリングがGNNの表現力にどのように影響するかの研究がまだ不足している。 また、最近のプール演算子の設計の進歩にもかかわらず、比較する原則的な基準は存在しない。 本研究では, プール演算子がMP層の表現力を完全に維持するために必要な条件を導出する。 これらの条件は、既存のプーリング演算子の中から選択したり、新しいものを設計するための普遍的で理論的な基準として機能する。 理論的な知見に基づき,既存のプーリング演算子を複数解析し,表現性の条件を満たすことができないものを同定する。 最後に,グラフ同型テストの実行能力の観点から,プール層を備えたGNNの表現力を実証的に検証する実験装置を提案する。

関連論文リスト

• Graph Classification with GNNs: Optimisation, Representation and Inductive Bias [0.6445605125467572]
  このような等価性は、付随する最適化問題を無視するものであり、GNN学習プロセスの全体像を提供するものではない、と我々は主張する。 理論的には、グラフ内のメッセージパッシング層は、識別サブグラフか、あるいはグラフ全体に分散した識別ノードの集合を探索する傾向にあることを証明している。
  論文  参考訳（メタデータ） (2024-08-17T18:15:44Z)
• DEGREE: Decomposition Based Explanation For Graph Neural Networks [55.38873296761104]
  我々は,GNN予測に対する忠実な説明を提供するためにDGREEを提案する。 GNNの情報生成と集約機構を分解することにより、DECREEは入力グラフの特定のコンポーネントのコントリビューションを最終的な予測に追跡することができる。 また,従来の手法で見過ごされるグラフノード間の複雑な相互作用を明らかにするために,サブグラフレベルの解釈アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2023-05-22T10:29:52Z)
• Higher-order Clustering and Pooling for Graph Neural Networks [77.47617360812023]
  グラフニューラルネットワークは、多数のグラフ分類タスクにおいて最先端のパフォーマンスを達成する。 HoscPoolはクラスタリングベースのグラフプーリング演算子で、階層的に高階情報をキャプチャする。 グラフ分類タスクにおいてHoscPoolを評価し,そのクラスタリングコンポーネントを地層構造を持つグラフ上で評価する。
  論文  参考訳（メタデータ） (2022-09-02T09:17:10Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• Breaking the Expressive Bottlenecks of Graph Neural Networks [26.000304641965947]
  近年, weisfeiler-lehman (wl) graph isomorphism test を用いてグラフニューラルネットワーク (gnns) の表現性の測定を行った。 本稿では,強力なアグリゲータを探索することで表現性を向上する。
  論文  参考訳（メタデータ） (2020-12-14T02:36:46Z)
• Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results [58.277290855841976]
  グラフニューラルネットワーク(GNN)の計算コストと表現力のトレードオフについて検討する。 新しいモデルでは、$k$のサブグラフをカウントでき、低次GNNの既知の制限を克服できることを示す。 いくつかの場合において、提案アルゴリズムは既存の高階$k$-GNNに比べて計算量を大幅に削減することができる。
  論文  参考訳（メタデータ） (2020-12-06T03:42:54Z)
• Rethinking pooling in graph neural networks [12.168949038217889]
  畳み込み層とその後のプール層との相互作用について検討する。 一般的な信念とは対照的に、局所プールは、関連する、広く使用されているベンチマーク上でのGNNの成功には寄与しない。
  論文  参考訳（メタデータ） (2020-10-22T03:48:56Z)
• The Surprising Power of Graph Neural Networks with Random Node Initialization [54.4101931234922]
  グラフニューラルネットワーク(GNN)は、関係データ上での表現学習に有効なモデルである。 標準 GNN はその表現力に制限があり、Weisfeiler-Leman グラフ同型(英語版)の能力以外の区別はできない。 本研究では,ランダムノード(RNI)を用いたGNNの表現力の解析を行う。 我々はこれらのモデルが普遍的であることを証明し、GNNが高次特性の計算に頼らない最初の結果である。
  論文  参考訳（メタデータ） (2020-10-02T19:53:05Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)
• SimPool: Towards Topology Based Graph Pooling with Structural Similarity Features [0.0]
  本稿では,2つの主要な寄与について提案する。1つ目は,隣接行列に基づく構造的類似性を計算した差分モジュールである。 2つ目の主な貢献は、これらの機能をDiffPool arXiv:1806.08804の再検討されたプール層と統合し、SimPoolと呼ばれるプーリング層を提案することである。 実験の結果、エンドツーエンドのグラフニューラルネットワークアーキテクチャの一部として、SimPoolは、より局所性に近いノードクラスタ割り当てを計算する。
  論文  参考訳（メタデータ） (2020-06-03T12:51:57Z)

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

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