技術要約: RTD-Lite

問題提起

重み付きグラフの比較は、機械学習、ネットワーク科学、および計算生物学における基本的な課題である。トポロジカル・データ解析（TDA）は、マルチスケールなトポロジー的特徴を捉えるためのパーシステンス・バーコードのような堅牢なツールを提供しているが、既存の手法は、重み付きグラフの比較において計算効率の面で課題を抱えていることが多い。具体的には、比較クロスバーコードに基づくトポロジー的相違を定量化する「表現トポロジー・ダイバージェンス（RTD）」メトリックは、大規模なデータセットに対しては計算量が膨大になりすぎる。完全なパーシステント・ホモロジーの計算に伴う高い計算複雑性は、ニューラルネットワークの訓練や次元削減といった、スケーラビリティが極めて重要となる実世界の学習タスクにおいて、厳密なトポロジー比較の適用を制限している。

手法

著者らは、頂点集合の間に一対一の対応関係が存在する2つの重み付きグラフ $A$ および $B$ のトポロジー的特徴を効率的に比較するために設計された、スケーラブルなアルゴリズムである RTD-Lite を提案している。この手法は、完全なパーシステンス・バーコードを計算することなく、任意のスケールにおける連結性とクラスター構造（0次元ホモロジー）の不一致を捉えることに焦点を当てている。

コアメカニズム

本アルゴリズムは、入力グラフ $A$ および $B$ から構築される補助グラフ $C$ 上で動作する：

1. グラフ構築: $A$ および $B$ と同じ頂点集合を持つ補助グラフ $C$ を形成する。エッジ $e$ の重み $c_e$ は、$a_e$ および $b_e$ をそれぞれ $A$ および $B$ の対応するエッジの重み（存在しないエッジは無限の重みとして扱う）としたとき、$c_e = \min(a_e, b_e)$ と定義される。
2. MSTの活用: 本手法は最小全域木（MST）を活用する。グラフ $C$ のMSTと、グラフ $A$ のMSTをそれぞれ計算する。
3. 区間の計算: $C$ のMSTに含まれる各エッジ $e$（重み $c_e$）について、アルゴリズムは、$C$ において $e$ によって接続されていた2つのクラスターが、$A$ において単一のクラスターに結合する最小レベル $t(e)$ を特定する。これは、$e$ の両端を接続するパスができるまで、MST $A$ からエッジを反復的に追加することで実現される。
4. バーコード生成: 結果として得られる一連の区間 $[c_e, t(e)]$ をRTD-Liteバーコードと呼ぶ。これらの区間の長さの総和 $\sum (t(e) - c_e)$ が、RTD-Liteメトリック値 $RTDL(A, B)$ を構成する。

アルゴリズム

本論文では2つのアルゴリズムを提案している：

• アルゴリズム1（直接法）: 全ての区間（バーコード）を計算する。これには、エッジのソート、MSTの構築、および連結性を追跡するためのテンポラリ・コピーを用いた非連結集合（DSU）構造の使用が含まれる。
• アルゴリズム2（簡略法）: 個々の区間を再構成することなく、区間の長さの総和（$RTDL(A, B)$）のみを計算する。これは、グラフ$A$ のMSTにおけるエッジの重みの総和（$s_A$）と、グラフ $C$ のMSTにおけるエッジの重みの総和（$s_C$）を計算し、$s_A - s_C$ を返す。このアプローチは、直接法と同じ総和を与えることが数学的に証明されている。

計算量

両アルゴリズムとも、頂点数 $n$ に対して、時間およびメモリの計算量は $O(n^2)$ を達成する。これは、シンプリシスの数に依存して3次またはそれ以上の計算量となる標準的なRTDと比較して、大幅な改善である。この $O(n^2)$ の計算量は、MST構築のためのプリム（Prim）アルゴリズムと、DSU管理に必要な線形操作に由来する。

微分可能性

RTD-Liteの区間の端点は、エッジの重みまたはエッジの重みの最小値によって決定されるため、（部分）微分可能である。この特性により、本メトリックをニューラルネットワークの訓練における微分可能な損失関数コンポーネントとして組み込むことが可能となり、トポロジー構造の保持を目的とした勾配ベースの最適化が可能になる。

