🤖 machine learning

TopoFormer: Topology Meets Attention for Graph Learning

TopoFormerは、グラフを並列化可能なシーケンスへと分解する斬新なTopo-Scanモジュールを介して、トポロジカル構造をアテンションベースのモデルに統合する、軽量でスケーラブルなフレームワークであり、従来のパーシステント・ホモロジーに伴う計算コストを課すことなく、グラフ学習において最先端の性能を実現します。

原著者： Md Joshem Uddin, Astrit Tola, Cuneyt Gurcan Akcora, Baris Coskunuzer

公開日 2026-07-31

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Md Joshem Uddin, Astrit Tola, Cuneyt Gurcan Akcora, Baris Coskunuzer

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

コンピュータに物の「形」を理解させる方法を教えようとしていると想像してみてください。データの世界では、私たちはしばず「グラフ」を使ってつながりを表現します。それは、ソーシャルネットワークにおける友人関係、分子の中の原子、あるいは地下鉄の路線図のようなものです。これらはスプレッドシートのような整然とした格子状ではなく、不規則で複雑な網目状のものです。長い間、コンピュータはこれらの網目における「全体像」を把握することに苦労してきました。なぜなら、個々の点（ノード）や線（エッジ）を見ることに夢中になりすぎて、木を見て森を見ずの状態になっていたからです。

これらの網目の「形」をコンピュータに見せるために、科学者たちは「トポロジカルデータ解析（TDA）」と呼ばれる数学の一分野を利用しています。TDAは、点の正確な大きさや位置には関心を持たず、形の中にある穴、ループ、あるいは島を数える方法だと考えてください。それは、ドーナツが巨大であろうと極小であろうと、それが一つの穴を持っていることを認識するようなものです。もう一つの重要な概念は、言語の読解や画像の認識で有名なAIの一種である「Transformer（トランスフォーマー）」です。Transformerは、単語の長いリストやピクセルのパターンを見つけることには長けていますが、通常、乱れた不規則なグラフには苦戦します。研究者たちが投げかけてきた大きな問いは、「どうすれば、これらの乱れた不規則なウェブを、その重要な『形』の情報を保ったまま、Transformerが読み取れるような整然とした順序のあるリストに変換できるか？」ということです。

ここで、TOPOFORMERという新しい論文が登場します。著者である米国の大学の研究チームは、グラフのためのハイテクスキャナーとして機能する巧妙なツールを構築しました。グラフを無理やり硬直した格子状に押し込める代わりに、TOPOFORMERはグラフを、パンをスライスしたり、体のCTスキャンを連続して撮ったりするように、一連の薄く順序立てられた層へと切り分けます。

この「魔法の手品」がどのように機能するかを説明しましょう。彼らはTopo-Scanと呼ぶ手法を用いています。複雑に絡まった紐の塊を想像してください。従来の手法では、塊全体を一度に測定しようとしたり、あらゆるねじれに対して複雑な3Dマップを作成しようとしたりしますが、これには膨大な時間と計算能力が必要です。しかし、TOPOFORMERは異なるアプローチを取ります。スライディングウィンドウを使用して、グラフをゆっくりと「スライス」していくのです。スライスが進むにつれて、その各層において単純な事柄をカウントします。紐の断片はいくつあるか？いくつのループが形成されているか？今、いくつの結び目が目に見えているか？

これらのカウントによって、短く整然とした数字のリスト、すなわち「トポロジカル・トークン・シーケンス」が作成されます。このリストは、Transformerが読み取るのに完璧な形状をしています。そしてTransformerはこのリストを見つめ、小さな局所的なループから大きな全体的な形に至るまで、グラフの全体的な構造を認識することを学習します。著者らは、この手法が従来の技術（高価な計算によって停滞しがちなもの）よりも高速で計算リソースへの負荷が低いだけでなく、驚くほど効果的であることを発見しました。

実験において、TOPOFORMERは2つの主要なタスクでテストされました。一つは、異なる種類のグラフ（例えば、グラフが化学分子を表しているのか、それともソーシャルネットワークを表しているのか）を分類すること、もう一つは、分子の特性（薬が効くか、あるいは毒性があるかなど）を予測することです。結果は目覚ましいものでした。8つの異なるグラフ分類ベンチマークにおいて、TOPOFORMERは最高精度または2番目に高い精度を達成し、長年標準であった多くの複雑で重量級のモデルを打ち負かしました。分子特性の予測においては、現在使用されているトップレベルのモデルと同等、あるいはそれ以上の性能を発揮し、しばしばトップ3に入りました。

