Download presentation
Presentation is loading. Please wait.
1
秘密のリンク構造を持つグラフのリンク解析
筑波大学 システム情報工学研究科 佐久間淳 東京工業大学 総合理工学研究科 小林 重信
2
動機：秘密情報を含むネットワークでリンク解析はできないか？
リンク解析→ グラフのリンク構造からノードを重要度に応じてランキング Web文書解析において有名かつ有用 (spectral ranking) E.g., PageRank (Page et al.) これまでのリンク解析の対象は… 文書ネットワーク、文献引用関係、たんぱく質・DNA相互作用関係、etc… 人間関係や経済活動などの実社会ネットワークを対象にできないか？ 人・企業などの信頼度や実績に応じたランキング プライバシー・機密性などがボトルネックになる そうでもない まあまあ ランダムウォーク時の 状態遷移確率行列 定常分布密度でranking 重要 まあまあ そうでもない べき乗法： マルコフ連鎖の定常分布 x を求める まあまあ そうでもない
3
グラフにおけるプライバシー(1)： 取引グラフ
企業間取引: 企業iの企業jからの購入額は年間wij円 取引関係がリンクeij, 取引額が重みwijなる重み付きグラフG=(V,E,W) 企業iと企業jは取引eijを認識、それ以外の企業には取引eijの存在は秘密 企業iと企業jは取引額wijを認識、それ以外の企業には取引額wijは秘密
4
グラフにおけるプライバシー(2)： 通信グラフ
個人間の通話: iさんからjさんへの通話頻度はwij 通話関係がリンクeij, 通話頻度が重みwijなる重み付きグラフG=(V,E,W) iさんとjさんは通話eijを認識、それ以外の人には通話eijの存在は秘密 iさんだけが通話頻度wijを認識、jさんとそれ以外の人には通話頻度wijは秘密
5
グラフにおけるプライバシー(3)： 評価グラフ
人事評価: iさんからjさんへの評価はwij 評価関係がリンクeij, 評価が重みwijなる重み付きグラフG=(V,E,W) iさんだけが評価関係eijを認識、それ以外の人には評価eijの存在は秘密 iさんだけが評価wijを認識、jさんとそれ以外の人には評価wijは秘密
6
ネットワーク構造を持つ秘密情報のモデル化: Private Graph
Privately shared matrix M=(mij) n×n行列 行列Mをn個に分解し、n個のノードが各パーツを保持している 各ノードが保持しているパーツは他のノードには秘密 典型的な2パターンを想定 Row-private: ノードiはi行目のみを保持 Symmetrically-private: ノードiはi行目およびi列目を保持 Node 1 Node 2 Node n
7
ネットワーク構造を持つ秘密情報のモデル化: Private Graph
Privately shared matrix M=(mij) n×n行列 行列Mをn個に分解し、n個のノードが各パーツを保持している 各ノードが保持しているパーツは他のノードには秘密 典型的な2パターンを想定 Row-private: ノードiはi行目のみを保持 Symmetrically-private: ノードiはi行目およびi列目を保持 Node 1 Node 2 Node n
8
ネットワーク構造を持つ秘密情報のモデル化: Private Graph
取引グラフ リンク先・リンク元ともに情報を共有 ↑ リンク構造の秘密性 ↑ 重みの秘密性
9
ネットワーク構造を持つ秘密情報のモデル化: Private Graph
通話グラフ リンク先・リンク元ともにリンク情報を共有 ↑ リンク構造の秘密性 ↑ 重みの秘密性
10
ネットワーク構造を持つ秘密情報のモデル化: Private Graph
評価グラフ リンク元のみが情報を保持 ↑ リンク構造の秘密性 ↑ 重みの秘密性
11
ネットワーク構造を持つ秘密情報のモデル化: Private Graph
目標：private graphを違反せずにspectral rankingを行う
12
Decentralized Spectral Ranking
Node iに着目 j xjpji xjpji j xjpji i xjpji Node iは，被リンク先ノードからpjiを送信してもらい Private graphでは… xjpjiはnode iにvisibleではない Node jはPjiをnode iに見せずに を更新したい
13
準同型公開鍵暗号: 値を見せずに足し算をする
整数m0,m1, ランダムな整数r0, r1について… 暗号化された値に対する和, 積が(解読プロセスなしに)実行可能 Bob, a, b Alice, x xに関する知識なしで, ax+bが評価できる 13 13
14
Link-awareモデルにおけるspectral ranking
cji←Enc(xjpji) j cji←Enc(xjpji) j xjpji i xjpji Link-awareモデルにおけるSpectral ranking 1. Node iにリンクしているノード (node j )はcji←Enc(xjpji) を計算しnode iに送信
15
Link-awareモデルにおけるspectral ranking
j cji j cji xjpji i xjpji Link-awareモデルにおけるspectral ranking Node iにリンクしているノード (node j )はcji←Enc(xjpji) を計算しnode iに送信 2. Node iは上の更新式のかわりに
16
Link-awareモデルにおけるspectral ranking
j cji j cji xjpji i xjpji Decentralized spectral ranking Link-awareモデルにおけるSpectral ranking
17
他のリンク解析法への拡張 Private graph上のPageRank: PrivateRank
Private graph上のHITS: PrivateHITS
18
実験：比較対象 Link-aware model
DSA(decentralized spectral analysis) [Kempe07] P2P上でspectral rankingを行うプロトコル SFE (secure function analysis) [Yao86] 任意の分散計算を安全に行うプロトコル PR (PrivateRank) 提案法
19
実験: Link-aware model SFE PR(提案法, 結託対性あり) PR(提案法, 結託対性なし) DSA
20
考察 DSA：計算は速いがプライバシ保護は完全ではない SFE: プライバシ保護は達成するが計算が重い
提案法(PR): プライバシ保護と計算効率性を両立
21
まとめ Link-unawareモデル，結託耐性モデルについては下記参照,
J. Sakuma and S. Kobayashi, Link Analysis for Private Weighted Graph (SIGIR2009, to appear) ネットワーク構造を持つプライバシモデルとしてprivate graphを提案 Private weighted graphモデルにおけるリンク解析法を提案 プライバシ保護と計算効率性の両立を実現 今後の発展 Private graphの拡張：ラベルつきグラフ，二部グラフ Private graph上のさまざまな計算 リンク予測，ノードクラスタリング，ラベル予測， etc…
Similar presentations
