論文の概要: The Self-Loop Paradox: Investigating the Impact of Self-Loops on Graph
Neural Networks
- arxiv url: http://arxiv.org/abs/2312.01721v1
- Date: Mon, 4 Dec 2023 08:23:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-05 15:50:09.670963
- Title: The Self-Loop Paradox: Investigating the Impact of Self-Loops on Graph
Neural Networks
- Title(参考訳): 自己ループパラドックス:グラフニューラルネットワークに対する自己ループの影響に関する研究
- Authors: Moritz Lampert, Ingo Scholtes
- Abstract要約: グラフニューラルネットワーク(GNN)はグラフに自己ループを追加し、各レイヤにノード自身に関する機能情報を含む。
直観は、この情報の"バックフロー"がグラフのないグラフに比べて自己ループを持つグラフで大きくなるべきであることを示唆している。
特定のGNNアーキテクチャでは、ノードが自身から得る情報は、同一のグラフに比べて、自己ループを持つグラフでは小さくすることができることを示す。
- 参考スコア(独自算出の注目度): 0.951828574518325
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Many Graph Neural Networks (GNNs) add self-loops to a graph to include
feature information about a node itself at each layer. However, if the GNN
consists of more than one layer, this information can return to its origin via
cycles in the graph topology. Intuition suggests that this "backflow" of
information should be larger in graphs with self-loops compared to graphs
without. In this work, we counter this intuition and show that for certain GNN
architectures, the information a node gains from itself can be smaller in
graphs with self-loops compared to the same graphs without. We adopt an
analytical approach for the study of statistical graph ensembles with a given
degree sequence and show that this phenomenon, which we call the self-loop
paradox, can depend both on the number of GNN layers $k$ and whether $k$ is
even or odd. We experimentally validate our theoretical findings in a synthetic
node classification task and investigate its practical relevance in 23
real-world graphs.
- Abstract(参考訳): 多くのグラフニューラルネットワーク(GNN)はグラフに自己ループを追加し、各層にノード自体の特徴情報を含む。
しかし、GNNが複数の層から構成されている場合、この情報はグラフトポロジのサイクルを通して元の情報に戻ることができる。
直観は、この情報の"バックフロー"がグラフのないグラフに比べて自己ループを持つグラフで大きくなるべきであることを示唆している。
本研究では、この直感に逆らって、ノードが自身から得る情報も、同一のグラフを使わずに自己ループのグラフでより小さくすることができることを示す。
我々は、与えられた次数列を持つ統計的グラフアンサンブルの研究に分析的アプローチを採用し、我々が自己ループパラドックスと呼ぶこの現象が、gnn層$k$の数と、$k$が偶数か奇数かの両方に依存することを示した。
本研究は,合成ノード分類タスクにおける理論的知見を実験的に検証し,23の実世界グラフにおいてその妥当性を検証した。
関連論文リスト
- Graph Neural Networks Use Graphs When They Shouldn't [29.686091109844746]
グラフニューラルネットワーク(GNN)は,グラフデータの学習において主流のアプローチである。
我々は、GNNが実際に与えられたグラフ構造に過度に適合する傾向があることを示す。
論文 参考訳(メタデータ) (2023-09-08T13:59:18Z) - FoSR: First-order spectral rewiring for addressing oversquashing in GNNs [0.0]
グラフニューラルネットワーク(GNN)は、グラフのエッジに沿ってメッセージを渡すことによって、グラフデータの構造を活用することができる。
本稿では,グラフにエッジを体系的に付加することで過疎化を防止する計算効率のよいアルゴリズムを提案する。
提案アルゴリズムは,いくつかのグラフ分類タスクにおいて,既存のグラフリウィリング手法よりも優れていることを示す。
論文 参考訳(メタデータ) (2022-10-21T07:58:03Z) - A Topological characterisation of Weisfeiler-Leman equivalence classes [0.0]
グラフニューラルネットワーク(GNN)は、グラフと信号をグラフ上で処理することを目的とした学習モデルである。
本稿では、GNNが区別できないグラフのクラスを完全に特徴づけるために、被覆空間の理論に依存する。
データセット内の識別不能グラフの数は,ノード数とともに指数関数的に増加することを示す。
論文 参考訳(メタデータ) (2022-06-23T17:28:55Z) - 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) - The Exact Class of Graph Functions Generated by Graph Neural Networks [43.25172578943894]
グラフ関数と出力が同一のグラフニューラルネットワーク(GNN)?
本稿では,この疑問に完全に答え,GNNで表現可能なグラフ問題のクラスを特徴付ける。
この条件は2次的に多くの制約をチェックすることで効率よく検証できることを示す。
論文 参考訳(メタデータ) (2022-02-17T18:54:27Z) - 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) - GraphSVX: Shapley Value Explanations for Graph Neural Networks [81.83769974301995]
グラフニューラルネットワーク(GNN)は、幾何データに基づく様々な学習タスクにおいて大きな性能を発揮する。
本稿では,既存のGNN解説者の多くが満足する統一フレームワークを提案する。
GNN用に特別に設計されたポストホックローカルモデル非依存説明法であるGraphSVXを紹介します。
論文 参考訳(メタデータ) (2021-04-18T10:40:37Z) - Multilevel Graph Matching Networks for Deep Graph Similarity Learning [79.3213351477689]
グラフ構造オブジェクト間のグラフ類似性を計算するためのマルチレベルグラフマッチングネットワーク(MGMN)フレームワークを提案する。
標準ベンチマークデータセットの欠如を補うため、グラフグラフ分類とグラフグラフ回帰タスクの両方のためのデータセットセットを作成し、収集した。
総合的な実験により、MGMNはグラフグラフ分類とグラフグラフ回帰タスクの両方において、最先端のベースラインモデルより一貫して優れていることが示された。
論文 参考訳(メタデータ) (2020-07-08T19:48:19Z) - Graph Pooling with Node Proximity for Hierarchical Representation
Learning [80.62181998314547]
本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。
その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
論文 参考訳(メタデータ) (2020-06-19T13:09:44Z) - Graphon Neural Networks and the Transferability of Graph Neural Networks [125.71771240180654]
グラフニューラルネットワーク(GNN)は、ネットワークデータから局所的な特徴を抽出するためにグラフ畳み込みに依存する。
我々は,GNNのリミットオブジェクトとしてグラフオンNNを導入し,GNNの出力とそのリミットグラフオン-NNとの差を証明した。
これにより、GNNの識別可能性と転送可能性のトレードオフが確立される。
論文 参考訳(メタデータ) (2020-06-05T16:41:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。