論文の概要: Transformers Provably Learn Directed Acyclic Graphs via Kernel-Guided Mutual Information

• arxiv url: http://arxiv.org/abs/2510.25542v1
• Date: Wed, 29 Oct 2025 14:07:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-30 15:50:45.692631
• Title: Transformers Provably Learn Directed Acyclic Graphs via Kernel-Guided Mutual Information
• Title（参考訳）: カーネルガイドによる相互情報による非循環グラフの学習
• Authors: Yuan Cheng, Yu Huang, Zhe Xiong, Yingbin Liang, Vincent Y. F. Tan,
• Abstract要約: 注意機構を活用するトランスフォーマーベースのモデルは、グラフ内の複雑な依存関係をキャプチャする上で、強い経験的成功を示している。 本稿では,カーネル誘導相互情報(KG-MI)を$f$-divergenceに基づく新しい情報理論指標を提案する。 我々は、K$親和性DAGによって生成された任意のシーケンスが、勾配上昇による単層マルチヘッドトランスを訓練し、大域的最適時間に収束することを証明した。
• 参考スコア（独自算出の注目度）: 91.66597637613263
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Uncovering hidden graph structures underlying real-world data is a critical challenge with broad applications across scientific domains. Recently, transformer-based models leveraging the attention mechanism have demonstrated strong empirical success in capturing complex dependencies within graphs. However, the theoretical understanding of their training dynamics has been limited to tree-like graphs, where each node depends on a single parent. Extending provable guarantees to more general directed acyclic graphs (DAGs) -- which involve multiple parents per node -- remains challenging, primarily due to the difficulty in designing training objectives that enable different attention heads to separately learn multiple different parent relationships. In this work, we address this problem by introducing a novel information-theoretic metric: the kernel-guided mutual information (KG-MI), based on the $f$-divergence. Our objective combines KG-MI with a multi-head attention framework, where each head is associated with a distinct marginal transition kernel to model diverse parent-child dependencies effectively. We prove that, given sequences generated by a $K$-parent DAG, training a single-layer, multi-head transformer via gradient ascent converges to the global optimum in polynomial time. Furthermore, we characterize the attention score patterns at convergence. In addition, when particularizing the $f$-divergence to the KL divergence, the learned attention scores accurately reflect the ground-truth adjacency matrix, thereby provably recovering the underlying graph structure. Experimental results validate our theoretical findings.
• Abstract（参考訳）: 実世界のデータに基づく隠れグラフ構造を明らかにすることは、科学分野にまたがる幅広い応用において重要な課題である。 近年、アテンション機構を利用したトランスフォーマーモデルにより、グラフ内の複雑な依存関係を捕捉する実験的な成功が証明されている。 しかし、それらの訓練力学の理論的理解は、各ノードが1つの親に依存する木のようなグラフに限られている。 証明可能な保証をより汎用的な非巡回グラフ(DAG)(ノード毎に複数の親を含む)に拡張することは、主に異なる注意を向け、複数の異なる親関係を個別に学習することを可能にする訓練目標を設計することの難しさから、依然として困難である。 本研究では,カーネル誘導相互情報(KG-MI)を$f$-divergenceに基づいて,新しい情報理論メトリクスを導入することでこの問題に対処する。 本研究の目的は,KG-MIとマルチヘッドアテンション・フレームワークを組み合わせることであり,各ヘッドは異なる限界遷移カーネルに関連付けられ,多様な親子依存関係を効果的にモデル化することである。 我々は、K$親和性DAGによって生成される任意のシーケンスが、勾配上昇による単層多頭部変圧器を多項式時間で大域的最適に収束させることを証明した。 さらに,注意点パターンを収束時に特徴付ける。 さらに、KL分散に対する$f$-divergenceを特定する場合、学習された注目スコアは、接地トラバス隣接行列を正確に反映し、基礎となるグラフ構造を確実に復元する。 実験結果から理論的知見が得られた。

関連論文リスト