特にエキサイティングなのは、TOPOFORMERはグラフ内のすべてのノードに対して、あらかじめ独自の「エンベディング（複雑な内部コード）」を学習する必要がないという点です。その代わりに、グラフ全体を単一の構造化されたオブジェクトとして扱い、直接スキャンします。著者らは、このアプローチが、グラフのための「基盤モデル（あらゆる種類のネットワークを、毎回最初から学習し直すことなく理解できる超スマートなAIシステム）」を構築するための、効率的な新たな道筋を提供すると示唆しています。また、彼らは自分たちの手法が「安定している」ことを数学的に証明しました。つまり、入力となるグラフがわずかに変化しても、出力がめちゃくちゃにならないということであり、これは実世界の信頼性において極めて重要です。

要約すると、TOPOFORMERは、乱れた不規則なグラフの世界を、クリーンで読み取り可能な「物語」へとスライスし、強力なAIにその物語を読ませることで、データの形を理解させるのです。これは、機械に「つながり」や「形」という観点から世界を見せるための、より軽く、より速く、そして驚くほど効果的な方法なのです。

技術要約: TOPOFORMER

問題提起

グラフ表現学習は、視覚や言語における基盤モデルで見られるような汎化性能を達成する上で、大きな課題に直面しています。グラフの不規則かつ非ユークリッド的な性質は、転移可能な帰納バイアス（inductive biases）の設計を困難にします。トポロジカル・データ解析（TDA）、特にパーシステント・ホモロジー（PH）は、安定したマルチスケールの構造情報（グローバルな連結性とサイクル）を符号化するための原理的な手法を提供しますが、そのディープラーニングへの採用は主に2つのボトルネックによって阻害されてきました：

計算コスト: 標準的なPHパイプラインは、パーシステンス図（persistence diagrams）を計算するために高価なグローバル削減を必要とし、並列化が困難です。
ベクトル化の摩擦: パーシステンス図をベクトル（例：パーシステンス・イメージ、ランドスケープ）に変換するプロセスは、しばしばアドホックであり、逐次的な構造情報を破壊し、ダウンストリームの性能に大きな影響を与えます。さらに、グラフに対する従来のサブレベル・フィルトレーション（sublevel filtrations）は、「早期飽和」の問題に陥ることが多く、高値のノードが早期に活性化することで複体を埋め尽くし、遅れて出現するトポロジカルな特徴を抑制してしまいます。

既存のグラフ・トランスフォーマー（Graphormer, GPSなど）は、通常、ノード・トークンに直接作用し、位置エンコーディングやアテンション・バイアスを通じて構造を注入しますが、これらは計算負荷が高く、グローバルなトポロジカル不変量への焦点が薄い傾向があります。

手法: TOPOFORMER と Topo-Scan

著者らは、完全なパーシステンス図や複雑なベクトル化ステップを回避し、トポロジカルな構造をアテンションに適したシーケンスへと符号化する、軽量でスケーラブルなフレームワークである TOPOFORMER を提案しています。

コア・コンポーネント: Topo-Scan

中心となる革新技術は Topo-Scan です。これは、グラフを短く順序付けられたトポロジカル・トークンのシーケンスへと分解するモジュールです。標準的なPHが単一の入れ子状のフィルトレーションを構築するのに対し、Topo-Scanはスライディング・ウィンドウ・アプローチを採用しています：

フィルトレーション: 頂点上にスカラー関数 $f: V \to \mathbb{R}$ を定義します（例：次数、曲率、熱核シグネチャ）。
スライシング: 累積的な閾値を用いる代わりに、フィルトレーション関数による区間 $[\alpha_i, \alpha_i + m]$ に基づいて、グラフを重複する部分グラフ $G_i$ に分割（スライス）します。
トークン生成: 各スライスに対してクリーグ複体（clique complex）を形成し、4つの不変量を計算します：
1. $\beta_0$ : 連結成分の数（Betti-0）。
2. $\beta_1$ : サイクルまたは穴の数（Betti-1）。
3. $|V_i|$ : ノード数。
4. $|E_i|$ : エッジ数。
シーケンス形成: これらの不変量は、長さ $4N$ （ $N$ はスライスの数）のコンパクトで順序付けられたシーケンス $\Gamma(G)$ を形成します。このシーケンスは、標準的なサブレベル・フィルトレーションにおける早期飽和の問題を回避しながら、異なるスケールにおけるトポロジカルな特徴の進化を保持します。

トランスフォーマー・アーキテクチャ

生成されたトポロジカル・シーケンスは、トランスフォーマー・エンコーダに直接入力されます。

入力: 特定のスライスのトポロジカルな状態を表すトークンのシーケンス。
処理: トランスフォーマーは自己注意（self-attention）メカニズムを利用してシーケンス間の依存関係を捉え、マルチレゾリューションな構造パターンを効果的にモデリングします。
デュアル・トランスフォーマー・フレームワーク: モデルは複数のフィルトレーション関数（例：Ollivier-Ricci曲率、熱核シグネチャ）を並列に処理できます。独立したトランスフォーマーからの出力は、学習可能な加重和とMLP分類器を介して融合され、グラフレベルの埋め込みを生成します。
分子特性予測 (MPP): 分子タスク向けに、本フレームワークは、標準的な分子フィンガープリント（例：ECFPs）と共にトポロジカル・シーケンスを統合し、それらをアテンションベースの結合（concatenation）によって組み合わせます。

