带属性随机游走的图循环网络

1. 背景

随机游走模型被广泛应用于从网络嵌入到标签传播的各种网络分析任务中。但是在真实的系统中，节点通常不是纯顶点，而是具有不同的特征。然而，为具有属性的网络开发随机游走模型是困难的，节点属性使得节点间的交互更加复杂，拓扑结构也更加异构。本文探索了在属性网络上进行联合随机游走，并利用它们来促进深度节点的学习。最后，利用实验与最先进的嵌入算法作比较，证明了模型的有效性。 # 2. 介绍 在纯网络上的随机游走已经得到了深入的研究，但是在真实的系统中，节点通常不是纯粹的顶点，而是含有大量的属性数据，这些属性描述了节点的特定特征。这种网络称为属性网络。这些节点属性可以潜在地用于推进基于随机游走的分析。本文提出在属性网络上进行有效的随机游走，并通过深度学习技术对提取的信息进行卷积，实现节点表示学习。通过设计了一种新的属性网络嵌入框架（带属性随机游走的图回归网络：GraphRNA)），它由一个有效的联合游走机制(AttriWalk)组成，并结合了带属性随机游走的图回归神经网络的优点。

3. 问题重述

设V为现实信息系统中的n个节点集合，通过无向网络连接，加权邻接矩阵记为G∈R^n×n。对于每一对节点i和j，如果它们之间没有链接，则w_ij为0，而w_ij越大，则表明它们之间的关系越强。每个节点i还与一个高维特征向量a_i相关联，称为节点属性。本文使用矩阵A∈R^n×m来表示所有节点属性的集合。这种类型的网络G = (V,G,A)被定义为带属性的网络。为了使问题在物理上有意义，本文假设G和A的元素都是非负的。 定义1(属性网络嵌入ANE)：给定一个属性网络G = (V,G,A)和小维度d，学习一个映射f:{G,A}→H, H∈R^n×d,使G中所描述的关联信息和A中所描述的节点属性信息可以尽可能多的保存在H中。 定义2(基于随机游走的属性网络嵌入)：开发一个符合ANE数据特征的框架，包括复杂的节点交互、非线性关联和异构信息源，同时保持随机游走带来的良好特性。 # 4. 基于属性游走的嵌入 为了有效地实现基于随机游走的属性网络嵌入，本文提出了一种新的深度嵌入框架GraphRNA。

4.1 属性随机游走-AttriWalk

在本节中，本文研究在属性网络上执行随机游走，其中节点不仅具有网络连接G的特征，还具有节点属性A所描述的丰富辅助信息。联合采样G和A将使随机游走更有信息性。 随机游走可以作为桥梁，帮助本文提出的深度嵌入架构处理几何结构。本文探索利用随机游走将不规则属性网络G转换为结构化数据。 ### 4.1.1 简单方案 基于A构造一个新的网络S，其中节点i和j之间的边权定义为a_i和a_j之间的相似性。这样，A就转化为拓扑结构S。这种直观的实现代价很高。计算S的时间复杂度为O(nN_A)，其中N_A表示A中非零元素的总数。 ### 4.1.2 统一游走策略 本文构造基于节点属性的二部图网络，利用它来推动随机游走的多样性，缓解向网络中心度高的节点收敛的趋势。 为了平衡G和A中的元素,本文首先采用ℓ1标准规范化G和A的每一行分别得到G¯和A¯。然后本文收集所有m节点属性类别作为一个集合,把这个集合定义为U。通过考虑每个节点属性类别δ_k∈U作为一个节点,本文可以定义一个新的二部图网络, 其中ε表示相应的边集。如果节点i包含属性δ_k，则在节点i和δ_k之间有一条边。这条边的权重被定义为。

提出的Attriwalk将在所有节点之间跳转。假设目前本文已经跳跃到一个节点i。设抛硬币正面朝上的概率为α，则接下来的如下公式计算。 (i) 如果正面朝上，那么本文就在G¯上走一步。本文跳转到节点j∈V，其概率定义为， (ii) 如果反面朝上,然后本文在A上走两步:首先,本文跳到一个节点δk∈U，概率为, 第二,从节点δk,本文跳到一个节点j∈V,概率定义为, 在V中的节点游走时, 当α= 1, AttriWalk类似于香草随机游走。随着α逐渐减弱,走路会更依赖于节点的属性。对应的转移概率矩阵可表示为: ### 4.1.3 理论属性 定理3.1 在自然损耗游走中，当硬币正面朝上时，从节点i走到另一个节点j的概率： D是一个对角矩阵： ### 4.1.4 采样设置

采样所有局部节点的拓扑结构和节点属性。所有的随机游走都将被截断为长度L。对于每个节点i∈V，设置一个固定数量B表示固定游走长度。

4.2 图递归网络- GRN

4.2.1 网络结构

递归神经网络(RNN)中的隐状态序列符合这些抽样节点间的相互作用。因此，本文利用RNN对T中的顺序信息进行建模。图2描述了所提出的图循环网络的体系结构，具体如下。 1)让{1,δ₃, 6, 4, δ₄, 4}是一个在τ_i中长度为L的序列。本文把每一个L指标映射到一个m维向量。 2)本文使用一个全连接层来减少节点属性的维数，得到向量{xj}，其中j = 1，…，L。在数学上，xj的计算是基于, 其中σ是sigmoid函数, W_a∈R^m×d是权重矩阵。 3) 对于给定的{x_j}，本文使用双向RNN，如长短时记忆和门控循环单元来学习正向的隐藏状态序列和反向的隐藏状态序列。 4)对于每一个节点i∈V,在他的序列集τi中,每个节点有BL指数。相应地，本文可以从双向RNN层得到BL嵌入向量{rj}。首先使用池化方法将所有的B序列合并成一个，标记为 然后本文应用池化方法再次把所有的 1) 合并为r_i。最终的嵌入表示h_i定义为

4.2.2 与Graph Convolutional Networks的关系

GCN可以解释为本文提出的图递归网络(GRN)的一个特例。如果本文去除GRN中的双向RNN层，随着采样B的数量不断增加，GRN中的池操作将趋向于向所有邻居进行归纳学习。一些研究也证明了从多跳邻居中随机抽样可以提高GCN的性能。带属性的随机游走使本文能够通过考虑节点交互顺序信息来增强GCN。GCN通过层与层实现节点交互，而GRN则允许节点和属性类别在同一个双向RNN层内交互。GCN对多层不适用，因为它会变成过度平滑的。因此，节点在GCN内只能交互几次。但是在GRN中，双向RNN层允许更长的交互。 ## 4.3 优化 GraphRNA可以在无监督、有监督或半监督的环境下进行训练。这个不错的属性是从GCN继承的。 损失函数基于交叉熵误差，目标函数定义如下: 式中，y_i为表示节点i标签的one-hot向量。 # 实验结果 对于所有的deep baselines和GraphRNA，本文使用标签来训练模型，最后的隐藏状态被返回为H。本文也使用多层感知器分类器一起训练它们，并在端到端方法类别中报告结果。三个数据集的微观平均实验分类结果如表3所示。 从表3的结果中可以验证GraphRNA的有效性。