【每日一读】Graph Recurrent Networks With Attributed Random Walks

简介

Hello！
非常感谢您阅读海轰的文章，倘若文中有错误的地方，欢迎您指出～
 
ଘ(੭ˊᵕˋ)੭
昵称：海轰
标签：程序猿｜C++选手｜学生
简介：因C语言结识编程，随后转入计算机专业，获得过国家奖学金，有幸在竞赛中拿过一些国奖、省奖…已保研
学习经验：扎实基础 + 多做笔记 + 多敲代码 + 多思考 + 学好英语！
 
唯有努力💪
 
【每日一读】每天浅读一篇论文，了解专业前沿知识，培养阅读习惯（阅读记录 仅供参考）

论文简介

原文链接：https://dl.acm.org/doi/10.1145/3292500.3330941

会议：KDD '19: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining （CCF A类）

年度：2019年7月25日（发表日期）

ABSTRACT

随机游走被广泛应用于从网络嵌入到标签传播的各种网络分析任务中。它可以捕获几何结构并将其转换为结构化序列，同时缓解稀疏和维度灾难的问题。尽管已经对普通网络上的随机游走进行了深入研究，但在现实世界系统中，节点通常不是纯顶点，而是具有不同的特征，由与其相关的丰富数据集描述。这些节点属性包含丰富的信息，通常补充网络，并为基于随机游走的分析带来机会。然而，尚不清楚如何为属性网络开发随机游走以实现有效的联合信息提取。节点属性使节点交互更加复杂，并且在拓扑结构方面是异构的。

为了弥合差距，我们探索在属性网络上执行联合随机游走，并利用它们来促进深度节点表示学习。所提出的框架 GraphRNA 由两个主要组件组成，即协作行走机制 - AttriWalk，以及用于随机行走的定制深度嵌入架构，称为图循环网络 (GRN)。

AttriWalk 将节点属性视为一个二分网络，并使用它来推动行走更加多样化，并减轻向具有高中心性的节点收敛的趋势。 AttriWalk 使我们能够将著名的深度网络嵌入模型、图卷积网络推进到更有效的架构 - GRN。 GRN 使节点表示能够以与节点在原始属性网络中交互相同的方式进行交互。与最先进的嵌入算法相比，真实世界数据集的实验结果证明了 GraphRNA 的有效性。

1 INTRODUCTION

随着社交媒体 [35] 和蛋白质-蛋白质相互作用网络 [10] 等网络系统的普及，网络分析在实践中得到了广泛的应用。随机游走是一种基本工具，已被证明在各种网络分析任务中有效，例如网络嵌入 [9, 34]、链接预测 [1] 和推荐 [32]。随机游走是在节点之间连续移动的随机过程。它通常用作对局部拓扑结构进行采样并将复杂节点交互转换为结构化序列的关键功能。已经证明，在一定的约束条件下，普通随机游走的转移概率等价于归一化切割和谱分割[30, 40]。由于行走是自然地以分布式方式进行的，基于随机行走的方法具有对稀疏性和高维度鲁棒性的良好特性[32]。但是，随机游走带来的限制也可能会限制分析性能。普通随机游走倾向于收敛到具有高中心性的节点 [28, 32]，这由它们的数学属性 [30] 决定。正如在许多应用中经验性地验证的那样 [5]，这种趋势会使学习结果的判别性降低。

虽然对普通网络上的随机游走进行了深入研究 [1, 34]，但在现实世界的系统中，节点通常不是纯顶点，而是与丰富的属性数据相关联，即节点属性，描述节点的特定特征。这样的系统被称为属性网络[12, 22]。示例包括带有推文的 Twitter 网络和带有论文摘要的学术网络。除了用于表征节点属性的网络交互之外，节点属性还提供了丰富且高度相关的辅助信息 [36]。例如，在亚马逊联合采购网络中，一起购买的产品往往会收到主题相似的评论 [29]。大量评论还可以作为可靠的资源，供客户查找产品属性并做出明智的购买决定。这些节点属性可能用于推进基于随机游走的分析。然而，在属性网络上开发有效的随机游走以实现联合信息提取是一项艰巨的任务。此外，鉴于从属性网络中学习到的结构化步行序列，在保持良好的步行特性的同时，将它们用于各种现成的分析算法（如 SVM）仍然具有挑战性。

