论文《DeepInf: Social Influence Prediction with Deep Learning》阅读_structinf: mining structural influence from social

论文概况

这篇文章《DeepInf: Social Influence Prediction with Deep Learning》是清华大学唐杰老师团队的一篇关于社交影响力预测方面的论文，本文提出了DeepInf模型，通过使用深度学习算法对图结构中节点影响力进行预测，发表在SIGKDD 2018上。

论文地址： https://arxiv.org/abs/1807.05560
PDF下载： https://arxiv.org/pdf/1807.05560.pdf

本文亮点主要集中在(1)网络嵌入Network Embedding，(2)图卷积神经网络，(3)注意力机制的引入。

下面对这篇文章进行介绍，介绍内容夹杂了很多个人的理解，主要分为以下几个部分：

• 摘要
• Introduction
• 问题形式化
• 模型介绍
• 实验部分

摘要

社交网络的兴起，加速了我们被社交网络所影响的过程。以往的社交影响力模型，都是通过手动构造特征进行建模，这样不利于模型的迁移。

基于这一现象，本文提出了一个端到端的深度学习模型，具体的，通过结合网络的结构特征和用户层面的特征信息，使用图卷积神经网络进行了学习，并分别在OAG，Twitter，Weibo，Digg这四个数据集上进行了实验。

Introduction

社会影响力在以往的研究中分为个人影响力（user-level）和群体影响力（aggregated or global patterns of social influence），在很多模式下，个体影响力的分析更加有用。个体影响力的分析，也就是从社交网络中将每一个个体的特征进行提取，并对个人的影响力进行分类或者预测等任务。

社交网络一般以图的形式存在，相比较于图像，语句等比较规则的数据（CNN用于处理固定大小的图像，RNN用于NLP中的语句，图像大小一般是固定的，在NLP中用于构建语义的词向量长度也是固定的），图结构更不易处理（对于图中的每个节点，其出度、入度一般都不相同）。因此最近提出的图神经网络对于图结构就是一个比较自然的选择。

如上图所示，本文¹主要解决的问题如下：给定节点v，和她的近邻节点，在一个时间窗口内，通过对开始时间各节点状态（包括图结构和节点特征）进行建模，完成对结束时间节点v状态的预测（激活或者未激活）。

在论文中，图结构使用图神经网络GCN（Graph Convolutional Neural Network）抽取，节点特征使用训练好的DeepWalk工具 ² 进行抽取。另外，本文在此基础上，使用注意力机制，通过对节点v临近的不同节点赋予不同的权重，使用图注意力网络GAT（Graph Attention Model）进行了进一步拓展。

问题形式化

对社会影响力进行形式化描述之前，首先对一些概念进行定义。
r-近邻(r-neighbor)：给定图 $G=(V,E)$， 其中V表示用户（vertex）， $E\subseteq V\times V$ 表示用户关系（edge），则用户$v$的r-近邻定义为 Γ v r = { u : d ( u , v ) ≤ r } \Gamma_v^r=\{u:d(u, v)\leq r\} Γvr​={u:d(u,v)≤r}，其中 $d(u,v)$ 用于表示节点 $u$ 和节点 $v$ 之间的最短距离。

r-中心网络(r-ego network)：用户 $v$ 的r-中心网络就是由上述的r-近邻及其节点之间的连线组成的网络，用 $G_v^r$ 表示。

用户行为在本文中只有两个状态，针对时间戳 $t$ ，如果用户 $u$ 有完成状态，则 $s_u^t=1$ ；反之，如果在整个观察窗口内都没有完成动作，则 $s_u^t=0$ 。动作包括：转发行为、引用行为等。

基于上述定义，作者给出文章想要解决的问题——局部社会影响力（social influence locality）：给定用户 $v$ 的r中心网络 $G_v^r$ 以及r-近邻（不含 $v$）的用户行为状态集合 S v t = { s u t : u ∈ Γ v r ∖ { v } } S_v^t=\{s_u^t:u\in\Gamma_v^r \setminus \{v\}\} Svt​={sut​:u∈Γvr​∖{v}} ，局部社会影响力拟解决在一段时间 $\Delta t$ 之后，对用户 $v$的用户行为的预测问题，即$$P(s_v^{t+\Delta t}|G_v^r,S_v^t)$$

为解决这一问题，具体的，可以形式化如下：对于$N$个样本，每个样本是一个三元组$(v,a,t)$，v表示用户，a表示行为，t表示时间。对于每个三元组，给定 $G_v^r$ 和 $S_v^t$，以及 $\Delta t$ 时间之后用户 $v$ 的状态 $s_v^{t+\Delta t}$，则社会影响力预测问题可以转化为一个二元图分类问题，进一步通过最大似然估计法解决问题，即$$\mathcal{L}(\Theta )=-{\sum }_{i=1}^{N}log(P_{\Theta }(s_{v_i}^{t_i+\Delta t}|G_{v_i}^r,S_{v_i}^{t_i}))$$

