論文の概要: Convergence of Invariant Graph Networks
- arxiv url: http://arxiv.org/abs/2201.10129v1
- Date: Tue, 25 Jan 2022 07:02:58 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-27 05:16:37.629884
- Title: Convergence of Invariant Graph Networks
- Title（参考訳）: 不変グラフネットワークの収束性
- Authors: Chen Cai, Yusu Wang
- Abstract要約: 本稿では,1つの強力なGNN, Invariant Graph Network (IGN) のグラフからのグラフへの収束について検討する。
IGN-small には、スペクトル GNN を任意に近似できるような関数クラスがまだ存在することを示す。
- 参考スコア（独自算出の注目度）: 13.008323851750442
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Although theoretical properties such as expressive power and over-smoothing
of graph neural networks (GNN) have been extensively studied recently, its
convergence property is a relatively new direction. In this paper, we
investigate the convergence of one powerful GNN, Invariant Graph Network (IGN)
over graphs sampled from graphons.
We first prove the stability of linear layers for general $k$-IGN (of order
$k$) based on a novel interpretation of linear equivariant layers. Building
upon this result, we prove the convergence of $k$-IGN under the model of
\citet{ruiz2020graphon}, where we access the edge weight but the convergence
error is measured for graphon inputs.
Under the more natural (and more challenging) setting of
\citet{keriven2020convergence} where one can only access 0-1 adjacency matrix
sampled according to edge probability, we first show a negative result that the
convergence of any IGN is not possible. We then obtain the convergence of a
subset of IGNs, denoted as IGN-small, after the edge probability estimation. We
show that IGN-small still contains function class rich enough that can
approximate spectral GNNs arbitrarily well. Lastly, we perform experiments on
various graphon models to verify our statements.
- Abstract（参考訳）: グラフニューラルネットワーク(GNN)の表現力や過剰スムーシングなどの理論的性質は近年広く研究されているが、その収束性は比較的新しい方向である。
本稿では,1つの強力なGNN, Invariant Graph Network (IGN) のグラフからのグラフへの収束について検討する。
まず、線形同変層の新しい解釈に基づいて、一般$k$-IGN(例えば$k$)に対する線形層の安定性を証明した。
この結果に基づいて, エッジウェイトにアクセスできるが, グラファイト入力に対しては収束誤差が測定される, \citet{ruiz2020graphon} モデルの下での$k$-IGNの収束を証明した。
より自然な(かつより困難な)設定である \citet{keriven2020convergence} では、エッジ確率に従ってサンプリングされた 0-1 の隣接行列にしかアクセスできないので、まず、任意の ign の収束が不可能である負の結果を示す。
次に、エッジ確率推定の後、IGN のサブセットである IGN-small の収束を求める。
IGN-small には、スペクトル GNN を任意に近似できるような関数クラスがまだ存在することを示す。
最後に,様々なグラフモデル上で実験を行い,ステートメントを検証する。
関連論文リスト
- Graph neural networks and non-commuting operators [4.912318087940015]
我々は,グラフトン・タプルニューラルネットワークの極限理論を開発し,それを普遍的な伝達可能性定理の証明に利用する。
我々の理論的結果は、GNNのよく知られた移動可能性定理を、複数の同時グラフの場合にまで拡張する。
得られたモデルの安定性を確実に実施する訓練手順を導出する。
論文 参考訳（メタデータ） (2024-11-06T21:17:14Z) - Generalization of Geometric Graph Neural Networks [84.01980526069075]
幾何グラフニューラルネットワーク(GNN)の一般化能力について検討する。
我々は,このGNNの最適経験リスクと最適統計リスクとの一般化ギャップを証明した。
最も重要な観察は、前の結果のようにグラフのサイズに制限されるのではなく、1つの大きなグラフで一般化能力を実現することができることである。
論文 参考訳（メタデータ） (2024-09-08T18:55:57Z) - The Heterophilic Snowflake Hypothesis: Training and Empowering GNNs for Heterophilic Graphs [59.03660013787925]
ヘテロフィリー・スノーフレーク仮説を導入し、ヘテロ親和性グラフの研究をガイドし、促進するための効果的なソリューションを提供する。
観察の結果,我々のフレームワークは多種多様なタスクのための多目的演算子として機能することがわかった。
さまざまなGNNフレームワークに統合することができ、パフォーマンスを詳細に向上し、最適なネットワーク深さを選択するための説明可能なアプローチを提供する。
論文 参考訳（メタデータ） (2024-06-18T12:16:00Z) - Almost Surely Asymptotically Constant Graph Neural Networks [7.339728196535312]
出力は定数関数に収束し、これらの分類器が一様に表現できる上限となることを示す。
この強い収束現象は、芸術モデルを含む非常に幅広い種類のGNNに適用される。
我々はこれらの知見を実証的に検証し、収束現象がランダムグラフだけでなく、実世界のグラフにも現れることを観察した。
論文 参考訳（メタデータ） (2024-03-06T17:40:26Z) - Implicit Graph Neural Diffusion Networks: Convergence, Generalization,
and Over-Smoothing [7.984586585987328]
Inlicit Graph Neural Networks (GNN)は、グラフ学習問題に対処する上で大きな成功を収めた。
パラメータ化グラフラプラシアン演算子に基づく暗黙グラフ拡散層を設計するための幾何学的枠組みを提案する。
ディリクレエネルギー最小化問題の固定点方程式として, 暗黙のGNN層がどう見えるかを示す。
論文 参考訳（メタデータ） (2023-08-07T05:22:33Z) - Geometric Graph Filters and Neural Networks: Limit Properties and
Discriminability Trade-offs [122.06927400759021]
本稿では,グラフニューラルネットワーク (GNN) と多様体ニューラルネットワーク (MNN) の関係について検討する。
これらのグラフ上の畳み込みフィルタとニューラルネットワークが連続多様体上の畳み込みフィルタとニューラルネットワークに収束することを示す。
論文 参考訳（メタデータ） (2023-05-29T08:27:17Z) - 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) - Zero-One Laws of Graph Neural Networks [7.783835522945603]
グラフニューラルネットワーク(GNN)は、グラフ上の機械学習のためのデファクト標準ディープラーニングアーキテクチャである。
我々はGNNの表現と外挿能力に関する新しい理論的視点を提供する。
ErdHos-R'enyi モデルから拡大するグラフを描くと、そのようなグラフが特定の出力にマップされる確率は 0 か 1 のいずれかになる傾向があることを示す。
論文 参考訳（メタデータ） (2023-01-30T17:02:23Z) - Stable and Transferable Hyper-Graph Neural Networks [95.07035704188984]
グラフニューラルネットワーク(GNN)を用いたハイパーグラフでサポートする信号処理アーキテクチャを提案する。
スペクトル類似性により任意のグラフにまたがってGNNの安定性と転送可能性の誤差をバウンドするフレームワークを提供する。
論文 参考訳（メタデータ） (2022-11-11T23:44:20Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。