論文の概要: An Empirical Study of Realized GNN Expressiveness

• arxiv url: http://arxiv.org/abs/2304.07702v4
• Date: Sat, 1 Jun 2024 08:37:02 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-04 21:39:44.248715
• Title: An Empirical Study of Realized GNN Expressiveness
• Title（参考訳）: 実効GNN表現性に関する実証的研究
• Authors: Yanbo Wang, Muhan Zhang,
• Abstract要約: 本稿では,実用的なモデルインスタンスが,新しい表現性データセットBRECを用いて実現可能な実感表現力について検討する。 BREC上で高-1-WL表現率23モデルを合成試験した。 本実験は,1-WL GNNモデルを超えるこれらの最先端の表現性について,その実感性を初めて徹底的に測定するものである。
• 参考スコア（独自算出の注目度）: 27.458151256734947
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Research on the theoretical expressiveness of Graph Neural Networks (GNNs) has developed rapidly, and many methods have been proposed to enhance the expressiveness. However, most methods do not have a uniform expressiveness measure except for a few that strictly follow the $k$-dimensional Weisfeiler-Lehman ($k$-WL) test hierarchy, leading to difficulties in quantitatively comparing their expressiveness. Previous research has attempted to use datasets for measurement, but facing problems with difficulty (any model surpassing 1-WL has nearly 100% accuracy), granularity (models tend to be either 100% correct or near random guess), and scale (only several essentially different graphs involved). To address these limitations, we study the realized expressive power that a practical model instance can achieve using a novel expressiveness dataset, BREC, which poses greater difficulty (with up to 4-WL-indistinguishable graphs), finer granularity (enabling comparison of models between 1-WL and 3-WL), a larger scale (consisting of 800 1-WL-indistinguishable graphs that are non-isomorphic to each other). We synthetically test 23 models with higher-than-1-WL expressiveness on BREC. Our experiment gives the first thorough measurement of the realized expressiveness of those state-of-the-art beyond-1-WL GNN models and reveals the gap between theoretical and realized expressiveness. Dataset and evaluation codes are released at: https://github.com/GraphPKU/BREC.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)の理論表現性の研究は急速に進展し,その表現性を高めるために多くの手法が提案されている。 しかしながら、ほとんどのメソッドは、$k$-次元のWeisfeiler-Lehman(k$-WL)テスト階層に厳密に従う数を除いて、一様表現性尺度を持たないため、それらの表現性を比較するのが困難である。 これまでの研究ではデータセットを計測に利用しようと試みてきたが、難易度(1-WLを超えるモデルは100%近い精度)、粒度(モデルは100%正しいかランダムに近い確率で推測される)、スケール(基本的にはいくつかの異なるグラフのみを含む)の問題に直面していた。 これらの制約に対処するために、実用モデルインスタンスが実現可能な表現力について、より難易度の高いBREC(4-WL非識別可能なグラフ)、より細かい粒度(1-WLと3-WLのモデルの比較)、より大きなスケール(800個の1-WL非同型グラフからなる)を用いて検討する。 BREC上で高-1-WL表現率23モデルを合成試験した。 本実験では, 従来の1-WL GNNモデルを超えて, 実現された表現性について, 理論的表現性と実現された表現性とのギャップを明らかにする。 データセットと評価コードは、https://github.com/GraphPKU/BRECでリリースされている。

関連論文リスト

• Path Neural Networks: Expressive and Accurate Graph Neural Networks [23.824156607376697]
  グラフニューラルネットワーク(GNN)は最近、グラフ構造化データによる学習の標準的なアプローチになっている。 本稿では,ノードからの経路を集約することでノード表現を更新するPathNNを提案する。 これらの2つの変種は1-WLアルゴリズムよりも厳密に強力であることが証明され、理論的結果が実験的に検証された。
  論文  参考訳（メタデータ） (2023-06-09T15:11:49Z)
• Probing Graph Representations [77.7361299039905]
  グラフ表現でキャプチャされた意味のある情報の量を定量化するために、探索フレームワークを使用します。 本研究は, グラフモデルにおける帰納的バイアスを理解するための探索の可能性を示すものである。 グラフベースモデルを評価する上で有用な診断ツールとして,探索を提唱する。
  論文  参考訳（メタデータ） (2023-03-07T14:58:18Z)
• 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)
• Less is More: SlimG for Accurate, Robust, and Interpretable Graph Mining [16.44814089547141]
  グラフニューラルネットワーク(GNN)は多くのグラフマイニングタスクに成功しているが、様々なグラフシナリオへの一般化性は限られている。 本研究では,4つの望ましい特性を示す半教師付きノード分類のためのSlimGを提案する。 グラフデータのすべてのシナリオを処理するのは(a)正確で、13の現実世界のデータセットのうち10つ中10つであり、(b)堅牢で、(d)線形性と疎性のおかげで解釈可能である。
  論文  参考訳（メタデータ） (2022-10-08T18:24:36Z)
• 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)
• 1-WL Expressiveness Is (Almost) All You Need [3.4012007729454807]
  メッセージパッシングニューラルネットワーク (MPNN) は、一階のWeisfeiler-Leman (1-WL) グラフ同型テストと同型である。 本研究では,MPNNや他の標準グラフデータセットのWLモデルにおいて,限定表現性が実際に制限要因であるかどうかを解析する。
  論文  参考訳（メタデータ） (2022-02-21T12:05:06Z)
• Distributionally Robust Semi-Supervised Learning Over Graphs [68.29280230284712]
  グラフ構造化データに対する半教師付き学習(SSL)は、多くのネットワークサイエンスアプリケーションに現れる。 グラフ上の学習を効率的に管理するために,近年,グラフニューラルネットワーク(GNN)の変種が開発されている。 実際に成功したにも拘わらず、既存の手法のほとんどは、不確実な結節属性を持つグラフを扱うことができない。 ノイズ測定によって得られたデータに関連する分布の不確実性によっても問題が発生する。 分散ロバストな学習フレームワークを開発し,摂動に対する定量的ロバスト性を示すモデルを訓練する。
  論文  参考訳（メタデータ） (2021-10-20T14:23:54Z)
• Combining Label Propagation and Simple Models Out-performs Graph Neural Networks [52.121819834353865]
  多くの標準的なトランスダクティブノード分類ベンチマークでは、最先端のGNNの性能を超えたり、一致させることができる。 これをC&S(Correct and Smooth)と呼ぶ。 我々のアプローチは、様々なベンチマークで最先端のGNNの性能を上回るか、ほぼ一致している。
  論文  参考訳（メタデータ） (2020-10-27T02:10:52Z)
• 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)

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

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