マイケル・ブロンスタインは代数的位相幾何学から学び、新しいグラフニューラルネットワークのコンピューティング構造を提案しました。

この記事は、Cristian Bodnar と Fabrizio Frasca の共著で、2021 ICML で発表された C. Bodnar、F. Frasca らによる論文「Weisfeiler and Lehman Go Topological: Simple Networks with Information Passing」と、2021 NeurIPS で発表された「Weisfeiler and Lehman Go Cellular: CW Networks」に基づいています。

この記事は、微分幾何学と代数的位相幾何学の観点からグラフニューラルネットワークについて説明するシリーズの一部にすぎません。

グラフは、コンピュータネットワークから大型ハドロン衝突型加速器内の粒子の相互作用まで、あらゆるものをシミュレートするために使用できます。グラフは離散的かつ組み合わせ的な特性を持ち、計算しやすいまま抽象的な関係を表現できるため、あらゆるところに存在しています。グラフが人気を博している理由の 1 つは、ノードが空間内のどこにあるのか、エッジがどのように曲がっているのかといったジオメトリを抽象化し、ノードがどのように接続されているかという表現のみを残すことです。

グラフ理論は、レオンハルト・オイラーが 1741 年に著した『Geometria situs』の中で、有名なケーニヒスベルクの 7 つの橋の問題には解がないことを指摘したことに由来しています。

キャプション: 7 つの橋の問題では、ケーニヒスベルク市内で橋を何度も渡ることなく円形の歩行ルートを見つける必要があります。オイラーが言ったように、ケーニヒスベルクの街の正確な形は重要ではありません。重要なのは、異なる土地区画 (グラフのノード) が互いにどのように接続されているか (エッジ) です。オイラーは、すべてのノードの次数が偶数である場合にのみ、そのようなサイクルが存在することを示しました。さらに、オリジナルの橋のうち、現代まで残っているのは 5 つだけです。画像出典: Wikipedia

興味深いことに、オイラーの発見はグラフ理論の始まりを示すだけでなく、位相幾何学の誕生とも考えられています。グラフと同様に、位相学者は空間の特定の形状や幾何学とは無関係な特性に興味を持っています。

これらのアイデアの現代的な表現は、1895 年にアンリポアンカレによる独創的な論文「Analysis situs」に登場しました。この論文により、位相不変量をより簡単に見つけて計算できる多様体の組み合わせ的記述への関心が高まりました。

キャプション: レオンハルト・オイラー (1707-1783) とアンリ・ポアンカレ (1854-1912)

これらの組み合わせ記述は現在ではセル複合体と呼ばれ、グラフの高次元一般化として考えることができます。

ノードとエッジによって形成されるグラフとは異なり、セル複合体には高次元構造または「セル」も含めることができます。頂点は 0 セル、エッジは 1 セル、2D サーフェスは 2 セルなどです。セル複合体を構築するには、セルの境界を他の低次元セルに接着して層状にします。

特殊なケースとして、単位格子が単体（辺、三角形、四面体など）で構成されている場合、これらの空間は単体複合体とも呼ばれます。

キャプション: グラフは、エッジ (1 セル) を接続する頂点の集合として見ることができます。同様に、単一細胞複合体と細胞複合体は、2 つの細胞 (青で表示)、3 つの細胞 (緑で表示) などを接続するグラフとして表示できます。

1 機械学習とデータサイエンスにおけるトポロジー

トポロジーが実用的なツールになるまで 400 年も待つ必要はないと私たちは考えています。

浅い複合体などの位相構造は、機械学習やデータサイエンスにおいて、1990 年代に登場し、メトリックに依存しない、ノイズに対して堅牢な方法で「データの形状」を分析することを目指す手法のクラスである位相データ分析 (TDA) の傘下で使用されてきました。

TDA のルーツは、1920 年代後半の最も多作な位相幾何学者の 1 人である Leopold Visholis の研究にまで遡ることができます。しかし、これらの技術が大規模に適用できるようになるには、現代のコンピューティングの出現を待たなければなりませんでした。

