論文の概要: The expressive power of pooling in Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2304.01575v1
- Date: Tue, 4 Apr 2023 07:03:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-05 14:54:51.467855
- Title: The expressive power of pooling in Graph Neural Networks
- Title（参考訳）: グラフニューラルネットワークにおけるプールの表現力
- Authors: Filippo Maria Bianchi, Veronica Lachi
- Abstract要約: グラフニューラルネットワーク(GNN)では、階層的なプーリング演算子は、グラフ構造とその特徴の局所的な要約を作成することにより、入力データの粗い表現を生成する。
プーリング演算子がMP層の表現力を完全に維持できる十分な条件を提供する。
そこで我々は,グラフ同型テストの実行能力の観点から,プール層を備えたGNNの表現力を実証的に測定した。
- 参考スコア（独自算出の注目度）: 5.571369922847262
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In Graph Neural Networks (GNNs), hierarchical pooling operators generate a
coarser representation of the input data by creating local summaries of the
graph structure and its vertex features. Considerable attention has been
devoted to studying the expressive power of message-passing (MP) layers in
GNNs, while a study on how pooling operators affect the expressivity of a GNN
is still lacking. Additionally, despite the recent advances in the design of
effective pooling operators, there is not a principled criterion to compare
them. Our work aims to fill this gap by providing 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 reviewed several existing pooling operators and
identified those that fail to satisfy the expressiveness assumptions. Finally,
we introduced an experimental setup to empirically measure 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。