論文の概要: From Relational Pooling to Subgraph GNNs: A Universal Framework for More
Expressive Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2305.04963v1
- Date: Mon, 8 May 2023 18:00:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-10 14:53:28.407205
- Title: From Relational Pooling to Subgraph GNNs: A Universal Framework for More
Expressive Graph Neural Networks
- Title（参考訳）: リレーショナルプールからサブグラフGNNへ:より表現力のあるグラフニューラルネットワークのためのユニバーサルフレームワーク
- Authors: Cai Zhou, Xiyuan Wang, Muhan Zhang
- Abstract要約: メッセージパッシングニューラルネットワークの表現力を向上させるために、ノードにラベルを割り当てる方法を示す。
実験により,本手法は普遍的に互換性があり,任意のベースGNNモデルの表現性を向上させることができることを示した。
私たちの$k,l$-GNNは、多くの合成および実世界のデータセットで優れたパフォーマンスを実現しています。
- 参考スコア（独自算出の注目度）: 8.121462458089141
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Relational pooling is a framework for building more expressive and
permutation-invariant graph neural networks. However, there is limited
understanding of the exact enhancement in the expressivity of RP and its
connection with the Weisfeiler Lehman hierarchy. Starting from RP, we propose
to explicitly assign labels to nodes as additional features to improve
expressive power of message passing neural networks. The method is then
extended to higher dimensional WL, leading to a novel $k,l$-WL algorithm, a
more general framework than $k$-WL. Theoretically, we analyze the expressivity
of $k,l$-WL with respect to $k$ and $l$ and unifies it with a great number of
subgraph GNNs. Complexity reduction methods are also systematically discussed
to build powerful and practical $k,l$-GNN instances. We theoretically and
experimentally prove that our method is universally compatible and capable of
improving the expressivity of any base GNN model. Our $k,l$-GNNs achieve
superior performance on many synthetic and real-world datasets, which verifies
the effectiveness of our framework.
- Abstract（参考訳）: リレーショナルプーリング(relation pooling)は、より表現豊かで置換不変なグラフニューラルネットワークを構築するためのフレームワークである。
しかし、RP の表現率の正確な拡張と、Weisfeiler Lehman 階層との関係についての理解は限られている。
RPから、メッセージパッシングニューラルネットワークの表現力を改善するために、ノードにラベルを明示的に割り当てることを提案する。
その後、この手法は高次元WLに拡張され、新しい$k,l$-WLアルゴリズムとなり、$k$-WLよりも一般的なフレームワークとなる。
理論的には、$k,l$-WL の表現率を$k$ および $l$ に対して解析し、多数のサブグラフ GNN で統一する。
複雑度低減法はまた、強力で実用的な$k,l$-GNNインスタンスを構築するために体系的に議論されている。
我々は,本手法が普遍的互換であり,任意のベースgnnモデルの表現性を向上させることができることを理論的および実験的に証明する。
当社の$k,l$-gnnは多くの合成および実世界のデータセットで優れたパフォーマンスを達成しています。
関連論文リスト
- Improving the Expressiveness of $K$-hop Message-Passing GNNs by Injecting Contextualized Substructure Information [17.56609419806051]
K$ホップメッセージパスGNNの表現力を高めるために,テキストサブストラクチャ符号化関数を提案する。
提案手法は,従来の$K$-hopグラフニューラルネットワークや1-WLサブグラフGNNよりも強力である。
論文 参考訳（メタデータ） (2024-06-27T15:10:56Z) - 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) - A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph
Weisfeiler-Lehman Tests [30.558563815430418]
GNN(Subgraph Neural Network)は、表現型グラフニューラルネットワーク(GNN)を開発するための重要な方向として登場した。
本稿では,WIP(Subgraph Weisfeiler-Lehman Tests)のレンズを用いた一般ノードベースサブグラフGNNの系統的研究を行う。
ノードベースの部分グラフ GNN が 6 つのSWL 等価クラスのうちの 1 つに該当することを証明し、その中で $mathsfSSWL$ が最大表現力を達成する。
論文 参考訳（メタデータ） (2023-02-14T14:42:54Z) - 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) - 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) - Counting Substructures with Higher-Order Graph Neural Networks:
Possibility and Impossibility Results [58.277290855841976]
グラフニューラルネットワーク(GNN)の計算コストと表現力のトレードオフについて検討する。
新しいモデルでは、$k$のサブグラフをカウントでき、低次GNNの既知の制限を克服できることを示す。
いくつかの場合において、提案アルゴリズムは既存の高階$k$-GNNに比べて計算量を大幅に削減することができる。
論文 参考訳（メタデータ） (2020-12-06T03:42:54Z) - 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) - Optimization and Generalization Analysis of Transduction through
Gradient Boosting and Application to Multi-scale Graph Neural Networks [60.22494363676747]
現在のグラフニューラルネットワーク(GNN)は、オーバースムーシング(over-smoothing)と呼ばれる問題のため、自分自身を深くするのは難しいことが知られている。
マルチスケールGNNは、オーバースムーシング問題を緩和するための有望なアプローチである。
マルチスケールGNNを含むトランスダクティブ学習アルゴリズムの最適化と一般化を保証する。
論文 参考訳（メタデータ） (2020-06-15T17:06:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。