《Embedding Temporal Network via Neighborhood Formation》--- 论文笔记

HTNE是北航老师提出的针对时序网络(temporal network)嵌入的一个模型,论文发表在2018年KDD上。时序网络,即网络是随时间动态变化的(节点和边会增加或减少)。文章研究了时序网络的embedding问题,旨在建模网络的时序形成模式,从而提升网络embedding的效果。

文章通过节点的邻居形成序列(neighborhood formation sequence)建模节点的演变过程,然后利用霍克斯过程(Hawkes process)捕获历史邻居对当前邻居形成序列的影响,从而得到节点的embedding。由于历史节点对当前邻居形成会有不同的影响,论文还采用attention机制,学习历史邻居对当前邻居的影响权重。

1、Movitation

已有的一些network embedding方法大多聚焦于静态网络,也就是网络的结构是保持不变的,节点和边的数量不会发生变化。因此这些方法通常有一个假设:一个节点的邻居是无序的,也就是它们通常忽略连接(link)的形成过程。因为网络在动态变化时,节点的邻居不是同时增加的,连接也不是一蹴而就的增加。如果只是观察网络的一个快照(snapshot),只能观测到一个时间段内网络的积累,而忽略了节点增加的这个过程(什么时候,怎么增加)。因此,网络中边的建立是通过序列事件逐渐建立的,即定义为时序网络(temporal network)。建模网络中节点和邻居建立连接的过程,可以更好的反映出网络的动态变化。

2、Model

论文首先给出了时序网络(temporal netowork)的定义 $\mathcal{G}=\langle\mathcal{V}, \mathcal{E}; \mathcal{A} \rangle$,其中$\mathcal{V, E}$分别表示节点和边的集合,$\mathcal{A}$表示事件(event)集合。每条边 $\langle x,y \rangle$ 可以看作是按时间先后顺序排列的事件,即:$\mathbf{a}_{x,y}=\{a_1\to{a_2}\to{…}\}\subset\mathcal{A}$,其中 $\mathbf{a}_i$表示在事件i时刻的一个事件。

在时序网络中,根据一个节点与其邻居建立连接的时间,从前到后组织为一个序列,这个序列也就反应了节点(网络)演变的过程。论文中形式化定义了邻居的形成序列。给定一个源节点(source node)$x\in{\mathcal{V}}$,其邻居定义为:$\mathcal{N}(x)=\{y_i=1,2,3,…\}$,源节点与邻居节点(目标节点)的边可以看作是按时间顺序排列的事件 $\mathcal{a}_{x,y_i}$。因此,邻居形成序列可以定义为一些列目标节点到达事件,即:$\{x:(y_1,t_1)\to(y_2,t_2)\to…\to(y_n,t_n)\}$,其中每一个元组表示一个事件:在 $t$ 时刻,节点 $ y_i$ 和 $x$ 建立联系,成为其邻居。

图示是时序网络的一个简单实例以及邻居形成序列。可以看到,如果只是观察网络的一个快照片,那么只能通过边上的权重反映出来。而通过邻居形成序列(图b),节点的邻居可能出现不止一次,可以显式地建模出网络中边的形成过程。同时,目标节点之间可能会相互影响(1是源节点,其邻居是目标节点),也就是说历史的邻居会影响当前邻居的形成。这个影响可能会因为节点的不同而不同,所以可以通过attention机制,学习其中的权重。

时序网络embedding目的在于:考虑网络中的时序信息,学习网络中节点的表示。这篇论文通过考虑邻居的形成序列,并考虑邻居间的相互影响,从而学习节点的表示。

论文基于Hawkes Process建模邻居形成序列。Hawkes 过程是一种典型的时序点过程(point process),其假设历史事件会影响当前事件的发生,以此建模分离的时序事件。在point process 中,通常定义一个条件强度函数(conditionl intensity function),描述序列事件的到达率(发生率)。因此,对于一个源节点 $x$,目标节点 $y$ 与其建立连接的条件强度函数可以定义为:

其中 $\mu_{x,y}$ 是 $x$和 $y$ 之间建立边的基强度,$h$ 是邻居形成序列中的历史目标节点,也就是说在 $t$ 时刻之前,$h$ 和 $x$ 是已经建立连接的。$\alpha _{h,y}$ 表示历史邻居 $h$ 对当前邻居 $y$ 的影响度,$\kappa(·)$ 是一个核函数,表示随时间的衰减影响,通常表示为指数函数:$\kappa(t-t_h)=\exp(-\delta_s(t-t_h)$ 。这里的衰减率 $\delta_s$ 是一个依赖于源节点 $s$ 的参数,因为对于每个源节点,其历史邻居节点对当前邻居的形成是不同的。

为了学习节点的低维表示,假设节点 $i$ 的表示为 $\mathbf{e}_i\in{\mathbb{R}^D}$,然后将其送入强度函数(公式1),如果强度越大,节点应该更有可能建立连接。很明显,基强度反映了源节点和目标节点之间的相似性,越相似,基强度的数值也应该越大。因此,论文定义负的欧式距离平方(negative squared Euclidean)去度量节点间的相似度,即:

由于强度函数 $\lambda_{y|x}(t)$ 应该是正数值,而公式 (2) 是一个非正数值,所以论文采用指数函数将条件强度率转化为一个正数值,即:

其实这里也可以采用其他一些函数,论文这里使用指数函数主要是为了方便后面的求解。

考虑到不同历史节点对当前邻居节点(目标节点)的影响不同,而这个影响应该是和源节点有直接关系的(取决于目标节点),论文定义源节点和历史节点之间的权重:

所以历史节点对当前邻居节点(目标节点)的影响可以定义为:

注意这里目标节点和历史节点之间的类似性 $ f(\mathbf{e}_h,\mathbf{e}_y) $ 也定义为负的欧式距离平方(negative squared Euclidean),主要是和前面的保持一致。

至此,给定历史事件,在t时刻,源节点和目标目标节点建立边的强度 $\lambda_{y|x}(t)$ 已经给出完整定义。因此,源节点和目标节点之间建立边的概率就可以定义为:

对于网络中所有节点,邻居形成序列的log-likehood(似然函数)可以定义为(即优化目标):

根据公式 (3)和公式 (6),可以得到 $p(y|x, \mathcal{H}_x(t)) = \frac{\exp{(\tilde{\lambda}_{y|x}(t)})}{\sum{\exp{…}}}$,,所以最大化公式 (7)可以通过负采样的简化计算,最后的优化优化目标为:

其中 $\sigma(·)=\frac{1}{1+\exp(-x)}$ 是一个sigmoid函数。

需要注意的是,因为历史邻居序列的长度影响强度函数的计算复杂度,论文固定最大邻居序列长度,并且只保留最近的目标节点。

3、Experiment

实验部分,论文首先通过节点分类链路预测验证了节点表示的有效性,然后验证了通过时序推荐任务验证了条件强度函数的有效性,最后是网络可视化和参数实验。

节点分类和链路预测任务比较常规,具体分析和结果可以参考论文。值得注意的是,这里的时序推荐任务(temporal recommendation),本质上是一个排序任务,只不过训练集和测试集的划分按照时间节点划分。论文以条件强度函数作为两个节点是够建立连接的概率(评分 ranking score),用t时刻以前的数据作为训练,然后预测t时刻之后,给定节点的之间建立连接的可能。

4、Summary

总结一下,不同于常规的network embedding模型,这篇论文立足于temporal network embedding问题,考虑了真实网络的动态变化性,这应该是一个比较大的亮点。其次,论文从邻居节点的形成序列描述网络的动态演变模式,也是一种比较新颖的角度,这一点感觉和最近很火的graph convolution network有一些相似(从邻居聚合节点的表示)。最后,论文很好的利用了point process 中的Hawkes process去建模这种时间序列事件,同时采用attention机制考虑不同节点之间的不同影响,最终将问题转化为最大似然估计问题求解。论文写作也挺好,实验也比较充分,基本验证了模型的各个方面。

在看这篇论文过程中,同时也有几个问题。首先是强度函数没有考虑历史节点之间本身存在的联系,每个历史节点对当前节点的影响也只是简单叠加,是不是可以考虑的更复杂一些?其次,对于历史邻居序列的长度,如果考虑有很多邻居很长,就会导致 $\lambda$的计算复杂度较高,所以论文只考虑较短的邻居序列,这样是否会损失很多信息?同时,对于条件强度函数中的 $\delta_s$ 是如何取值确定的,论文好像没有给出说明,不清楚这个是不是Hawkes process 中的常见参数,且有常用取值。最后,论文实验部分的,每个数据集中有静态边和时序边,论文好像没有叙述清楚具体的实验是怎么进行的。

写的还不错?那就来个红包吧!
0%