キャプション: ポイントクラウドが与えられると、各ポイントの周りの固定半径の閉じた球間の交差によって、単純な合成が生成されます。球の半径を徐々に大きくすることで、単純な複合体の入れ子になったシーケンスを取得できます。画像提供: Bastian Rieck。

TDA の主力は、ポイントクラウドからトポロジカルな特徴を抽出する方法であるパーシステントホモロジー (PH) です。ポイントのデータセットが与えられると、PH は単純な複素数のネストされたシーケンスを作成します。各複素数は、分析される基礎となるポイントクラウドの特定のスケールに対応します。次に、スケールが徐々に大きくなり、シーケンス内のある複合体から次の複合体に移行するにつれて現れたり消えたりするさまざまなトポロジカルな特徴 (接続されたコンポーネント、ループ、穴など) を追跡します。

ディープラーニングの時代において、永続的ホモロジーは「第二の人生」を迎えました。これは、永続的ホモロジーを介してバックプロパゲーションが可能であることが示され、すでに確立されている TDA デバイスをディープラーニングフレームワークに統合できるようになったためです。

最近の一連の研究では、データと計算をサポートするためのより豊富な基礎位相空間として、幾何学的深層学習における簡略化とセルラー複合体のさまざまな使用法が提案されています。

この洞察を活用した最初のいくつかの研究では、単純化された複合体上で動作する畳み込みモデルとランダムウォーク法が提案されました。この論文のように、畳み込みモデルは、単純複合体と細胞複合体における情報伝達の特定の例として理解することができます。

計算はこれらの空間の位相構造 (つまり近傍構造) によって実行されるため、この一連の方法を位相情報転送と呼びます。このフレームワークでは、下の図に示すように、異なる次元の可能性のある隣接するセルが情報を交換しています。

キャプション: トポロジカル情報伝送の概略図。青い矢印は、上位層の隣接するセル、つまり同じ高次元セルの境界にあるセル間の情報の「水平」伝播を表しています。赤い矢印は「垂直」の情報伝播を表しており、セルは境界にある低次元のセルから情報を受け取ります。境界セルからの情報は、より粗い表現に集約され、これは（微分可能な）集約の形式として解釈できる計算です。

GNN におけるグラフを超えて

細胞複合体によって提供される豊富な構造にもかかわらず、グラフが機械学習において最も一般的なトポロジカルオブジェクトであり、それを上回るデータセットはほとんどないことを無視することはできません。それでも、入力グラフを変換することで、これらの興味深い位相空間を活用することができます。

グラフを高次元位相空間に変換することを、カテゴリ理論における同名の概念に似せて「リフティング」と呼びます。これは、特定のルールに従って入力グラフに高次元ユニットを追加する変換です。たとえば、グラフ内の各崖またはサイクルに高次元セルを付加することで、グラフをセル複合体に昇格できます。これを行うことで、グラフは、元のグラフよりも構造が強化され、GNN の計算構造を改善できる別の空間に置き換えられます。以下では、このアプローチの具体的な利点について説明します。

キャプション: 2 次元の閉じたディスクの境界をグラフ内の誘導ループに接着することで、グラフから高次元のセル複合体を構築できます。

高レベルの機能と構造

GNN は通常、ノード中心のビューを採用し、エッジに存在するデータは頂点間の通信を増やすための補助情報としてのみ扱われます。トポロジカルな情報伝達では、すべてのユニットがファーストクラスのオブジェクトです。次元に関係なく、隣接するユニットと情報を交換することによって展開される特定の表現が割り当てられます。これにより、特定の高次構造とその相互作用を明示的にモデル化するための方法が提供されます。特に、入力グラフの限界（つまり、1 セル）機能を進化させる原理的な方法を提供します。これは、GNN モデルの大規模なクラスでは考慮されていない問題です。

高レベルのインタラクション

グラフは定義上バイナリ（「ペアワイズ」）であり、2 つ以上のオブジェクトが関与する関係や相互作用を表すことはできません。これは、高次の相互作用を特徴とする複雑なシステムをモデル化する場合、問題になる可能性があります。たとえば、化学反応における 3 つの反応物は同時に相互作用する可能性があります。細胞複合体では、この状況は 2 つの細胞間の反応物の接続 (つまり、「塗りつぶされた」三角形) によってエンコードできます。したがって、モデルの計算フローは、高次の相互作用の存在に適応します。

