Cleora：シンプルで強力かつスケーラブルなグラフ埋め込み手法

グラフ埋め込み分野では現在、対照学習（contrastive learning）手法が主流を占めており、明示的な目的関数の定式化とポジティブ・ネガティブ例のサンプリングを必要とする。これにより、概念的・計算的なオーバーヘッドが生じる。一方、多次元尺度構成法（Multidimensional Scaling, MDS）やラプラシアン固有写像（Laplacian eigenmap）といった単純で古典的な非教師あり手法は、煩雑な目的関数最適化を回避し、データの幾何構造を直接利用できる。しかしながら、これらの手法は行列固有値分解といった極めて高コストな演算に依存しており、現代のデジタル環境で一般的な大規模グラフへのスケーラビリティに欠けるという課題を抱えている。本論文では、二つの利点を兼ね備えた新アルゴリズム「Cleora」を提案する。これは非教師ありでありながらも、非常に高いスケーラビリティを実現している。我々は、例のサンプリングを伴う一般的な段階的学習フレームワークを用いずに、高品質な埋め込みを生成できることを示す。Cleoraの直感的な学習目的は、「ノードはその近傍ノードと類似しているべきである」というものであり、離散的なノード同士を明示的に遠ざける必要はない。この目的は、ノードの近傍ノードの埋め込みを反復的に重み付き平均化し、次に次元ごとの正規化を行うことで達成される。平均化操作により、アルゴリズムは埋め込み空間を迅速に探索でき、通常数回の反復で最適な埋め込みに到達する。Cleoraは他の最先端CPUベースのアルゴリズムよりも高速に動作し、リンク予測やノード分類といった下流タスクにおいて、競争力のある性能を発揮する。また、Cleoraが対照学習手法と類似したデータ抽象を学習していることを示し、その計算コストははるかに低い。本研究ではCleoraをMITライセンスのもとオープンソース化し、商用利用も可能としている。詳細は https://github.com/Synerise/cleora にて公開されている。