論文の概要: A note on the VC dimension of 1-dimensional GNNs

• arxiv url: http://arxiv.org/abs/2410.07829v1
• Date: Thu, 10 Oct 2024 11:33:15 GMT
• ステータス: 処理完了
• システム内更新日: 2024-10-31 14:36:05.001350
• Title: A note on the VC dimension of 1-dimensional GNNs
• Title（参考訳）: 1次元GNNのVC次元に関する一考察
• Authors: Noah Daniëls, Floris Geerts,
• Abstract要約: グラフニューラルネットワーク(GNN)は,グラフ構造化データを解析するための重要なツールとなっている。 本稿では,GNNの一般化について,Vapnik-Chervonenkis(VC)次元について検討する。
• 参考スコア（独自算出の注目度）: 6.0757501646966965
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph Neural Networks (GNNs) have become an essential tool for analyzing graph-structured data, leveraging their ability to capture complex relational information. While the expressivity of GNNs, particularly their equivalence to the Weisfeiler-Leman (1-WL) isomorphism test, has been well-documented, understanding their generalization capabilities remains critical. This paper focuses on the generalization of GNNs by investigating their Vapnik-Chervonenkis (VC) dimension. We extend previous results to demonstrate that 1-dimensional GNNs with a single parameter have an infinite VC dimension for unbounded graphs. Furthermore, we show that this also holds for GNNs using analytic non-polynomial activation functions, including the 1-dimensional GNNs that were recently shown to be as expressive as the 1-WL test. These results suggest inherent limitations in the generalization ability of even the most simple GNNs, when viewed from the VC dimension perspective.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)は、複雑なリレーショナル情報をキャプチャする能力を活用して、グラフ構造化データを分析する上で不可欠なツールとなっている。 GNNの表現性、特にWeisfeiler-Leman(英語版)(1-WL)同型テストの同値性はよく文書化されているが、それらの一般化能力を理解することは依然として重要である。 本稿では,GNNの一般化について,Vapnik-Chervonenkis(VC)次元について検討する。 我々は,1つのパラメータを持つ1次元GNNが非有界グラフに対して無限のVC次元を持つことを示すために,以前の結果を拡張した。 さらに,最近1-WLテストと同程度の表現性を示した1次元GNNを含む,解析的非ポリノミカルアクティベーション関数を用いたGNNにも有効であることを示す。 これらの結果は、VC次元の観点から見て、最も単純なGNNの一般化能力に固有の限界を示唆している。

関連論文リスト

• Generalization of Graph Neural Networks is Robust to Model Mismatch [84.01980526069075]
  グラフニューラルネットワーク(GNN)は、その一般化能力によってサポートされている様々なタスクにおいて、その効果を実証している。 本稿では,多様体モデルから生成される幾何グラフで動作するGNNについて検討する。 本稿では,そのようなモデルミスマッチの存在下でのGNN一般化の堅牢性を明らかにする。
  論文  参考訳（メタデータ） (2024-08-25T16:00:44Z)
• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
  我々は、スペクトル領域の多様体からサンプリングされたグラフ上のGNNの統計的一般化理論を確立するために多様体の視点を取る。 我々はGNNの一般化境界が対数スケールのグラフのサイズとともに線形に減少し、フィルタ関数のスペクトル連続定数とともに線形的に増加することを証明した。
  論文  参考訳（メタデータ） (2024-06-07T19:25:02Z)
• VC dimension of Graph Neural Networks with Pfaffian activation functions [4.141514895639094]
  グラフニューラルネットワーク(GNN)は、近年、広範囲のグラフドメインでタスクを学習する強力なツールとして登場している。 我々の研究の目的は、GNNのVC次元に関するこの分析を、シグモイドや双曲タンジェントといった他のよく使われる活性化関数に拡張することである。
  論文  参考訳（メタデータ） (2024-01-22T21:11:22Z)
• Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPs [71.93227401463199]
  本稿では、P(ropagational)MLPと呼ばれる中間モデルクラスを導入することにより、GNNの性能向上を本質的な能力に向ける。 PMLPは、トレーニングにおいてはるかに効率的でありながら、GNNと同等(あるいはそれ以上)に動作することを観察する。
  論文  参考訳（メタデータ） (2022-12-18T08:17:32Z)
• A Unified View on Graph Neural Networks as Graph Signal Denoising [49.980783124401555]
  グラフニューラルネットワーク(GNN)は,グラフ構造化データの学習表現において顕著に普及している。 本研究では,代表的GNNモデル群における集約過程を,グラフ記述問題の解法とみなすことができることを数学的に確立する。 UGNNから派生した新しいGNNモデルADA-UGNNをインスタンス化し、ノード間の適応的滑らかさでグラフを処理する。
  論文  参考訳（メタデータ） (2020-10-05T04:57:18Z)
• The Surprising Power of Graph Neural Networks with Random Node Initialization [54.4101931234922]
  グラフニューラルネットワーク(GNN)は、関係データ上での表現学習に有効なモデルである。 標準 GNN はその表現力に制限があり、Weisfeiler-Leman グラフ同型(英語版)の能力以外の区別はできない。 本研究では,ランダムノード(RNI)を用いたGNNの表現力の解析を行う。 我々はこれらのモデルが普遍的であることを証明し、GNNが高次特性の計算に頼らない最初の結果である。
  論文  参考訳（メタデータ） (2020-10-02T19:53:05Z)
• Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs [95.63153473559865]
  グラフニューラルネットワーク(GNN)は、グラフ上の新たな機械学習モデルである。 既存のGNNモデルの多くは浅く、本質的に機能中心である。 我々は,既存の浅いGNNがグラフ構造をよく保存できないことを経験的かつ解析的に示す。 本稿では,グラフ構造保存におけるGNNの能力を高めるプラグインモジュールであるEigen-GNNを提案する。
  論文  参考訳（メタデータ） (2020-06-08T02:47:38Z)
• Generalization and Representational Limits of Graph Neural Networks [46.20253808402385]
  ローカル情報に完全に依存するグラフニューラルネットワーク(GNN)では,いくつかの重要なグラフ特性を計算できないことを示す。 メッセージパッシングGNNに対する最初のデータ依存一般化境界を提供する。 私たちのバウンダリは、既存のVC次元ベースのGNN保証よりもはるかに厳格で、リカレントニューラルネットワークのRademacherバウンダリと同等です。
  論文  参考訳（メタデータ） (2020-02-14T18:10:14Z)

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

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