Outlier Detection in Graph Streams

Outlier Detection in Graph Streams

  • Charu C. Aggarwal, Yuchen Zhao, Philip S. Yu
    • AggarwalはIBM Research
  • ICDE 2011

概要

  • タイトルのまんま
  • 問題としては初出なので、ちゃんとした比較対象はない
  • outlierって何?
    • 互いに異なるコミュニティに属する人々がつながった!
    • 異分野の人たちが共著するとか
    • 興味深い!
  • グラフでかいし難しい!
    • ちょっとだけ持つよ!

モデリング

  • ※辺がどんどんくるストリームモデルを想定
  • C = C_1,…C_kはVの分割
    • 理想はコミュニティに分割
  • p_ij(C): C_iとC_jの間に辺が張られる確率
  • 辺ijの尤度: p_I(i,C),I(j,C)
    • Iはiの属する分割のインデックス
  • 1個じゃやばい!ロバストじゃない!一杯分割を用意する
  • 合成尤度: MF(i,j,C_1,…C_r) = median{p_I(i,C_1),I(j,C_1), p_I(i,C_r),I(j,C_r)}
    • r個の分割についてのmedian
  • グラフの尤度: GF(G,C_1,…,C_r) = [Π_{(i,j)}MF(i,j,C_1,…,C_r)]^{1/|G|}
  • pはどうやって見積もるの?
  1. non-sample estimated p_ij^n: iとjの属する分割のサイズの積で重み付け
  2. sample-estimated p_ij^s: 分割iとjの間にある辺の割合
  3. estimated: p_ij(C_m) = λp_ij^n(C_m) + (1-λ)p_ij^s(C_m)
  • 別にこのへんの計算は動的に更新できる

サンプリング

  • 密なクラスタに分割したいね
  • 単調な集合関数がキーらしい
    • 連結成分の数: 単調非増加
    • 最大の連結成分のサイズ: 単調非減少
  • f: 最大の連結成分のサイズとする
  • ランダムにしたいので、辺にハッシュ関数をかませる
  • 適当な閾値使ってfがそれ以上になったら、ちまちま分割の数を増やす感じ?
  • 割りと適当に見えるが多分気のせい

実験

  • GOutlier: Graph Stream Outlier Detection Method
  • 比較手法がないので、GMicroとか言うのを使う
  • データセットはDBLPとInternet Movie Database Data Setと合成
  • 評価基準
    • False Positive Rate
    • False Negative Rate
  • 実際のグラフは面白い結果が出るよ
  • 合成は答えが分かっているので比較
    • 悪くはない
    • 時間とかもまあ普通

まとめ

  • 飛ばして読んだので良く分からん
  • これは評価すんの難しいなあと思った
  • Charu C. Aggarwalはよく見る気がする

ICDE outlier streaming algorithm

2014-01-07 00:07:59 (Tue)

最終更新:2014年01月07日 00:07