論文の概要: 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のカウントパワーを維持できることが示された。

関連論文リスト

• MAG-GNN: Reinforcement Learning Boosted Graph Neural Network [68.60884768323739]
  特定の研究の行は、GNNの表現性を向上させるためにサブグラフ情報を使用するサブグラフGNNを提案し、大きな成功を収めた。 このような効果は、すべての可能な部分グラフを列挙することによって、GNNの効率を犠牲にする。 本稿では,強化学習(RL)により強化されたGNNである磁気グラフニューラルネットワーク(MAG-GNN)を提案する。
  論文  参考訳（メタデータ） (2023-10-29T20:32:21Z)
• GNN-Ensemble: Towards Random Decision Graph Neural Networks [3.7620848582312405]
  グラフニューラルネットワーク(GNN)は、グラフ構造化データに広く応用されている。 GNNは、大量のテストデータに基づいて推論を行うために、限られた量のトレーニングデータから潜伏パターンを学習する必要がある。 本稿では、GNNのアンサンブル学習を一歩前進させ、精度、堅牢性、敵攻撃を改善した。
  論文  参考訳（メタデータ） (2023-03-20T18:24:01Z)
• Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
  グラフニューラルネットワーク(GNN)は、ネットワーク化されたデータの意味のあるパターンを活用するために、グラフ畳み込みに依存している。 我々は,成長するグラフ列の極限オブジェクトであるグラフオンを利用して,非常に大きなグラフ上のGNNを学習することを提案する。
  論文  参考訳（メタデータ） (2022-10-27T16:00:45Z)
• Boosting the Cycle Counting Power of Graph Neural Networks with I$^2$-GNNs [9.806910643086043]
  本稿では,各サブグラフ内のルートノードとその隣人に異なる識別子を割り当てることで,サブグラフMPNNを拡張するための2$-GNNを提案する。 2$-GNNsの識別力は、サブグラフMPNNよりも強く、3WLテストより部分的に強いことが示されている。 我々の知る限りでは、理論的な保証とともに6サイクルを数えられる最初の線形時間GNNモデルである。
  論文  参考訳（メタデータ） (2022-10-22T09:40:00Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Expressive Power of Invariant and Equivariant Graph Neural Networks [10.419350129060598]
  Folklore Graph Neural Networks (FGNN) は、与えられたテンソル次数に対してこれまで提案されてきた最も表現力のあるアーキテクチャである。 FGNNはこの問題の解決方法を学ぶことができ、既存のアルゴリズムよりも平均的なパフォーマンスが向上する。
  論文  参考訳（メタデータ） (2020-06-28T16:35:45Z)
• Fast Graph Attention Networks Using Effective Resistance Based Graph Sparsification [70.50751397870972]
  FastGATは、スペクトルスペーシフィケーションを用いて、注目に基づくGNNを軽量にし、入力グラフの最適プルーニングを生成する手法である。 我々は,ノード分類タスクのための大規模実世界のグラフデータセット上でFastGATを実験的に評価した。
  論文  参考訳（メタデータ） (2020-06-15T22:07:54Z)
• 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)

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

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