《Link Prediction with Personalized Social Influence》论文解读

论文：Huo, Zepeng, Xiao Huang, and Xia Hu. "Link Prediction with Personalized Social Influence." (2018).

1. Motivation

先思考几个问题

已知一个微博用户今天的活动记录（转发、评论、点赞等），能否预测其明天的活动情况？
假设该用户追星，而且其偶像的每一条微博他都会转发评论，那么对其明天的活动情况的预测是不是会更容易？
为什么更容易了？因为该用户的偶像对他有影响，这种影响降低了预测该用户活动的随机性，于是预测就更容易。
那么如果给出了所有用户的活动记录，是不是能够反推出用户间的相互影响力，进而更精确地对用户和网络建模表示，从而提高链接预测等应用的精确度。

那么接下来的问题是怎么由活动记录反推影响力。

1.1 由活动记录反推影响力

『已知用户 (u_i) 的活动记录，预测其明天的活动情况』与『已知用户偶像 (u_j) 和该用户 (u_i) 的活动记录，预测其明天的活动情况』，两个预测的不确定性之间，相差的就是偶像 (u_j) 对该用户 (u_i) 的影响。
那么怎么衡量这种不确定性？信息熵。熵在信息论中代表随机变量不确定度的度量。下面这个是信息熵的公式。

[H(mathbf{X})=-sumlimits_{xin mathcal{X}} p(x)log p(x) ]

2. 问题定义

现在来定义一下要解决的问题。

令 (mathcal{G}=left{mathcal{U},mathcal{E} ight}) 表示网络，其中 (mathcal{U}={u_1,u_2,ldots,u_N}) 表示 (N) 个用户组成的集合，(mathcal{E}subseteq mathcal{U imes U}) 为边集合。令 (mathcal{A}) 表示活动时间戳集合，(mathcal{A}^{(i)}=left{t_{i,1},t_{i,2},ldots ight}) 表示用户 (u_i) 的活动时间戳序列。

本文中的链接预测问题为：给定 (mathcal{G}) 和 (mathcal{A})，预测任意用户 (u_i) 到用户 (u_j) 有边的概率。

本文希望对于每个用户 (u_i) 能学习到两个向量 (S_i) 和 (T_i) ，分别为该用户作为边起点和边终点的表示。作为边起点时，用户对其他用户产生影响；作为终点时，该用户受其他用户的影响。最终，任意用户 (u_i) 和 (u_j) 有边的概率可通过 (S_iT_j) 表示。

3. 社交影响力度量

先解决上面说的度量社交影响力的问题，即借用信息熵由活动记录反推影响力。

3.1 时间序列建模

定义用户 (u_i) 的时间片大小为 (Delta t^i=(t_{max}-t_{min})/M)，从而将用户 (u_i) 的活动时间划分为 (M) 段。

定义任意用户 (u_x) 在第 (m) 段的活动频度为 (A_{x,m}^{(i)})。

则对用户 (u_i) 来说，时间戳序列集合 (mathcal{A}) 被转化为一个矩阵 (A^{(i)}in mathbb{R}^{N imes M})。

于是，我们将有 (N) 个不同的矩阵，即 (left{A^{(i)} ight}, ext{for} i=1,2,ldots,N)
下图为对这 (N) 个矩阵的一种具象的表示。

3.2 影响力度量

考虑边 ((i,j))，用户 (u_i) 关注 (u_j)，则 (u_j) 对 (u_i) 产生影响。在矩阵 (A^{(i)}) 上计算用户 (u_j) 对 (u_i) 的影响力如下：

将 (A^{(i)}_i) 视为马尔可夫链，即可由 (A^{(i)}_{i,m}) 预测 (A_{i,m+1}^{(i)})，则可定义用户 (u_i) 在 (m+1) 段活跃的概率为

[P(A_{i,m+1}^{(i)} eq 0mid A_{i,m}^{(i)}) ]

则可得一个分布

[p_1=left{P(A_{i,m+1}^{(i)} eq 0mid A_{i,m}^{(i)}) ight}, ext{for} m=1,ldots,M-1 ]

该分布表达在不知 (u_j) 影响的前提下，对 (u_i) 活跃度预测的不确定性。
2. 类似可得分布

[p_2=left{P(A_{i,m+1}^{(i)} eq 0mid A_{i,m}^{(i)},A_{j,m}^{(i)}) ight}, ext{for} m=1,ldots,M-1 ]

该分布表达在已知 (u_j) 活动记录和 (u_i) 活动记录前提下，对 (u_i) 活跃度预测的不确定性。

于是可将两分布的熵之差视作 (u_j) 对 (u_i) 影响的度量：

