我们要解决的问题就是如何在已知部分标签的情况下，通过图数据本身的特点去预测无标签的样本；

除此之外，还有一个典型的场景是我们需要去预测edge——这被称为link prediction。

介绍了普通的有监督学习的流程，基本上都是讲烂的东西这里就不翻了，因为常规的feature engineering非常耗时耗力而且也不一定能够将原始数据中潜在的一些规律表示出来，所以希望借助神经网络来自动抽取潜在的特征并且以特征矩阵的形式展现。
这里把针对分类、回归、聚类等不同目标的模型训练与应用称之为 下游任务，而特征工程则属于上游任务。

目标：我们希望图数据的特征工程能够作为独立的上游任务进行，通过一些方法在特征工程阶段对特征进行抽取，然后将得到的最终的特征矩阵用于下游的各种任务，比如使用gbdt分类、kmeans进行聚类分析等等。
具体的形式就是将每一个节点表示成一个d维的向量；
如果熟悉word2cec的其实对这种思路应该是非常熟悉的，这和文本中将没有给单词embedding成一个词向量几乎是一样的思路。

说老实话，这一段的描述和文本的发展历程是非常相似的，文本早期最简单也最麻烦的是词袋模型，而图数据对应的简单而麻烦的是adjacency matrix——即领接矩阵：https://baike.baidu.com/item/%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5/9796080?fr=aladdin
词袋和邻接矩阵都有类似的问题：
1、高维稀疏，这对于gbdt或者是knn、kmeans之类的算法来说是非常麻烦gbdt太容易过拟合，knn这类base on 距离计算的算法受到高维诅咒的问题影响效果很差；
2、丢失了空间结构的信息，词袋丢失了上下文的关系信息，邻接矩阵丢失了二度、三度。。等结构信息，实际上是一种损失信息的特征转换的方式；
3、etc；
而对于embedding的方式二者也是非常类似的，文本有矩阵分解、lsi、lda这类的向量化方法，也有word2vec这类基于神经网络结构的embedding方式，以及自编码器这样的自监督的方式，而图也有node2vec这类基于统计方法的embedding方式，基于gnn的embedidng方式以及graph 自编码器这样的方式。可以说，对照文本来类比学习，很多图上的概念就能很好的切身体会；

是不是很类似于：

word2vec之后的二维可视化的图？

我们平常熟悉的CNN和RNN可以处理的数据，这里统称为“grid”网格结构，如上图所示，例如一张图片中的每一个像素点都是一个节点，一段语音波形也可以表示成一个一维的有序列关系的节点，

这里实际上是把图像、音频（其实也有包括文本和传统的tabular数据）都当作了图数据的一种。
对于无序的tabular数据，即没有图像的规律的空间结构（比如某一个局部是一个鼻子，那么这些鼻子上的像素点相互之间是有空间关联关系的；比如一段有顺序的文本中，单词是有先后顺序关系的，而tabular数据就是一个一个完全独立的节点，不同的节点（样本）之间是没有任何关联的，而每一个样本的特征就是节点对应的属性（property））
然而：
实际中，我们遇到的问题更加复杂：
1、不像grid数据那样有规律性；
2、没有固定的节点顺序或者参考点（一个典型的图数据结构对齐进行左右、上下翻转等不会改变图数据本身的含义）
3、 图数据常常是动态（例如节点不是固定的，可能会随着时间消失或出现，比如新的社交关系的生成，而对于图像、文本和表格数据，这些是相对固定）的并且具有多模态特征（例如edge可以代表节点之间的社交关系，也可以代表节点之间的主次关系）。

现在我们假设一个简单的场景，我们有一个图G，V是G的顶点集，A是G的领接矩阵的表示，假设是一个binary的邻接矩阵（也就是节点之间是一度关系，不考虑更复杂的多度关系的情况）并且我们不考虑节点的属性（特征矩阵）或者是其它的额外的信息。
当然也有将节点属性考虑进去的embedding方法，但是这节课不做介绍。

