定期更新干货算法笔记和世间万物的学习记录～
图表示学习是目前搜索、推荐、广告等系统中常用的一种方法，利用场景数据构造图，建立用户、商品等节点之间的联系，然后利用图学习的方法学习每个节点的表示。这个表示一般会让相似或相关的实体的表示更接近，这些表示可以提升下游多种任务的效果。本文梳理了图表示学习的经典模型，包括3个阶段，分别是基于随机游走的图表示学习、基于图神经网络的图表示学习，以及异构图中的图表示学习。
1
基于随机游走的图表示学习
DeepWalk: Online Learning of Social Representations（2014）中提出的DeepWalk是最早一批实现图表示学习的工作，DeepWalk提出的背景问题是对社交网络上的每个成员进行分类。为了解决这个分类问题，文中提出无监督学习方法利用图结构学习每个节点的一个低维表示。
DeepWalk借鉴了早期词向量训练方法SkipGram，利用节点（SkipGram中是单词）的共现关系学习每个节点（单词）的表示。具体实现方法为，首先在图上随机选一个节点，采用随机游走的方式，生成一个序列（可以类别为多个单词组成的一句话）。接下来，采用滑动窗口的方法，在这个节点序列上构造共现样本。重复多次上述随机游走 滑动窗口生成样本后，使用SkipGram 层次Softmax的方法进行无监督训练。通过这种方式，得到了每个节点类似词向量的表示，在社交网络中经常共现在一起的节点具有相似的表示。
node2vec: Scalable Feature Learning for Networks（2016）提出的Node2vec仍然是基于SkipGram的思想学习图上节点的embedding，但是对采样方式进行了优化。文中提出，在图中进行邻居节点采样时，主要包括BFS和DFS两种极端采样方法，BFS即广度优先遍历，每次采样节点都要求是该节点的一跳直接邻居，这种采样方法的结果是生成的图表示更关注局部信息。与之相对的，DFS为深度优先遍历，每次采样节点都尽可能增加和初始节点的距离，这种采样方法的结果是生成的图表示更关注全局信息。在图中一般有两个假设homophily和structural equivalence，homophily表示相邻的节点、距离比较近的节点，其属性应该具有相似性；structural equivalence表示周围结构相似的节点属性和表示应该具有相似性。BFS通过捕捉局部信息，生成的表示更倾向于描述每个节点的结构信息，适用于structural equivalence假设；DFS更多反映了整个图的宏观信息，适用于homophily假设。
具体的，Node2vec采用如下的随机游走方式构造训练样本。如下图，假设上一步已经从t游走到v，现在在v点判断下一步要走向哪个节点，由p和q两个参数组成。p越小，越有较大的概率回到初始点，这就强制了游走在初始节点附近进行（即BFS）；q越小，随机游走更倾向于于探索更远的节点（即DFS，x2和x3距离初始节点t是二跳，x1是一跳）。
此外，LINE: Large-scale Information Network Embedding（2015）也是一种类似的图表示生成方法。这三种方法的关系是，Deep Walk可以理解DFS随机游走进行样本生成，LINE是BFS随机游走样本生成，而Node2vec结合了BFS和DFS，可以理解为Deep Walk和LINE的升级版。
2
基于图神经网络的图表示学习
上述基于random walk的方法是由随机游走和表示学习多个阶段组成的，每个阶段的优化目标不同，不是端到端的模型。Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering（2017）、SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS（ICLR 2017）提出了图卷积（ChebNet、GCN）网络实现图上的表示学习，也是现在仍然非常常用的图学习基础方法。第二篇文章是在第一篇文章的基础上做了简化，使运行效率提升，也是目前最常用的图卷积模型之一。文中最初想要解决的问题是，对图上的节点作分类，并且只知道图中一部分节点的label，那么问题的核心就是如何将有label的节点信息通过图结构传播到无label的节点上，进而实现无label节点的分类。图卷积有深入的公式推倒过程，会在后续的文章中详细介绍，这里我们重点介绍其基本思路。每一层图卷积传入上一层每个节点的表示，然后利用图的结构信息（用拉普拉斯矩阵表示）对周围节点的表示进行融合，得到每个节点在下一层的表示，经过多层邻居节点信息的融合，在每层不断更新节点表示，核心公式如下（可以理解为一个利用图结构进行信息融合的过程，详细推倒和含义后续文章会详细介绍）：
除了图卷积外，Attention也被用来实现图表示学习。在GRAPH ATTENTION NETWORKS（ICLR 2018）中，提出使用多头注意力机制学习图中节点之间的关系，来进行信息融合。和GCN相比，GAN相当于使用attention score来代替拉普拉斯矩阵计算的融合方法。GAN的具体实现为，计算每个节点和其邻居节点的attention score，再用attention score融合邻居节点的表示得到该节点新的表示，公式表示如下：
上面的方法都需要在整张图上进行学习，一个问题是当图节点太多的时候开销太大，另一个问题是由于直接学习所有节点的表示，当有一些新的原来图上没有的节点加入时候，无法生成新节点的表示。为了解决这两个问题，Inductive Representation Learning on Large Graphs（NIPS 2017）提出了GraphSAGE方法。该方法的思路为学习一个aggregation函数而非直接学习节点表示，利用每个节点的邻居节点表示汇聚成该节点的表示，并通过采样的方式提升训练效率。GraphSAGE的基本思路如下图：
Aggregation function部分对于每一个节点，获取其邻居节点，并使用一种aggregation方法，对当前节点及其邻居节点的表示进行融合，得到该节点新的表示，通过多层的aggregation让每个节点逐渐吸收更大范围的信息。文中提出的aggregation方法包括mean、LSTM、pooling三种方法。在学习每个节点的表示时，不会融合所有邻居节点，而是采样固定数量的邻居节点进行融合。模型采用无监督损失函数进行优化，如果两个节点之间是k阶邻居，即从A节点到B节点走k步可以到达，那么就作为正样本，其他作为负样本，公式可以表示如下，其中Pn表示负采样分布：
3
基于metapath的异构图表示学习
上面介绍的图表示学习方法假设输入的图是同构图，即图中每个节点都是相同类型的。然而在实际应用中，很多场景的数据都是异构图，例如在电商平台中，需要建立用户、商品、搜索词等多种类型节点之间的图，不同类型节点之间的边类型所代表的含义也是不同的。这种情况下，使用简单的random walk生成序列将无法捕捉这种异构信息，并且random walk会由于不同类型节点数量、路径数量不同存在采样的bias。
metapath2vec: Scalable Representation Learning for Heterogeneous Networks（KDD 2017）提出了metapath2vec方法，针对异构图进行表示学习，核心思路仍然是基于随机游走 skipgram的方法，但是通过引入metapath修改随机游走方式来实现异构图表示学习。首先定义meta-path，指的是一个预先定义的随机游走规则，要求每次游走的节点为对应类型。例如下图中的例子，APA表示必须从author类型节点走到paper类型节点再走到author类型节点。在定义众多meta-path后，随机游走以这些meta-path为指导构造采样序列。这种基于meta-path进行随机游走的好处是让每个采样的序列都是有意义的，而不像一般的随机游走，各种类型节点混杂在一起。
为了在输出阶段考虑不同节点的类型，文中进一步提出metapath2vec 方法，在输出阶段的负采样过程中，只能采样相同类型节点的负样本进行softmax，而不是在所有节点中随机采样，如下图：
随后，越来越多的异构图学习方法逐渐提出，包括RGCN、HIN2Vec、MAGNN等，很多异构图学习方法都是基于meta-path的思路，构造可视为同构的子图，再利用GCN等方法在子图上学习表示信息，并对不同子图信息进行融合。
4
总结
本文介绍了图表示学习发展的3个阶段，从随机游走 skipgram的两阶段方法，演变到图卷积、GAT等端到端的图学习方法，再到基于meta-path的异构图表示学习方法。图学习目前是工业界非常常用的方法之一，利用图表示学习，可以学习到图中每个实体的良好表示，帮助下游其他任务取得更好效果。
END
