技術的サマリー：トークン化に埋没する：トランスフォーマーにおけるグラフトークン化の根本的なトレードオフ

問題定義

トランスフォーマーはグラフ学習のための強力なアーキテクチャとして登場したが、グラフ構造化データへの適用には予備的なステップ、すなわちトークン化が必要である。シーケンスやグリッドとは異なり、グラフには標準的な連続入力形式が存在しない。したがって、どの構造的な情報が入力層でモデルに露呈するかを決定するために、グラフからトークンへのマッピングを選択しなければならない。

多様なトークン化戦略（例えば、スペクトル法、ランダムウォーク、隣接行列など）が存在するが、これらはしばしば経験的な設計選択や前処理の詳細として扱われる。本論文は、トークン化の選択がトランスフォーマーの表現力の根本的な構成要素であると主張する。中心となる問題は、異なるトークン化が相互に交換可能なのか、あるいはグラフタスクを解決するために必要な深さや構造的な情報の復元能力に関して、明確な計算レジームを誘発するものなのかどうかである。

手法

著者らは、グラフトークン化を計算モデルの不可欠な部分として形式化し、有限の深さ（$L$）、幅（$m$）、精度（$p$）を持つトランスフォーマーの表現力を、3 つの主要なトークン化ファミリーの下で分析する。

1. 隣接トークン化 (Adjacency Tokenization): 各ノードの隣接行を通じて、そのノードの局所的な接続性を符号化する。これは損失なしであるが、局所的な構造のみを露呈させる。
2. スペクトル（ラプラシアン）トークン化 (Spectral (Laplacian) Tokenization): グラフラプラシアン（$L = D - A$）の固有値分解からトークンを導出する。これは大域的なトポロジカルな性質を捉えるが、置換共変的である。
3. ランダムウォークトークン化 (Random-Walk Tokenization): 長さ $1$から$t(n)$ のランダムウォークの帰還確率を符号化する。これは拡散パターンを捉えるが、本質的に損失を伴う。

手法は計算量理論的分析と制御された実験を組み合わせる。

• 理論的分析: 著者らは、グラフタスクを計算量クラス（例：$TC^0$、$NC^1$、$L$）にマッピングすることで、下限と不可能性の結果を確立する。有限の深さの制約とトークン表現の数学的性質（例：条件数、情報損失）を考慮しつつ、特定のタスク（例：$k$-閉路検出、連結性、三角形の数え上げ、平面性）が異なるトークン化の下でどのように振る舞うかを分析する。
• 実証的検証: 合成タスク（深さの分離を検証）と実世界のベンチマーク（GraphBench、Open Graph Benchmark、ZINC）を用いて実験を行う。本研究は、各トークン化の完全版と切り詰め版、ならびに組み合わせたトークン化を用いたトランスフォーマーを評価し、DeepSet や GIN のベースラインと比較する。

主要な貢献

1. 計算制約としてのトークン化の形式化

本論文は、入力表現が有限の深さにおけるトランスフォーマーの表現力をどのように制約するかを形式化する。トークン化は単なる特徴量エンジニアリングのステップではなく、モデルがアクセス可能な構造的依存関係を決定する要因であることを示す。

2. トークン化間の深さの分離

著者らは、同じグラフ計算がトークン化に応じて著しく異なる深さを必要とする可能性を証明する。

• ランダムウォーク対隣接: $k$-閉路の検出は、統計量が明示的であるためランダムウォークトークン化では $O(1)$ の深さで解決可能であるが、隣接トークン化では $\Omega(\log k)$ の深さを必要とする。これは、置換群 $S_5$ 上の単語問題（$NC^1$-完全問題）からグラフトポロジーへの帰着によって証明されており、定数深さのトランスフォーマー（$TC^0$）が隣接トークンが要求する逐次的な経路走査をシミュレートできないことを示している。
• 隣接対スペクトル: グローバルなグラフ連結性の解決には、隣接トークン化では $\Omega(\log n)$ の深さが必要であるのに対し、スペクトルトークン化では $O(1)$ の深さで解決される。

3. 本質的な限界と損失性

• ランダムウォークは証明可能な損失性を持つ: 歩行長に関わらず、ランダムウォークトークン化はグラフの平面性を決定できない。著者らは Godsil-McKay (GM) 切り替えを用いて、同一のランダムウォーク分布を持つ平面グラフと非平面グラフを構成し、トランスフォーマーの深さや幅がトポロジカルな区別を復元できないことを証明する。
• スペクトルの切り詰めは脆弱である: ラプラシアンスペクトルを切り詰めること（単一の固有値であっても）は、三角形の数え上げを不可能にする可能性がある。著者らは、対称なノード間のエッジを追加すると固有値が 1 つのみ変化するが、この固有値が切り詰められた場合、トランスフォーマーはグラフを区別できないことを示す。
• 隣接の切り詰め: 隣接トークンの次元を（ランダム射影を通じて）切り詰めることは、通信量理論の下限（集合の非共通性）によって証明されるように、三角形の数え上げなどのタスクを解決する能力を破壊する。

