論文の概要: Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs

• arxiv url: http://arxiv.org/abs/2411.05464v1
• Date: Fri, 08 Nov 2024 10:34:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-11 14:54:05.472783
• Title: Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs
• Title（参考訳）: 分散グラフ上のグラフニューラルネットワークの一般化, 表現性, 普遍性
• Authors: Levi Rauchwerger, Stefanie Jegelka, Ron Levie,
• Abstract要約: ノード属性を持つ属性グラフ上でのグラフニューラルネットワーク(GNN)の普遍性と一般化を解析する。 我々は、GNNに対する普遍近似定理と、属性グラフの任意のデータ分布上のGNNの有界一般化を証明した。 我々の研究は、属性のないグラフのみの導出理論、GNNが連続だが分離パワーのない導出コンパクトなメトリクス、GNNが連続かつ分離ポイントである導出指標を拡張・統合する。
• 参考スコア（独自算出の注目度）: 33.266521866968304
• License:
• Abstract: We analyze the universality and generalization of graph neural networks (GNNs) on attributed graphs, i.e., with node attributes. To this end, we propose pseudometrics over the space of all attributed graphs that describe the fine-grained expressivity of GNNs. Namely, GNNs are both Lipschitz continuous with respect to our pseudometrics and can separate attributed graphs that are distant in the metric. Moreover, we prove that the space of all attributed graphs is relatively compact with respect to our metrics. Based on these properties, we prove a universal approximation theorem for GNNs and generalization bounds for GNNs on any data distribution of attributed graphs. The proposed metrics compute the similarity between the structures of attributed graphs via a hierarchical optimal transport between computation trees. Our work extends and unites previous approaches which either derived theory only for graphs with no attributes, derived compact metrics under which GNNs are continuous but without separation power, or derived metrics under which GNNs are continuous and separate points but the space of graphs is not relatively compact, which prevents universal approximation and generalization analysis.
• Abstract（参考訳）: 属性付きグラフ上でのグラフニューラルネットワーク(GNN)の普遍性と一般化をノード属性で解析する。 この目的のために、GNNの微細な表現性を記述する全ての属性グラフの空間上の擬測度を提案する。 すなわち、GNNは、我々の擬距離に関してリプシッツ連続であり、計量において遠い属性グラフを分離することができる。 さらに、すべての属性グラフの空間は、我々のメトリクスに関して相対的にコンパクトであることを示す。 これらの性質に基づいて、GNNに対する普遍近似定理と、属性グラフの任意のデータ分布上のGNNに対する一般化境界を証明した。 提案手法は,計算木間の階層的最適輸送により,属性グラフの構造間の類似性を計算する。 我々の研究は、属性を持たないグラフのみの導出理論、GNNが連続であるが分離力のない導出コンパクトなメトリクス、GNNが連続かつ分離点であるがグラフの空間は比較的コンパクトではなく、普遍近似や一般化解析を妨げている導出コンパクトなメトリクスを拡張・統合する。

関連論文リスト

• Generalization of Geometric Graph Neural Networks [84.01980526069075]
  幾何グラフニューラルネットワーク(GNN)の一般化能力について検討する。 我々は,このGNNの最適経験リスクと最適統計リスクとの一般化ギャップを証明した。 最も重要な観察は、前の結果のようにグラフのサイズに制限されるのではなく、1つの大きなグラフで一般化能力を実現することができることである。
  論文  参考訳（メタデータ） (2024-09-08T18:55:57Z)
• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
  グラフニューラルネットワーク(GNN)は、グラフ畳み込みの連続的な応用により、隣接ノードからの情報を結合する。 ノードレベルとグラフレベルの両方のタスクにおけるGNNの一般化ギャップについて検討する。 トレーニンググラフのノード数によって一般化ギャップが減少することを示す。
  論文  参考訳（メタデータ） (2024-06-07T19:25:02Z)
• Generalization of Graph Neural Networks through the Lens of Homomorphism [7.223313563198697]
  本稿では,グラフ・ニューラル・ネットワーク(GNN)の一般化を,グラフ準同型のエントロピー解析という新たな視点で研究することを提案する。 グラフ準同型と情報理論測度を結びつけることにより、グラフ分類とノード分類の両方の一般化境界を導出する。 これらの境界は、パス、サイクル、傾きなど、様々なグラフ構造に固有の微妙さを捉えることができる。
  論文  参考訳（メタデータ） (2024-03-10T03:51:59Z)
• 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)
• Relation Embedding based Graph Neural Networks for Handling Heterogeneous Graph [58.99478502486377]
  我々は、同種GNNが不均一グラフを扱うのに十分な能力を持つように、シンプルで効率的なフレームワークを提案する。 具体的には、エッジ型関係と自己ループ接続の重要性を埋め込むために、関係1つのパラメータのみを使用する関係埋め込みベースのグラフニューラルネットワーク(RE-GNN)を提案する。
  論文  参考訳（メタデータ） (2022-09-23T05:24:18Z)
• Discovering the Representation Bottleneck of Graph Neural Networks from Multi-order Interactions [51.597480162777074]
  グラフニューラルネットワーク(GNN)は、ノード機能を伝搬し、インタラクションを構築するためにメッセージパッシングパラダイムに依存している。 最近の研究は、異なるグラフ学習タスクはノード間の異なる範囲の相互作用を必要とすることを指摘している。 科学領域における2つの共通グラフ構築法、すなわち、emphK-nearest neighbor(KNN)グラフとemphfully-connected(FC)グラフについて検討する。
  論文  参考訳（メタデータ） (2022-05-15T11:38:14Z)
• Meta-Weight Graph Neural Network: Push the Limits Beyond Global Homophily [24.408557217909316]
  グラフニューラルネットワーク(GNN)は,グラフデータマイニングに強い表現力を示す。 しかしながら、すべてのグラフがホモ親和性を持つわけではないが、同じグラフであっても、分布は著しく異なるかもしれない。 異なるノードに対するグラフ畳み込み層を適応的に構築するメタウェイトグラフニューラルネットワーク(MWGNN)を提案する。
  論文  参考訳（メタデータ） (2022-03-19T09:27:38Z)
• On the approximation capability of GNNs in node classification/regression tasks [4.141514895639094]
  グラフニューラルネットワーク(GNN)は、グラフ処理のための幅広い種類の接続モデルである。 GNNはノード分類/回帰タスクの確率の普遍近似であることを示す。
  論文  参考訳（メタデータ） (2021-06-16T17:46:51Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)

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

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