On the Hardness of Graph Anonymization - todo314 @ ウィキ

On the Hardness of Graph Anonymization

• Charu C. Aggarwal, Yao Li, Philip S. Yu
• ICDM 2011

概要

• 匿名化手法は色々あるけど、ランダムに辺を追加削除するだけはヤバイ！
• これを理論的に示す
• 特にソーシャルネットワークはmassiveかるsparseでこれが効いてくるらしい
• perturbation（摂動）に対してロバストなパラメータがある
• ↑を元にした手法を作り実験

Linkage Covariance

• $$ LinkCov(p,q) = \sum_{i}x_{pi}x_{qi}/n - \sum_{i}x_{pi}/n \sum_{j}x_{qj}/N $$
• ロバスト性
• 確率f_aで辺を追加するとLinkCov(p,q)は期待値で 2m_{pq}f_a/n 下がる
• 確率f_dで辺を削除するとLinkCov(p,q)は期待値で LinkCov(p,q)(1-2f_d) になる
  • m_{pq}はpとqの共通近傍数

非匿名化手法

• ↑のパラメータを使ってマッチングっぽいことをする
• よく分からん

実験

• 評価基準
  • Distance perturbation: 距離の変化みたいなのを見る？
  • Node re-identification rate: どの位の確率で暴かれたか
• 結構グラフを変化させないとヤバイ暴かれる
• しかも変化させると1つのパラメータがどんどん上がっていってつらい

まとめ

• とりあえず本質的に匿名化は難しいということらしい
• 本当はもっと色々な防御策に対応するべきだけど、
• 今のところ提案されているアドホック防御策はそんなに役に立たなさそうなことが分かった

ICDM anonymization

2014-02-02 21:18:54 (Sun)