Counting Triangles in Large Graphs using Randomized Matrix Trace Estimation - todo314 @ ウィキ

Counting Triangles in Large Graphs using Randomized Matrix Trace Estimation

• Haim Avron
  • IBM Research（っぽい？）
• COSN 2013

概要

• タイトルそのまんまの内容
• トレースを愚直に求めるのは難しいので、ランダムベクトルで挟んでいっぱい計算して平均をとる
• サンプル数は結構多いけど、実験的にはO(log^2|V|)個でよい
• 実験は微妙…

既存手法とか

• 簡単なアルゴリズム
  • Σdeg(v)^2で遅い
• 行列積とかで頑張る…O(|E|^1.41)
• 近似する場合…サンプリング
• Spectral counting
  • $$ \Delta(G) = \frac{1}{6}\mathrm{trace}(A^3) = \frac{1}{6}\sum_{i=1}^{n}\lambda_i^{3} $$
  • 元のグラフの固有値求めればいいのでよさげ
  • いくつ固有値求めればいいかよく分からん、データ依存なので辛い

提案手法

• 主な方針

1. M回以下を繰り返す
   • x: ランダムベクトル
   • y = Ax
   • T_i = y^TAy/6
2. Δ = ΣT_i/M

• Aは疎なので（当然）ベクトルとの積はO(|E|)でできる
  • 普通にやろうとするとA^3を計算しないといけなくて大変、挟み込んだことで速い
• ただし、各T_iの分散がかなり大きい、Chernoff boundを使っても…

1. アルゴリズムN
   • ベクトルの各要素を標準正規分布から抽出
2. アルゴリズムR
   • ベクトルの各要素をRademacher分布（±1が等確率）から抽出
   • ちょっと速いしちょっと良い？
3. アルゴリズムM
   • 適当に決めるのはよくないから、一個だけ特別視してDCTするようなベクトル
   • 一個だけっていうのをランダムに決める、ベクトルはn個しかない

• いくつサンプルをとればいいってのは実験からO(log^2|V|)でおk、とかいってる

実験

• 大体真の値の10%以内には収まっている？
• とおもいきや、全体の試行の60%程度しか10%以内に収まっていないのも…
• ただし、固有値を頑張って求めて計算するよりはよほど良い
• 固有値を求める場合の8倍位速い、最大で
  • 遅くなっているのもある(´・ω・`)

まとめ

• 普通っぽい
• 結構解析が長い
• 実験がう～ん
• 期待していた程の面白みは無かった
• K_3=C_3だが、K_4=C_4なので4の時は悲しい(´・ω・`)

COSN triangle

2013-12-18 23:08:43 (Wed)