我们的目标就是将所有节点都映射到一个新的特征空间，并且在原始的图结构上相近的节点，在新的特征空间中也是具有强相似性的（和word2vec的思路是一样的）；
但是这个时候就有一个比较重要的地方了，我们要使得原始图结构中，节点之间的相似性度量的结果和embedding之后的节点之间的相似度度量的结构是接近的（这里对于embedding之后的特征空间的相似性度量方式定义如下图，就是简单的dot product 点积）

这里给的相似性定义的例子如上，就是两个向量的dot product（点积）。

这里给node embedding的思路如上：
1、首先我们要定义一个encoder，也就是node 到 embedding的编码器（映射函数）；
2、然后我们要定义相似性函数（例如，在原始的图结构上的相似性的度量函数）
3、优化encoder的参数使得节点在原始的图结构和embedding空间中的相似度接近，说白了就是A和B在embedding前是靠近的，A和B在embedding之后还得是靠近的。

所以这里就有两个需要解决的问题：
1、encoder如何定义；
2、原始的图结构中的similarity function如何定义（embedding空间的similarity直接使用dot product定义，当然这只是一种最长使用的embedding空间的similarity的定义方式，我们可以根据自己的需要去定义别的度量方式，不过这里没深入介绍了）；
（学生问题，我们前面仅仅是针对相似节点embedding之后也要相似的问题进行优化，那么如果原始的图结构里两个不相似的节点在embedding之后却相似了该怎么办？答案是在我们的优化目标中加入不同节点之间的相似性度量，这样模型能够同时优化“相同节点相似”和“不同节点不相似” 两个目标，后面会详细介绍）
现在进入第一个问题，encoder如何定义，首先介绍了最简单的一种encoder的方法：

浅层编码，如下图：

这实际上和nlp里的embedding的形式是几乎一样的；
对所有节点做onehot展开，然后通过lookup的方式来查询每一个node在node embedding 矩阵中其对应的embedding向量；
常见的这类shallow浅层的embedding方法有：

（node2vec是deepwalk的一种扩展方法，以及一种知识图谱嵌入的方法TransE。

我们选择哪一种embedding的方法取决于我们如何在原始的图结构中定义相似性，是互相连接的节点具有相似性？还是具有相同的邻居的节点具有相似性？还是具有相同结构作用的节点具有相似性？等等，这部分的定义取决于你要解决的问题的形式。比如说如果在反欺诈的场景中，欺诈分子之间的connect特别强，典型的团伙作案模式，那么我们就把similairy定义为connected similarity。
不同的相似性定义决定了我们如何去选择不同的embedding的方法。

首先是random walk的定义；
给定一个图G和一个起点A，我们随机选择A的一个邻节点B，并且移动到这个邻节点B，然后我们在点B上再随机选择一个B的邻节点C，然后移动到这个邻节点C，依此类推。这样，我们最终得到的一个随机的序列A—>B—>C—>。。。。即为图G上的一个随机游走产生的序列。

1、使用某种随机游走策略R估计从节点u开始的随机游走过程中访问到节点v的概率；
2、优化embedding矩阵以将random walk的统计信息encode进来。

为什么要使用random walk的策略？
1、强大的表达能力：通过随机游走的方式灵活的定义了节点的相似性，充分考虑了本地和高阶的邻域信息；
2、 高效：训练时不需要考虑所有节点对；只需要考虑在随机游走中”共现“的节点对；

可以看到random walk的过程中没有应用到任何的标签，属于一种无监督的特征学习的方法（个人感觉用自监督的representation learning描述更合适。。）
直觉：找到一个d维的embedding的空间，这个空间中可以保持原始的图结构中的节点之间的相似性；
方法：学习node embedding使得在原始的图结构中靠近的节点在互相接近；
那么给定一个节点u，我们如何来定义其邻域的节点们呢？
方法是通过某种策略R来得到u的邻节点的一些特定的信息Nr（u）；
（学生问，如果一个节点其邻节点的数量非常大，random walk的效率是不是就会降低很多，答案是，对的，因此不会使用一个节点的所有邻节点进行random walk而会采取一些优化措施，例如像word2vec一样定义一个windows，只取一部分上下文进行word embedding的训练）

