論文の概要: Weisfeiler and Leman Go Measurement Modeling: Probing the Validity of the WL Test
- arxiv url: http://arxiv.org/abs/2307.05775v3
- Date: Sun, 31 Mar 2024 17:03:00 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-02 15:54:17.596311
- Title: Weisfeiler and Leman Go Measurement Modeling: Probing the Validity of the WL Test
- Title(参考訳): Weisfeiler と Leman Go の測定モデル: WL テストの有効性の検証
- Authors: Arjun Subramonian, Adina Williams, Maximilian Nickel, Yizhou Sun, Levent Sagun,
- Abstract要約: グラフ機械学習実践者の表現力概念化と$k$-WLとの相違を明らかにする。
ベンチマークに基づく表現力の拡張的定義と測定について論じる。
- 参考スコア(独自算出の注目度): 58.1543112860658
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The expressive power of graph neural networks is usually measured by comparing how many pairs of graphs or nodes an architecture can possibly distinguish as non-isomorphic to those distinguishable by the $k$-dimensional Weisfeiler-Leman ($k$-WL) test. In this paper, we uncover misalignments between graph machine learning practitioners' conceptualizations of expressive power and $k$-WL through a systematic analysis of the reliability and validity of $k$-WL. We conduct a survey ($n = 18$) of practitioners to surface their conceptualizations of expressive power and their assumptions about $k$-WL. In contrast to practitioners' beliefs, our analysis (which draws from graph theory and benchmark auditing) reveals that $k$-WL does not guarantee isometry, can be irrelevant to real-world graph tasks, and may not promote generalization or trustworthiness. We argue for extensional definitions and measurement of expressive power based on benchmarks. We further contribute guiding questions for constructing such benchmarks, which is critical for graph machine learning practitioners to develop and transparently communicate our understandings of expressive power.
- Abstract(参考訳): グラフニューラルネットワークの表現力は、通常、アーキテクチャが$k$-dimensional Weisfeiler-Leman(k$-WL)テストで区別できるグラフやノードの数を比較することで測定される。
本稿では,グラフ学習実践者の表現力の概念化と$k$-WLの信頼性と妥当性の体系的分析により,グラフ機械学習実践者のミスアライメントを明らかにする。
我々は,表現力の概念化と約$k$-WLの仮定を明らかにするために,実践者の調査(n = 18$)を行う。
実践者の信念とは対照的に、我々の分析(グラフ理論とベンチマーク監査から導かれる)は、$k$-WLは等尺性を保証せず、現実世界のグラフタスクとは無関係であり、一般化や信頼性を促進できないことを明らかにしている。
ベンチマークに基づく表現力の拡張的定義と測定について論じる。
グラフ機械学習の実践者にとって、表現力の理解を深め、透過的に伝達することが重要である。
関連論文リスト
- Generalization Limits of Graph Neural Networks in Identity Effects
Learning [12.302336258860116]
グラフニューラルネットワーク(GNN)は、さまざまなグラフドメインでデータ駆動学習を行う強力なツールとして登場した。
我々は、いわゆるアイデンティティ効果の学習において、GNNの新たな一般化特性と基本的限界を確立する。
我々の研究は、単純な認知タスクを行う際に、GNNの能力を理解する必要性によって動機付けられている。
論文 参考訳(メタデータ) (2023-06-30T20:56:38Z) - Fine-grained Expressivity of Graph Neural Networks [15.766353435658043]
我々は1ドルWLとMPNNの連続的な拡張をグラファイトに検討する。
連続的な1ドルWLの変動は,MPNNのグラフ上での表現力の正確なトポロジ的特徴を与えることを示す。
また,グラフ距離の保存能力に基づいて,異なるMPNNアーキテクチャの評価を行った。
論文 参考訳(メタデータ) (2023-06-06T14:12:23Z) - Three iterations of $(d-1)$-WL test distinguish non isometric clouds of
$d$-dimensional points [58.9648095506484]
Wesfeiler--Lehman テストが完全距離グラフで表されるユークリッド点の雲に対して完備であるときの研究を行う。
我々の主な結果は、$(d-1)$-dimensional WL テストが$d$-dimensional Euclidean 空間の点雲に対して完備であり、任意の$dge 2$ に対して完備であり、テストサフィスを3回だけ繰り返すことである。
論文 参考訳(メタデータ) (2023-03-22T18:23:24Z) - Probing Graph Representations [77.7361299039905]
グラフ表現でキャプチャされた意味のある情報の量を定量化するために、探索フレームワークを使用します。
本研究は, グラフモデルにおける帰納的バイアスを理解するための探索の可能性を示すものである。
グラフベースモデルを評価する上で有用な診断ツールとして,探索を提唱する。
論文 参考訳(メタデータ) (2023-03-07T14:58:18Z) - Rethinking the Expressive Power of GNNs via Graph Biconnectivity [45.4674360883544]
本稿では,グラフ双連結性による表現度指標の新たなクラスを導入し,理論と実践の両面での重要性を強調した。
我々は、GD-WL(Generalized Distance Weisfeiler-Lehman)と呼ばれる原理的で効率的なアプローチを導入する。
実際に,GD-WLをTransformerのようなアーキテクチャで実装し,完全な並列化性を保ち,実現可能であることを示す。
論文 参考訳(メタデータ) (2023-01-23T15:58:59Z) - Representation Power of Graph Neural Networks: Improved Expressivity via
Algebraic Analysis [124.97061497512804]
標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。
また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
論文 参考訳(メタデータ) (2022-05-19T18:40:25Z) - Improving Graph Neural Network Expressivity via Subgraph Isomorphism
Counting [63.04999833264299]
グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。
Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。
グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
論文 参考訳(メタデータ) (2020-06-16T15:30:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。