H好菇凉666用万字长文聊一聊 Embedding 技术( 九 )

其中，是归一化的拉普拉斯矩阵的特征向量的矩阵：，和分别表示度矩阵和图的邻接矩阵。由于上述卷积运算的计算复杂度较高（相乘的计算复杂度为$O(N^2) ，以及图的拉普拉斯分解计算量较大），使得传统的普卷积运算无法得到有效应用。
为了缓解计算问题， Hammond在2011年的论文《Wavelets on graphs via spectral graph theory - HAL-Inria》中提出可以用切比雪夫多项式近似核卷积：
其中，，表示的最大特征值。是切比雪夫多项式系数向量。通过使用切比雪夫多项式展开，卷积运算可以通过递归近似：取多项式的前K项表示对k跳的领据及特征进行卷机运算。
Thomas等人在2017年对上式做了进一步简化：限制每个卷积层仅处理一阶邻居特征，通过采用分层传播规则叠加多层卷机，从而实现对多阶邻居特征的传播。通过限制卷机核的一阶近似能缓解节点度分布非常宽的图对局部邻域结构的过度拟合问题。如下图所示，通过集联多个卷积层，节点能聚合多个邻居节点特征。

本文插图
使用切比雪夫一阶展开（K=1）的核卷积+非线性单元如下：
其中，表示第层卷积核的输出，作为的数据，为各节点的特征。是卷积核的一阶近似，可以简单理解成邻接节点特征的加权平均。为非线性激活函数，为第层的卷积核参数（每个节点共享）。
Thomas等人在设计卷积核时做了两个trick：

每个节点增加了selp-loop ，使在卷积计算时能考虑当前节点自身特征：
对进行对称归一化：。避免了邻接节点数越多，卷积后结果越大的情况。此外这个操作还能考虑邻接节点度大小对卷积核的影响。

GraphSAGE（Graph SAmple and aggreGatE）是基于空间域方法，其思想与基于频谱域方法相反，是直接在图上定义卷积操作，对空间上相邻的节点上进行运算。其计算流程主要分为三部：

对图中每个节点领据节点进行采样
根据聚合函数聚合邻居节点信息（特征）
得到图中各节点的embedding向量，供下游任务使用

本文插图
GraphSAGE生成Embedding向量过程如下：

本文插图
其中K表示每个节点能够聚合的邻居节点的跳数（例如K=2时，每个顶点可以最多根据其2跳邻居节点的信息来表示自身的embedding向量）。算法直观上是在每次迭代中，节点聚合邻居信息。随着不断迭代，节点得到图中来自越来越远的节点信息。
邻居节点采样：在每个epoch中，均匀地选取固定大小的邻居数目，每次迭代选取不同的均匀样本。
GraphSAGE的损失函数如下：
其中，和表示节点和的embedding向量，是固定长度的邻居觉点，是sigmoid函数，和分别表示负样本分布和数目。
对于聚合函数的，由于在图中节点的邻居是无序的，聚合函数应是对称的（改变输入节点的顺序，函数的输出结果不变），同时又具有较强的表示能力。主要有如下三大类的聚合函数：