メモ：What Is the Added Value of Negative Links in Online Social Networks?　WWW13

論文

What Is the Added Value of Negative Links in Online Social Networks?

signedネットワークについての論文
ネガティブリンクの特徴について調査．
ネガティブリンクとは‐＞foes…敵，distrust…不信
ネガティブリンクの予測をポジティブリンクだけを用いて行う．
高い正答率を出すのにネガティブリンクの特徴は不必要である！
また、新リンクの付加価値を評価する方法論について述べる
2つのソーシャルネットワークで評価し、結果として、中心性を
近接性を組み合わせたリンク予測モデルがよさそう．
また、ネガティブリンクの特徴は小さいが、付加価値の測定はできる
ことを示す．

ネットワーク1
Slashdot
ユーザによって作成される技術系のニュースサイト
ポジティブリンク…そのユーザの投稿を読みやすくなる
ネガティブリンク…そのユーザの投稿が表れにくくなる

ネットワーク2
Epinions
製品レビューサイト
ポジティブリンク…そのユーザのレビューが高いポジションに現れる
ネガティブリンク…そのユーザの投稿が自分から閲覧できなくなる

どっちもネガティブリンクが少ない（2割くらい）

・特徴と分析

一般的なリンク予測モデル（生成モデル）で使われる優先選択と高クラスタ係数の特性を利用する．
優先選択…PageRank，次数
高クラスタ係数…ノード間の近接性、すなわち共通隣接ノードやコサイン類似度

任意のユーザ間のPR値とコサイン類似度を定義

ネットワークを分割
Positiveを3：1になるようにランダムサンプリング
P_A、P_B、N、Oを定義…Nはネガティブ、Oはもともとエッジがないノードペアで、
P_Bと同じ大きさに設定

P_B、N、OのPRとコサイン類似度をP_Aを基盤にして測定
特徴として
・Oはコサイン類似度0かつPR値が非常に小さい
・Nは非0の非常に小さいコサイン類似度でOに比べると高いPR値
・P_Bは高いコサイン類似度とOに比べると高いPR値

・モデル検討
問題として、ポジティブリンク集合からネガティブリンクを予測していく．

設定として、トレーニングデータ用のリンク集合、予測用の真のリンク集合
くわえてどちらにも属さない偽のリンク集合

・近接性ベースの予測関数
コサイン類似度
iとjの間の長さ2のパスの数（実際にはノードの数で、CNN風の考え）
長さ3のパスの数（仲介リンク(k,l)の本数）
Jaccard係数
Adamic-Adar数
指数的グラフカーネル（隣接行列を使用）
ニューマングラフカーネル

・中心性ベース関数
PageRank
ノードi,jの次数の掛け合わせ

・評価手法
AUC…Area under the curve
ROC曲線化の面積，U検定，うまくいけば１、ランダムなら0.5
ROC…Receiver Operating Characteristic
分割ポイントを変えながら、真偽の割合をプロットする

※分割サイズに対して頑健だから選んだ

2つの実験
1．分類精度向上に貢献しそうな特徴量を探す

ポジティブエッジを2分割して、片方（75％）をテストデータ
3つのタイプの精度評価

①ネガティブかポジティブか
②ネガティブリンクかリンクなしか
②ネガティブか、ポジティブorリンクなしか



2．実際に予測してみる

ネガティブリンクも3対1の割合で2分割
ネガティブリンクを学習した場合にどれくらい精度が上がるか

2つのタイプの精度評価
①ポジティブリンクを学習して、ネガティブか、ポジティブorリンクなしか
②ポジティブandネガティブを学習して、ネガティブか、ポジティブorリンクなしか

※次数に関して修正
これまではポジティブリンクとネガティブリンクでつながった隣接ノードも
加算していたが、一致した隣接ノードしか加算しないようにする

・アンサンブル学習
中心性と近接性を組み合わせる
それぞれの特徴量をロジステック回帰に組み込む．特徴量が0になる場合、
他の特徴量で代用したり、非常に小さな値で代用する．

ほぼ同じ役割を果たす特徴量はまとめる（近接ノード数とAdamic-Adarスコアなど）
2つ用意
・全部盛り
・PRとCosine
比較として、それぞれの特徴量のみで予測も入れる

近似は最小二乗法．この回帰式は主に実験1でしか使わない（？）

実験1結果
①ネガティブかポジティブか、はうまくリンクの予測ができているが（AUC>0.5）
②ネガティブか、ポジティブorリンクなしかについてはほとんどの特徴量でダメ（AUC<0.5）
ところが、PRとCosineをアンサンブルした回帰はどのパターンでもそこそこの精度
で予測がうまくいっている．この特徴量が最もよさそうだ．


実験2結果

学習データにネガティブリンクを加えてもほとんど精度向上に効果はない（AUCで0.05程度）．
とはいえ、価値自体は小さいかもしれないが、ネガティブリンクの許容がソーシャルネット
ワークに付加価値を与えることは間違いないだろう．

                • -

リンク予測はなかなか精度上がらないで有名だけど、Signed Networkのリンク予測は新規だったのか、既存との比較的なものはなかった．
Signed Networkといえば、東工大の村田先生の研究室でコミュニティ抽出をやっていた気がする．
基本的に全部盛りすると良くなるような勝手なイメージがあったけど、今回はPR＋Cosineが最もよいということで、それはそれで面白かった．
こういう風に論文読みながら名前しかしらない手法の勉強をしていくのがあっていそうな気がしてきた．