論文の概要: OOD Link Prediction Generalization Capabilities of Message-Passing GNNs
in Larger Test Graphs
- arxiv url: http://arxiv.org/abs/2205.15117v1
- Date: Mon, 30 May 2022 14:04:32 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-31 20:25:11.771175
- 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を予測できることを示す。
ランダムグラフにおける実験結果は理論結果と一致している。
関連論文リスト
- 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) - Relation Embedding based Graph Neural Networks for Handling
Heterogeneous Graph [58.99478502486377]
我々は、同種GNNが不均一グラフを扱うのに十分な能力を持つように、シンプルで効率的なフレームワークを提案する。
具体的には、エッジ型関係と自己ループ接続の重要性を埋め込むために、関係1つのパラメータのみを使用する関係埋め込みベースのグラフニューラルネットワーク(RE-GNN)を提案する。
論文 参考訳(メタデータ) (2022-09-23T05:24:18Z) - Towards Better Generalization with Flexible Representation of
Multi-Module Graph Neural Networks [0.27195102129094995]
ランダムグラフ生成器を用いて,グラフサイズと構造特性がGNNの予測性能に与える影響について検討する。
本稿では,GNNが未知のグラフに一般化できるかどうかを決定する上で,平均ノード次数が重要な特徴であることを示す。
集約された入力に対して単一の正準非線形変換を一般化することにより、ネットワークが新しいグラフに柔軟に対応可能なマルチモジュールGNNフレームワークを提案する。
論文 参考訳(メタデータ) (2022-09-14T12:13:59Z) - Generalizing Graph Neural Networks on Out-Of-Distribution Graphs [51.33152272781324]
トレーニンググラフとテストグラフの分散シフトを考慮せずにグラフニューラルネットワーク(GNN)を提案する。
このような環境では、GNNは、たとえ素早い相関であるとしても、予測のためのトレーニングセットに存在する微妙な統計的相関を利用する傾向がある。
本稿では,スプリアス相関の影響を排除するため,StableGNNと呼ばれる一般的な因果表現フレームワークを提案する。
論文 参考訳(メタデータ) (2021-11-20T18:57:18Z) - Permutation-equivariant and Proximity-aware Graph Neural Networks with
Stochastic Message Passing [88.30867628592112]
グラフニューラルネットワーク(GNN)は、グラフ上の新たな機械学習モデルである。
置換等価性と近接認識性は、GNNにとって非常に望ましい2つの重要な特性である。
既存のGNNは、主にメッセージパッシング機構に基づいており、同時に2つの特性を保存できないことを示す。
ノードの近さを保つため,既存のGNNをノード表現で拡張する。
論文 参考訳(メタデータ) (2020-09-05T16:46:56Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。