Approximating the Spectrum of a Graph - todo314 @ ウィキ

Approximating the Spectrum of a Graph

• David Cohen-Steiner, Weihao Kong, Christian Sohler, Gregory Valiant
• KDD 2018

概要

• （正規化）Laplacianのスペクトラムが欲しい！
• $$ \exp(O(1/\epsilon)) $$時間：定数！！！
  • $$ \| \tilde{\mathbf{\lambda}} - \mathbf{\lambda} \|_1 \leq \epsilon|V| $$
• 性質検査的な話もあるよ！

提案手法

• 定数時間にしたいので、出力は[0,2]上の離散分布
  • $$ \epsilon|V|, 2\epsilon|V|, 3\epsilon|V| $$番目、の近似
  • なので、earth mover distanceで近似を測る
• 戦略
  • モーメントを求めたいよ！$$ \frac{1}{n} \sum_{i \in [n]} \lambda_i^{\ell} $$
    • これさえ分かれば元のものを復元できる
  • $$ Tr(A^i) = \sum_{i} \lambda^i = \sum_{i} \Pr[\text{i-step RW from j returns to j}] $$
  • ランダムにjを選び、$$\ell$$ステップ目でjに戻るかを見て繰り返せば良い（s回）
    • Hoeffding不等式の保証が得られる
• 分布の復元
  • 全体を1/ε刻みにして、得られたモーメントに対してそれっぽい線形計画を解く
  • さらに、線形時間かければ、n次元ベクトルに変換もできる
• 技術的には、、、
  • 上位モーメントから分布のWasserstein距離を抑える（既存）
  • 線形計画を解いた結果と真の分布のearth mover distance
  • 合わせて、どのくらいの試行回数が十分か？
    • ここで、$$ \ell = O(1/\epsilon) $$とか、$$ s = e^{1/\epsilon} $$とかになる

実験

• 設定は適当（定数パラメタがやばいので仕方がない）
• 10000回のRW、20次モーメントまで、を、20回平均取る
• 5分で終わった。

まとめ

• 性質検査が乗り込みつつある
• 解析は、異常に難しくはないかな？
• Wassersteinとかで測るのはアルゴリズム的にも流行るかな？

KDD スペクトラルグラフ理論 定数時間アルゴリズム

2018/08/05