Fugu-MT 論文翻訳(概要): Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning

論文の概要: Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning

arxiv url: http://arxiv.org/abs/2403.13749v2
Date: Wed, 06 Nov 2024 19:37:01 GMT
ステータス: 翻訳完了
システム内更新日: 2024-11-09 00:48:48.901402
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:
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 Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
論文参考訳（メタデータ） (2024-08-03T20:08:02Z)
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)
Graph Chain-of-Thought: Augmenting Large Language Models by Reasoning on Graphs [60.71360240206726]
大規模言語モデル(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)
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)
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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。