AAAI 2018入选论文解读：关于网络表示学习的最新研究

冯瑞，浙江大学本科三年级，ZJU DCD 实验室实习。AAAI 2018 入选论文一作。

分享主题：网络的学习表示

分享提纲：

网络的表示学习问题和经典算法介绍

欧式空间中保持无标度特性的可能性

针对无标度网络表示学习的优化策略

可保持时序信息的网络表示学习模型

社交网络中的表示学习

如何用合理的方式表示数据是网络挖掘的关键问题，表示学习的目的是为网络中的每一个节点分配一个某个线性空间中（比如欧式空间）的向量，使得这些向量能够保持原来网络的结构信息。接下来的分享内容讨论表示学习的诸多问题，比如在欧式空间中的无标度网络的表示学习，讨论是否保持网络的无标度特性，并对此优化以提高向量的表示能力。我们同时还讨论如何处理网络时序序列，使得表示向量能够保持时序信息。

什么是图嵌入

图嵌入是给图中的点找到一个映射，给每一个点分配一个向量表示。

图嵌入的应用

网络挖掘里经常会用到这项技术进行边的预测，节点的聚类，节点的分类。

关于社交网络的表示学习

社交网络最主要的特性是它是一个动态网络。社交网络是一个不断演进的过程，或者称为网络的时间序列。如果只看某一个时间的静态网络是不能反映全部的网络信息的。

接下来介绍这个模型就是解决这个问题，怎么把持续的信息加入到图嵌入中。它能反映用户之间的交互，信息传递的过程，用户之间的关系等特征。

复杂网络的另一个特征是它是一个无标度（scale-free)网络。关于无标度网络的介绍可以观看视频。

第一个模型是Dynamic Network embedding。下面是A和B的拓扑特征图。从图中，连接A的几个节点，相互之间也有了连接，可以看出A的影响力比B大。

上图中的演变过程是闭三角形过程。开三角形演变为闭三角形取决于K的影响力。

同时有多个开三角形演变为闭三角形的概率如何计算。

模型训练过程

关于应用

分别在移动网络，学术网络，服务器网络上进行了应用。在移动网络上判断是否电信欺诈，在网贷网络上判断用户是否还钱，在服务器网路上判断网络是否会崩溃。

网络重建和边预测

网络重建是给两个节点去预测两个节点间是否有条边。边预测是看是否能预测在未来某个时间是否出现一条边。

实验同时，使用了四个模型对照，Deepwork，TNE(Temporal Network Embedding) ，Node2vec，Dynamic Triad模型对照。

实验结果

下面来看无标度网络的表示学习

无标度网络的性质

上图中（a）表示原来网络的度分布，（b）的算法高估网络度比较高的点的概率，（c）是我们模型得到优化后的效果。

理论分析

论文中的解决方案

网络映射方法要保持一度和二度临近。如果两个节点有边就是一度临近。两个节点有很多公共邻节点成为二度临近。一个节点如果度很高的话，需要惩罚相邻节点的相似度。

两个模型，第一个是DP-Spectral（degree penalty based spectral embedding ），基于光谱嵌入的度惩罚。

第二个是DP-Walker,（Degree Penalty based Random Walk）基于随机游动的度惩罚。