GNN(续)

十四、GCMC

  1. 推荐算法有两个主流方向:基于内容的推荐、基于协同过滤的推荐。

    • 基于内容的推荐使用 useritem 的内容信息来进行推荐
    • 基于协同过滤的推荐使用 user-item 交互数据(如购买、评分等)来进行推荐
  2. 给定用户集合 以及 item 集合 。考虑评分矩阵 ,矩阵的第 行、 列代表用户 item 的评分

    事实上我们已经有部分观测到的评分 observed rating ,即 。推荐算法的目标是预测未观测到的 user-item 评分,即 。这等价于矩阵补全matrix completion 问题。

    论文 《Graph Convolutional Matrix Completion》 将矩阵补全问题视为一个图的链接预测问题:以二部图来表示用户和 item ,以用户顶点和 item 顶点的链接来表示观测到的评分。未观测评分的预测可以转换为该二部图的链接预测问题。

    另外,还可以将内容信息通过顶点特征的方式自然而然地纳入到该框架中,从而结合了 内容信息以及交互信息。

    因此,论文提出了图卷积补全框架 graph convolutional matrix completion:GC-MC ,一种基于图的深度学习技术最新进展的图的矩阵补全自编码器框架。

    • 首先利用自编码器,以在二部图上进行消息传递的方式来生成 user embeddingitem embedding
    • 然后利用双线性解码器,基于 user embeddingitem embedding 来重建二部图的已观测链接。

    当有额外的辅助信息side information 可用时(如社交网络图结构、用户内容信息、顶点内容信息),将矩阵补全问题视为二部图上的链接预测问题带来的好处尤为明显。将辅助信息和交互数据结合在一起可以有效缓解冷启动问题。

    实验表明,我们的 GCMC 模型超越了最新的 SOA 方法。

  3. 基于 useritem 的自编码器是协同过滤的一个方向,可以将其视为我们的图自编码器模型的特例:在编码器中仅考虑 user embedding 或者 item embedding (与之对比,我们的图自编码器同时考虑了 user embedding/ item embedding )。

    • AutuRec (Sedhain et al.) 是第一个此类的模型,其中将观测到的 user 评分向量(或者观测到的 item 评分向量)映射到低维潜在空间中,并使用解码器重构。模型的损失函数为最小化重构的均方误差 MSE

    • CF-NADE ( Zheng et al.) 是上述自编码器体系结构的特殊情况。

      • user-based setting 中,消息仅从 item 传递给 user;在 item-based setting 中,消息仅从 user 传递给 item

        我们的图自编码器同时考虑了 item 传递给 user ,以及 user 传递给 item

      • 未观测的评分默认为 3 分(5分制),从而构建了全连接的交互图。

        我们的模型仅考虑观测的评分,因此不是全连接的。

      • CF-NADE 随机对顶点排序,并通过随机的 cutincomming mmesage 拆分为两组,并且仅保留其中的一组。因此该模型可以视为降噪自编码器,因为在每轮迭代中都会随机 drop out 输入空间的一部分。

  4. 很多流行的协同过滤算法都是基于矩阵分解 MF 模型,这种方式将评分矩阵进行低秩分解:

    其中: 表示用户 embedding 矩阵,每一行代表一个用户的 user embedding 向量; 表示 item embedding 矩阵,每一行代表一个 item embedding 向量;embedding 向量的维度,并且满足

    • 概率矩阵分解 PMF 假设 中的评分是带高斯噪声的独立随机变量,然后最大化观测评分。这种最大似然估计等价于 中的观测值和 中对应的预估值之间的均方误差最小化。
    • BiasedMF 通过融合 user-specifc bias, item-specific bias, global-bias 来改进 PMF
    • 神经网络矩阵分解 NNMF 通过将 user embeddingitem embedding 输入到前馈神经网络来扩展 MF 方法。
    • 局部低秩近似使用不同的低秩逼近的组合来重构
  5. 在矩阵补全问题中,目标是使用低秩矩阵来逼近 。但是,秩 rank 的最小化是一个棘手的问题。Candes & Recht 使用最小化核函数(矩阵的奇异值之和)来代替秩的最小化,从而将目标函数变成了可处理的凸函数。

    • Inductive matrix completion:IMCuseritem 的内容信息融入到特征向量中,并预估 user item 的评分为:

      其中 为用户 的特征向量, item 的特征向量。 为低秩的、待学习的user embedding 矩阵和 item embedding 矩阵。

    • geometric matrix completion:GCM 模型通过以 user graphitem graph 的形式添加辅助信息,从而对矩阵补全模型进行正则化。

    • GRALS 模型使用一种更有效的交替最小二乘优化方法,从而优化带正则化的图矩阵补全问题。

    • sRGCNN 提出通过在图上使用卷积神经网络,并结合循环神经网络来建模动态的评分过程,从而将 graph-based 辅助信息纳入矩阵补全模型中。

      和他们不同,GCMC 直接使用图卷积编码器/解码器对评分的二部图进行建模,通过一个non-iterative 步骤即可预测未观测的评分。

      相比之下,sRGCNN 需要用迭代式的多个 step 才能预测评分。

