"Social Rank":節點重要度在網路表示學習中的影響

09-26

來自專欄 RUC智能情報站9 人贊了文章

引階論文：RaRE: Social Rank Regulated Large-scale Network Embedding. 原文鏈接

發表會議：WWW 2018

作者：Yupeng Gu, Yizhou Sun, Yanen Li, Yang Yang.

相關單位：University of California，Snapchat Inc，Zhejiang University

本知乎文章作者：陳俊華,來自中國人民大學大數據管理與分析方法研究北京市重點實驗室(BDAI)。學術型碩士研究生，研究方向為Network Embedding,Tag Recommendation等。

前言：本文在"節點相似度(proximity-based)高的節點更有可能存在直接相連邊"這一論斷基礎上，提出節點重要度(social rank-based)對於網路中生成邊概率的影響，並認為這兩個因素並不是相互獨立而是互相影響的。

一、寫作動機(背景)

到2018年為止，網路嵌入式表示學習(Network Embedding)已經從同質網路發展到大型異構網路學習，大型屬性網路學習。在眾多理論學習中，基本都默認地認定了一個假設：更相似的用戶直接相連的概率更高(nodes that are more similar will have higher probability to connect to each other)。而在現實網路中，往往並不是這樣。微博上有諸如何炅,謝娜這些粉絲過億的超級用戶，粉絲群體龐大，但與本人相似的節點可能相當稀少，但正是因為其強大的影響力使其粉絲數量不斷增長。因此，我們在思考2個節點是否相連的時候，不僅僅考慮到的是節點相似度差異，還要考慮節點重要度差異。

二、難點與創新

節點相似度與節點重要度是獨立的嗎？作者認為不是。當目標節點越受歡迎，它與源節點的相似度可能會更低；而當目標節點並非是重要節點時，它與源節點的相似性可能會更高。因此，需要探究這2個因素是如何依賴的。此外，這種方法應該如何擴展到邊數節點數巨大的現實網路，也是作者要解決的問題。

三、問題定義

信息網路(An information network)： $G=(V,E)$ , $V=left{ u_{n} ight}_{n=1}^{N}$ 為節點集合； $Esubset V^{2}$ 為邊集。 $e_{ij}$ 表示邊權，既可以是01無權邊,也可以是非負有權邊。目標是同時推出基於節點相似度的低維表示 $left{ z_{v} | vin V ight} subset R^{K}$ ,節點的重要度表示 $left{ r_{v} | vin V ight}subset R^{+}$ 。當節點越受歡迎， $r$ 值越低。

四、方法

核心就是研究對於 $i,j$ 兩個節點， $e_{ij}$ 是否存在的Bernoulli事件：

$p(e_{ij}=1 | r_{i},r_{j},z_{i},z_{j})=f(d_{r},d_{z})$ ， $d_{r},d_{z}$ 分別表示相似度差異和重要度差異。

根據貝葉斯規則，上式可以寫成：

equation(1)

其中 $f_{ij}$ 為：

equation(2)

所以現在需要得到的是 $p(dr|dz,e_{ij}=1(0)),p(dz|e_{ij}=1(0)),p(e_{ij}=1(0))$ 的概率分布。

本文中直接假定了2個高斯分布：

$p(dr|dz,e_{ij}=1)=N(mucdot h(dz),sigma_{R}^{2})$

$p(dz|e_{ij}=1)=frac{1}{Z} cdot I_{R}^{+}(dz)cdot N(0,sigma_{1}^{2})$

第一個是均值為正並依賴於 $dz$ 的高斯分布，第二個是 $dz>0$ 的截斷分布。

當 $e_{ij}=0$ 時，2個節點可能既不相似，也不存在重要度差異，因此第一個分布的均值變為0:

$p(dr|dz,e_{ij}=0)=N(0,sigma_{R}^{2})$

$p(dz|e_{ij}=0)=frac{1}{Z} cdot I_{R}^{+}(dz)cdot N(0,sigma_{2}^{2})$

綜合eq.1，eq.2以及上述2個概率分布，能夠得到 $f_{ij}$ 的最終表達式：

至此，得到了 $p(e_{ij}=1 | r_{i},r_{j},z_{i},z_{j})=f(d_{r},d_{z})$ 的最終優化函數。隨後採用隨機梯度上升(stochastic gradient ascent)的優化方法優化該函數。

五、實驗

5.1 數據集

作者選取了幾個現實世界的網路數據集：

Snapchat Friendship：美國的一款利用照片傳遞信息的社交網路。

Tencent Weibo Retweet：騰訊微博社交網路。

Venue Citation：論文引用網路。

Wikipedia Hyperlink：維基百科的頁面超鏈接網路。

Wikipedia Clickstream：維基百科點擊流網路。

數據集一覽

5.2 評測任務

5.2.1 Classification

BaseLine:

Matrix factorization(MF)
Graph Factorization (GF)
LINE
Node2vec

Metric:

Jaccard Index
Hamming Loss
F1 score

Results:

Multilabel classifcation results on Venue Citation dataset

Multilabel classifcation results on Wikipedia Hyperlink dataset

Multilabel classifcation results on Wikipedia Clickstream dataset

5.2.2 Link Prediction

BaseLine:

MF
GF
LINE(1st&2nd)
Node2vec
RaRE

Metric:

Result:

Link prediction AUC (%) on all datasets

5.2.3 Embedding as Additional Features for Classification & Novel Polar Coordinate-based Visualization

Gender prediction accuracy (%) on Snapchat dataset

Visualization on Venue Citation dataset. These plots are best viewed in color

六、筆者後記

本文亮點在於將節點的"Social Rank"第一次加入到邊的概率生成模型中，並認為"Social Rank"與"Social Proximity"相互依賴，由此引出 $e_{ij},dr,dz$ 三者的條件概率分布。"Social Rank"在現實網路中是必須要考慮的方面，區分普通節點和超級節點對於聚類,用戶畫像都有舉足輕重的作用。