Path Sampling : A Fast and Provable Method for Estimating 4-Vertex Subgraph Counts (WWW '15)

Jha, Madhav Seshadhri, C. Pinar, Ali

概要

名前の通りパスをランダムサンプリングして４頂点の連結部分グラフの個数を近似計算するという論文。３頂点の連結部分グラフ（パスまたは三角形）の個数はグラフの構造を調べるのに役立ちデータマイニングなどに応用がある。Uganderら(WWW '13)によって、４頂点の連結部分グラフの個数を調べることでグラフの面白い性質を調べることが示された。

４頂点の連結部分グラフは組み合わせ爆発によって非常に大きくなるため厳密に計算しようとすると現実のグラフでは数日かかってしまう。この論文では長さ３のパスをサンプルしパス上の４頂点から誘導される部分グラフの個数を数えることで、各連結部分グラフのunbiased estimatorを得る。Chernoff boundによって近似率に対する保証を得ることができ、degeneracy orderingを用いた枝刈りによってさらに良い精度を得ることができる（？イントロだけだとよくわからない）。

実験結果により使用した全てのグラフにおいて相対誤差が1%に収まっていることが示された。Orkut (約２億辺）のグラフにおける計算が１分以内に終了するので非常に高速である。

感想

各個数の絶対値が大きくなるおかげでChernoff boundと相性が良さそう。部分グラフの各サンプルは簡単に行えるので、良いサンプリング手法さえ考えられれば大勝利感がある。