【源头活水】GNN超越一维WL图同构测试？GraphSNN来了

“问渠那得清如许，为有源头活水来”，通过前沿领域知识的学习，从其他研究领域得到启发，对研究问题的本质有更清晰的认识和理解，是自我提高的不竭源泉。为此，我们特别精选论文阅读笔记，开辟“源头活水”专栏，帮助你广泛而深入的阅读科研文献，敬请关注。

来源：知乎—鱼wy

地址：https://zhuanlan.zhihu.com/p/435460527

GraphSNN: 超越WL同构图测试的图神经网络

论文：A New Perspective on "How Graph Neural Networks Go Beyond Weisfeiler-Lehman?"

链接：https://openreview.net/forum?id=uxgg9o7bI_3

01

前言

最近一直想写点论文解读督促一下自己，就先拿这篇开刀(于是我就把组会写的草稿复制过来了)。

这篇论文摘自ICLR2022 open review 四个审稿人不约而同的给了8分，作者信息现在还是匿名状态不知道出自哪个大神之手

02

正文

ICLR 2022 open review 审稿人评分[8,8,8,8]

作者对设计功能强大的图神经网络(GNNs)提出了一个新的视角。简而言之，这使得一个通用的解决方案能够将图的结构属性注入到gnn的消息传递聚合方案中。作为理论基础，作者首先在邻域子图上开发了一个新的局部同构层次结构。然后，作者将消息传递聚合方案推广，从理论上描述gnn如何被设计为在WL测试之外更具表现性。为了阐述这个框架，作者提出了一种新的神经模型，称为GraphSNN，并证明了该模型在区分图结构方面严格比WL检测更具表现性。作者通过实证验证了我们的模型在不同的图形学习任务上的强度。结果表明，作者的模型在不牺牲计算的简单性和效率的情况下，不断改进了基准任务上最先进的方法。

03

同构图检测

定义： 如果图   与图   同构， 那么存在一个从  到  的双射  满足：   当且仅当  

• 双射：单射+满射，也称一一映射

04

WL同构图检测

05

图神经网络

通用框架

GNN使用图的结构和节点特征来学习一个顶点、  或整个图、  的表示向量。现代gnn遵循一种邻域聚合策略，其中通过聚合一个节点的邻居表示来迭代地更新一个节点的表示。经过k次聚合迭代后，一个节点的表示捕获其k-hop网络邻域内的结构信息。形式上，GNN的第k层是

GraphSAGE

GCN

GAT

GIN

06

不同层次的局部同构概念

在本节中，作者描述了基于局部邻域子图的图同构层次结构，并探索其与1-WL的联系。

首先是符号表示：

• 简单无向图：  ，其中  分别是顶点集和边集顶点
• 顶点  邻居顶点的集合：   ，  
• 顶点  邻居集的子图表示：  ，由  归纳出的  的子图，包含  中的两个端点均属于  的边
• 顶点  和  的重叠子图表示：  
• 顶点  的特征：  

**注意：**如果   和   是相邻的子图，  和  不一定是相邻的顶点。

其次作者定义了三个局部图同构的概念，它们对应于邻域子图中不同类别的局部结构：

1.如果存在一个双射   如   使得任意两个顶点  和  在  中是相邻的当且仅当  和  在  是相邻的，且   ，  则称   和   是子图同构的，表示为   

2. 如果存在一个双射   如    使得任意一个顶点   和  满足  则称  和  是重叠同构的，表示为   

3.   

4. 如果存在一个双射   如    使得任意一个顶点  和  满足  则称   和   是子树同构的，表示为  

作者又证明了两个定理：

1.    为真，反之则不然

• 表明邻域子图上的局部同构概念之间存在一个层次，其中子图同构最强，子树同构最弱，重叠同构介于两者之间
  

2. 首先定义了两个概念：

• 邻域集子图的集合:   
• 该集合到节点层级嵌入的映射：  

定理2描述：令M是一个GNN，M和1-WL算法辨别非同构图的能力一样强大，如果M有足够的层数，且满足以下条件：

• 其中每层可以将   映射两个为不同的嵌入向量当且仅当  

07

通用消息传递框架

在本节中，作者提出了一个通用的消息传递框架(GMP)，它能够根据重叠子图将局部结构注入到聚合方案中。在这个框架中，作者从理论上描述了gnn如何被设计成比1-WL更具表现力。

前置定义:

•    中的重叠子图集合：  
• 顶点    中的结构系数   

