論文の概要: A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph
Weisfeiler-Lehman Tests
- arxiv url: http://arxiv.org/abs/2302.07090v1
- Date: Tue, 14 Feb 2023 14:42:54 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-15 15:17:37.176928
- Title: A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph
Weisfeiler-Lehman Tests
- Title（参考訳）: Weisfeiler-Lehmanテストによる部分グラフGNNの完全表現性階層
- Authors: Bohang Zhang, Guhao Feng, Yiheng Du, Di He, Liwei Wang
- Abstract要約: 本稿では,WIP(Subgraph Weisfeiler-Lehman Tests)のレンズを用いた一般ノードベースサブグラフGNNの系統的研究を行う。
我々の中心的な成果は、厳密に表現性を高めたSWLの完全な階層を構築することである。
ZINCベンチマークの実験では、$mathsfSSWL$-inspired subgraph GNNsは、非常に単純であるにもかかわらず、以前のアーキテクチャよりも大幅に優れていることが示されている。
- 参考スコア（独自算出の注目度）: 30.558563815430418
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recently, subgraph GNNs have emerged as an important direction for developing
expressive graph neural networks (GNNs). While numerous architectures have been
proposed, so far there is still a limited understanding of how various design
paradigms differ in terms of expressive power, nor is it clear what design
principle achieves maximal expressiveness with minimal architectural
complexity. Targeting these fundamental questions, this paper conducts a
systematic study of general node-based subgraph GNNs through the lens of
Subgraph Weisfeiler-Lehman Tests (SWL). Our central result is to build a
complete hierarchy of SWL with strictly growing expressivity. Concretely, we
prove that any node-based subgraph GNN falls into one of the six SWL
equivalence classes, among which $\mathsf{SSWL}$ achieves the maximal
expressive power. We also study how these equivalence classes differ in terms
of their practical expressiveness such as encoding graph distance and
biconnectivity. In addition, we give a tight expressivity upper bound of all
SWL algorithms by establishing a close relation with localized versions of
Folklore WL tests (FWL). Overall, our results provide insights into the power
of existing subgraph GNNs, guide the design of new architectures, and point out
their limitations by revealing an inherent gap with the 2-FWL test. Finally,
experiments on the ZINC benchmark demonstrate that $\mathsf{SSWL}$-inspired
subgraph GNNs can significantly outperform prior architectures despite great
simplicity.
- Abstract（参考訳）: 近年,GNNは表現型グラフニューラルネットワーク(GNN)を開発する上で重要な方向として現れている。
多数のアーキテクチャが提案されているが、これまでのところ、様々な設計パラダイムが表現力の観点からどのように異なるかは限定的であり、アーキテクチャの複雑さを最小限に抑えながら、設計原理が最大限表現性を達成するかは明確ではない。
本論文は,これらの基本的課題を対象とし,SWL (Subgraph Weisfeiler-Lehman Tests) のレンズによる一般ノードベースサブグラフGNNの体系的研究を行う。
我々の中心的な成果は、厳密に表現性を高めたSWLの完全な階層を構築することである。
具体的には、任意のノードベースの部分グラフ GNN が6つのSWL同値類のうちの1つに該当することを証明し、その中で$\mathsf{SSWL}$ が最大表現力を達成する。
また、グラフ距離の符号化や双連結性といった実用的表現性の観点から、これらの同値類がどのように異なるかについても検討する。
さらに,folklore wl test (fwl) の局所化バージョンとの密接な関係を確立することにより,全swlアルゴリズムの密接な表現率上限を与える。
その結果,既存のサブグラフGNNのパワーを把握し,新しいアーキテクチャの設計を導くとともに,2-FWLテストに固有のギャップを明らかにすることで,その限界を指摘することができた。
最後に、ZINCベンチマークの実験により、$\mathsf{SSWL}$-inspired subgraph GNNsは、非常に単純であるにもかかわらず、以前のアーキテクチャよりも大幅に優れていることを示した。
関連論文リスト
- Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN
Expressiveness [35.409017863665575]
準同型表現性は、GNNモデルが準同型の下でグラフを数える能力を測定する。
ケーススタディとして著名なGNNの4つのクラスを調べることで、それらの同型表現の単純で統一的でエレガントな記述を導き出す。
本研究の結果は, 過去の一連の研究に対する新たな洞察を与え, 地域社会における様々なサブアレスの景観を統一し, いくつかのオープンな疑問を解決した。
論文 参考訳（メタデータ） (2024-01-16T17:23:23Z) - MAG-GNN: Reinforcement Learning Boosted Graph Neural Network [68.60884768323739]
特定の研究の行は、GNNの表現性を向上させるためにサブグラフ情報を使用するサブグラフGNNを提案し、大きな成功を収めた。
このような効果は、すべての可能な部分グラフを列挙することによって、GNNの効率を犠牲にする。
本稿では,強化学習(RL)により強化されたGNNである磁気グラフニューラルネットワーク(MAG-GNN)を提案する。
論文 参考訳（メタデータ） (2023-10-29T20:32:21Z) - Equivariant Polynomials for Graph Neural Networks [38.15983687193912]
グラフネットワーク(GNN)は本質的に表現力に制限がある。
本稿では、GNNがある程度の同変を計算する能力に基づく代替パワー階層を提案する。
これらの強化されたGNNは、複数のグラフ学習ベンチマークの実験において最先端の結果を示す。
論文 参考訳（メタデータ） (2023-02-22T18:53:38Z) - 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) - Twin Weisfeiler-Lehman: High Expressive GNNs for Graph Classification [48.087302573188396]
本稿では,ノードラベルとノードIDを同時に渡す新しいグラフ同型テスト手法Twin-WLを提案する。
2つのツイン-GNNは、従来のメッセージパッシングGNNよりも表現力が高いことが証明された。
論文 参考訳（メタデータ） (2022-03-22T12:58:03Z) - Equivariant Subgraph Aggregation Networks [23.26140936226352]
本稿では,この問題に対処するためのEquivariant Subgraph Aggregation Networks (ESAN) という新しいフレームワークを提案する。
2つのグラフはMPNNでは区別できないかもしれないが、しばしば区別可能な部分グラフを含む。
グラフ同型に対する1次元Weisfeiler-Leman(1-WL)テストの新しい変種を開発し、ESANの表現性に対する下界を証明した。
サブグラフ選択ポリシーや同変ニューラルアーキテクチャといった設計選択がアーキテクチャの表現力にどのように影響するかを記述する理論的結果を提供する。
論文 参考訳（メタデータ） (2021-10-06T16:45:07Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。