在科学研究中，从方法论上来讲，都应“先见森林，再见树木”。当前，人工智能学术研究方兴未艾，技术迅猛发展，可谓万木争荣，日新月异。对于AI从业者来说，在广袤的知识森林中，系统梳理脉络，才能更好地把握趋势。为此，我们精选国内外优秀的综述文章，开辟“综述专栏”，敬请关注。
地址：https://zhuanlan.zhihu.com/p/384141329
01
Google团队研究发现Word2vec算法可以方便的将词语表示为向量形式，有利于下游任务的灵活计算。Yoav Goldberg等人通过Word2vec算法的实现发现句子中相似的单词得到的嵌入向量在空间中也较为接近。图数据中节点集可以被当作词表，而通过随机游走策略得到的固定长度序列可以被当作一种特殊语言的句子。按照SkipGram算法的思路，通过给定句子中的某个单词（图中的节点）及这个单词的上下文，最大化上下文窗口 内句子中所有单词（序列）出现的概率，中间得到的权重矩阵中的列向量就是得到的节点向量，SkipGram算法的损失函数：
其中 指的是表示矩阵，该矩阵用于将图数据中的节点映射到向量空间中，假设句子中各个单词与给定单词 之间相互独立， 可展开表示为 ，可得到随机游走序列上最终的优化目标函数：
其中，S表示随机游走策略得到的序列集合，N表示图中节点总数，通过多次迭代，即对每个节点做多次随机游走，最终得到节点向量，该向量能使图中连接的节点在向量空间中保持彼此靠近。DeepWalk的输入是图G和相关参数（窗口大小，序列长度，抽取序列数等），输出是映射表示矩阵 ，算法过程的描述如下：打乱节点集V，每次将V中的一个节点 作为起始节点，根据边集E从 的邻居节点中随机采样作为下一个访问节点，重复此过程，直至访问序列长度满足预设长度。使用SkipGram模型对上一步随机游走得到的每个序列进行处理，对于序列中的每个节点 ，使用窗口大小为 的上下文共 个节点中的每个节点 更新表示矩阵 ：将上述步骤重复γ次，即对每个节点做γ次随机游走，得到最终的节点向量。
02
DeepWalk算法中通过随机的游走采样策略得到定长的随机游走序列，每个邻居节点被采样作为下一节点的概率相同。Node2vec算法是一种通过无监督学习将图数据中的每一个节点映射到低维空间中向量的算法，该算法对邻居的定义更加灵活，同时用BFS和DFS对邻居节点进行采样。将生成随机游走序列输入到SkipGram模型中，学习得到的节点向量可以将相同相同社区和类似角色的节点映射到相近的位置，此外，也可以使两个连接通路较多的节点在映射后的距离很近。Node2vec算法使用了一种带权重的随机游走策略，在该策略下，随机游走序列从第i-1步的 节点到第i步的 节点的概率分布见下图：
表示随机游走序列中的第i个节点， 表示节点 和 之间的转移概率，Z表示 的标准化因子。当节点 和节点 之间没有边连接时，随机游走序列从 到 的概率为0。
随机游走策略通过调节因子在图的深度和广度优先搜索之间取得更加合理的游走方式。深度优先搜索会游走到离源节点较远的位置，侧重于社区结构信息，广度优先搜索会在初始节点的周围游走，侧重于节点角色信息。因此通过这种方法可以得到更具有代表性的随机游走序列中的下一个节点。其中调节因子p用于控制访问已经过的节点的概率， 时倾向于深度优先搜搜；调节因子q用于控制访问未经过节点的概率， 时倾向于广度优先搜索。
节点 和节点 之间的转移概率 受偏执参数 和节点间边权重 的影响：
其中， 表示随机游走序列的上一个节点， 表示随机游走序列的当前节点， 表示随机游走序列的下一个可能的节点。偏执参数 受调节因子和节点 与节点 之间的最短距离影响：
Node2vec算法使用随机梯度下降（StochasticGradientDescent）作为优化器更新目标函数参数，最终得到图中每个节点的向量表示。优化目标函数如下图所示：
其中， 表示节点 到向量空间中的映射函数， 表示根据源节点 通过带权重的随机游走策略S产生的邻居节点集合，通过最大化邻居节点集的出现概率，学习由节点到向量空间的映射表示。
论文提出了两个假设解决目标函数的优化问题。第一个假设是条件独立性假设，它假设在同一个节点的邻居节点集中，任一节点出现的概率与节点集中其他的节点无关，故可以将多个条件影响的概率变为单个条件影响概率的乘积，从而简化运算；第二个假设是特征空间对称假设，即同一个节点在作为源节点和作为源节点的邻居节点时是相同的，使用同一个embedding向量。根据这两个假设，上面优化目标函数可以改写为：
03
LINE算法是一种基于邻域相似假设来学习节点的向量表示的方法，倾向于广度优先搜索方式进行随机游走来构造邻域。除此之外，LINE算法还可以应用在带权图中。LINE算法使用了两种度量方式计算节点间的相似性。第一种方法是一阶相似度，这个指标仅用在无向图中，表示两个连边节点的相似度，大小为连边的权重，当节点间不存在连边时，相似度为0。第二种方法是二阶相似度，该指标适用于有向或者无向图，用于描述图中不直接相邻但有共同连接节点之间的相似度。令 表示顶点u与所有其他顶点间的一阶相似度，则u与v的二阶相似度可以通过 和 的相似度表示，若u和v之间不存在相同的邻居顶点，则二阶相似度为0。
表示节点 的低维向量表示。同时定义经验分布表示为：
其中， 是两个分布的距离，常用的衡量两个概率分布差异的指标为KL散度，使用KL散度并忽略常数项后得到公式：
对于二阶相似度，每个节点维护两个embedding向量，一个是该顶点本身的表示向量，一个是该点作为其他顶点的上下文顶点时的表示向量。在有向边(i,j)中，节点 的条件已知，则节点 的概率可以表示为：
其中， 表示控制节点重要性的因子，可以通过顶点的度数或者PageRank等方法估计得到。同时，经验分布定义表示为：
其中， 是节点 的出度，对于带权图 ，使用KL散度并设 ，并忽略常数项后得到公式：
在计算二阶相似度时，使用softmax函数计算时会遍历所有节点，为了减少计算这里使用了负采样，目标函数改写为：
其中 ， 表示顶点 的出度。上面 的公式在梯度优化时，将梯度直接乘以权重系数 。若图中边权的方差较大，则学习率的选择会变得很重要。当学习率较大时，则对于较大的边权进行参数优化时可能会出现梯度爆炸的情况；当学习率较小时，则对于较小的边权进行参数优化时可能会导致梯度过小。所以当所有边的边权都相同时，学习率的选择会简单很多。论文中采用了将带权边拆分为等权边的一种方法，对于权重为 的边，将其拆分为 个权重为1的边，这样就可以解决学习率选择的问题，但同时由于边数在拆分过程中的增长，存储的需求也会增加。另一种方法则是从原始的带权边中进行采样，每条边被采样的概率正比于原始图中边的权重，这样既解决了学习率的问题，又没有带来过多的存储开销。
04
2018年阿里公布了其在淘宝应用的Embedding方法EGES（Enhanced Graph Embedding with Side Information），其基本思想是在DeepWalk生成的graph embedding基础上引入补充信息。如果单纯使用用户行为生成的物品相关图，固然可以生成物品的embedding，但是如果遇到新加入的物品，或者没有过多互动信息的长尾物品，推荐系统将出现严重的冷启动问题。为了使“冷启动”的商品获得“合理”的初始Embedding，阿里团队通过引入了更多补充信息来丰富Embedding信息的来源，从而使没有历史行为记录的商品获得Embedding。生成Graph embedding的第一步是生成物品关系图，通过用户行为序列可以生成物品相关图，利用相同属性、相同类别等信息，也可以通过这些相似性建立物品之间的边，从而生成基于内容的knowledge graph。而基于knowledge graph生成的物品向量可以被称为补充信息（side information）embedding向量，当然，根据补充信息类别的不同，可以有多个side information embedding向量。那么如何融合一个物品的多个embedding向量，使之形成物品最后的embedding呢？最简单的方法是在深度神经网络中加入average pooling层将不同embedding平均起来，阿里在此基础上进行了加强，对每个embedding加上了权重，如图7所示，对每类特征对应的Embedding向量，分别赋予了权重a0，a1…an。图中的Hidden Representation层就是对不同Embedding进行加权平均操作的层，得到加权平均后的Embedding向量后，再直接输入softmax层，这样通过梯度反向传播，就可以求的每个embedding的权重ai(i=0…n)。图7 阿里的EGES Graph Embedding模型
在实际的模型中，阿里采用了 而不是aj作为相应embedding的权重，一是避免权重为0，二是因为 在梯度下降过程中有良好的数学性质。阿里的EGES并没有过于复杂的理论创新，但给出一个工程性的结合多种Embedding的方法，降低了某类Embedding缺失造成的冷启动问题，是实用性极强的Embedding方法。
05
Node2vec中通过BFS体现网络的结构性，通过DFS体现网络的同质性。这里结构性指的是微观结构，而不是大范围内，甚至整个网络范围内的宏观结构，而是一阶、二阶范围内的微观结构，同质性不是指一阶、二阶这类非常局限的同质性，而是在相对较广范围内的，能够发现一个社区、一个群、一个聚集类别的同质性。对于宽度优先搜索（BFS）来说，其搜索往往是在当前节点（这里以节点u为例）的邻域进行的，特别是在node2vec中，由于存在所谓的“返回概率”，所以即使从u搜索到了s1，也有很大概率从s1再返回u，所以BFS产生的序列往往是在u附近的节点间进行来回的震荡，这就相当于对u周围的网络结构进行了一次微观扫描（microscope view）。那么这个微观扫描当然更容易得到微观结构的观察，所以BFS就更容易使embedding结果更多反应网络的结构性。对于深度优先搜索（DFS）来说，相当于对网络结构进行了一次宏观扫描（macroscope view），只有在宏观的视角，才能发现大的集团、社区的聚集性，和集团内部节点的同质性。Q：如果是类似淘宝的商品推荐场景，那么什么样的商品之间是同质性较强的？什么样的商品之间是结构性相似度较强的？A：结构性关注的特定节点在系统中的相对位置（居于中心还是边缘），而不关心节点本身的特有的属性。类似每个品类的热门商品，热销商品，凑单商品等容易有这样的特点（处于网络中的特定位置）。同质性相反，更多关注内容之间本身的相似性，所以同品类，同店铺，同价格区间等内容更容易表现同质性（处于网络中相似的位置）https://zhuanlan.zhihu.com/p/64200072
本文目的在于学术交流，并不代表本公众号赞同其观点或对其内容真实性负责，版权归原作者所有，如有侵权请告知删除。
“综述专栏”历史文章
更多综述专栏文章，
请点击文章底部“阅读原文”查看
分享、点赞、在看，给个三连击呗！