4. 局所タスクに対するスペクトルトークン化の不良条件化

スペクトルトークン化は大域的トポロジを捉えるが、エッジ予測のような局所タスクに対しては数学的に不良条件化されている。本論文は、大域的スペクトルから局所的エッジを復号するために必要なパラメータノルムの下限を導出し、それが最大次数（$d_{max}$）に比例して増加することを示す。これにより、モデルが Softmax の飽和（勾配消失）に苦しむか、あるいは爆発的な重みを必要として最適化が困難になるというトレードオフが生じる。

5. 限られた深さにおける変換の不可能性

本論文は、トークン化ファミリー間の変換が一般的に限られた深さでは不可能であることを確立する。

• トランスフォーマーは、隣接トークンをランダムウォーク統計量に効率的に変換できない（$\Omega(\log k)$ の深さが必要）。
• トランスフォーマーは、情報損失のため、ランダムウォークトークンから完全な隣接またはラプラシアン表現を復元できない。
• 大域的（スペクトル）と局所的（隣接）な視点間の変換は、深刻な計算ボトルネックまたは最適化の不安定性を招く。

結果

理論的知見:

• 深さの分離: 実証的検証により、スペクトルトークン化はすべてのグラフサイズにおいて $L=1$ で連結性タスクを解決するのに対し、隣接トークン化はより大きなグラフ（$n \ge 128$）では偶然の性能に崩壊することが確認された。
• 復元限界: 隣接トークンからランダムウォークの帰還確率を予測するようにトランスフォーマーを訓練した場合、誤差は歩行長 $k$ とともに増加し、$\Omega(\log k)$ の深さ要件と一致する。
• 平面性: 深さを増やしても、ランダムウォークトークンを使用するモデルは平面グラフと非平面グラフを区別できず、理論的な不可能性の結果を確認する。

実証的知見:

• タスク依存性: 単一のトークン化が支配的ではない。
  • 局所タスク: 明示的な局所制約に支配されるタスク（最大クリーク、トポロジカルソートなど）では、隣接トークン化が最良の性能を発揮する。
  • 大域タスク: 大域的幾何学に依存するタスク（Tox21 分子特性予測など）では、スペクトル（ラプラシアン）トークン化が最良の性能を発揮する。
  • 組み合わせアプローチ: 相補的なトークン化（隣接 + スペクトル + ランダムウォーク）を組み合わせることは、モデルが異なる構造的シグナルを活用できるようにし、しばしば最良の性能をもたらす。
• 切り詰め効果: 切り詰められたトークン化は、特に正確な構造的復元を必要とするタスク（三角形の数え上げなど）において、一般的に性能を低下させ、切り詰め理論の「脆弱性」を実証する。

意義と主張

本論文は、グラフトークン化は前処理の詳細ではなく、根本的なトレードオフであると主張する。トークン化の選択は、トランスフォーマーが受け取るグラフの「視点」を決定し、それによって有限の深さでモデルが表現できる構造的依存関係のクラスを制約する。

著者らが強調する主要な教訓は以下の通りである。

1. 非交換性: 隣接、スペクトル、ランダムウォークのトークン化は相互に交換可能ではない。これらは明確な深さレジームと表現力の限界を誘発する。
2. 本質的な限界: 特定のトークン化には証明可能な盲点がある（例：ランダムウォークは平面性を認識できない。スペクトルは局所エッジに対して不良条件化されている）。
3. 変換の障壁: 初期トークン化が不利な場合、トランスフォーマーは単にこれらの表現間を効率的に「学習して」変換することはできない。これらのギャップを埋めるために必要な深さは、非現実的である可能性がある。
4. 実用的含意: 最適なトークン化は、ダウンストリームタスクの構造的性質に依存する。相補的な視点を組み合わせることは、単一の表現の限界を克服するための堅牢な戦略である。

著者らは、分析がノードレベルのトークン化に焦点を当てているものの、その知見はより広範な原理を示唆すると結論づける。すなわち、入力表現はグラフ学習における複雑性の重要な軸であり、今後の研究は最適化の課題やエッジレベルのトークン化を探求すべきである。