論文の概要: Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning
- arxiv url: http://arxiv.org/abs/2403.13749v1
- Date: Wed, 20 Mar 2024 16:58:28 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-21 16:08:57.388282
- Title: Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning
- Title(参考訳): WeisfeilerとLeman Go Loopy:グラフ表現学習の新しい階層
- Authors: Raffaele Paolino, Sohir Maskey, Pascal Welke, Gitta Kutyniok,
- Abstract要約: グラフ同型テストの新しい階層構造と対応するGNNフレームワークである$r$-$ell$MPNNを導入し、最大長さ$r + 2$までサイクルをカウントできる。
特に、$r$-$ell$WL がサクタスグラフの準同型を数えることができることを示す。
提案した$r$-$ell$MPNNの複数の合成データセットに対する表現力とカウント力を実証的に検証し,様々な実世界のデータセットに対する最先端の予測性能を示す。
- 参考スコア(独自算出の注目度): 17.646846505225735
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We introduce $r$-loopy Weisfeiler-Leman ($r$-$\ell{}$WL), a novel hierarchy of graph isomorphism tests and a corresponding GNN framework, $r$-$\ell{}$MPNN, that can count cycles up to length $r + 2$. Most notably, we show that $r$-$\ell{}$WL can count homomorphisms of cactus graphs. This strictly extends classical 1-WL, which can only count homomorphisms of trees and, in fact, is incomparable to $k$-WL for any fixed $k$. We empirically validate the expressive and counting power of the proposed $r$-$\ell{}$MPNN on several synthetic datasets and present state-of-the-art predictive performance on various real-world datasets. The code is available at https://github.com/RPaolino/loopy
- Abstract(参考訳): グラフ同型テストの新しい階層と対応するGNNフレームワークである$r$-loopy Weisfeiler-Leman$r$-$\ell{}$WLを導入する。
特に、$r$-$\ell{}$WL がサクタスグラフの準同型を数えることができることを示す。
これは、木の準同型しか数えられない古典的な 1-WL を厳密に拡張し、実際、任意の固定された $k$ に対して $k$-WL と相容れない。
提案した$r$-$\ell{}$MPNNの複数の合成データセットに対する表現力とカウント力を実証的に検証し,様々な実世界のデータセットにおける最先端の予測性能を示す。
コードはhttps://github.com/RPaolino/loopyで公開されている。
関連論文リスト
- Graph Chain-of-Thought: Augmenting Large Language Models by Reasoning on Graphs [56.073652738501394]
大規模言語モデル(LLM)は、特に知識集約的なタスクにおいて幻覚に悩まされる。
既存の研究は、外部知識コーパスから取得した個々のテキスト単位でLLMを拡張することを提案する。
本稿では,グラフを反復的に推論することで,LLMをグラフで拡張するためのGraph Chain-of-thinkt (Graph-CoT) というフレームワークを提案する。
論文 参考訳(メタデータ) (2024-04-10T15:41:53Z) - On dimensionality of feature vectors in MPNNs [49.32130498861987]
我々は、メッセージパッシンググラフニューラルネットワーク(MPNN)がWeisfeiler--Leman(WL)同型テストに対する識別力に等しいというモリスら(AAAI'19)の古典的な結果を再考する。
論文 参考訳(メタデータ) (2024-02-06T12:56:55Z) - Fine-grained Expressivity of Graph Neural Networks [15.766353435658043]
我々は1ドルWLとMPNNの連続的な拡張をグラファイトに検討する。
連続的な1ドルWLの変動は,MPNNのグラフ上での表現力の正確なトポロジ的特徴を与えることを示す。
また,グラフ距離の保存能力に基づいて,異なるMPNNアーキテクチャの評価を行った。
論文 参考訳(メタデータ) (2023-06-06T14:12:23Z) - Extending the Design Space of Graph Neural Networks by Rethinking
Folklore Weisfeiler-Lehman [66.23316415757456]
近年、グラフニューラルネットワーク(GNN)の最も人気のあるフレームワークとして、メッセージパッシングニューラルネットワーク(MPNN)が登場している。
しかし、その表現力は1次元のWeisfeiler-Lehman (1-WL) テストによって制限される。
我々は、任意の同変集合をすべてのノードの代わりに隣人と考える拡張、$(k,t)$-FWLを提案する。
N$2-GNN は ZINC-Subset (0.059) で記録破りの結果を達成し、以前の SOTA の成績を 10.6% 上回った。
論文 参考訳(メタデータ) (2023-06-05T21:35:32Z) - Improving Expressivity of Graph Neural Networks using Localization [1.323700980948722]
局所$k-$WLのパワーを分析し、$k-$WLよりも表現力が高く、少なくとも$(k+1)-$WLと同じくらい表現力があることを示す。
また,1-$WL のみを用いて,最大 4 個の部分グラフの正確な数を保証するフラグメンテーション手法を提案する。
論文 参考訳(メタデータ) (2023-05-31T08:46:11Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳(メタデータ) (2022-04-22T12:37:56Z) - Listing Maximal k-Plexes in Large Real-World Graphs [21.79007529359561]
大きなグラフで高密度なサブグラフをリストすることは、コミュニティ検出のような様々なネットワーク分析アプリケーションにおいて重要なタスクである。
本稿では、最大$k$-プレックスと最大$k$-プレックスを所定の大きさで列挙する研究線を継続する。
私たちの最初のコントリビューションはアルゴリズムListPlexで、すべての最大$k$-plexesを$O*(gammaD)$ time for each constant $k$, where $gamma$ is a value to $k$ but strictly smaller than 2, and $D$ is the degeneracy of the graph that far less。
論文 参考訳(メタデータ) (2022-02-17T16:25:56Z) - Scalable Deep Generative Modeling for Sparse Graphs [105.60961114312686]
既存のディープニューラルネットワーク手法では、隣接行列を構築することで、$Omega(n2)$複雑さを必要とする。
我々は,この空間を利用して完全隣接行列を生成する新しい自己回帰モデルBiGGを開発した。
トレーニング中、この自己回帰モデルは$O(log n)$同期ステージで並列化できる。
論文 参考訳(メタデータ) (2020-06-28T04:37:57Z) - Walk Message Passing Neural Networks and Second-Order Graph Neural
Networks [4.355567556995855]
我々は,新しいタイプのMPNNである$ell$-walk MPNNを紹介した。
2ドル(約2万円)のMPNNが表現力で2-WLと一致していることを示す。
特に、W[$ell$]を表現力で一致させるために、各層で$ell-1$行列乗法を許す。
論文 参考訳(メタデータ) (2020-06-16T20:24:01Z) - Improving Graph Neural Network Expressivity via Subgraph Isomorphism
Counting [63.04999833264299]
グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。
Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。
グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
論文 参考訳(メタデータ) (2020-06-16T15:30:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。