目前对于图的研究主要是基于静态图网络的表示学习，对于动态图网络的表示学习，大部分是基于特定的应用场景的，因此，本文（《Learning Representation over Dynamic Graphs》）提出了一种动态图网络的通用框架DyRep。DyRep将动态图网络的改变划分为两个过程：associate过程和communication过程，对连接两个过程的潜在中介过程进行建模，保证学习出的节点表示是综合两个过程后的结果。DyRep最终输出的节点表示由三部分组成：局部传播、自传播、外力驱动，其中局部传播为本文关键所在。局部传播是对网络结构信息的提取和聚合，聚合过程中使用动态变化的attention来区分网络结构中各个邻居节点的重要性。文章定义了节点对强度函数，使用强度函数定义损失函数，通过最小化负对数似然进行无监督学习。DyRep作为一种inductive的图表示方法，可以处理新增节点，也支持节点属性、边属性的添加。

1、摘要

由于图表示学习的普适性，图表示学习也受到了广泛的关注。目前，大部分的图表示学习方法还是基于静态图网络的，对于动态图网络的表示学习，依然还处在一个发展阶段。动态图网络表示学习有两个基本的问题：(i)如何对图的动力学过程进行建模；(ii)如何有效的对动态图信息进行低维表示。文章提出了一种新颖的动态图网络模型框架——DyRep，考虑网络拓扑结构和节点交互的变化，将动态网络拆分成两个过程：association process和communication process，表示学习可看做是这两个过程之间的中介，将两个过程有效的连接起来。DyRep使用无监督的方法进行训练，能够处理新增节点，是一种inductive的图表示方法。

2、问题背景

图表示学习在机器学习中扮演着重要角色，在社交网络、生物信息、自然语言处理、推荐系统等领域，都具有广泛的应用。动态网络中，边是动态的变化的，节点是动态的，会动态增加或减少，甚至属性也是动态变化的。动态图网络更符合实际情况，但由于整个图结构是动态变化的，研究起来也更困难。目前对于动态网络的的表示主要有两种方式：snapshot和Continuous-Time Approach：

• snapshot：将时序图网络离散化，拆分成多个时刻的静态网络  ，其中 即为  时刻的静态网络，是一种粗粒度的图表示方法，一般通过聚合函数将多个网络表示结果进行聚合，得到最终表示。
• Continuous-Time Approach：将整个时序过程中产生的关系都记录下来，通过时间戳来区分。在某些特定的任务中，这种方法表现很好，其模型要么分离为简单的结构和复杂的时间属性，要么直接使用简单的时序模型。

现实中，随着复杂动力学的演化，往往存在高度非线性结构，如何高效的从复杂结构中挖掘信息仍是一个待探索和解决的问题。文章将动态图网络划分为两个基础过程：Association Process和Communication Process：

• Association Process：关于当前网络的动态变化过程，会造成长期性的路径变化，会造成当前网络拓扑结构的改变，网络中节点增加、边的增加，均为Association Process。如在社交网络中，节点A和节点B成为了朋友，这种关系是未来长期存在的，会造成拓扑结构的改变。
• Communication Process：在当前网络上的动态过程，只是当前网络中已有节点之间的交互，不会引入新的节点和新的边。如在社交网络中，节点A和节点B参加了同一场会议，这种关系是一种临时性的短期关系，可能只发生一次， 不会造成网络拓扑结构改变。

Figure 1图中(a)对应于Association 事件（  ），新增节点和新增边造成网络拓扑结构改变，从而引起节点表示的变化，进一步会影响下一时刻网络发生Association 事件。图中(c)对应于Communication事件（  ），节点间发生短期的交互事件，造从而引起节点表示的变化，进一步会影响节点在下一时刻的交互。事实上，不论两个事件中哪一个事件造成节点表示变化，都会影响另一事件的发生，即associate->embedding->communication、communication->embedding->associate。因此，DyRep将节点表示学习的目标定位为对潜在的中介过程进行建模，该中介过程将上述两个基础过程联系起来，从而学习驱动两个过程的复杂时间动态，使节点表示随时间动态演化。

3、相关定义

：表示  时刻的图，其中  为节点集合，  表示边集合。

 ：表示节点  和节点  在  时刻发生事件  ，  ，  表示发生 topological evolution process (association process)，  表示发生node interaction process (communication process)

 ：表示在时间窗口[0,T]的事件集合。

 ：节点  的embedding表示。

4、DyRep

4.1、节点表示

文章将节点的表示可拆分成三部分：self-propagation(自传播)、exogenous drive（外部驱动）、localized embedding propagation（局部传播）。

• self-propagation：可以看做是控制单个节点演变的最小组成部分，是节点相对于其自身之前的位置的演变，而不是随机演变。
• exogenous drive：在一定的时间间隔下，某些外力可能驱动更新节点特征。
• localized embedding propagation：节点间形成临时的或长期的路径，信息从一个邻域传播到另一个邻域。

