スペクトラルクラスタリングは、データ内の隠れたクラスタ構造を捉える最も効果的なクラスタリング手法の一つです。しかし、類似グラフの構築とその後の固有値分解において二次的な複雑さを持つため、大規模な問題には適していません。これまでに、スペクトラルクラスタリングを加速するための多くの手法が提案されてきましたが、計算ボトルネックを削減するために元のデータから大幅な情報損失を引き起こすことが多いです。本論文では、ランダムビニング特徴量（Random Binning features: RB）を使用して類似グラフの構築と固有値分解を同時に加速する新しいスケーラブルなスペクトラルクラスタリング手法を提案します。具体的には、RBによって生成された大きな疎行列の内積により、グラフ類似度（カーネル）行列を暗黙的に近似します。次に、最先端のSVDソルバーを導入し、この大きな行列の固有ベクトルを効率的に計算してスペクトラルクラスタリングを行います。これらの2つの要素を使用することで、計算コストはデータ点数に対して線形となりながらも同様の精度を達成できます。理論解析によると、RBを通じたスペクトラルクラスタリングは標準的なランダム特徴量近似よりも正確なスペクトラルクラスタリングへの収束が速いことが示されています。8つのベンチマークデータセットでの広範な実験結果は、提案手法が既存の最先端手法と比較して精度と実行時間において優れているか同等であることを示しています。さらに、提案手法はデータサンプル数およびRB特徴量数に対して線形スケーラビリティを持つことが確認されました。