論文の概要: Towards Better Evaluation of GNN Expressiveness with BREC Dataset

• arxiv url: http://arxiv.org/abs/2304.07702v2
• Date: Mon, 8 May 2023 10:05:01 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-09 20:38:35.171176
• Title: Towards Better Evaluation of GNN Expressiveness with BREC Dataset
• Title（参考訳）: BRECデータセットを用いたGNN表現性向上に向けて
• Authors: Yanbo Wang, Muhan Zhang
• Abstract要約: $textbfBREC$は、4つの主要なカテゴリから慎重に選択された400組の非同型グラフを含む。 BRECデータセット上で,高い-1-WL表現率を持つ16のモデルを合成試験した。 我々の実験は、これらの1-WL GNNモデルを超える最先端の表現性を初めて徹底的に比較したものである。
• 参考スコア（独自算出の注目度）: 14.81226562631374
• 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. Their theoretical analyses are often limited to distinguishing certain families of non-isomorphic graphs, leading to difficulties in quantitatively comparing their expressiveness. In contrast to theoretical analysis, another way to measure expressiveness is by evaluating model performance on certain datasets containing 1-WL-indistinguishable graphs. Previous datasets specifically designed for this purpose, however, face 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 a few essentially different graphs in each dataset). To address these limitations, we propose a new expressiveness dataset, $\textbf{BREC}$, which includes 400 pairs of non-isomorphic graphs carefully selected from four primary categories (Basic, Regular, Extension, and CFI). These graphs have higher difficulty (up to 4-WL-indistinguishable), finer granularity (able to compare models between 1-WL and 3-WL), and a larger scale (400 pairs). Further, we synthetically test 16 models with higher-than-1-WL expressiveness on our BREC dataset. Our experiment gives the first thorough comparison of the expressiveness of those state-of-the-art beyond-1-WL GNN models. We expect this dataset to serve as a benchmark for testing the expressiveness of future GNNs. Our dataset and evaluation code are released at: https://github.com/GraphPKU/BREC.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)の理論表現性の研究は急速に進展し,その表現性を高めるために多くの手法が提案されている。 しかしながら、ほとんどのメソッドは、$k$-次元Weisfeiler-Lehman(k$-WL)テスト階層に厳密に従う数を除いて、一様表現性尺度を持たない。 それらの理論解析は、しばしば非同型グラフの特定の族を区別することに限定され、その表現性を定量的に比較することが困難となる。 理論的解析とは対照的に、表現性を測定する別の方法は、1-WL非識別グラフを含む特定のデータセット上でのモデル性能を評価することである。 しかし、この目的のために特別に設計された以前のデータセットは、難易度(1-WLを超えるモデルは100%近い精度)、粒度(モデルは100%正しいかランダムに近い確率で推測される)、スケール(各データセットで本質的に異なるグラフのみ)の問題に直面している。 これらの制約に対処するため、我々は4つの主要なカテゴリ(Basic, Regular, Extension, CFI)から慎重に選択された400組の非同型グラフを含む新しい表現性データセット、$\textbf{BREC}$を提案する。 これらのグラフはより難易度が高く(最大4-WLは区別できない)、より細かい粒度(1-WLと3-WLのモデルを比較することができる)、より大きなスケール(400対)を持つ。 さらに、BRECデータセット上で、高い-1-WL表現率を持つ16のモデルを合成試験した。 我々の実験は、これらの1-WL GNNモデルを超える最先端の表現性を初めて徹底的に比較した。 我々は、このデータセットが将来のGNNの表現性をテストするためのベンチマークになることを期待している。 データセットと評価コードは、https://github.com/GraphPKU/BREC.comで公開されています。

関連論文リスト

• Enhanced Expressivity in Graph Neural Networks with Lanczos-Based Linear Constraints [7.605749412696919]
  グラフニューラルネットワーク(GNN)はグラフ構造化データの処理に優れるが、リンク予測タスクでは性能が劣ることが多い。 グラフラプラシア行列の固有基底に誘導された部分グラフを埋め込むことによりGNNの表現性を高める新しい手法を提案する。 提案手法は,PubMedとOGBL-Vesselのデータセットから,5%と10%のデータしか必要とせず,20倍と10倍の高速化を実現する。
  論文  参考訳（メタデータ） (2024-08-22T12:22:00Z)
• 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)
• 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)

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

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