論文の概要: Rethinking the Expressive Power of GNNs via Graph Biconnectivity

• arxiv url: http://arxiv.org/abs/2301.09505v3
• Date: Sun, 11 Feb 2024 03:44:23 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-14 01:31:40.415979
• Title: Rethinking the Expressive Power of GNNs via Graph Biconnectivity
• Title（参考訳）: グラフ結合によるGNNの表現力の再考
• Authors: Bohang Zhang, Shengjie Luo, Liwei Wang, Di He
• Abstract要約: 本稿では,グラフ双連結性による表現度指標の新たなクラスを導入し,理論と実践の両面での重要性を強調した。 我々は、GD-WL(Generalized Distance Weisfeiler-Lehman)と呼ばれる原理的で効率的なアプローチを導入する。 実際に,GD-WLをTransformerのようなアーキテクチャで実装し,完全な並列化性を保ち,実現可能であることを示す。
• 参考スコア（独自算出の注目度）: 45.4674360883544
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Designing expressive Graph Neural Networks (GNNs) is a central topic in learning graph-structured data. While numerous approaches have been proposed to improve GNNs in terms of the Weisfeiler-Lehman (WL) test, generally there is still a lack of deep understanding of what additional power they can systematically and provably gain. In this paper, we take a fundamentally different perspective to study the expressive power of GNNs beyond the WL test. Specifically, we introduce a novel class of expressivity metrics via graph biconnectivity and highlight their importance in both theory and practice. As biconnectivity can be easily calculated using simple algorithms that have linear computational costs, it is natural to expect that popular GNNs can learn it easily as well. However, after a thorough review of prior GNN architectures, we surprisingly find that most of them are not expressive for any of these metrics. The only exception is the ESAN framework, for which we give a theoretical justification of its power. We proceed to introduce a principled and more efficient approach, called the Generalized Distance Weisfeiler-Lehman (GD-WL), which is provably expressive for all biconnectivity metrics. Practically, we show GD-WL can be implemented by a Transformer-like architecture that preserves expressiveness and enjoys full parallelizability. A set of experiments on both synthetic and real datasets demonstrates that our approach can consistently outperform prior GNN architectures.
• Abstract（参考訳）: 表現型グラフニューラルネットワーク(gnns)の設計は、グラフ構造化データを学ぶ上で重要なトピックである。 Weisfeiler-Lehman (WL) テストにおいて、GNNを改善するための多くのアプローチが提案されているが、一般的には、それらが体系的かつ確実に得られる追加のパワーについて深い理解がない。 本稿では,WLテスト以外のGNNの表現力について,根本的に異なる視点で検討する。 具体的には,グラフバイコネクティビティを用いた新しい表現性指標のクラスを導入し,理論と実践の両方においてその重要性を強調する。 線形計算コストの単純なアルゴリズムで双連結性を容易に計算できるため、一般的なGNNでも容易に学習できると期待することは当然である。 しかし、以前のGNNアーキテクチャを徹底的にレビューした結果、これらの指標のほとんどに表現力がないことがわかった。 唯一の例外は、esanフレームワークであり、その能力の理論的正当性を与える。 両接続性指標すべてに対して確実に表現可能な一般距離ワイスフェイラーレーマン(GD-WL)と呼ばれる原理的かつ効率的なアプローチを導入する。 GD-WLは,表現性を保ち,完全な並列性を楽しむトランスフォーマーのようなアーキテクチャで実装可能であることを示す。 合成データセットと実データセットの両方に関する一連の実験は、我々のアプローチが従来のGNNアーキテクチャよりも一貫して優れていることを示した。

関連論文リスト

• From Relational Pooling to Subgraph GNNs: A Universal Framework for More Expressive Graph Neural Networks [8.121462458089141]
  メッセージパッシングニューラルネットワークの表現力を向上させるために、ノードにラベルを割り当てる方法を示す。 実験により,本手法は普遍的に互換性があり,任意のベースGNNモデルの表現性を向上させることができることを示した。 私たちの$k,l$-GNNは、多くの合成および実世界のデータセットで優れたパフォーマンスを実現しています。
  論文  参考訳（メタデータ） (2023-05-08T18:00:50Z)
• Equivariant Polynomials for Graph Neural Networks [38.15983687193912]
  グラフネットワーク(GNN)は本質的に表現力に制限がある。 本稿では、GNNがある程度の同変を計算する能力に基づく代替パワー階層を提案する。 これらの強化されたGNNは、複数のグラフ学習ベンチマークの実験において最先端の結果を示す。
  論文  参考訳（メタデータ） (2023-02-22T18:53:38Z)
• 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)
• A Practical, Progressively-Expressive GNN [27.267362661067285]
  近年,メッセージパッシングニューラルネットワーク(MPNN)がグラフニューラルネットワーク(GNN)の主流となっている。 MPNNは、グラフ同型テストのフレームワークにおいてグラフを区別する1次元のWeisfeiler-Leman (1-WL)テストと同じくらい強力である。 我々は,k-tuples ノードから =c 連結成分上で定義された=k ノードの集合へ移動することで,k-WL から k-WL への複雑性を大幅に低減した (k, c)(=)-SETWL 階層を提案する。
  論文  参考訳（メタデータ） (2022-10-18T01:27:21Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth [57.10183643449905]
  グラフニューラルネットワーク(GNN)は表現力と一般化のレンズから研究されている。 GNNのダイナミクスを深部スキップ最適化により研究する。 本研究は,GNNの成功に対する最初の理論的支援を提供する。
  論文  参考訳（メタデータ） (2021-05-10T17:59:01Z)
• 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)
• Node Masking: Making Graph Neural Networks Generalize and Scale Better [71.51292866945471]
  グラフニューラルネットワーク(GNN)は近年,多くの関心を集めている。 本稿では,芸術空間のGNNの状態によって実行される操作をよりよく可視化するために,いくつかの理論ツールを利用する。 私たちはNode Maskingというシンプルなコンセプトを導入しました。
  論文  参考訳（メタデータ） (2020-01-17T06:26:40Z)

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

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