在众多网络分析技术中，深度网络嵌入架构，尤其是图卷积网络 (GCN) 已引起广泛关注 [3, 17]。学习到的节点表示可以保留原始网络信息，并直接用作节点特征来推进各种下游应用，例如节点分类 [17]、网络聚类 [40] 和异常检测 [27]。卓越的经验性能及其灵活的参数化架构促使我们将它们与随机游走相结合，以在属性网络上进行更有效的节点表示学习。最近的研究 [10, 43] 试图利用 GCN 将随机游走纳入深度网络嵌入。然而，它们只采用传统的随机游走，GCN 中的聚合操作没有考虑节点顺序信息 [16]。

我们建议在属性网络上执行有效的随机游走，并通过深度学习技术对提取的信息进行卷积以进行节点表示学习。然而，这仍然是一项具有挑战性的任务。

• 首先，节点属性相对于拓扑结构是异构的[13]。简单地将它们插入现有的基于随机游走的模型可能会在降低性能的同时增加计算负担。
• 其次，节点属性使节点交互更加复杂。为了揭示属性网络中复杂的节点交互和非线性相关性，需要有适当的联合随机游走机制和有效的嵌入算法。
• 第三，为了充分利用从属性网络中学习到的结构化步行序列，需要一种符合步行的嵌入算法。因此，我们的目标是定制深度嵌入架构，以与属性随机游走相耦合并保留良好的步行特性。

为了弥合这一差距，我们提出了一种新的属性网络嵌入框架，名为 Graph Recurrent Networks with Attributed random walks (GraphRNA)，由名为 AttriWalk 的有效联合行走机制和结合循环神经架构优势的定制图循环神经网络和 AttriWalk 组成.

具体来说，我们旨在调查两个研究问题。

• (i) 如何利用异构信息、节点属性来缓解普通随机游走的局限性并进行信息丰富的联合随机游走？
• (ii) 如何利用学习到的属性随机游走，有效地模拟属性网络中复杂的节点交互和非线性相关性？

我们将我们的主要贡献总结如下。

• 图RNA。我们定义了一个名为基于随机游走的属性网络嵌入的新问题，并提出了一个有效的框架——GraphRNA，来解决这个问题。
• 归因于随机游走。我们设计了一种联合游走机制 AttriWalk，它将节点属性视为一个二分网络，并利用它来推动随机游走更加多样化，并减轻向高中心性节点收敛的趋势。
• 图循环网络。基于 AttriWalk，我们将图卷积网络推进到一种更有效的神经架构，称为图循环网络，其中节点表示被允许以与节点在原始属性网络中交互相同的方式进行交互。
• 评估。我们凭经验验证了 GraphRNA 在三个真实世界属性网络上的有效性。

2 PROBLEM STATEMENT

符号：在本文中，我们用大写粗体字母表示矩阵（例如 G），用小写粗体字母表示向量（例如 g），用小写字母表示标量（例如 ä）。矩阵或向量的转置表示为 G⊤ 或 g⊤。我们用 gi 来表示 G 的第 i 行，用 дi j 来表示 G 的第 i 行和第 j 列中的元素。我们用 {ri } 来表示向量 ri 的序列。操作 z = [x, y] 表示将行向量 x 和 yin 连接成一个新的行向量 z。

我们在表 1 中总结了主要符号及其定义。设 V 是现实世界信息系统中的一组 n 个节点，由一个无向网络连接，加权邻接矩阵表示为 G ∈ Rn×n。对于每对节点 i 和 j，如果它们之间没有联系，则 w j 将为 0，较大的 w j 表明它们的关系往往更强。除了链接关系，每个节点 i ∈ V 还与一个高维描述性特征向量 ai 相关联，称为节点属性。我们使用矩阵 A ∈ Rn×m 来收集所有节点属性。这种类型的网络 G = (V, G, A) 被定义为属性网络。为了使问题在物理上有意义，我们假设 G 和 A 的元素都是非负的。