図のキャプション: 細胞ワイスファイラー・レーマン (CWL) テストは、古典的な WL テストを細胞集団に拡張したもので、アルゴリズムの各ステップで隣接する細胞 (異なる次元を持つ場合もある) の色を完全にハッシュします。

表現力

情報伝達型 GNN の表現力は、Weisfeiler-Leman (WL) グラフ同型性テストによって制限されます。このテストでは、三角形やサイクルなどの特定のグラフのサブ構造を検出できないことが知られており、非常に単純な非同型グラフさえも区別できません。

以前の論文（論文アドレス：https://arxiv.org/abs/2103.03212; https://arxiv.org/abs/2106.12575）によると、細胞バージョンの WL テスト（CWL）を使用して、細胞複合体の同型性をテストできます。この新しいテストを上記のグラフリフティング手順と組み合わせると、WL テストよりも大きなクラスのグラフを区別できることがわかります。したがって、特定の条件下では、トポロジカル情報転送プロセスはこのテストの利点を継承し、標準の GNN と比較して表現力が向上します。

スムージング不足、スムージング過剰、ボトルネック

メッセージパッシング GNN では、n ホップ離れたノードが通信できるようにするために n レイヤーが必要です。少数のレイヤーのみが使用され、遠くにあるノードが情報を交換できない場合、この現象はアンダーリーチと呼ばれます。

対照的に、レイヤーを多すぎる数使用すると、過度に平滑化され、グラフの構造的なボトルネックで情報が失われる可能性があります。

セル複合体は、高次元セルによって誘導されるより豊富な近傍構造によって、遠く離れたノード間のショートカットが作成されるため、これらの問題を軽減できます。したがって、情報が有効になるには、いくつかの計算手順を実行するだけで済みます。

キャプション: GNN では、離れたノードが通信できるようにするために多くのレイヤーが必要です (左)。高次元セルはショートカットを作成することで、空間の基礎となるトポロジを変更します (右)。これにより、リモートノードはいくつかのメッセージングステップで情報を交換できるようになります。

階層モデリング

トポロジカルな情報の受け渡しによって実行される計算は階層的であり、情報は低次元セルから高次元セルへ、また高次元セルから低次元セルへ流れ、標準的なグラフニューラルネットワークの「水平」プーリングではなく、「垂直」(微分可能) プーリングの形式として考えることができます。これにより、GNN ベースのプーリングのパフォーマンスに悪影響を与える入力グラフのきめ細かい情報を無視することなく、グラフの領域を「圧縮」するという誘導バイアスが維持されます。

図 1: トポロジカルな情報転送により、異なる次元のユニット間のレイヤーに情報が存在できるようになります。

ドメインアライメント

特定のアプリケーションは、細胞複合体の構造と自然に一致しています。たとえば、分子の原子、結合、化学環は、0 セル、1 セル、2 セルとして表現できます。分子の物理的構造とセルの複合体表現が直接対応しているため、トポロジカル情報転送によって上記の特性を活用できます。これらの表現は、分子特性予測タスクにおけるトポロジカル情報転送によって達成される最先端の結果も実証しています。

アライメントが適切に機能するその他のアプリケーションとしては、コンピューターグラフィックスアプリケーションの離散多様体 (グリッド)、ソーシャルネットワーク (クリークが特に重要)、Google マップなどの空間グラフ (街路ブロックを自然に「立方体」セルとして表現できる) などが挙げられます。

図1: カフェインは2次元細胞複合体としてモデル化される

2 位相幾何学と微分幾何学の融合

代数的位相幾何学や微分幾何学との多くの興味深いつながりが位相情報転送で保持され、これまでグラフや幾何学の深層学習で十分に活用されていなかった数学的ツールの使用が可能になります。

ホール代数と方向の同値性

