刘旭昕作者

图神经网络之动态图

图这种结构普遍存在于人类社会生活中,如互联网中网页间的互相链接会构成图、网民购买商品会构成“网民-商品”图、人和人的交流会构成图、论文的互相引用也会构成图。有许多任务需要根据这些图的信息完成,例如根据用户和商品的历史交互,预测一个用户是否会购买一个商品或对它感兴趣;又如根据用户间的好友关系或交流记录,预测用户和用户之间是否构成好友关系。

因为经典的深度学习方法如RNN、CNN等不能直接使用到图这种结构中,最近几年图神经网络(Graph Neural Network)成为了深度学习的研究热点之一。图神经网络在对图中节点之间的依赖关系建模方面的强大功能使得与图分析相关的研究领域取得了重要突破。但这些图神经网络算法如DeepWalk[1]、GCN[2]等大多都是基于静态图(static graph)而不是基于动态图(dynamic graph)的,所以这些算法很多时候没有完整地使用上一个图中的所有信息。

静态图与动态图

一个图G=(V,E)由节点集合V以及边集合E组成,每个节点v∈V有自身的节点属性,每条边e∈E有自身的边属性。静态图指的是图的节点和边都是固定的,不会随时间变化。而实际上在现实世界中,图的节点和边往往都是动态变化的,边会动态增加(用户购买新的商品、用户关注另一个用户),节点会增加(新网页上线、新用户注册),节点的属性会变化(用户的属性会随时间变化)等。基于静态图去解决问题,虽然处理起来更简单,但不符合实际,预测效果也会大打折扣。动态图则认为图中的节点、边都是会动态变化的,会出现节点和边的动态增加、动态减少以及属性的动态变化。虽然动态图更符合实际,但因为要研究的目标是在图上动态变化的,可以想象研究难度会比静态图高不少。随着静态图算法的日趋成熟,不少研究人员开始在基于静态图的神经网络算法[1][2]的研究基础上提出了一些动态图算法,这里我们以两个代表算法CTDNE[3]和JODIE[4]为例介绍他们使用动态图来解决静态图局限性的思路。

CTDNE

CTDNE[3]是在DeepWalk基础上发展出来的算法框架,也是训练图中节点的embedding表示。在图1中,每条边可以代表现实生活中两个实体(如用户、商品等)的一次交互(如打电话、发邮件、关注等),边上的数字代表交互发生的时间。DeepWalk算法是基于静态图的算法,相当于忽略了边的发生时间,然后在图中随机选取一个节点作为起点,以随机游走(Random Walk)的方式采样出一条路径。在采样出大量的路径后,使用SkipGram的结构训练每个节点的embedding。但使用Random Walk采样因为忽略了边是动态增加的,往往会采样出不合理的路径,例如用户v1先发消息给v2,然后v2发给v3,v3发给v4,v4发给v1。但Random Walk可能会采样出路径v4-v1-v2,这条路径相当于跳过了v3,表达的意思就是由v4发消息给v1然后v1再发给v2,这样的路径是不合理的。

图1. 动态图样例[3]

CTDNE认为,一条合理的时序路径(temporal walk)应该满足规则:“路径中每条边的时间都应该小于等于下一条边的时间”。在满足这一规则的基础上,还需要确定两个随机采样方式。初始节点/边的采样方式以及采样下一个满足规则的邻居节点/边的采样方式。论文通过实验证明,对于初始边的采样使用线性增长的采样最好,也就是一条边的被采样概率随着边的发生时间增长而线性增长。而对于采样下一条边,在满足下一条边的时间大于等于当前边的条件下,采样等概率采样的方式更好。

总结起来,CTDNE就是在DeepWalk基础上,通过修改路径采样方式使得路径满足实际的发生顺序,从而使得采样路径更加合理。

JODIE

JODIE[4]主要处理用户(user)与物品(item)间的交互序列(sequence of interaction)预测问题。用户和物品的交互在现实中普遍存在,例如用户购买商品、学生注册某个 MOOC 课程、一个网友编辑了某个Wikipedia页面等。一个用户往往会在不同的时间和不同的物品进行交互,对同一个物品也可能会出现多次的交互。预测用户和物品间的交互是非常重要的问题,如预测用户的购买商品行为可以进行商品推荐;预测学生什么时候可能退出MOOC课程可以为他们制定后续的教育计划;预测用户何时可能在平台(如Reddit、Wikipedia)上会出现恶意操作对维护平台的稳定非常重要。

