图节点表征学习

本章内容较少，可以理解为后续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向量的更新，这个即成为学习；
2. 定义相似度函数 ，即如何定义两个节点相似度的大小；
3. 通过数据的学习不断来优化编码器参数，保证 ；

Random Walk

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

Random Walk有两个特点：

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

非监督特征学习

给定图G=（V， E）， 学习一种映射 ，目标函数：

优化

1. 使用某种策略R，从图上的每个节点开始进行固定长度的较短的random walks；
2. 对于每个节点u，得到其的邻居 );
3. 根据上图中似然函数，对embedding进行优化；

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

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下很重要的工作。