Unsupervised Feature Selection in Signed Social Networks 閱讀筆記

02-02

轉載請註明出處：All Minable團隊的搬磚日常

論文來源：KDD 2017

論文鏈接：Unsupervised Feature Selection in Signed Social Networks

ABSTRACT

有符號的社交網路中存在正連接（positive links）和負連接（negative links），最近的一些研究指出，負連接具有一些正連接沒有的額外信息。因此，本文提出了一個基於有符號社交網路的無監督特徵選擇框架SignedFS，同時利用正連接和負連接來獲取網路特徵的潛在表達，從而實現更好的聚類效果。

INTRODUCTION

隨著在線社交網路的發展，產生數據的維度變得越來越大，這就給傳統的數據挖掘和機器學習演算法帶來了挑戰，因此需要進行降維操作，特徵選擇是一個比較常用並且有效的降維方法。

在社交網路中連接（links）和網路的特徵是緊密相關的，因此可以從links中提取網路的特徵。

真實世界中的社交網路包括正連接和負連接，如果兩個用戶中是正連接則可理解為他們是朋友，是比隨機的兩個用戶要更加相似，因此有很多現存的演算法利用正連接來進行特徵選擇。如果兩個是負連接，則可認為他們是敵人，他們之間的相似性比隨機兩個用戶的相似性低，這些信息也可以用來輔助特徵選擇。

真實的社交網路包括有符號的和無符號的。這篇論文針對的是有符號的社交網路。

這篇論文的主要動機是解決這兩個問題：

如何在有符號的應用現存的社交網路理論知識來進行特徵提取？
如何準確的運用正連接和負連接來進行特徵選擇？

基於剛剛那兩個選擇，作者的工作主要有以下四個貢獻：

證明了在有符號社交網路中用戶存在一階近似性及二階近似性；
提出了一個無監督的特徵選擇框架SignedFS，這個框架同時用了正連接和負連接來獲取網路的潛在特徵表達來進行特徵提取；
為這個框架提出了一個有效的演算法；
在兩個真實世界的數據集中進行實驗並取得很好的結果。

ANALYSIS OF SIGNED SOCIAL NETWORKS

Datasets

實驗採用的數據集均是來源於真實世界的數據：

Epinions：是一個消費者評價網，用戶可以在上面選擇商品評價，且可以選擇相信其他用戶和不相信其他用戶，商品標籤的ground truth是所有用戶多數選擇的種類。
Wiki-rfa：是維基百科選擇管理員的投票數據，用戶可以投只支持票也可以投反對票。

這個表格是兩個數據集更詳細的說明。

這是數據集的正連接和負連接的度分布，可以看到正連接負連接是比較均衡的。

Analysis

接下來是社交網路的一些理論知識，這些理論可以發現用戶間的相似性和用戶正連接，負連接交互的一些關係。例如：

相互吸引原則（Principle of homophily），指出了具有正連接的兩個用戶間的相似性是大於隨機兩個用戶的；
平衡理論（Balance theory），認為朋友的朋友是朋友，敵人的敵人是朋友。

先看一些定義，首先是兩個用戶之間的相似性分數定義：

$p_{1}$ 是具有正連接的用戶之間的相似性， $n_{1}$ 是具有正連接的用戶之間的相似性。

作者在這裡通過t-test驗證相吸原則和平衡理論，也就是一階近似和二階近似。這裡的顯著度是0.01，r是隨機兩個用戶之間的相似性，如表2：

從表2可以看出兩個數據在三個假設下的P值都是遠小於0.01的，因此就證明了在有符號的社交網路中是存在一階近似和二階近似的。

一階近似：具有正連接關係的兩個用戶之間的相似性是大於隨機兩個用戶之間的隨機性的；
二階近似：具有「朋友的朋友是朋友」和「敵人的敵人是朋友」的兩個用戶之間的相似性是大於隨機兩個用戶之間的隨機性的。

THE PROPOSED FRAMEWORK

首先是在有符號的社交網路中獲取正連接和負連接矩陣，然後分三階段進行，第一個階段計算用戶的潛在特徵表達，第二階段特徵選擇，第三階段進行歸一化處理。如下圖：

$c$

首先是第一階段，計算用戶的潛在特徵表達U：

利用正連接和負連接矩陣來求這個式子的最優解， $c$ 是用戶的潛在因子數目， $A^{p}$ 和 $A^{n}$ 是正連接和負連接的矩陣信息， $beta^{+}$ 和 $beta^{-}$ 是用來平衡正連接和負連接的因子， $V^{p}$ 和 $V^{n}$ 是從正連接和負連接信息中捕獲的相關信息，還有hadamard積是對應元素相乘。式子的前面部分是正連接後面是負連接，hadamard積是用來保證前一部分只提取了正連接信息和保證後一部分只提取了負連接信息。