14.1 模型

  1. 给定用户集合 以及 item 集合 。考虑评分矩阵 ,矩阵的第 行、 列代表用户 item 的评分

    我们将矩阵补全问题转化为链接预测问题。考虑二部图 ,其中 为所有顶点集合, 表示所有链接集合(每个链接表示一个观测评分), 为评分等级(这里最高 级评分)。

    表示用户 item 的评分为

    如下图所示:

    • 左图为评分矩阵 (原始论文中记作 ),每一项对应于 user-item 之间的评分(评分在 1~5 分之间),或者未观测(评分记作 0)。
    • 第二幅图表示 user-item 评分的二部图,边对应于评分行为,边上的数字对应于评分数值。
    • 最后两幅图表示矩阵补全问题可以转换为二部图上的链接预测问题,并使用端到端的可训练的图自编码器进行建模。

  2. 之前的 graph-based 推荐算法通常采用 multi-stage pipeline,其中包括图的特征抽取模型(如 graph embedding 模型)以及图的链接预测模型。这些模型都是独立分开训练。

    但是最近的研究结果表明:通过端到端的技术来建模图结构化数据可以显著提升效果。在这些端到端技术中,应用于无监督学习和链接预测的图自编码技术尤为突出。因此我们提出针对推荐任务的一种图自编码器的变种。

  3. 图自编码器由一个编码器和一个解码器组成,其中:

    • 编码器模型: 。其中:

      • 为输入的特征矩阵,每一行代表一个顶点的特征向量, 为顶点的特征向量维度。
      • 为图的邻接矩阵。
      • 为顶点的 embedding 矩阵,每一行代表一个顶点的 embedding 向量, 为顶点的 embedding 向量维度。
    • 解码器模型: 。解码器以一对顶点 embedding 为输入,并预测顶点 之间的连接性,即预估的邻接矩阵的项

    对于二部图 ,我们重新定义编码器为:

    其中:

    • user embedding 矩阵,item embedding 矩阵。

    • 为评分等级为 的邻接矩阵,它的元素在 {0,1} 内取值,并且当用户 item 的观测评分 否则为零。

      因此, 定义了原始评分矩阵中评分等级为 关联的邻接矩阵。

    类似地,我们重新定义解码器为:

    解码器输入一对 user-itemembedding 向量,并返回 user item 预估的评分

    我们通过最小化预测评分矩阵 和真实评分矩阵 之间的重构误差来训练该自编码器(注意:通常只考虑观测值上的重构误差)。通常评估重构误差的指标为 RMSE (将评分预测视为回归问题)或者交叉熵(将评分预测视为分类问题)。

    最后,我们注意到可以将最近提出的几个矩阵补全 SOA 模型纳入我们的框架中,并将它们视为我们模型的特例。

  4. 编码器:我们选择局部图卷积 local graph covolution 作为编码器模型。这类局部图卷积可以视为消息传递的一种方式,其中消息在图的链接之间传递和转换。

    在我们case 中,我们为每个评分等级分配一个level-specific 变换,使得从 item 到用户 的消息传递形式为:

    其中:

    • 为归一化常数,通常选择为 (左归一化left normalization) 或者 (对称归一化)。 为顶点 的邻域顶点集合。
    • 为评分等级 level-specific 权重矩阵。
    • 为顶点 的特征向量。

    同理,用户 item 的消息传递形式为:

    这里也可以选择使用不同的 level-specific 权重矩阵(即 user -> itemitem -> user 传递消失时,权重矩阵不同)。

    在消息传递之后:

    • 首先通过求和来聚合类型为 的所有邻居 的消息,得到领域类型为 的单个representation 向量
    • 然后将所有邻域类型的 representation 向量聚合,从而得到顶点的单个聚合向量
    • 最后对聚合向量进行变换,最终得到顶点的 embedding 向量

    以下公式为用户顶点 embedding 计算公式,item 顶点 embedding 也是类似的。

    其中第一行公式称作卷积层,第二行公式称作 dense 层。

    注意:

    • 当没有辅助信息可用时, dense 层对于 useritem 都采用相同的参数矩阵

      当存在辅助信息可用时, dense 层对于 useritem 都采用相互的参数矩阵 ,分别记作

    • 这里卷积层只有一层。虽然可以堆叠更多的卷积层来构建更深的模型,但是在最初的实验中我们发现堆叠更多卷积层并不能提高性能。

      同理,堆叠更多的 dense 层也不能提高性能。因此,最终我们选择单层卷积层 + 单层 dense 层的组合作为图编码器。

    • 这里给出的模型仅仅是一种可能性。虽然编码器的选择相对简单,但是也可以选择不同的变种。例如:

      • 可以使用神经网络来计算消息传递(),从而替换掉简单的线性变换。
      • 可以使用 attention 机制从模型中学习每个消息的权重,从而替代消息的归一化常数
  5. 解码器:我们使用双线性解码器 bilinear decoder 来重建二部图的链接。令用户 item 预估的评分为 ,则解码器输出预估评分为 的概率为:

    其中每个评分等级 关联一个可训练的参数 embedding 向量的维度。

    模型最终预估的评分为所有评分等级预估结果的期望值:

  6. 损失函数:模型训练期间我们将 GCMC 模型的损失函数定义为:最小化预估评分 的对数似然:

    其中:

    • 为示性函数:
    • 为观测值的mask 矩阵:对于观测值对应的项, ;对于未观测值对应的项,

    因此,上述目标函数仅在所有观测的评分上优化。

  7. GCMC 模型的整体框架如下所示(原始论文中采用了不同的符号, 就是这里的 )。

    GCMC 模型由图卷积编码器 以及双线性解码器 组成。其中:编码器从 user-> item 或者 item -> user 传递并变换消息;解码器根据 user embeddingitem embeddingpair 对来预估评分。

  8. drop out:为使得模型能够很好地推广到未观测的评分,我们以概率 随机丢弃某个顶点传出的所有消息,我们称之为 node dropout 。注意:和常规 dropout 一样,在消息丢弃之后需要 rescale

    这种 node 级别的 dropout 和常规的 dropout 不同。常规的 dropout 是在消息级别进行 dropout,称作 message dropout

    • message dropout 中,每条消息随机独立地丢弃,使得最终 embedding 对于边的扰动更为鲁棒。
    • 而在 node dropout 中,每个顶点随机独立地丢弃,使得最终 embedding 对于特定用户和特定 item 的影响更为鲁棒。这会缓解一些热门用户或热门item 的影响。

    最后,我们还对卷积自编码器的 dense 层的隐单元使用了常规的 dropout

  9. mini-batch 训练:为了训练较大的数据集(如 MovieLens-10M 数据集),我们需要对观测数据进行采样,从而进行 mini-batch 训练。这是将 MovieLens-10M 的完整模型加载到 GPU 内存所必须的。

    我们从每个等级的观测评分中采样固定比例的评分,然后仅考虑这 mini-batch 的损失。这样我们在训练过程中仅需要考虑当前 mini-batch 中出现的 useritem。这既是正则化的有效手段,又可以降低训练模型需要的内存。

    通过在 Movielens-1M 数据集上使用 mini-batch 训练和 full-batch 训练的实验对比(对比时针对二者分别调优了各自的正则化参数),我们发现二者产生了可比的结果。

    最后,对于 MovieLens-10M 以外的其它数据集,我们选择 full-batch 训练,因为 full-batch 训练相比 mini-batch 训练的收敛速度更快。

  10. GCMC 的实现中,我们可以使用高效的稀疏矩阵乘法来实现图自编码器模型,其算法复杂度和边的数量呈线性关系,即

    假设聚合函数 accum 为累加,则图卷积编码器为(采用左归一化):

    其中:

    • 为顶点的度矩阵 degree matrix
    • 可以替换为向量拼接(而不是累加)

    另外,采用对称归一化的图卷积编码器以及双线性解码器的向量化 vectorization 也以类似的方式进行。

  11. 辅助信息 side information:理论上可以将包含每个顶点的信息(如内容信息)的特征直接作为顶点的输入特征(即特征矩阵 ),并直接作用到图自编码器中。但是,当内容信息不足以区分不同的用户(或者 item)及其兴趣时,将内容信息直接馈入图卷积层会导致严重的信息流瓶颈。

    此时,可以通过单独的处理通道 channel,从而将用户特征向量或 item 特征向量以辅助信息的形式纳入全连接层中。

    由于内容信息灌入到模型的最后一层,因此上述的信息流瓶颈不会出现。因为瓶颈只会出现在中间层。

    我们选择输入特征矩阵 为一个单位矩阵,即每个顶点的输入特征为顶点的 one-hot 表示。令用户顶点 的辅助信息特征向量为 ,则作用到全连接层之后,顶点的embedding 为:

    其中:

    • 都是可训练的权重矩阵, 为可训练的 bias 向量。
    • user 顶点的参数为 ,而 item 顶点的参数为 。即 user,item 类型的顶点使用两套不同的参数。
    • 本文实验中使用的数据集中,用户内容以及 item 内容的信息大小有限,因此我们使用这种辅助信息的方式。

    注意:辅助信息不一定要以顶点特征向量的形式出现,也可以是图结构(如社交网络)、自然语言或者图像数据。此时可以将上式中的 dense 层替换为适当的可微模块,如 RNNCNN 或者其它图卷积网络。

  12. 编码器权重共享:在辅助信息的方式中,我们使用顶点的 one-hot 向量作为输入。此时矩阵 的第 列可以视为顶点 在评分等级 下的潜在因子向量。这些潜在因子向量通过消息传递,被传递到与该顶点相连的 user 顶点(如果顶点 item 顶点)或者 item 顶点(如果顶点 user 顶点)。

    但是,并非所有用户拥有评分等级为 的相同评分数量,也并非所有 item 拥有评分等级为 的相同评分数量。这将导致 的某些列的优化频次明显低于其它列。因此,对于不同的 我们期待矩阵 之间的权重共享,从而缓解该优化问题。

    我们实现了以下权重共享策略:

    由于更高的评分等级包含的权重矩阵数量更多,因此我们称这种权重共享为有序权重共享 ordinal weight sharing

  13. 解码器权重共享:对于成对双线性解码器,我们采用一组基权重矩阵 basis weight matrix ,其中:

    其中:

    • 为基权重矩阵的数量。注意,为缓解过拟合并减少参数数量, 应该小于评分等级数量
    • 为可学习的参数,用于决定对每个解码器权重矩阵 的线性组合的系数。

    这种解码器的权重共享是一种有效的正则化手段。