下面开始正式进入算法原理讲解环节：

给定图G=(V,E)，我们的目标是学习到一个映射函数Z，可以将u映射到一个d维空间；
我们的目标函数就是最大化对数似然函数；
看到这里可能会有点懵，没事儿，继续往下看，后面会给出详细的解释和具体的例子。

random walk优化的流程：
1、在一个完整的图上，我们使用某个策略R为每一个node跑一个固定长度的短的random walk；
2、为每一个node——u，保存以u为starting node的random walk产生的序列数据；
3、根据最大对数似然函数对embedding进行参数更新；

看的时候比较懵逼，找到了一些大佬的笔记是2014年的关于deep walk的论文，然后才看明白了。

这里所说的deepwalk就是我们前面说的通过 random walk来对节点embedding。
思路看起来非常简单自然， DeepWalk的思想类似word2vec，使用> 图中节点与节点的共现关系来学习节点的向量表示。那么关键的问题就是如何来描述节点与节点的共现关系，DeepWalk给出的方法是使用随机游走(RandomWalk)的方式在图中进行节点采样。
例如这是一个完整的网络图，如果我们以节点3为starting point，进行一次固定长度为3的短序列，那么我们可以得到:
然后开始借鉴NLP思想，这条路径上临近点与点之间必然联系密切 有共同特征。现在将3-2-4-5当作一个句子，各个顶点为句子中单词 这样，3-2-4-5就是word2vec中的一个句子，3，2，4，5分别对应的是一个单词。
然后就是word2vec的求解过程了。。。。

这样，后面猝不及防的公式就都迎刃而解了：

对比一下word2vec的损失函数：

经过softmax之后：
简直和ppt上的公式一毛一样
这里我们对word2vec的损失函数取负数转换为极小化问题，其形式就非常相似了，V代表所有random walk出来的序列，Nr（u）代表了以u为start point而random walk出来的一条序列，v代表了这条序列上的与u”共现“的所有的节点；
显然，random walk出来的序列u对应了text里的每个句子w，而u里的每个节点v就是句子中的每个词语C。w；θ 对应的就是Zu的变换关系。
自然而然的，在早期版本的word2vec中我们使用的是softmax来处理P，softmax函数后面对应的输出是所有单词，这里也是一样，使用softmax，输出对应的是所有节点。

那么，如果熟悉word2vec，那么接下来的一切就很顺畅了，上面的问题早期的word2vec也面临着一样的问题，因为我们的softmax后面借的是所有的词或者所有的节点，所以无论是前向和反向都要算到死，因此后来的大佬们想出了一些替代的，近似的方法。一个是把softmax变成分层softmax，通过霍夫曼树的方式来构建，关于技术细节，后续整理representation learning的时候再讨论吧。另一个更常见的方式是使用negtive samplin。

（上面绿色的部分对应的论文介绍了为什么这种近似的方法是有效的）

另外主要注意两点，k越大则对于embedding的计算越鲁棒然而越大的k也意味着对于少数样本的估计偏差越大（因为一个node所在random walk序列的与其共现的节点数量相对于全部节点来说是很稀少的，所以我们仅仅在不与其共现的节点中抽取一部分出来参与embedding的训练）。

这里的negtive sampling的概念和word2vec里的是一样的，所以就不详细介绍了。
需要注意的是，这里的negtive sampling和我们在不均衡学习中所说的负采样不一样，（当然二者都能缓解不均衡问题）我们在unbalanced learning中提到的负采样使用的均匀采样，而word2vec和deepwalk的负采样都是根据词或者节点出现的频率来采样的，简单说，出现的频率越大其被采样到的次数越多，否则越少，关于negtive sampling以及另外一种 分层softmax，这一节课没有详细介绍，感兴趣的百度即可，挺多人讨论过这两种优化方法的了。

