「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
++ V-Sの頂点zを（適当な順で）削除
++ $$ x, y \in N(z) $$について
++ $$ w_H(x,y), w_H(x, \mathsc{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なので無い
- なんかいい感じらしいです？
* まとめ
- そこそこ良さそう？
- 辺重みを自由に変えられるので自由度が高そう
- 誤差がτなのは良いか分からん
-- τ毎の辺数・誤差の実験結果が欲しいですぅ
&tags()
2016/12/12
* 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
++ V-Sの頂点zを（適当な順で）削除
++ $$ x, y \in N(z) $$について
++ $$ 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なので無い
- なんかいい感じらしいです？
* まとめ
- そこそこ良さそう？
- 辺重みを自由に変えられるので自由度が高そう
- 誤差がτなのは良いか分からん
-- τ毎の辺数・誤差の実験結果が欲しいですぅ
&tags()
2016/12/12