节点  在第  个事件的embedding可表示为：

(4)式中节点的表示聚合了图结构信息、自身先前的信息以及外部信息。参数  为当前事件的时间点，  为事件发生前的时间点，  为节点  前一个事件的时间点。

关于图结构信息的聚合，实际上是聚合了节点  的多个邻居节点  的信息，那使用什么样的方式聚合呢，如何判断每个邻居节点的重要性呢，下一节将进行详细介绍。

4.2、节点信息聚合

关于信息节点聚合，有一些常见的方法，如均值聚合、pooling、或者使用LSTM框架等，但这几种方法要么过于绝对，忽略了节点的重要性，要么过于复杂，使整个模型显得太过厚重。文章使用了Attention机制，这种机制广泛应用于NLP领域，图表示学习算法GAT（Graph Attention Networks）的核心思想也是应用attention来度量各个节点的权重。文章参考GAT中的attention思想，但与之不同的是，GAT是针对静态网络，而本文是针对于动态网络，这也是文章的一大亮点。通俗来讲，Attention机制是希望模型将注意力放到对当前任务更重要的信息上，忽略不重要的信息。

在localized embedding propagation部分，基于邻域结构捕获了丰富的结构信息，这也是图表示学习中很关键的一点。对于一个节点，不是所有的邻居节点都同等重要，为了能够尽可能获取对自身节点有用的邻居节点信息，文章使用attention来定义各个邻居节点的权重，并且考虑了网络动态变化对attention的影响。

以上公式中，使用attention度量节点的重要性，并采用max-pooling聚合节点信息。  定义了节点  与节点  之间的attention：

 为一个  矩阵，表示在  时刻，节点对之间的强度。

其中，  为最近一次节点的embedding。

4.3、条件强度函数

4.2节中已经提到，矩阵  是表示了节点对的强度，为了度量“强度”，文章定义了条件强度函数，在  时刻，对节点  和节点  的事件建模。

其中，  表示在当前事件之前的时间点，内部函数  计算了近期更新的两个节点间的兼容性：

[;]为聚合过程  为学习尺度特定兼容性模型参数。

外部函数  要满足两个关键点：计算结果为正值；区分associate和communication两个过程。

其中  对应于(1)式中的  ，  为学习到的标量时间参数，对应过程中发生相关事件的比例。下标  对动态图的两个变化过程进行了区分。

4.4 强度矩阵  的更新

动态网络要求attention要是动态的，即要求强度矩阵  是动态的，  会在两种情况下进行更新：拓扑结构的变化、节点间发生交互事件。参考邻接矩阵  对  进行初始化：  时，  时，  。  表示节点  的邻居节点的个数。随着时间的推移，会发生associate(  )和communication(  )两种事件，两种事件的对  影响程度不同的，associate是一个全局影响，communication是一个局部的影响。而邻接矩阵  只会在发生associate事件(  )时更新。  和邻接矩阵  的更新过程为：

 的更新案例参考：(a)为初始化，使用邻居节点个数初始化  ；(b)为节点  和节点  发生communication事件,如图虚线处，邻接矩阵  的不变，  发生局部变化，使用强度函数更新  和  ，其他不变；(c)为节点  和节点  发生了associate事件，如图曲线处，造成邻接矩阵  的更新，和强度矩阵  的更新。

4.5、模型训练过程

DyRep采用了无监督的学习过程，整个过程中待学习参数： 

整个模型训练通过最小化负对数似然实现，对于一个有  个事件的事件集合  ，loss function定义为：

其中  为条件强度函数：  ，  为各个节点对的条件强度函数值之和：

5、实验结果

本文在链路预测和事件概率预测两个任务上进行了实验。首先，链路预测任务，在两个数据集上对比了DyRep、GraphSage、node2vec等几种方法在链路预测上的效果，在两种动态图网络过程中进行了对比，图a-b为Communication Event Prediction Performance，图c-d为Association Event Prediction Performance。

事件概率预测，预测下一个时间点某个事件发生的概率，使用两个数据集，对比了DyRep、MHP、Know-Evolve三种方法的表现效果，显然DyRep表现最好。

在DyRep和GraphSage两种方法下，使用tSNE可视化对比节点表示的差异，很显然，DyRep可将节点表示得更为分散：

6、结论

本文提出了一种新的动态图网络表示学习方法，将动态图网络划分为两个过程，将表示学习作为潜在的连接两个过程的中间桥梁，学习网络中的时序结构信息，是一个通用的动态图表示学习框架。文章使用了基于时间点的动态的attention机制，可有效利用邻居节点的历史信息。DyRep可支持带有节点属性和边类型的网络，可在节点编码初始化时带入节点自身属性信息，也可在节点聚合时可区分边的类型后再进行聚合。此外，DyRep是一种inductive的图表示方法，可处理新增节点，对新增节点进行编码表示。