LasGNN
在搜索广告平台中，我们通常关注两个目标：用户搜索请求和广告之间的相关性以及CTR，然而传统的召回模型往往只关注相关性目标而忽视了CTR。如果在召回阶段只关注相关性，会和后续排序目标不一致，给搜索用户、商家、平台三方都带来损失。
在第一代无监督图模型中，我们面向相关性目标，提出了基于游走的大规模异构Graph Embedding算法LsHNE。LsHNE是一种无监督的学习方法，目标是通过节点Embedding的内积来反应节点之间的相关性，从而刻画图的结构信息。
虽然LsHNE已经取得了出色的效果，其仍然存在两个主要问题。1）LsHNE本质上是一个无监督模型，缺乏面向CTR/RPM目标进行有监督学习的能力。2）对冷门节点不友好。LsHNE通过图游走以及负采样的方式来产生训练样本，对于含有极少量连接边的冷门节点，只能以极低的概率出现在训练样本中，因此往往难以学习到鲁棒的表达。
由于图结构天然的满足基于流形假设的半监督框架，我们可以很自然的引入半监督学习，将CTR作为学习目标，充分利用Label数据和丰富的Unlabel数据；同时我们可以使用图卷积网络（GCN）来学习节点之间的相关性，标注节点的embedding信息可以通过异构卷积网络传播至周围的无标注节点，对冷门节点更加友好。因此，我们可以天然的将CTR和相关性目标融合起来。
然而这样的大规模异构网络在模型设计和应用层面面临着两个巨大的挑战，我们创新地提出了相应的解法。
1）异构网络。我们的网络是由多种类型的节点和多种类型的边组成的异构网络，而传统的GCN方法大部分都应用在同构图，如果我们直接将传统的GCN方法应用在异构网络上会带来训练参数爆炸的问题。为了解决这一难题，我们首次将metapath的思想应用于图卷积网络中，并提出了metapathGCN模型。
2）大规模。除此之外，我们的异构网络中有十亿量级的节点和百亿量级的边，传统的GCN方法并无法支持该量级的计算，基于Node-wise的邻居采样会面临邻居数随着层数指数增长的问题。为此，我们提出了metapathSAGE模型，在模型中我们设计了Layer-wise+Beam Search的邻居采样的方法，使得大规模的多层邻居卷积成为可能。
基于metapathGCN和metapathSAGE模型，我们提出了第二代半监督大规模异构图的广告检索方案LasGNN。
首先，我们根据用户日志以及相关商品、广告数据，为搜索召回场景构造了一张丰富的搜索交互图，如图所示。图中包含item、query、ad等节点，分别表示召回场景下的不同实体。为深度表达不同节点间的关联关系，图中加入不同维度刻画的多种类型边：
1）用户行为边：表示用户的历史行为偏好。
i. 点击边：顾名思义，表示query和item/ad之间的点击；
ii. session边：表示同session同query下共同点击过的item/ad；
iii. cf边：表示不同节点间的协同过滤关系；
其中i和ii侧重于刻画用户的短时偏好，iii侧重刻画用户长时偏好。
2）内容相似边：表示节点间文本相似度，方便刻画冷门节点。
3）属性相似边：表示节点间领域（如品牌、种类等）重叠程度。
目前我们构造的大规模异构图包含上亿节点以及百亿边，训练样本规模达200亿。
以往的研究实验验证了不能将同构图表示学习方法直接应用到异构网络上，受metapath2vec的启发，我们提出了一种基于meta-path的GCN方法，对指定类型邻居进行汇聚。作为GCN构建的模式指导，一个阶metapath 可以定义为
，其中
表示第l-1层与第l层节点间边所属类型,
表示第
层节点所属类型。在metapath
的指导下，第
层邻居选择方法可定义为：
其中，和
分别表示节点和边类型求取函数。
与之对应，的卷积操作也可以表示为：
其中：
表示第
层的节点
满足metapath条件的邻居,
表示此时节点间边权重。
需要注意的是，为了防止参数爆炸和模型过拟合，不同metapathGCN共享权重
。同时共享权重也有助于将embedding结果映射到一致的空间中。
相同的节点在不同metapathGCN中可能会产生不同的embedding结果，为了统一的embedding表示，选用attention机制对相同节点类型的metapathGCN embedding结果进行聚合：
其中，假设节点类型为
，
表示第
层节点类型为
的metapath集合。
因超高的算法复杂度和参数量级，GCN是无法直接应用到超大规模网络中的，所以我们提出了一种基于beam-search的layer-wise邻居采样方法，对metapathGCN进行优化。
具体方法则是根据对节点与上层节点所有连边权重之和作为节点的权重，根据权重选取top 个节点作为候选集。为了防止邻居选择结果过分偏向于少量热门节点，我们基于节点的权重
进行加权采样，得到
个节点作为当前层保留邻居。权重
可表示为：
不同于node-wise的采样方法，layer-wise采样方法可以在兼顾上层节点所有连接关系的基础上，将邻居节点增长趋势由指数级降到线性级别，即可以将每层节点个数控制在固定范围内。
加入邻居采样后，我们也对卷积结构进行了相应的调整，借鉴GraphSAGE的思路，将卷积结构更改如下：
不同于[1]和[2]，我们提出的启发式layer-wise邻居采样方法在大规模图中有着更低的计算复杂度，在实际应用中有更好的表现。
基于3.2提出的metapathSAGE模型，我们构建了如上图所示的工业级广告召回架构，整个召回架构以广告的点击状态为标签，面向CTR进行学习，同时利用metapathSAGE学习结构信息，即广告、商品、query之间的相关性。
我们通过PV/Click数据构造样本，将当前请求下被点击的⼴告视为正例，展现未点击的⼴告视为负例。所以我们的样本结构如下：
其中，request可表示为：
我们使用sigmoid 交叉熵作为损失函数，整个架构的优化目标可以表示为：
其中分别表示虚拟请求节点和广告节点的embedding结果，
表示虚拟请求节点和广告节点embedding距离度量函数。
在我们的检索方案中，为了充分表达用户的请求意图，我们将用户的请求由传统的序列结构表示为子图结构；同时我们在不同的metaSAGE模块中设计了embedding共享机制。
为个性化表达用户意图，我们构建了一个虚拟请求节点。该节点由当前query节点和个前置点击商品（广告）节点组成。不同于传统召回方法将类似的用户意图视为序列，我们利用卷积结构，将用户意图视为如上图所示的子图结构。相比于序列结构的单一表达，子图结构的虚拟请求节点可以通过多层异构图卷积同时刻画query、用户实时意图以及长时意图信号，从⽽表征更为丰富更深层次的⽤户搜索意图。同时考虑到request节点的稀疏性，并未将其作为实际节点置⼊异构⽹络中进⾏学习，⽽是⽤query和item/ad的embedding结果联合表达。
值得注意的是，架构中所有metapathSAGE模块共享feature embedding层。一则是因为不同类型节点有相同类型的特征，二则有助于将不同类型的节点embedding结果映射到同一空间，三则能够防止参数爆炸。
我们在离线数据集上对比了LR、GBDT、metapathSAGE以及其不带图卷积版本，其中LR和GBDT使用了63天作为训练数据，metapathSAGE以及其不带图卷积的版本使用了6天数据作为训练数据，所有的方法均采用下一天的数据作为测试数据。如下图所示，对比非卷积版本
，我们的方法metapathSAGE目前在离线Next AUC上千分位提升9个点。
我们在公开数据集Aminer上也和传统的Graph Embedding方法进行对比。和BaseLine的方法一样，我们首先在全图上训练每个节点的embedding，接着将node embedding作为输入，使用sigmoid分类器对节点做多分类。我们使用公开的walk序列和负样本训练triplet loss，得到节点的embedding。节点多分类的Macro-F1和Micro-F1效果如下图所示(其他BaseLine的方法直接采用metapath2vec文章结果)，我们的方法metapathGCN和metapathSAGE相比于BaseLine方法均有明显的提升。
[1] Chen, Jie, et al. “FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling.” International Conference on Learning Representations, 2018.
[2] Huang, Wenbing, et al. “Adaptive Sampling Towards Fast Graph Representation Learning.” Neural Information Processing Systems, 2018, pp. 4563–4572.