模型介绍

获取r-中心网络

针对用户 $v$，想要获取她的r-中心网络 $G_v^r$ ，最直接的方法是进行从 $v$ 开始的广度优先遍历。但由于（1）不同节点 $v$ 的r-中心网络规模可能相差很大；（2）六度分隔理论表明一个节点 $v$ 的r-中心网络可能会很大（在本文中，r设置为3）。因此本文进一步使在原始的r-中心网络中进行下采样，以固定样本规模。

下采样的方式使用重启随机游走算法（Random Walk with Restart，RWR），即从用户 $v$ 或她的激活临近用户出发，每次以一定概率游走到下一个节点，或者回到出发节点再次游走。通过这样的方式，就可以形成一个固定规模 $n$ 的r-近邻 ${\bar{\Gamma }}_v^r$ 。( $|{\bar{\Gamma }}_v^r|=n$ )，由此产生固定规模的r-中心网络 ${\bar{G}}_v^r$，以及新的状态集合 S ˉ v t = { s u t : u ∈ Γ ˉ v r ∖ { v } } \bar{S}_v^t=\{s_u^t:u\in \bar{\Gamma}_v^r \setminus \{v\}\} Sˉvt​={sut​:u∈Γˉvr​∖{v}}。因此，重新定义目标函数如下：
$$\mathcal{L}(\Theta )=-\sum _{i=1}^{N}log(P_{\Theta }(s_{v_i}^{t_i+\Delta t}|{\bar{G}}_{v_i}^r,{\bar{S}}_{v_i}^{t_i}))$$

网络结构

网络的整体结构如下图所示，下面分别进行介绍：

嵌入层

在原始输入的网络中使用DeepWalk²模型，得到嵌入矩阵$\mathbf{X}\in {\mathbb{R}}^{D\times |V|}$，其中每一行${\mathbf{x}}_u\in {\mathbb{R}}^D$ 表示对于其中任意节点的嵌入向量。

归一化层

为使不同用户（节点）之间特征向量量纲统一，使用归一化层。具体的，针对不同用户的特征向量，将相同坐标的特征向量进行统一。 ${\mu }_d$ 表示均值， ${\sigma }_d^2$ 表示方差， $ϵ$ 表示一个极小值。具体如下：
$$y_{u}d=\frac{x_{ud}-{\mu }_d}{\sqrt{{\sigma }_d^2+ϵ}}d=1,2,..,D$$
其中，$${\mu }_d=\frac{1}{n}\sum _{u\in {\Gamma }_v^r}{x}_{ud}$$
$${\sigma }_d^2=\frac{1}{n}\sum _{u\in {\Gamma }_v^r}(x_{ud}-{\mu }_d{)}^2$$

输入层

经过上面两层，已经将图中的特征进行了提取，本文又进一步添加了三类手动提取的特征：

• 用户行为状态
• 用户是否是中心用户（ego user）
• 一些定制的节点结构化特征如下：
  

GCN/GAT层

这一层执行真正的深度学习运算。GCN执行图卷积运算，GAT则是在GCN的基础上加入了attention机制，能够在临近节点的影响中加入权重，从而能够将临近节点的影响进行差异化。

两个模型的原理，都是通过利用图中的特征信息和图的拓扑结构信息这两类信息，完成图中节点特征的映射，将特征进行非线性变换，映射到一个2维的结果向量上（也就是用户的行为状态）。

我们使用 $H$ 表示每一层的输入向量， $H^{\prime }$表示输出的向量，假定每个batch使用的用户数量为n，则 $H\in {\mathbb{R}}^{n\times F}$ ， $H$ 中的每一行$h_i^{\mathsf{T}}$ 表示一个用户的特征。其中F表示输入的特征向量的长度，对于第一层来说，F就是我们输入层输出的向量长度（DeepWalk长度 + 1（ego标志位） + 2（状态标志位） + 手动特征长度）。

这一层的目的，就是进行非线性变换，输出一个$H^{\prime }$向量，$H^{\prime }\in {\mathbb{R}}^{n\times F^{\prime }}$。转换过程如下：
$$H^{\prime }=GCN(H)=g(A(G)H{W}^{\mathsf{T}}+b)$$

在上式中，

