論文の概要: Cayley Graph Propagation

• arxiv url: http://arxiv.org/abs/2410.03424v1
• Date: Fri, 4 Oct 2024 13:32:34 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-02 22:29:14.873156
• Title: Cayley Graph Propagation
• Title（参考訳）: Cayley Graph Propagation
• Authors: JJ Wilson, Maya Bechler-Speicher, Petar Veličković,
• Abstract要約: トルーニケーションはケイリーグラフ構造の膨張特性に有害であることを示す。 代わりに、完全なケイリーグラフ構造上の情報を伝播する手法であるCGPを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In spite of the plethora of success stories with graph neural networks (GNNs) on modelling graph-structured data, they are notoriously vulnerable to over-squashing, whereby tasks necessitate the mixing of information between distance pairs of nodes. To address this problem, prior work suggests rewiring the graph structure to improve information flow. Alternatively, a significant body of research has dedicated itself to discovering and precomputing bottleneck-free graph structures to ameliorate over-squashing. One well regarded family of bottleneck-free graphs within the mathematical community are expander graphs, with prior work$\unicode{x2014}$Expander Graph Propagation (EGP)$\unicode{x2014}$proposing the use of a well-known expander graph family$\unicode{x2014}$the Cayley graphs of the $\mathrm{SL}(2,\mathbb{Z}_n)$ special linear group$\unicode{x2014}$as a computational template for GNNs. However, in EGP the computational graphs used are truncated to align with a given input graph. In this work, we show that truncation is detrimental to the coveted expansion properties. Instead, we propose CGP, a method to propagate information over a complete Cayley graph structure, thereby ensuring it is bottleneck-free to better alleviate over-squashing. Our empirical evidence across several real-world datasets not only shows that CGP recovers significant improvements as compared to EGP, but it is also akin to or outperforms computationally complex graph rewiring techniques.
• Abstract（参考訳）: グラフ構造化データのモデリングにおいて、グラフニューラルネットワーク(GNN)を使った成功談は多々あるが、それらは過度な監視に弱いことで知られており、タスクはノードの距離ペア間の情報の混合を必要とする。 この問題に対処するため、先行研究では、情報フローを改善するためにグラフ構造を書き換えることを提案している。 あるいは、重要な研究機関が、オーバー・スカッシングを改善するためにボトルネックのないグラフ構造の発見と事前計算に力を入れている。 数学界におけるボトルネックのないグラフのファミリの一つとして、拡張グラフがある。先行研究$\unicode{x2014}$Expander Graph Propagation (EGP)$\unicode{x2014}$proposing the use of a well-known expander graph family$\unicode{x2014}$the Cayley graphs of the $\mathrm{SL}(2,\mathbb{Z}_n)$ special linear group$\unicode{x2014}$as a computer template for GNNs。 しかし、EGPでは、使用する計算グラフは与えられた入力グラフと整合するように切り詰められる。 本研究は, トランケーションが対流膨張特性に有害であることを示す。 代わりに、完全なケイリーグラフ構造上の情報を伝播する手法であるCGPを提案する。 実世界の複数のデータセットにまたがる実証的な証拠は、CGPがEGPに比べて大幅な改善を回復するだけでなく、計算に複雑なグラフリウィリング技術に類似していることを示している。

関連論文リスト

• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Unlearnable Graph: Protecting Graphs from Unauthorized Exploitation [68.59161853439339]
  学習不可能なグラフの例を生成するための新しい手法を提案する。 Error-Minimizing Structure Poisoning (EMinS) モジュールを使ってグラフに妄想的だが知覚不可能なノイズを注入することにより、グラフを説明不能にすることができる。
  論文  参考訳（メタデータ） (2023-03-05T03:30:22Z)
• FoSR: First-order spectral rewiring for addressing oversquashing in GNNs [0.0]
  グラフニューラルネットワーク(GNN)は、グラフのエッジに沿ってメッセージを渡すことによって、グラフデータの構造を活用することができる。 本稿では,グラフにエッジを体系的に付加することで過疎化を防止する計算効率のよいアルゴリズムを提案する。 提案アルゴリズムは,いくつかのグラフ分類タスクにおいて,既存のグラフリウィリング手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-10-21T07:58:03Z)
• Expander Graph Propagation [0.0]
  本稿では,拡張グラフ上での情報伝達に基づくエレガントなアプローチを提案する。 EGPは、セットアップに最小限の労力を要しながら、上記の懸念に対処できることを示します。 我々の分析は、GNNの過剰な監視に対処する、スケーラブルな方法の新たなクラスへの道を開くものだと信じています。
  論文  参考訳（メタデータ） (2022-10-06T15:36:37Z)
• SPGP: Structure Prototype Guided Graph Pooling [1.3764085113103217]
  グラフレベルの表現を学習するための構造プロトタイプガイドプーリング(SPGP)を提案する。 SPGPはグラフ構造を学習可能なプロトタイプベクトルとして定式化し、ノードとプロトタイプベクトル間の親和性を計算する。 実験の結果,SPGPはグラフ分類ベンチマークデータセットにおいて,最先端のグラフプーリング手法よりも優れていた。
  論文  参考訳（メタデータ） (2022-09-16T09:33:09Z)
• Graph Neural Network Bandits [89.31889875864599]
  グラフ構造データ上で定義された報酬関数を用いた帯域最適化問題を考察する。 この設定の主な課題は、大きなドメインへのスケーリングと、多くのノードを持つグラフへのスケーリングである。 グラフニューラルネットワーク(GNN)を用いて報酬関数を推定できることを示す。
  論文  参考訳（メタデータ） (2022-07-13T18:12:36Z)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。 アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。 理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
  論文  参考訳（メタデータ） (2021-11-12T07:08:13Z)
• Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Prediction [123.20238648121445]
  我々は、新しい自己教師型学習フレームワーク、グラフ情報支援ノード機能exTraction (GIANT)を提案する。 GIANT は eXtreme Multi-label Classification (XMC) 形式を利用しており、これはグラフ情報に基づいた言語モデルの微調整に不可欠である。 我々は,Open Graph Benchmarkデータセット上での標準GNNパイプラインよりもGIANTの方が優れた性能を示す。
  論文  参考訳（メタデータ） (2021-10-29T19:55:12Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)

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

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