当前位置：网站首页>【论文阅读｜深读】GraLSP: Graph Neural Networks with Local Structural Patterns

【论文阅读｜深读】GraLSP: Graph Neural Networks with Local Structural Patterns

2022-07-15 21:34:00 【海轰Pro】

前言

Hello！
非常感谢您阅读海轰的文章，倘若文中有错误的地方，欢迎您指出～

自我介绍 ଘ(੭ˊᵕˋ)੭
昵称：海轰
标签：程序猿｜C++选手｜学生
简介：因C语言结识编程，随后转入计算机专业，获得过国家奖学金，有幸在竞赛中拿过一些国奖、省奖…已保研。
学习经验：扎实基础 + 多做笔记 + 多敲代码 + 多思考 + 学好英语！

唯有努力

知其然知其所以然！

本文仅记录自己感兴趣的内容

简介

原文链接：https://ojs.aaai.org//index.php/AAAI/article/view/5861

会议：AAAI 2020（CCF A类）

代码：https://github.com/KL4805/GRALSP

年度：2020/04/03

Abstract

直到最近，图神经网络(GNN)才被用来进行图表示学习，其中基于节点邻域内特征聚集的图表示学习取得了很大的成功

然而，尽管取得了这样的成就，GNN在确定一些常见的结构模式方面存在缺陷，不幸的是，这些模式在各种网络现象中发挥着重要作用

在本文中，我们提出了GraLSP，这是一个GNN框架，它通过随机匿名遍历将局部结构模式显式地结合到邻域聚集中

具体地说，我们通过随机匿名遍历捕获局部图结构，这是一种表示结构模式的强大而灵活的工具
然后将步态反馈到特征聚合中，在特征聚合中设计各种机制来应对结构特征的影响，包括自适应接受半径、注意力和放大
此外，我们设计的目标可以捕捉结构之间的相似性，并与节点邻近性目标一起进行优化

在充分利用结构模式的情况下，我们的模型能够在多个数据集中的各种预测任务中超越竞争对手

1 Introduction

图因其对关系数据的准确描述而无处不在

图表示学习(Cui et al.2018)，为了缓解图的稀疏性和不规则性，出现了将节点投影到向量空间，同时保持图的性质的方法

向量空间是规则的

因此，图表示学习是一种通用的工具，可以适应图上的大量预测任务

最近，将深度学习扩展到图的成功带来了图神经网络(GNN)(周等人。2018)，并取得了令人印象深刻的表现

许多GNN遵循一种称为邻域聚合的递归方案，其中节点的表示向量是通过聚合和变换其邻域内的特征来计算的

通过这样做，构建了以自下而上的方式计算的计算树

基于邻域聚合的GNNs1以其强大而高效的特性吸引了众多研究工作的关注(Xu et al.2018年；刘等人。2019年)。

除了GNN聚集的节点级特征外，图形中也普遍存在其他尺度的特征，其中频繁出现的不同尺度的结构模式是典型的，表明节点和图形的属性

例如分子网络中的功能(PrˇZulj2007)、信息流模式(Granovetter(1977)、ParanJapan(2017))和社会现象(Kovanen等人)。2013)
这些通常是节点级功能无法提供的全局洞察。

然而，尽管GNN确实对节点的邻域进行编码(Xu等人)。2018)，它们不能确保为具有不同结构模式的节点生成不同的结果

具体地说，局部结构模式之间的区别很小，例如一个或两个链接，这使得GNN很难为结构模式生成独特的嵌入，即使具有非常不同的语义

我们以社交网络中具有强联系特征的三元闭包模式为例(Huang et al.2015年)

我们在图1中显示了两层GNN中的三元闭包的计算树

在这里插入图片描述

可以看出，三元闭包的唯一不同之处在于树的第二层上存在一阶邻居(绿色节点)，其影响随着它们的邻域(红色节点)的扩展而减小

因此，基于邻域聚集，GNN在某些情况下可能无法为拓扑相似但语义截然不同的结构模式生成独特的嵌入

作为图像中CNN的对应物，我们认为GNN能够捕获不同级别和尺度的图形特征，包括节点和局部结构级别

因此，出现了一个问题：我们如何使GNN能够更充分地捕捉和利用多尺度的结构和节点特征？

一种简单的方法是首先测量每个节点的结构属性，然后将它们与它们的节点特征连接起来作为输入

然而，尽管这很容易，但仍有两个挑战有待解决。

Efficiency：测量结构模式的大多数度量都需要枚举和模式匹配，这通常需要非常高的复杂性
- 例如，作为一种广泛采用的度量，计算k-−统计量的时间复杂度为O(|V|dk Graphlet 1)(Shervashze等人)。2009)在图表中
Incorporation of structural properties：挑战还在于将这些资产纳入其中。一方面，结构特征传达了丰富的语义，这些语义揭示了图的属性，而这些属性不能仅通过统计来捕获。另一方面，结构属性可以指示图中节点的角色，从而指导特征的聚集(Liu等人。2019年；Ying等人。2018年)

