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)は簡単な線形関係にある
3-path 標本
-
一様無作為に3-pathを標本する
-
$$ \tau_{uv} = (d_u-1)(d_v-1) $$
-
W=Σ τ_e
-
e=(u,v)を確率τ_e/Wで選択
-
u' ← 一様無作為に選択した「v以外の」uの近傍
-
v' ← 一様無作為に選択した「u以外の」vの近傍
-
{(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を含むので,標本から推定できる
-
k個標本
-
標本した部分グラフに応じてcount_2,…,count_6をインクリメント
-
C'_2,…,C'_6をcountから計算
-
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が欲しい
-
全ての閉路ベースのmotifはある固定数の3-pathをSに含む
-
Sからの一様無作為抽出が可能
-
|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