論文の概要: 1-WL Expressiveness Is (Almost) All You Need

• arxiv url: http://arxiv.org/abs/2202.10156v1
• Date: Mon, 21 Feb 2022 12:05:06 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-23 09:54:17.809748
• Title: 1-WL Expressiveness Is (Almost) All You Need
• Title（参考訳）: 1-WL表現性は(ほとんど)必要なもの
• Authors: Markus Zopf
• Abstract要約: メッセージパッシングニューラルネットワーク (MPNN) は、一階のWeisfeiler-Leman (1-WL) グラフ同型テストと同型である。 本研究では,MPNNや他の標準グラフデータセットのWLモデルにおいて,限定表現性が実際に制限要因であるかどうかを解析する。
• 参考スコア（独自算出の注目度）: 3.4012007729454807
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: It has been shown that a message passing neural networks (MPNNs), a popular family of neural networks for graph-structured data, are at most as expressive as the first-order Weisfeiler-Leman (1-WL) graph isomorphism test, which has motivated the development of more expressive architectures. In this work, we analyze if the limited expressiveness is actually a limiting factor for MPNNs and other WL-based models in standard graph datasets. Interestingly, we find that the expressiveness of WL is sufficient to identify almost all graphs in most datasets. Moreover, we find that the classification accuracy upper bounds are often close to 100\%. Furthermore, we find that simple WL-based neural networks and several MPNNs can be fitted to several datasets. In sum, we conclude that the performance of WL/MPNNs is not limited by their expressiveness in practice.
• Abstract（参考訳）: グラフ構造化データのための一般的なニューラルネットワークのファミリーであるメッセージパッシングニューラルネットワーク(mpnns)は、より表現力のあるアーキテクチャの開発を動機づけた1次ワイスフェイラー・リーマン(1-wl)グラフ同型テストと同じくらい表現力が高いことが示されている。 本研究では,MPNNや他の標準グラフデータセットのWLモデルにおいて,限定表現性が実際に制限要因であるかどうかを解析する。 興味深いことに、WLの表現性は、ほとんどのデータセットでほぼ全てのグラフを識別するのに十分である。 さらに,分類精度の上限値が100\%に近い場合も少なくないことがわかった。 さらに、単純なWLベースのニューラルネットワークといくつかのMPNNを複数のデータセットに適合させることができる。 要約すると、WL/MPNNの性能は、実際は表現力によって制限されない。

関連論文リスト

• An Empirical Study of Realized GNN Expressiveness [27.458151256734947]
  本稿では,実用的なモデルインスタンスが,新しい表現性データセットBRECを用いて実現可能な実感表現力について検討する。 BREC上で高-1-WL表現率23モデルを合成試験した。 本実験は,1-WL GNNモデルを超えるこれらの最先端の表現性について,その実感性を初めて徹底的に測定するものである。
  論文  参考訳（メタデータ） (2023-04-16T05:53:47Z)
• On the Expressiveness and Generalization of Hypergraph Neural Networks [77.65788763444877]
  この拡張抽象化はハイパーグラフニューラルネットワーク(HyperGNN)の表現性、学習、および(構造的)一般化を分析するためのフレームワークを記述する。 具体的には、HyperGNNが有限データセットからどのように学習し、任意の入力サイズのグラフ推論問題に構造的に一般化するかに焦点を当てる。
  論文  参考訳（メタデータ） (2023-03-09T18:42:18Z)
• 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)
• Graph Representation Learning with Individualization and Refinement [19.436520792345064]
  グラフニューラルネットワーク(GNN)は、グラフ構造化データ上での表現学習の顕著なモデルとして登場した。 本研究では、個人化・再分極(IR)の古典的アプローチに従う。 我々の手法は、計算複雑性を管理しつつ、よりリッチなノード埋め込みを学習することを可能にする。
  論文  参考訳（メタデータ） (2022-03-17T07:50:48Z)
• Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
  グラフニューラルネットワーク(GNN)は、構造データのモデリングにおいて強力な能力を示している。 GMPTと呼ばれる新しいグラフマッチングベースのGNN事前学習フレームワークを提案する。 提案手法は,完全自己指導型プレトレーニングと粗粒型プレトレーニングに適用できる。
  論文  参考訳（メタデータ） (2022-03-03T09:53:53Z)
• Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results [58.277290855841976]
  グラフニューラルネットワーク(GNN)の計算コストと表現力のトレードオフについて検討する。 新しいモデルでは、$k$のサブグラフをカウントでき、低次GNNの既知の制限を克服できることを示す。 いくつかの場合において、提案アルゴリズムは既存の高階$k$-GNNに比べて計算量を大幅に削減することができる。
  論文  参考訳（メタデータ） (2020-12-06T03:42:54Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)

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

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