Preserving Personalized Pagerank in Subgraphs

Preserving Personalized Pagerank in Subgraphs

  • Andrea Vattani, Deepayan Chakrabarti, Maxim Gurevich
  • ICML 2011

概要

  • 既存のグラフサンプリングは、Sを計算して、G[S]を出力
    • 局所的な指標は良いけど、大域的な指標は駄目
    • S={u,v}だと、N(u)∩N(u)が大きくても、微妙になる
  • 辺を弄ってPPRを保持する問題
    • SINKを足すと上手く行く
    • 密になるので疎化

問題定式化と提案手法

  • 入力: $$ G=(V,w_G), S \subseteq V $$
  • 出力: $$ H=(S,w_H) $$
  • 目標: $$ \pi_i^H(j) = \pi_i^H(j) \forall i, j \in S $$
    • ※クラシカルにはH=G[S]で、PPRの値の差の最小化だが、これはNP-hard
  • 問題: (Gによっては)そんなHを作れないことがある
  • 解決法: SINKを作る
  • アルゴリズムNodeRemoval
    1. V-Sの頂点zを(適当な順で)削除
    2. $$ x, y \in N(z) $$について
    3. $$ w_H(x,y), w_H(x, \mathrm{sink}) $$を割り当てる
  • 利点: 厳密にPPRを保持する
  • 欠点: Sが小さい時に辺数がやばお
  • 解決法: 疎化
  • Weighted: wH(u,v)<τなら、(u,v)を消して(u,SINK)に割り振る
    • 理論的保証: 平均絶対誤差=O(τ)くらい
  • Unweighted: Weightedの結果の重みを無くす
  • グローバルPageRankの保持…SOURCEを作って頑張る(省略)

実験

  • 頂点部分集合Sの選択はSampling from Large Graphsの5手法
  • G[S]とUnweightedとWeightedを比較
    • NodeRemovalしただけの結果(疎化してない)は誤差=0なので無い
  • なんかいい感じらしいです?

まとめ

  • そこそこ良さそう?
  • 辺重みを自由に変えられるので自由度が高そう
  • 誤差がτなのは良いか分からん
    • τ毎の辺数・誤差の実験結果が欲しいですぅ

ICML PageRank 疎化

2016/12/12

タグ:

ICML PageRank 疎化
最終更新:2016年12月12日 19:22