リッジ・スペクトル・スパースィファイケーションによる大規模グラフ学習の改善

要旨: グラフベースの手法およびスペクトルグラフ理論は、機械学習分野における多様な重要な進展をもたらしてきました。解析における中心的対象は、グラフの構造を符号化するグラフラプラシアン L です。本研究では、分散ストリーミング設定において、このラプラシアン上で学習する問題を考えます。そこでは、グラフの新しい辺が、ワーカーのネットワークによってリアルタイムに観測されます。この設定では、L の分散表現を維持しながら、素早く、または近似的に学習することが困難です。こうした課題に対処するために、効果的抵抗の小さな部分集合を維持することで、ラプラシアンを効率的に疎化する新しいアルゴリズム GSQUEAK を提示します。我々のアルゴリズムは、単一パスで、かつ分散的に辺を処理しながら、強力なスペクトル近似の保証を満たす疎化器を生成することを示します。