主な貢献

1. 効率的なメトリックの提案: 0次元ホモロジー（連結成分）に焦点を当て、RTDの特徴の大部分を効率的に計算する手法として、RTD-Liteを導入した。
2. 計算量の分析: RTD-Liteが時間・メモリの両面で二次スケール（$O(n^2)$）であることを詳細に示し、標準的なRTDが機能しない大規模なデータセットへの適用可能性を実証した。
3. 学習への統合: 学習された表現におけるトポロジー構造の保持を促進するために、RTD-Liteをニューラルネットワークの訓練における損失関数のコンポーネントとして組み込むフレームワークを提示した。
4. 実証的検証: 合成データおよび実世界のデータセットを用いた広範な実験により、RTD-Liteが既存の手法と比較して計算時間を大幅に削減しながら、効果的にトポロジー的な差異を特定できることを示した。

実験結果

著者らは、以下のシナリオにおいてRTD-Liteを評価した：

• 合成データ（クラスターとリング）: クラスター数やリングの数が変化する点群を用いた実験において、RTD-Liteはトポロジー的な不一致の増加に対して単調な応答を示した。対照的に、Centered Kernel Alignment (CKA) メトリックは、トポロジーの変化を一貫して反映できず、混沌とした挙動を示した。
• UMAP表現: 近傍数を変えたUMAPによるMNISTデータセットの2D表現の比較において、RTD-LiteおよびRTDは、トポロジー構造の変化に伴い単調に増加する非類似性を示した。CKAは再び一貫したパターンを示すことができなかった。
• ニューラルネットワーク表現:
  • CNN: CIFAR-10において、RTD-Liteは、異なる初期化を用いて訓練されたネットワークの層が、他のネットワークの対応する層と最も類似していることを正確に特定した。対応する層のマッチングにおいて98%の分類精度を達成し、これはRTD（98%）およびCKA（96%）に匹敵する結果であったが、計算時間はRTDよりも約6倍高速であった。
  • GNN: Amazon Computersデータセットにおいて、RTD-Liteのスコアは、様々なGNNアーキテクチャ（GCN, GraphSAGE, GAT, ClusterGCN）にわたる対応する層において最も低くなり、標準的なRTDのスコアとよく一致した。
• スケーラビリティ: 50,000個の頂点を持つデータセット（CIFAR-10のフル訓練セット）に対し、RTD-Liteは3.75分で比較を完了した。標準的なRTDはGPUメモリの制約により失敗し、CKAは36分を要した。
• 次元削減（オートエンコーダ）: 次元削減のためのオートエンコーダ（"Spheres", F-MNIST, COIL-20データセット）における損失関数として使用した場合、RTD-Liteは、グローバルな多様体構造を保持する上でRTD-AEやTopoAEと同等の性能を達成した。極めて重要な点として、RTD-Liteを用いた訓練は大幅に高速であり、RTDベースの損失でしばしば必要とされる2段階の訓練手順（再構成損失の後にトポロジー損失を行う手順）を必要としなかった。

意義と主張

本論文は、RTD-Liteが、トポロジー的なグラフ比較に関連する決定的な計算上のボトルネックを解決することを主張している。複雑さを $O(n^2)$ に低減することで、これまで不可能であった大規模な学習タスクへの厳密なトポロジー解析の適用を可能にする。著者らは、RTD-Liteが以下の用途における実用的なツールとして機能すると断言している：

• CNNおよびGNNにおけるニューラル表現の比較。
• フルなパーシステンス・バーコードの計算オーバーヘッドなしに、トポロジー構造を保持することによる次元削減の強化。
• マルチスケールのトポロジー的感度が欠けているか、あるいは大規模なデータにスケールしない既存のグラフ比較手法に対する、スケーラブルな代替手段の提供。

本研究は、RTD-Liteを、あらゆる文脈におけるフルTDAの置き換えとしてではなく、現代の機械学習パイプラインへの統合に適した、本質的なトポロジー的差異（特にクラスター構造）を捉えるための非常に効率的な近似手法として位置づけている。