Embedding Temporal Network via Neighborhood Formation

转载 2020-06-17 21:52  阅读 32 次 评论 0 条

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)\(xin{\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\) 与其建立连接的条件强度函数可以定义为:

\(\tilde{\lambda}_{y|x}(t)=\mu_{x,y}+\sum_{t_h<t}{\alpha_{h,y}\kappa(t-t_{h})} \)

其中 \(\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}_iin{\mathbb{R}^D}\),然后将其送入强度函数(公式1),如果强度越大,节点应该更有可能建立连接。很明显,基强度反映了源节点和目标节点之间的相似性,越相似,基强度的数值也应该越大。因此,论文定义负的欧式距离平方(negative squared Euclidean)去度量节点间的相似度,即:

\(\mu_{x,y}=f(\mathbf{e}_x,\mathbf{e}_y)=-||\mathbf{e}_x-\mathbf{e}_y||^2\)

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

\(\lambda_{y|x}(t)=\exp(\tilde\lambda_{y|x}(t))\)

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

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

\(w_{h,x} = \frac{\exp(-||\mathbf{e}_x-\mathbf{e}_h||^2)}{\sum_{h'}{\exp(-||\mathbf{e}_x-\mathbf{e}_{h'}||^2)}}\)

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

\(\alpha_{h,y}=w_{h,x}f(\mathbf{e}_h,\mathbf{e}_y)=w_{h,x}(-||\mathbf{e}_h-\mathbf{e}_y||^2)\)

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

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

\(p(y|x, \mathcal{H}_x(t)) = \frac{\lambda_{y|x}(t)}{\sum_{y'}{\lambda_{y'|x}(t)}}\)

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

\(\log \mathcal{L}=\sum_{xin{\mathcal{V}}}{\sum_{yin{\mathcal{H}_x}}}{\log{p(y|x,\mathcal{H}(t))}}\)

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

\(\log{\sigma{(\tilde{\lambda}_{y|x}(t)))}}+\sum_{k=1}^K{\mathbb{E}_{v^ksim{P_n(v)}[-\log(\tilde{\lambda}_{v^k|x}(t)))]}}\)

其中 \(\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 中的常见参数,且有常用取值。最后,论文实验部分的,每个数据集中有静态边和时序边,论文好像没有叙述清楚具体的实验是怎么进行的。

本文地址:http://51blog.com/?p=10638
关注我们:请关注一下我们的微信公众号:扫描二维码广东高校数据家园_51博客的公众号,公众号:数博联盟
温馨提示:文章内容系作者个人观点,不代表广东高校数据家园_51博客对观点赞同或支持。
版权声明:本文为转载文章,来源于 大专栏 ,版权归原作者所有,欢迎分享本文,转载请保留出处!

发表评论


表情