同济子豪兄--随机游走的艺术-图嵌入表示学习【斯坦福CS224W图机器学习】

 人工特征工程就是前面几集提到的方法需要人工去设计一些方法去计算每个节点的特征。

引言--这集学习的就是图表示学习不需要人工设计特征不需要特征工程而是通过随机游走的方法在图中采样，自动的去学习每个节点嵌入和向量。 

豪哥的学习大纲：DeepWalk、Node2Vec、PageRank、GNN一直到Trans-R都（红框内）是把一个节点变成一个标量或者向量。Trans-E、Trans-R则是把知识图谱的三元组变成一个向量。

表示学习（Representation Learning）是机器学习中的一个重要概念，它指的是学习如何以一种能够揭示数据本质特征和结构的方式表示数据点的过程。在表示学习中，数据被转换成一种新的形式，这种形式使得机器学习算法能够更容易地识别和利用数据中的模式和关系。

解释：表示学习就是把各个模态的输入转成向量比如说视频、图像、声音都可以转化为向量，表示学习的目的就是把这些东西转化为向量，而且这个向量可以保留原始的信息。整个过程都不需要人工去干预。

将节点映射为一个D维向量，图中R表示实数，D表示D维向量。所形成的向量是一个低纬连续稠密的向量。

与下游任务无关意思是我们不关心下游任务是解决的节点的分类问题、连接预测问题、社群聚类问题还是整图的分类，这个向量是上游直接得到的我们不知道下游的任务是什么，只是先通过某种方式将节点变成的一个向量，至于你要用这个向量干嘛我们是不管心的。整个过程是无监督的。

D维向量中的相似度反映了实际图之间的节点相似度。

编码器-解码器

编码器：简单理解为输入一个节点输出一个D维的向量。

解码器：将两个向量做点成得到一个标量，这个标量可以反映相似度，若这两个向量完全不相似表示为这两个向量正交相似度为0，反之最高相似度为1表示为两个向量平行或者说这两个向量就是一个向量。

节点的相似度需要自己去定义：例如巴拉马运河和马六甲海峡虽然相隔了很远但是可以是相似的因为他们都是运输的要道。所以可以自己去定义节点的指标和向量之间的相似度。

那么咋样去定义相似度呢？有下图中提及的几种情况，我们重点说明随机游走算法。

最简单的一种编码器：查表（浅编码器）

假设Z矩阵包含了所有节点的向量，那么我们的目标就是迭代优化这个Z矩阵的每一个元素使得图中相似节点的数量积大、不相似的数量积小。

所以这个方法是一个无监督的方法，因为我们没有用到标签和节点的类别而是直接优化的嵌入向量。虽然该过程与下游方法无关但是是可以用于下游任务。 

随机游走 

随机游走（Random Walk）是一种数学统计模型，也是一门随机过程的分支。在图论中，随机游走可以被看作是在图的节点上的一个过程，其中每一步都从当前节点移动到其邻居节点之一，选择邻居节点的概率是依据某种概率分布进行的。在图的上下文中，随机游走的定义通常如下：

1. 起始节点： 随机游走从一个特定的节点开始，这个节点称为起始节点。

2. 转移概率： 在每一步中，游走者以一定的概率分布选择移至相邻的节点。在无权图中，通常每个邻居节点被选择的概率是相等的。在有权图中，转移概率可能取决于边的权重。

3. 游走长度： 随机游走的长度可以是固定的，也可以是无限的。在固定长度的随机游走中，游走在一定步数后停止。在无限长度的随机游走中，游走可以无限期地继续。

4. 状态空间： 随机游走的状态空间是图的所有节点的集合。在每一步，游走者都处于这个状态空间中的一个节点上。

5. 平稳分布： 如果随着步数的增加，随机游走的节点分布趋于稳定，那么这个分布被称为随机游走的平稳分布。在某些类型的图中，如强连通图，随机游走会收敛到一个唯一的平稳分布。

简单说：就是图中有一个醉汉在到处随机走动，而这个采集得到的序列就是随机游走序列。你也可以给醉汉指定一种游走模式例如在节点的领域（周围）走动或者往跟“远”的地方走动

图机器学习和NLP很相似。up主给出以下对应。

计算从u节点出发的随机游走序列经过 v节点的概率。根据Softmax来计算。

Softmax： 是一个在机器学习和深度学习中广泛使用的函数，特别是在处理多类分类问题时。它将一个实数向量转换为一个概率分布，使得向量中的每个元素都映射到一个介于0和1之间的值，并且所有元素的和为1。这使得Softmax成为多类分类问题中输出层的自然选择，因为它可以解释为分类结果的概率分布。

随机游走是否靠谱呢？

答：随机游走虽然看似随机但是可以捕捉周围和更高阶的领域的信息其次随机游走算法计算便捷，不需要很多计算资源而且是一个无监督的问题是一个万精油的方案。

