論文の概要: Equivariant Subgraph Aggregation Networks

• arxiv url: http://arxiv.org/abs/2110.02910v1
• Date: Wed, 6 Oct 2021 16:45:07 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-07 14:39:09.759379
• Title: Equivariant Subgraph Aggregation Networks
• Title（参考訳）: 等価部分グラフ集約ネットワーク
• Authors: Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M. Bronstein, Haggai Maron
• Abstract要約: 本稿では,この問題に対処するためのEquivariant Subgraph Aggregation Networks (ESAN) という新しいフレームワークを提案する。 2つのグラフはMPNNでは区別できないかもしれないが、しばしば区別可能な部分グラフを含む。 グラフ同型に対する1次元Weisfeiler-Leman(1-WL)テストの新しい変種を開発し、ESANの表現性に対する下界を証明した。 サブグラフ選択ポリシーや同変ニューラルアーキテクチャといった設計選択がアーキテクチャの表現力にどのように影響するかを記述する理論的結果を提供する。
• 参考スコア（独自算出の注目度）: 23.26140936226352
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Message-passing neural networks (MPNNs) are the leading architecture for deep learning on graph-structured data, in large part due to their simplicity and scalability. Unfortunately, it was shown that these architectures are limited in their expressive power. This paper proposes a novel framework called Equivariant Subgraph Aggregation Networks (ESAN) to address this issue. Our main observation is that while two graphs may not be distinguishable by an MPNN, they often contain distinguishable subgraphs. Thus, we propose to represent each graph as a set of subgraphs derived by some predefined policy, and to process it using a suitable equivariant architecture. We develop novel variants of the 1-dimensional Weisfeiler-Leman (1-WL) test for graph isomorphism, and prove lower bounds on the expressiveness of ESAN in terms of these new WL variants. We further prove that our approach increases the expressive power of both MPNNs and more expressive architectures. Moreover, we provide theoretical results that describe how design choices such as the subgraph selection policy and equivariant neural architecture affect our architecture's expressive power. To deal with the increased computational cost, we propose a subgraph sampling scheme, which can be viewed as a stochastic version of our framework. A comprehensive set of experiments on real and synthetic datasets demonstrates that our framework improves the expressive power and overall performance of popular GNN architectures.
• Abstract（参考訳）: メッセージパッシングニューラルネットワーク(MPNN)は、グラフ構造化データの深層学習における主要なアーキテクチャである。 残念ながら、これらのアーキテクチャは表現力に制限があることが示されている。 本稿では,この問題に対処するためのEquivariant Subgraph Aggregation Networks (ESAN) という新しいフレームワークを提案する。 主な観察では、2つのグラフはMPNNでは区別できないかもしれないが、しばしば区別可能な部分グラフを含んでいる。 そこで,各グラフを,事前定義された方針によって導出される部分グラフの集合として表現し,適切な同変アーキテクチャを用いて処理することを提案する。 グラフ同型に対する1次元Weisfeiler-Leman (1-WL)テストの新しい変種を開発し、これらの新しいWL変種の観点からESANの表現性に関する下限を証明した。 提案手法はMPNNとより表現力のあるアーキテクチャの両方の表現力を高める。 さらに、サブグラフ選択ポリシーや同変ニューラルアーキテクチャといった設計選択がアーキテクチャの表現力にどのように影響するかを記述する理論的結果を提供する。 計算コストの増大に対応するため,本フレームワークの確率的バージョンとみなすサブグラフサンプリング方式を提案する。 実および合成データセットに関する包括的な実験により、我々のフレームワークは一般的なGNNアーキテクチャの表現力と全体的な性能を改善していることを示す。

関連論文リスト

