1 引言

现实世界中许多的社会, 物理和信息系统都是以复杂网络的形式存在的^[1]. 在这些网络中, 人们通过挖掘网络的潜在信息可以解决许多实际的问题, 例如链路预测^[2], 链路重构^[3], 节点分类^[4], 边分类等. 网络表示学习将节点映射到潜在空间^[5], 并保留了丰富的结构信息, 为这些下游数据挖掘任务提供了一种新的解决方法, 已在许多论文中被证明能够非常有效地解决上述任务^[6-13].

近10年里, 有很多能够保持网络的结构特性的方法被提出来. 然而, 以往的研究往往只注重节点视角下的网络拓扑信息, 而没有充分考虑边视角. 现有的网络表示学习算法可以分为两大类: 基于随机游走的网络表示学习算法和基于深度学习框架的网络表示学习算法. 基于随机游走的网络表示学习算法, 例如DeepWalk^[8]和Node2Vec^[9], 主要分为随机游走和Skip-gram^[10]算法两部分, 他们通过随机游走以获取节点视角下的网络拓扑结构, 再利用Skipgram模型对每个节点进行更新学习, Node2Vec在DeepWalk的基础上, 加入了带有偏置的随机游走, 使得其能以不同偏好的游走方式获取节点的同质性和结构等价性. Line^[11]也是一种基于邻域相似假设的网络表示学习算法, 通过设置两种邻近性构造目标函数来获取节点的局部相似性和邻居相似性. 然而, 这些算法往往只关注了节点视角下网络拓扑信息, 而没有充分考虑边视角. 基于深度学习的网络表示算法, 如SDNE^[12], 利用半监督的自动编码器模型来学习网络中每个节点的表示向量, DNGR^[13]则通过Random Surfing模拟随机游走过程获取网络拓扑信息, 再利用堆叠降噪自编码器对节点表示向量进行训练. GAE^[14]通过图卷积作为自编码器的编码方式, 为每个节点聚合其邻居的特征信息, 再利用解码器重构网络的邻接信息. 这些基于深度学习架的网络表示学习算法往往效果很好, 但其涉及到许多复杂计算, 其空间和时间复杂度随着网络规模的扩大面临着巨大的挑战, 同时, 这些算法也只关注了节点视角下的节点之间的连接信息, 而没有考虑过边视角. 而在已有的针对边的一些研究中, 大多考虑的是边上的属性或标签信息^[15,16]. 如NEES^[15]通过边计算节点之间关系的相似性, 从而设置带有偏好的随机游走, 使得节点的随机游走的每一步都与上一步有尽可能相似的关系. ELAINE^[16]则通过重构每种边的标签向量, 使得最终学习得到的节点向量能够同时包含边的标签信息和网络结构信息. 事实上, 不同的视角会带来不同的有效信息, 比如不同的社区划分. 因此, 本文将研究重点从节点转移到边. 利用边图(line graph)^[17]从边的角度观察网络. 在边图中, 原始网络的边表现为边图中的节点, 边图中的边表示原始网络中边之间的连接关系. Ahn等人^[18]在对重叠社区发现问题的研究中就提出了边社区的概念, 他们通过边而不是节点来划分社区, 并指出边的层次结构与原始网络中的节点层次结构有所不同, 从边的角度观察目标网络可以发现更多的特征.

一个好的网络表示学习算法应该能够有效地保存网络中的社区结构^[9], 为了达到这一效果, 现有的基于随机游走的网络表示学习方法如DeepWalk主要采用随机游走获取网络中每个节点的上下文信息, 继而采用Skip-gram模型学习其低维表示, 从而使得具有相似拓扑属性的节点具有相似的低维表示. 过往的研究表明^[19], 一个社区的内部连接应该多于其外部连接, 由于社区内的连接密度应该比较高, 所以随机游走时停留在自己社区内节点上的概率要高于到外部的概率. 为了进一步了解边图, 本文选择DBLP数据集^[20], 分别在原始网络和对应的边图上进行随机游走. 在设置相同的总采样次数的情况下, 在图1中画出了其不同视角下的节点采样频率分布, 横坐标表示原始网络中的节点在不同视角下的采样过程中的出现次数, 纵坐标表示对应出现次数的节点数量, 可以看到在两种视角下随机游走得到的节点频率分布是不同的, 这是因为边图可以为我们提供更多的连接信息, 进而可以为我们更好地揭示原始网络中的层次结构.