14.2 实验

  1. 数据集:我们在多个常见的协同过滤 benchmark 数据集上评估我们的模型。

    • MovieLens100K,1M, 10M)数据集:包含多个用户对多部电影的评级数据,也包括电影元数据信息(如电影题材)和用户属性信息(如用户年龄、性别、职业)。该数据集有多个版本,对应于不同的数据量。
    • Flixster 数据集:来自于社交电影网站 Flixster 的电影评分数据集,数据集包含了用户之间的好友关系。
    • Douban 数据集:来自豆瓣的电影评分数据集,数据集包含用户之间的好友关系。
    • YahooMusic 数据集:来自 Yahoo! Music 社区的用户对音乐家的评分数据集。

    对于 Flixster,Douban, YahooMusic 数据集,我们使用Geometric matrix completion with recurrent multi-graph neural networks 论文提供的预处理的子集。预处理后,每个数据集包含 3000 个用户顶点以及 3000item 顶点,以及对应的 user-useritem-item 交互图。

    下图给出了数据集的统计信息,其中Features 表示是否包含用户特征或者item 特征,Ratings 表示数据集的评分数量,Density 表示评分矩阵中已观测评分的占比,Rating level 表示评分等级范围。

  2. baseline 模型:

    • 矩阵补全模型,包括 MC, IMC, GMC, GRALS, sRGCNN 。具体细节参考前文所述。
    • 矩阵分解模型,包括 PMF, I-RBM, BiasMF, NNMF 。 具体细节参考前文所述。
    • 协同过滤模型,包括 LLORMA-Local, I-AUTOREC, CF-NADE 。 具体细节参考前文所述。

    另外我们还对比了我们不带额外信息的GCMC 模型,以及带辅助信息的 GCMC+Feat 模型。

  3. 参数配置:

    • 所有 baseline 方法直接采用原始论文中的实验结论数据(因此也不需要实现和运行这些 baseline 方法)。

    • 对于 GCMC 模型,我们通过验证集从以下超参数范围选择最佳的超参数:

      • 聚合函数accumulationstack vs sum
      • 是否在编码器中使用有序权重共享:是 vs 否。
      • 编码器中 为归一化常数:左归一化 vs 对称归一化。
      • 顶点dropout 比例:

      另外,除非另有说明,否则我们使用以下超参数配置:

      • 使用学习率为 0.01Adam 优化器
      • 解码器基权重矩阵数量
      • 编码器采用:维度 500 的单层卷积层(使用 ReLU 激活函数) + 维度 50 的单层 dense层(无激活函数)

      最后,我们使用学习模型参数的指数移动平均(衰减因子 0.995)在保留的测试集上评估模型。

  4. Movielens-100k 数据集(特征向量形式的辅助信息实验):我们直接使用数据集原始的 u1.base/u1.test 的训练集/测试集拆分结果。对于该数据集,我们使用辅助信息来参与所有模型的训练。

    在该数据集我们对比了矩阵补全 baseline 方法和我们的 GCMC 方法。其中:GMC, GRALS,sRGCNN 通过 近邻图来表示 user/item 特征;其它方法直接使用原始特征向量。

    对于 GCMC 的超参数,我们将原始训练集按照 80:20 进行训练集/验证集的拆分,然后通过验证集来调优超参数:在图卷积中使用 stack 作为累积函数,选择 ,使用左归一化。一旦选择好超参数之后,我们就在整个原始训练集上重新训练模型,并利用训练好的模型来评估测试集。

    对于 GC-MC 模型,我们不带任何辅助信息;对于 GC-MC + Feat 我们使用辅助信息,并且辅助信息的 side information layer 使用维度大小为 10dense 层(采用 ReLU 激活函数)。

    我们使用 1000full-batch epoch 来训练 GC-MCGC-MC + Feat 。我们随机重复执行 5 次并报告测试集上的平均 RMSE 结果。整体评估结果如下(baseline 数据直接来自于 Geometric matrix completion with recurrent multi-graph neural networks)。

    结论:

    • 我们的 GCMC 方法明显优于baseline 方法,即使在没有辅助信息的情况下也是如此。

    • 和我们方法最接近的是 sRGCNN 方法,它在用户和 item 的近邻图上使用图卷积,并使用 RNN 以迭代的方式学习表示。

      实验结果表明,使用简单的解码器(而不是复杂的 RNN)直接从学到的user embedding/ item embedding 中直接评估评分矩阵可以更有效,同时计算效率更高。

  5. MovieLens-1M, MovieLens-10M 数据集(无辅助信息的实验):在该数据集上我们和当前的 SOA 协同过滤算法(如 AutoRec, LLorma, CF-NADE )进行比较。

    我们采取和 A neural autoregressive approach to collaborative filtering 相同的训练集/测试集拆分方式,拆分比例 90:10 。另外,baseline 方法的结果直接使用该论文的数值。

    该数据集不带任何辅助信息,因此我们没有比较 GC-MC + Feat 。我们对原始训练集按照 95:5 随机拆分为训练集/验证集,然后通过验证集来调优超参数:

    • 对于 MovieLens-1M 数据集,我们使用 sum 作为累计函数,选择 ,使用对称归一化。

    • 对于 MovieLens-10M,我们使用 stack 作为累计函数,选择 ,使用对称归一化。

      另外考虑到该数据集的评分等级数量翻倍,我们选择解码器的基参数矩阵数量 用于翻倍(即 )。

    一旦选择好超参数之后,我们就在整个原始训练集上重新训练模型,并利用训练好的模型来评估测试集。

    对于 MovieLens-1M 我们训练 3500full-batch epoch,对于 MovieLens-10M 我们训练 18000mini-batch step(对应于 batch size =10000, epoch = 20 )。

    我们按照 90:10 随机拆分原始训练集/测试集,并重复执行 5 轮,报告模型在测试集上的平均 RMSE。所有 baseline 评分来自于论文 A neural autoregressive approach to collaborative filtering 中的数据。对于 CF-NADE 我们报告了最佳性能的变体。

    结论:

    • GCMC 方法可以扩展到大规模数据集,其性能可以达到 user-based 或者 item-based 协同过滤的 SOA 方法。
    • CF-NADE 引入的几种技术,如:layer-specific 学习率、特殊的ordinal 损失函数、评分的自回归建模,这些都和我们的方法正交,因此这些技术也可以和我们的 GCMC 框架结合使用。

  6. Flixster, Douban, YahooMusic (图形式的辅助信息实验):这些数据集包含了一些图结构的辅助信息。我们通过使用这些图的邻接向量(根据degree 进行归一化)作为相应的 user/item 的特征向量,从而引入辅助信息。

    注意:辅助信息的图是社交网络等 user-user 图,或者 item-item 图。它们不同于 user-item 二部图。

    我们根据论文 Geometric matrix completion with recurrent multi-graph neural networks 的训练集/测试集拆分。所有 baseline 方法的结果都取自于该论文的数值。

    我们从训练集中按照 80:20 随机拆分为训练集/验证集,然后通过验证集来调优超参数:在图卷积中使用 stack 作为累积函数,选择 ,使用左归一化。一旦选择好超参数之后,我们就在整个原始训练集上重新训练模型,并利用训练好的模型来评估测试集。

    对于 GC-MC 模型,我们使用辅助信息,并且辅助信息的 side information layer 使用维度大小为 64dense 层(采用 ReLU 激活函数)。

    我们使用 full-batch 训练 200epoch

    最终我们重复执行 5 轮,并报告模型在测试集上的平均 RMSE。其中 Flixster 有两组结果:左侧结果表示同时引入了 user 辅助信息和 item 辅助信息;右侧结果表示仅考虑 item 辅助信息。

    结论:GC-MC 在所有baseline 中取得了 SOA 效果。

    注意:GC-MC 在所有三个数据集上都采用相同的超参数配置,如果针对各自数据集调优,效果会进一步提升。

  7. 冷启动实验:为深入了解 GCMC 模型如何通过辅助信息来提升冷启动性能,我们选择 MovieLens-100K 数据集,随机选择固定数量的冷启动用户 ,这些用户最多随机保留 个评分(整个实验中随机数种子固定,因此每次随机选择的结果都相同)。注意:MovieLens-=100K 原始数据仅包含具有至少 20 个评分的用户。

    我们考察当 GCMC 的性能( 表示所有用户都保留所有评分)。其中超参数和测试集如前面所述一样选择。结果如下图所示,虚线表示不带辅助信息时模型的表现。

    可以看到:对于冷启动用户,使用辅助信息能够带来显著的提升,在只有一个评分的用户上表现尤为突出。