随机游走已被广泛用于对各种网络分析任务中的拓扑结构进行建模 [1、32]。虽然在普通网络上基于随机游走的嵌入已经得到很好的研究 [9, 34]，但节点属性为随机游走和嵌入带来了机会。基于上述术语，我们首先正式定义了属性网络嵌入（ANE）[8, 12]，然后提出了基于随机游走的 ANE 问题。

定义 1（属性网络嵌入）给定属性网络 G = (V, G, A) 和预定义的小维度，目标是学习映射 f : {G, A} → H，其中 H ∈ Rn×d ，每一行 hi 对应节点 i ∈ V 的嵌入表示，这样 G 所描述的关系信息和 A 所表征的节点属性信息可以尽可能地保留在 H 中。这个映射 f 的有效性评估基于直接应用于实际应用（如节点分类）时 H 的有效性。

归因网络嵌入最近引起了相当大的关注，因为它作为连接现实世界高维网络数据和现成分析算法的桥梁[11]。然而，ANE 仍然是一项具有挑战性的任务 [13]。鉴于随机游走的良好特性，例如对稀疏性具有鲁棒性并且符合光谱分割，我们建议利用随机游走来提高 ANE。我们正式定义这个问题如下。

定义2（Random-walk-based Attributed Network Embedding）目标是开发一个符合ANE数据特征的框架，包括复杂的节点交互，非线性相关性和异构信息源，同时保持随机游走带来的良好特性。

3 ATTRIBUTED WALKS BASED EMBEDDING

为了有效地执行基于随机游走的属性网络嵌入，我们提出了一种名为 GraphRNA 的新型深度嵌入框架。

核心思想是在属性网络上执行联合随机游走以模拟属性节点交互，并涉及递归神经架构来嵌入非线性相关性。

图 1 说明了 GraphRNA 的详细信息。我们将这个统一的框架大致分为三个组件来介绍。

首先，我们定义了一个统一的行走机制来采样复杂的属性节点交互。如图 1 所示，为了在网络和节点属性内实现联合游走，我们构建了一个基于节点属性的二分网络 A。

节点会有一定的概率跳转到属性类别，这增加了游走的多样性。

因此，我们将复杂的属性节点交互转换为一系列信息丰富的节点索引序列 T。

其次，我们开发了一种名为图循环网络的有效深度架构来执行基于 T 的嵌入。它允许节点表示在模型内交互，就像节点在原始网络 G 中交互一样。我们为 T 中每个序列中的每个节点索引学习 d 维向量表示。

第三，对于每个节点 i ∈ V，我们采样少量的序列，它们都以 i 作为起始节点，表示为集合 τi。为了计算 i 的最终嵌入表示，我们应用池化方法来融合 τi 中节点索引的所有向量表示。我们现在介绍细节。

3.1 Attributed Random Walks - AttriWalk

在本节中，我们研究在属性网络上执行随机游走，其中节点不仅以网络交互 G 为特征，而且还以节点属性 A [12, 25] 描述的丰富辅助信息为特征。联合采样 G 和 A 会使随机游走提供更多信息 [36]。

随机游走将充当帮助我们提出的深度嵌入架构处理几何结构的桥梁。深度神经网络已被证明可有效建模多种类型的非结构化数据，例如自然语言、图像和音频 [20]。然而，当直接应用于模型拓扑结构时，鉴于网络位于不规则或非欧几里得空间 [6] 内，现有的深层架构通常会实现次优性能。虽然已经尝试基于图卷积网络 [16、17] 或复杂的目标函数 [8、21、25、26、44]，但我们探索利用随机游走将不规则属性网络 G 转换为结构化数据。然而，这是一项具有挑战性的任务，因为节点属性位于与网络不同的数据结构中。

3.1.1 直观的解决方案。为了联合采样网络和节点属性信息，一个直观的解决方案 [12, 35] 是基于 A 构建一个新的网络 S，其中节点 i 和 j 之间的边权重定义为 ai 和 aj 之间的相似度。通过这种方式，A 被转换为拓扑结构 S。在 G 和 S 上进行联合随机游走很简单。但是，这种直观的解决方案很昂贵。计算 S 的时间复杂度为 O(nNA )，其中 NA 表示 A 中非零元素的总数。此外，在实践中，如幂律所描述的，会存在一些高频属性类别。他们可以使 S 致密。因此，Swold 上的计算、存储和行走都具有很高的时间和空间复杂度。

