蚂蚁金服科技 + 关注
手机版

论文 | 2017CIKM-Network Embedding专题论文分享

  1. 云栖社区>
  2. 蚂蚁金服科技>
  3. 博客>
  4. 正文

论文 | 2017CIKM-Network Embedding专题论文分享

安和林 2017-12-20 14:40:39 浏览4114 评论0

摘要: 一篇文章带你学习Network Embedding的最前沿研究!

导读:

ACM CIKM 2017全称是The 26th ACM International Conference on Information and Knowledge Management,是国际计算机学会(ACM)主办的数据库、知识管理、信息检索领域的重要学术会议。

参会归来后,小编邀请了参会的同学与各位读者们第一时间分享了CIKM的参会感受。在接下来的CIKM系列分享中,你将会看到:CIKM最佳论文鉴赏,Network Embedding专题和Transfer Learning 专题。本篇文章是CIKM系列分享的二篇:CIKM Network Embedding专题分享。(CIKM最佳论文鉴赏请参考昨日的推送)

venue2

在CIKM 2017大会的171篇长论文中,有22篇Graph Mining相关,其中11篇为network representation learning(Network Embedding)。主会场共设置49场专题Session,Graph Representation/Graph Mining占到了其中的五分之一。Network Embedding太火热,沟通中发现,有部分数据库的研究人员也往这块涌进,同时,学术届也特别关注工业界在这个领域遇到的难题。定义新问题、并且融合更多信息,是推动后面新技术研究的核心。

Network Embedding概述

Network Embedding,即将网络节点、community投影到低维向量空间,用于node classification、link prediction、community detection、visualization等任务。

1

核心假设:节点间距离越近,embedding向量越接近,定义LOSS为:

2

Network Embedding算法分类

  • 基于矩阵特征向量计算(谱聚类)

目标是将相似性高的两个节点,映射到低维空间后依然保持距离相近,其损失函数定义为:

3

  • 基于random walk框架计算(Deep Walk & Node2Vec)

4

  • 基于Deep Learning框架计算
    SDNE(Structural Deep Network Embeddings)

主要思想:将节点的相似性向量 s~i~直接作为模型的输入,通过 Auto-encoder 对这个向量进行降维压缩,得到其向量化后的结果 z~i~。
其损失函数定义为:

5

模型框架为:

6

GCN(Graph Convolutional Networks)
主要思想:将节点本身及其邻居节点的属性(比如文本信息)或特征(比如统计信息)编码进向量中,引入了更多特征信息,并且在邻居节点间共享了一些特征或参数,基于最终的目标(如节点分类)做整体优化。
模型框架示意和计算流程:

7

CIKM2017中Network Embedding的新研究方向

经典的DeepWalk、Node2Vec、LINE算法,主要基于浅层模型,但由于网络结构本身比较复杂,浅层模型往往收敛于局部最优解,无法表示更高级的非线性网络结构。而且,如何融合节点属性、边的权重、边的属性、高阶网络结构做整体Embedding,以及动态网络的增量Embedding/meta-path/Multi-view/Attention等,提高节点分类/link预测的精度,是当前学术研究的核心方向。

8

  • Learning Node Embeddings in Interaction Graphs

https://web.cs.wpi.edu/~xkong/publications/papers/cikm17.pdf 注:本文中出现的所有网址建议请直接复制至浏览器中打开查看,下同。)
解读:网络构成中,边上带了很丰富的交互信息,如何同时利用这部分信息进行节点Embedding。比如“用户”-“股票“之间的交易网络,边上带有丰富的“时间、价格、数量”特征,如何结合这些信息和网络结构,得到“用户”、“股票”的embedding向量,进而用于预测“用户”后续会买哪只股票。

9

  • 网络信息转换成Squence

10

  • 如何得到两种节点的Embedding和预测模型(用户会买哪只股票)

1.目标定义

11

2.Model Structure

13

3.迭代计算,得到节点Embedding(隐层)和model的参数

14

适用场景:二步图推荐

  • Attributed Signed Network Embedding

http://www.public.asu.edu/~swang187/publications/SNEA.pdf
解读:融合节点属性的signed(边有Positive&Negative)网络的embedding,例如:社交网络,用户有基本属性,Positive关系有关注、点赞等,Negative关系有取消关注、不支持等。论文中的核心假设:1)从网络结构角度,“有Positive-Link节点间距离” < “无直接Link节点间距离” < “有negative-Link节点间距离”;2)从属性相似性角度,“有Positive-Link节点间距离” < “有negative-Link节点间距离” < “无直接Link节点间距离” 。如下图:

15

定义LOSS,由“网络结构+结构扩展限制+属性限制+属性扩展限制”4个模块组成,迭代求解。

16

  • Attributed Network Embedding for Learning in a Dynamic Environment

https://arxiv.org/abs/1706.01860
解读:动态网络Embedding,节点属性和网络结构(边)随时间动态变化,如何:A)去除网络关联和节点属性中的noisy and incomplete,得到综合“属性+网络边”的representation;B)embedding需要根据网络动态变化快速更新。论文算法DANE,提出同时融合节点属性和网络结构信息的无监督Embedding算法,且能够快速动态更新,核心2步走:
1.离线模型得到初始consensus embedding(网络结构和节点属性的Embedding最大程度一致)。
2.利用矩阵摄动理论(matrix perturbation theory)增量在线更新embedding results。

