Clustering Large Probabilistic Graphs

Clustering Large Probabilistic Graphs

  • George Kollios, Michalis Potamias, Evimaria Terzi
  • TKDE 2013

概要

  • Uncertain graphのクラスタリング
  • 編集距離ベースの目的関数
  • Correlation Clusteringと同じになる
  • その他自明な拡張

問題定義+提案手法

pClusterEdit

  • クラスタグラフ: (Gと同じ頂点集合を持つ、)互いに素なクリークの和集合
  • 期待編集距離: 「Gからサンプルした部分グラフ」と「クラスタグラフ」の(辺の意味での)編集距離の期待値
    • 辺毎に考えれば良く、クラスタグラフに辺が無い→p(e)/有る→1-p(e)
  • これはCorrelation Clusteringですね

提案手法

  • pKwikCluster
    • STOC '05の手法を適用すれば線形時間5近似算法
    • ClusterEdit問題(Discrete Applied Mathematics '04)の近似可能性を解決したと主張しているが何だかなあ…
  • Furthest…top-down
    • 全体を一つのクラスタと見做す
    • 遠い二頂点を選び、それらを中心とするクラスタに分割
    • 十分小さくなるまで繰り返し、一番良かったものを返す
    • O(nk^2)時間
  • Agglomerative…bottom-up
    • 逆に併合していく
    • O(knlogn)時間

p2ClusterEdit

  • クラスタグラフは決定的だった
  • (α,β)-クラスタグラフ: Pr[クリーク内の辺が存在]=α、Pr[クリーク間の辺が存在]=β
    • (1,0)は今までの決定的な奴
  • (α,1-α)が与えられた下で最小化
    • 期待編集距離はクラスタグラフも確率的な設定で自然に考えられる
  • 辺毎に考えれば良いので、結局pClusterEditに出来る
  • 最適なαを決めたい: α=0/1が最適値をとる∵αについて線形だから

p3ClusterEdit

  • 自明な事だけ
  • (α,β)が与えられた下で最小化
  • 最適な(α,β)を決めたい: (0,0),(0,1),(1,0),(1,1)のどれかが最適値をとる
    • 最適な(α,β)を見ると知見が多少は得られる

実験

  • ノーコメント(普通)

まとめ

  • コレ本当にTKDEに通ったの?
    • 新しい事が特に無いし、typoが多すぎてビビる
  • 問題定義が実際には逆で、Correlation Clusteringになるように、クラスタグラフだとか編集距離だとかを考えたのだと思う
  • 全体的に自明過ぎる
  • 定数近似線形時間算法があるのに、他のヒューリスティクスを提案する意味が分からない

TKDE uncertain graphs クラスタリング

2016/12/04

最終更新:2016年12月04日 01:38