論文の概要: Convergence of Message Passing Graph Neural Networks with Generic
Aggregation On Large Random Graphs
- arxiv url: http://arxiv.org/abs/2304.11140v1
- Date: Fri, 21 Apr 2023 17:22:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-24 13:46:10.440295
- 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要約: 乱数グラフモデルにおけるメッセージパッシンググラフニューラルネットワークの収束性について,ノード数が無限大になる傾向にあるため,その連続性について検討する。
このような結果を、古典的に使われているすべてのメッセージパッシンググラフニューラルネットワークを含む、非常に大規模な集約関数に拡張する。
- 参考スコア(独自算出の注目度): 17.396274240172126
- 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 degree-normalized means. We extend such
results to a very large class of aggregation functions, that encompasses all
classically used message passing graph neural networks, such as attention-based
mesage passing or max convolutional message passing on top of
(degree-normalized) convolutional 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, we treat
the case where the aggregation is a coordinate-wise maximum separately, at it
necessitates a very different proof technique and yields a qualitatively
different convergence rate.
- Abstract(参考訳): 本研究では,ランダムグラフモデル上でのメッセージパッシンググラフニューラルネットワークの収束について,ノード数が無限になりがちであることを示す。
これまでこの収束は、次数正規化手段の形で集約関数を持つアーキテクチャでのみ知られていた。
我々は、これらの結果を非常に大きな集約関数クラスに拡張し、(度数正規化)畳み込みメッセージパッシングの上に、注意に基づくメセージパッシングやmax畳み込みメッセージパッシングといった、古典的に使用されるすべてのメッセージパッシンググラフニューラルネットワークを包含する。
穏やかな仮定の下で、この収束を定量化する確率の高い非漸近境界を与える。
主な結果はmcdiarmid不等式に基づいている。
興味深いことに、アグリゲーションが座標ワイドの最大値である場合、それは全く異なる証明手法を必要とし、定性的に異なる収束率が得られる。
関連論文リスト
- Graph neural network outputs are almost surely asymptotically constant [8.01812577223632]
グラフニューラルネットワーク(GNN)は、グラフ上のさまざまな学習タスクのための主要なアーキテクチャである。
我々は、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) - Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on
Graph Diffusion [17.70434437597516]
本稿では,グラフニューラルネットワークの特徴拡散行列の最大特異値でスケールする一般化境界について述べる。
これらの境界は実世界のグラフの以前の境界よりも数値的にはるかに小さい。
ヘッセン語を用いた雑音摂動に対するグラフニューラルネットワークの安定性を測定する。
論文 参考訳(メタデータ) (2023-02-09T05:54:17Z) - GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
本稿では,高次元分布をモデル化し,グラフスケルトンと整合した複雑な関係特徴構造を持つデータの新しい例を生成することの問題点を考察する。
提案するモデルは,タスクを2つのフェーズに分割することで,各データポイントのグラフ構造に制約されたデータ特徴を生成する問題に対処する。
第一に、与えられたグラフのノードに関連する機能の分布をモデル化し、第二に、ノードのフィーチャに条件付きでエッジ機能を補完する。
論文 参考訳(メタデータ) (2022-12-01T11:49:07Z) - Stable and Transferable Hyper-Graph Neural Networks [95.07035704188984]
グラフニューラルネットワーク(GNN)を用いたハイパーグラフでサポートする信号処理アーキテクチャを提案する。
スペクトル類似性により任意のグラフにまたがってGNNの安定性と転送可能性の誤差をバウンドするフレームワークを提供する。
論文 参考訳(メタデータ) (2022-11-11T23:44:20Z) - Graph Neural Networks with Feature and Structure Aware Random Walk [5.431036185361236]
典型的な好適なグラフでは、エッジを指向する可能性があり、エッジをそのまま扱うか、あるいは単純に非指向にするかは、GNNモデルの性能に大きな影響を与える。
そこで我々は,グラフの方向性を適応的に学習するモデルを開発し,ノード間の長距離相関を生かした。
論文 参考訳(メタデータ) (2021-11-19T08:54:21Z) - Explicit Pairwise Factorized Graph Neural Network for Semi-Supervised
Node Classification [59.06717774425588]
本稿では,グラフ全体を部分的に観測されたマルコフ確率場としてモデル化するEPFGNN(Explicit Pairwise Factorized Graph Neural Network)を提案する。
出力-出力関係をモデル化するための明示的なペアワイズ要素を含み、入力-出力関係をモデル化するためにGNNバックボーンを使用する。
本研究では,グラフ上での半教師付きノード分類の性能を効果的に向上できることを示す。
論文 参考訳(メタデータ) (2021-07-27T19:47:53Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。