• Self-Reinforced Graph Contrastive Learning [7.49025068464945]
  SRGCL(Self-Reinforced Graph Contrastive Learning)を提案する。 多様なグラフレベルの分類タスクの実験では、SRGCLは最先端のGCL法よりも一貫して優れている。
  論文  参考訳（メタデータ） (2025-05-19T18:45:54Z)
• Balanced Multi-Relational Graph Clustering [5.531383184058319]
  マルチリレーショナルグラフクラスタリングは、複雑なネットワークの基盤となるパターンを明らかにすることに顕著な成功を収めた。 我々の実証的研究は、現実のグラフにおいて不均衡が広範に存在することを発見し、これは原則的にアライメントの動機と矛盾する。 我々は、教師なしの主観的マイニングと二重信号誘導表現学習からなるバランス付きマルチリレーショナルグラフクラスタリング(BMGC)を提案する。
  論文  参考訳（メタデータ） (2024-07-23T22:11:13Z)
• Introducing Diminutive Causal Structure into Graph Representation Learning [19.132025125620274]
  本稿では,グラフニューラルネット(GNN)が専門的な最小の因果構造から洞察を得ることを可能にする新しい手法を提案する。 本手法は,これらの小型因果構造のモデル表現から因果知識を抽出する。
  論文  参考訳（メタデータ） (2024-06-13T00:18:20Z)
• What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding [67.59552859593985]
  自己アテンションと位置エンコーディングを組み込んだグラフトランスフォーマーは、さまざまなグラフ学習タスクのための強力なアーキテクチャとして登場した。 本稿では,半教師付き分類のための浅いグラフ変換器の理論的検討について紹介する。
  論文  参考訳（メタデータ） (2024-06-04T05:30:16Z)
• Beyond DAGs: A Latent Partial Causal Model for Multimodal Learning [80.44084021062105]
  本稿では,非方向エッジで連結された2つの潜在結合変数を特徴とする,多モーダルデータに対する新しい潜在部分因果モデルを提案する。 特定の統計的仮定の下では、多モーダル・コントラッシブ・ラーニングによって学習された表現が、自明な変換までの潜在結合変数に対応することを示す。 事前トレーニングされたCLIPモデルの実験は、非絡み合った表現を具現化し、数ショットの学習を可能にし、さまざまな現実世界のデータセットにわたるドメインの一般化を改善する。
  論文  参考訳（メタデータ） (2024-02-09T07:18:06Z)
• Directed Acyclic Graph Structure Learning from Dynamic Graphs [44.21230819336437]
  特徴(変数)の有向非巡回グラフ(DAG)の構造を推定することは、潜在データ生成プロセスを明らかにする上で重要な役割を果たす。 このようなユビキタスな動的グラフデータに基づくノード特徴生成機構の学習問題について検討する。
  論文  参考訳（メタデータ） (2022-11-30T14:22:01Z)
• Discovering the Representation Bottleneck of Graph Neural Networks from Multi-order Interactions [51.597480162777074]
  グラフニューラルネットワーク(GNN)は、ノード機能を伝搬し、インタラクションを構築するためにメッセージパッシングパラダイムに依存している。 最近の研究は、異なるグラフ学習タスクはノード間の異なる範囲の相互作用を必要とすることを指摘している。 科学領域における2つの共通グラフ構築法、すなわち、emphK-nearest neighbor(KNN)グラフとemphfully-connected(FC)グラフについて検討する。
  論文  参考訳（メタデータ） (2022-05-15T11:38:14Z)
• Graph Representation Learning via Graphical Mutual Information Maximization [86.32278001019854]
  本稿では,入力グラフとハイレベルな隠蔽表現との相関を測る新しい概念であるGMIを提案する。 我々は,グラフニューラルエンコーダの入力と出力の間でGMIを最大化することで訓練された教師なし学習モデルを開発する。
  論文  参考訳（メタデータ） (2020-02-04T08:33:49Z)

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

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