[egin{align*} I_{j o i} & riangleq H(p_1)-H(p_2) \\ &=-sumlimits_{m=1}^{M-1} P(A_{i,m+1}^{(i)} eq 0 mid A_{i,m}^{(i)}) log P(A_{i,m+1}^{(i)} eq 0mid A_{i,m}^{(i)}) \\ & +sumlimits_{m=1}^{M-1}P(A_{i,m+1}^{(i)} eq 0mid A_{i,m}^{(i)},A_{j,m}^{(i)})log P(A_{i,m+1}^{(i)} eq 0mid A_{i,m}^{(i)},A_{j,m}^{(i)})\\ end{align*} ]

3.3 (p_1) 和 (p_2) 的计算

(p_1) 是通过 Logistic 回归计算的：

[P(A_{i,m+1}^{(i)} eq 0mid A_{i,m}^{(i)})={frac{1}{1+e^{-alpha_0-alpha_1f(A_{i,m}^{(i)})}}} ]

其中 (alpha_0) 和 (alpha_1) 是通过学习得到的。
学习过程的输入为 (left{A_{i,1}^{(i)},A_{i,2}^{(i)},ldots,A_{i,M-1}^{(i)} ight})，对应 label 为 (left{ ext{sgn}(A_{i,2}^{(i)}), ext{sgn}(A_{i,3}^{(i)}),ldots, ext{sgn}(A_{i,M}^{(i)}) ight})。

其中 (f(x)=egin{cases} x,& ext{if} xleq 2,\ 1+lceillog(1+x) ceil, &o/w. \ end{cases})，是为保证更符合现实情况，如某个用户在短时间内发了大量微博，其他用户并不一定每一条都看到。

类似地，(p_2) 可如下计算：

[P(A_{i,m+1}^{(i)} eq 0mid A_{i,m}^{(i)},A_{j,m}^{(i)})=frac{1}{1+e^{-alpha_0-alpha_1 f(A_{i,m}^{(i)})-alpha_2 f(A_{i,m}^{(i)})}} ]

4. 社交影响力 + 网络结构

如果在保持网络结构的基础上，边的强度与边两端节点的影响力成正比，这样学习到的表示就能够更有效地利用网络中的信息。
定义 (u_i) 到 (u_j) 有边的概率为

[hat{p}(u_jmid u_i)=I_{j o i}/d_i^{ ext{out}} ]

其中 (d_i^{ ext{out}}=sum_{(i,n)in mathcal{E}}I_{n o j})。
再定义由节点向量表示计算 (u_i) 到 (u_j) 有边的概率为

[p(u_jmid u_i)=frac{e^{S_i T_j^ op}}{sum_{n=1}^N e^{S_i T_n^ op}} ]

于是，将目标函数设置为最小化两者的 KL 散度即可：

[egin{align*} ext{min} mathcal{J}_1&=sumlimits_{(i,j)inhat{mathcal{E}}} d_i^{out}D_{KL}(hat{p}(u_jmid u_i)lVert p(u_jmid u_i))\\ &=-sumlimits_{(i,j)inhat{mathcal{E}}}I_{j o i}log p(u_jmid u_i)+cfrac{I_{j o i}}{d_i^{out}}log cfrac{I_{j o i}}{d_i^{out}} end{align*} ]

去掉常数项得：

[ ext{max} hat{mathcal{J}_1}=sumlimits_{(i,j)inhat{mathcal{E}}} I_{j o i} log p(u_jmid u_i) ]

4.1 负采样

通过定义新的条件概率区别正负样本：

[p(u_j > u_nmid u_i)=sigma(S_iT_j^ op-S_iT_n^ op) ]

则目标函数为：

[ ext{max} mathcal{J}_2=sumlimits_{(i,j)inhat{mathcal{E} } }I_{j o i} sumlimits_{u_nin mathcal{U}ackslash j} logsigma(S_i T_j^ op-S_i T_n^ op ) ]

则最终的目标函数为：

[ ext{max} mathcal{J}=sum_{(i,j)inmathcal{E}} I_{j o i} sum^K E_{u_nsim P_n(u)}log sigma(S_i T_j^ op -S_i T_n^ op)-frac{eta_1}{2} lVert S Vert_F^2 -frac{eta_2}{2}lVert T Vert_F^2 ]

之后使用异步随机梯度下降迭代更新参数 (S) 和 (T) 即可学习到节点的表示。

5. 总结

网络结构 + 社交影响力
构造分布，使用信息熵度量影响力
每个用户有 (S) 和 (T) 两个向量，表达其不同角色

END

2018.4.9