十五、JK-Net

  1. 目前大多数深度学习方法遵循邻域聚合(也称作消息传递 message passing )方案。这些模型迭代式地聚合每个顶点的 hidden feature 及其周围邻域顶点的 hidden feature,从而作为该顶点的新的 hidden feature。其中每一次迭代都由一层神经网络来表示。理论上讲,执行 次迭代从而得到顶点 hidden feature 的聚合过程中,利用了以顶点 为根节点的一棵高度为 的子树结构。

    已经表明这种方案是 Weisfeiler-Lehman 图同构测试的推广,从而能够同时学习图的拓扑结构以及邻域顶点特征的分布。

    但是,这种聚合方式可能会产生出人意料的结果。例如,已经观察到 GCN 的深度为 2 时达到最佳性能;当采用更深网络时,虽然理论上每个顶点能够访问更大范围的信息,但是GCN 的效果反而更差。

    在计算机视觉领域中,这种现象称作学习退化 degradation ,该问题可以通过残差连接来解决,这极大地帮助了深度模型的训练。但是在 GCN 中,在很多数据集上即使采用了残差连接,多层 GCN 的效果仍然比不过 2GCN

    基于上述观察,论文 《Representation Learning on Graphs with Jumping Knowledge Networks》 研究了邻域聚合方案的特点及其局限性,并提出了jumping knowledge network:JK-Net 框架。该框架和现有的模型不同,JK-Net 为每个顶点灵活地利用不同的邻域范围,从而实现自适应的结构感知表示 structure-aware representation

    通过大量实验我们证明了 JK-Net 达到了 SOA 性能。另外,讲 JK-Net 框架和 GCN/GraphSage/GAT 等模型结合,可以持续改善这些模型的性能。

  2. 为评估不同邻域聚合方案的行为,我们分析了顶点 representation 依赖的邻域范围。我们通过顶点的影响力分布 the influence distribution (即不同顶点对于 representation 的贡献的分布)来刻画这个邻域范围。

    邻域范围隐式的编码了 nearest neighbors 的先验假设。特别是这个邻域范围严重受到图结构的影响。因此引发了一个疑问:是否所有的顶点 都适用于同一个邻域范围?尤其是当图中存在各种各样类型的子图时。

    进一步地,我们形式化的分析将 的影响力分布和从顶点 开始的随机游走扩散联系在一起。这是一个易于理解的现象,因为影响力分布是图结构和特征值 eigenvalue 的函数。

  3. 除了顶点特征之外,子图结构对于邻域聚合结构也有非常大的影响。邻域范围扩张的速度(或者叫影响半径的增长)通过随机游走的 mixing time 来刻画(即:从顶点 的随机游走收敛到平稳分布所需要的时间)。这个时间在不同结构的子图上差异巨大。因此,相同数量的迭代可能导致局部差异很大的影响力分布。

    例如考虑如下 GooglePlus 的社交网络,该图说明了从正方形顶点开始的随机游走的扩散(随机游走的扩散也代表了影响力分布的扩散)。可以看到:不同结构的子图带来不同的邻域范围。

    • a 中,来自核心区域内顶点的随机游走很快就覆盖了几乎整个图(随机游走覆盖的顶点以绿色表示)。
    • b 中,来自tree 形区域顶点的随机游走经过相同的 step 之后,仅覆盖图的一小部分(随机游走覆盖的顶点以绿色表示)。
    • c 中,来自 tree 形区域顶点使用更长的 step 之后达到了核心区域,并且影响力突然快速扩散。

    在图表示模型中,这种随机游走的扩散转换为影响力分布。这表明:在同一个图中,相同数量的随机游走 step 可以导致非常不同的效果。因此我们需要根据具体的图,同时结合较大的邻域范围和较小的邻域范围:太大的邻域范围可能会导致过度平滑,从而丢失局部信息;太小的邻域范围可能信息不足,从而不足以支撑准确的预测。

  4. 上述观察提出一个问题:能否有可能对不同的图和不同的顶点自适应地调整邻域范围。为此我们提出了 JK-Net 框架,该框架在网络最后一层选择性地组合不同邻域范围,从而自适应地学习不同邻域的局部性locality 。如,将不同邻域范围 jump 到最后一层,因此这个网络被称作 Jumping Knowledge Networks:JK-Nets

