スペクトルクラスタリングの彼方へ：微分可能なグラフ分割のための確率的カット

Abstract

グラフカットの確率的緩和は、スペクトルクラスタリングに対する微分可能な代替手段を提供し、固有分解なしでエンドツーエンドおよびオンライン学習を可能にします。しかし従来研究は RatioCut に焦点を当てており、一般的な保証や原理に基づく勾配は欠けていました。われわれは、正規化カットを含む広範なカットのクラスを包含する統一的な確率的枠組みを提示します。この枠組みは、積分表現とガウスの超幾何関数によって期待される離散カットに対する厳密な解析的上界を与え、前向きおよび後向きの計算を閉形式で実現します。これらの結果により、広範なクラスタリングおよび対照学習目的をカバーする、スケーラブルで微分可能なグラフ分割のための、厳密で数値的に安定した基盤が提供されます。