論文の概要: 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 network outputs are almost surely asymptotically constant [8.01812577223632]
グラフニューラルネットワーク(GNN)は、グラフ上のさまざまな学習タスクのための主要なアーキテクチャである。
我々は、GNN確率分類器の予測がより大きなグラフに適用されるにつれてどのように進化するかを考察する。
出力は定数関数に収束し、これらの分類器が一様に表現できる上限となることを示す。
論文 参考訳(メタデータ) (2024-03-06T17:40:26Z) - Learning to Reweight for Graph Neural Network [63.978102332612906]
グラフニューラルネットワーク(GNN)は、グラフタスクに対して有望な結果を示す。
既存のGNNの一般化能力は、テストとトレーニンググラフデータの間に分散シフトが存在する場合に低下する。
本稿では,分布外一般化能力を大幅に向上させる非線形グラフデコリレーション法を提案する。
論文 参考訳(メタデータ) (2023-12-19T12:25:10Z) - 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) - Graph Neural Network Bandits [89.31889875864599]
グラフ構造データ上で定義された報酬関数を用いた帯域最適化問題を考察する。
この設定の主な課題は、大きなドメインへのスケーリングと、多くのノードを持つグラフへのスケーリングである。
グラフニューラルネットワーク(GNN)を用いて報酬関数を推定できることを示す。
論文 参考訳(メタデータ) (2022-07-13T18:12:36Z) - ES-GNN: Generalizing Graph Neural Networks Beyond Homophily with Edge
Splitting [32.69196871253339]
本稿では,グラフエッジを適応的に識別する新しいエッジ分割GNN(ES-GNN)フレームワークを提案する。
これは本質的に、元のグラフを同じノードセットを持つ2つの部分グラフに変換するが、排他的なエッジセットである。
本稿では,ES-GNNを非交叉グラフ記述問題の解とみなすことができることを示す。
論文 参考訳(メタデータ) (2022-05-27T01:29:03Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。