极大似然估计（Maximum Likelihood Estimation, MLE）是一种在统计学中用于估计概率模型参数的方法。它的核心思想是：给定一个概率模型，以及一些生成于这个模型的观测数据，我们希望找到模型参数的估计值，使得这些参数下观测数据出现的概率（即似然函数）最大。

1. 定义似然函数：似然函数是给定模型参数时，观测数据出现的概率。如果样本是独立同分布的（i.i.d.），似然函数可以表示为每个观测数据概率的乘积。

2. 取对数：由于乘积形式的似然函数在计算时可能会遇到数值下溢的问题，通常会取似然函数的自然对数，将其转换为对数似然函数，这样乘积就变成了求和，更容易处理。

3. 求导数：对对数似然函数关于模型参数求导，找到使对数似然函数最大化的参数值。

4. 解似然方程：解求导后的方程，找到参数的估计值。

本质上就是我们希望让相似的节点预测出来的概率是最大化的

流程就是先以每个点为起始节点然后在遍历出现在了随机游走序列里面的节点。

去掉下图中的负号就是最大化。

蓝色框里面的意思是从u节点出发来预测v节点的概率，然后这个概率有前文提及的Softmax来计算。exp表示e，括号里面的是次方的意思，Softmax公式的分子意思是e的u节点和v节点的数量积，分母是u节点与图中所有节点的数量积的和

在这个式子中有两个地方要遍历所有节点。所以复杂度式v的平方

V的平方的数量积还是很大的，下面做了一些优化，在分母中原来需要做所有节点的遍历，现在只做k个负样本，k个样本是从图中非均匀随机采样的k个样本，每个样本被找到的概率是不一样的

理论上,同-个随机游走序列中的节点,不应被采样为“负样本也很难采集为“负样本”例如在14亿人中随机采样5-20人很难采集到在同一个随机游走序列中的节点。

优化的过程采用的就是随机梯度下降（一种是全局的梯度下降一种是求每个样本的随机，梯度下降）

全局的叫做Gradient Descent，首先初始化Z表然后求出所有节点u的总梯度在根据这个梯度的负方向乘一个学习率，迭代更新D维向量的每一个元素        

也可以每一个样本（每一个随机序列）优化一次这种被称为Stochastic Gradient Descent

上面的随机游走是完全的随机游走，那么我们能否控制随机的方向呢？答案是可以的。

采用Node2Vec方法可以实现。

Node2Vec在前面跟DeepWalk一样区别是Node2Vec是有偏的二阶随机游走。

你可以控制p和q两个参数来控制“醉汉”是优先探索邻域还是优先探索远方。一个参数控制是否要回上一个节点，一个参数控制是否往“远”方走。

有1/p的概率会回到上一个节点，有1/q的概率会走向更远的节点还会有1的权重会走跟上一个点距离相等的点

p大q小和p小q大情况如下。

理解为：不同的p和q探索的是图的不同区域得到的嵌入也不一样

矩阵分解的角度理解图嵌入和随机游走

将矩阵A分解为两个矩阵Z和Z转置其中A矩阵中的1就代表着两个节点相似，0代表两个节点不相似（两个向量正交）

但是Z矩阵是d行n列的“矮胖”型的矩阵在数学上没有唯一解。所以我们通过数值估计的方法进行估计，将式子写成费罗贝尼乌斯的形式然后迭代的去优化这个式子直到这个值足够小

DeepWalk和node2vec也可以也可以写成 矩阵分解的形式只不过会很复杂如下图所示

基于随机游走的图嵌入方法的缺陷：

1.无法适用于动态图如微信的社交网络一直都有节点在产生，用已有的方法无法立刻泛化到新加入的节点

2.随机游走只是探索一个节点相邻局部的信息，例如从u节点出发，那么u节点周围的节点大概率会被采样到。但是实际上相距很远的两个点的功能上很有可能是相近的例如前面举过的例子马六甲海峡和巴拉马运河。

3.它只用到了图本身的社交连接信息没有用到图本身的属性信息

嵌入整张图

最简单的方法就是把所有节点的D维向量求和

也可以引入虚拟节点，如下图的红色节点，然后求出这个红色节点的嵌入作为这个子图整体的嵌入

匿名随机游走：每次遇见一个没见过的就发一个新的编号，例子如下图所示。

所以得采样多少次才能使这个式子比较稳定呢？

论文那种提出了如下的公式解决：匿名随机游游走长度固定时，欲使误差大于的概率小于需采样m次。

另外一种方式我们给每种匿名随机游走的序列学习一个嵌入的编码，然后全图也单独学习一个编码。

假设如下图一样已知全图编码以及一、二、三的编码现在预测四的编码。首先将一、二、三的编码相加在求平均然后和全图的编码堆叠在一起形成一个2d的向量然后去预测四的编码。

一个小时的视频~~~码字不易求点赞求关注~~~