理論的保証

論文では、Topo-Scanに対する理論的な安定性の保証が提供されています。著者らは離散的な $\ell_1$ 安定性境界を確立し、フィルトレーション関数の小さな摂動が、出力シーケンスに限定的な変化しか与えないことを証明しています。これは、Topo-Scanトークンとインターレベル・パーシステンス・モジュールの関係に基づており、本手法が入力信号のノイズに対して堅牢であることを示しています。

主な貢献

スケーラブルなトポロジカル符号化: トポロジカルな構造をアテンション対応のシーケンスに変換する手法であり、ノード埋め込みや重い前処理に依存することなく、トランスフォーマーによるグラフ処理を可能にします。
TDAとディープラーニングの架け橋: 逐次的なアテンション・メカニズムを通じて、局所的およびグローバルなグラフ構造の両方を捉える統一されたフレームワークを提供し、パーシステンス図の計算オーバーヘッドを回避します。
包括的な評価: グラフ分類および分子特性予測のベンチマークにおいて、最先端（SOTA）の性能を示す広範な実験を実施しました。
効率性と安定性: 表現の堅牢性に関する理論的保証と、大規模なアプリケーションに適した、予測可能で効率的な計算能力に関する実証的証拠を提供します。

実験結果

著者らは、多様なデータセットを用いてTOPOFORMERを評価しました。

グラフ分類: 9つのベンチマーク（BZR, MUTAG, IMDB-B/M, REDDIT-B/5K, OGBG-MOLHIVを含む）でテスト。
- TOPOFORMERは、8つのベンチマークのうち7つで最高または2番目に高い精度を達成しました。
- BZR, MUTAG, PROTEINS, IMDB-M, REDDIT-B, REDDIT-5Kにおいて新たなSOTAを確立しました。
- GNN、トポロジカル手法（PersLay, DMP）、およびコントラスティブ学習モデルを含む20のベースラインを上回りました。
- 大規模なOGBG-MOLHIVデータセットにおいて、強力なGraphormerベースラインのAUCから約2ポイント以内の差に抑えており、スケーラビリティを示しました。
分子特性予測 (MPP): MoleculeNetの7つのデータセット（BBBP, Tox21, ToxCast, ClinTox, SIDER, BACE, HIV）でテスト。
- TOPOFORMER*（フィンガープリントとの結合）は、ToxCast, ClinTox, BACEにおいて最高のROC AUCを達成しました。
- Tox21では準優勝となり、HIVにおいても非常に競争力のある結果を示しました。
- 全データセットにおける最高モデルからの平均偏差および平均ランクにおいて、2番目に低い値を記録しました。
アブレーション研究:
- vs. PH: TOPOFORMERは、標準的なPH-MLPおよびPH-Transformerのベースラインの両方を上回り、Topo-Scanが標準的なPHフィルトレーションよりも表現力豊かな構造を捉え、逐次的符号化が静的なベクトル化よりも優れていることを確認しました。
- フィルトレーションの感度: モデルは、異なるフィルトレーション関数（Degree, Ollivier-Ricci, HKS）およびウィンドウ幅に対して堅牢性を示しました。
- 特徴量の組み合わせ: トポロジカルな特徴を分子フィンガープリントと組み合わせることで、いずれか一方のモダリティのみを使用する場合よりも一貫して高い性能を示しました。

意義と主張

本論文は、TOPOFORMERを完全な基盤モデルそのものではなく、トポロジーを考慮したグラフ基盤モデルへの一歩として位置付けています。その意義は以下の通りです：

統一的アプローチ: トポロジカルな帰納バイアスをアテンション・フレームワークに直接統合する、並列化可能な統一的アプローチを提供します。
効率性: グローバルなパーシステンス図の計算を回避することで、予測可能かつ効率的な計算を実現し、従来のTDAが遅すぎる大規模なアプリケーションへの適用を現実的なものにします。
汎用性: TOPOFORMERが生成する固定サイズの転移可能な表現は、様々なサイズやドメインのグラフ間で一貫した埋め込みを必要とするタスクに適しており、グラフ学習における中心的な課題に対処しています。
限定的なスコープ: 著者らは、本研究が簡略化されたグラフレベルの実装に焦点を当てていることを明示しています。ノード/エッジレベルのタスク、ヘテロジニアスな設定（時系列/引用グラフ）、およびヘテロジニアスなコーパスを用いた大規模な事前学習については、今後の課題としています。彼らは、Topo-Scanを、完全なパーシステント・ホモロジーを置き換えるものではなく、それを補完する軽量な要約として捉えています。