論文の概要: Convergence of Message Passing Graph Neural Networks with Generic Aggregation On Large Random Graphs

• arxiv url: http://arxiv.org/abs/2304.11140v3
• Date: Tue, 13 Aug 2024 10:06:57 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-14 23:38:51.694983
• Title: Convergence of Message Passing Graph Neural Networks with Generic Aggregation On Large Random Graphs
• Title（参考訳）: 大規模ランダムグラフ上のジェネリックアグリゲーションを用いたメッセージパッシンググラフニューラルネットワークの収束性
• Authors: Matthieu Cordonnier, Nicolas Keriven, Nicolas Tremblay, Samuel Vaiter,
• Abstract要約: 乱数グラフモデルにおけるメッセージパッシンググラフニューラルネットワークの収束性について,ノード数が無限大になる傾向にあるため,その連続性について検討する。 このような結果を、古典的に使われているすべてのメッセージパッシンググラフニューラルネットワークを含む、多数の集約関数に拡張する。
• 参考スコア（独自算出の注目度）: 19.33515519621001
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the convergence of message passing graph neural networks on random graph models to their continuous counterpart as the number of nodes tends to infinity. Until now, this convergence was only known for architectures with aggregation functions in the form of normalized means, or, equivalently, of an application of classical operators like the adjacency matrix or the graph Laplacian. We extend such results to a large class of aggregation functions, that encompasses all classically used message passing graph neural networks, such as attention-based message passing, max convolutional message passing, (degree-normalized) convolutional message passing, or moment-based aggregation message passing. Under mild assumptions, we give non-asymptotic bounds with high probability to quantify this convergence. Our main result is based on the McDiarmid inequality. Interestingly, this result does not apply to the case where the aggregation is a coordinate-wise maximum. We treat this case separately and obtain a different convergence rate.
• Abstract（参考訳）: 乱数グラフモデルにおけるメッセージパッシンググラフニューラルネットワークの収束性について,ノード数が無限大になる傾向にあるため,その連続性について検討する。 それまで、この収束は、正規化された手段の形で集約関数を持つアーキテクチャ、あるいはそれと同値に、隣接行列やグラフラプラシアンのような古典作用素の応用でのみ知られていた。 このような結果は、注目ベースのメッセージパッシング、最大畳み込みメッセージパッシング、(次数正規化)畳み込みメッセージパッシング、モーメントベースのアグリゲーションメッセージパッシングなど、古典的に使われているすべてのメッセージパッシンググラフニューラルネットワークを含む、大規模な集約関数に拡張する。 穏やかな仮定の下では、この収束を定量化する確率の高い非漸近境界を与える。 私たちの主な結果はMcDiarmidの不等式に基づいている。 興味深いことに、この結果はアグリゲーションが座標ワイドの最大値である場合に当てはまらない。 我々はこのケースを別々に扱い、異なる収束率を得る。

関連論文リスト

• Generalization of Geometric Graph Neural Networks [84.01980526069075]
  幾何グラフニューラルネットワーク(GNN)の一般化能力について検討する。 我々は,このGNNの最適経験リスクと最適統計リスクとの一般化ギャップを証明した。 最も重要な観察は、前の結果のようにグラフのサイズに制限されるのではなく、1つの大きなグラフで一般化能力を実現することができることである。
  論文  参考訳（メタデータ） (2024-09-08T18:55:57Z)
• Almost Surely Asymptotically Constant Graph Neural Networks [7.339728196535312]
  出力は定数関数に収束し、これらの分類器が一様に表現できる上限となることを示す。 この強い収束現象は、芸術モデルを含む非常に幅広い種類のGNNに適用される。 我々はこれらの知見を実証的に検証し、収束現象がランダムグラフだけでなく、実世界のグラフにも現れることを観察した。
  論文  参考訳（メタデータ） (2024-03-06T17:40:26Z)
• Seq-HGNN: Learning Sequential Node Representation on Heterogeneous Graph [57.2953563124339]
  本稿では,シーケンシャルノード表現,すなわちSeq-HGNNを用いた新しい異種グラフニューラルネットワークを提案する。 Heterogeneous Graph Benchmark (HGB) と Open Graph Benchmark (OGB) の4つの広く使われているデータセットについて広範な実験を行った。
  論文  参考訳（メタデータ） (2023-05-18T07:27:18Z)
• Optimality of Message-Passing Architectures for Sparse Graphs [13.96547777184641]
  スパース設定における特徴デコレーショングラフ上のノード分類問題、すなわちノードの期待次数がノード数で$O(1)$である場合について検討する。 局所ベイズ最適性(英語版)と呼ばれるノード分類タスクに対するベイズ最適性(英語版)の概念を導入する。 最適なメッセージパッシングアーキテクチャは,低グラフ信号のレギュレーションにおける標準と高グラフ信号のレギュレーションにおける典型とを補間することを示す。
  論文  参考訳（メタデータ） (2023-05-17T17:31:20Z)
• GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
  本稿では,高次元分布をモデル化し,グラフスケルトンと整合した複雑な関係特徴構造を持つデータの新しい例を生成することの問題点を考察する。 提案するモデルは,タスクを2つのフェーズに分割することで,各データポイントのグラフ構造に制約されたデータ特徴を生成する問題に対処する。 第一に、与えられたグラフのノードに関連する機能の分布をモデル化し、第二に、ノードのフィーチャに条件付きでエッジ機能を補完する。
  論文  参考訳（メタデータ） (2022-12-01T11:49:07Z)
• Dynamic Graph Message Passing Networks for Visual Recognition [112.49513303433606]
  長距離依存のモデリングは、コンピュータビジョンにおけるシーン理解タスクに不可欠である。 完全連結グラフはそのようなモデリングには有益であるが、計算オーバーヘッドは禁じられている。 本稿では,計算複雑性を大幅に低減する動的グラフメッセージパッシングネットワークを提案する。
  論文  参考訳（メタデータ） (2022-09-20T14:41:37Z)
• Graph Neural Networks with Feature and Structure Aware Random Walk [7.143879014059894]
  典型的な好適なグラフでは、エッジを指向する可能性があり、エッジをそのまま扱うか、あるいは単純に非指向にするかは、GNNモデルの性能に大きな影響を与える。 そこで我々は,グラフの方向性を適応的に学習するモデルを開発し,ノード間の長距離相関を生かした。
  論文  参考訳（メタデータ） (2021-11-19T08:54:21Z)
• Graph Neural Networks with Composite Kernels [60.81504431653264]
  カーネル重み付けの観点からノード集約を再解釈する。 本稿では,アグリゲーション方式における特徴類似性を考慮したフレームワークを提案する。 特徴空間における特徴類似性をエンコードするために,元の隣り合うカーネルと学習可能なカーネルの合成として特徴集約を提案する。
  論文  参考訳（メタデータ） (2020-05-16T04:44:29Z)
• Residual Correlation in Graph Neural Network Regression [39.54530450932135]
  我々は条件付き独立仮定が予測力を著しく制限していることを示します。 この問題を解釈可能かつ効率的なフレームワークで解決する。 我々のフレームワークは、競合するベースラインよりもかなり高い精度を実現している。
  論文  参考訳（メタデータ） (2020-02-19T16:32:54Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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