那么，我们应该怎么random walk？

实际上前面的deepwalk就是一种比较多见的思路了，就是每一个节点走随机random walk。。。
然而，这种方式定义的相似性太过局限。
1、deepwalk无法应用于有权图，因为使用word2vec的思路是没有考虑边的概念的，因为词与词之间也没有所谓边的概念（补充）；
2、更重要的是，我们前面说过如何定义原始的图数据上 的相似性的问题：

显然，deepwalk的方法只能定义 connected和neighbor的相似性，也就是只能捕捉到node和node之间相互连接以及share the same nodes这种相似性；但是假设有两个节点node a和node b，其graph structure是一摸一样的，但是二者的距离很远，显然deepwalk是无法捕捉到这种相似性的。具体的例子后面的ppt有详细介绍

这里需要补充一个知识点，关于dfs（深度优先搜索）和bfs（广度优先搜索），我们之前提到random walk，在deep walk的算法中，random walk用的是dfs，所谓dfs，经常刷leetcode的人应该不陌生：
CSDN-专业IT技术社区-登录blog.csdn.net
下文来自上面链接：
广度优先搜索BFS
基本思想：首先访问起始顶点v，接着由v出发，依次访问v的各个未访问过的邻接顶点w1,w2,…,wi，然后再依次访问w1,w2,…,wi的所有未被访问过的邻接顶点；再从这些访问过的顶点出发，再访问它们所有未被访问过的邻接顶点……依次类推，直到图中所有顶点都被访问过为止。
通过下面的图，我们看看BFS是如何遍历的：

1.假设我们从A开始访问，这时候遍历的结果为A
2.A的邻接结点有B、C，我们先访问B、再访问C，这时候遍历的结果为A->B->C。
3.A的邻接结点已经访问完了，我们开始访问B结点的邻接结点，因为C已经被访问过，所以B的未被访问过的邻接结点只有D，这时候遍历的结果为A->B->C->D。
4.B的邻接结点已经访问完了，我们开始访问C结点的邻接结点，因为D已经被访问过，所以C的未被访问过的邻接结点只有E，这时候遍历的结果为A->B->C->D->E。
5.C的邻接结点全部被访问过，D的未被访问过的邻接结点只有F，因此最后遍历的结果为A->B->C->D->E->F。
从上面可以看出，广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点。
深度优先搜索DFS
基本思想：
首先访问图中某一起始顶点v，然后由v出发，访问与v邻接且未被访问的任一顶点w1，再访问与w1邻接且未被访问的任一顶点w2，……重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直到图中所有顶点均被访问过为止。
通过下面的图，我们看看DFS是如何实现遍历的：

1.假设从A顶点出发，与A相邻的顶点有B和C，我们先访问B，这时候遍历的结果为：A->B。
2.再从B出发，与B相邻的顶点且未被访问过的顶点为C和D，我们先访问C，这时候遍历的结果为：A->B->C。
3.再从C出发，与C相邻的顶点且未被访问过的顶点为D和E，我们先访问D，这时候遍历的结果为：A->B->C->D。
4.再从D出发，与D相邻的顶点且未被访问过的顶点为E和F，我们先访问E，这时候遍历的结果为：A->B->C->D->E。
5.再从E出发，与E没有相邻的顶点，这时候，返回D，与D相邻的顶点且未被访问过的还有F，我们再访问F，此时所以的顶点都被访问完，遍历的结果为：A->B->C->D->E->F。
这种算法所遵循的搜索策略是尽可能“深”的搜索一个图。

另一种node embedding的算法：line使用的是bfs的搜索策略，不过这节课没有介绍，所以这里不详细介绍了，感兴趣的可以关注：

这个大佬的专栏，写的非常详细，还有示例代码。。。太牛逼。

然后我们接下去看才不那么懵逼了；

