論文の概要: Expressive Power of Invariant and Equivariant Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2006.15646v3
- Date: Sun, 6 Jun 2021 15:37:55 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-16 02:24:47.150443
- Title: Expressive Power of Invariant and Equivariant Graph Neural Networks
- Title（参考訳）: 不変および同変グラフニューラルネットワークの表現力
- Authors: Wa\"iss Azizian, Marc Lelarge
- Abstract要約: Folklore Graph Neural Networks (FGNN) は、与えられたテンソル次数に対してこれまで提案されてきた最も表現力のあるアーキテクチャである。
FGNNはこの問題の解決方法を学ぶことができ、既存のアルゴリズムよりも平均的なパフォーマンスが向上する。
- 参考スコア（独自算出の注目度）: 10.419350129060598
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Various classes of Graph Neural Networks (GNN) have been proposed and shown
to be successful in a wide range of applications with graph structured data. In
this paper, we propose a theoretical framework able to compare the expressive
power of these GNN architectures. The current universality theorems only apply
to intractable classes of GNNs. Here, we prove the first approximation
guarantees for practical GNNs, paving the way for a better understanding of
their generalization. Our theoretical results are proved for invariant GNNs
computing a graph embedding (permutation of the nodes of the input graph does
not affect the output) and equivariant GNNs computing an embedding of the nodes
(permutation of the input permutes the output). We show that Folklore Graph
Neural Networks (FGNN), which are tensor based GNNs augmented with matrix
multiplication are the most expressive architectures proposed so far for a
given tensor order. We illustrate our results on the Quadratic Assignment
Problem (a NP-Hard combinatorial problem) by showing that FGNNs are able to
learn how to solve the problem, leading to much better average performances
than existing algorithms (based on spectral, SDP or other GNNs architectures).
On a practical side, we also implement masked tensors to handle batches of
graphs of varying sizes.
- Abstract（参考訳）: グラフニューラルネットワーク(gnn)の様々なクラスが提案され、グラフ構造化データを用いた幅広いアプリケーションで成功していることが示されている。
本稿では,これらのGNNアーキテクチャの表現力を比較するための理論的枠組みを提案する。
現在の普遍性定理は、GNNの難解類にのみ適用される。
ここでは,実用的なGNNに対する最初の近似保証を証明し,それらの一般化をよりよく理解するための道を開く。
我々の理論的結果は,グラフ埋め込み(入力グラフのノードの置換は出力に影響を与えない)とノードの埋め込み(入力の置換は出力に影響を及ぼす)を演算する同変GNNに対して証明される。
行列乗算を付加したテンソルベースGNNであるFolklore Graph Neural Networks (FGNN) が, 与えられたテンソル次数に対して提案されている最も表現力のあるアーキテクチャであることを示す。
本稿では、FGNNが既存のアルゴリズム(スペクトル、SDP、その他のGNNアーキテクチャに基づく)よりもずっと優れた平均性能を実現することができることを示すことにより、擬似代入問題(NP-Hard組合せ問題)について述べる。
実用的側面として,様々な大きさのグラフのバッチを扱うためのマスクテンソルも実装している。
関連論文リスト
- A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
我々は、スペクトル領域の多様体からサンプリングされたグラフ上のGNNの統計的一般化理論を確立するために多様体の視点を取る。
我々はGNNの一般化境界が対数スケールのグラフのサイズとともに線形に減少し、フィルタ関数のスペクトル連続定数とともに線形的に増加することを証明した。
論文 参考訳（メタデータ） (2024-06-07T19:25:02Z) - Degree-based stratification of nodes in Graph Neural Networks [66.17149106033126]
グラフニューラルネットワーク(GNN)アーキテクチャを変更して,各グループのノードに対して,重み行列を個別に学習する。
このシンプルな実装変更により、データセットとGNNメソッドのパフォーマンスが改善されているようだ。
論文 参考訳（メタデータ） (2023-12-16T14:09:23Z) - Equivariant Polynomials for Graph Neural Networks [38.15983687193912]
グラフネットワーク(GNN)は本質的に表現力に制限がある。
本稿では、GNNがある程度の同変を計算する能力に基づく代替パワー階層を提案する。
これらの強化されたGNNは、複数のグラフ学習ベンチマークの実験において最先端の結果を示す。
論文 参考訳（メタデータ） (2023-02-22T18:53:38Z) - Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
グラフニューラルネットワーク(GNN)は、ネットワーク化されたデータの意味のあるパターンを活用するために、グラフ畳み込みに依存している。
我々は,成長するグラフ列の極限オブジェクトであるグラフオンを利用して,非常に大きなグラフ上のGNNを学習することを提案する。
論文 参考訳（メタデータ） (2022-10-27T16:00:45Z) - Towards Better Generalization with Flexible Representation of
Multi-Module Graph Neural Networks [0.27195102129094995]
ランダムグラフ生成器を用いて,グラフサイズと構造特性がGNNの予測性能に与える影響について検討する。
本稿では,GNNが未知のグラフに一般化できるかどうかを決定する上で,平均ノード次数が重要な特徴であることを示す。
集約された入力に対して単一の正準非線形変換を一般化することにより、ネットワークが新しいグラフに柔軟に対応可能なマルチモジュールGNNフレームワークを提案する。
論文 参考訳（メタデータ） (2022-09-14T12:13:59Z) - Graph Neural Networks with Local Graph Parameters [1.8600631687568656]
ローカルグラフパラメータは、任意のグラフニューラルネットワーク(GNN)アーキテクチャに追加することができる。
我々の結果は、有限モデル理論と有限変数論理の深い結果とGNNを結びつける。
論文 参考訳（メタデータ） (2021-06-12T07:43:51Z) - A Unified View on Graph Neural Networks as Graph Signal Denoising [49.980783124401555]
グラフニューラルネットワーク(GNN)は,グラフ構造化データの学習表現において顕著に普及している。
本研究では,代表的GNNモデル群における集約過程を,グラフ記述問題の解法とみなすことができることを数学的に確立する。
UGNNから派生した新しいGNNモデルADA-UGNNをインスタンス化し、ノード間の適応的滑らかさでグラフを処理する。
論文 参考訳（メタデータ） (2020-10-05T04:57:18Z) - The Surprising Power of Graph Neural Networks with Random Node
Initialization [54.4101931234922]
グラフニューラルネットワーク(GNN)は、関係データ上での表現学習に有効なモデルである。
標準 GNN はその表現力に制限があり、Weisfeiler-Leman グラフ同型(英語版)の能力以外の区別はできない。
本研究では,ランダムノード(RNI)を用いたGNNの表現力の解析を行う。
我々はこれらのモデルが普遍的であることを証明し、GNNが高次特性の計算に頼らない最初の結果である。
論文 参考訳（メタデータ） (2020-10-02T19:53:05Z) - Distance Encoding: Design Provably More Powerful Neural Networks for
Graph Representation Learning [63.97983530843762]
グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。
GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。
より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。
本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
論文 参考訳（メタデータ） (2020-08-31T23:15:40Z) - Random Features Strengthen Graph Neural Networks [40.60905158071766]
グラフニューラルネットワーク(GNN)は、さまざまなグラフ学習タスクのための強力な機械学習モデルである。
本稿では,各ノードにランダムな特徴を加えるだけで,GNNが強力になることを示す。
本稿では, グラフ畳み込みネットワーク (GCN) やグラフ同型ネットワーク (GIN) など, 通常のGNNでは解けない様々な問題を, ランダムな特徴の追加によりGNNが解決できることを示す。
論文 参考訳（メタデータ） (2020-02-08T12:47:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。