写在net embedding之前
一个标准的机器学习流程如下：
其中如何设计一套合理方式来高效地进行特征表示，是十分重要的，比如在cv与nlp任务中，我们会分别设计cnn模块与RNN模块来建模图像中像素点表征的信息、word表征的信息。
那么在graph中，如何进行特征表示呢 ？ Graph的特征表示极为复杂，主要表现在以下三个方面：
- 极其复杂的拓扑结构，很难简单地像图像中的感受野来提取有效信息；
- 无特定的节点顺序；
- 通常graph会是动态变化的， 且使用多模态特征；
今天我们就来了解下如何对graph进行特征学习；
Embedding Nodes
假设有图G，V表示节点集合，A为对应的邻接矩阵，embedding node是对图当中的节点进行有效地编码，保证相似的节点在编码也有类似的相似性，如下图：
节点的向量学习分为以下三个方面：
- 定义编码器， 即ENC(v)，将图中的节点通过周边结构关系的学习，映射到低维的向量表示，如\(Z_{v}\)，在常见的任务中，通常就是一个embedding矩阵，通过lookup拿到对应节点的向量，然后反向进行embedding向量的更新，这个即成为学习；
- 定义相似度函数sim(u,v)，即如何定义两个节点相似度的大小；
- 通过数据的学习不断来优化编码器参数，保证\(sim(u,v) = Z_{v}^{T}Z_{u}\)；
Random Walk
何谓"随机游走"？给定一个graph和一个起点，随机选择其一个邻居，并移动到这个邻居，然后继续随机选择这个点的邻居，产生随机的点序列，而点和点之间出现的概率即为\(Z_{v}^{T}Z_{u}\)
Random Walk有两个特点：
- 极具表达性： 节点相似计算的定义、随机，且包含了局部（邻居）以及高阶邻居的信息；
- 效率级高：训练时不需要穷举所有的节点对，只需要考虑随机游走中同时的对；
非监督特征学习
给定图G=（V， E）， 学习一种映射\(z: u->R^{d}\)，目标函数：
其中，\(N_{R}(u)\)表明以策略R得到的节点u的邻居：
优化
- 使用某种策略R，从图上的每个节点开始进行固定长度的较短的random walks；
- 对于每个节点u，得到其的邻居\(N_{R}(u)\);
- 根据上图中似然函数，对embedding进行优化；
这里，将目标函数，修改为以下，其中\(p(v|z_{u})\)可通过softmax得到：
但是一旦使用softmax，其复杂度变得极大，你必须计算graph当中所有的节点，其复杂度达到了\(O(|V|^2)\)，和大家十分熟悉的word2vec，我们采用Negative Sampling来近似计算：
Negative Sampling
Negative Sampling仅仅随机选择k个负样本进行归一化操作，其中\(P_V\)是所有节点的随机分布，其中k属于超参，通常有以下经验：
- k越大，预估有更强的鲁棒性；
- k越大，负样本偏差会越大；
- k通常使用5-20；
Node2vec
Node2vec解决的和random类似的额问题， Node2vec扩展节点u的邻居\(N_{R}(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下很重要的工作。