論文の概要: Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness

• arxiv url: http://arxiv.org/abs/2401.08514v1
• Date: Tue, 16 Jan 2024 17:23:23 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-18 19:05:25.305676
• Title: Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness
• Title（参考訳）: Weisfeiler-Lehman氏: GNN表現性のための定量的フレームワーク
• Authors: Bohang Zhang, Jingchu Gai, Yiheng Du, Qiwei Ye, Di He, Liwei Wang
• Abstract要約: 準同型表現性は、GNNモデルが準同型の下でグラフを数える能力を測定する。 ケーススタディとして著名なGNNの4つのクラスを調べることで、それらの同型表現の単純で統一的でエレガントな記述を導き出す。 本研究の結果は, 過去の一連の研究に対する新たな洞察を与え, 地域社会における様々なサブアレスの景観を統一し, いくつかのオープンな疑問を解決した。
• 参考スコア（独自算出の注目度）: 35.409017863665575
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Designing expressive Graph Neural Networks (GNNs) is a fundamental topic in the graph learning community. So far, GNN expressiveness has been primarily assessed via the Weisfeiler-Lehman (WL) hierarchy. However, such an expressivity measure has notable limitations: it is inherently coarse, qualitative, and may not well reflect practical requirements (e.g., the ability to encode substructures). In this paper, we introduce a unified framework for quantitatively studying the expressiveness of GNN architectures, addressing all the above limitations. Specifically, we identify a fundamental expressivity measure termed homomorphism expressivity, which quantifies the ability of GNN models to count graphs under homomorphism. Homomorphism expressivity offers a complete and practical assessment tool: the completeness enables direct expressivity comparisons between GNN models, while the practicality allows for understanding concrete GNN abilities such as subgraph counting. By examining four classes of prominent GNNs as case studies, we derive simple, unified, and elegant descriptions of their homomorphism expressivity for both invariant and equivariant settings. Our results provide novel insights into a series of previous work, unify the landscape of different subareas in the community, and settle several open questions. Empirically, extensive experiments on both synthetic and real-world tasks verify our theory, showing that the practical performance of GNN models aligns well with the proposed metric.
• Abstract（参考訳）: 表現型グラフニューラルネットワーク(gnns)の設計は、グラフ学習コミュニティの基本的なトピックである。 これまでのところ、GNN表現性は主にWeisfeiler-Lehman(WL)階層を通して評価されてきた。 しかし、そのような表現度尺度は、本質的に粗く質的であり、実際的な要件(例えば、部分構造をエンコードする能力)を十分に反映していない。 本稿では,GNNアーキテクチャの表現性を定量的に研究するための統一的なフレームワークを提案する。 具体的には、gnnモデルが準同型の下でグラフを数える能力を定量化する基本表現性測度を準同型表現性と呼ぶ。 完全性はGNNモデル間の直接的表現性比較を可能にし、実用性はサブグラフカウントのような具体的なGNN能力を理解することができる。 ケーススタディとして著名なGNNの4つのクラスを調べることで、同型表現の単純で統一的でエレガントな記述を、不変条件と同変条件の両方に対して導き出す。 これまでの一連の研究に新たな洞察を与え,コミュニティ内のさまざまなサブエリアの景観を統一し,いくつかの疑問を解決した。 実証実験により,GNNモデルの実用性能が提案手法とよく一致していることが確認された。

関連論文リスト

• Towards Bridging Generalization and Expressivity of Graph Neural Networks [11.560730203511111]
  グラフニューラルネットワーク(GNN)における表現性と一般化の関係について検討する。 本稿では,GNNの一般化と,それらが捉えることのできるグラフ構造の分散を結合する新しいフレームワークを提案する。 我々は,クラス内濃度とクラス間分離のトレードオフを明らかにする。
  論文  参考訳（メタデータ） (2024-10-14T00:31:16Z)
• Fine-Grained Expressive Power of Weisfeiler-Leman: A Homomorphism Counting Perspective [24.729126775414922]
  グラフニューラルネットワークの任意のクラス(GNN)の準同型カウント能力を決定するための理論的枠組みを提供する。 検討されている設計空間は、既知の強力なGNNのほとんどすべてに対応するのに十分の大きさであるので、我々の結果は既存のすべての作業を大幅に拡張し、GNNモデル設計の自動化にその応用を見出すことができるかもしれない。
  論文  参考訳（メタデータ） (2024-10-04T15:36:48Z)
• On the Expressive Power of Graph Neural Networks [0.0]
  グラフニューラルネットワーク(GNN)は、社会科学、化学、医学といった分野における様々なタスクを解くことができる。 ディープラーニングをグラフ構造化データに拡張することにより、GNNは、社会科学、化学、医学といった分野におけるさまざまなタスクを解決できる。
  論文  参考訳（メタデータ） (2024-01-03T08:54:56Z)
• Generalization Limits of Graph Neural Networks in Identity Effects Learning [12.302336258860116]
  グラフニューラルネットワーク(GNN)は、さまざまなグラフドメインでデータ駆動学習を行う強力なツールとして登場した。 我々は、いわゆるアイデンティティ効果の学習において、GNNの新たな一般化特性と基本的限界を確立する。 我々の研究は、単純な認知タスクを行う際に、GNNの能力を理解する必要性によって動機付けられている。
  論文  参考訳（メタデータ） (2023-06-30T20:56: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)
• Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPs [71.93227401463199]
  本稿では、P(ropagational)MLPと呼ばれる中間モデルクラスを導入することにより、GNNの性能向上を本質的な能力に向ける。 PMLPは、トレーニングにおいてはるかに効率的でありながら、GNNと同等(あるいはそれ以上)に動作することを観察する。
  論文  参考訳（メタデータ） (2022-12-18T08:17:32Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• 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)
• Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs [95.63153473559865]
  グラフニューラルネットワーク(GNN)は、グラフ上の新たな機械学習モデルである。 既存のGNNモデルの多くは浅く、本質的に機能中心である。 我々は,既存の浅いGNNがグラフ構造をよく保存できないことを経験的かつ解析的に示す。 本稿では,グラフ構造保存におけるGNNの能力を高めるプラグインモジュールであるEigen-GNNを提案する。
  論文  参考訳（メタデータ） (2020-06-08T02:47:38Z)
• Node Masking: Making Graph Neural Networks Generalize and Scale Better [71.51292866945471]
  グラフニューラルネットワーク(GNN)は近年,多くの関心を集めている。 本稿では,芸術空間のGNNの状態によって実行される操作をよりよく可視化するために,いくつかの理論ツールを利用する。 私たちはNode Maskingというシンプルなコンセプトを導入しました。
  論文  参考訳（メタデータ） (2020-01-17T06:26:40Z)

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

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