論文の概要: Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results

• arxiv url: http://arxiv.org/abs/2012.03174v1
• Date: Sun, 6 Dec 2020 03:42:54 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-22 09:22:03.272995
• Title: Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results
• Title（参考訳）: 高次グラフニューラルネットワークによるサブ構造の推定:可能性と不可能性
• Authors: Behrooz Tahmasebi, Stefanie Jegelka
• Abstract要約: グラフニューラルネットワーク(GNN)の計算コストと表現力のトレードオフについて検討する。 新しいモデルでは、$k$のサブグラフをカウントでき、低次GNNの既知の制限を克服できることを示す。 いくつかの場合において、提案アルゴリズムは既存の高階$k$-GNNに比べて計算量を大幅に削減することができる。
• 参考スコア（独自算出の注目度）: 58.277290855841976
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: While massage passing based Graph Neural Networks (GNNs) have become increasingly popular architectures for learning with graphs, recent works have revealed important shortcomings in their expressive power. In response, several higher-order GNNs have been proposed, which substantially increase the expressive power, but at a large computational cost. Motivated by this gap, we introduce and analyze a new recursive pooling technique of local neighborhoods that allows different tradeoffs of computational cost and expressive power. First, we show that this model can count subgraphs of size $k$, and thereby overcomes a known limitation of low-order GNNs. Second, we prove that, in several cases, the proposed algorithm can greatly reduce computational complexity compared to the existing higher-order $k$-GNN and Local Relational Pooling (LRP) networks. We also provide a (near) matching information-theoretic lower bound for graph representations that can provably count subgraphs, and discuss time complexity lower bounds as well.
• Abstract（参考訳）: マッサージパスベースのグラフニューラルネットワーク(GNN)は、グラフで学ぶための人気アーキテクチャになりつつあるが、最近の研究は、その表現力の重要な欠点を明らかにしている。 これに対し、いくつかの高次GNNが提案され、表現力を大幅に向上するが、計算コストが大きい。 このギャップに動機づけられ、計算コストと表現力のトレードオフを異なるものにする、ローカル近傍の新たな再帰的プーリング技術を導入し、分析する。 まず、このモデルでは、$k$のサブグラフをカウントでき、低次GNNの既知の制限を克服できることを示す。 第二に、いくつかのケースにおいて、提案アルゴリズムは既存の$k$-GNNやローカルリレーショナルポーリング(LRP)ネットワークと比較して計算複雑性を大幅に削減できることを示す。 また,グラフ表現のための情報理論下限を(近く)マッチングし,サブグラフのカウントを可能とし,時間複雑性下限についても議論する。

関連論文リスト

• SPGNN: Recognizing Salient Subgraph Patterns via Enhanced Graph Convolution and Pooling [25.555741218526464]
  グラフニューラルネットワーク(GNN)は、グラフやネットワークのような非ユークリッドデータ上での機械学習の分野に革命をもたらした。 本稿では,ノード表現をインジェクティブに更新する結合型グラフ畳み込み機構を提案する。 また,WL-SortPoolと呼ばれるグラフプーリングモジュールを設計し,重要なサブグラフパターンをディープラーニングで学習する。
  論文  参考訳（メタデータ） (2024-04-21T13:11:59Z)
• MAG-GNN: Reinforcement Learning Boosted Graph Neural Network [68.60884768323739]
  特定の研究の行は、GNNの表現性を向上させるためにサブグラフ情報を使用するサブグラフGNNを提案し、大きな成功を収めた。 このような効果は、すべての可能な部分グラフを列挙することによって、GNNの効率を犠牲にする。 本稿では,強化学習(RL)により強化されたGNNである磁気グラフニューラルネットワーク(MAG-GNN)を提案する。
  論文  参考訳（メタデータ） (2023-10-29T20:32:21Z)
• Factor Graph Neural Networks [20.211455592922736]
  グラフニューラルネットワーク(GNN)は、多くの現実世界のアプリケーションで大きな成功を収めながら、エンドツーエンドで強力な表現を学習することができる。 推論と学習の高次関係を効果的に捉えるためにFGNN(Facter Graph Neural Networks)を提案する。
  論文  参考訳（メタデータ） (2023-08-02T00:32:02Z)
• A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking [124.21408098724551]
  グラフニューラルネットワーク(GNN)の大規模グラフトレーニングは、非常に難しい問題である 本稿では,既存の問題に対処するため,EnGCNという新たなアンサンブルトレーニング手法を提案する。 提案手法は,大規模データセット上でのSOTA(State-of-the-art)の性能向上を実現している。
  論文  参考訳（メタデータ） (2022-10-14T03:43:05Z)
• Relation Embedding based Graph Neural Networks for Handling Heterogeneous Graph [58.99478502486377]
  我々は、同種GNNが不均一グラフを扱うのに十分な能力を持つように、シンプルで効率的なフレームワークを提案する。 具体的には、エッジ型関係と自己ループ接続の重要性を埋め込むために、関係1つのパラメータのみを使用する関係埋め込みベースのグラフニューラルネットワーク(RE-GNN)を提案する。
  論文  参考訳（メタデータ） (2022-09-23T05:24:18Z)
• Simple and Efficient Heterogeneous Graph Neural Network [55.56564522532328]
  不均一グラフニューラルネットワーク(HGNN)は、不均一グラフの豊富な構造的および意味的な情報をノード表現に埋め込む強力な能力を持つ。 既存のHGNNは、同種グラフ上のグラフニューラルネットワーク(GNN)から多くのメカニズム、特に注意機構と多層構造を継承する。 本稿では,これらのメカニズムを詳細に検討し,簡便かつ効率的なヘテロジニアスグラフニューラルネットワーク(SeHGNN)を提案する。
  論文  参考訳（メタデータ） (2022-07-06T10:01:46Z)
• Decoupling the Depth and Scope of Graph Neural Networks [21.273445344654597]
  最先端のグラフニューラルネットワーク(GNN)は、グラフとモデルサイズに関して、スケーラビリティに制限がある。 本稿では,GNNの深度と範囲を分離する設計原理を提案する。 我々の設計は、計算量やハードウェアコストの大幅な削減により、大幅な精度向上を実現している。
  論文  参考訳（メタデータ） (2022-01-19T20:52:42Z)
• Weisfeiler and Lehman Go Cellular: CW Networks [3.0017241250121383]
  グラフニューラルネットワーク(GNN)は、表現力に制限があり、長距離相互作用に苦慮し、高次構造をモデル化する原則的な方法が欠けている。 SC の最近の理論的結果は、SC とグラフを柔軟にサブスムする位相対象である正則なセルコンプレックスに拡張する。 この一般化は、グラフリフトの変換の強力なセットを提供し、それぞれがユニークなメッセージパッシング手順につながることを示す。
  論文  参考訳（メタデータ） (2021-06-23T17:59:16Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)

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

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