在根据用户与物品的交互序列进行预测时,需要解决两个主要问题。

1. 用户和物品的属性会随着时间发展而变化。例如图2中用户u3的兴趣爱好可能会随着时间推移慢慢从书本转移到电影再转移到衣服。书本可能一开始在老年人中流行,慢慢地在年轻人中也流行了开来。而静态图将这些交互都存放在一张没有时间记录的图上,无法建模节点的属性变化。

2. 用户和物品会因为他们交互的对象属性不同而对自身属性产生不同影响。例如用户 u2在书本i2获得普利策奖之后购买,与u2在书本获奖之前购买,模型建模得到的u2的属性变化应该是不一样的。同样,静态图也没有办法建模出这样的信息。

图2. 用户和物品的交互序列(左)以及在JODIE中的动态表示[4]

在JODIE中,每个用户和物品都有两个 embedding:static embedding和dynamic embedding。static embedding 表示一个用户/物品的长期静态属性,而dynamic embedding表示不断变化的属性,通过 JODIE 模型进行学习。这使得JODIE能够根据用户的静态属性和随时间变化的时序属性进行预测。

JODIE模型有三个主要的组成部分:更新函数(update function),映射函数(project function)和预测函数(predict function)。

图3. JODIE模型框架[4]

JODIE的更新函数通过两个RNN来生成用户和物品的dynamic embedding:

在每次交互时,根据用户和物品上一刻的 embedding:u(tˉ)和i(tˉ)、当前交互与用户上一次交互的时间间隔△u以及当前交互的特征f来更新用户的embedding。类似地,RNNi会更新物品的embedding。


用户的属性在上一次交互之后短时间内基本不变,但是随着时间增长往往会显著变化,而模型中用户的embedding却一直没有改变,使用这个embedding进行预测往往是不科学的。于是JODIE的映射函数通过类似attention的学习方式,评估/转换用户上一次的embedding u(t)在经过时间间隔△u之后新的用户embedding。

最后,JODIE的预测函数会直接输出用户最有可能与之交互的物品的embedding,因此模型中只需要进行一次神经网络的前向传递,然后找到与目标embedding最接近的物品的embedding,这比进行N次前向传递(与N个物品进行预测)然后进行排序要高效得多。

总结起来,JODIE会根据用户和物品的交互序列动态地更新用户和物品的embedding,从而建模出用户和物品动态变化的属性。

总结

本文先从静态图的局限性出发介绍了动态图的优势,然后通过CTDNE和JODIE两个算法介绍了动态图算法的基本思路。动态图算法的研究目前还处于初级阶段,未来的研究方向包括:如何设计更好的动态图模型使得算法可以更合理地建模图中节点和边的属性;使用什么数据结构使得动态图算法能大规模部署和运行;如何将知识图谱等信息引入动态图中。希望这篇文章能对从事图算法相关领域的朋友有参考意义,对于本文的不足之处,请读者不吝赐教。

参考文献

[1] Perozzi, Bryan, Rami Al-Rfou, and Steven Skiena. "Deepwalk: Online learning of social representations." Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2014.

[2] Kipf, Thomas N., and Max Welling. "Semi-supervised classification with graph convolutional networks." arXiv preprint arXiv:1609.02907 (2016).

[3] Nguyen, Giang Hoang, et al. "Continuous-time dynamic network embeddings." Companion of the The Web Conference 2018 on The Web Conference 2018. International World Wide Web Conferences Steering Committee, 2018.

[4] Kumar, Srijan, Xikun Zhang, and Jure Leskovec. "Learning Dynamic Embeddings from Temporal Interactions." arXiv preprint arXiv:1812.02289 (2018).

•作者简介

姓名:刘旭钦

专业:数据科学(计算机科学与技术)

年级:硕士三年级

研究方向:图神经网络

极验
极验

极验是全球顶尖的交互安全技术服务商,于2012年在武汉成立。全球首创 “行为式验证技术” ,利用生物特征与人工智能技术解决交互安全问题,为企业抵御恶意攻击防止资产损失提供一站式解决方案。

入门其他智能领域神经网络深度学习图像处理
5
暂无评论
暂无评论~