因此，为了补充GNN以更好地处理这些结构模式，我们提出了具有局部结构模式的图神经网络，简称GraLSP

这是一个将局部结构模式结合到邻居聚集中的GNN框架

具体地说，我们通过随机匿名行走捕获局部结构模式，随机匿名行走是能够以一般方式捕获局部结构的随机行走的变体
然后将走行投影到向量，以保留其基本的结构语义

我们设计了多种复杂技术的邻域聚合方案，以反映结构对特征聚合的影响

此外，我们还提出了基于路径和节点的两两邻近度来联合优化路径和节点向量的目标

广泛的实验表明，由于我们精心融入了结构模式，我们的模型在各种任务中的表现优于竞争对手

综上所述，我们做出了以下贡献

我们分析了邻域聚合方案，得出结论：常见的GNN在识别一些常见的结构模式方面存在缺陷
我们提出随机游动可以用来捕捉结构模式，并对其进行分析
我们提出了一种新的邻域聚合方案，该方案通过自适应的接受半径、注意力和放大来结合结构和节点属性
我们进行了大量的实验，结果表明，我们的模型将结构模式融入到GNN中，获得了令人满意的性能

2 Related Work

Graph Representation Learning (GRL)

将离散图形转换为向量，GRL已成为链接预测等任务的流行工具(Chen等人。2018)、社区检测(Wang等人2017年；Long等人。2019年)等

通常有两种类型的GRL方法，由不同的节点相似性概念定义

一方面，像DeepWalk(2014)和GraphSAGE(2017)这样的方法采用了由紧密联系定义的同质性、相似性的概念
另一方面，诸如struc2vec(2017)和Graphwave(2018)等方法将相似性定义为具有相似的拓扑结构

应该注意的是，虽然我们的方法捕获了结构模式，但像大多数GNN一样，它属于前一种类型，采用了同质性而不是结构相似性的思想

我们将在实验中更多地演示节点相似性的两个概念。

Graph Neural Networks (GNNs)

近年来，GNN(Scarselli(2008)、Bruna(2013)、Niepert(2016)、Kipf(2016))逐渐流行起来

最近的研究人员普遍采用邻域聚合的方法，即合并邻域内的节点特征来表示中心节点(Hamilton(2017))。

确定GNN和图结构之间的联系也很流行

(Xu等人)2018)和(Morris et al.2019)证明了GNN和1-WL同构测试之间的等价性
(Li，han和Wu 2018)展示了GNN和拉普拉斯平滑之间的联系
与前人的工作相比，我们的工作更多地集中在“局部”结构上
徐等人。2018)更多地关注全局图结构，例如图同构

Measuring Structural Patterns

以往关于测量结构模式的工作都关注于特征结构，包括最短路径和小图形(Shervashze(2009)，Borgwardt(2005))等

此外，(Micali和朱2016)表明可以通过在图上匿名随机行走来重建局部邻域，这对我们的模型来说是令人惊讶和鼓舞的

这种匿名行走的概念被(Ivanov和Burnaev 2018)推广，他们提出了在匿名行走上嵌入图的方法

3 Model: GraLSP

在这一节中，我们将介绍我们的模型GraLSP的设计，并在图2中进行简要的概述

在这里插入图片描述

3.1 Preliminaries

我们首先介绍与我们的问题相关的几个背景，包括图表示学习、随机和匿名行走以及图神经网络

Definition 1 (Graph & Graph Representation Learning)

给定一个图 $G = (V ， E)$ ，其中 $V=\{v_1，...v_{|V|}\}$ 是节点集， $E=\{<vi，vj>\}$ 是边集，图表示学习学习映射函数

在这里插入图片描述

$h_i$ 就是节点 $v_i$ 的嵌入

具体地说，GNN将它们的映射函数表征为迭代的

其中节点的表示向量是通过其邻域内的特征的聚集来计算的，这可以用以下等式来概括

在这里插入图片描述

许多流行的GNN，包括GCN和GraphSAGE，都可以用公式来概括

Definition 2 (Random Anonymous Walks) 匿名随机游走

给定 随机游走 $w=(w_1，w_2，...，w_l)$

其中 $w_i，w_{i+1}>∈E$

$w$ 的 匿名随机游走 定义为

在这里插入图片描述

其中 $Dis(w，w_i)$ 表示 $w_i$ 首次出现在 $w$ 中时， $w$ 中不同节点的数量，即

在这里插入图片描述

比如 $w =(w_1，w_2，...，w_l) = (1, 3 , 4, 2, 3, 2)$
$DIS(w, w_1) = |\{1\}| = 1$
$DIS(w, w_2) = |\{1,3\}| = 2$
$DIS(w, w_3) = |\{1,3, 4\}| = 3$
$DIS(w, w_4) = |\{1,3, 4, 2\}| = 4$
$DIS(w, w_5) = |\{1,3\}| = 2$ 因为 $w_5 = 3$ ，而第一次出现 $3$ 是在 $w$ 中的第二个数
…
也就是看 $w_i$ 第一次出现的位置