首先明确目标：我们希望具有相似的网络结构的node在embedding空间中接近；
那么还是使用极大似然法来进行求解，并且独立于下游任务，因此还是使用无监督学习的方法来完成。
重要的发现： 更加灵活的网络邻域节点的定义能够带来表达能力更强的node embedding结果。
我们不再像deepwalk那样使用dfs的策略来进行random walk，而是使用 biaesd second order random walk的策略来产生node u的领域节点。

如上图，假设我们random walk的steps是3步，u节点使用的是bfs的搜索策略，那么比较容易就在其附近搜索完就了事儿了，从u开始只能搜索到s1、s2、s3，则只能捕捉到 local microscopic view（局部关联特征。。谷歌翻译很奇怪，这是自己意译的）
如果，而如果使用dfs的策略，则相对容易能够搜索到s4、s5、s6，但是却丧失了局部关联特征而丧失了 local microscopic view（全局关联特征），这说的是啥意思呢？

实际上是这样，如果我们使用deep walk，走的是蓝色这条线，捕获了全局关联特征，丧失了局部特征关联，那么如果我们还想要考虑局部关联特征怎么办？比如u和s6分别是左右两个社区的中心点，他们的网络结构是类似的，比如说不同的欺诈团伙，左边是A团伙，右边是B团伙，他们的组织结构类似，但是他们之间没有关联，可是他们的组织结构可能对于反欺诈的判别来说非常重要，那么这个时候我们就需要使用到bfs了，但是如果我们仅使用bfs，就顾此失彼了，比如另一个场景，欺诈分子之间关系都是非常密切，假设s4，s5，s6就是三个诈骗犯，一丘之貉，那么使用bfs的策略就无法cover到这种情况了。

而现实的场景可能更加复杂，骗子之间可能是既是在深度上相互关联，也具有相似的社区结构，只不过可能有的时候其中一种情况的程度更深一点，另一种情况的程度更浅一代女，那么我们该如何解决这种问题？

答案就是讲二者通过权重的方式结合起来，我们引入了一种称为biased random walks的方法：

上图非常形象的解释了整个算法工作的流程。直接对照着最后一幅图讲也就是上面这幅图讲即可，假设我们从u出发到达s1，然后假设s1到达w（此时无论dfs、bfs都只能随机选择s2或者w，因为这个时候还没的选呢），此时我们陷入了决策，是使用bfs还是dfs继续搜索，如果使用bfs，则我们要从w到s2（因为bfs是先把访问到的节点所有的邻节点访问完，因为这里s2直接和w相连所以直接从w搜索到s2），如果使用dfs，则w可以访问s3或者s4（不访问s1的另节点）。可以看到上面定义了dist(s1,t)，t表示s1下一步要到达的节点。
这里定义了两个超参数p for bfs；
q for dfs；
这个时候引入了一个偏置函数：

dist(s1,t)只有0，1，2三个取值：
1、如果w走向s3或者s4，显然是dfs的策略，因为此时s1的邻节点还没搜索完，则dist(s1,s3)=2，因为要经过s1和s3间隔了两个edge，对应的prob为1/q；
2、如果w走向s2，则是bfs的策略，dist(s1,s3)=1，对应的prob为1；
3、如果w回到了s1，则是bfs的策略，dist(s1,s1)=0，对应的prob为1/p;
其中p和q是人工指定的超参数，用户自己定义。 这样一来，就可以看出，超参数p控制的是重新访问原来结点的概率，也就是保守探索系数，而超参数q控制的是游走向更远方向的概率，也就是激进探索系数。如果q较大，那么游走策略则更偏向于广度优先策略，若q较小，则偏向于深度优先策略。

不过其实感觉这里不考虑dfs和bfs也是很好理解的，我们只要理解这个偏置函数就可以了；

这样整个算法的流程大概就出来了。
不过在另一篇文章里面看到了更完整的描述。不过这里的算法步骤介绍的比较粗略，更加详细的算法推导过程可见：

这里介绍了如何使用embedding的结果。