論文の概要: Towards Dynamic Graph Neural Networks with Provably High-Order Expressive Power

• arxiv url: http://arxiv.org/abs/2410.01367v1
• Date: Wed, 2 Oct 2024 09:28:59 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-04 21:29:22.031627
• Title: Towards Dynamic Graph Neural Networks with Provably High-Order Expressive Power
• Title（参考訳）: 高次表現力を有する動的グラフニューラルネットワークの実現に向けて
• Authors: Zhe Wang, Tianjian Zhao, Zhen Zhang, Jiawei Chen, Sheng Zhou, Yan Feng, Chun Chen, Can Wang,
• Abstract要約: 動的グラフニューラルネットワーク(DyGNN)は、進化するグラフに関する学習表現に対して、研究の注目を集めている。 その効果にもかかわらず、既存のDyGNNの表現力の制限は、動的グラフの重要な進化パターンを捉えるのを妨げる。 我々はDyGNNの表現力を高めるために高次表現力を持つ動的グラフニューラルネットワーク(HopeDGN)を提案する。
• 参考スコア（独自算出の注目度）: 24.271816124466188
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Dynamic Graph Neural Networks (DyGNNs) have garnered increasing research attention for learning representations on evolving graphs. Despite their effectiveness, the limited expressive power of existing DyGNNs hinders them from capturing important evolving patterns of dynamic graphs. Although some works attempt to enhance expressive capability with heuristic features, there remains a lack of DyGNN frameworks with provable and quantifiable high-order expressive power. To address this research gap, we firstly propose the k-dimensional Dynamic WL tests (k-DWL) as the referencing algorithms to quantify the expressive power of DyGNNs. We demonstrate that the expressive power of existing DyGNNs is upper bounded by the 1-DWL test. To enhance the expressive power, we propose Dynamic Graph Neural Network with High-order expressive power (HopeDGN), which updates the representation of central node pair by aggregating the interaction history with neighboring node pairs. Our theoretical results demonstrate that HopeDGN can achieve expressive power equivalent to the 2-DWL test. We then present a Transformer-based implementation for the local variant of HopeDGN. Experimental results show that HopeDGN achieved performance improvements of up to 3.12%, demonstrating the effectiveness of HopeDGN.
• Abstract（参考訳）: 動的グラフニューラルネットワーク(DyGNN)は、進化するグラフに関する学習表現に対して、研究の注目を集めている。 その効果にもかかわらず、既存のDyGNNの表現力の制限は、動的グラフの重要な進化パターンをキャプチャすることを妨げる。 ヒューリスティックな特徴を持つ表現能力を向上しようとする研究もあるが、証明可能で定量的な高次表現力を持つDyGNNフレームワークはいまだに不足している。 そこで我々はまず,DyGNNの表現力の定量化のための参照アルゴリズムとして,k次元動的WLテスト(k-DWL)を提案する。 既存のDyGNNの表現力は1-DWLテストにより上界となることを示した。 表現力を高めるために,周辺ノードペアとの相互作用履歴を集約して中央ノードペアの表現を更新する高次表現力を有する動的グラフニューラルネットワーク(HopeDGN)を提案する。 理論的な結果から,ホープDGNは2-DWL検定と同等の表現力が得られることが示された。 次に,局所変種であるHopeDGN に対する Transformer ベースの実装を提案する。 実験の結果、ホープDGNは最大3.12%の性能向上を達成し、ホープDGNの有効性を示した。

関連論文リスト

• Improving Graph Machine Learning Performance Through Feature Augmentation Based on Network Control Theory [3.2505793054002963]
  グラフニューラルネットワーク(GNN)は、様々なネットワークベースの学習タスクにおいて、例外的な有用性を示している。 多くの現実世界のシステムはノードレベルの情報を欠いている可能性があり、GNNにとって課題となっている。 我々は,NCTに基づく拡張機能拡張(NCT-EFA)という新たなアプローチを導入し,GNNの性能向上のための機能拡張パイプラインに,他の集中度指標とともに平均制御性を同化させる。
  論文  参考訳（メタデータ） (2024-05-03T19:11:54Z)
