論文の概要: Generalization Bounds for Message Passing Networks on Mixture of Graphons

• arxiv url: http://arxiv.org/abs/2404.03473v1
• Date: Thu, 4 Apr 2024 14:26:47 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-05 14:41:45.463770
• Title: Generalization Bounds for Message Passing Networks on Mixture of Graphons
• Title（参考訳）: グラフの混合によるメッセージパッシングネットワークの一般化境界
• Authors: Sohir Maskey, Gitta Kutyniok, Ron Levie,
• Abstract要約: メッセージパッシングニューラルネットワーク(MPNN)の一般化機能について検討する。 正規化和アグリゲーションと平均アグリゲーションを持つMPNNに対して、特に一般化バウンダリを導出する。 以上の結果から,MPNNはトレーニングセットのサイズよりも複雑度が高いため,依然として効果的に一般化可能であることが示唆された。
• 参考スコア（独自算出の注目度）: 21.457225542391267
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the generalization capabilities of Message Passing Neural Networks (MPNNs), a prevalent class of Graph Neural Networks (GNN). We derive generalization bounds specifically for MPNNs with normalized sum aggregation and mean aggregation. Our analysis is based on a data generation model incorporating a finite set of template graphons. Each graph within this framework is generated by sampling from one of the graphons with a certain degree of perturbation. In particular, we extend previous MPNN generalization results to a more realistic setting, which includes the following modifications: 1) we analyze simple random graphs with Bernoulli-distributed edges instead of weighted graphs; 2) we sample both graphs and graph signals from perturbed graphons instead of clean graphons; and 3) we analyze sparse graphs instead of dense graphs. In this more realistic and challenging scenario, we provide a generalization bound that decreases as the average number of nodes in the graphs increases. Our results imply that MPNNs with higher complexity than the size of the training set can still generalize effectively, as long as the graphs are sufficiently large.
• Abstract（参考訳）: 本稿では,グラフニューラルネットワーク(GNN)の一般的なクラスであるMPNN(Message Passing Neural Networks)の一般化機能について検討する。 正規化和アグリゲーションと平均アグリゲーションを持つMPNNに対して、特に一般化バウンダリを導出する。 本分析は,テンプレートグラフの有限セットを組み込んだデータ生成モデルに基づく。 このフレームワーク内の各グラフは、ある程度の摂動で1つのグラフからサンプリングすることで生成される。 特に、これまでのMPNNの一般化結果を、以下の変更を含むより現実的な設定に拡張する。 1) 重み付きグラフの代わりにベルヌーイ分布エッジを用いた単純なランダムグラフを解析する。 2)清潔なグラフの代わりに乱れたグラフからグラフ信号とグラフ信号の両方をサンプリングする。 3) 密度グラフの代わりにスパースグラフを解析する。 このより現実的で挑戦的なシナリオでは、グラフの平均ノード数が増加するにつれて減少する一般化境界を提供する。 その結果,グラフが十分に大きければ,トレーニングセットのサイズよりも複雑なMPNNを効果的に一般化できることが示唆された。

関連論文リスト

• Generalization of Geometric Graph Neural Networks [84.01980526069075]
  幾何グラフニューラルネットワーク(GNN)の一般化能力について検討する。 我々は,このGNNの最適経験リスクと最適統計リスクとの一般化ギャップを証明した。 最も重要な観察は、前の結果のようにグラフのサイズに制限されるのではなく、1つの大きなグラフで一般化能力を実現することができることである。
  論文  参考訳（メタデータ） (2024-09-08T18:55:57Z)
• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
  我々は、スペクトル領域の多様体からサンプリングされたグラフ上のGNNの統計的一般化理論を確立するために多様体の視点を取る。 我々はGNNの一般化境界が対数スケールのグラフのサイズとともに線形に減少し、フィルタ関数のスペクトル連続定数とともに線形的に増加することを証明した。
  論文  参考訳（メタデータ） (2024-06-07T19:25:02Z)
• Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion [17.70434437597516]
  本稿では,グラフニューラルネットワークの特徴拡散行列の最大特異値でスケールする一般化境界について述べる。 これらの境界は実世界のグラフの以前の境界よりも数値的にはるかに小さい。 ヘッセン語を用いた雑音摂動に対するグラフニューラルネットワークの安定性を測定する。
  論文  参考訳（メタデータ） (2023-02-09T05:54:17Z)
• Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
  グラフニューラルネットワーク(GNN)は、ネットワーク化されたデータの意味のあるパターンを活用するために、グラフ畳み込みに依存している。 我々は,成長するグラフ列の極限オブジェクトであるグラフオンを利用して,非常に大きなグラフ上のGNNを学習することを提案する。
  論文  参考訳（メタデータ） (2022-10-27T16:00:45Z)
• Graph Condensation via Receptive Field Distribution Matching [61.71711656856704]
  本稿では,元のグラフを表す小さなグラフの作成に焦点をあてる。 我々は、元のグラフを受容体の分布とみなし、受容体が同様の分布を持つ小さなグラフを合成することを目的としている。
  論文  参考訳（メタデータ） (2022-06-28T02:10:05Z)
• Stability and Generalization Capabilities of Message Passing Graph Neural Networks [4.691259009382681]
  グラフ分類におけるMPNNの一般化能力について検討する。 経験的損失と統計的損失の間の一般化ギャップに非漸近的境界を導出する。 これは、グラフに適用されたMPNNが、グラフが識別する幾何学的モデルに適用されたMPNNを近似することを示すことで証明される。
  論文  参考訳（メタデータ） (2022-02-01T18:37:53Z)
• Transferability Properties of Graph Neural Networks [125.71771240180654]
  グラフニューラルネットワーク(GNN)は、中規模グラフでサポートされているデータから表現を学ぶのに成功している。 適度な大きさのグラフ上でGNNを訓練し、それらを大規模グラフに転送する問題について検討する。 その結果, (i) グラフサイズに応じて転送誤差が減少し, (ii) グラフフィルタは非線型性の散乱挙動によってGNNにおいて緩和されるような転送可能性-識別可能性トレードオフを有することがわかった。
  論文  参考訳（メタデータ） (2021-12-09T00:08:09Z)
• Towards Scale-Invariant Graph-related Problem Solving by Iterative Homogeneous Graph Neural Networks [39.370875358317946]
  現在のグラフニューラルネットワーク(GNN)は、多くのグラフ解析問題を解く際に、スケール(グラフサイズ、グラフ径、エッジウェイトなど)に関する一般化性に欠ける。 まず,グラフサイズに対する共通グラフ理論アルゴリズムの反復回数の依存性に着想を得て,GNNにおけるメッセージパッシングプロセスの終了を,進捗に応じて順応的に学習する。 第二に、多くのグラフ理論アルゴリズムがグラフの重みに関して均一であるという事実に着想を得て、一般のGを変換するために、普遍的同次関数近似器である同次変換層を導入する。
  論文  参考訳（メタデータ） (2020-10-26T12:57:28Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• MathNet: Haar-Like Wavelet Multiresolution-Analysis for Graph Representation and Learning [31.42901131602713]
  本稿では,マルチレゾリューション・ハール型ウェーブレット(MathNet)を用いたグラフニューラルネットワークのためのフレームワークを提案する。 提案したMathNetは、特にデータセットにおいて、既存のGNNモデルよりも優れている。
  論文  参考訳（メタデータ） (2020-07-22T05:00:59Z)

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

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