1 要点

1.1 概述

题目：子结构感知图神经网络 (Substructure aware graph neural networks, SAGNN)

背景：尽管图神经网络 (GNN) 在图学习方面取得了巨大成就，但由于GNN的传播范式与一阶Weisfeiler-Leman图同构测试算法 (1-WL) 的一致性，导致其难以突破1-WL表达能力的上限。

思路：通过子图更容易区分原始图。

方法：提出子结构感知图神经网络 (SAGNN)：

1. 剪切子图 (Cut subgraph)：通过连续且有选择地去除边获得；
2. 随机游走编码范式扩展到子图上跟节点的返回概率，以捕获结构信息并将其作为节点特征，以提高GNN的表达能力；
3. 理论证明所提出的SAGNN相较于1-WL的强结构感知能力。

1.2 一些概念

• 1-WL：一种图同构测试算法，用于判断两个图是否同构。传统GNN的表达能力与1-WL算法相当，也就是说，GNN不能区分1-WL不能区分的图；
• EgoNetwork：一种图的子结构，它由一个中心节点和它的邻居节点，以及它们之间的边组成；
• $k$跳内的节点集：与根节点之间的最短路径长度不超过$k$的所有节点的集合；
• 边介数中心性 (EBC)：通过一条边的最短路径的数量或比例，用于衡量边在图或网络中的重要性；

1.3 代码

https://github.com/BlackHalo-Drake/SAGNN-Substructure-Aware-Graph-Neural-Networks

1.4 引用

@inproceedings{Zeng:2023:1112911137,
author		=	{Ding Yi Zeng and Wan Long Liu and Wen Yu Chen and Li Zhou and Ma Lu Zhang and Hong Qu},
title		=	{Substructure aware graph neural networks},
booktitle	=	{{AAAI}},
pages		=	{11129--11137},
year		=	{2023},
url			=	{https://ojs.aaai.org/index.php/AAAI/article/download/26318/26090}
}

2 基础知识

2.1 符号

令$G=(V,E,\mathbf{X})$表示一个无向连通图，其中$V$是节点的有限集、$E$是边的有限集，以及$\mathbf{X}=[{\text{x}}_1,{\text{x}}_2,\dots ,{\text{x}}_n^{\top }]$是节点特征。

2.2 信息传递神经网络 (MPNN)

MPNN提供了一种通过消息传统机制的统一试图，以抽象GNN。在MPNN中，节点到节点的信息是通过迭代地将相邻节点的信息聚合到中心节点来传播。形式上，给定$G$中的节点$i$，其$t$轮迭代的隐藏表示为${\mathbf{h}}_i^t$、邻居节点为$N(i)$、边${\mathbf{e}}_{ij}$连接了节点$i$和$j$，则标准信息传递范式表示为：
$${\mathbf{c}}_i^t=\sum _{j\in N(i)}{\varphi }^t({\mathbf{h}}_i^t,{\mathbf{h}}_j^t,{\mathbf{e}}_{ij}),\text{\hspace{1em}(1)}$$$${\mathbf{h}}_i^{t+1}={\sigma }^t({\mathbf{c}}_i^t,{\mathbf{h}}_i^t),\text{\hspace{1em}(2)}$$其中${\varphi }^t$和${\sigma }^t$分别表示聚合和更新函数。

3 方法

MPNN在足够深度和宽度的表达能力方面仍然不能超过1-WL，而区分更大的图则需要更强的表达能力。基于子图比原始图更容易区分这一事实，本文讲图同构问题概括为子图同构问题，并依次介绍所提出的SAGNN的三个步骤：a) 子图提取；b) 子图随机游走返回概率编码；以及$\text{c}$) 子图信息注入。具体如图1。

3.1 子图提取

子图提取是模型表达的关键步骤，其被分为基于节点和基于图的策略。

3.1.1 基于节点的策略

该策略定义为基于单个节点的子图提取，即不需要完整图的信息。通常而言，在当前策略中。子图的数量等于原始图中节点的数量，其中EgoNetwork是最常用的策略。

令$N(v)$表示根节点$v$的邻居节点的集合，$N_k(v)$表示$k$跳内节点集。$Ego(v{)}_k$是以节点$v$为根节点的的k跳EgoNetwork，其对应节点是根节点$v$的k跳$N_k(v)$内的邻居。