• GNN-VPA: A Variance-Preserving Aggregation Strategy for Graph Neural Networks [11.110435047801506]
  本稿では, 分散保存アグリゲーション関数 (VPA) を提案する。 その結果, 正常化フリー, 自己正規化GNNへの道を開くことができた。
  論文  参考訳（メタデータ） (2024-03-07T18:52:27Z)
• The Expressive Power of Graph Neural Networks: A Survey [9.08607528905173]
  定義の異なる表現力向上モデルに関する第1回調査を行う。 モデルは、グラフ機能拡張、グラフトポロジ拡張、GNNアーキテクチャ拡張という3つのカテゴリに基づいてレビューされる。
  論文  参考訳（メタデータ） (2023-08-16T09:12:21Z)
• Generalization Limits of Graph Neural Networks in Identity Effects Learning [12.302336258860116]
  グラフニューラルネットワーク(GNN)は、さまざまなグラフドメインでデータ駆動学習を行う強力なツールとして登場した。 我々は、いわゆるアイデンティティ効果の学習において、GNNの新たな一般化特性と基本的限界を確立する。 我々の研究は、単純な認知タスクを行う際に、GNNの能力を理解する必要性によって動機付けられている。
  論文  参考訳（メタデータ） (2023-06-30T20:56:38Z)
• Graph Neural Networks Provably Benefit from Structural Information: A Feature Learning Perspective [53.999128831324576]
  グラフニューラルネットワーク(GNN)は、グラフ表現学習の先駆けとなった。 本研究では,特徴学習理論の文脈におけるグラフ畳み込みの役割について検討する。
  論文  参考訳（メタデータ） (2023-06-24T10:21:11Z)
• An Empirical Study of Retrieval-enhanced Graph Neural Networks [48.99347386689936]
  グラフニューラルネットワーク(GNN)は、グラフ表現学習に有効なツールである。 本稿では,グラフニューラルネットワークモデルの選択に非依存な GraphRETRIEVAL という検索強化方式を提案する。 我々は13のデータセットに対して包括的な実験を行い、GRAPHRETRIEVALが既存のGNNよりも大幅に改善されていることを観察した。
  論文  参考訳（メタデータ） (2022-06-01T09:59:09Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• Theoretically Improving Graph Neural Networks via Anonymous Walk Graph Kernels [25.736529232578178]
  グラフニューラルネットワーク(GNN)は、グラフマイニングで大きな成功を収めました。 一般的なGNNとしてMPGNNは、多くのグラフのサブ構造を識別、検出、カウントできないことが理論的に示されている。 理論的にはグラフ構造を区別する能力の強いGNNモデルであるGSKNを提案する。
  論文  参考訳（メタデータ） (2021-04-07T08:50:34Z)
• A Unified View on Graph Neural Networks as Graph Signal Denoising [49.980783124401555]
  グラフニューラルネットワーク(GNN)は,グラフ構造化データの学習表現において顕著に普及している。 本研究では,代表的GNNモデル群における集約過程を,グラフ記述問題の解法とみなすことができることを数学的に確立する。 UGNNから派生した新しいGNNモデルADA-UGNNをインスタンス化し、ノード間の適応的滑らかさでグラフを処理する。
  論文  参考訳（メタデータ） (2020-10-05T04:57:18Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Binarized Graph Neural Network [65.20589262811677]
  我々は二項化グラフニューラルネットワークを開発し、二項化ネットワークパラメータを用いてノードのバイナリ表現を学習する。 提案手法は既存のGNNベースの埋め込み手法にシームレスに統合できる。 実験により、提案された二項化グラフニューラルネットワーク、すなわちBGNは、時間と空間の両方の観点から、桁違いに効率的であることが示されている。
  論文  参考訳（メタデータ） (2020-04-19T09:43:14Z)

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

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