3.1.2 统一行走机制。为了处理异构信息并有效地对属性节点交互进行采样，AttriWalk 定义了一个统一的步行机制。关键思想是基于节点属性构建一个二分网络A，并利用它来推动随机游走更加多样化，并缓解向具有高网络中心性的节点收敛的趋势。我们现在详细描述它。

为了平衡G和A中的元素，我们首先采用ℓ1范数对G和A的每一行分别进行归一化，得到̄G和̄A。然后我们将所有 m 个节点属性类别收集为一个集合，记为 U。通过将每个节点属性类别 δk ∈ U 视为一个节点，我们可以定义一个新的二分网络为 A ≜ (V, U, E)，其中 E 表示相应的边集。如果节点 i 包含属性 δk，则节点 i ∈ V 和 δk ∈ U 之间存在一条边。这条边的权重定义为 ̄aik ，即 ̄A 的第 i 行第 k 列的值。

提议的 Attriwalk 将在所有这些 n + mnode 之间跳转。假设当前我们已经跳转到节点 i ∈ V。如图 1 所示，为了确定下一个转换，我们翻转一个偏硬币，该硬币产生正面的概率为 α。

A 上的步行增强了 AttriWalk 的多样性和灵活性。在行走过程中，V 中的节点不仅可以基于网络 ̄G 进行交互，还可以通过节点属性 categoriesU 进行交互。当 α = 1 时，AttriWalk 屈服于网络上的普通随机游走。随着 α 的减小，游走将更多地依赖于节点属性。相应的转移概率矩阵可以写成，

需要注意的是，P的每一行之和为1。

3.1.3 理论性质。 AttriWalk 定义了网络 ̄G 和 A 内的统一游走。̄G 上的游走继承了传统随机游走 [30, 34, 40] 的良好特性，包括符合归一化切割和光谱分割。 A 上的游走也遵循对称节点相似度矩阵，可以将其视为一个新网络，如定理 3.1 中所述。

定理 3.1。在 AttriWalk 中，当硬币转头时，从节点 i ∈ V 通过任何属性类别走到另一个节点 j ∈ V 的概率，遵循定义如下的相似度矩阵 S

其中 D 是对角矩阵，dkk = 1∑n q=1 ̄aqk 。

证明。假设我们从节点 i ∈ V 走到任意属性类别 δk ，那么从 δk 到节点 j 的过程独立于从 i 到 δk 的过程。因此，我们计算从 i 跳到 j 的概率为：

我们可以使用别名方法 [7] 从离散概率分布中采样，总共需要走 O(n) 步。与直观解的时间复杂度 O(nNA + n2 + n) 相比，AttriWalk 的时间复杂度为 O(NA + n)。

3.1.4 采样设置。基于 AttriWalk，我们对所有节点的局部拓扑结构和节点属性进行采样。我们采用如下设置。所有随机游走都将被截断为长度 L。对于每个节点 i ∈ V，我们进行固定数量 B 的固定长度游走。他们都使用 i 作为初始节点。我们将所有 B 个学习的节点索引序列表示为一个集合 τi。我们收集所有节点的学习序列作为集合 T。例如，在图 1 中，我们有 B = 2，L = 6，并且设置 τ1 = {{1, 4, δ4, 3, 2, 5}, {1, δ3, 6, 4, δ4, 4}} .通过这种方式，我们将复杂的属性节点交互转换为一系列信息丰富的节点索引序列 T。

3.2 Graph Recurrent Networks - GRN

我们现在研究通过利用学习序列 T 来执行有效的嵌入。一种广泛采用的方法 [9, 34] 是将序列视为句子，将节点视为单词，并应用单词嵌入技术 [31] 来学习每个单词的潜在表示。这种方法已被证明在普通网络中是有效的。然而，在属性网络中，节点属性也受节点属性的影响。词嵌入模型无法考虑这些辅助信息。另一项工作 [10, 43] 利用图卷积网络 (GCN) 将随机游走纳入深度学习模型。但是 GCN 中的聚合操作没有考虑节点顺序信息 [16, 17]。