15.1 模型

  1. 定义图 ,其中 为顶点集合, 为边集合。每个顶点 关联一个顶点特征向量 为特征向量的维度。

    定义图 为图 每个顶点 上添加一个自连接得到的图,其中

    假设基于消息传递的模型有 层,第 层学到的顶点 hidden feature ,其中 hidden feature 的维度。为讨论方便,我们选择所有层的 hidden feature 维度都相等。另外,我们记

    定义顶点 的邻域 为与顶点 直接相连的顶点集合。定义 中顶点 的邻域 ,它包含了顶点 自身。

    则典型的消息传递模型可以描述为:对于第 层,每个顶点 hidden feature 更新方程为:

    其中:

    • AGG 为聚合函数,不同的模型采用不同的聚合函数
    • 为待学习的第 层的权重矩阵,它在所有顶点之间共享
    • 为一个非线性激活函数
  2. GCN 图卷积神经网络(Kipf&Welling,2017hidden feature 更新方程为:

    其中 为顶点 在图 中的 degree

  3. Hamilton et al. (2017) 推导出一个在 inductive learing 中的 GCN 变体,其hidden feature 更新方程为:

    其中 为顶点 中的 degree

  4. 最近的一些模型并没有同时聚合顶点及其邻域,而是先聚合邻域,然后将得到的邻域表示和顶点的上一层表示相结合。其hidden feature 更新方程为:

    其中 函数由具体的模型定义。 在这种范式中,COMBINE 函数是关键,可以将其视为跨层的跳跃连接 skip connection。 对于COMBINE 的选择,GraphSAGE 在特征转换之后直接进行拼接;Column Network 对二者进行插值;Gated GCN 使用 GRU 单元。

    但是,该跳跃连接是 input-specific 的,而不是 output-specific 的。考虑某个顶点 ,假设在第 层计算 时使用了 skip 。则后续更高层 中,对于所有依赖于顶点 的其它顶点 ,计算 都隐式的使用了这个 skip 。我们无法做出这样的选择:对于第 层使用 skip、对于第 层不使用 skip。即跳跃连接是由输入决定,而不是由输出决定。因此跳跃连接无法自适应地调整最终层中的邻域大小。

  5. 最近有些模型没有平等地看到邻域顶点,而是对“重要”的邻居给与更大的权重。可以将这类方法视为 directional bias 的邻域聚合,因为顶点受到某些方向的影响要大于其它方向。

    例如:GATVAIN 通过 attention 机制选择重要的邻居;GraphSAGEmax-pooling 隐式的选择重要的邻居。

    这个研究方向和我们的研究方向正交。因为它调整的是邻域扩张的方向,而我们研究的是调整邻域扩张的范围。我们的方法可以和这些模型相结合,从而增加模型的表达能力。

  6. 在下文中,我们证明了 JK-Net 框架不仅适用于简单的邻域聚合模型(GCN),还适用于跳跃连接 (GraphSAGE)和 directional biasGAT )。

