論文の概要: Generalization Limits of Graph Neural Networks in Identity Effects Learning

• arxiv url: http://arxiv.org/abs/2307.00134v1
• Date: Fri, 30 Jun 2023 20:56:38 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-05 17:52:53.895326
• Title: Generalization Limits of Graph Neural Networks in Identity Effects Learning
• Title（参考訳）: アイデンティティ効果学習におけるグラフニューラルネットワークの一般化限界
• Authors: Giuseppe Alessio D'Inverno and Simone Brugiapaglia and Mirco Ravanelli
• Abstract要約: グラフニューラルネットワーク(GNN)は、さまざまなグラフドメインでデータ駆動学習を行う強力なツールとして登場した。 我々は、いわゆるアイデンティティ効果の学習において、GNNの新たな一般化特性と基本的限界を確立する。 我々の研究は、単純な認知タスクを行う際に、GNNの能力を理解する必要性によって動機付けられている。
• 参考スコア（独自算出の注目度）: 9.768161100857405
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph Neural Networks (GNNs) have emerged as a powerful tool for data-driven learning on various graph domains. They are usually based on a message-passing mechanism and have gained increasing popularity for their intuitive formulation, which is closely linked to the Weisfeiler-Lehman (WL) test for graph isomorphism to which they have been proven equivalent in terms of expressive power. In this work, we establish new generalization properties and fundamental limits of GNNs in the context of learning so-called identity effects, i.e., the task of determining whether an object is composed of two identical components or not. Our study is motivated by the need to understand the capabilities of GNNs when performing simple cognitive tasks, with potential applications in computational linguistics and chemistry. We analyze two case studies: (i) two-letters words, for which we show that GNNs trained via stochastic gradient descent are unable to generalize to unseen letters when utilizing orthogonal encodings like one-hot representations; (ii) dicyclic graphs, i.e., graphs composed of two cycles, for which we present positive existence results leveraging the connection between GNNs and the WL test. Our theoretical analysis is supported by an extensive numerical study.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)は、さまざまなグラフドメインでデータ駆動学習を行う強力なツールとして登場した。 それらは通常、メッセージパス機構に基づいており、表現力の点で同等であることが証明されたグラフ同型に対するWeisfeiler-Lehman (WL)テストと密接に関連している直感的な定式化で人気を高めている。 本研究では,物体が2つの同一成分からなるか否かを判断するタスク,いわゆるアイデンティティ効果の学習の文脈において,新たな一般化特性とgnnの基本限界を確立する。 本研究の目的は,GNNが単純な認知タスクを遂行する際の能力を理解することであり,計算言語学や化学への応用の可能性にある。 2つのケーススタディを分析しました (i)二文字の単語は、一線表現のような直交符号化を利用する場合、確率勾配降下により訓練されたGNNが、見知らぬ文字に一般化できないことを示す。 (ii)二環グラフ、すなわち2つのサイクルからなるグラフは、GNNとWLテストの接続を利用して正の存在結果を示す。 我々の理論解析は広範な数値研究によって裏付けられている。

関連論文リスト

• 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)
• Graph Neural Networks Provably Benefit from Structural Information: A Feature Learning Perspective [53.999128831324576]
  グラフニューラルネットワーク(GNN)は、グラフ表現学習の先駆けとなった。 本研究では,特徴学習理論の文脈におけるグラフ畳み込みの役割について検討する。
  論文  参考訳（メタデータ） (2023-06-24T10:21:11Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• 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)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)
• Can Graph Neural Networks Count Substructures? [53.256112515435355]
  グラフニューラルネットワーク(GNN)の能力について,属性付きグラフサブ構造をカウントする能力を用いて検討する。 我々は2種類のサブストラクチャカウントを区別する: インダクションサブグラフカウントとサブグラフカウント、および人気のあるGNNアーキテクチャに対する肯定的および否定的な回答である。
  論文  参考訳（メタデータ） (2020-02-10T18:53:30Z)

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

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