综上所述, 本文提出了一种融合节点视角和边视角的耦合网络表示学习算法DPBCNE (Dual Perspectives Based Coupled Network Embedding). 分别从两个视角下学习网络拓扑信息, 在这个耦合模型中, 可以同时学习节点和边的低维表示. 通过使用节点-边的耦合训练机制, 可以将节点和边映射到相同的低维空间中. 与大多数现有的网络表示学习方法间接获取边的表示方法不同, DPBCNE可以直接学习得到节点和边的表示, 更具有解释性. 本文在4个真实复杂网络中验证了DPBCNE的性能, 并通过节点分类, 边分类, 链路预测和链路重构4个任务来比较DPBCNE与当下最先进的网络表示学习方法的效果. 在链路预测任务中, 与基准方法相比, DPBCNE取得了较好的结果, 在合作者网络中仅次于CN算法. 而在节点分类, 边分类和链路重构任务中, DPBCNE均优于其他所有网络表示学习基准方法.

2 基于双视角的耦合网络表示学习算法

本文提出了一种新的基于双视角的耦合网络表示学习算法. 其主要模型框架如图2所示, 模型可以分为两个部分: 第1部分, 获取两种视角下的网络结构信息, 给定一个原始网络, 首先构建边图, 在原始网络和边图上分别进行随机游走, 得到不同视角下的节点采样序列. 第2部分, 耦合更新原始网络中的节点向量和边向量, 根据节点和边之间的对应关系以及不同视角下中心词节点和其上下文节点的关系, 将上述两个视角结合起来进行耦合更新, 在更新过程中共享节点和边的向量表示, 最终获得融合两种视角下网络结构信息的节点向量和边向量.

2.1 融合两种视角的网络表示学习

对于边视角, 本文首先根据原始网络构建边图(line graph) 来获取边视角下的结构信息. 给定的图 $G(V,E)$ , 其中 $V$ 表示节点集合, $E$ 表示边集合. 令图 $G$ 对应的边图为 ${G_{\rm link}}$ . 在边图 ${G_{\rm link}}$ 中, 图G的边集合E映射为边图的节点集合 ${V_{\rm link}}$ , 节点集合则映射为边图的边集合 ${E_{\rm link}}$ . 通过这种转化构建的边图记为 ${G_{\rm link}} < {V_{\rm link}},{E_{\rm link}} >$ .

对于两种视角下信息的获取, 本文采用DeepWalk的方法. 通过对不同视角下的节点进行随机游走得到语料库, 每一个随机游走序列都可以看作是自然语言处理中的一个句子, 然后用Skip-gram算法最大化中心词节点和其上下文的共现概率, 从而得到不同视角下每个节点的表示向量, 使得在同一视角下具有相似结构的节点具有相似的向量.

因此, 双视角下网络结构信息获取的目标函数分别为:

$L_{1}^{\rm node} = \sum\nolimits_{i = 1}^N {\sum\nolimits_{s \in S} {\sum\nolimits_{ - w \le j \le w,j \ne 0} {\log_2 P({v_{i + j}}|{v_i})} } } $

(1)

$L_{1}^{\rm link} = \sum\nolimits_{i = 1}^{{N^{\rm link}}} {\sum\nolimits_{{s^{\rm link}} \in {S^{\rm link}}}^{} {\sum\nolimits_{ - w \le j \le w,j \ne 0}^{} {\log_2 P\left( {v_{i + j}^{\rm link}|v_i^{\rm link}} \right)} } } $

(2)

其中, ${N}$ 为节点网络中节点的个数, ${S}$ 为随机游走得到的节点序列集合, ${w}$ 表示窗口大小, ${v}$ 表示节点网络中的节点. ${S^{\rm link}}$ 为边图中随机游走得到的序列集合, ${N^{\rm link}}$ 为边图中的节点个数即原始网络中边的数量, ${v^{\rm link}}$ 表示边图中的节点也即原始网络中的边.

该部分总的目标函数为:

${L_{\rm{1}}} = L_{1}^{\rm node} + L_{1}^{\rm link}$

(3)

