論文の概要: Lost in Tokenization: Fundamental Trade-offs in Graph Tokenization for Transformers

• arxiv url: http://arxiv.org/abs/2605.22471v1
• Date: Thu, 21 May 2026 13:32:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-22 16:35:42.275275
• Title: Lost in Tokenization: Fundamental Trade-offs in Graph Tokenization for Transformers
• Title（参考訳）: トークン化の損失:変換器のグラフトークン化における基本的なトレードオフ
• Authors: Maya Bechler-Speicher, Gilad Yehudai, Gil Harari, Clayton Sanford, Amir Globerson, Joan Bruna,
• Abstract要約: グラフ・ツー・トケン写像の選択は変換器の表現性の基本成分であることを示す。 既存の多くのグラフトークン化のためのビルディングブロックとして機能する3つのトークン化(スペクトル、ランダムウォーク、隣接トークン化)について検討する。
• 参考スコア（独自算出の注目度）: 50.98108117044413
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Transformers have become a central architecture for graph learning, but their application to graphs requires first choosing a tokenization: a graph-to-token map that determines which structural information is exposed at the input. In this work, we show that this choice is a fundamental component of transformer expressivity. We examine three tokenizations that serve as building blocks for many existing graph tokenizations: spectral, random-walk, and adjacency tokenizations. We prove that different tokenizations induce distinct depth regimes: the same graph computation may be realizable by a shallow transformer under one tokenization, while requiring substantially larger depth under another. For example, we prove that random-walk tokenization is lossy for any walk length, making it impossible in general to recover the graph from it, and that while spectral tokenization is lossless, it is ill-conditioned for local tasks. We further show that although both random-walk and spectral tokenizations are derived from adjacency information, it is impossible for a limited-depth transformer to convert between tokenization families in general. In particular, we establish lower bounds and impossibility results showing that unfavorable tokenizations may preclude the efficient recovery of more suitable structural representations. Finally, we complement our theory with controlled experiments on synthetic and real-world tasks, validating the predicted separations and showing that different tasks favor different structural views, and combining complementary tokenizations allows the transformer to leverage distinct signals from each representation.
• Abstract（参考訳）: トランスフォーマーは、グラフ学習の中心的なアーキテクチャとなっているが、そのグラフへの応用には、最初にトークン化を選択する必要がある。 本研究では,この選択が変圧器表現性の基本成分であることを示す。 既存の多くのグラフトークン化のためのビルディングブロックとして機能する3つのトークン化(スペクトル、ランダムウォーク、隣接トークン化)について検討する。 同じグラフ計算は、1つのトークン化の下で浅い変圧器によって実現可能であり、他方ではより大きな深さを必要とする。 例えば、ランダムウォークトークン化は任意のウォーク長に対して損失であり、一般的にグラフを復元することは不可能であり、スペクトルトークン化は損失のないが、局所的なタスクに対しては不条件であることを示す。 さらに、ランダムウォークとスペクトルトークン化の両方が隣接情報から導出されるが、限定深度変換器では一般にトークン化ファミリ間の変換は不可能であることを示す。 特に、不利なトークン化がより適切な構造表現の効率的な回復を妨げていることを示す。 最後に、我々の理論を合成的および実世界のタスクに関する制御された実験で補完し、予測された分離を検証し、異なるタスクが異なる構造的視点を優先することを示し、補完的なトークン化を組み合わせることで、変換器は各表現から異なる信号を利用することができる。

関連論文リスト

• Graph Tokenization for Bridging Graphs and Transformers [22.184950064615403]
  本稿では,グラフの逐次表現を生成するグラフトークン化フレームワークを提案する。 この研究は、グラフ構造化データとシーケンスモデルのエコシステムの間のギャップを埋める。
  論文  参考訳（メタデータ） (2026-03-11T08:57:10Z)
• Plain Transformers Can be Powerful Graph Learners [64.50059165186701]
  研究者たちは、Transformerをグラフ学習に移行しようとしたが、ほとんどの高度なGraph Transformerは、普通のTransformerから遠く離れている。 この研究は、普通のTransformerアーキテクチャが強力なグラフ学習者になれることを示した。
  論文  参考訳（メタデータ） (2025-04-17T02:06:50Z)
• What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding [67.59552859593985]
  自己アテンションと位置エンコーディングを組み込んだグラフトランスフォーマーは、さまざまなグラフ学習タスクのための強力なアーキテクチャとして登場した。 本稿では,半教師付き分類のための浅いグラフ変換器の理論的検討について紹介する。
  論文  参考訳（メタデータ） (2024-06-04T05:30:16Z)
• Toward a Theory of Tokenization in LLMs [26.516041872337887]
  本稿では, 簡単なデータ生成プロセスにおいて, 変圧器の挙動を研究することによって, 理論的観点からトークン化について検討する。 変換器によって学習された最も単純なユニグラムモデルでさえ、$ktextth$-order Markovソースから引き出されたシーケンスの確率を最適にモデル化できることを示す。
  論文  参考訳（メタデータ） (2024-04-12T09:01:14Z)
• How Transformers Learn Causal Structure with Gradient Descent [44.31729147722701]
  自己注意はトランスフォーマーが因果構造をエンコードすることを可能にする。 我々は、潜在因果構造を学習する必要があるコンテキスト内学習タスクを導入する。 我々は、文脈内学習タスクで訓練されたトランスフォーマーが、様々な因果構造を回復できることを示す。
  論文  参考訳（メタデータ） (2024-02-22T17:47:03Z)
• Transformers are efficient hierarchical chemical graph learners [7.074125287195362]
  SubFormerは、メッセージパッシング機構によって情報を集約するサブグラフで動作するグラフトランスフォーマーである。 従来のグラフニューラルネットワークでは,SubFormerのオーバースムース化が制限され,オーバースキャッシングを回避することが示されている。
  論文  参考訳（メタデータ） (2023-10-02T23:57:04Z)
• What Makes for Good Tokenizers in Vision Transformer? [62.44987486771936]
  変圧器は自己注意を用いて対関係を抽出することができる。 優れたトークンライザとなるものは、コンピュータビジョンではよく理解されていない。 Tokens (MoTo) を横断する変調は、正規化によるトークン間モデリング機能を備えている。 TokenPropの正規化対象は、標準トレーニング体制で採用されている。
  論文  参考訳（メタデータ） (2022-12-21T15:51:43Z)
• Partition and Code: learning how to compress graphs [50.29024357495154]
  まず、分割アルゴリズムがグラフを基本構造に分解し、これらを確率分布を学習する小さな辞書の要素にマッピングし、エントロピーエンコーダが表現をビットに変換する。 提案アルゴリズムは,非パラメトリックおよびパラメトリックグラフ圧縮器の異なるファミリーに対して,多種多様な実世界のネットワーク上で定量的に評価し,大幅な性能向上を実現している。
  論文  参考訳（メタデータ） (2021-07-05T11:41:16Z)

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

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