論文の概要: An Efficient Subgraph GNN with Provable Substructure Counting Power

• arxiv url: http://arxiv.org/abs/2303.10576v2
• Date: Thu, 13 Jun 2024 06:48:19 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-15 02:38:50.649682
• Title: An Efficient Subgraph GNN with Provable Substructure Counting Power
• Title（参考訳）: 確率的部分構造カウントパワーを有する高効率サブグラフGNN
• Authors: Zuoyu Yan, Junru Zhou, Liangcai Gao, Zhi Tang, Muhan Zhang,
• Abstract要約: 本稿では,グラフニューラルネットワーク(GNN)のサブストラクチャカウント能力による表現能力の向上について検討する。 近年の進歩では、入力グラフを多数のサブグラフに分割するサブグラフGNNが採用され、グラフ全体の表現を拡大するためにそれぞれにGNNが適用されるようになった。 様々なサブ構造を識別できるにもかかわらず、サブグラフGNNは計算とメモリの大幅なコストによって妨げられる。
• 参考スコア（独自算出の注目度）: 32.44487589958533
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the enhancement of graph neural networks' (GNNs) representation power through their ability in substructure counting. Recent advances have seen the adoption of subgraph GNNs, which partition an input graph into numerous subgraphs, subsequently applying GNNs to each to augment the graph's overall representation. Despite their ability to identify various substructures, subgraph GNNs are hindered by significant computational and memory costs. In this paper, we tackle a critical question: Is it possible for GNNs to count substructures both \textbf{efficiently} and \textbf{provably}? Our approach begins with a theoretical demonstration that the distance to rooted nodes in subgraphs is key to boosting the counting power of subgraph GNNs. To avoid the need for repetitively applying GNN across all subgraphs, we introduce precomputed structural embeddings that encapsulate this crucial distance information. Experiments validate that our proposed model retains the counting power of subgraph GNNs while achieving significantly faster performance.
• Abstract（参考訳）: 本稿では,グラフニューラルネットワーク(GNN)のサブストラクチャカウント能力による表現能力の向上について検討する。 近年の進歩では、入力グラフを多数のサブグラフに分割するサブグラフGNNが採用され、グラフ全体の表現を拡大するためにそれぞれにGNNが適用されるようになった。 様々なサブ構造を識別できるにもかかわらず、サブグラフGNNは計算とメモリの大幅なコストによって妨げられる。 本稿では、GNNが \textbf{efficiently} と \textbf{provably} の両方のサブ構造をカウントすることは可能か? 我々のアプローチは、サブグラフ内のルートノード間距離が、サブグラフ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)

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

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