論文の概要: Equivariant Polynomials for Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2302.11556v1
- Date: Wed, 22 Feb 2023 18:53:38 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-23 14:08:43.620583
- Title: Equivariant Polynomials for Graph Neural Networks
- Title(参考訳): グラフニューラルネットワークのための等変多項式
- Authors: Omri Puny, Derek Lim, Bobak T. Kiani, Haggai Maron, Yaron Lipman
- Abstract要約: グラフネットワーク(GNN)は本質的に表現力に制限がある。
本稿では、GNNがある程度の同変を計算する能力に基づく代替パワー階層を提案する。
これらの強化されたGNNは、複数のグラフ学習ベンチマークの実験において最先端の結果を示す。
- 参考スコア(独自算出の注目度): 38.15983687193912
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Graph Neural Networks (GNN) are inherently limited in their expressive power.
Recent seminal works (Xu et al., 2019; Morris et al., 2019b) introduced the
Weisfeiler-Lehman (WL) hierarchy as a measure of expressive power. Although
this hierarchy has propelled significant advances in GNN analysis and
architecture developments, it suffers from several significant limitations.
These include a complex definition that lacks direct guidance for model
improvement and a WL hierarchy that is too coarse to study current GNNs. This
paper introduces an alternative expressive power hierarchy based on the ability
of GNNs to calculate equivariant polynomials of a certain degree. As a first
step, we provide a full characterization of all equivariant graph polynomials
by introducing a concrete basis, significantly generalizing previous results.
Each basis element corresponds to a specific multi-graph, and its computation
over some graph data input corresponds to a tensor contraction problem. Second,
we propose algorithmic tools for evaluating the expressiveness of GNNs using
tensor contraction sequences, and calculate the expressive power of popular
GNNs. Finally, we enhance the expressivity of common GNN architectures by
adding polynomial features or additional operations / aggregations inspired by
our theory. These enhanced GNNs demonstrate state-of-the-art results in
experiments across multiple graph learning benchmarks.
- Abstract(参考訳): グラフニューラルネットワーク(GNN)は本質的に表現力に制限がある。
最近のセミナー作品(Xu et al., 2019; Morris et al., 2019b)は、表現力の尺度としてWeisfeiler-Lehman階層を導入した。
この階層構造は、GNN分析とアーキテクチャ開発に大きな進歩をもたらしたが、いくつかの重大な制限に悩まされている。
これには、モデル改善のための直接的なガイダンスが欠けている複雑な定義と、現在のGNNを研究するには大きすぎるWL階層が含まれる。
本稿では、GNNが等変多項式をある程度計算する能力に基づいて、別の表現力階層を提案する。
最初のステップとして、具体的基礎を導入し、前の結果を著しく一般化することで、すべての同変グラフ多項式の完全な特徴づけを提供する。
各基底要素は特定の多重グラフに対応し、そのグラフデータ入力上の計算はテンソル収縮問題に対応する。
第2に、テンソルの縮約配列を用いてGNNの表現性を評価するアルゴリズムツールを提案し、人気のあるGNNの表現力を算出する。
最後に,この理論に触発された多項式特徴や演算・集約を追加することで,共通gnnアーキテクチャの表現性を高める。
これらの強化されたGNNは、複数のグラフ学習ベンチマークの実験において最先端の結果を示す。
関連論文リスト
- Uplifting the Expressive Power of Graph Neural Networks through Graph
Partitioning [3.236774847052122]
グラフ分割のレンズによるグラフニューラルネットワークの表現力について検討する。
我々は新しいGNNアーキテクチャ、すなわちグラフ分割ニューラルネットワーク(GPNN)を導入する。
論文 参考訳(メタデータ) (2023-12-14T06:08:35Z) - 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) - Weisfeiler--Lehman goes Dynamic: An Analysis of the Expressive Power of
Graph Neural Networks for Attributed and Dynamic Graphs [1.1083289076967897]
グラフニューラルネットワーク(GNN)は、グラフ処理のための大規模なリレーショナルモデルである。
GNNの表現力に関する最近の研究は2つの問題に焦点を当てている。
本研究は汎用GNNモデルを考察し,これらの領域に対して適切な1-WLテストを提案する。
論文 参考訳(メタデータ) (2022-10-08T10:14:41Z) - Representation Power of Graph Neural Networks: Improved Expressivity via
Algebraic Analysis [124.97061497512804]
標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。
また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
論文 参考訳(メタデータ) (2022-05-19T18:40:25Z) - Expressiveness and Approximation Properties of Graph Neural Networks [6.1323142294300625]
Wesfeiler-Leman (WL) テストの観点で GNN の分離パワーのバウンダリを得るためのエレガントな方法を提供する。
我々はテンソル言語を用いて、MPNNの自然な拡張である高次メッセージパッシングニューラルネットワーク(またはk-MPNN)を定義する。
提案手法は,GNNアーキテクチャ設計者がGNNの分離パワーを解析できるツールボックスを提供する。
論文 参考訳(メタデータ) (2022-04-10T11:33:04Z) - Counting Substructures with Higher-Order Graph Neural Networks:
Possibility and Impossibility Results [58.277290855841976]
グラフニューラルネットワーク(GNN)の計算コストと表現力のトレードオフについて検討する。
新しいモデルでは、$k$のサブグラフをカウントでき、低次GNNの既知の制限を克服できることを示す。
いくつかの場合において、提案アルゴリズムは既存の高階$k$-GNNに比べて計算量を大幅に削減することができる。
論文 参考訳(メタデータ) (2020-12-06T03:42:54Z) - 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) - Distance Encoding: Design Provably More Powerful Neural Networks for
Graph Representation Learning [63.97983530843762]
グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。
GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。
より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。
本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
論文 参考訳(メタデータ) (2020-08-31T23:15:40Z) - Expressive Power of Invariant and Equivariant Graph Neural Networks [10.419350129060598]
Folklore Graph Neural Networks (FGNN) は、与えられたテンソル次数に対してこれまで提案されてきた最も表現力のあるアーキテクチャである。
FGNNはこの問題の解決方法を学ぶことができ、既存のアルゴリズムよりも平均的なパフォーマンスが向上する。
論文 参考訳(メタデータ) (2020-06-28T16:35:45Z) - Improving Graph Neural Network Expressivity via Subgraph Isomorphism
Counting [63.04999833264299]
グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。
Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。
グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
論文 参考訳(メタデータ) (2020-06-16T15:30:31Z) - Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs [95.63153473559865]
グラフニューラルネットワーク(GNN)は、グラフ上の新たな機械学習モデルである。
既存のGNNモデルの多くは浅く、本質的に機能中心である。
我々は,既存の浅いGNNがグラフ構造をよく保存できないことを経験的かつ解析的に示す。
本稿では,グラフ構造保存におけるGNNの能力を高めるプラグインモジュールであるEigen-GNNを提案する。
論文 参考訳(メタデータ) (2020-06-08T02:47:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。