論文の概要: What functions can Graph Neural Networks compute on random graphs? The role of Positional Encoding

• arxiv url: http://arxiv.org/abs/2305.14814v1
• Date: Wed, 24 May 2023 07:09:53 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-25 18:54:08.905276
• Title: What functions can Graph Neural Networks compute on random graphs? The role of Positional Encoding
• Title（参考訳）: ランダムグラフ上でグラフニューラルネットワークが計算できる関数は何か? 位置符号化の役割
• Authors: Nicolas Keriven (CNRS, IRISA), Samuel Vaiter (CNRS, LJAD)
• Abstract要約: 我々は,グラフニューラルネットワーク(GNN)の大規模グラフに対する理論的理解を深めることを目指しており,その表現力に着目している。 近年、GNNは、非常に一般的なランダムグラフモデルにおいて、ノード数が増加するにつれて、特定の関数に収束することを示した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We aim to deepen the theoretical understanding of Graph Neural Networks (GNNs) on large graphs, with a focus on their expressive power. Existing analyses relate this notion to the graph isomorphism problem, which is mostly relevant for graphs of small sizes, or studied graph classification or regression tasks, while prediction tasks on nodes are far more relevant on large graphs. Recently, several works showed that, on very general random graphs models, GNNs converge to certains functions as the number of nodes grows. In this paper, we provide a more complete and intuitive description of the function space generated by equivariant GNNs for node-tasks, through general notions of convergence that encompass several previous examples. We emphasize the role of input node features, and study the impact of node Positional Encodings (PEs), a recent line of work that has been shown to yield state-of-the-art results in practice. Through the study of several examples of PEs on large random graphs, we extend previously known universality results to significantly more general models. Our theoretical results hint at some normalization tricks, which is shown numerically to have a positive impact on GNN generalization on synthetic and real data. Our proofs contain new concentration inequalities of independent interest.
• Abstract（参考訳）: 我々は,グラフニューラルネットワーク(gnns)の大規模グラフに対する理論的理解を深め,その表現力に着目した。 既存の分析では、この概念はグラフ同型問題と関係しており、これは小サイズのグラフや、グラフ分類や回帰タスクの研究に主に関係しており、ノード上の予測タスクは大きなグラフよりもはるかに関連している。 近年、GNNは、非常に一般的なランダムグラフモデルにおいて、ノード数が増加するにつれて特定の関数に収束することを示した。 本稿では、ノードタスクに対する同変gnnによって生成される関数空間のより完全かつ直感的な記述を、いくつかの例を包含する収束の一般概念を通じて提供する。 本稿では,入力ノード機能の役割を強調し,ノード位置エンコーディング(PE)の影響について検討する。 大規模なランダムグラフ上のPEのいくつかの例の研究を通じて、既知の普遍性の結果をはるかに一般的なモデルに拡張する。 理論的な結果は,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)
• Uplifting the Expressive Power of Graph Neural Networks through Graph Partitioning [3.236774847052122]
  グラフ分割のレンズによるグラフニューラルネットワークの表現力について検討する。 我々は新しいGNNアーキテクチャ、すなわちグラフ分割ニューラルネットワーク(GPNN)を導入する。
  論文  参考訳（メタデータ） (2023-12-14T06:08:35Z)
• 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)
• Explicit Pairwise Factorized Graph Neural Network for Semi-Supervised Node Classification [59.06717774425588]
  本稿では,グラフ全体を部分的に観測されたマルコフ確率場としてモデル化するEPFGNN(Explicit Pairwise Factorized Graph Neural Network)を提案する。 出力-出力関係をモデル化するための明示的なペアワイズ要素を含み、入力-出力関係をモデル化するためにGNNバックボーンを使用する。 本研究では,グラフ上での半教師付きノード分類の性能を効果的に向上できることを示す。
  論文  参考訳（メタデータ） (2021-07-27T19:47:53Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Towards Deeper Graph Neural Networks [63.46470695525957]
  グラフ畳み込みは近傍の集約を行い、最も重要なグラフ操作の1つである。 いくつかの最近の研究で、この性能劣化は過度に滑らかな問題に起因している。 本研究では,大きな受容領域からの情報を適応的に組み込むディープ適応グラフニューラルネットワーク(DAGNN)を提案する。
  論文  参考訳（メタデータ） (2020-07-18T01:11:14Z)
• Incomplete Graph Representation and Learning via Partial Graph Neural Networks [7.227805463462352]
  多くのアプリケーションでは、グラフノードの属性が部分的に未知/欠落している不完全な形式でグラフがやってくる可能性がある。 既存のGNNは、属性不完全なグラフデータを直接処理できない完全なグラフに基づいて設計されている。 本研究では,属性不完全グラフ表現と学習のための部分グラフニューラルネットワーク(PaGNN)を新たに開発した。
  論文  参考訳（メタデータ） (2020-03-23T08:29:59Z)
• The Power of Graph Convolutional Networks to Distinguish Random Graph Models: Short Version [27.544219236164764]
  グラフ畳み込みネットワーク(GCN)はグラフ表現学習において広く使われている手法である。 サンプルグラフの埋め込みに基づいて異なるランダムグラフモデルを区別するGCNのパワーについて検討する。
  論文  参考訳（メタデータ） (2020-02-13T17:58:42Z)

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

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