Press "Enter" to skip to content

图节点表征学习

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

本章内容较少,可以理解为后续cs224w GNN部分的入门课

 

写在net embedding之前

 

一个标准的机器学习流程如下:

其中如何设计一套合理方式来高效地进行特征表示,是十分重要的,比如在cv与nlp任务中,我们会分别设计cnn模块与RNN模块来建模图像中像素点表征的信息、word表征的信息。

 

那幺在graph中,如何进行特征表示呢 ? Graph的特征表示极为复杂,主要表现在以下三个方面:

极其复杂的拓扑结构,很难简单地像图像中的感受野来提取有效信息;
无特定的节点顺序;
通常graph会是动态变化的, 且使用多模态特征;

今天我们就来了解下如何对graph进行特征学习;

 

Embedding Nodes

 

假设有图G,V表示节点集合,A为对应的邻接矩阵,embedding node是对图当中的节点进行有效地编码,保证相似的节点在编码也有类似的相似性,如下图:

节点的向量学习分为以下三个方面:

 

 

    1. 定义编码器, 即ENC(v),将图中的节点通过周边结构关系的学习,映射到低维的向量表示,如Zv,在常见的任务中,通常就是一个embedding矩阵,通过lookup拿到对应节点的向量,然后反向进行embedding向量的更新,这个即成为学习;

 

    1. 定义相似度函数

    1. ,即如何定义两个节点相似度的大小;

 

    1. 通过数据的学习不断来优化编码器参数,保证

 

 

Random Walk

 

何谓”随机游走”?给定一个graph和一个起点,随机选择其一个邻居,并移动到这个邻居,然后继续随机选择这个点的邻居,产生随机的点序列,而点和点之间出现的概率即为

Random Walk有两个特点:

极具表达性: 节点相似计算的定义、,且包含了局部()以及高阶邻居的信息;
效率级高:训练时不需要穷举所有的节点对,只需要考虑随机游走中同时的对;

非监督特征学习

 

给定图G=(V, E), 学习一种映射 ,目标函数:

其中,

表明以策略R得到的节点u的邻居:

 

优化

 

 

    1. 使用某种策略R,从图上的每个节点开始进行固定长度的较短的random walks;

 

    1. 对于每个节点u,得到其的邻居

    1. );

 

    1. 根据上图中似然函数,对embedding进行优化;

 

 

这里,将目标函数,修改为以下,其中 可通过softmax得到:

但是一旦使用softmax,其复杂度变得极大,你必须计算graph当中所有的节点,其复杂度达到了

,和大家十分熟悉的word2vec,我们采用Negative Sampling来近似计算:

 

Negative Sampling

 

Negative Sampling仅仅随机选择k个负样本进行归一化操作,其中 是所有节点的随机分布,其中k属于超参,通常有以下经验:

k越大,预估有更强的鲁棒性;
k越大,负样本偏差会越大;
k通常使用5-20;

Node2vec

 

Node2vec解决的和random类似的额问题, Node2vec扩展节点u的邻居 的定义,来丰富embedding的建模信息;

 

Biased Walk

 

DeepWalk选取随机游走序列中下一个节点的方式是均匀随机分布的,而node2vec通过引入两个参数p和q,其中p为返回到上一个节点的概率, q表示生成策略选择DFS或者BFS的概率, 将宽度优先搜索和深度优先搜索引入随机游走序列的生成过程。宽度优先搜索(BFS)注重周围的节点,并刻画了相对局部的一种网络表示,宽度优先中的节点一般会出现很多次,从而降低刻画中心节点的邻居节点的方差;深度优先搜索(BFS)反应了更高层面上的节点间的同质性。(即BFS能够探究图中的结构性质,而DFS则能够探究出内容上的相似性(相邻节点之间的相似性)。其中结构相似性不一定要相连接,甚至可能相距很远。

得到Walks之后, Node2vec算法和DeepWalk基本类似,整体流程如下:

计算随机游走的概率;
模型从每个节点u开始的步长为l的r次随机游走;
利用优化方法优化目标函数;

如何使用节点的embedding?

 

训练好的节点向量可用于很多场景:

比如专栏前面文章提到的聚类、社区检测;
节点分类,比如根据节点embedding预测节点是否属于薅羊毛人群,新闻实体是否为fake news;
关系预测,比如预测用于是否与对应实体可能产生连接关系,即是否可能产生行为关系;

总结

 

本章课程,主要介绍了在graph中做node embedding的基本概念,以及常见的方法如Random Walk、Node2vec,并简要介绍了embedding的用途,视频教程中还有基于KG的Translating Embedding的应用,因为讲的过于简单,仅仅介绍TranE的三元组关系,感觉并不能理清楚其实际落地细节,所以本文不做描述,这部分相关工作建议直接阅读TranE的相关文档,比如药物中蛋白质分子的应用的等等,其实本文将是接下来各种复杂GNN的入门课程,大概所有的深度学习模型其实都在学习一种有效地特征表示,如本章内容而言,仅是入门,还有很多有意思的工作,比如是否能建模graph的dynamic的信息,行为是动态更新的,dynamic在某些场景下更能表征节点的社交行为结构化信息,另外还有包括side information的引入,都是在graph下的embedding node下很重要的工作。

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注