2W字长文 | 漫谈工业界图神经网络推荐系统（2）

1.3 Scalable GNN

1.3.1 问题背景

一方面，GCN在设计之初其卷积操作是在全图上进行的，在每一层对于所有结点聚合1阶邻居并融入自身表征，这样第K层的输出表征就包含了K阶邻居的信息。另一方面，图数据不同于其他数据集，结点之间存在边这种关联，无法直接通过随机采样进行Mini-Batch训练。因此GNN的许多模型无法直接扩展到大图上，然而真实业务场景中的图数据往往都是亿级别的。该章节介绍一些大图上训练GNN的方法，主要分为基于采样的方法和基于预处理的方法。

1.3.2 基于采样的方法

基于采样的方法可以分为三小类，Node-Wise Sampling，Layer-Wise Sampling和Subgraph-Wise Sampling。其中Node-Wise Sampling是一种比较通用有效的方法，在GNN4Rec方向中应用得最多；Layer-Wise Sampling其实就是一种弱化地Node-Wise Sampling，效果不咋地意义不大；Subgraph-Wise Sampling比较受限于场景，这一点在后面总结GNN4Rec工作时会提到。

Node-Wise Sampling[5]：由GraphSage首次提出，首先随机采样一个batch的root结点，接着从root结点出发迭代地采样1-K阶邻居，在训练时则迭代地聚合K-1阶邻居，最终得到每个root结点融合了K-Hop邻居信息的表征。这种方法主要存在以下几个缺点：

随着层数增加，采样到的邻居数量指数增长

结点的利用率低（许多结点的表征存在大量重复计算）

没有考虑采样造成的偏差和方差

Node-Wise Sampling

Layer-Wise Sampling[21]：由FastGCN首次提出，对于每一层都采样固定数量的结点，最终采样的结点数量与层数成线性关系；同时分析了采样带来的偏差与方差（做了大量简化），确保采样方法尽可能无偏有效。但是，该方法采样到的结点连接非常稀疏，不利于进行有效地消息传递，实际上实验效果也确实比较差。

Layer-Wise Sampling

Subgraph-Wise Sampling[22]：由ClusterGNN首次提出，首先用图划分算法（Metis等）将原图划分为一些子图，这些子图具有“高内聚，低耦合”的特点，接着在每个Batch随机采样一个子图（或多个子图合并为更大的子图从而降低方差），在该子图上训练完全的GCN。GraphSAINT进一步考虑了子图采样的偏差，通过两个正则化系数来修正子图采样给“邻居聚合”与“损失函数”带来的偏差，不过从之前个人复现的情况来看[23]，GraphSAINT的实验结果主要是靠论文中没有提到的代码中的一系列Trick。

Subgraph-Wise Sampling

1.3.3 基于预处理的方法

基于预处理的方法是针对一类特定的GNN模型设计的，不具有通用性，这类模型将消息传递与特征变换解耦，对于消息传递部分可以预计算（例如SGC，PPNP，SIGN[24]），最后退化为数据预处理+MLP（也可以是其他模型），而MLP部分是可以直接随机采样做Mini-Batch训练的。特别地，对于PPNP，迭代计算的方式复杂度还是挺高的，因此可以进一步使用传统的Push算法[25]或蒙特卡罗算法[26]近似计算。

Push算法

1.4 Heterogeneous GNN

1.4.1 问题背景

现实场景中大多是异构图，结点类型和边类型是多样的，例如，在电商场景，结点可以是Query，Item，Shop，User等，边类型可以是点击，收藏，成交等，GCN，GAT等模型无法建模这样的异构性：一方面，不同类型的结点的Embedding维度就没法对齐；另一方面，不同类型的结点的Embedding位于不同的语义空间。这限制了模型做特征融合和Attention计算。以下会介绍几个比较典型的异构GNN模型，它们都是通过Node or Edge Type-Specific Transformation来建模结点或边的异构性。不过KDD 2021[27]一篇工作通过实验比较发现，对异构性的建模带来的提升十分有限，该方向的工作大多存在不公平比较的问题，实际上只使用简单的GCN或GAT就能取得非常好的效果，吊打一堆所谓的SOTA Heterogeneous GNN。最近也有在做异构图建模的工作，业务场景是手淘的下拉推荐（搜索场景），从离线的实验结果来看，当结点的特征比较复杂且数据的规模比较庞大时，对异构性的建模效果还是比较明显的。

