論文の概要: Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers

• arxiv url: http://arxiv.org/abs/2501.10688v2
• Date: Sun, 02 Feb 2025 23:41:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-04 16:08:04.129109
• Title: Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers
• Title（参考訳）: ループ変換器を用いたハイパーグラフのニューラルネットワーク推論
• Authors: Xiaoyu Li, Yingyu Liang, Jiangxuan Long, Zhenmei Shi, Zhao Song, Zhen Zhuang,
• Abstract要約: ループ変換器は、従来のグラフアルゴリズムでは例外的なアルゴリズム推論能力を示している。 ハイパーグラフアルゴリズムをシミュレートするために,Loop Transformerアーキテクチャのニューラルネットワーク推論機能を拡張する。
• 参考スコア（独自算出の注目度）: 22.641550077885686
• License:
• Abstract: Looped Transformers have shown exceptional neural algorithmic reasoning capability in simulating traditional graph algorithms, but their application to more complex structures like hypergraphs remains underexplored. Hypergraphs generalize graphs by modeling higher-order relationships among multiple entities, enabling richer representations but introducing significant computational challenges. In this work, we extend the Loop Transformer architecture's neural algorithmic reasoning capability to simulate hypergraph algorithms, addressing the gap between neural networks and combinatorial optimization over hypergraphs. Specifically, we propose a novel degradation mechanism for reducing hypergraphs to graph representations, enabling the simulation of graph-based algorithms, such as Dijkstra's shortest path. Furthermore, we introduce a hyperedge-aware encoding scheme to simulate hypergraph-specific algorithms, exemplified by Helly's algorithm. We establish theoretical guarantees for these simulations, demonstrating the feasibility of processing high-dimensional and combinatorial data using Loop Transformers. This work highlights the potential of Transformers as general-purpose algorithmic solvers for structured data.
• Abstract（参考訳）: ループ変換器は、従来のグラフアルゴリズムをシミュレートする際、例外的なアルゴリズム推論能力を示してきたが、ハイパーグラフのようなより複雑な構造への応用はいまだ探索されていない。 ハイパーグラフは、複数のエンティティ間の高次関係をモデル化してグラフを一般化し、よりリッチな表現を可能にするが、重要な計算課題を導入する。 本研究では、ループトランスフォーマーアーキテクチャのニューラルネットワーク推論能力を拡張し、ハイパーグラフアルゴリズムをシミュレートし、ニューラルネットワークとハイパーグラフに対する組合せ最適化のギャップに対処する。 具体的には、グラフ表現にハイパーグラフを還元する新しい劣化機構を提案し、Dijkstraの最短経路のようなグラフベースのアルゴリズムのシミュレーションを可能にする。 さらに,Hellyのアルゴリズムを例として,ハイパーグラフ固有のアルゴリズムをシミュレートするハイパーエッジ対応符号化方式を提案する。 これらのシミュレーションの理論的保証を確立し,ループトランスフォーマを用いた高次元および組合せデータ処理の実現可能性を示す。 この研究は、構造化データの汎用的アルゴリズム解法としてのトランスフォーマーの可能性を強調している。

関連論文リスト

• Tuning Algorithmic and Architectural Hyperparameters in Graph-Based Semi-Supervised Learning with Provable Guarantees [9.141919626212903]
  グラフベースの半教師付き学習は、基礎となるグラフ構造をモデリングし活用するための機械学習の強力なパラダイムである。 グラフ畳み込みニューラルネットワーク(GCN)とグラフアテンションネットワーク(GAT)を各層に補間する可変アーキテクチャを提案する。
  論文  参考訳（メタデータ） (2025-02-18T15:16:23Z)
• Modularity Based Community Detection in Hypergraphs [1.4999444543328293]
  ハイパーグラフモジュラリティ関数h-Louvainを用いたスケーラブルなコミュニティ検出アルゴリズムを提案する。 これは、ハイパーグラフの文脈における古典的なルーヴァンアルゴリズムの適応である。
  論文  参考訳（メタデータ） (2024-06-25T13:49:56Z)
• Simulation of Graph Algorithms with Looped Transformers [6.0465914748433915]
  理論的観点から, グラフ上のアルゴリズムをシミュレートするトランスフォーマーネットワークの能力について検討する。 このアーキテクチャは、Dijkstraの最も短い経路のような個々のアルゴリズムをシミュレートできることを示す。 付加的なアテンションヘッドを利用する場合のチューリング完全度を一定幅で示す。
  論文  参考訳（メタデータ） (2024-02-02T02:48:03Z)
• From Hypergraph Energy Functions to Hypergraph Neural Networks [94.88564151540459]
  パラメータ化されたハイパーグラフ正規化エネルギー関数の表現型族を示す。 次に、これらのエネルギーの最小化がノード埋め込みとして効果的に機能することを実証する。 提案した双レベルハイパーグラフ最適化と既存のGNNアーキテクチャを共通的に用いている。
  論文  参考訳（メタデータ） (2023-06-16T04:40:59Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Convolutional Learning on Multigraphs [153.20329791008095]
  我々は、多グラフ上の畳み込み情報処理を開発し、畳み込み多グラフニューラルネットワーク(MGNN)を導入する。 情報拡散の複雑なダイナミクスを多グラフのエッジのクラス間で捉えるために、畳み込み信号処理モデルを定式化する。 我々は,計算複雑性を低減するため,サンプリング手順を含むマルチグラフ学習アーキテクチャを開発した。 導入されたアーキテクチャは、最適な無線リソース割り当てとヘイトスピーチローカライゼーションタスクに適用され、従来のグラフニューラルネットワークよりも優れたパフォーマンスを提供する。
  論文  参考訳（メタデータ） (2022-09-23T00:33:04Z)
• Graph Kernel Neural Networks [53.91024360329517]
  本稿では、グラフ上の内部積を計算するカーネル関数であるグラフカーネルを用いて、標準畳み込み演算子をグラフ領域に拡張することを提案する。 これにより、入力グラフの埋め込みを計算する必要のない完全に構造的なモデルを定義することができる。 私たちのアーキテクチャでは,任意の種類のグラフカーネルをプラグインすることが可能です。
  論文  参考訳（メタデータ） (2021-12-14T14:48:08Z)
• HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering [9.438207505148947]
  本稿では,ハイパーグラフのスペクトル(構造)特性を保存するために,効率的なスペクトルハイパーグラフ粗大化手法を提案する。 提案手法は,ハイパーグラフクラスタリングのマルチウェイコンダクタンスを大幅に向上させることができることを示す。
  論文  参考訳（メタデータ） (2021-08-17T22:20:23Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  結合ネットワークトポロジ推論は、異種グラフ信号から複数のグラフラプラシア行列を学習する標準的な問題を表す。 新規な構造化融合正規化に基づく一般グラフ推定器を提案する。 提案するグラフ推定器は高い計算効率と厳密な理論保証の両方を享受できることを示す。
  論文  参考訳（メタデータ） (2021-03-05T04:42:32Z)
• Unrolling of Deep Graph Total Variation for Image Denoising [106.93258903150702]
  本稿では,従来のグラフ信号フィルタリングと深い特徴学習を併用して,競合するハイブリッド設計を提案する。 解釈可能な低パスグラフフィルタを用い、最先端のDL復調方式DnCNNよりも80%少ないネットワークパラメータを用いる。
  論文  参考訳（メタデータ） (2020-10-21T20:04:22Z)

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

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