为了得到有效的网络潜在特征, 本文同时融合节点视角和边视角进行网络表示学习. 介于节点与边的一对多的关系, 节点与其对应边的向量应当更相似, 通过不断耦合更新得到包含两种视角下网络拓扑信息的节点向量和边向量, 将另一视角的网络信息聚合到当前视角的节点向量学习上. 节点和边视角耦合关联模型目标函数分别如下:

$ L_{{{CO}}}^{\rm node} = \sum\nolimits_{i = 1}^N {\sum\nolimits_{v_c^{\rm link} \in {{{C}}^{\rm node}}({v_i})}^{} {\log_2 P\left( {v_c^{\rm link}|{v_i}} \right)} } $

(4)

$ L_{{{CO}}}^{{\rm{link}}} = \sum\nolimits_{i = 1}^N {\sum\nolimits_{{v_c} \in {C^{\rm link}}\left( {v_i^{\rm link}} \right)}^{} {\log_2 P\left( {{v_c}|v_i^{\rm link}} \right)} } $

(5)

关联部分总的目标函数为:

${L_{CO}} = L_{CO}^{\rm node} + L_{CO}^{\rm link}$

(6)

其中, ${C^{\rm node}}({v_i})$ 表示原始网络中与节点 ${v_i}$ 直接相连的所有边的集合. ${C^{\rm link}}\left( {v_i^{\rm link}} \right)$ 表示原始网络中与边 $v_i^{\rm link}$ 直接相连的所有节点的集合.

根据上述内容, DBPBCNE算法的总目标函数如下:

$L = \alpha {L_{\rm{1}}} + (1 - \alpha ){L_{CO}}$

(7)

其中, $\alpha \in [0,1]$ 是用来平衡不同视角重要性的一个参数, 通过联合优化使得在节点学习的过程中耦合边视角下的信息, 以得到更有效的节点表示, 同时也能学习得到耦合两个视角下信息的边向量.

2.2 耦合训练过程

本文使用随机梯度上升(SGA)来训练模型, 通过Softmax公式来计算上述公式中的概率公式, 例如式(1)中使用的 $P({v_{i + j}}|{v_i})$ , 可以通过下列方式来计算:

$P({v_{i + j}}|{v_i}) = \frac{{\exp \left( {{X^\prime }_{{v_{i + j}}}^{\rm{T}} \cdot {X_{{v_i}}}} \right)}}{{\displaystyle\sum\limits_{v \in V,v \ne {v_{i + j}}}^{} {\exp } \left( {{X^\prime }_v^{\rm{T}} \cdot {X_{{v_i}}}} \right)}}$

(8)

为降低时间复杂度, 本文采用负采样的方法对公式(8)进行简化. 除了更新窗口中的已知邻居节点外, 为给定节点生成 $k$ 个负样本. 在计算公式(1)中的梯度时, 便不需要在每个梯度步骤中枚举式(8)中的所有节点, 只需要计算根据词分布构建的负样本和已知的正样本. 假设给定邻居节点 ${v_{i + j}}$ 的负样本集合为 $NEG({v_{i + j}}) = $ $ \{ {v_1},{v_2}, \cdots ,{v_k}\} $ 则:

$ P({v_{i + j}}|{v_i}) = \prod\nolimits_{u \in \{ {v_{i + j}}\} \cap NEG({v_{i + j}})} {P(u|{v_i})} $

(9)