3.1.2 基于图的策略

该策略需要整张图的信息以获取子图，其子图的数量与原始图中的节点数无直接联系。最简单的策略是随机删除一个边或者一个节点，但这很难提升模型的表示能力，且在高密度强规则图中的性能很差。为了提升GNN的表达能力，本文提出了剪切子图。

定义1 $Cut(v{)}_b$子图定义为$b$个块中包含节点$v$的块，其通过从原始图中去除边获得：首先计算原始图中所有边的边介数中心性 (Edge betweenness centrality, EBC)，并持续去掉图中具有最大EBC的边，直到图被划分为$b$块。

1. $b=1$时$Cut(v{)}_b$等价于原始图。随着$b$的增加，$Cut(v{)}_b$的大小及其包含的信息级别均下降；
2. $b$等于节点数时，$Cut(v{)}_b$等价于节点；
3. $Cut(v{)}_b$是包含节点$v$的连通图。

3.2 随机游走返回概率编码

在子图中计算返回概率，可以有效应对图编码的随机游走的时间开销大或者表达欠缺的问题。具体地，在子图$G_{sub}$中，节点$v$的随机游走返回概率编码定义为：
$${\mathbf{p}}_v^{G_{sub}}={\left[{\mathbf{R}}_{G_{sub}}^1(v,v),{\mathbf{R}}_{G_{sub}}^2(v,v),\dots ,{\mathbf{R}}_{G_{sub}}^S(v,v)\right]}^T,$$其中${\mathbf{R}}_{G_{sub}}^s(v,v)$是$s$步随机游走在子图$G_{sub}$中从节点$v$开始的概率。基于此，分别获得对Ego子图和Cut子图的返回概率${\mathbf{p}}_v^{Ego}$和${\mathbf{p}}_v^{Cut}$。接下来，使用一个线性层将返回概率编码为子图隐藏表示向量${\mathbf{h}}_v^{Ego}$和${\mathbf{h}}_v^{Cut}$。注意，单个节点的Ego编码是所有包含当前节点的Ego子图编码的汇聚。

3.3 子图信息注入的信息传递

为了注入子图信息并捕捉全局结构信息，本文同时拼接了子图隐藏表示向量和对应于原始图$G$的节点$v$的结构隐藏表示${\mathbf{h}}_v^G$。最终获取的子图信息注入特征定义为：
$${\mathbf{h}}_v^{E,0}=[{\mathbf{x}}_v,{\mathbf{h}}_v^{Ego},{\mathbf{h}}_v^G],{\mathbf{h}}_v^{C,0}=[{\mathbf{x}}_v,{\mathbf{h}}_v^{Cut},{\mathbf{h}}_v^G].\text{\hspace{1em}(4)}$$信息传递通道包括Ego通道和Cut通道，分别定义为：
$${\mathbf{c}}_v^{E,t}=\sum _{u\in N(v)}{\varphi }_E^t({\mathbf{h}}_v^{E,t},{\mathbf{h}}_u^{E,t},{\mathbf{e}}_{vu}),\text{\hspace{1em}(5)}$$$${\mathbf{c}}_v^{C,t}=\sum _{u\in N(v)}{\varphi }_C^t({\mathbf{h}}_v^{C,t},{\mathbf{h}}_u^{C,t},{\mathbf{e}}_{vu}),\text{\hspace{1em}(6)}$$$${\mathbf{h}}_v^{E,t+1}={\sigma }_E^t({\mathbf{c}}_v^{E,t},{\mathbf{h}}_v^{E,t}),{\mathbf{h}}_v^{C,t+1}={\sigma }_C^t({\mathbf{c}}_v^{C,t},{\mathbf{h}}_v^{C,t}),\text{\hspace{1em}(7)}$$其中${\varphi }^t$和${\sigma }^t$分别是汇聚和更新函数。最终，全局图表示${\mathbf{h}}_G$通过全局池化获得：
h G = POOL ( { h v E , L , h v C , L ∣ v ∈ V } ) . (8) \tag{8} \mathbf{h}_G=\text{POOL}(\{ \mathbf{h}_v^{E,L},\mathbf{h}_{v}^{C,L}|v\in V \}). hG​=POOL({hvE,L​,hvC,L​∣v∈V}).(8)