网络中的机器学习
节点分类
链接预测
机器学习的生命圈需要特征工程
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231340461-425429812.png)
网络的特征学习——特征向量 embedding
network embedding的意义
节点的表征
节点的相似度衡量→网络相似度衡量
网络信息编码,生成节点表征
用途:异常检测,属性预测,聚类,关系预测
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231341153-199441324.png)
例子:deepwalk
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231341496-563375655.png)
难度:当前的深度学习视为序列或网格数据而设计的,但网络结构比这些更复杂,没有固定的空间结构,没有固定的顺序,是动态的,并且有多类特征
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231341814-999664924.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231342172-1241700633.png)
Embedding Nodes
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231342434-1092436103.png)
假设我们有图G,V是节点集合,A是邻接矩阵,![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231342655-843995033.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231342655-843995033.png)
将节点编码,编码后的向量计算得到的相似度与原网络的一致
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231342947-1449238139.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231343266-1788544742.png)
因此需要定义一个编码器,以及计算节点相似度的函数,并优化encoder
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231343658-1652694434.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231344020-1041733982.png)
浅层encoding,有一个大矩阵,存储各类节点的向量,encoder只是look-up,类似于word embedding
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231344376-1928032955.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231344707-2133598529.png)
常见的方法:deepwalk,node2vec,transE
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231344980-1074939549.png)
如何定义节点相似性
例子:若两个节点的embedding相似,那么在物理结构上,他们:相连?有相同邻居?相似的结构角色?等
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231345271-1694437702.png)
随机游走→node embedding
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231345521-1676185943.png)
随机游走:从一个节点出发,随机选择一个邻居节点,游走到该节点,再重复上述步骤。经过的节点组成的序列即为图的random walk
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231345789-2095774221.png)
公式表示节点u,v在random walk中共同出现的概率
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231346130-235378961.png)
步骤:
1. 随机游走,得到若干序列
2. 优化encoder,使共同出现的节点的序列相似度更近
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231346512-910923120.png)
random walk的意义:
能充分表达网络的结构(邻居信息)
高效性,不需要考虑网络中的所有节点
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231346869-258561757.png)
非监督的学习,整体的过程类似于词向量,此处不加赘述
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231347229-1004148433.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231347896-976907432.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231348337-2099053553.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231348742-268036248.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231349137-9094345.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231349486-352568370.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231349830-1300678376.png)
负样本抽样 窗口 + 负样本
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231350555-750119099.png)
演变为固定短长度的random walk
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231350913-315823962.png)
如何随机游走?
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231351264-894169364.png)
node2vec的概述
:
具有相似邻居的节点得到的向量相似
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231351630-72134162.png)
游走:广度,深度
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231351993-609701005.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231352483-1202878642.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231352816-1086217679.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231353107-1041892838.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231353424-1823482633.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231353782-1063528945.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231354123-750638850.png)
node2vec的步骤
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231354511-1657855274.png)
embedding的使用:
聚类,社区发现
节点分类
关系预测
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231354836-944306980.png)
多关系数据模型的translating Embeddings
多关系模型,例如,知识图谱,边具有多类关系
知识图谱填充→关系预测
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231355502-2012191518.png)
transE
三元组关系 (实体1,关系,实体2)(h,l,t)
首先,实体已被表示未向量
那么关系如何表示呢?若l也是一个向量,那么应满足 h+l≈t
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231355832-462185182.png)
transE算法
整图的Embedding
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231356457-784573766.png)
将整个图通过向量表示
用途:鉴别分子是否有毒;鉴别网络是否异常
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231356713-293211778.png)
方法1:
基于node2vec得到每个节点的向量,求和或平均得到整个网络的向量
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231357071-2128473887.png)
方法2:
引入虚拟节点来表征网络向量??
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231357394-1856334919.png)
方法3:
匿名游走??需要看论文才能了解
当游走长度为3时,共有5个匿名。游走长度增长时,匿名的类别数如图所示
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231358119-1723536780.png)
枚举步长为l的ai游走,并记录出现的次数
将图表示为这些游走的概率分布
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231358448-94816255.png)
计算图中所有的匿名游走可能是不可行的
抽样得到近似的分布
需要的random walk的次数如公式所示
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231358834-761361147.png)
学习每个匿名walk的Embedding,求和/平均/拼接后的结果即为图的表征
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231359306-604646302.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231359687-1264279406.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231400067-664633861.png)