【AAAI2018】预测你的下一步-动态网络节点表示学习，浙江大学和南加州大学团队工作，代码已开源

2017 年 12 月 20 日 专知专知内容组（编）

【导读】以往的网络表示学习模型只会为固定的网络节点学习表示向量，而实际上，网络节点会根据时间的变化通过节点间的交互呈现出不同的网络结构特性。浙江大学和南加州大学团队提出了基于动态网络的节点表示的概念，利用DynamicTriad，在可以保存网络的结构信息的同时又保存网络的演化模式。该模型在链接预测上取得了不错的效果，而且方法未来可以有效地应用于识别移动网络中的电话欺诈，并预测网络中的用户是否偿还贷款。论文已经放出，代码也已开源。

论文：Dynamic Network Embedding by Modeling Triadic Closure Process

▌详细内容

动态网络嵌入（Dynamic Network Embedding）

所谓的“网络嵌入”（也称为“网络节点表示”）的目标是将一个图中的每个节点映射到一个低维空间中的向量上。这项任务最近吸引了相当多的研究工作，并且经常作为更复杂问题的一个基本的特征提取方法。现有的网络嵌入工作主要集中在静态网络[2,3]，然而，大多数现实世界的网络都将进化视为其自然的特征，并且有大量的研究集中在网络动力学的内在机制上[4,5]。

动态网络中的网络嵌入问题，即动态网络嵌入，已经变得越来越流行，一方面它继承了网络嵌入的所有优点——为图像提取可靠的压缩特征，另一方面它适用于动态场景，这在我们现实世界中是经常遇到的。据我们所知，目前还没有一种被广泛接受的动态网络嵌入算法在实践中被证明是运行良好的。

大多数现有的动态网络嵌入算法普遍持两种常见的假设，即社会同质性（social homophily）和时间平滑性（temporal smoothness）[6,7]。社会同质性假设包括在静态网络中已经研究得很好的各种结构性近似，而时间平滑性是指连续时间步长中同一顶点的投影之间的关系，这常常描述了一个“smooth”随时间的变化。然而，这些假设单独考虑空间和时间关系，导致它们难以捕捉复杂的网络演进模式（即结构变化模式）。

三元闭包过程和社交策略（Triadic Closure Process and Social Strategy）

为了将进化模式直接纳入考虑范围，我们尝试在动态网络嵌入算法中对一些基本模式进行建模。三角形是我们所熟知的一个社交网络的常见组成部分，三角形的闭合被认为是新边出现的最重要的因素之一[8]。因此，三元闭包过程是对在我们最新的论文AAAI 18[1]中提出的动态网络嵌入算法进行直接建模。

在社交网络中，三元闭包过程描述了这样的场景：当用户被他们的共同朋友介绍给对方。很明显，两个用户相互认识的概率取决于他们的共同朋友之间相互介绍的热切程度，我们称之为用户的社交策略（准确地说，我们讨论的并不止是“社交策略”的字面意思）。很明显，假设社交策略对于网络中的每个用户（顶点）是不同的。如下图所示，用户A倾向于在他/她的朋友之间引入新的链接，而用户B倾向于保持关系不变。

基于三元闭包过程的动态网络嵌入（Dynamic Network Embedding by Modeling Triadic Closure Process）

文章[1]的核心思想是根据用户的关系强度，建模用户介绍他/她的朋友的意愿，我们称之为社交策略，并将这些信息整合到用户的嵌入向量中。

所提出的算法定义了每个开三角的三元损失，根据三个顶点在潜在空间中的相对位置、顶点之间边的权重、下一次的开三角是否闭合，来计算这个损失。具体地，在时间步t中，给定有共同朋友k的两个无连接的用户i和j，三角形闭合的概率是

其中

由三角形中边的权重和顶点的嵌入向量的相对位置决定。

通过对在网络中采样的开放三角形的负对数闭合概率的求和，定义了三值闭合过程的总体损失。

