論文の概要: Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond
Message Passing
- arxiv url: http://arxiv.org/abs/2102.08786v3
- Date: Mon, 21 Aug 2023 01:14:25 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-23 03:34:19.681264
- Title: Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond
Message Passing
- Title(参考訳): Weisfeiler Leman階層から抜け出す: メッセージパッシングを超えたグラフ学習
- Authors: Jan T\"onshoff, Martin Ritzert, Hinrikus Wolf, Martin Grohe
- Abstract要約: グラフ学習のためのニューラルネットワークアーキテクチャであるCRaWlを提案する。
CRaWlはメッセージパッシンググラフニューラルネットワークとは根本的に異なる。
CRaWlの表現性はWeisfeiler Lemanアルゴリズムと相容れないことを示す。
- 参考スコア(独自算出の注目度): 4.272016212825404
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We propose CRaWl, a novel neural network architecture for graph learning.
Like graph neural networks, CRaWl layers update node features on a graph and
thus can freely be combined or interleaved with GNN layers. Yet CRaWl operates
fundamentally different from message passing graph neural networks. CRaWl
layers extract and aggregate information on subgraphs appearing along random
walks through a graph using 1D Convolutions. Thereby it detects long range
interactions and computes non-local features. As the theoretical basis for our
approach, we prove a theorem stating that the expressiveness of CRaWl is
incomparable with that of the Weisfeiler Leman algorithm and hence with graph
neural networks. That is, there are functions expressible by CRaWl, but not by
GNNs and vice versa. This result extends to higher levels of the Weisfeiler
Leman hierarchy and thus to higher-order GNNs. Empirically, we show that CRaWl
matches state-of-the-art GNN architectures across a multitude of benchmark
datasets for classification and regression on graphs.
- Abstract(参考訳): グラフ学習のためのニューラルネットワークアーキテクチャであるCRaWlを提案する。
グラフニューラルネットワークと同様に、crawlレイヤはグラフ上のノード機能を更新できるため、gnnレイヤと自由に結合したり、インターリーブしたりすることができる。
しかし、CRaWlはメッセージパッシンググラフニューラルネットワークとは根本的に異なる。
CRaWl層は、1D畳み込みを用いてランダムなウォークに沿って現れるサブグラフの情報を抽出し集約する。
これにより、長距離の相互作用を検出し、非局所的な特徴を計算する。
このアプローチの理論的根拠として,クロールの表現性はワイスフェイラー・レマンアルゴリズムのそれと比べられず,グラフニューラルネットワークとも相容れないという定理を証明した。
すなわち、CRaWlで表現できる関数があるが、GNNでは表現できない。
この結果はWeisfeiler Leman階層の上位レベルにまで拡張され、したがって高階のGNNにも拡張される。
実験により、CRaWlは、グラフ上の分類と回帰のための多数のベンチマークデータセットで最先端のGNNアーキテクチャと一致することを示す。
関連論文リスト
- Graph as a feature: improving node classification with non-neural graph-aware logistic regression [2.952177779219163]
Graph-aware Logistic Regression (GLR) はノード分類タスク用に設計された非神経モデルである。
GNNにアクセスできる情報のごく一部しか使わない従来のグラフアルゴリズムとは異なり、提案モデルではノードの特徴とエンティティ間の関係を同時に活用する。
論文 参考訳(メタデータ) (2024-11-19T08:32:14Z) - Harnessing Collective Structure Knowledge in Data Augmentation for Graph Neural Networks [25.12261412297796]
グラフニューラルネットワーク(GNN)は,グラフ表現学習において最先端のパフォーマンスを達成した。
我々は新しいアプローチ、すなわち集合構造知識強化グラフニューラルネットワーク(CoS-GNN)を提案する。
論文 参考訳(メタデータ) (2024-05-17T08:50:00Z) - Graph Neural Networks Provably Benefit from Structural Information: A
Feature Learning Perspective [53.999128831324576]
グラフニューラルネットワーク(GNN)は、グラフ表現学習の先駆けとなった。
本研究では,特徴学習理論の文脈におけるグラフ畳み込みの役割について検討する。
論文 参考訳(メタデータ) (2023-06-24T10:21:11Z) - Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
グラフニューラルネットワーク(GNN)は、ネットワーク化されたデータの意味のあるパターンを活用するために、グラフ畳み込みに依存している。
我々は,成長するグラフ列の極限オブジェクトであるグラフオンを利用して,非常に大きなグラフ上のGNNを学習することを提案する。
論文 参考訳(メタデータ) (2022-10-27T16:00:45Z) - Automatic Relation-aware Graph Network Proliferation [182.30735195376792]
GNNを効率的に検索するためのARGNP(Automatic Relation-Aware Graph Network Proliferation)を提案する。
これらの操作は階層的なノード/リレーショナル情報を抽出し、グラフ上のメッセージパッシングのための異方的ガイダンスを提供する。
4つのグラフ学習タスクのための6つのデータセットの実験により、我々の手法によって生成されたGNNは、現在最先端の手作りおよび検索に基づくGNNよりも優れていることが示された。
論文 参考訳(メタデータ) (2022-05-31T10:38:04Z) - Discovering the Representation Bottleneck of Graph Neural Networks from
Multi-order Interactions [51.597480162777074]
グラフニューラルネットワーク(GNN)は、ノード機能を伝搬し、インタラクションを構築するためにメッセージパッシングパラダイムに依存している。
最近の研究は、異なるグラフ学習タスクはノード間の異なる範囲の相互作用を必要とすることを指摘している。
科学領域における2つの共通グラフ構築法、すなわち、emphK-nearest neighbor(KNN)グラフとemphfully-connected(FC)グラフについて検討する。
論文 参考訳(メタデータ) (2022-05-15T11:38:14Z) - ACE-HGNN: Adaptive Curvature Exploration Hyperbolic Graph Neural Network [72.16255675586089]
本稿では、入力グラフと下流タスクに基づいて最適な曲率を適応的に学習する適応曲率探索ハイパーボリックグラフニューラルネットワークACE-HGNNを提案する。
複数の実世界のグラフデータセットの実験は、競争性能と優れた一般化能力を備えたモデル品質において、顕著で一貫したパフォーマンス改善を示す。
論文 参考訳(メタデータ) (2021-10-15T07:18:57Z) - Topological Graph Neural Networks [14.349152231293928]
永続ホモロジーを用いたグラフのグローバルトポロジ情報を取り入れた新しい層であるTOGLを提案する。
我々の層によるGNNの拡張は、合成データセットと実世界のデータの両方において、有益な予測性能をもたらす。
論文 参考訳(メタデータ) (2021-02-15T20:27:56Z) - Hierarchical Message-Passing Graph Neural Networks [12.207978823927386]
本稿では,新しい階層型メッセージパッシンググラフニューラルネットワークフレームワークを提案する。
鍵となるアイデアは、フラットグラフ内のすべてのノードをマルチレベルなスーパーグラフに再編成する階層構造を生成することである。
階層型コミュニティ対応グラフニューラルネットワーク(HC-GNN)と呼ばれる,このフレームワークを実装した最初のモデルを提案する。
論文 参考訳(メタデータ) (2020-09-08T13:11:07Z) - Graph Neural Networks: Architectures, Stability and Transferability [176.3960927323358]
グラフニューラルネットワーク(GNN)は、グラフでサポートされている信号のための情報処理アーキテクチャである。
これらは、個々の層がグラフ畳み込みフィルタのバンクを含む畳み込みニューラルネットワーク(CNN)の一般化である。
論文 参考訳(メタデータ) (2020-08-04T18:57:36Z) - Higher-Order Explanations of Graph Neural Networks via Relevant Walks [3.1510406584101776]
グラフニューラルネットワーク(GNN)は、グラフ構造化データを予測するための一般的なアプローチである。
本稿では,GNNを高次展開を用いて自然に説明できることを示す。
本稿では,テキストデータの感情分析,量子化学における構造・不適切な関係,画像分類に関する実践的な知見を抽出する。
論文 参考訳(メタデータ) (2020-06-05T17:59:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。