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