論文の概要: WL meet VC

• arxiv url: http://arxiv.org/abs/2301.11039v2
• Date: Sat, 27 May 2023 18:27:12 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-31 02:07:55.686236
• Title: WL meet VC
• Title（参考訳）: WL meet VC
• Authors: Christopher Morris, Floris Geerts, Jan T\"onshoff, Martin Grohe
• Abstract要約: 本稿では,Vapnik-Chervonenkis(VC)次元理論のレンズによるグラフニューラルネットワーク(GNN)の表現力について検討する。 我々は、GNNのVC次元と1text-mathsfWL$およびGNNのVC次元によって生成される色数を用いて、GNNのVC次元の上限を導出する。
• 参考スコア（独自算出の注目度）: 9.468816647649104
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, many works studied the expressive power of graph neural networks (GNNs) by linking it to the $1$-dimensional Weisfeiler--Leman algorithm ($1\text{-}\mathsf{WL}$). Here, the $1\text{-}\mathsf{WL}$ is a well-studied heuristic for the graph isomorphism problem, which iteratively colors or partitions a graph's vertex set. While this connection has led to significant advances in understanding and enhancing GNNs' expressive power, it does not provide insights into their generalization performance, i.e., their ability to make meaningful predictions beyond the training set. In this paper, we study GNNs' generalization ability through the lens of Vapnik--Chervonenkis (VC) dimension theory in two settings, focusing on graph-level predictions. First, when no upper bound on the graphs' order is known, we show that the bitlength of GNNs' weights tightly bounds their VC dimension. Further, we derive an upper bound for GNNs' VC dimension using the number of colors produced by the $1\text{-}\mathsf{WL}$. Secondly, when an upper bound on the graphs' order is known, we show a tight connection between the number of graphs distinguishable by the $1\text{-}\mathsf{WL}$ and GNNs' VC dimension. Our empirical study confirms the validity of our theoretical findings.
• Abstract（参考訳）: 近年,グラフニューラルネットワーク(GNN)の表現力について,1次元Weisfeiler-Lemanアルゴリズム(1\text{-}\mathsf{WL}$)にリンクすることで研究されている。 ここで、1\text{-}\mathsf{WL}$ はグラフ同型問題に対するよく研究されたヒューリスティックであり、グラフの頂点集合を反復的に色付けまたは分割する。 この関係は、GNNの表現力の理解と強化に大きな進歩をもたらしたが、その一般化性能、すなわちトレーニングセットを超えて有意義な予測を行う能力についての洞察を与えていない。 本稿では,GNNの一般化能力を,Vapnik-Chervonenkis(VC)次元理論のレンズを用いて2つの設定で研究し,グラフレベルの予測に焦点を当てた。 まず、グラフの順序の上限が知られていない場合、gnnの重みのビット長がvc次元に密着していることを示す。 さらに、GNN の VC 次元の上限を $1\text{-}\mathsf{WL}$ で生成される色数を用いて導出する。 第二に、グラフの順序の上限が分かっているとき、 1\text{-}\mathsf{wl}$ と gnns の vc 次元で区別可能なグラフの数と密接な関係を示す。 実験結果は理論的な結果の妥当性を確認した。

関連論文リスト

• A note on the VC dimension of 1-dimensional GNNs [6.0757501646966965]
  グラフニューラルネットワーク(GNN)は,グラフ構造化データを解析するための重要なツールとなっている。 本稿では,GNNの一般化について,Vapnik-Chervonenkis(VC)次元について検討する。
  論文  参考訳（メタデータ） (2024-10-10T11:33:15Z)
• 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)
• Uplifting the Expressive Power of Graph Neural Networks through Graph Partitioning [3.236774847052122]
  グラフ分割のレンズによるグラフニューラルネットワークの表現力について検討する。 我々は新しいGNNアーキテクチャ、すなわちグラフ分割ニューラルネットワーク(GPNN)を導入する。
  論文  参考訳（メタデータ） (2023-12-14T06:08:35Z)
• Generalization Limits of Graph Neural Networks in Identity Effects Learning [12.302336258860116]
  グラフニューラルネットワーク(GNN)は、さまざまなグラフドメインでデータ駆動学習を行う強力なツールとして登場した。 我々は、いわゆるアイデンティティ効果の学習において、GNNの新たな一般化特性と基本的限界を確立する。 我々の研究は、単純な認知タスクを行う際に、GNNの能力を理解する必要性によって動機付けられている。
  論文  参考訳（メタデータ） (2023-06-30T20:56:38Z)
• Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
  グラフニューラルネットワーク(GNN)は、ネットワーク化されたデータの意味のあるパターンを活用するために、グラフ畳み込みに依存している。 我々は,成長するグラフ列の極限オブジェクトであるグラフオンを利用して,非常に大きなグラフ上のGNNを学習することを提案する。
  論文  参考訳（メタデータ） (2022-10-27T16:00:45Z)
• Two-Dimensional Weisfeiler-Lehman Graph Neural Networks for Link Prediction [61.01337335214126]
  グラフニューラルネットワーク(GNN)のリンク予測 リンク予測のためのほとんどの既存のGNNは、1次元Weisfeiler-Lehman (1-WL) テストに基づいている。 テキスト2次元Weisfeiler-Lehman (2-WL) テストに基づいて,ノード対(リンク)表現を直接取得可能な,まったく異なるアプローチを提案する。
  論文  参考訳（メタデータ） (2022-06-20T04:50:38Z)
• Twin Weisfeiler-Lehman: High Expressive GNNs for Graph Classification [48.087302573188396]
  本稿では,ノードラベルとノードIDを同時に渡す新しいグラフ同型テスト手法Twin-WLを提案する。 2つのツイン-GNNは、従来のメッセージパッシングGNNよりも表現力が高いことが証明された。
  論文  参考訳（メタデータ） (2022-03-22T12:58:03Z)
• Training Free Graph Neural Networks for Graph Matching [103.45755859119035]
  TFGMは、グラフニューラルネットワーク(GNN)ベースのグラフマッチングのパフォーマンスをトレーニングなしで向上するフレームワークである。 TFGMをさまざまなGNNに適用することは、ベースラインよりも有望な改善を示している。
  論文  参考訳（メタデータ） (2022-01-14T09:04:46Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Let's Agree to Degree: Comparing Graph Convolutional Networks in the Message-Passing Framework [5.835421173589977]
  我々は、グラフ上に定義されたニューラルネットワークをメッセージパッシングニューラルネットワーク(MPNN)としてキャストした。 匿名MPNNと学位対応MPNNの2種類のMPNNについて検討する。 Wesfeiler-Lehman (WL)アルゴリズムの差分パワーの観点から,MPNNの差分パワーの下位値と上位値を求める。
  論文  参考訳（メタデータ） (2020-04-06T12:14:00Z)

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

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