A Fast and Provable Method for Estimating Clique Counts Using Turan's Theorem

A Fast and Provable Method for Estimating Clique Counts Using Turán's Theorem

  • Shweta Jain, C. Seshadhri
  • CoRR

概要

  • k-クリークの個数の数え上げ
  • サンプリングでの精度を上げるために、元のグラフをclique shadowと言うものに分解し、その上でサンプリング
  • shadowの良さをTuránの定理を使って与える←辺密度がある値以上
  • 構築はクリーク探索の再帰的アルゴリズムを途中打ち切り
  • shadowの大きさは上手くバウンドできないけど、実際的にはかなり小さく上手く行く

Turán's theorem

  • k-cliqueの密度 $$ \rho_k(G) := |C_k(G)|/{|V| \choose k} $$
  • 定理3.1 Turán
    • $$ \rho_2(H) > 1-\frac{1}{k-1} $$ならHはk-cliqueを含む
    • (k-1)-部グラフがタイトな例
  • 定理3.2 Erdős
    • t頂点グラフHについて、
    • $$ \rho_2(H) > 1-\frac{1}{k-1} $$ならHはk-cliqueを$$ (t/(k-1))^{k-1} $$個以上のk-cliqueを含む
  • 言い換え: $$ f(k)=k^{k-2}/k! $$とすると、$$ \rho_k(H) \geq 1/f(k)t^2 $$

Clique shadows

  • $$k$$-clique shadow $$ \mathbf{S} = \{ (S_i, \ell_i) \}_i $$
  • $C_k(G)$$と$$ \bigcup_{(S,\ell) \in \mathbf{S}}C_\ell(S) $$との間に全単射関係がある
    • multisetでも良い、$$(S,\ell)$$中の$$\ell$$-cliqueをかき集めると、G中のk-cliqueに対応する
  • $$\gamma$$-saturated: $$ \forall (S, \ell) \in \mathbf{S}, \rho_\ell(S) \geq \gamma $$
    • 密度が高いと嬉しい
  • $$ \textsf{sample}(\mathbf{S},\gamma,k,\epsilon,\delta) $$
    1. $$(S,\ell)$$ の確率分布$$\mathcal{D}$$ を $$ p(S) \propto {|S| \choose \ell} $$で定める
    2. $$ \frac{20}{\gamma \epsilon^2} \log \delta^{-1} $$回繰り返し
      • $$ (S,\ell) $$を標本、Sから$$\ell$$-tuple Aを標本、Aが$$\ell$$-クリークなら、カウントインクリメント
    3. カウントを適当に正規化し返す
    • 時間$$ O(\mathrm{size}(\mathbf{S}) + \frac{1}{\gamma \epsilon^2} \log \delta^{-1}) $$
    • $$\gamma$$-saturatedなら $$ (1 \pm \epsilon) $$-近似 w.p. $$1-\delta$$
  • $$\gamma$$-saturatedってどうやって確認するの?←Erdősの定理3.2
  • 定理4.4
    • $$ \rho_2(S) > 1-\frac{1}{\ell -1} $$なら、
    • $$ \gamma = 1/\max_{(S,\ell) \in \mathbf{S}}f(\ell) |S|^2 $$-saturated

Saturated clique shadowの構成

  • クリーク探索の伝統的なアルゴリズムを使う:
    • k-core分解な感じの向き付けをする
      • 出近傍は大抵小さい
    • (S内のk-cliqueの個数) = (S中の点sの出近傍$$N_s^+$$内の(k-1)-cliqueの個数)の和
      • 近傍は誘導部分グラフで考える
    • これを再帰的に実行する
  • 今回は、
    • $$ \mathbf{T} = \{(V,k)\} $$から始めて、
    • $$ \rho_2(N_s^+) > 1-\frac{1}{\ell-2} $$なら打ち切って、$$ \mathbf{S} $$に$$(N_s^+,\ell-1)$$を追加
    • そうでないなら、$$ \mathbf{T} $$に$$(N_s^+,\ell-1)$$を追加
    • ※$$ \mathbf{S} \cup \mathbf{T} $$は常にclique shadowで、$$ \mathbf{S} $$は常に$$\gamma$$-saturated
  • |S|がcore numberで抑えられるので、実行時間が$$ O(\alpha(G)\mathrm{size}(\mathbf{S})) $$と線形時間になる
  • size(S)は分からんが実際のグラフだと超小さい

実験

  • 短めだけど、一通り調べている
  • 誤差を小さく、既存手法を圧倒
  • shadowの大きさが大体グラフサイズに比例
  • クリーク数がkに応じて増えるグラフと減るグラフがある

まとめ

  • shadowの概念がかなり面白い
  • クリーク探索の再帰的アルゴリズムを知っていたら、確かにそうっぽい感じを受けるのだろうけど、
  • 打ち切る条件をTurán's theoremでKOOLに定めている
  • こういう普通のサンプリングが上手く行かないので、非自明な工夫をするのは面白い

クリーク サンプリング

2017/01/01

最終更新:2017年01月01日 19:25