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

2017 年 12 月 20 日 蚂蚁程序猿 蚂蚁金服科技

导读：

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最佳论文鉴赏请参考昨日的推送）

在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等任务。

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

Network Embedding算法分类

基于矩阵特征向量计算（谱聚类）

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

基于random walk框架计算（Deep Walk & Node2Vec）

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

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

其损失函数定义为：

模型框架为：

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

CIKM2017中Network Embedding的新研究方向

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

Learning Node Embeddings in Interaction Graphs

（https://web.cs.wpi.edu/~xkong/publications/papers/cikm17.pdf 注：本文中出现的所有网址建议请直接复制至浏览器中打开查看，下同。）

解读：网络构成中，边上带了很丰富的交互信息，如何同时利用这部分信息进行节点Embedding。比如“用户”－“股票“之间的交易网络，边上带有丰富的“时间、价格、数量”特征，如何结合这些信息和网络结构，得到“用户”、“股票”的embedding向量，进而用于预测“用户”后续会买哪只股票。

网络信息转换成Squence

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

1.目标定义

2.Model Structure

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

适用场景：二步图推荐

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节点间距离” 。如下图：

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

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步走：

离线模型得到初始consensus embedding（网络结构和节点属性的Embedding最大程度一致）。
利用矩阵摄动理论（matrix perturbation theory）增量在线更新embedding results。

离线模型得到初始consensus embedding

（备注：去噪的思路值得参考，用于无监督embedding优化）

基本假设：两节点存在连边，则属性一致性越高。

步骤：

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

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

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

各种推导，最终的一致表达为：

实时在线增量更新计算

该方法有两个隐含限制：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大任务通常都作为独立的问题去解，本文提出一个闭环算法结构，算法的输出同时包含节点向量、社区向量以及最优社区结构划分。