【源头活水】Subgraph Neural Networks

地址：https://www.zhihu.com/people/tan-cheng-70-42

论文地址：

【1】https://papers.nips.cc/paper/2020/file/5bca8566db79f3788be9efd96c9ed70d-Paper.pdf

快捷下载：本公众号后台回复【paper64】下载本论文

01

Story

这篇文章是来自NeurIPS 2020的《Subgraph Neural Networks》[1]，作者首先提出了一个新的问题：子图分类；然后设计了subgraph neural networks（SubGNN）来有效地获取子图表征。

在图的node-level和graph-level预测的任务上，深度学习方法已经取得了很好的表现了，但是对子图（subgraph）预测的研究很少。graph-level的表征提供了对图的全局视角但损失了一定的局部信息，而node-level的表征更关注局部拓扑结构。subgraph-level的表征需要关注近邻（neighbor）、结构（structure）和位置（position）三个方面的信息，更多的信息带来更多的挑战：

（1）要求对不同大小的子图进行联合预测，这涉及到怎样在忽略节点邻域且包含一些迥然不同的节点时（如下图1左，红框内的两个绿色节点）得到表征；

（2）子图包含丰富的高阶连接模式，包括内部成员节点和外部与补图（原图除了给定子图的部分）的连接，这涉及到怎样把两类连接的信息注入GNN的信息传输；

（3）子图位于原图的某一区域，这涉及到怎样有效学习子图在原图上的位置；

（4）子图之间不可避免地会存在依赖关系，这涉及到怎样在保持特征信息的同时利用依赖关系并实现inductive learning。

图1 子图示意图

02

问题描述

子图表征和属性预测：给定子图集合

，SubGNN定义了信息传播结构

，用于为每个子图

生成

维的子图表征

，然后用这些表征学习子图分类器

，即

。

子图表征学习要求模型对子图特有的一些属性编码。如下图2所示，子图有六个拓扑属性，两列表示子图内部和外部的，三行表示位置、近邻和结构三类。对于位置，border position表示子图与补图之间的距离，internal position表示元素和子图之间的相对距离；对于近邻，border neighborhood表示

中任意节点k步内的节点集合，internal neighborhood表示每个元素自己的border neighborhood；对于结构，border structure表示内部节点与border neighborhood之间的边，internal structure表示子图元素之间的内部连接。

图2 子图的六个拓扑属性

03

Method

如下图所示，SubGNN用启发式的方法，把message从anchor patches传递到子图元素，然后聚合得到的表征到最终的子图embedding。

图3 SubGNN结构

04

Subgraph-Level Message Passing

Anchor patches

是从图

上随机采样的子图，定义message从anchor patch

到子图元素

为：

其中

表示通道（位置、结构和近邻），

是衡量元素

和anchor patch

的相似度函数。这些messages然后会被转换为顺序不变的隐层表征

和子图元素

：

其中

是对通道

可学习的权重矩阵，

是

的简写。表征

的顺序不变性对于层间message传递是必要的，但是它会限制捕捉子图结构和位置的能力。因此这里构造了property-aware的输出表征

。最后SubGNN把信息汇聚到P，N，S三个子通道并concat起来（

）。chaneel-specific表征

首先通过通道聚合函数

聚合成每一层子图元素的表征，然后通过聚合函数

聚合所有层元素的表征得到最后的子图元素表征

。最后每个元素

的元素表征

通过

聚合到最后的子图表征

。

05

Property-Aware Routing

每个通道

有三个要素：

（1）用于生成anchor patches的采样函数

；

（2）anchor patch的编码器

；

（3）用于给anchor patches和子图元素之间的message赋权重的相似函数

。