論文の概要: Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries
- arxiv url: http://arxiv.org/abs/2206.11140v1
- Date: Wed, 22 Jun 2022 14:35:47 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-23 15:28:30.201292
- Title: Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries
- Title(参考訳): 対称性の再考によるグラフGNNの理解と拡張
- Authors: Fabrizio Frasca, Beatrice Bevilacqua, Michael M. Bronstein, Haggai
Maron
- Abstract要約: グラフGNNはグラフをサブグラフのコレクションとしてモデル化するグラフニューラルネットワーク(GNN)の最近のクラスである。
ノードベースの部分グラフ選択ポリシーを用いた,最も顕著な部分グラフ法について検討する。
本稿では,従来のノードベースサブグラフGNNを一般化したサブグラフ手法に対して,メッセージパッシングの一般的なファミリを提案する。
- 参考スコア(独自算出の注目度): 33.07812045457703
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Subgraph GNNs are a recent class of expressive Graph Neural Networks (GNNs)
which model graphs as collections of subgraphs. So far, the design space of
possible Subgraph GNN architectures as well as their basic theoretical
properties are still largely unexplored. In this paper, we study the most
prominent form of subgraph methods, which employs node-based subgraph selection
policies such as ego-networks or node marking and deletion. We address two
central questions: (1) What is the upper-bound of the expressive power of these
methods? and (2) What is the family of equivariant message passing layers on
these sets of subgraphs?. Our first step in answering these questions is a
novel symmetry analysis which shows that modelling the symmetries of node-based
subgraph collections requires a significantly smaller symmetry group than the
one adopted in previous works. This analysis is then used to establish a link
between Subgraph GNNs and Invariant Graph Networks (IGNs). We answer the
questions above by first bounding the expressive power of subgraph methods by
3-WL, and then proposing a general family of message-passing layers for
subgraph methods that generalises all previous node-based Subgraph GNNs.
Finally, we design a novel Subgraph GNN dubbed SUN, which theoretically unifies
previous architectures while providing better empirical performance on multiple
benchmarks.
- Abstract(参考訳): グラフGNNはグラフをサブグラフのコレクションとしてモデル化するグラフニューラルネットワーク(GNN)の最近のクラスである。
これまでのところ、サブグラフGNNアーキテクチャやその基本的な理論的性質の設計領域は、まだ明らかにされていない。
本稿では,egoネットワークやノードマーキングや削除といった,ノードベースのサブグラフ選択ポリシを用いたサブグラフ手法の最も顕著な形態について検討する。
1)これらの手法の表現力の上限は何か?
そして、(2)これらのサブグラフの集合上の同変メッセージパッシングレイヤのファミリーは何ですか?
.
これらの質問に答える最初のステップは、ノードベースの部分グラフコレクションの対称性をモデル化するには、以前の研究で採用されたものよりもはるかに小さな対称性群が必要であることを示す新しい対称性解析である。
この分析は、サブグラフGNNと不変グラフネットワーク(IGN)のリンクを確立するために使われる。
本稿では,まず3WLでサブグラフ手法の表現力を表現し,次に,従来のノードベースサブグラフGNNを一般化したサブグラフ方式の一般的なメッセージパス層を提案する。
最後に、SUNと呼ばれる新しいサブグラフGNNを設計し、理論的には以前のアーキテクチャを統一し、複数のベンチマーク上でより優れた経験的性能を提供する。
関連論文リスト
- A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening [18.688057947275112]
グラフグラフニューラルネットワーク(サブグラフGNN)は,グラフをサブグラフの集合として表現することで,メッセージパスGNNの表現性を向上する。
以前のアプローチでは、ランダムにまたは学習可能なサンプリングによって選択されたサブグラフのサブセットのみを処理することを提案していた。
本稿では,これらの問題に対処する新しいSubgraph GNNフレームワークを提案する。
論文 参考訳(メタデータ) (2024-06-13T16:29:06Z) - From Hypergraph Energy Functions to Hypergraph Neural Networks [94.88564151540459]
パラメータ化されたハイパーグラフ正規化エネルギー関数の表現型族を示す。
次に、これらのエネルギーの最小化がノード埋め込みとして効果的に機能することを実証する。
提案した双レベルハイパーグラフ最適化と既存のGNNアーキテクチャを共通的に用いている。
論文 参考訳(メタデータ) (2023-06-16T04:40:59Z) - Seq-HGNN: Learning Sequential Node Representation on Heterogeneous Graph [57.2953563124339]
本稿では,シーケンシャルノード表現,すなわちSeq-HGNNを用いた新しい異種グラフニューラルネットワークを提案する。
Heterogeneous Graph Benchmark (HGB) と Open Graph Benchmark (OGB) の4つの広く使われているデータセットについて広範な実験を行った。
論文 参考訳(メタデータ) (2023-05-18T07:27:18Z) - Stochastic Subgraph Neighborhood Pooling for Subgraph Classification [2.1270496914042996]
Subgraph Neighborhood Pooling (SSNP) は、ラベル付けトリックのような計算コストの高い操作をすることなく、サブグラフとその周辺情報を共同で集約する。
実験により、我々のモデルは、トレーニングにおいて最大3倍高速でありながら、最先端の手法(マージンが最大2%)より優れています。
論文 参考訳(メタデータ) (2023-04-17T18:49:18Z) - Bring Your Own View: Graph Neural Networks for Link Prediction with
Personalized Subgraph Selection [57.34881616131377]
異なるエッジに対して最適なサブグラフを自動,個人的,帰納的に識別するプラグイン・アンド・プレイ・フレームワークとしてパーソナライズされたサブグラフセレクタ(PS2)を導入する。
PS2は二段階最適化問題としてインスタンス化され、効率よく解ける。
GNNLPトレーニングに対する新たなアプローチとして,まずエッジの最適な部分グラフを識別し,次にサンプル部分グラフを用いて推論モデルをトレーニングすることを提案する。
論文 参考訳(メタデータ) (2022-12-23T17:30:19Z) - Graph Convolutional Networks with Dual Message Passing for Subgraph
Isomorphism Counting and Matching [42.55928561326902]
グラフニューラルネットワーク(GNN)とメッセージパッシングニューラルネットワーク(MPNN)は、サブグラフ構造に対して表現可能であることが証明されている。
サブストラクチャ表現学習を強化するために,デュアルメッセージパッシングニューラルネットワーク(DMPNN)を提案する。
論文 参考訳(メタデータ) (2021-12-16T10:23:48Z) - VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using
Vector Quantization [70.8567058758375]
VQ-GNNは、Vector Quantization(VQ)を使用して、パフォーマンスを損なうことなく、畳み込みベースのGNNをスケールアップするための普遍的なフレームワークである。
我々のフレームワークは,グラフ畳み込み行列の低ランク版と組み合わせた量子化表現を用いて,GNNの「隣の爆発」問題を回避する。
論文 参考訳(メタデータ) (2021-10-27T11:48:50Z) - On Explainability of Graph Neural Networks via Subgraph Explorations [48.56936527708657]
本稿では,グラフニューラルネットワーク(GNN)を説明するための新しい手法,SubgraphXを提案する。
我々の研究は,GNNのサブグラフを明示的に識別する最初の試みである。
論文 参考訳(メタデータ) (2021-02-09T22:12:26Z) - Scalable Graph Neural Networks for Heterogeneous Graphs [12.44278942365518]
グラフニューラルネットワーク(GNN)は、グラフ構造化データを学習するためのパラメトリックモデルの一般的なクラスである。
最近の研究は、GNNが主に機能をスムースにするためにグラフを使用しており、ベンチマークタスクで競合する結果を示していると主張している。
本研究では、これらの結果が異種グラフに拡張可能かどうかを問うとともに、異なるエンティティ間の複数のタイプの関係を符号化する。
論文 参考訳(メタデータ) (2020-11-19T06:03:35Z) - Distance Encoding: Design Provably More Powerful Neural Networks for
Graph Representation Learning [63.97983530843762]
グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。
GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。
より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。
本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
論文 参考訳(メタデータ) (2020-08-31T23:15:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。