看到这里可能会产生一个问题：怎么去设计  函数才能使它能够很好的描述顶点和邻居之间的邻域关系。因此，给定   和  ,一个理想的  应该满足以下条件：

1. **局部紧密性(Local closeness): **    代表有i个顶点完全图，如果    则   

2. 局部稠密性(Local denseness): 如果    的顶点数和边数服从于   则  

3. 同构不变性(isomorphic invariant)： 如果  是同构的则  

前置定义:

• 多重集： 允许重复的元素，可以用一个二元组  表示
• 正则化后的结构系数：  
• 特征矩阵和顶点的特征向量：  
• 经过  层后的顶点特征：  

第  的聚合方案可与定义为：

• 从  的邻居及其结构系数中聚合出来的信息

• 在  和  之间执行逐元素乘法后，来自   的“调整”消息，以解释其邻居的结构效应

定理3：令M是一个GNN，其中的聚合函数   由前面所述式子定义，在辨别非同构图时M会比1-WL更具表达性，如果M有足够的层数，且满足以下条件：

• M 至少能辨别一对满足以下三个条件的的邻居子图  

•    是单射的

定理3表明，如果    足够强大，能够区分邻域子树之外的结构，并且邻域聚合函数  在足够多的层数下是单射的，那么GNN可以比1-WL具有更强的表达能力

08

GraphSNN

一般来说，设计    和  函数的方法有很多不同，这导致了具有不同表达能力的gnn。为了详细说明这一点，作者提出了一个新的GNN模型，名为GraphSNN，其聚合方案是是通用消息传递框架的一个实例。作者证明了GraphSNN的表达能力超过了1-WL。

模型设计：根据    的性质（即局部紧密性、局部稠密性和同构不变性），可以如下实例化  来定义GraphSNN的  ，其中  ：

带权邻接矩阵   ，为了使结构系数在不同的节点之间可以很容易地进行比较，需要将该邻接矩阵归一化：   （求和相除，  ） ，第   层的特征向量更新为:

   是一个可学习的标量参数。由于  指的是v的一跳邻域，因此可以堆叠多层来处理多个一跳邻域。注意，为了确保在结构系数存在时特征聚合的单射性，作者在方程的第一项和第二项中执行了+1。这种设计对于保证GraphSNN在1-WL之外的表达性至关重要。

前置定义： 定义三个可数集    (可数集：能与自然数集的某个子集一一对应的集合)，分别表示：

• 节点的特征空间：  
• 结构系数空间：   
•    的组合空间   
•    分别表示包含   元素的多重集，且满足  

引理1. 存在一个函数    且该函数满足    对于任何不同的  多集对都是唯一的.

引理2. 存在一个函数   且该函数满足   对于任何不同的   是唯一的。其中  

定理4. GraphSNN 比1-WL分辨更具有表达力

09

实验

10

与其他模型的联系

GCN

图卷积网络(GCN)(Kipf&Welling，2017)应用归一化平均聚合，将节点v的特征向量与其邻域内的特征向量结合起来

   是边   的归一化系数，源自于归一化的邻接矩阵  

GraphSNN

GraphSAGE

GraphSAGE通过从节点的局部邻域采样和聚合特征来学习聚合函数，以诱导新的节点特征向量。GraphSAGE考虑了三种不同的聚合函数，如平均聚合器、LSTM聚合器和池化聚合器。作者主要关注的是平均聚合器，对于每个顶点  ，取其邻域内节点的特征向量的平均值，并将其与  的特征向量连接起来，如下所示：

GraphSNN

GAT

图注意网络(GAT)对输入的特征向量进行线性变换，并在变换后对邻域顶点的特征向量进行加权和。GAT利用注意机制计算注意权值α(t)vu，并将特征向量聚集如下：

看到这里是不是会自然的想到:

然后GraphSNN化的GAT：

然而这样做估计是效果不好，作者加了个小trick：

GAT表示这很不公平

GIN

GraphSNN

11

小结

作者把4个经典GNN 进行了GraphSNN化，对于GCN, GraphSAGE, GIN 三个软柿子，直接粗暴的带公式就可以得到性能的提升，但是面对GAT时作者使用了一些额外的小tirck性能才超越。GAT在图的预训练、和GraphSAGE上都表现出了一定的水土不服性，至于为什么目前还没有文献报道，值得研究者再去深入挖掘。

本文目的在于学术交流，并不代表本公众号赞同其观点或对其内容真实性负责，版权归原作者所有，如有侵权请告知删除。

“源头活水”历史文章

更多源头活水专栏文章，

请点击文章底部“阅读原文”查看

分享、在看，给个三连击呗！