技術要約：EntroPath – マニフォールド学習のための最大エントロピー・パス・アンサンブル埋め込み

1. 問題提起

単一細胞トランスクリプトミクスや分子動力学のトラジェトリ（軌跡）といった現代の高次元データセットは、しば_低次元のリーマン多様体の近傍に集中していることが多い。マニフォールド学習の主要な目標は、これらの多様体の内在的な幾何学構造、特にその測地線距離を低次元表現として復元することである。

既存のアプローチには、以下のような重大な限界が存在する：

• 最短経路法（Isomapなど）： 近傍グラフ上の単一の最短経路を通じて測地線を推定する。これらは脆弱であり、測地学的に離れた領域間にたった一つの「ショートカット」となるエッジが存在するだけで、グローバルな距離が損なわれる可能性がある。さらに、非凸または分岐を持つ多様体においては、理論的な復元保証が成立しないことが多い。
• 局所近傍法（t-SNE, UMAPなど）： 確率的な目的関数を通じて局所的な関係性の保存に焦点を当てる。これらは可視化には効果的だが、グローバルな測地構造を明示的に符号化するものではない。
• 標準的な拡散法（Diffusion Maps, PHATEなど）： パスのアンサンブル（集合）を介して情報を集約し、グラフ誤差に対する堅牢性を提供する。しかし、これらは通常、局所的なノード次数によって正規化された**標準ランダムウォーク（SRW）**に依存している。これにより、拡散が密にサンプリングされた領域へとドリフトし、疎な分岐やボトルネックを圧縮してしまい、トラジェトリ・データにおける高密度な終端状態へと表現をバイアスさせる原因となる。

2. 手法：EntroPath

EntroPathは、最大エントロピーランダムウォーク（MERW）と、パス・アンサンブルから導出される自由エネルギー非類似度に基づいて非類似度を構築することで、これらの問題に対処する。

2.1 最大エントロピーランダムウォーク (MERW)

SRWとは異なり、MERWは局所的なノード次数によって遷移確率を正規化するのではなく（$T_{ij} = A_{ij}/d_i$）、パスのエントロピーをグローバルに最大化する。遷移行列は以下のように定義される：
$$T_{ij} = \frac{A_{ij}}{\lambda_{\max}} \frac{\psi_j}{\psi_i}$$
ここで、$A$はアフィニティ行列、$\lambda_{\max}$は最大固有値、$\psi$は対応するペロン＝フロベニウス固有ベクトルである。

• グローバルな再重み付け： MERWは$\psi$を通じてグローバルなグラフ構造を取り入れる。これにより、パスの確率をアンサンブル全体に均一に分布させ、低次数のボトルネックに確率質量が集中することを防ぐ。
• シュレディンガー演算子の構造： MERWラプラシアン（$I-T$）は、離散シュレディンガー演算子 $H = \lambda_{\max}I - A = -\Delta + V$ に類似している。ここで、$V$は次数の不均一性に起因するポテンシャル（$V_i = \lambda_{\max} - d_i$）である。この構造は、本手法の理論的保証の中心となっている。

2.2 自由エネルギー非類似度

EntroPathは、ノード $i$ と $j$ の間の非類似度を、単一の最短経路としてではなく、$k$ ステップのパス全体の重みの総和（分配関数）の負の対数として定義する。

• パスのコスト： エッジのコストは負の対数アフィニティ、 $E(u,v) = -\log A_{uv}$ として定義される。
• Log-Sum-Exp定式化： 非類似度は以下のようになる：
  $$D_{ij} = -\log \left( \tilde{A}^k \right)_{ij}$$
  ここで $\tilde{A} = A/\lambda_{\max}$ である。これは、最短経路距離の**ソフト最小化（soft-min）**緩和を表しており、全 $k$ ステップのアンサンブルを集約するものである。
• エントロピー項： この非類似度は、エントロピー項（$-\sum p(\gamma) \log p(\gamma)$）を含んでおり、多くの比較可能なパスによって接続されているペアを評価する。これは最短経路メトリックとは異なる点である。
• 対称化： 一般的なアフィニティに対して、非類似度は前方および後方への遷移確率の幾何平均を用いて対称化される：$D_{ij} = -\log \sqrt{T^k_{ij} T^k_{ji}}$。対称なケース（ガウス型アフィニティにおける標準的なケース）では、これは $-\log (\tilde{A}^k)_{ij}$ に簡略化される。

2.3 幾何学的レジームとスケーリング

拡散深度 $k$ は、以下の2つのレジームを補間する：

1. 測地線レジーム（小さい $k$）： 非類似度は、Varadhanの短時間熱核公式を通じて、グラフの測地線（最短経路）を近似する。
2. 混合レジム（大きい $k$）： 非類似度は、ペロン・ベクトルのみに依存する定常分布に収束し、微細な幾何学的詳細を失う。
   本手法は、von Neumannエントロピーの「膝（knee）」を用いて $k$ を自動的に選択し、拡散時間が、点同士を接続するには十分であるが、過剰に混合してしまうほど長くならないように制御する。