我们将长度为 $l$ 的匿名行走表示为 $ω^l_1，ω^l_2...$ 根据他们的词典编排顺序

例如

$ω^4 _1=(1，2，1，2)$
$ω^4_2=(1，2，1，3)$
$ω^4_3=(1，2，3，1)$
…

匿名漫游和随机漫游之间的关键区别在于，无论访问的确切节点是什么，匿名漫游都描述了随机漫游的基本“模式”

例如，即使 $w_1$ 和 $w_2$ 访问了不同的节点

$w_1=(v_1，v_2，v_3，v_4，v_2)$
$w_2=(v_2，v_1，v_3，v_4，v_1)$

都对应于相同的匿名行走 $aw(w_1)=aw(w_2)=(1，2，3，4，2)$

3.2 Extracting Structural Patterns

我们首先介绍通过匿名遍历提取结构模式

对于每个节点 $v_i$ ，对长度为 $l$ 的 $γ$ 随机游走序列 $W^{(i)}$ 的集合进行采样

使用别名(Alias)采样，使得采样复杂度为 $O (γV l)$

然后我们计算他们潜在的匿名行走的经验分布为

在这里插入图片描述

另外，我们把整个图 $G$ 上的平均经验分布看作

在这里插入图片描述
作为真实分布 $p(ω^l_j|v_i)$ 和 $p(ω^l_j|G)$ 的估计

Rationale of Anonymous Walks

有一些作品探索了匿名行走的性质。Micali(2016)表明，人们 可以使用匿名行走来重建局部子图

我们在这里给出这个定理。

在这里插入图片描述

这个定理强调了匿名行走以一种高度通用的方式捕获结构的能力，因为它们捕获了完整的r-hop邻域

然而，考虑到在GNN中表示结构模式，这个定理是不现实的

例如，对于数据集Cora和 $r = 2$ ，我们得到 $l = 118$ ，这是不可能处理的

因为匿名行走的数量随着 $l$ 呈指数增长(Ivanov和Burnaev 2018)

相反，我们提出了一个更适合我们的任务的替代方案

在这里插入图片描述
这些推论表明了使用相当长的匿名步行来描述一般局部结构模式的基本原理

具体地说，对于包括Cora，Citeseer和AMiner在内的引文图，等式(2)的值约为10

在这里插入图片描述

由于篇幅限制，我们省略了详细的证明

此外，我们对我们认为有吸引力的匿名散步提供了直观的解释

直观地说，具有 $k$ 个不同结点的匿名行走 $ω$ 可得到一个图 $G_ω=(V_ω，E_ω)$

其中 $V_ω=\{1，2...k\}$
且 $i，j>∈E_ω⇔(j，i)$ 或 $(i ， j) \subseteq ω$

从这个意义上说，单个匿名行走是对底层图形的部分重建，它能够指示某些结构，如三元组

在图3中，我们以一个三元闭包为例展示了行走的直觉

在这里插入图片描述

3.3 Aggregation of Structural Patterns

在本节中，我们将介绍将结构模式合并到节点表示中

Representing Anonymous Walks

将匿名漫游表示为统计数据是不够的，因为漫游代表彼此具有不同相似性的结构模式

例如，我们会直观地认为 $(1 ， 2 ， 3 ， 1 ， 4)$ 与 $(1 ， 2 ， 3 ， 1 ， 2)$ 非常相似

因为它们都指示潜在的三和弦，但不同于 $(1 ， 2 ， 3 ， 4 ， 5)$ ，因为没有指示三和弦

因此，由于我们希望捕获不同漫游序列的属性，因此我们通过嵌入表查找将每个匿名漫游表示为向量（以捕捉不同walks和结构的特性）

在这里插入图片描述

Neighborhood Aggregation

在这一部分中，我们将介绍如何聚合结构和节点级特征

具体地说，我们专注于如何在节点的局部结构模式的影响下聚合节点特征，而不是简单地使用拼接将它们聚合在一起

直观地说，我们认为结构对图上的信息聚合有以下影响：

Defining Receptive Paths : 随机游走可以被视为可接受的路径，显示信息如何在图中流动(Liu等人。2019年)。因此，我们希望根据 $v$ 的随机行走来定义灵活的接受路径，或 $v$ 的“邻居”，而不是固定的1跳邻居
Importance of Neighbors： 一般来说，邻域不会统一施加影响，而是表现出不同的力量。人们已经研究过，包括集团或密集集群在内的结构通常表明强烈的社会影响(Granovetter 1977)，这应该被我们的模型所捕捉
Selective Gathering of Information： 结构模式也可以表征对要收集的信息的选择。例如，生物网络中的酶共享独特的结构，从而能够选择性地催化生物反应(Ogata等人。2000)。

为了解决上述影响，我们设计了如下聚合公式。

在这里插入图片描述
其中