3.2.1 提出的神经架构。 T 中的序列描述了节点如何通过拓扑结构和节点属性与邻居交互。递归神经网络 (RNN) 中的隐藏状态序列自然符合这些采样节点交互。因此，我们探索利用 RNN 对 T 中的订单信息进行建模。所提出的图循环网络的架构如图 2 所示，详细信息如下。

I. 令 {1, δ3, 6, 4, δ4, 4} 为 τi 中长度为 L 的序列。我们将每个 L 个索引映射到一个 m 维向量。如果它是节点 j ∈ V 的索引，那么我们将它映射到它的节点属性 aj 。如果它是属性类别 δj ∈ U 的索引，那么我们将其映射到第 j 个元素等于 1 的 one-hot 向量 ej。

二、我们采用全连接层来降低节点属性的维数，并得到向量 {xj }，对于 j = 1, 。 . . , L. 在数学上，xj 的计算基于，

其中 σ 是 sigmoid 函数，Wa ∈ Rm×d 是权重矩阵。它的每一行 wj 对应于节点属性类别 δj 的潜在表示。因此，当输入序列中有索引δj 时，ej 将帮助它查找 wj。

三、给定 {xj }，我们使用**双向 RNN，**例如长短期记忆和门控循环单元 [2] 来学习前向隐藏状态序列（-→r1，-→r2，…，-→rL）和后向隐藏状态序列（←-r1，←-r2，…，←-rL）。每个隐藏状态都可以解释为一个节点，RNN 使节点能够与前向和后向邻居交互。它符合原始网络G中节点交互的方式。此外，相应的节点属性已经传输到每个隐藏状态，这使得异构网络和节点属性信息以一种自然的方式融合。

我们以前向隐藏状态序列 {−→rj } 为例。在数学上，−→rj 是通过以下方式计算的，

fj 、 ij 和 oj 表示遗忘门、输入门和输出门的激活向量。 cj 表示细胞状态向量。 ◦ 表示 Hadamard 产品。 tanh 表示双曲正切函数。这个双向 RNN 层的输出是通过连接前向和后向隐藏状态向量获得的，即 rj = [−→rj , ←−rj ]。

四。对于每个节点 i ∈ V，在其序列集 τi 中完全有 BL 索引。相应地，我们可以从双向 RNN 层获得 BL 嵌入向量 {rj }。我们遵循一个经过充分研究的架构 [10, 43] 来计算节点 i 的最终嵌入表示。我们首先应用一种池化方法将所有 B 序列合并为一个，记为 {̄r1, ̄r2, . . . , ̄rL }。然后我们再次应用池化方法来合并所有的 {̄r2, ̄r3, . . . , ̄rL } 转化为 ^ri 。最终的嵌入表示 hi 定义为，

需要注意的是，τi 中的序列必须以索引 i 开始。因此，̄r1 是节点 i 在第二次池化之前的潜在表示。

3.2.2 与图卷积网络的关系。 GCN 的关键思想是将节点属性或可训练的嵌入查找表输入到一个特殊的多层感知器中，其中每个节点的表示是通过平均其在前一层 [10, 16] 中的邻居表示来学习的。它可以被认为是谱图卷积的一阶近似[6, 17]。

GCN 可以解释为我们提出的图循环网络（GRN）的一个特例。如果我们移除 GRN 中的双向 RNN 层，随着采样 B 的数量不断增加，GRN 中的池化操作将接近于从所有邻居中进行归纳学习。一些努力 [4, 43] 还表明，从多跳邻居中随机抽样将提高 GCN 的性能。属性随机游走使我们能够通过考虑节点交互顺序信息来提升 GCN。 GCN 通过层到层实现节点交互，而 GRN 使节点和属性类别能够在同一个双向 RNN 层内交互。 GCN 对多层不鲁棒，因为它会变得过度平滑 [24]。因此，节点只能在 GCN 中交互几次。但在 GRN 中，双向 RNN 层允许更长的交互。

3.3 Optimization

GraphRNA 可以在无监督、有监督或半监督设置下进行训练。这个不错的属性继承自 GCN [10, 17]。损失函数不是本文的重点。我们以监督设置为例。基于交叉熵误差，目标函数可以定义如下，

