論文の概要: On the Expressive Power of Geometric Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2301.09308v1
- Date: Mon, 23 Jan 2023 08:08:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-24 14:02:18.310007
- Title: On the Expressive Power of Geometric Graph Neural Networks
- Title(参考訳): 幾何学的グラフニューラルネットワークの表現力について
- Authors: Chaitanya K. Joshi, Cristian Bodnar, Simon V. Mathis, Taco Cohen,
Pietro Li\`o
- Abstract要約: 基礎となる物理対称性を尊重しながら幾何グラフを識別するための幾何版WLテスト(GWL)を提案する。
鍵となる設計選択が幾何的GNN表現性に与える影響を解き放つ。
- 参考スコア(独自算出の注目度): 12.037054246020954
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The expressive power of Graph Neural Networks (GNNs) has been studied
extensively through the Weisfeiler-Leman (WL) graph isomorphism test. However,
standard GNNs and the WL framework are inapplicable for geometric graphs
embedded in Euclidean space, such as biomolecules, materials, and other
physical systems. In this work, we propose a geometric version of the WL test
(GWL) for discriminating geometric graphs while respecting the underlying
physical symmetries: permutations, rotation, reflection, and translation. We
use GWL to characterise the expressive power of geometric GNNs that are
invariant or equivariant to physical symmetries in terms of distinguishing
geometric graphs. GWL unpacks how key design choices influence geometric GNN
expressivity: (1) Invariant layers have limited expressivity as they cannot
distinguish one-hop identical geometric graphs; (2) Equivariant layers
distinguish a larger class of graphs by propagating geometric information
beyond local neighbourhoods; (3) Higher order tensors and scalarisation enable
maximally powerful geometric GNNs; and (4) GWL's discrimination-based
perspective is equivalent to universal approximation. Synthetic experiments
supplementing our results are available at
https://github.com/chaitjo/geometric-gnn-dojo
- Abstract(参考訳): グラフニューラルネットワーク(GNN)の表現力はWeisfeiler-Leman(WL)グラフ同型テストを通じて広く研究されている。
しかし、標準GNNとWLフレームワークは、生体分子、材料、その他の物理系などのユークリッド空間に埋め込まれた幾何学グラフには適用できない。
本研究では,幾何学的グラフを識別するための幾何版WLテスト(GWL)を提案し,その基礎となる物理対称性(置換,回転,反射,変換)を尊重する。
我々はGWLを用いて、幾何学グラフの区別の観点から、物理対称性に不変または同変である幾何学的GNNの表現力を特徴づける。
GWLは, 鍵設計選択が幾何的GNN表現性にどのように影響するかを解き明かす。(1) 不変層は, 1ホップの同一幾何グラフを区別できないため, 有限表現性を持つ; (2) 等変層は, 局所的に幾何学情報を伝播させることにより, グラフのより大きなクラスを区別する; (3) 高次テンソルとスカラー化により, 最大で強力な幾何的GNNを可能にする;(4) GWLの識別に基づく視点は普遍近似と等価である。
私たちの結果を補う合成実験はhttps://github.com/chaitjo/geometric-gnn-dojoで利用可能です。
関連論文リスト
- 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) - Graph Neural Networks Are More Powerful Than we Think [124.97061497512804]
グラフニューラルネットワーク(GNN)は、様々なノードレベルおよびグラフレベルタスクにおいて顕著なパフォーマンスを示す強力な畳み込みアーキテクチャである。
彼らの成功にもかかわらず、GNNの表現力は限られており、Weisfeiler-Lehman (WL)アルゴリズムと同じくらい差別的であるという共通の信念がある。
GNNは、少なくとも1つの固有値が異なるグラフと、WLアルゴリズムよりも確実に表現可能な単純なGNNアーキテクチャを区別できることを示す。
論文 参考訳(メタデータ) (2022-05-19T18:40:25Z) - The Exact Class of Graph Functions Generated by Graph Neural Networks [43.25172578943894]
グラフ関数と出力が同一のグラフニューラルネットワーク(GNN)?
本稿では,この疑問に完全に答え,GNNで表現可能なグラフ問題のクラスを特徴付ける。
この条件は2次的に多くの制約をチェックすることで効率よく検証できることを示す。
論文 参考訳(メタデータ) (2022-02-17T18:54:27Z) - Geometrically Equivariant Graph Neural Networks: A Survey [44.73146997637709]
GNNにおけるメッセージパッシングとアグリゲーションの表現方法に関して,既存の手法を3つのグループに分けて分析・分類する。
また、ベンチマークと関連するデータセットを要約し、方法論開発と実験評価のための後の研究を促進する。
論文 参考訳(メタデータ) (2022-02-15T07:12:21Z) - Graph Neural Networks with Learnable Structural and Positional
Representations [83.24058411666483]
任意のグラフの大きな問題は、ノードの標準位置情報の欠如である。
ノードの位置ノード(PE)を導入し、Transformerのように入力層に注入する。
両方のGNNクラスで学習可能なPEを考えると、分子データセットのパフォーマンスは2.87%から64.14%に向上する。
論文 参考訳(メタデータ) (2021-10-15T05:59:15Z) - Graph Neural Networks with Local Graph Parameters [1.8600631687568656]
ローカルグラフパラメータは、任意のグラフニューラルネットワーク(GNN)アーキテクチャに追加することができる。
我々の結果は、有限モデル理論と有限変数論理の深い結果とGNNを結びつける。
論文 参考訳(メタデータ) (2021-06-12T07:43:51Z) - 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) - Gauge Equivariant Mesh CNNs: Anisotropic convolutions on geometric
graphs [81.12344211998635]
メッシュ上の畳み込みを定義する一般的なアプローチは、それらをグラフとして解釈し、グラフ畳み込みネットワーク(GCN)を適用することである。
本稿では、GCNを一般化して異方性ゲージ同変カーネルを適用するGauge Equivariant Mesh CNNを提案する。
本実験は,従来のGCNおよび他の手法と比較して,提案手法の表現性を大幅に向上することを示した。
論文 参考訳(メタデータ) (2020-03-11T17:21:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。