代数的位相幾何学では、有向単体複合体を扱うことが多く、各単体は任意の「方向」を持ちます。たとえば、各エッジのソースノードとターゲットノードを選択し、各三角形のノードをトラバースする順序を選択します。方向が選択されると、「境界演算子」を介して特定の単体の境界を計算するなど、複雑な代数演算子を実行できます。これらの代数演算は、単体複合体内の「穴」、つまり境界はないが他のものの境界上にはない領域を見つけるためにも使用できます。舞台裏では、パーシステントホモロジーはこれらの計算を利用してトポロジカルな特徴を検出します。

キャプション: 2 単体に境界演算子を適用すると三角形が生成されます。演算子を三角形に再度適用すると、三角形は閉路であるため境界がないため、ゼロになります。

位相情報転送は、境界演算子などの代数演算子の (非線形) 一般化として考えることができます。したがって、トポロジカルな情報転送も同様に動作する必要があります。つまり、各レイヤーの出力が入力複合体の方向の変化に「一貫して」応答することが望まれます。言い換えれば、レイヤーが方向的に等しくなるようにしたいのです。私たちの研究では、適切な非線形性と情報伝達関数を選択することで、トポロジカル情報伝達がこの特性をどのように満たすことができるかを研究しており、これは純粋な畳み込み設定でも研究されています。

位相空間の区別

最も古くから知られている位相不変量の 1 つであるオイラー特性は、もともとプラトン立体の分類に使用されており、各次元のセルの数の交互の合計として定義できます。驚くべきことに、2 つのセル複合体が同相である場合、同じ空間の異なる離散体であっても、これらの合計は一致します。

興味深いことに、トポロジ情報伝達モデルの読み出し操作では、各次元セルに不変量を含む削減を適用するため、このトポロジの不変量を簡単に計算できます。

したがって、このタイプのモデルは、構築によって特定の非同型空間（つまり、異なるオイラー特性を持つ空間）を区別することができます。計算の観点から見ると、これは WL テストの一般化と見なすことができます。ここでは、2 つのセル複合体が同一であるかどうかを判断するだけでなく、それらが互いに同型であるかどうかを判断することにも関心があります。

離散ホッジ理論

離散ホッジ理論は、細胞複合体の位相特性に対してより幾何学的な説明を提供します。 k セルに関連付けられた特徴の符号が k セルの方向に依存する場合、これらの特徴は、微分幾何学からの微分 k シェイプの離散化バージョン (つまり、積分可能な k 次元の体積要素) として数学的に考えることができます。ホッジラプラスと呼ばれる演算子はグラフィカルラプラスを一般化し、これらの微分形式で使用できます。このラプラシアンに基づく拡散 PDE は、複合体内のホールに関連付けられた信号に極限で収束することが示されます。

図のキャプション: ホッジラプラス演算子に基づく拡散偏微分方程式は、ラプラス演算子カーネル上の初期微分形式の投影の限界に収束します。この画像は、ホッジラプラシアンのゼロ固有ベクトルが複合体の穴の周囲でどのように高い値をとるかを示しています。

最初の単純なニューラルネットワークモデルは、実際にはホッジラプラスの畳み込みモデルに基づいており、これはトポロジカル信号処理にヒントを得たものでした。つい最近、この演算子に基づく畳み込みモデルのバージョンが、計算代数トポロジーにおける NP 困難問題を解決するために使用されました。

3 最終的な考察

これらは単なる偽装されたチャートなのでしょうか?

最近の論文では、とりわけ、トポロジカルな情報伝達手法は、細胞複合体の構造をエンコードする修正されたグラフ上で情報伝達を行う GNN にすぎないと主張しています。これは、メッセージパッシング計算にセルのペアが関係する畳み込みモデルに当てはまります。

ただし、最も一般的な形式では、情報関数により、高次元セルは境界上の低次元セル間で渡される情報を調整できます。一般に、エッジは正確に 2 つのノードを接続し、2 セルは任意の数のエッジに接続できるため、グラフ上で通常の情報転送を実現できます。

どちらの場合も、計算はデータが存在する基礎となる空間のトポロジによって実行されます。情報転送に関してこのトポロジカルな観点を採用することで、純粋に計算上の考慮を超えた利点がもたらされると考えています。貴重な数学的つながりに加えて、他の数学およびコンピューティング分野への研究討論も開かれ、単調になりがちなコミュニティ間の積極的な相互交流を促進します。