$H\in {\mathbb{R}}^{n\times F}$表示输入的特征向量，
$A(G)$是一个函数，输出一个$n\times n$大小的矩阵，用于表示图卷积神经网络中的拉普拉斯矩阵。图卷积神经网络通过构造拉普拉斯矩阵完成了归一化。这部分具体可以参考【图结构】之图神经网络GCN详解 这篇博客，对GCN的一些细节进行了讲解，这里不再赘述。
$W\in {\mathbb{R}}^{F^{\prime }\times F}$， $b\in {\mathbb{R}}^{F^{\prime }}$ 用于表示模型中的参数。

GCN相关处理

GCN中的 $A(G)$ 使用下式进行：

$$A_{GCN}(G)=D^{-1/2}A{D}^{-1/2}$$

在上式中，$A$是图结构的邻接矩阵（但事实上是在邻接矩阵的基础上对角线全部+1，也即，$A=A+I$，这样保证了在特征相互影响的过程中能够将元素本身考虑进去）;$D$是一个对角矩阵，对角线元素用来表示每个节点的度。

GAT相关处理

GCN通过将图中的结构信息加以考虑，使得节点的特征映射受到了邻接节点的影响。但是这种影响是相同的，没有对每个邻接节点进行单独考虑，这显然与实际情况不相符合。GAT就是利用这一点，通过注意力机制的引入，对不同节点加以不同的权重，得到了一个有所侧重的特征影响过程。

具体地，GAT中的 $A(G)$ 使用下式进行：
$$A_{GAT}(G)=[a_{ij}{]}_{n\times n}$$
$a_{ij}$的计算过程较为复杂，如下：

• 首先，我们通过attention函数计算出attention系数， attn函数完成运算： $e_{ij}=attn(W{h}_i,W{h}_j)$ 。值得注意的，这里的$e_{ij}$只对邻接节点及节点自身进行计算。这样，就可以将图中的结构信息进行计算。attn 函数完成节点之间的关联重要性：${\mathbb{R}}^{F^{\prime }}\times {\mathbb{R}}^{F^{\prime }}\to \mathbb{R}$
• 之后，再将上述计算的系数进行归一化，使用softmax函数进行。具体地， $a_{ij}=softmax(e_{ij})=\frac{exp(e_{ij})}{\sum _{k\in {\Gamma }_i^1}exp(e_{ik})}$ 。这里 ${\Gamma }_i^1$ 就是节点 $i$ 的直接相邻节点。

在本文中，attn函数相当于一个单层的前馈神经网络，即把 $2F^{\prime }$ 长度的向量通过$c^{\mathsf{T}}$作为权重映射到一个实数域上。结合所有上述信息，我们可以得到最终的 $A(G)$计算如下：

$$a_{ij}=\frac{\mathsf{exp}(LeakyReLU({\mathbf{c}}^{\mathsf{T}}[\mathbf{W}{\mathbf{h}}_{\mathbf{i}}||\mathbf{W}{\mathbf{h}}_{\mathbf{j}}]))}{{\sum }_{k\in {\Gamma }_i^1}\mathsf{exp}(LeakyReLU({\mathbf{c}}^{\mathsf{T}}[\mathbf{W}{\mathbf{h}}_{\mathbf{i}}||\mathbf{W}{\mathbf{h}}_{\mathbf{j}}]))}$$

更进一步地，多头注意力（Multi-Head Graph Attention）的使用可以聚合多种注意力影响下的特征向量。每一个头就是上述的一个注意力矩阵，通过并行使用多个头并进行聚合，可以提取多种注意力下的影响力。这一过程和CNN中的多个核原理是一样的。如下：

$$H^{\prime }=g(Aggregate(A_1(G)H{W}_1^{\mathsf{T}},\dots ,A_k(G)H{W}_k^{\mathsf{T}})+b)$$

输出层

输出层共两个，用于表示用户的行为状态（转发/未转发，引用/未引用等），通过与标记结果进行比较，并进行反向梯度传播，完成参数的更新。

实验部分

实验部分在OAG(Open Academic Graph)，Digg， Twitter， Weibo四个数据集上进行了实验，这里贴一个结果，略过……

如果你看到了这篇文章的最后，并且觉得有帮助的话，麻烦点个赞，谢谢了！也欢迎和我进行讨论！

---

1. Jiezhong Qiu, Jian Tang, Hao Ma, Yuxiao Dong, KuansanWang, and Jie Tang.2018. DeepInf: Social Influence Prediction with Deep Learning . In KDD ’18: The 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, August 19–23, 2018, London, United Kingdom. ACM, New York, NY, USA, 10 pages. https://doi.org/10.1145/3219819.3220077 ↩︎

2. Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014. Deepwalk: Online learning of social representations. In KDD ’14. ACM, 701–710. ↩︎ ↩︎