Large-scale semi-supervised learning with online spectral graph sparsification
Abstractの概要
本論文は、完全な類似度グラフをメモリに格納することが不可能な厳しいメモリおよび計算制約の下で動作する、スケーラブルなグラフベース半教師あり学習アルゴリズムSparse-HFSを提案している。オンラインスペクトルグラフスパース化（Kelner and Levin, 2013）とSDD行列ソルバーを組み合わせ、挿入のみのエッジストリームからスペクトルスパーシファイアを逐次的に維持し、O(n polylog(n))の空間計算量とO(m polylog(n))の時間計算量を達成する。アルゴリズム安定性解析を通じた理論的汎化限界を提供し、スパース化精度εが学習性能にどのように影響するかを定量化している。合成データセットでの実験により、近似手法が大幅に少ないエッジ数で正確なstable-HFSに近い精度を達成することが示された。
新規性
主な新規性は、オンラインスペクトルグラフスパース化をグラフベース半教師あり学習に統合し、完全なグラフをメモリに格納する必要のないstable-HFSのセミストリーミング変種を実現した点にある。また、安定性に基づく汎化解析を提供し、スパース化近似が学習性能に与える影響を形式的に定量化し、固定εに対して収束速度が保持されることを示した点も特徴的である。
成果
定理1により、固定されたスパース化精度εに対して、Sparse-HFSは正確なstable-HFSと同じ漸近的な汎化誤差収束オーダーを保持し、ε²/l²にスケールする追加の近似項は他の限界項に支配されることが証明された。12,100点の合成データセットでの実験（ε=0.8, γ=1）において、精度がほぼ最適となるk=4500付近で、スパーシファイアは元のグラフのエッジの約10%のみを保持しながらstable-HFSと同等の精度を達成した。
論文の注目点
- Sparse-HFSはオンライン(1±ε)スペクトルスパーシファイアを維持し、完全なグラフを格納することなく挿入のみのストリームからエッジを処理しながら、O(n polylog(n))の空間計算量とO(m polylog(n))の時間計算量でグラフベースSSLを実行可能にする。
- アルゴリズム安定性による理論解析により、スパース化は汎化限界に制御された近似項（ε²/l²にスケール）を追加するが、固定εに対して正確なstable-HFSと同じ漸近的収束オーダーが保持されることが示された。
- 12,100点の合成ベンチマークにおいて、Sparse-HFSは最適動作領域（k≈4500）付近でstable-HFSの性能に近い結果を示し、元のグラフのエッジの約10%のみを保持するだけで済んだ。