1.4.2 代表工作

RGCN[14]：RGCN可能是最早考虑异构性的GNN模型了，通过Edge-Type-Specific Transformation建模边的异构性。

RGCN

HAN[15]：通过Node-Type-Specific Transformation建模结点的异构性，在计算Attention时不仅考虑了某Meta-Path下邻居的重要性，还考虑了不同Meta-Path之间的重要性。不过HAN比较依赖Meta-Path的人工选择。

HAN

KGAT[28]：通过Edge-Type-Specific Transformation + Ralation Embedding（类似于TransR）建模结点和边的异构性。

KGAT

HGT[29]：在Attention计算和Message Passing阶段都考虑到了对异构性的建模，分别使用Node-Type-Specific Transformation和Edge-Type-Specific Transformation建模结点和边的异构性（不过这参数量相当大呀）。

HGT

1.5 图神经网络的优势

在应用某项技术解决业务场景中的某个问题时，我们需要充分了解这项技术的特点和优势，以下从五个方面谈谈个人对GNN优点的理解。

GNN VS MLP/CNN/RNN：图数据中结点邻居具有两个特点，一是数量不定，二是顺序不定，因此MLP/CNN/RNN无法直接处理这样的非欧式数据而只能用GNN建模。实际上，我们可以将GNN看做一种更加泛化的模型，例如，RNN相当于线性图上的GNN，而Transformer相当于完全图上的GNN。

GNN VS Graph Embedding：在GNN火起来之前已经涌现出很多Graph Embedding方法，并被广泛应用在搜推的向量召回阶段，这类方法受Word2vec[30]启发设计，从最初的的Item2Vec[31]的Item Sequence+Skip-Gram，到DeepWalk[32]的Random Walk+Skip-Gram；到Node2Vec[33]基于平衡同质性和结构性的考虑改进Random Walk部分；到MetaPath2Vec[34]基于对图的异构性的考虑改进Random Walk部分；到EGES[35]引入属性数据缓解行为数据的稀疏性，可以发现这类方法都遵循着Skip-Gram的范式。GNN相比这些方法的优点主要体现在四处：

GNN可以结合目标任务端到端地训练，而Graph Embedding更像是预训练的方式，其学习到的Embedding不一定与我们的目标任务相关，特别是在样本规模庞大的业务场景，端到端训练得到的Embedding比预训练得到的Embedding更有效。

GNN的层级网络结构方便与其他深度学习技术结合（缝合怪水论文最爱），例如GCN+Attention=GAT。

GNN可以适用Inductive的任务，即当图的结构发生变化后，例如加入了一些新的结点，Graph Embedding方法就需要重新训练模型，而GNN可以使用类似GraphSage Node-Wise Sampling的方式，使用已经训练好的模型直接对新的结点进行推断。

GNN可以使用更加丰富的特征，Graph Embedding方法本质上使用的是ID特征，GNN在消息传递的过程中可以使用多种特征。

GNN VS Feature Concat & Collaborative Filtering & Proximity Loss：GNN相比后三种方法的优点可以统一归纳为：通过堆叠多层显示地学习高阶的关联信息。Feature Concat表示将特征拼接到一起然后通过特征交叉（例如FM，NFM等）可以学习到一阶的属性关联信息（区别于交叉特征的阶数），例如，user a买过item b，item b和item c都具有属性attribute a，那么user a也有可能购买item b，但是Feature Concat不保证能学到高阶的属性关联信息；Collaborative Filtering可以通过用户历史行为学习到一阶的行为关联信息，例如，user a和user b都购买过item a， user b又购买过item b，那么user a也有可能购买item b；Proximity Loss表示在损失函数中加入正则项使得相邻的结点更相似，但是一方面它是一种隐式的方式，另一方面想确保学习到高阶的相似关系，就需要加入更复杂的2,3，...，K阶正则项，实际上这也是GCN提出时的出发点之一。

KGAT论文中的例子