Path Sampling: A Fast and Provable Method for Estimating 4-Vertex Subgraph ...

Path Sampling: A Fast and Provable Method for Estimating 4-Vertex Subgraph Counts

  • Madhav Jha, C. Seshadhri, Ali Pinar
  • WWW 2015

概要

  • 数千万辺でも数十秒
  • 誤差1%以下
  • Chernoff boundからエラーバーも出せる

問題定義

  • 4-頂点部分グラフは6種類
    • 3-star, 3-path, tailed-triangle
    • 4-cycle, chordal-4-cycle, 4-clique
  • C_i: 誘導部分グラフにおけるi-th 部分グラフの出現個数
  • N_i: i-th 部分グラフの出現個数
  • (C_i)と(N_i)は簡単な線形関係にある
    • 特に各N_iは(C_i)から簡単に計算できる

3-path 標本

  • 一様無作為に3-pathを標本する
  • $$ \tau_{uv} = (d_u-1)(d_v-1) $$
  • W=Σ τ_e
  1. e=(u,v)を確率τ_e/Wで選択
  2. u' ← 一様無作為に選択した「v以外の」uの近傍
  3. v' ← 一様無作為に選択した「u以外の」vの近傍
  4. {(u',u),(u,v),(v,v')}を出力
  • u'-u-v-v'が3-path
  • 主張 3.1.
    • 各3-pathが出力される確率は1/W
      • ∵ Pr[(u,v)が選択]×Pr[u'が選択|(u,v)が選択]×Pr[v'が選択|(u,v)が選択]
      • = [(d_u-1)(d_v-1)/W]×[1/(d_u-1)]×[1/(d_v-1)] = 1/W
  • 3-star以外は3-pathを含むので,標本から推定できる
  1. k個標本
  2. 標本した部分グラフに応じてcount_2,…,count_6をインクリメント
  3. C'_2,…,C'_6をcountから計算
  4. C'_1をN_1とC'_2,…,C'_6から逆算
  • 定理 3.2.
    • $$ \mathbb{E}[\hat{C_i}] = C_i $$
  • Chernoff boundを適用すると,
  • k=O(1/ε^2)
  • $$ \Pr[|\hat{C_i}-C_i| > \epsilon W / A_{2,i}] < \delta $$ (2≦i≦6)
  • 良さそうじゃね,ともーじゃん?
  • 大体kは(W/C_i)^2欲しい→測ってみた
  • i=4,5,6だと(W/C_i)^2>10^8でやばめ
    • 4-cycleを含む4,5,6-th motifは精度が落ちる
    • C_iが全体の3-path数に比べてそれ程無いのが原因

Centered 3-pathによる4-cycle-basedを用いた推定

  • 実グラフの構造が影響する?
  • 次を満たす3-pathの集合Sが欲しい
    1. 全ての閉路ベースのmotifはある固定数の3-pathをSに含む
    2. Sからの一様無作為抽出が可能
    3. |S|<<W
  • さっきのは,uvについてN(u)×N(v)を標本してたがもっと枝刈りしたい
  • 頂点を次数順に整列して順序付ける
  • (u,v)を中心に
    • uの近傍: vより大きい
    • vの近傍: uより大きい
    • だけを見る,と次数が減る
  • centeredとは:
  • {(t,u),(u,v),(v,w)}についてv≺t, u≺w
  • 補題
    • 4-cycle,chordal-4-cycleは,centered 3-pathを1つだけ含む
    • 4-cliqueはcentered 3-pathを丁度3つ含む
  • 標本した3経路が中心で無いこともある
  • けど,ある中心3経路が標本される確率は1/Λ
  • λ_e=#(vより大きいuの近傍)×#(uより大きいvの近傍)
  • Λ=Σ λ_e

Centered 3-pathの効果

  • W→Λに減ったのが大きい
    • 実グラフだとW/Λは10~100
    • 自乗するとかなりデカイ
  • 3-path-sampler: C_1,C_2,C_3
  • centered-sampler: C_4,C_5,C_6

実験

  • k=200K
  • 誤差1%以下
  • 理論的なエラーバーも10%~5%以下

まとめ

  • いい話っぽい
  • n=5は考慮すべき部分グラフそのものが多いのでつらそう…

WWW モチーフ 数え上げ

2015/05/18 16:30

最終更新:2015年05月18日 16:34