論文の概要: Towards Better Evaluation of GNN Expressiveness with BREC Dataset
- arxiv url: http://arxiv.org/abs/2304.07702v3
- Date: Mon, 3 Jul 2023 07:10:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-04 13:54:04.255017
- 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表現率を持つ23のモデルを合成試験した。
我々の実験は、これらの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 23 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表現率23モデルを合成試験した。
我々の実験は、これらの1-WL GNNモデルを超える最先端の表現性を初めて徹底的に比較した。
我々は、このデータセットが将来のGNNの表現性をテストするためのベンチマークになることを期待している。
データセットと評価コードは、https://github.com/GraphPKU/BREC.comで公開されています。
関連論文リスト
- Challenging the Myth of Graph Collaborative Filtering: a Reasoned and
Reproducibility-driven Analysis [69.46993865095247]
本稿では,6つの人気グラフと最近のグラフ推薦モデルの結果を再現するコードを提案する。
これらのグラフモデルと従来の協調フィルタリングモデルを比較する。
ユーザの近所からの情報フローを調べることにより,データセット構造における内在的特徴にどのようなモデルが影響するかを同定することを目的とする。
論文 参考訳(メタデータ) (2023-08-01T09:31:44Z) - A Simple and Scalable Graph Neural Network for Large Directed Graphs [11.792826520370774]
入力グラフ内のノード表現とエッジ方向認識の様々な組み合わせについて検討する。
そこで本研究では,A2DUGを簡易かつ包括的に分類する手法を提案する。
我々は、A2DUGが様々なデータセットで安定して動作し、最先端の手法と比較して11.29まで精度が向上することを示した。
論文 参考訳(メタデータ) (2023-06-14T06:24:58Z) - GCNH: A Simple Method For Representation Learning On Heterophilous
Graphs [4.051099980410583]
グラフニューラルネットワーク(GNN)は、ホモフィルグラフの学習に適している。
近年,異種グラフの性能向上を目的とした標準GNNアーキテクチャの拡張が提案されている。
ヘテロフィリィ(GCNH)のためのGCNを提案し,ヘテロフィリィシナリオとホモフィリィシナリオの両方に適用できる簡易かつ効果的なGNNアーキテクチャを提案する。
論文 参考訳(メタデータ) (2023-04-21T11:26:24Z) - 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) - 1-WL Expressiveness Is (Almost) All You Need [3.4012007729454807]
メッセージパッシングニューラルネットワーク (MPNN) は、一階のWeisfeiler-Leman (1-WL) グラフ同型テストと同型である。
本研究では,MPNNや他の標準グラフデータセットのWLモデルにおいて,限定表現性が実際に制限要因であるかどうかを解析する。
論文 参考訳(メタデータ) (2022-02-21T12:05:06Z) - 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) - Graph Contrastive Learning with Augmentations [109.23158429991298]
グラフデータの教師なし表現を学習するためのグラフコントラスト学習(GraphCL)フレームワークを提案する。
我々のフレームワークは、最先端の手法と比較して、類似またはより良い一般化可能性、転送可能性、堅牢性のグラフ表現を作成できることを示す。
論文 参考訳(メタデータ) (2020-10-22T20:13:43Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。