今天给大家介绍香港科技大学的Yilun Jin等人在AAAI 2020发表的一篇文章“GraLSP:Graph Neural Networks with Local Structural Patterns”。作者在文章中提出了一个新的图神经网络模型——GraLSP，针对当前GNN难以识别局部结构模式这一缺点，该模型通过随机匿名游走将局部结构模式纳入节点的邻域特征聚合中，充分利用结构模式使得该模型能够在多个数据集上的各种预测任务中优于其它模型。
1
研究背景
采用图神经网络(GNN)进行图表示学习时，虽然基于节点邻域内特征聚合的神经网络表现很好，但GNN难以识别常见的节点结构模式，而这些结构模式往往在各种网络中发挥重要作用，并且GNN在对节点邻域进行编码时，无法为具有不同结构模式的节点生成独特的编码结果。针对这一问题，作者提出了一个新的GNN框架——GraLSP，该框架首先通过随机的匿名游走和表示结构模式的工具来捕获局部图结构，之后将这些游走序列输入到特征聚合中，在实现邻域聚合时考虑的是如何在局部结构模式的影响下聚合节点特征，通过自适应接收半径、注意力和放大机制来结合结构和节点的特性，而不是使用级联将节点特征和游走序列简单的聚合在一起。
2
模型
GraLSP模型设计如图1所示，首先对某个节点的随机匿名游走进行采样，然后将匿名游走映射为向量，之后通过注意力和放大机制沿着结构感知的邻域对向量进行聚合，最后利用结构和节点邻近度的联合损失优化模型。
图1 GraLSP模型设计
2.1提取结构模式
通过匿名游走提取结构模式，对于每个节点，采样一组长度为的随机游走序列，然后计算它们潜在的匿名游走的经验分布和整个图上的平均经验分布作为真实分布。
2.2 结构模式聚合
在聚合结构以及节点级特征时，将重点放在如何在局部结构模式的影响下聚合节点特征，而不是使用级联将二者简单地聚合在一起。作者指出结构模式对图上信息的聚合有三个主要影响：（1）定义接收路径；（2）确定邻域重要性；（3）选择性收集信息。另外，作者提出了邻域采样的自适应接收半径来解决游走过程中访问过多或过少不同节点的问题，引用注意力模块来模拟邻域节点的重要性，并且引入放大模块来模拟节点特征在邻域中的选择性聚合。
2.3学习模型
如果两个匿名游走都经常出现在同一个邻域内，那么它们描述的是相似的结构信息——相同的邻域，因此需要针对游走邻近度设计一个目标函数。为了保留节点特性，还需要一个目标函数来保留节点邻近度。把以上两个目标函数结合在一起，得到一个多任务目标函数，可以同时保留成对节点之间以及成对游走之间的邻近度。
3
实验
实验中使用的四个数据集的统计数据如表1所示：
表1 数据集统计
为了验证GraLSP的有效性，作者将GraLSP与其它三类基线方法进行比较：（1）skip-gram models: 包括DeepWalk和LINE，它们优化了节点之间的邻近度。（2）Structure models: 包括struct2vec和Graphwave，专注于拓扑相似性。（3）GNNs: 包括GraphSAGE、GCN和GAT。
3.1节点分类
该实验对四个数据集进行节点分类，并且使用整个图来学习表示向量。实验中使用20%的节点作为测试数据集，使用80%的节点作为训练数据集，以宏观和微观的F1-score对分类结果进行评估，此外，每个实验结果都是对10个独立实验的结果平均值。实验结果如表2所示，结果表明从原始GNN到GraLSP的性能增益非常大，这表明GraLSP能够弥补GNN识别局部结构模式的缺陷。
表2 不同数据集节点分类的macro-f1 score和micro-f1 score
3.2可视化真实数据集
该实验在真实数据集上进行可视化以定性地评估GraLSP模型，学习Cora数据集的表示向量之后利用PCA将其降维成二维向量。实验中选择了DeepWalk 、GraphSAGE和struc2vec与GraLSP模型进行比较，实验结果如图2所示， 其中黄色、绿色、蓝色和红色点对应于Cora中的4个标签，结果表明与DeepWalk和GraphSAGE相比，GraLSP能够产生更清晰的边界。
图2 二维空间中各算法的表示向量的可视化
4
总结
在论文中，作者提出了一个GNN框架——GraLSP，该框架可将局部结构模式合并到当前的GNN中。作者先分析当前GNN存在难以识别某些结构模式的缺点，之后指出匿名游走是衡量局部结构模式的有效替代方法，然后用向量表示匿名游走序列，并将它们合并到具有多个模块的邻域聚合中，最后提出一个多任务目标函数，该函数可以通过保留成对节点和游走的邻近度来保留特定结构下的语义。通过充分考虑局部结构模式，GraLSP模型在实验中的表现优于各种基准模型。
