論文の概要: A graphon-signal analysis of graph neural networks
- arxiv url: http://arxiv.org/abs/2305.15987v1
- Date: Thu, 25 May 2023 12:27:35 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-26 15:17:35.974044
- Title: A graphon-signal analysis of graph neural networks
- Title(参考訳): グラフニューラルネットワークのグラフ-信号解析
- Authors: Ron Levie
- Abstract要約: 本稿では,グラフトン解析からいわゆるグラフトン信号解析への拡張に基づく,メッセージパッシンググラフニューラルネットワーク(MPNN)の解析手法を提案する。
我々は、MPNNがグラフ-信号距離空間上のリプシッツ連続函数であることを証明した。
- 参考スコア(独自算出の注目度): 2.931632009516441
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present an approach for analyzing message passing graph neural networks
(MPNNs) based on an extension of graphon analysis to a so called graphon-signal
analysis. A MPNN is a function that takes a graph and a signal on the graph (a
graph-signal) and returns some value. Since the input space of MPNNs is
non-Euclidean, i.e., graphs can be of any size and topology, properties such as
generalization are less well understood for MPNNs than for Euclidean neural
networks. We claim that one important missing ingredient in past work is a
meaningful notion of graph-signal similarity measure, that endows the space of
inputs to MPNNs with a regular structure. We present such a similarity measure,
called the graphon-signal cut distance, which makes the space of all
graph-signals a dense subset of a compact metric space -- the graphon-signal
space. Informally, two deterministic graph-signals are close in cut distance if
they ``look like'' they were sampled from the same random graph-signal model.
Hence, our cut distance is a natural notion of graph-signal similarity, which
allows comparing any pair of graph-signals of any size and topology. We prove
that MPNNs are Lipschitz continuous functions over the graphon-signal metric
space. We then give two applications of this result: 1) a generalization bound
for MPNNs, and, 2) the stability of MPNNs to subsampling of graph-signals. Our
results apply to any regular enough MPNN on any distribution of graph-signals,
making the analysis rather universal.
- Abstract(参考訳): 本稿では,グラフトン解析からいわゆるグラフトン信号解析への拡張に基づく,メッセージパッシンググラフニューラルネットワーク(MPNN)の解析手法を提案する。
MPNNはグラフとグラフ上の信号(グラフ信号)を取得し、ある値を返す関数である。
MPNNの入力空間はユークリッドではないため、グラフは任意の大きさとトポロジーを持つことができるため、一般化のような特性はユークリッドニューラルネットワークよりもMPNNではよく理解されていない。
我々は、過去の研究で欠落している重要な要素の一つが、正規構造を持つMPNNへの入力の空間を与えるグラフ信号類似度尺度の有意義な概念であると主張している。
このような類似性測度をgraphon-signal cut distance と呼び、すべてのgraph-signals の空間をコンパクト距離空間 -- graphon-signal space の高密度部分集合とする。
形式的には、2つの決定論的グラフ信号は同じランダムグラフ信号モデルから'look like'がサンプリングされた場合、カット距離に近づいた。
したがって、カット距離はグラフ信号類似性の自然な概念であり、任意の大きさと位相のグラフ信号対を比較することができる。
我々は、MPNNがグラフ-信号距離空間上のリプシッツ連続函数であることを証明した。
次にこの結果の応用を2つ挙げる。
1) mpnn に対する一般化,及び,
2)MPNNのグラフ信号のサブサンプリングに対する安定性
この結果はグラフ信号の任意の分布に対して十分なMPNNを適用でき、解析はより普遍的である。
関連論文リスト
- Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs [33.266521866968304]
ノード属性を持つ属性グラフ上でのグラフニューラルネットワーク(GNN)の普遍性と一般化を解析する。
我々は、GNNに対する普遍近似定理と、属性グラフの任意のデータ分布上のGNNの有界一般化を証明した。
我々の研究は、属性のないグラフのみの導出理論、GNNが連続だが分離パワーのない導出コンパクトなメトリクス、GNNが連続かつ分離ポイントである導出指標を拡張・統合する。
論文 参考訳(メタデータ) (2024-11-08T10:34:24Z) - Generalization Bounds for Message Passing Networks on Mixture of Graphons [21.457225542391267]
メッセージパッシングニューラルネットワーク(MPNN)の一般化機能について検討する。
正規化和アグリゲーションと平均アグリゲーションを持つMPNNに対して、特に一般化バウンダリを導出する。
以上の結果から,MPNNはトレーニングセットのサイズよりも複雑度が高いため,依然として効果的に一般化可能であることが示唆された。
論文 参考訳(メタデータ) (2024-04-04T14:26:47Z) - 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) - Graphon Pooling for Reducing Dimensionality of Signals and Convolutional
Operators on Graphs [131.53471236405628]
グラフ空間における[0, 1]2の分割上のグラフとグラフ信号の誘導的グラフ表現を利用する3つの方法を提案する。
これらの低次元表現がグラフとグラフ信号の収束列を構成することを証明している。
我々は,層間次元減少比が大きい場合,グラノンプーリングは文献で提案した他の手法よりも有意に優れていることを観察した。
論文 参考訳(メタデータ) (2022-12-15T22:11:34Z) - From Local to Global: Spectral-Inspired Graph Neural Networks [28.858773653743075]
グラフニューラルネットワーク(GNN)は、非ユークリッドデータのための強力なディープラーニング手法である。
MPNNは、局所グラフ地区の信号を集約して結合するメッセージパッシングアルゴリズムである。
MPNNは、過密や過密といった問題に悩まされる可能性がある。
論文 参考訳(メタデータ) (2022-09-24T17:19:00Z) - Stability and Generalization Capabilities of Message Passing Graph
Neural Networks [4.691259009382681]
グラフ分類におけるMPNNの一般化能力について検討する。
経験的損失と統計的損失の間の一般化ギャップに非漸近的境界を導出する。
これは、グラフに適用されたMPNNが、グラフが識別する幾何学的モデルに適用されたMPNNを近似することを示すことで証明される。
論文 参考訳(メタデータ) (2022-02-01T18:37:53Z) - Graph and graphon neural network stability [122.06927400759021]
グラフネットワーク(GNN)は、ネットワークデータの有意義な表現を生成するためにグラフ構造の知識に依存する学習アーキテクチャである。
我々は,GNNの安定性を,グラファイトと呼ばれるカーネルオブジェクトを用いて解析する。
論文 参考訳(メタデータ) (2020-10-23T16:55:56Z) - Distance Encoding: Design Provably More Powerful Neural Networks for
Graph Representation Learning [63.97983530843762]
グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。
GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。
より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。
本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
論文 参考訳(メタデータ) (2020-08-31T23:15:40Z) - Graph Neural Networks: Architectures, Stability and Transferability [176.3960927323358]
グラフニューラルネットワーク(GNN)は、グラフでサポートされている信号のための情報処理アーキテクチャである。
これらは、個々の層がグラフ畳み込みフィルタのバンクを含む畳み込みニューラルネットワーク(CNN)の一般化である。
論文 参考訳(メタデータ) (2020-08-04T18:57:36Z) - Graphon Pooling in Graph Neural Networks [169.09536309161314]
グラフニューラルネットワーク(GNN)は、グラフによってモデル化された不規則構造上の信号の処理を含む様々なアプリケーションで効果的に使用されている。
本稿では,グラフのスペクトル特性を保存したグラフオンを用いて,GNNのプールとサンプリングを行う新しい手法を提案する。
論文 参考訳(メタデータ) (2020-03-03T21:04:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。