KDD 2019 | 结合属性随机游走的图递归网络

今天给大家介绍德克萨斯A&M大学的Xiao Huang等人在KDD 2019发表的一篇文章“Graph Recurrent Networks with Attributed Random Walks”，作者提出一种新的基于属性的网络嵌入框架--GraphRNA，通过将协作游走机制AttriWalk和图递归网络GRN结合起来，可以在属性网络上更有效地学习节点的表示。

1

研究背景

随机游走广泛应用于网络嵌入和链接预测等各种网络分析任务中，它可以将几何结构转换为结构化序列，同时可以缓解稀疏和维数灾难的问题。然而在实际系统中，网络节点通常具有不同的特性且包含用于补充网络的丰富的信息，这些节点属性相对于拓扑结构而言是异构的，这也会使节点交互更加复杂，目前还没有为属性网络开发一种可以有效提取联合信息的随机游走方式。为了解决这一问题，作者提出了GraphRNA框架，该框架是一种新的基于属性的网络嵌入框架，将协作游走机制AttriWalk与图递归网络GRN结合，在属性网络上更有效地学习节点的表示。

2

模型

GraphRNA的核心思想是在属性网络上实现联合随机游走，对属性节点之间的相互作用进行建模，并采用递归神经网络结构嵌入非线性关联。图1展现了GraphRNA的细节，该框架可大致分成三个部分：（1）定义一个统一的游走机制对属性节点交互进行采样，为了在网络和节点属性中实现联合游走，构造一个基于节点属性的二分网络，增加游走的多样性，最终将复杂的属性节点交互转换为一系列信息节点索引序列；（2）开发一种有效的深度体系结构，称为图递归网络，它允许节点表示在模型内以与原始网络中节点交互相同的方式进行交互，学习每个序列中每个节点索引的 维向量表示；（3）对于每个节点 ，采样少量以 为起始节点的序列，表示为集合 ，最后应用一种池化方法融合 中节点索引的所有向量表示来计算节点 的最终嵌入表示。

图1 GraphRNA框架结构

2.1 基于属性的随机游走 - AttriWalk

为了处理异构信息并有效地采样属性节点之间的交互，AttriWalk定义了一个统一的游走机制，其核心思想是基于节点的属性构建一个节点-属性二分网络，并利用这个二分网络来增加随机游走多样性，缓解向高度聚集的节点收敛的趋势。AttriWalk以一定的概率决定在采样的二分图网络上走两步还是在采样的局部拓扑网络上走一步，最后根据确定的随机游走长度L，将复杂的属性节点交互转换为一系列信息节点索引序列。

2.2 图递归神经网络 - GRN

序列描述了节点如何通过拓扑结构和节点属性与邻接节点交互， 循环神经网络(RNN)中的隐状态序列自然地与这些采样节点交互相一致，因此，可以利用RNN对序列中的顺序信息进行建模，对于任意节点的生成序列，将序列中的每个游走节点用向量表示，对于拓扑节点使用属性节点特征表示向量，对于属性类型节点使用one-hot向量表示，将当前序列中的每个节点对应的表示向量送入全连接层进行降维，将采用双向GRU学习到的前向隐状态和反向隐状态序列中的对应向量拼接，对任意节点i中的所有序列，通过第一次池化操作生成一个序列表示，再对除了初始节点以外的所有节点向量采用第二次池化操作生成一个向量ri，再与第一次池化生成的初始节点i的表示向量r1进行拼接，生成最终的节点i的表示向量hi。作者提出的图递归网络的体系结构如图2所示。

图2 图递归网络的体系结构

GraphRNA可以用无监督、监督或半监督的设置来训练，这个属性继承于图卷积网络。作者以监督学习为例，基于交叉熵误差的目标损失函数定义如下：

其中是用于表示节点的标签的one-hot向量。整体GraphRNA算法如表1所示：

表1 GraphRNA的算法框架

3

实验

作者在三个真实的属性网络上对提出的框架GraphRNA进行分析，实验中使用的三个公开可用的属性网络的统计信息如表2所示：

表2 三个真实数据集的统计信息

为了验证GraphRNA的有效性，作者将其提出的方法GraphRNA与其他三类基线方法进行比较：（1）Single Source: 为了研究每个单一源的信息量如何，作者使用节点属性嵌入方法Attribute-Spec与网络嵌入方法DeepWalk和LINE进行对比。（2）Shallow ANE: 为了研究GraphRNA与浅层模型相比的有效性，作者使用两个最先进的浅层ANE方法MulitSpec和AANE模型与GraphRNA做对比。（3）Deep ANE: 为了分析GraphRNA相较于GCN结构的先进性，使用普通GCN和GraphSAGE与GraphRNA模型做对比。

此外，作者还针对提出的基于属性的网络嵌入模型GraphRNA进行消融研究，通过观察没有AttriWalk的GraphRNA-noAttriW和没有RNN层的GraphRNA-noRNN的性能，对GraphRNA不同组件的贡献度进行评估分析。整体实验结果如表3所示:

表3 所有baseline针对节点分类问题的micro-average性能

实验表明，针对于micro-average指标，GraphRNA在BlogCatalog和Flickr数据集上都实现了最佳的性能，在Citation数据集上也达到了一个与最佳结果有可比性的性能。随着训练数据集的百分比增加（25%，50%，100%），各种方法的性能都有所提升。此外，消融研究的实验结果表明在没有AttriWalk的情况下，GraphRNA-noAttriW的性能下降，特别是在Flickr数据集上；在没有RNN层的情况下，GraphRNA-noRNN的性能略差于GraphRNA；相较于GRN，AttriWalk组件能给GraphRNA带来更多的性能改进，这表明AttriWalk是一个更重要的组件，总体而言，将两个组件结合起来的方法GraphRNA可以获得最佳性能。

4

总结

在网络分析中，人们对图上的随机游走进行了深入研究，但是很少有人针对属性网络开发基于随机游走的技术对异构信息进行编码，以增强节点表示学习能力。针对这一问题，作者提出了一种游走机制AttriWalk，它可以在网络和节点属性内进行协作采样。受表示学习中深度学习技术的启发，作者在AttriWalk上进一步设计了一种定制的图神经网络体系结构GraphRNA，实现基于属性的网络嵌入。GraphRNA将复杂的属性节点交互转化为一系列基于AttriWalk的信息节点索引序列，并通过图递归网络将其编码成统一的向量表示。在真实数据集上进行的评估实验结果表明，与不同的基线模型相比GraphRNA更具有效性。

参考资料

https://www.kdd.org/kdd2019/accepted-papers/view/graph-recurrent-networks-with-attributed-random-walks

代码

https://github.com/xhuang31/GraphRNA_KDD19