其中 yi 是一个 one-hot 向量，表示节点 i 的标签。将 L 替换为其他特定于任务的目标函数很简单，例如基于负采样的无监督目标函数 [10, 38]。

我们总结了算法 1 中 GraphRNA 的优化。给定一个属性网络 G = (V, G, A)，我们首先对 Gand A 进行归一化以构造 P。它总结了 G 和 A 内联合随机游走的转移概率。我们使用别名方法 [7] 从 P 中的离散概率分布中对截断的随机游走进行采样。对于每个节点 i ∈ V，我们对 B 序列进行采样并将它们附加到 τi 。它们都以 i 作为起始节点。我们使用 τi 和节点 i 的标签来训练 GRN，基于方程中的目标函数 L。 (14) 。在几个 epoch 训练 GRN 之后，我们使用它将 τi 嵌入到 hi 中。

4 EXPERIMENTS

5 RELATED WORK

归因网络嵌入弥合了现实世界网络系统和下游分析算法之间的差距。我们将现有的 ANE 模型大致分为如下两类。

浅归因网络嵌入。为了结合拓扑结构和节点属性，已经从不同方面进行了尝试[12、14]。齐等人。 [35]专注于多媒体对象，并通过联合建模它们的内容信息相似性和上下文链接来学习它们的潜在语义表示。 Le 和 Lauw [19] 通过合并文档之间的链接来推进主题建模。杨等人。 [41]将网络转换为逐点互信息，并采用矩阵三因子化来联合嵌入属性网络。潘等人。 [33] 设计了一个基于耦合随机游走的模型，该模型具有三个目标，以结合网络、节点属性和标签。黄等人。 [11]通过将ANE分解为许多独立的子问题并以分布式方式优化来加速ANE。李等人。 [22] 设计了一种在线 ANE 算法来处理动态场景。杨等人。 [42] 提出利用 Weisfeiler-Lehman 图核来学习属性网络的二进制向量表示。还提出了几种基于耦合矩阵分解的 ANE 方法 [23, 45]。

深度属性网络嵌入。鉴于丰富的训练数据变得可用，一系列有效的深度 ANE 算法已经被开发出来。张等人。 [3] 涉及非线性多层嵌入函数，以协同嵌入异构网络和节点内容。 Kipf 和 Welling [16, 17] 引入了图卷积网络，作为 K 局部谱图卷积的一阶近似，将卷积运算从空间域扩展到非欧几里得空间。汉密尔顿等人。 [10]提出了归纳表示学习，其中每个节点的表示是通过聚合其所有邻居的表示来学习的。梁等人。 [25] 通过使用双输入和双输出神经架构推进了归纳表示学习。另一条研究方向是基于复杂的目标函数执行联合嵌入[8,21,26,44]。最近，人们还致力于利用图递归神经网络来进行节点或图表示嵌入 [15, 37]。

6 CONCLUSION AND FUTURE WORK

在网络分析中对平面图上的随机游走进行了深入研究。尽管它已经显示出突出地位，但在开发基于随机游走的属性网络技术以对异构信息进行编码从而增强节点表示学习方面进行了罕见的探索。为了弥补这一差距，我们提出了一种优雅的行走机制——AttriWalk，它可以在网络和节点属性内进行协作采样。受表示学习中深度学习技术的最新进展的启发，我们进一步在 AttriWalk 上设计了一个定制的图神经网络架构，名为 GraphRNA，以进行属性网络嵌入。 GraphRNA 基于 AttriWalk 将复杂的属性节点交互转换为一系列信息丰富的节点索引序列，并通过图循环网络将它们编码为统一的向量表示。对真实世界数据集的评估证明了 GraphRNA 与不同基线相比的有效性。

对于未来的工作，由于图循环网络自然适用于序列数据，我们打算开发一种在线更新方案，用于在动态网络中编码时间漂移信息。另一个有价值的方向是探索其他有意义的池化方法，除了本文采用的均值池化用于联合表示。

结语

文章仅作为个人学习笔记记录，记录从0到1的一个过程

希望对您有一点点帮助，如有错误欢迎小伙伴指正