技術要約: SLeDGe – グラフ構造学習を用いたデータストリームにおける半教師あり学習

1. 問題定義

本論文は、データストリームにおける半教師あり学習 (Semi-Supervised Learning: SSL) の課題に取り組んでいる。この設定では、データが高ボリュームで逐次的に（$D = \{x_t\}_{t=1}^T$）到着し、学習器は以下の2つの厳しい制約の下で動作しなければならない：

1. メモリ制約: システムには固定された限定的なメモリ容量 ($M$) があり、ストリームの全履歴を保存することはできない。
2. ラベルの希少性: 到着するサンプルのごくわずかな割合にしか観測されたラベル ($y_t$) が存在しないため、従来の教師あり学習は実行不可能である。

既存のストリーム向けSSL手法は、サンプルを独立したものとして扱ったり、固定された類似性ヒューリスティック（進化する関係性を捉えることができない）に依存したり、あるいは静的なオフラインデータセットを想定したりしているため、失敗することが多い。核心となる問題は、限られたラベルによる監督をいかに効果的にラベルなしサンプルへと伝播させ、時間の経過とともに進化するデータ分布および関係性に適応させるかである。

2. 手法: SLeDGe

著者らは、予測モデルと適応的なグラフ構造を共同で学習するフレームワークである SLeDGe (Semi-supervised Learning on Data Stream with Graph structure learning) を提案している。この手法は、流入する各サンプル $x_t$ に対して、以下の3つの連続したステージで動作する。

A. 二重メモリ更新メカニズム

迅速な適応（可塑性/Plasticity）の必要性と、歴史的な一貫性の保持（安定性/Stability）の必要性のバランスをとるために、SLeDGeは2つの異なるコンパクトなメモリバッファを維持する：

• ラベル付きメモリ ($M_L$): 可塑性に最適化されている。各クラスのプロトタイプを格納する。新しいラベル付きサンプルが到着すると、空のスロットを埋めるか、あるいは最も類似した既存のプロトタイプを重み付き結合によって更新する。更新重み $\alpha$ は動的であり、新しい特徴の迅速な統合を促進するために、新しい入力を優先する。
• ラベルなしメモリ ($M_U$): 安定性に最適化されている。代表的なラベルなしプロトタイプを格納する。ここでの更新には、ラベルなしデータの不確実性を反映し、情報の漸進的な蓄積を確実にするために、既存のプロトタイプを優先する重み $\beta$ を使用する。

B. 動的なグラフ構造学習 (GSL)

固定されたグラフや静的な類似性指標を使用する代わりに、SLeDGeは、メモリ ($M_L \cup M_U$) と現在のサンプル $x_t$ に対して、各タイムステップで動的にグラフを構築する。

1. 埋め込み ($f_E$): 多層パーセプトロン (MLP) が入力特徴量を潜在空間に写像する。
2. スコアリング ($f_S$): スコアリング関数（コサイン類似度）が、メモリ内の全ノードと現在のサンプルの間のペアワイズな関係の重みを計算し、密な隣接行列を生成する。
3. プルーニング ($f_P$): 効率性を確保するため、密な行列は各ノードにつき上位 $k$ 個の接続のみを保持するようにプルーニングされ、結果として疎な隣接行列 $A_t$ が得られる。
4. 分類 ($f_B$): グラフ畳み込みネットワーク (GCN) スタイルのバックボーンが、学習されたグラフ構造 $A_t$ を通じて監督情報を伝播させ、予測を生成する。

C. モデルの最適化

モデルは、以下の複合損失関数を用いて更新される：

• 教師あり損失 ($L_L$): ラベル付きメモリ上で計算されるクロスエントロピー損失であり、直近のサンプルを優先するために時間的減衰係数によって重み付けされる。
• 構造的正則化 ($L_{reg}$): 入力空間におけるペアワイズな類似性と潜在空間における類似性の間の一貫性を促す項。これにより、動的なグラフ推論が安定し、グラフ構造が不安定になるのを防ぐ。

D. 軽量版: SLeDGe-L

メモリサイズ $M$ が大きい場合にグラフ構築の二次時間計算量 ($O(M^2)$) が発生することを解決するため、著者らは SLeDGe-L を提案している。このバリアントは、グラフのスコアリングをクラス中心のアプローチに制限し、ラベル付きプロトタイプとすべてのメモリサンプル間の類似性のみを計算する。これにより、計算量は $M$ に対して線形 ($O(c \cdot M)$) に削減される（ここで $c$ はクラス数）。

3. 主な貢献

1. 適応的なグラフ構造: 固定されたグラフに依存する従来のストリーム向けSSL手法とは異なり、SLeDGeはデータのストリームと共に進化する動的なグラフトポロジーを学習し、時間とともに変化するサンプル間の依存関係を捉える。
2. 二重戦略メモリ管理: ラベル付き（可塑性重視）とラベルなし（安定性重視）のメモリに対して異なる更新戦略を導入することで、新しい特徴への適応と歴史的な知識の保持のバランスをとることを可能にした。
3. 制約下での効率性: 本フレームワークは、厳格なメモリ予算と極端なラベルの希少性（ラベル率 0.1% まで）の下で動作するように設計されており、疎なグラフプルーニングと軽量版 (SLeDGe-L) を通じて計算効率を維持している。
4. 構造的正則化: 一貫性正則化項の導入により、学習されたグラフ構造がストリーミングプロセス中に安定し、意味のあるものとなることを保証している。

4. 実験結果

著者らは、ウェブ、画像、テーブルデータのドメインにわたる 12のデータセット で SLeDGe を評価した。

• 性能: SLeDGeは、すべてのデータセットにおいて最先端の競合手法 (TLP, ReSSL, HDSSL) を上回った。
  • 0.1% のラベルにおいて、最強のベースラインに対して平均 31.7% の相対的な精度向上を達成した。
  • 1.0% のラベルにおいて、平均 14.8% の相対的な精度向上を達成した。
• アブレーション研究: メモリモジュールと動的グラフ構造の両方が極めて重要であることを実験で確認した。動的グラフを削除（静的な k-NN グラフへ回帰）すると、性能が著しく低下し、進化する関係性を学習する必要性が検証された。
• スケーラビリティ: 本手法は、データストリームのサイズに対して線形にスケールすることを示している（サンプルあたりの定数時間）。SLeDGe-Lは、フルバージョンと比較してメモリバッファサイズに対して優れたスケーラビリティを示し、理論的な計算量分析を裏付けた。
• 速度: ディープラーニングモデルであるにもかかわらず、SLeDGeは、特に高次元データにおいて埋め込みレベルの計算を活用することで、クラスタリングベースの手法に対して競争力のある実行時間を実現した。

5. 意義と主張

本論文は、メモリとラベルが厳しく制約されている環境において、グラフ構造学習 (GSL) をストリーミング設定で実現することにより、既存文献の重要なギャップを埋めるものであると主張している。著者らは、既存の手法はサンプル間の関係が時間の経過とともにどのように進化するかをモデル化できないために失敗すると述べている。予測モデルとグラフ構造を共同で学習することにより、SLeDGeは限られた監督情報をラベルなしデータへと効果的に伝播させ、データ履歴の全保存を必要とせずに大幅な精度向上を達成する。この研究は、非定常なデータストリーム環境において、動的なグラフ推論が静的な類似性尺度よりも優れていることを強調している。