• From Hypergraph Energy Functions to Hypergraph Neural Networks [94.88564151540459]
  パラメータ化されたハイパーグラフ正規化エネルギー関数の表現型族を示す。 次に、これらのエネルギーの最小化がノード埋め込みとして効果的に機能することを実証する。 提案した双レベルハイパーグラフ最適化と既存のGNNアーキテクチャを共通的に用いている。
  論文  参考訳（メタデータ） (2023-06-16T04:40:59Z)
• Combining Stochastic Explainers and Subgraph Neural Networks can Increase Expressivity and Interpretability [12.526174412246107]
  サブグラフ強化グラフニューラルネットワーク(SGNN)は、標準的なメッセージパッシングフレームワークのパワーを高めることができる。 本稿では,グラフのクラスと説明的スパース部分グラフの集合を共同で予測する新しいフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-04-14T14:21:20Z)
• A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests [30.558563815430418]
  GNN(Subgraph Neural Network)は、表現型グラフニューラルネットワーク(GNN)を開発するための重要な方向として登場した。 本稿では,WIP(Subgraph Weisfeiler-Lehman Tests)のレンズを用いた一般ノードベースサブグラフGNNの系統的研究を行う。 ノードベースの部分グラフ GNN が 6 つのSWL 等価クラスのうちの 1 つに該当することを証明し、その中で $mathsfSSWL$ が最大表現力を達成する。
  論文  参考訳（メタデータ） (2023-02-14T14:42:54Z)
• Ordered Subgraph Aggregation Networks [19.18478955240166]
  グラフ強化グラフニューラルネットワーク(GNN)が登場し、標準(メッセージパス)GNNの表現力を確実に向上させている。 本稿では, 理論的枠組みを導入し, サブグラフ強化GNNの表現性を拡張した。 部分グラフサイズの増加は常に表現力を高め、それらの制限をよりよく理解することを示します。
  論文  参考訳（メタデータ） (2022-06-22T15:19:34Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• Structure-Aware Transformer for Graph Representation Learning [7.4124458942877105]
  本研究では,トランスフォーマーによって生成されるノード表現と位置符号化が必ずしも類似点を捉えるとは限らないことを示す。 本稿では,新しい自己認識機構上に構築された,単純で柔軟なグラフ変換器のクラスであるStructure-Aware Transformerを提案する。 我々のフレームワークは,既存のGNNを利用してサブグラフ表現を抽出し,ベースとなるGNNモデルに対する性能を体系的に向上することを示す。
  論文  参考訳（メタデータ） (2022-02-07T09:53:39Z)
• Frame Averaging for Invariant and Equivariant Network Design [50.87023773850824]
  フレーム平均化(FA)は、既知の(バックボーン)アーキテクチャを新しい対称性タイプに不変あるいは同変に適応するためのフレームワークである。 FAモデルが最大表現力を持つことを示す。 我々は,新しいユニバーサルグラフニューラルネット(GNN),ユニバーサルユークリッド運動不変点クラウドネットワーク,およびユークリッド運動不変メッセージパッシング(MP)GNNを提案する。
  論文  参考訳（メタデータ） (2021-10-07T11:05:23Z)
• Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results [58.277290855841976]
  グラフニューラルネットワーク(GNN)の計算コストと表現力のトレードオフについて検討する。 新しいモデルでは、$k$のサブグラフをカウントでき、低次GNNの既知の制限を克服できることを示す。 いくつかの場合において、提案アルゴリズムは既存の高階$k$-GNNに比べて計算量を大幅に削減することができる。
  論文  参考訳（メタデータ） (2020-12-06T03:42:54Z)
• Building powerful and equivariant graph neural networks with structural message-passing [74.93169425144755]
  本稿では,2つのアイデアに基づいた,強力かつ同変なメッセージパッシングフレームワークを提案する。 まず、各ノードの周囲の局所的コンテキスト行列を学習するために、特徴に加えてノードの1ホット符号化を伝搬する。 次に,メッセージのパラメトリゼーション手法を提案する。
  論文  参考訳（メタデータ） (2020-06-26T17:15:16Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)

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

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