秘密のリンク構造を持つグラフのリンク解析 筑波大学 システム情報工学研究科 佐久間淳 東京工業大学 総合理工学研究科 小林 重信

動機：秘密情報を含むネットワークでリンク解析はできないか？ リンク解析→ グラフのリンク構造からノードを重要度に応じてランキング Web文書解析において有名かつ有用 (spectral ranking) E.g., PageRank (Page et al.) これまでのリンク解析の対象は… 文書ネットワーク、文献引用関係、たんぱく質・DNA相互作用関係、etc… 人間関係や経済活動などの実社会ネットワークを対象にできないか？ 人・企業などの信頼度や実績に応じたランキング プライバシー・機密性などがボトルネックになる そうでもない まあまあ ランダムウォーク時の 状態遷移確率行列 定常分布密度でranking 重要 まあまあ そうでもない べき乗法： マルコフ連鎖の定常分布 x を求める まあまあ そうでもない

グラフにおけるプライバシー(1)： 取引グラフ 企業間取引: 企業iの企業jからの購入額は年間wij円 取引関係がリンクeij, 取引額が重みwijなる重み付きグラフG=(V,E,W) 企業iと企業jは取引eijを認識、それ以外の企業には取引eijの存在は秘密 企業iと企業jは取引額wijを認識、それ以外の企業には取引額wijは秘密

グラフにおけるプライバシー(2)： 通信グラフ 個人間の通話: iさんからjさんへの通話頻度はwij 通話関係がリンクeij, 通話頻度が重みwijなる重み付きグラフG=(V,E,W) iさんとjさんは通話eijを認識、それ以外の人には通話eijの存在は秘密 iさんだけが通話頻度wijを認識、jさんとそれ以外の人には通話頻度wijは秘密

グラフにおけるプライバシー(3)： 評価グラフ 人事評価: iさんからjさんへの評価はwij 評価関係がリンクeij, 評価が重みwijなる重み付きグラフG=(V,E,W) iさんだけが評価関係eijを認識、それ以外の人には評価eijの存在は秘密 iさんだけが評価wijを認識、jさんとそれ以外の人には評価wijは秘密

ネットワーク構造を持つ秘密情報のモデル化: 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

ネットワーク構造を持つ秘密情報のモデル化: 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

ネットワーク構造を持つ秘密情報のモデル化: Private Graph 取引グラフ リンク先・リンク元ともに情報を共有 　　　　↑ リンク構造の秘密性 　　↑ 重みの秘密性

ネットワーク構造を持つ秘密情報のモデル化: Private Graph 通話グラフ リンク先・リンク元ともにリンク情報を共有 　　　　↑ リンク構造の秘密性 　　↑ 重みの秘密性

ネットワーク構造を持つ秘密情報のモデル化: Private Graph 評価グラフ リンク元のみが情報を保持 　　　　↑ リンク構造の秘密性 　　↑ 重みの秘密性

ネットワーク構造を持つ秘密情報のモデル化: Private Graph 目標：private graphを違反せずにspectral rankingを行う

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に見せずに　　　　　　　　　　を更新したい

準同型公開鍵暗号: 値を見せずに足し算をする 整数m0,m1, ランダムな整数r0, r1について… 暗号化された値に対する和, 積が(解読プロセスなしに)実行可能 Bob, a, b Alice, x xに関する知識なしで, ax+bが評価できる 13 13

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に送信

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は上の更新式のかわりに

Link-awareモデルにおけるspectral ranking j cji j cji xjpji i xjpji Decentralized spectral ranking Link-awareモデルにおけるSpectral ranking

他のリンク解析法への拡張 Private graph上のPageRank: PrivateRank Private graph上のHITS: PrivateHITS

実験：比較対象 Link-aware model DSA(decentralized spectral analysis) [Kempe07] P2P上でspectral rankingを行うプロトコル SFE (secure function analysis) [Yao86] 任意の分散計算を安全に行うプロトコル PR (PrivateRank) 提案法

実験: Link-aware model SFE PR(提案法, 結託対性あり) PR(提案法, 結託対性なし) DSA

考察 DSA：計算は速いがプライバシ保護は完全ではない SFE: プライバシ保護は達成するが計算が重い 提案法(PR): プライバシ保護と計算効率性を両立

まとめ 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…