論文の概要: OOD Link Prediction Generalization Capabilities of Message-Passing GNNs in Larger Test Graphs

• arxiv url: http://arxiv.org/abs/2205.15117v2
• Date: Wed, 1 Jun 2022 11:23:17 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-04 09:58:29.847566
• Title: OOD Link Prediction Generalization Capabilities of Message-Passing GNNs in Larger Test Graphs
• Title（参考訳）: 大規模テストグラフにおけるメッセージパージングGNNのOODリンク予測一般化機能
• Authors: Yangze Zhou, Gitta Kutyniok, Bruno Ribeiro
• Abstract要約: この研究は、メッセージパッシングニューラルネットワーク(gMPNN)をグラフ化し、誘導的アウト・オブ・ディストリビューション(OOD)リンク予測タスクを実行する能力に関する最初の理論的研究を提供する。 まず、置換同変(構造的)ノード埋め込みに基づくリンク予測器が、テストグラフが大きくなるにつれてランダムな推測に収束することを示す。 次に、構造的なペア(2ノード)埋め込みを出力し、テストグラフが大きくなるにつれて、これらの埋め込みが埋め込みに収束することを示す理論的に正しいgMPNNを提案する。
• 参考スコア（独自算出の注目度）: 13.118954965368333
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This work provides the first theoretical study on the ability of graph Message Passing Neural Networks (gMPNNs) -- such as Graph Neural Networks (GNNs) -- to perform inductive out-of-distribution (OOD) link prediction tasks, where deployment (test) graph sizes are larger than training graphs. We first prove non-asymptotic bounds showing that link predictors based on permutation-equivariant (structural) node embeddings obtained by gMPNNs can converge to a random guess as test graphs get larger. We then propose a theoretically-sound gMPNN that outputs structural pairwise (2-node) embeddings and prove non-asymptotic bounds showing that, as test graphs grow, these embeddings converge to embeddings of a continuous function that retains its ability to predict links OOD. Empirical results on random graphs show agreement with our theoretical results.
• Abstract（参考訳）: この研究は、グラフニューラルネットワーク(gnns)のようなグラフメッセージパッシングニューラルネットワーク(gmpnn)が、トレーニンググラフよりもデプロイ(テスト)グラフのサイズが大きい、誘導的分散(ood)リンク予測タスクを実行する能力に関する、最初の理論的研究を提供する。 まず,gMPNNで得られた置換同変(構造)ノード埋め込みに基づくリンク予測器が,テストグラフが大きくなるにつれてランダムな推測に収束することを示す。 次に、構造的対(2ノード)埋め込みを出力し、テストグラフが大きくなるにつれて、これらの埋め込みが連続関数の埋め込みに収束し、OODを予測できることを示す。 ランダムグラフにおける実験結果は理論結果と一致している。

関連論文リスト

• Graph neural networks and non-commuting operators [4.912318087940015]
  我々は,グラフトン・タプルニューラルネットワークの極限理論を開発し,それを普遍的な伝達可能性定理の証明に利用する。 我々の理論的結果は、GNNのよく知られた移動可能性定理を、複数の同時グラフの場合にまで拡張する。 得られたモデルの安定性を確実に実施する訓練手順を導出する。
  論文  参考訳（メタデータ） (2024-11-06T21:17:14Z)
• 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)
• Disentangling Node Attributes from Graph Topology for Improved Generalizability in Link Prediction [5.651457382936249]
  提案手法であるUPNAは,一対のノード属性を学習し,エッジの確率を予測することによって,帰納的リンク予測問題を解く。 UPNAは、様々なペアワイズ学習タスクに適用でき、既存のリンク予測モデルと統合して、一般化可能性とグラフ生成モデルを強化することができる。
  論文  参考訳（メタデータ） (2023-07-17T22:19:12Z)
• What functions can Graph Neural Networks compute on random graphs? The role of Positional Encoding [0.0]
  我々は,グラフニューラルネットワーク(GNN)の大規模グラフに対する理論的理解を深めることを目指しており,その表現力に着目している。 近年、GNNは、非常に一般的なランダムグラフモデルにおいて、ノード数が増加するにつれて、特定の関数に収束することを示した。
  論文  参考訳（メタデータ） (2023-05-24T07:09:53Z)
• Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion [17.70434437597516]
  本稿では,グラフニューラルネットワークの特徴拡散行列の最大特異値でスケールする一般化境界について述べる。 これらの境界は実世界のグラフの以前の境界よりも数値的にはるかに小さい。 ヘッセン語を用いた雑音摂動に対するグラフニューラルネットワークの安定性を測定する。
  論文  参考訳（メタデータ） (2023-02-09T05:54:17Z)
• When Do We Need Graph Neural Networks for Node Classification? [38.68793097833027]
  グラフニューラルネットワーク(GNN)は基本ニューラルネットワーク(NN)を拡張する 場合によっては、GNNのパフォーマンスは向上せず、グラフに依存しないNNの性能も低くなる。
  論文  参考訳（メタデータ） (2022-10-30T23:10:23Z)
• Generalizing Graph Neural Networks on Out-Of-Distribution Graphs [51.33152272781324]
  トレーニンググラフとテストグラフの分散シフトを考慮せずにグラフニューラルネットワーク(GNN)を提案する。 このような環境では、GNNは、たとえ素早い相関であるとしても、予測のためのトレーニングセットに存在する微妙な統計的相関を利用する傾向がある。 本稿では,スプリアス相関の影響を排除するため,StableGNNと呼ばれる一般的な因果表現フレームワークを提案する。
  論文  参考訳（メタデータ） (2021-11-20T18:57:18Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)
• Can Graph Neural Networks Count Substructures? [53.256112515435355]
  グラフニューラルネットワーク(GNN)の能力について,属性付きグラフサブ構造をカウントする能力を用いて検討する。 我々は2種類のサブストラクチャカウントを区別する: インダクションサブグラフカウントとサブグラフカウント、および人気のあるGNNアーキテクチャに対する肯定的および否定的な回答である。
  論文  参考訳（メタデータ） (2020-02-10T18:53:30Z)

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

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