2.4 スケーラビリティ

大規模なデータセットに対して、EntroPathは以下を採用する：

• ランドマーク投影： 新しい点が、グローバルな演算子の再計算を回避しながら、ランドマークのサブセットの埋め込みへとカーネル補間を通じて投影される、Nyström型の拡張。
• 適応型カーネル： 非一様なサンプリング密度を効果的に扱うために、局所的な $k$-NN 距離に基づく適応的なバンド幅を使用する。

3. 主な貢献

1. アルゴリズムの革新： MERWと、パス・アンサンブルから導出される自由エネルギー非類似度に基づいた、マニフォールド学習手法であるEntroPathの導入。
2. 理論的定式化： 対称化された自由エネルギー非類似度が、短時間極限において、基礎となる多様体上の二乗測地線距離に収束するという証明（定理 5.3）。これは、MERWラプラシアンの離散シュレディンガー演算子構造とVaradhanの公式に基づいている。
3. カーネルとの接続： 対称化されたMERWカーネルが正確な**グラム因子分解（Gram factorization）**を持つことを実証し（命題 4.1）、多くのプロファイルベースの拡散法とは異なり、EntroPathをカーネル法や拡散マップに直接結びつけた。
4. スケーラブルな拡張： アウトオブサンプル埋め込みのためのランドマークベースの手法、および拡散ポテンシャルを用いた擬似時間（pseudotime）推定の開発。
5. 評価プロトコル： 距離レベル（カーネルの質）と埋め込みレベル（レイアウトの質）の性能を分離した2段階の評価プロトコル。これにより、グラウンドトゥルースで使用された特定の $k$-NNグラフに有利に働く、標準的な測地線評価のバイアスを浮き彫りにした。

4. 実験結果

EntroPathは、合成多様体（Swiss roll, 疎なツリー）および6つの生物学的単一細胞データセット（例：Paul15, Nestorowa, Root Atlas）を用いて評価された。

• 合成多様体：

  • 非一様にサンプリングされた多様体や疎な分岐ツリーにおいて、EntroPathは、拡散ベースのベースライン（PHATE, HeatGeo, DTNE）や最短経路法（Isomap）よりも、測地幾何学の復元において一貫して優れた性能を示した。
  • 距離レベルの評価において、グラウンドトゥルースの測地線との間で最高のSpearmanおよびPearson相関を達成した。
  • 埋め込みレベルの評価において、EntroPathは局所的手法（UMAP, t-SNE）よりもグローバルな構造をよく保持し、他の拡散法と比較して、特に疎な領域において、SRWベースの手法がボトルネックを「漏れる（leak）」現象が見られる中で、優れた信頼性と連続性を示した。

• 単一細胞データ：

  • EntroPathは、DEMaP（多様体保存）や信頼性（trustworthiness）といった指標において、PHATE, HeatGeo, DTNEと同等またはそれ以上の性能を実現した。
  • 非一様なサンプリングや、明確に分離された分岐トラジェトリを持つデータセットにおいて、特に高い堅牢性を示し、細胞の状態を密なクラスターへと平滑化することなく、明確な分離を維持した。
  • 大規模なArabidopsis根アトラス（$1.1 \times 10^5$ 細胞）において、EntroPathは、ランドマークおよび適応型カーネル戦略を活用することで、ハードな $k$-NN が必要とする密なグラフ累乗の計算コストを回避しつつ、DTNEと同等の幾何学的忠実度を約15秒で達成した。

5. 意義と主張

本論文は、EntroPathが、局所的な次数の正規化（SRWにおける拡散のバイアスを生む）と、グローバルな測地線復元（最短経路法において脆弱である）の間の緊張関係に対する、原理的な解決策を提供すると主張している。

• サンプリング密度への堅牢性： MERWを利用することで、EntroPathは低次数のボトルネックを高エネルギー障壁として扱い、これらを容易な通過経路としてではなく扱います。これにより、疎にサンプリングされた分岐の分離を維持し、SRWベースの埋め込みで頻繁に見られるグローバル幾何学の「崩壊」を防ぎます。
• 理論的保証： 二乗測地線距離への収束は、厳密な幾何学的基盤を提供し、ヒューリスティックな拡散距離とは一線を画しています。
• 実用的な有用性： 本手法は、自動的な深度選択を用いることで、多様なデータレジーム（合成ベンチマークから複雑な生物学的トラジェトリまで）において競争力のある性能を発揮する、スケーラブルでパラメータ設定の少ないアプローチを提供します。

著者らは、エントロピーに基づく深度選択が非常に短い分岐においてノイズになりやすいという制限事項を述べており、連続時間定式化や、方向性を持つアフィニティ（例：RNAベロシティ）の取り扱いに関する今後の課題を示唆している。