Fugu-MT 論文翻訳(概要): A Topological characterisation of Weisfeiler-Leman equivalence classes

論文の概要: A Topological characterisation of Weisfeiler-Leman equivalence classes

arxiv url: http://arxiv.org/abs/2206.11876v1
Date: Thu, 23 Jun 2022 17:28:55 GMT
ステータス: 処理完了
システム内更新日: 2022-06-24 13:14:53.055778
Title: A Topological characterisation of Weisfeiler-Leman equivalence classes
Title（参考訳）: Weisfeiler-Leman同値類の位相的特徴付け
Authors: Jacob Bamberger
Abstract要約: グラフニューラルネットワーク(GNN)は、グラフと信号をグラフ上で処理することを目的とした学習モデルである。本稿では、GNNが区別できないグラフのクラスを完全に特徴づけるために、被覆空間の理論に依存する。データセット内の識別不能グラフの数は,ノード数とともに指数関数的に増加することを示す。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Graph Neural Networks (GNNs) are learning models aimed at processing graphs and signals on graphs. The most popular and successful GNNs are based on message passing schemes. Such schemes inherently have limited expressive power when it comes to distinguishing two non-isomorphic graphs. In this article, we rely on the theory of covering spaces to fully characterize the classes of graphs that GNNs cannot distinguish. We then generate arbitrarily many non-isomorphic graphs that cannot be distinguished by GNNs, leading to the GraphCovers dataset. We also show that the number of indistinguishable graphs in our dataset grows super-exponentially with the number of nodes. Finally, we test the GraphCovers dataset on several GNN architectures, showing that none of them can distinguish any two graphs it contains.
Abstract（参考訳）: グラフニューラルネットワーク(GNN)は、グラフや信号を処理するための学習モデルである。最も人気があり、成功したGNNはメッセージパッシング方式に基づいている。そのようなスキームは本質的に2つの非同型グラフの区別に関して限定的な表現力を持つ。本稿では、GNNが区別できないグラフのクラスを完全に特徴づけるために、被覆空間の理論に依存する。そして、GNNでは区別できない非同型グラフを任意に生成し、GraphCoversデータセットを生成する。また,データセット内の識別不能グラフの数は,ノード数とともに指数関数的に増加することを示す。最後に、いくつかのGNNアーキテクチャ上でGraphCoversデータセットをテストする。

関連論文リスト

Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
ノード分類タスクにおける大規模グラフの利用は、グラフニューラルネットワーク(GNN)の現実的な応用を妨げる本稿では,GNNのグラフコアセットについて検討し,スペクトル埋め込みに基づくエゴグラフの選択により相互依存の問題を回避する。我々のスペクトルグレディグラフコアセット(SGGC)は、数百万のノードを持つグラフにスケールし、モデル事前学習の必要性を排除し、低ホモフィリーグラフに適用する。
論文参考訳（メタデータ） (2024-05-27T17:52:12Z)
Uplifting the Expressive Power of Graph Neural Networks through Graph Partitioning [3.236774847052122]
グラフ分割のレンズによるグラフニューラルネットワークの表現力について検討する。我々は新しいGNNアーキテクチャ、すなわちグラフ分割ニューラルネットワーク(GPNN)を導入する。
論文参考訳（メタデータ） (2023-12-14T06:08:35Z)
Graph Neural Networks Use Graphs When They Shouldn't [29.686091109844746]
グラフニューラルネットワーク(GNN)は,グラフデータの学習において主流のアプローチである。我々は、GNNが実際に与えられたグラフ構造に過度に適合する傾向があることを示す。
論文参考訳（メタデータ） (2023-09-08T13:59:18Z)
Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
グラフニューラルネットワーク(GNN)は、ネットワーク化されたデータの意味のあるパターンを活用するために、グラフ畳み込みに依存している。我々は,成長するグラフ列の極限オブジェクトであるグラフオンを利用して,非常に大きなグラフ上のGNNを学習することを提案する。
論文参考訳（メタデータ） (2022-10-27T16:00:45Z)
Incorporating Heterophily into Graph Neural Networks for Graph Classification [6.709862924279403]
グラフニューラルネットワーク(GNN)は、しばしばグラフ分類において強いホモフィリを仮定し、ヘテロフィリを考えることは滅多にない。 We developed a novel GNN architecture called IHGNN (short for Incorporated Heterophily into Graph Neural Networks) 我々は、様々なグラフデータセット上でIHGNNを実証的に検証し、グラフ分類のための最先端のGNNよりも優れていることを示す。
論文参考訳（メタデータ） (2022-03-15T06:48:35Z)
Graph Neural Networks for Graphs with Heterophily: A Survey [98.45621222357397]
異種グラフに対するグラフニューラルネットワーク(GNN)の総合的なレビューを提供する。具体的には,既存の異好性GNNモデルを本質的に支配する系統分類法を提案する。グラフヘテロフィリーと様々なグラフ研究領域の相関を議論し、より効果的なGNNの開発を促進することを目的とした。
論文参考訳（メタデータ） (2022-02-14T23:07:47Z)
Transferability Properties of Graph Neural Networks [125.71771240180654]
グラフニューラルネットワーク(GNN)は、中規模グラフでサポートされているデータから表現を学ぶのに成功している。適度な大きさのグラフ上でGNNを訓練し、それらを大規模グラフに転送する問題について検討する。その結果, (i) グラフサイズに応じて転送誤差が減少し, (ii) グラフフィルタは非線型性の散乱挙動によってGNNにおいて緩和されるような転送可能性-識別可能性トレードオフを有することがわかった。
論文参考訳（メタデータ） (2021-12-09T00:08:09Z)
Imbalanced Graph Classification via Graph-of-Graph Neural Networks [16.589373163769853]
グラフニューラルネットワーク(GNN)は、グラフの分類ラベルを識別するグラフ表現の学習において、前例のない成功を収めている。本稿では,グラフ不均衡問題を軽減する新しいフレームワークであるグラフ・オブ・グラフニューラルネットワーク(G$2$GNN)を提案する。提案したG$2$GNNは,F1-macroとF1-microのスコアにおいて,多くのベースラインを約5%上回る性能を示した。
論文参考訳（メタデータ） (2021-12-01T02:25:47Z)
Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
論文参考訳（メタデータ） (2020-08-31T23:15:40Z)
XGNN: Towards Model-Level Explanations of Graph Neural Networks [113.51160387804484]
グラフニューラルネットワーク(GNN)は、隣の情報を集約して組み合わせることでノードの特徴を学習する。 GNNはブラックボックスとして扱われ、人間の知的な説明が欠けている。我々はモデルレベルでGNNを解釈する新しい手法 XGNN を提案する。
論文参考訳（メタデータ） (2020-06-03T23:52:43Z)
Incomplete Graph Representation and Learning via Partial Graph Neural Networks [7.227805463462352]
多くのアプリケーションでは、グラフノードの属性が部分的に未知/欠落している不完全な形式でグラフがやってくる可能性がある。既存のGNNは、属性不完全なグラフデータを直接処理できない完全なグラフに基づいて設計されている。本研究では,属性不完全グラフ表現と学習のための部分グラフニューラルネットワーク(PaGNN)を新たに開発した。
論文参考訳（メタデータ） (2020-03-23T08:29:59Z)

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