論文の概要: Efficiently Counting Substructures by Subgraph GNNs without Running GNN
on Subgraphs
- arxiv url: http://arxiv.org/abs/2303.10576v1
- Date: Sun, 19 Mar 2023 05:35:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-21 18:32:33.419601
- Title: Efficiently Counting Substructures by Subgraph GNNs without Running GNN
on Subgraphs
- Title(参考訳): 部分グラフ上でGNNを走らせることなくGNNによる部分構造を効率的にカウントする
- Authors: Zuoyu Yan, Junru Zhou, Liangcai Gao, Zhi Tang, Muhan Zhang
- Abstract要約: サブグラフGNNを使用する一般的な方法は、入力グラフをサブグラフのコレクションに分解することである。
サブグラフGNNは複雑なサブ構造を数えることができるが、高い計算とメモリコストに悩まされている。
提案モデルでは,GNNを桁違いに高速に動作させながら,GNNのカウント能力を維持することができることを示す。
- 参考スコア(独自算出の注目度): 19.672271500059832
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Using graph neural networks (GNNs) to approximate specific functions such as
counting graph substructures is a recent trend in graph learning. Among these
works, a popular way is to use subgraph GNNs, which decompose the input graph
into a collection of subgraphs and enhance the representation of the graph by
applying GNN to individual subgraphs. Although subgraph GNNs are able to count
complicated substructures, they suffer from high computational and memory
costs. In this paper, we address a non-trivial question: can we count
substructures efficiently with GNNs? To answer the question, we first
theoretically show that the distance to the rooted nodes within subgraphs is
key to boosting the counting power of subgraph GNNs. We then encode such
information into structural embeddings, and precompute the embeddings to avoid
extracting information over all subgraphs via GNNs repeatedly. Experiments on
various benchmarks show that the proposed model can preserve the counting power
of subgraph GNNs while running orders of magnitude faster.
- Abstract(参考訳): グラフニューラルネットワーク(GNN)を用いてグラフサブ構造をカウントするといった特定の関数を近似することは、グラフ学習における最近のトレンドである。
これらの研究の中で一般的な方法は、入力グラフをサブグラフの集合に分解し、個々のサブグラフにGNNを適用することでグラフの表現を強化するサブグラフGNNを使うことである。
サブグラフGNNは複雑なサブ構造を数えることができるが、計算とメモリのコストが高い。
本稿では,非自明な問題に対処し,GNNを用いて,部分構造を効率的に数えることができるか?
この疑問に答えるために、まず、サブグラフ内のルートノード間の距離が、サブグラフGNNのカウント能力を高める鍵であることを理論的に示す。
そして、それらの情報を構造埋め込みにエンコードし、埋め込みを事前計算することで、gnnによる全てのサブグラフの情報抽出を繰り返すのを避ける。
様々なベンチマーク実験により,提案手法は,桁違いに高速に実行しながら,サブグラフgnnのカウントパワーを維持できることが示された。
関連論文リスト
- Subgraphormer: Unifying Subgraph GNNs and Graph Transformers via Graph
Products [22.851643314208715]
本稿では,Subgraphormerを注目と位置エンコーディングと統合するアーキテクチャを提案する。
本結果は,幅広いデータセット上で,Subgraph GNNとGraph Transformerの双方に対して,大幅な性能向上を示した。
論文 参考訳(メタデータ) (2024-02-13T13:37:13Z) - MAG-GNN: Reinforcement Learning Boosted Graph Neural Network [68.60884768323739]
特定の研究の行は、GNNの表現性を向上させるためにサブグラフ情報を使用するサブグラフGNNを提案し、大きな成功を収めた。
このような効果は、すべての可能な部分グラフを列挙することによって、GNNの効率を犠牲にする。
本稿では,強化学習(RL)により強化されたGNNである磁気グラフニューラルネットワーク(MAG-GNN)を提案する。
論文 参考訳(メタデータ) (2023-10-29T20:32:21Z) - Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
グラフニューラルネットワーク(GNN)は、ネットワーク化されたデータの意味のあるパターンを活用するために、グラフ畳み込みに依存している。
我々は,成長するグラフ列の極限オブジェクトであるグラフオンを利用して,非常に大きなグラフ上のGNNを学習することを提案する。
論文 参考訳(メタデータ) (2022-10-27T16:00:45Z) - KerGNNs: Interpretable Graph Neural Networks with Graph Kernels [14.421535610157093]
グラフニューラルネットワーク(GNN)は、下流グラフ関連タスクにおける最先端の手法となっている。
我々は新しいGNNフレームワークKernel Graph Neural Networks(KerGNNs)を提案する。
KerGNNはグラフカーネルをGNNのメッセージパッシングプロセスに統合する。
提案手法は,既存の最先端手法と比較して,競争性能が向上することを示す。
論文 参考訳(メタデータ) (2022-01-03T06:16:30Z) - Nested Graph Neural Networks [20.28732862748783]
グラフニューラルネットワーク(GNN)のグラフ分類における成功は、Weisfeiler-Lehman (1-WL)アルゴリズムと密接に関連している。
そこで我々は,Nested Graph Neural Networks (NGNN) を提案する。
論文 参考訳(メタデータ) (2021-10-25T18:22:24Z) - On Explainability of Graph Neural Networks via Subgraph Explorations [48.56936527708657]
本稿では,グラフニューラルネットワーク(GNN)を説明するための新しい手法,SubgraphXを提案する。
我々の研究は,GNNのサブグラフを明示的に識別する最初の試みである。
論文 参考訳(メタデータ) (2021-02-09T22:12:26Z) - GPT-GNN: Generative Pre-Training of Graph Neural Networks [93.35945182085948]
グラフニューラルネットワーク(GNN)は、グラフ構造化データのモデリングにおいて強力であることが示されている。
生成事前学習によりGNNを初期化するためのGPT-GNNフレームワークを提案する。
GPT-GNNは、様々な下流タスクにおいて、事前トレーニングを最大9.1%行うことなく、最先端のGNNモデルを大幅に上回ることを示す。
論文 参考訳(メタデータ) (2020-06-27T20:12:33Z) - Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs [95.63153473559865]
グラフニューラルネットワーク(GNN)は、グラフ上の新たな機械学習モデルである。
既存のGNNモデルの多くは浅く、本質的に機能中心である。
我々は,既存の浅いGNNがグラフ構造をよく保存できないことを経験的かつ解析的に示す。
本稿では,グラフ構造保存におけるGNNの能力を高めるプラグインモジュールであるEigen-GNNを提案する。
論文 参考訳(メタデータ) (2020-06-08T02:47:38Z) - XGNN: Towards Model-Level Explanations of Graph Neural Networks [113.51160387804484]
グラフニューラルネットワーク(GNN)は、隣の情報を集約して組み合わせることでノードの特徴を学習する。
GNNはブラックボックスとして扱われ、人間の知的な説明が欠けている。
我々はモデルレベルでGNNを解釈する新しい手法 XGNN を提案する。
論文 参考訳(メタデータ) (2020-06-03T23:52:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。