論文の概要: Limits, approximation and size transferability for GNNs on sparse graphs via graphops

• arxiv url: http://arxiv.org/abs/2306.04495v1
• Date: Wed, 7 Jun 2023 15:04:58 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-08 13:51:20.110858
• Title: Limits, approximation and size transferability for GNNs on sparse graphs via graphops
• Title（参考訳）: グラフを用いたスパースグラフ上のGNNの極限,近似およびサイズ伝達性
• Authors: Thien Le and Stefanie Jegelka
• Abstract要約: 我々は,GNNを構成する集約演算など,グラフから導出される演算子の極限を取るという観点から考える。 我々の結果は、密でスパースなグラフ、およびグラフ極限の様々な概念に当てはまる。
• 参考スコア（独自算出の注目度）: 44.02161831977037
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Can graph neural networks generalize to graphs that are different from the graphs they were trained on, e.g., in size? In this work, we study this question from a theoretical perspective. While recent work established such transferability and approximation results via graph limits, e.g., via graphons, these only apply non-trivially to dense graphs. To include frequently encountered sparse graphs such as bounded-degree or power law graphs, we take a perspective of taking limits of operators derived from graphs, such as the aggregation operation that makes up GNNs. This leads to the recently introduced limit notion of graphops (Backhausz and Szegedy, 2022). We demonstrate how the operator perspective allows us to develop quantitative bounds on the distance between a finite GNN and its limit on an infinite graph, as well as the distance between the GNN on graphs of different sizes that share structural properties, under a regularity assumption verified for various graph sequences. Our results hold for dense and sparse graphs, and various notions of graph limits.
• Abstract（参考訳）: グラフニューラルネットワークは、トレーニングされたグラフ(例えば、サイズ)とは異なるグラフに一般化できるだろうか? 本研究では,この問題を理論的観点から考察する。 最近の研究は、グラフ制限(例えば、グラノン)によるそのような移動可能性や近似結果を確立したが、これらはグラフの密接な部分に対してのみ非自明に適用される。 有界度グラフや強法則グラフなど、頻繁に遭遇するスパースグラフを含めるために、GNNを構成する集約操作など、グラフから導出される演算子の制限を取るという視点をとる。 これは最近導入されたグラフの極限概念(Backhausz と Szegedy, 2022)に繋がる。 我々は, 有限 GNN と無限グラフ上の極限の間の距離の量的境界と, 様々なグラフ列に対して検証された正則性仮定の下で, 構造的性質の異なるグラフ上の GNN との距離を, 作用素視点がいかに発展させるかを示す。 我々の結果は、密度とスパースグラフ、およびグラフ極限の様々な概念を裏付ける。

関連論文リスト

• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
  我々は、スペクトル領域の多様体からサンプリングされたグラフ上のGNNの統計的一般化理論を確立するために多様体の視点を取る。 我々はGNNの一般化境界が対数スケールのグラフのサイズとともに線形に減少し、フィルタ関数のスペクトル連続定数とともに線形的に増加することを証明した。
  論文  参考訳（メタデータ） (2024-06-07T19:25:02Z)
• Zero-One Laws of Graph Neural Networks [7.783835522945603]
  グラフニューラルネットワーク(GNN)は、グラフ上の機械学習のためのデファクト標準ディープラーニングアーキテクチャである。 我々はGNNの表現と外挿能力に関する新しい理論的視点を提供する。 ErdHos-R'enyi モデルから拡大するグラフを描くと、そのようなグラフが特定の出力にマップされる確率は 0 か 1 のいずれかになる傾向があることを示す。
  論文  参考訳（メタデータ） (2023-01-30T17:02:23Z)
• Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
  グラフニューラルネットワーク(GNN)は、ネットワーク化されたデータの意味のあるパターンを活用するために、グラフ畳み込みに依存している。 我々は,成長するグラフ列の極限オブジェクトであるグラフオンを利用して,非常に大きなグラフ上のGNNを学習することを提案する。
  論文  参考訳（メタデータ） (2022-10-27T16:00:45Z)
• A Topological characterisation of Weisfeiler-Leman equivalence classes [0.0]
  グラフニューラルネットワーク(GNN)は、グラフと信号をグラフ上で処理することを目的とした学習モデルである。 本稿では、GNNが区別できないグラフのクラスを完全に特徴づけるために、被覆空間の理論に依存する。 データセット内の識別不能グラフの数は,ノード数とともに指数関数的に増加することを示す。
  論文  参考訳（メタデータ） (2022-06-23T17:28:55Z)
• 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)
• Increase and Conquer: Training Graph Neural Networks on Growing Graphs [116.03137405192356]
  本稿では,このグラフからBernoulliをサンプリングしたグラフ上でGNNをトレーニングすることで,WNN(Graphon Neural Network)を学習する問題を考察する。 これらの結果から着想を得た大規模グラフ上でGNNを学習するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-07T15:05:59Z)
• Graphon Neural Networks and the Transferability of Graph Neural Networks [125.71771240180654]
  グラフニューラルネットワーク(GNN)は、ネットワークデータから局所的な特徴を抽出するためにグラフ畳み込みに依存する。 我々は,GNNのリミットオブジェクトとしてグラフオンNNを導入し,GNNの出力とそのリミットグラフオン-NNとの差を証明した。 これにより、GNNの識別可能性と転送可能性のトレードオフが確立される。
  論文  参考訳（メタデータ） (2020-06-05T16:41:08Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。