Large-scale semi-supervised learning with online spectral graph sparsification

以下は、Calandriello、Lazaric、Valko による論文「Large-scale semi-supervised learning with online spectral graph sparsification」の詳細な技術的概要です。

1. 問題定義

本論文は、大規模な設定における**半教師あり学習（SSL）**の課題に取り組んでいます。その課題とは以下の通りです：

• ラベル付きデータの不足と高コスト: 高品質なラベルの取得は困難であり、一方でラベルなしデータは豊富に存在します。
• グラフ構造: データの類似性は、ノードがデータ点を表し、エッジが類似性を表すグラフ $G=(V, E)$ に符号化されています。
• 計算およびメモリ制約: 調和関数解法（HFS）などの従来のグラフベース SSL 手法は、グラフラプラシアン（$L_G$）を含む線形系を解く必要があります。
  • $n$ 個のノードを持つ密なグラフの場合、標準的なソルバは$O(n^3)$ の時間と$O(n^2)$ の空間を必要とします。
  • これは $n$ が大きい場合（例：数百万ノード）には実行不可能であり、完全な類似性行列をメモリに格納することを妨げます。
• 目標: 完全なグラフを一度も格納することなく、エッジのストリームを$O(n \cdot \text{polylog}(n))$ の空間で処理し、エッジあたりの償却計算コストを $O(\text{polylog}(n))$とするアルゴリズムを開発することです。

2. 手法

著者らは、理論的に健全な HFS の変種であるStable-HFSとオンラインスペクトルグラフスパース化を組み合わせるアルゴリズムSparse-HFSを提案します。

A. Stable-HFS 定式化

標準的な HFS は正則化最小二乗問題を最小化しますが、ラプラシアン行列の特異性に悩まされます。著者らは Belkin ら（2004）のStable-HFSアプローチを採用し、定数ベクトルに直交する関数（$\langle f, \mathbf{1} \rangle = 0$）に仮説空間を制限します。
解は以下のように定式化されます：
$$\hat{f} = (\gamma l L_G + I_S)^+ y - \mu \mathbf{1}$$
ここで、$I_S$ はラベルなしノードをマスクする単位行列であり、$\mu$ は直交制約を強制するために閉形式で計算される補正項です。

B. オンラインスペクトルスパース化

複雑性を低減するため、著者らは完全なグラフ $G$ 上で系を解くのではなく、スペクトルスパースィファイア $H \subseteq G$ を維持します。

• 定義: グラフ $H$ が $G$ の $(1 \pm \epsilon)$-スペクトルスパースィファイアであるとは、すべてのベクトル $x$ に対して以下が成り立つことを意味します：
  $$(1-\epsilon)x^T L_G x \leq x^T L_H x \leq (1+\epsilon)x^T L_G x$$
• インクリメンタル構築（Kelner-Levin アルゴリズム）:
  • このアルゴリズムはセミストリーミング設定で動作します。エッジを 1 つずつ受け取ります。
  • エッジはバッファ $A$ に蓄積され、サイズが $O(n \log^2 n / \epsilon^2)$ に達するまで保持されます。
  • その後、バッファは現在のスパースィファイア $H$ とマージされ、新しいスパースィファイアが計算されます。
  • 主要なメカニズム: エッジは有効抵抗（$R_e$）に基づいてサンプリングされます。正確な $R_e$ の計算は高価であるため、著者らは**対称対角優位（SDD）**線形ソルバ（Koutis ら、2011）を用いて $R_e$ を $O(n \cdot \text{polylog}(n))$ の時間で近似します。
  • 得られるスパースィファイア $H$ は $O(n \cdot \text{polylog}(n))$ 個のエッジを持ち、これによりラプラシアン系の効率的な解法が可能になります。

C. Sparse-HFS アルゴリズム

1. 空のスパースィファイア $H$ を初期化する。
2. ストリームからエッジを受け取る。
3. バッファサイズ閾値に達したら、Kelner-Levin スパース化手順を用いて $H$ を更新する。
4. ラプラシアン $L_H$ を構築し、$G$ ではなく $H$ 上で Stable-HFS 線形系を解く。
5. 解 $\hat{f}$ を出力する。

3. 主要な貢献

1. スケーラブルなアルゴリズム: Sparse-HFSの導入。これは$O(n \cdot \text{polylog}(n))$ の空間とエッジあたりの償却 $O(\text{polylog}(n))$ の時間で大規模 SSL 問題を解決する最初の手法です。完全な類似性行列の格納を回避します。
2. 理論的な汎化保証:
   • 著者らは、スパース近似に対する汎化誤差 $R(\hat{f})$ の上限を導出しました。
   • アルゴリズム的安定性理論を用いて、スパース化によって生じる誤差（$\epsilon$ によって制御される）が収束率を劣化させないことを証明しました。
   • 定理 1: 固定された $\epsilon$ に対して、近似アルゴリズムは正確な Stable-HFS と同じ次数の保証を提供することを示しています。近似誤差項は $1/l^2$（$l$ はラベル付きノード数）としてスケーリングするため、利用可能なラベルが増えるにつれて無視できるようになります。
3. 特異性の処理: 安定性制約（$\mathbf{1}$ への直交性）の統合により、疑似逆行列やスパースィファイアの使用にもかかわらず、厳密な理論分析が可能になりました。

4. 実験結果

著者らは、$n=12,100$ 個の点と 2 つのクラスを持つ合成データセット（$R2$）上で Sparse-HFS を評価しました。

• 設定: 彼らは $k$ を 100 から 12,000 まで変化させた $k$-NN グラフを構築し、エッジ数は最大 $1.38 \times 10^8$ になりました。
• 性能:
  • Sparse-HFS と Stable-HFS の両方とも、$k > 4000$（クラスターが接続する点）になるまでラベルを効果的に伝播できませんでした。
  • 一度接続されると、Sparse-HFS はスパース化されたグラフを使用しているにもかかわらず、Stable-HFS と同等の精度を達成しました。
  • 効率性: 最適な精度点（$k=4500$）において、スパースィファイア $H$ は元のグラフ $G$ のエッジの**約 10%**しか含んでいませんでしたが、同様の性能を維持しました。
• 結論: 近似誤差は十分に小さく、メモリと計算量の大幅な削減は最終的な分類精度に大きな影響を与えません。

5. 意義と今後の課題

• 意義: この研究は、理論的な SSL の保証と実用的な大規模展開の間のギャップを埋めています。スペクトルスパース化は単なる線形ソルバのツールではなく、メモリに収まらない大規模なグラフでの SSL を可能にする学習アルゴリズムとしての viable な戦略であることを実証しています。
• 限界: 現在の手法は挿入のみのストリームをサポートしています。エッジの削除（動的グラフ）の処理は容易ではありません。動的スパース化のための既存のスケーリング手法は、最終的な解を計算するために $O(n^2)$ の時間を必要とし、本論文の効率性制約に違反します。
• 今後の課題: 二次未満の計算複雑性を維持しながら、これらのスパース化技術を完全な動的設定（挿入と削除の両方を処理）に拡張することが、重要な未解決問題として特定されています。

要約すると、本論文はオンラインスペクトルスパース化を活用することで、大規模半教師あり学習のための厳密な枠組みを提供し、計算効率が高く理論的に健全な解決策を提示しています。