通过总结在网络中被采样的开三角的负对数的闭合概率来定义三元闭包过程的整体损失。结合社会趋同性和时间平滑性的基本假设，我们先定义了每个假设的损失函数，然后将嵌入（embedding）任务转化为优化问题。用EM算法可以有效地解决优化问题。关于损失函数的详细介绍，可参阅文献[1]。

评价结果（Evaluation Results）

为了验证算法的有效性，我们进行了大量的实验，其中包括文献[1]中的“学术”数据集的顶点嵌入的可视化，如下所示

对“学术数据集”的第5个时间步中计算的原始嵌入向量进行可视化，并且根据从第6个时间步提取的信息标记顶点。使用t-SNE算法对嵌入进行2D平面投影，从而如上图可视化出来。

数据挖掘常常和其他领域有交叉融合，因此我们的可视化方法或多或少有其他社区的贡献，但是，我们的算法表现出比baseline更好的结果，这要归功于我们的模型把动态信息融入到嵌入向量中。

参考文献：

[1] Zhou, L; Yang, Y; Ren, X; Wu, F and Zhuang, Y, 2018, Dynamic Network Embedding by Modelling Triadic Closure Process, In AAAI, 2018

[2] Perozzi, B., Al-Rfou, R. and Skiena, S. (2014, August). Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 701-710). ACM.

[3] Grover, A. and Leskovec, J. (2016, August). node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 855-864). ACM.

[4] Sun, J., Faloutsos, C., Papadimitriou, S. and Yu, P. S. (2007, August). Graphscope: parameter-free mining of large time-evolving graphs. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 687-696). ACM.

[5] Zhuang, H., Sun, Y., Tang, J., Zhang, J. and Sun, X. (2013, December). Influence maximization in dynamic social networks. In Data Mining (ICDM), 2013 IEEE 13th International Conference on (pp. 1313-1318). IEEE.

[6] Zhu, L., Guo, D., Yin, J., Ver Steeg, G. and Galstyan, A. (2016). Scalable temporal latent space inference for link prediction in dynamic social networks. IEEE Transactions on Knowledge and Data Engineering, 28(10), 2765-2777.

[7] Heaukulani, C. and Ghahramani, Z. (2013, February). Dynamic probabilistic models for latent feature propagation in social networks. In International Conference on Machine Learning (pp. 275-283).

[8] Gamst, F. C. (1991). Foundations of social theory. Anthropology of Work Review, 12(3), 19-25.

原文链接：

https://luckiezhou.github.io/DynamicTriad/

▌论文

论文：Dynamic Network Embedding by Modeling Triadic Closure Process

摘要：

网络嵌入是一个重要的任务，它的目的是学习顶点的低维度表示，该领域最近也吸引了大量的研究工作。在现实世界，网络是动态的（比如社交网络和生物网络），它随着时间的推移而变化。然而，大多数现有的网络嵌入方法关注的是静态网络，而忽略了对动态网络的研究。

本文中，我们提出一个新颖的表示学习方法称为DynamicTriad，既可以保存网络的结构信息又可以保存网络的演化模式。我们的方法一般是利用三元组（包含三个顶点），作为网络的基本单位之一。特别地，我们模拟了一个由三个顶点相互连接组成的闭合三元组是如何从一个开放的三元组中发展而来的，这个三元组中的三个顶点中有两个没有相互连接。这种三元闭合过程是网络形成和演化的基本机制，从而使得我们的模型能够捕获网络的演变，并且在不同的时间步骤学习每个顶点的向量表示。

我们在三个真实的网络中进行实验，实验结果表明，与其他最新的技术相比，我们的DynamicTriad在多个应用场景中取得了实质性的进展。例如，我们的方法可以有效地应用于识别移动网络中的电话欺诈，并预测网络中的用户是否偿还贷款。

▌Github代码

代码链接：https://github.com/luckiezhou/DynamicTriad