$ P(u|{v_i}) = \left\{ {\begin{array}{*{20}{l}} {\sigma \left( {X_{{v_i}}^{\rm{T}} \cdot {{X'}_u}} \right)},&{I_{1}^{{v_{i + j}}}(u) = 1} \\ 1 - \sigma \left( {X_{{v_i}}^{\rm{T}} \cdot {{X'}_u}} \right),&{I_{1}^{{v_{i + j}}}(u) = 0} \end{array}} \right. $

(10)

其中, ${X'_u}$ 表示待定参数, ${X_{{v_i}}}$ 为这部分要更新得到的节点向量, 指示函数 $I_{1}^{{v_{i + j}}}(u) = \left\{ {\begin{array}{*{20}{lc}}1,&{u = {v_{i + j}}}\\0,&{u \ne {v_{i + j}}}\end{array}} \right.$ . 对 $L_1^{\rm node}$ 求导可以得出:

$ \frac{{\partial L_1^{\rm node}}}{{\partial {X_{{v_i}}}}} = \sum\nolimits_{u \in NEG\left( {{v_{i + j}}} \right)}^{} {\left[ {I_{1}^{{v_{i + j}}}\left( u \right) - \sigma \left( {X_{{v_i}}^{\rm{T}} \cdot {{X'}_u}} \right)} \right]{{X'}_u}} $

(11)

$ \frac{{\partial L_1^{\rm node}}}{{\partial {{X'}_u}}} = \left[ {I_1^{{v_{i + j}}}(u) - \sigma \left( {X_{{v_i}}^{\rm{T}} \cdot {{X'}_u}} \right)} \right]{X'_v} $

(12)

从而可以得到原始网络中的节点在节点视角下通过上下文节点进行更新的公式如下:

$ {X'_u} = {X'_u} + \eta \left[ {I_1^{{v_{i + j}}}(u) - \sigma \left( {X_{{v_i}}^{\rm{T}} \cdot {{X'}_u}} \right)} \right]X_{{v_i}}^{} $

(13)

$ {X_{{v_i}}} = {X_{{v_i}}} + \eta \sum\nolimits_{u \in \{ {v_{i + j}}\} \cap NEG({v_{i + j}})} {\left[ {I_1^{{v_{i + j}}}(u) - \sigma \left( {X_{{v_i}}^{\rm{T}} \cdot {{X'}_u}} \right)} \right]{{X'}_u}} $

(14)

其中, $\eta $ 表示学习率. 同样的, 对于 $L_1^{\rm link}$ 也采用负采样以简化计算. 对于给定边视角下的已知的邻居节点 $v_{i + j}^{\rm link}$ , 负样本集合为 $NEG\left( {v_i^{\rm link}} \right) = \left\{ {v_1^{\rm link},v_2^{\rm link}, \cdots ,v_k^{\rm link}} \right\}$ , 边图中每个节点在边视角下通过上下文节点更新的公式如下:

$ {X'_{{u^{\rm link}}}} = {X'_{{u^{\rm link}}}} + \eta \left[ {I_1^{v_{i + j}^{\rm link}}\left( {{u^{\rm link}}} \right) - \sigma \left( {X_{v_i^{\rm link}}^{\rm{T}} \cdot {{X'}_{{u^{\rm link}}}}} \right)} \right]{X_{v_i^{\rm link}}}$

(15)

$\begin{split} {X_{v_i^{\rm link}}} =& {X_{v_i^{\rm link}}} + \eta \sum\nolimits_{u \in \{ v_{i + j}^{\rm link}\} \cap NEG(v_{i + j}^{\rm link})} {} \\ &{\left[ {I_1^{v_{i + j}^{\rm link}}\left( {{u^{\rm link}}} \right) - \sigma \left( {X_{v_i^{\rm link}}^{\rm{T}} \cdot {{X'}_{{u^{\rm link}}}}} \right)} \right]{{X'}_{{u^{\rm link}}}}} \end{split} $

(16)

其中, 指示函数为 $I_{1}^{v_{i + j}^{\rm link}}({u^{\rm link}}) = \left\{ {\begin{array}{*{20}{l}}1,&{{u^{\rm link}} = v_{i + j}^{\rm link}}\\0,&{{u^{\rm link}} \ne v_{i + j}^{\rm link}}\end{array}} \right.$ .

对于节点-边耦合关联模型部分, 本文通过用原始网络中与边相连的节点更新边, 用与节点相连的边更新节点, 从而使得最终得到的原始网络的节点和边向量同时学习得到两个视角下的网络信息.

对于节点向量更新部分, 给定一个原始网络中的节点 ${v_i}$ 和对应的一个相连边 $v_c^{\rm link}$ , 其负采样得到的负样本集合为 $NEG\left( {v_c^{\rm link}} \right){\rm{ = }}\left\{ {v_{\rm{1}}^{\rm link},v_{\rm{2}}^{\rm link}, \cdots ,v_{{k}}^{\rm link}} \right\}$ , 同样, 对于边向量更新部分, 给定一个边图中的节点 $v_i^{\rm link}$ 和他对应的一个原始网络中的节点 ${v_{\rm{c}}}$ , 其通过负采样得到的负样本集合为 $NEG({v_{\rm{c}}}){\rm{ = \{ }}{v_1},{v_2}, \cdots ,{v_k}{\rm{\} }}$

原始网络中节点在关联部分的向量更新公式如下:

${X'_{{u^{\rm link}}}} = {X'_{{u^{\rm link}}}} + \eta \left[ {I_{CO}^{{v_c}}\left( {{u^{\rm link}}} \right) - \sigma \left( {X_{{v_i}}^T \cdot {{X'}_{{u^{\rm link}}}}} \right)} \right]{X_{{v_i}}} $

(17)

$\begin{split} {X_{{v_i}}} =& {X_{{v_i}}} + \eta \sum\nolimits_{{u^{\rm link}} \in \{ {v^{\rm link}}\} \cap NEG({v^{\rm link}})} {} \\ &\left[ {I_{CO}^{{v^{\rm link}}}\left( {{u^{\rm link}}} \right) - \sigma \left( {X_{{v_i}}^{\rm{T}} \cdot {{X'}_{{u^{\rm link}}}}} \right)} \right]{{X'}_{{u^{\rm link}}}} \end{split}$

(18)

其中, 指示函数 ${{I}}_{{{CO}}}^{{v^{\rm link}}}{{(}}{{{u}}^{\rm link}}{{) = }}\left\{ {\begin{array}{*{20}{l}} 1,&{{u^{\rm link}} = {v^{\rm link}}} \\ 0, &{{u^{\rm link}} \ne {v^{\rm link}}} \end{array}} \right.$ .

原始网络中的边在关联部分的向量更新公式如下:

${X'_u} = {X'_u} + \eta \left[ {I_{CO}^{v_c^{\rm link}}(u) - \sigma \left( {X_{v_i^{\rm link}}^{\rm{T}} \cdot {{X'}_u}} \right)} \right]{X_{v_i^{\rm link}}} $

(19)

${X_{v_i^{\rm link}}} = {X_{v_i^{\rm link}}} + \eta \sum\nolimits_{u \in \{ v\} \cap NEG(v)} {\left[ {I_{CO}^{{v_c}}(u) - \sigma \left( {X_{v_i^{\rm link}}^T \cdot {{X'}_u}} \right)} \right]{{X'}_u}} $

(20)

其中, 指示函数 ${{I}}_{{{CO}}}^{{v_{{c}}}}{{(u) = }}\left\{ {\begin{array}{*{20}{l}} 1, &{u = {v_c}} \\ 0, &{u \ne {v_c}} \end{array}} \right.$ .

为了更加详尽地介绍本文提出的DPBCNE算法的具体流程, 本文给出了算法伪代码如算法1所示.

算法1. 基于双视角的耦合网络表示学习算法

输入: 图 $\scriptstyle{{G}}(V,E)$ , 窗口大小 $\scriptstyle{{w}}$ , 向量维度 $\scriptstyle{{d}}$ , 随机游走次数 $\scriptstyle \gamma $ , 总迭代次数 $\scriptstyle{{ITER}}$ , 游走长度 $\scriptstyle{{l}}$ , 学习率 $\scriptstyle \eta $ , 负采样个数 $\scriptstyle k$ .

输出: 节点表示向量矩阵 $\scriptstyle{{{X}}_{{v}}} \in {R^{N \times d}}$ , 边表示向量矩阵 $\scriptstyle{{{X}}_{{{{v}}^{\rm link}}}} \in {R^{{N^{\rm link}} \times d}}$ .

1. 初始化 $\scriptstyle{{X}}$ , $\scriptstyle{{{X}}^{{{link}}}}$

2. 根据 $\scriptstyle{{G}}(V,E)$ 构建边图 $\scriptstyle{G_{\rm link}} < {V_{\rm link}},{E_{\rm link}} >$

3. 　For $\scriptstyle{{i}} = {{0}}$ to $\scriptstyle\gamma $ :

4. 　　 $\scriptstyle \varOmega {=shuffle}({V})$

5. 　　 $\scriptstyle {\varOmega }^{{\rm link}}{=shuffle}({{V}}^{\rm link})$

6. 　　For each $\scriptstyle{{{v}}_i} \in \varOmega $ do

7.　　　 $\scriptstyle{{S}} = RandomWalk(G,{v_i},l)$

8. 　　End for

9. 　　For each $\scriptstyle{{v}}_{{i}}^{{{\rm link}}} \in {\varOmega ^{\rm link}}$ do

10. 　　　 $\scriptstyle{{{S}}^{{{link}}}} = RandomWalk({G^{link}},v_i^{link},l)$

11.　　 End for

12. 　End for

13.　 For $\scriptstyle{{iter}} = 1,2,3, \cdots ,ITER$ do

14.　　 For each $\scriptstyle{{s}} \in S$ do

15.　　　 根据式(13)和式(14)更新 $\scriptstyle{X_v}$ 和 $\scriptstyle{X'_{{v}}}$

16.　　　 根据式(15)和式(16)更新 $\scriptstyle{X_{{v}}}$ 和 $\scriptstyle{X'_{{{{v}}^{{{\rm link}}}}}}$

17.　　 End for

18.　　 For each $\scriptstyle{{{s}}^{\rm link}} \in {S^{\rm link}}$ do

19.　　　 根据式(18)和式(17)更新 $\scriptstyle{X_{{{{v}}^{{{\rm link}}}}}}$ 和 $\scriptstyle{X'_{{{{v}}^{\rm link}}}}$

20.　　　 根据式(19)和式(20)更新 $\scriptstyle{X_{{{{v}}^{{{\rm link}}}}}}$ 和 $\scriptstyle{X'_{{v}}}$

21.　　 End for

22. 　End for

算法可以分为第一步获取双视角下的网络结构信息部分和第二步耦合更新部分. 第2–10行分别对节点视角和边视角下的网络进行随机游走采样获取两个视角下的网络结构信息, 第14–22行表示耦合更新过程, 第14–17行对于第1步在原始网络中采样得到的所有节点序列中的每个节点, 分别用其对应的上下文节点和对应的边进行耦合更新, 同样, 第18–21行是对于边图中的采样得到的所有节点序列中的节点, 也即原始网络中的边, 分别用其上下文节点和对应的原始网络中的关联节点进行迭代耦合更新, 最终得到融合两个视角的原始网络的节点向量和边向量.

对于每一轮的迭代, 第一部分的对原始网络随机游走的时间复杂度为 $Nrl$ , 对边图的随机游走时间复杂度为 ${N^{\rm link}}rl$ , 第二步耦合更新部分, 对于节点的更新过程时间复杂度为 $Ngdk + Ndwrlk$ , 其中 $g$ 表示原始网络中节点的平均度, 对于边的更新过程时间复杂度为 $2{N^{\rm link}}dk + $ $ {N^{\rm link}}dwrlk$ , 其中, 每个网络的平均度通常都有一个最大值, 其余的 $d$ , $w$ , $r$ , $l$ , $k$ 均为可以设置的常数.

3 实验分析 3.1 数据集

本文主要针对传统的网络表示学习研究只是通过节点视角这一单一的视角而没有考虑边视角的问题, 提出了一种新的基于双视角的耦合网络表示学习算法(DPBCNE). 本文在4个真实的复杂网络数据集中分别验证了该方法的性能, 分别为Facebook^[21], GRQC^[22], HEPTH^[22]和DBLP^[20]数据集. 其中Facebook为社交网络, 总共有193种节点标签; GRQC和HEPTH为合作者网络, 数据集中没有标签信息; DBLP为引文网络, 总共有4种节点标签.

3.2 基准方法

在学习到节点的表示向量后, 本文分别在4个任务中与当下主流的网络表示学习算法进行比较, 其中, (1)–(3) 项是基于随机游走的网络表示学习算法, (4)–(6)项是基于深度学习的网络表示学习算法, 此外, 针对链路预测和链路重构任务, 本文还选择了一种效果良好的传统链路预测方法Common Neighbor^[23]作为对比方法, 相关基准算法简介如下:

(1) DeepWalk^[8]: 对节点采用随机游走和Skip-gram模型以学习得到每个节点的表示向量.

(2) Node2Vec^[9]: 在DeepWalk的基础上, 引入了带偏置的随机游走, 以选择不同的搜索方式采样节点. 其中, 偏置参数 $p = 0.25$ , $q = 0.5$ .

(3) Line^[11]: 通过分别定义损失函数同时保存网络中节点的一阶邻近度和二阶邻近度.

(4) SDNE^[12]: 使用自动编码器通过联合优化目标函数来保持节点一阶和二阶邻近性. 该方法采用高度非线性的函数对网络的邻接矩阵进行编码.

(5) DNGR^[13]: 利用Random Surfing策略生成概率共现矩阵, 再作为叠加去噪自动编码器的输入进行节点表示的学习.

(6) GAE^[14]: 使用图卷积网络(GCN)编码器和内积解码器. 该方法利用GCN学习节点间的高阶关系.

(7) Common Neighbor (CN)^[20]: 以每个节点对之间的公共邻居数作为节点之间的相似度评分, 以进行链路预测.

在实验过程中, 为保证公平比较, 所有实验的参数均统一设置. 对于网络表示学习算法, 其维度为128, 负采样样本数为5, 窗口大小为5, 每个节点的随机游走次数为10, 步长是40, 边图的设置与原始网络相同. 学习率为0.01, 最大迭代次数为200.

3.3 评价指标

为验证DPBCNE的有效性, 本文分别在链路预测, 链路重构, 节点分类和边分类4个任务上进行了对比实验.

对于链路预测和链路重构, 采用了AUC (Area Under Curve)和AP (Average Precision) 指标来验证最终的效果.

AUC表示当随机选择一个正样本和一个负样本时, 正样本分数高于负样本的概率. 例如, 在链路预测任务中, 随机挑选测试集中的一条边和一条不存在的边并进行比较, 重复进行n次, 其中有 $ n' $ 次测试集中边的分数大于不存在的边, 有 $ n''$ 次两者获得同样的分数, 那么最终得到的AUC计算公式如下:

${{AUC}} = \frac{{n' + 0.5n''}}{n}$

(21)

AP表示平均准确率, 其计算公式如下:

${{AP}} = \frac{{\displaystyle\sum {Pr ecision} }}{M}$

(22)

其中, Precision表示每个类别的准确率, M表示类别数.

对于节点分类和边分类实验, 采用了Micro-F1和Macro-F1来作为评价指标. 定义如下:

${{Micro}} - F1 = \frac{{\displaystyle\sum\nolimits_{A \in C} {F1(A)} }}{{|C|}}$

(23)

${{Macro}} - F1 = \frac{{2 \cdot Pr \cdot R}}{{Pr + R}}$

(24)

其中, F1(A)表示标签A的F1得分, C表示所有的标签集. Pr表示总的准确率, R表示总的召回率.

3.4 节点分类

节点分类是网络表示学习中用以验证算法有效性的一个重要任务. 此任务在Facebook和DBLP数据集上验证了DPBCNE算法, 首先移除数据集中没有标签的节点, 将数据集按照30%的比例划分训练集, 剩余的节点作为测试集, 将每个节点学习得到的表示向量作为逻辑回归分类器的输入进行训练, 通过计算Micro-F1和Macro-F1来比较不同模型之间的效果, 最终结果如表1所示.

从表1中可以看到, DPBCNE模型地结果在两个数据集上都优于其他算法. 在Facebook数据集中, DPBCNE的Macro-F1得分比其他算法中表现最好的DNGR算法高出了0.99%, Micro-F1得分则比DNGR算法高出了1.19%. 这表明, 通过融合两种视角下的网络表示学习能够获取比在单一视角下更丰富的节点采样结果, 也就是更丰富的网络结构信息, 使得其在节点的类别划分上比只关注单一视角的效果更好. 而在DBLP数据集中, DPBCNE算法的Macro-F1和Micro-F1得分比DNGR分别高了0.3%和0.55%. DPBCNE模型在Facebook数据集中的提升效果比在DBLP数据集中更好, 这是因为Facebook数据集中每个节点具有多个标签, 而DBLP数据集的每个节点有且只有一个标签, 融合了边视角的耦合网络表示学习, 也更能区分出节点的重叠社区.

3.5 边分类

传统的网络表示学习算法通常使用两个节点向量简单相连或相加来作为两个节点之间的边的表示^[9]. 在本任务中, 对于所有的网络表示学习基准算法, 首先学习到每个节点的向量, 再用 $ ({v}_{i}+{v}_{j})/2 $ 表示节点 $ {v}_{i} $ 和节点 $ {v}_{j} $ 之间的边向量. 而对于DPBCNE, 通过耦合学习, 可以直接得到每条边的表示, 使其更具解释性. 本任务采用Facebook数据集进行验证, 聚合每对节点的标签, 作为其对应边的标签, 按照1%~9%的比例对于网络中的边划分出训练集作为逻辑回归分类器的输入. 本任务采用了Micro-F1和Macro-F1指标来衡量最终的效果, 具体结果如图3所示.

图3中, DeepWalk (Link) 方法通过直接对边图的节点进行随机游走, 不进行耦合训练直接得到边向量. DeepWalk (Link) 在边分类任务中也取得了比只在节点上进行DeepWalk学习节点表示再拼接成边向量更好的结果, 这说明对于边向量的计算, 在边图上直接进行学习得到是有效的. 同时, DPBCNE始终高于其他所有方法包括效果良好的DeepWalk (Link), 这说明融合两个视角的耦合训练学习得到的边向量可以更好地保存网络中的信息.

3.6 链路预测

在这个任务中, 首先将网络中所有的边划分为测试集和训练集(比例为3:7), 同时保持网络的连通性, 通过对训练集进行网络表示学习, 得到网络中每个节点的表示, 再计算 $ {|v}_{i}-{v}_{j}| $ 作为 $ {v}_{i} $ 和 $ {v}_{j} $ 之间的边的表示. 本文认为两个节点之间是否存在边可以由节点对应向量的绝对差来决定^[4]. 将测试集中的边看作为正例, 对每一个正例等比例地构建一条不存在的边当作负例, 将其作为逻辑回归分类器的输入. 本任务用AUC和AP作为本任务的评价指标, 具体结果如表2所示.

由表2可以看到, DPBCNE的AUC指标都在75%以上, 这说明DPBCNE可以有效地预测网络中的未知边. 在Facebook数据集以及DBLP数据集中, DPBCNE取得了最好的效果, 在GRQC与HEPTH数据集中DPBCNE的效果仅次于CN算法, 这说明在合作者网络中, 节点之间的关系非常受共同邻居的影响, 复杂的学习反而没有简单的指标来得有效, 但DPBCNE仍然高于其他所有基于随机游走和深度学习的网络表示学习, 由于融合了两种视角, DPBCNE能够更好地预测网络中未知的边.

3.7 链路重构

链路重构任务类似于链路预测, 不同的是链路重构所重构的是现有的边, 而不是去预测未知的边. 给定一个网络, 使用不同的链路重构方法来重构原始网络的所有边. 在这个任务中, 依旧使用两个节点表示向量之间的绝对差作为每条边的表示. 同样, 采用AUC和AP作为评价指标. 具体结果如表3所示.

可以看到, DPBCNE模型的AUC结果都接近于1, 这说明该方法能够很好地保存网络的邻接关系. 在4个数据集中, DPBCNE始终效果是最好的, 相比于传统的链路预测方法CN, DPBCNE在AUC指标上提升了1.03%~17.59%, 在AP指标上提升了0.87%~17.16%, 相比于效果最好的基于随机游走的算法LINE, DPBCNE在AUC指标上提升了0.96%~19.05%, 在AP指标上提升了0.69%~24.1%, 对比效果最好的基于深度学习的算法DNGR, DPBCNE在AUC指标上提升了1.76%~5.3%, 在AP指标上提升了1.7%~7.73%.

4 结论与展望

本文讨论了两种不同视角在社区结构和随机游走方面的差异, 通过经验分析, 本文得出边视角和节点视角在随机游走中出现的节点分布是不同的, 这意味着通过不同的视角, 可以获得更多的网络拓扑信息. 因此, 本文提出了一种新的网络表示学习算法DPBCNE, 可以同时考虑边视角和节点视角, 并通过耦合学习, 学习得到节点向量和边向量. 本文在节点分类, 边分类, 链路预测和链路重构4个任务上验证了该方法的效果. DPBCNE在4个任务中都展现了其良好的性能. 本文只在静态网络中进行了任务验证, 而在现实生活中, 网络是不断变化的, 因此, 未来的研究 将该算法考虑扩展到动态网络以及加入深度学习框架以获得更好的效果^[24]. 同时, 鉴于DPBCNE可以直接学习得到每条边的表示, 还将考虑将其扩展到知识图谱的应用研究中^[25].