17

3.离线模型得到初始consensus embedding
(备注:去噪的思路值得参考,用于无监督embedding优化)
基本假设:两节点存在连边,则属性一致性越高。

步骤:
1.网络结构Embedding , 网络拉普拉斯矩阵的TOP-K特征向量(不包含0特征值对应的单位向量)。

18

2.节点属性embedding,节点属性相似矩阵的TOPK特征向量。

19

3.去除noisy,通过LOSS,使得属性embedding和网络结构具有强一致性。

20

各种推导,最终的一致表达为:

21

实时在线增量更新计算

22

该方法有两个隐含限制:1)节点的属性和网络的形成相关,比如“兴趣社交网络,有共同爱好的节点更容易连接”、“黑产网络,节点的异常属性和网络结构相关”;2)动态更新,要求不同STEP,网络节点属性或者LINK变化很小(文中实验数据变化<0.5%)。

适用场景:实时风险识别,快速更新高维信息的向量表达。

  • Learning Community Embedding with Community Detection and Node Embedding on Graphs

http://sentic.net/community-embedding.pdf
解读:community embedding,网络社区结构的向量表达,通常是其节点集合的向量分布(多元高斯分布)。基本假设:节点embedding,与其所在社区的中心节点相似度高,这个假设约束有助于Node Embedding更好的引入网络高阶信息,进而更好的支持community detection。当前,community embedding, community detection and node embedding这3大任务通常都作为独立的问题去解,本文提出一个闭环算法结构,算法的输出同时包含节点向量、社区向量以及最优社区结构划分。

community embedding 示意:

23

闭环Embedding框架

24

一般解法,每个步骤独立计算,信息之间没有得到有效互补
1.基于谱聚类、LPA等得到社区划分结果。
2.基于DeepWalk、Node2Vec等得到节点的embedding。
3.融合社区所有节点的embedding信息,得到Community的分布(多元高斯模型)。

论文的“一站式”解法,定义LOSS,梯度求解,复杂度linear to the graph size(|V|+|E|)

25

应用场景:通过节点增量embedding,实现实时团伙识别。

  • HIN2Vec: Explore Meta-paths in Heterogeneous Information Networks for Representation Learning

解读:提出异构网络中,如何融合网络结构和不同关系(meta-path)信息框架,得到节点的embedding,核心创新点:通过将边的信息转化成meta-path,整个模型目标是预测meta-path,从而达到融合异构网络边类型信息的效果。整个方案框架分2个步骤:

26

1.训练数据准备

27

基于randwalk将网络转化成节点序列,并定义meta-path。
节点做onehot编码,选定2个节点X、Y作为输入,对应的输出为可能的meta-path。
例如:节点P1、A1,可能的meta-path为P-A、P-P-A ,模型的目标为[0,1,0,0,1,0,0,0]

2.node embedding学习

28

隐层的d维向量即节点的Embedding信息。

应用场景:异构网络中,提取异构路径信息的新思路。

  • An Attention-based Collaboration Framework for Multi-View Network Representation Learning

解读:区分网络多种构成方式,比如:社交关联、资金转账网、属性相似性网等,从不同的视角分别做节点embedding,再基于Attention机制融合不同的embedding结果。整体框架如下图:

29

整体优化目标LOSS:

30

  • Name Disambiguation in Anonymized Graphs using Network Embedding

解读:重名的人很多,而独一无二的指纹/DNA信息通常很难获取或因涉及用户隐私不能使用,如何正确区分同名不同人。论文中提出仅依赖关系网embedding的方法,能够将同名不同人的聚类区分。例如:在GOOGLE搜索人名,希望同一自然人的文章能够一起顺序展示,如下图,不同的颜色代表不同的自然人:

31

针对上述问题,论文先构建“用户-用户”、“用户-论文”、“论文-论文”组成的异构网络,如下图:

32

基本假设:存在LINK的节点间Embedding距离 < 无LINK的节点间Embedding距离,定义异构网络的LOSS,计算梯度迭代求解,得到“Document”的embedding后聚类。

33

  • From Properties to Links: Deep Network Embedding on Incomplete Graphs

这篇论文主要想解决的问题是:图上的节点以及改节点上的属性改如何总体起来去提取对应的graph embedding,其基本方法是通过组合multi-view和SDNE两个概念而产生的:

34

35


其中一路是该节点的邻居结构,一路是该节点的属性数据。两路数据分别使用autoencoder进行学习,但在学习过程中会将两路数据在中间过程中进行合并,从而达到作者所说的节点和其属性的合并学习。

同时,使用基于autoencoder的方式来获得图的embedding有一个潜在的好处,可以很快的获得之前在学习的时候还没有的节点对应的embedding,当然这也是有一定限制的,即新加入的点的邻居只能限定在已有的图中。

同时这种方法的一个问题在于训练的时间复杂度会很高,在处理较大的图的时候可能会面临训练时间过长的问题。

【云栖快讯】阿里巴巴小程序繁星计划,20亿补贴第一弹云应用免费申请,限量从速!  详情请点击

网友评论