15.1.1 影响力分布

  1. 我们首先利用 Koh & Liang, 2017 中的敏感性分析 sensitivity analysis 以及影响力函数的思想,它们衡量了单个训练样本对于参数的影响。给定顶点 ,我们研究都有哪些其它顶点会影响顶点 representation。从这个影响范围,我们可以了解到顶点 获取有效信息的邻域范围大小。

    给定一个图 ,令 为顶点 的输入特征相连, 为顶点 在网络第 层的 hidden feature 为顶点 的最终representation

    定义雅可比矩阵:

    则定义顶点 对顶点 的影响力得分 influence score 为:雅可比矩阵 的各元素的绝对值之和:

    影响力得分刻画了顶点 对顶点 的敏感性,其物理意义为:顶点 的输入特征的变化对于 的最终 representation 的影响。

    顶点 的影响力分布 influence distribution 定义为所有顶点对于顶点 的影响力得分的归一化分布:

    对于任何顶点 ,影响力分布 捕获了图中所有顶点对它的 representation 的影响。

  2. 考虑在 上从顶点 开始的随机游走。假设在第 步随机游走到顶点 ,则第 步均匀随机地移动到 的任何邻居顶点(包括 自身)。因此,顶点 开始的随机游走的分布为:

    其物理意义为:随机游走第 步到达顶点 的概率。类似的定义适用于具有非均匀转移概率的随机游走。

    随机游走分布的一个重要属性是:如果图是非二部图non-bipartite,则它随着 的增加而扩散 spread ,并收敛到极限分布。收敛速度取决于以顶点 开始的子图结构,并受到随机游走转移概率矩阵的spectral gap (或者 conductance) 的限制bounded

  3. 不同聚合模型和顶点的影响力分布可以深入了解各个 representation 所捕获的信息。以下结果表明:常见的聚合方法的影响力分布和随机游走分布密切相关。这些观察暗示了我们接下来要讨论的优缺点。

    假设 relu 在零点的导数也是零(实际上 relu 函数在零点不可导),则我们得到 GCN 和随机游走之间的关系:

    定理:给定一个 层的 GCN 变体,假设以相同的成功率 激活了模型计算图中的所有路径。则任意顶点 的影响力分布 等价于(在期望上)在 上从顶点 开始的 步的随机游走分布。

    证明:令 经过激活函数之前的值,即:

    则有:

    这里我们简化了 函数的梯度,认为:

    这里 为对角矩阵: