TPAMI 2022 | 利用子图同构计数提升图神经网络的表达能力

公众号新闻

2022-10-28 15:10

©作者 | 桑士龙

来源 | MIND Laboratory

论文标题：

Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting

论文地址：

https://arxiv.org/pdf/2006.09252.pdf

论文介绍

尽管图神经网络（GNNs）在很多的应用中都取得了很大的成绩，但是最近研究发现 GNNs 捕捉底层图结构上仍然有缺陷。研究表明标准的 GNNs 表达能力受到 Weisfeiler-Leman（WL）图同构测试的限制，例如无法检测和计数图的子结构，然而在一些任务中的子结构往往与下游任务密切相关。因此，本文提出了图结构网络（GSN），是一种基于子结构编码的拓扑感知的消息传递方案，并分析了 GSN 的表达能力，证明了它比 WL test 的表达能力更强，还证明了它的普适性。

在复杂的网络中，子结构是十分重要的，但是大多数 GNNs 依靠多个消息传递过程来使该节点发现全图的结构。

本文提出了三个问题：

（1）如何超越各向同性，也就是局部对称和聚合函数

（2）如何确保 GNNs 知道图的结构？

（3）如何不牺牲同构性和 GNNs 泛化能力的前提下实现上述的目标？

作者首先通过在聚合函数中引入结构信息来打破局部对称问题：每个邻居（消息）的贡献根据其与节点中心的结构关系进行不同的转换，这些关系是通过计算某些子结构的外观来表示的。这样可以解决问题 1 和问题 2，而子结构对顶点的排列是不变的，所以 GNNs 对同构是不变的，因此可以解决问题 3。

基本概念

令表示图 G，是一张子图，其中 .

2.1 同构和自同构

如果存在邻接保留双向映射（adjacency-preserving bijective mapping），即若，使得，则称图 G 和图 H 同构，记为。对于给定的一个小图 H，子图同构问题相当于找到图 G 中的一个子图使得，而 H 的自同构则是将 H 映射到自身上，所有唯一的自同构集合形成了图的自同构群，它包含了图的所有可能的对称，记为 Aut（H）。

自同构群将顶点划分为的不相交子集，这个子集称为“轨道”。这可以通过对顶点的结构角色进行划分，例如在图 1 中一条路径上的末端点，或者一个环上的所有顶点。

一个节点的轨道，是它可以通过自同构映射到的节点集合

当所有轨道的集合作用于图 H 上时：

称为自同构的商。文中主要关注的是集合中唯一的元素

，其中是商的基数。

文中同样通过对边的自同构定义了边的结构角色，也就是从边到它自身的双向映射，保持了边的邻接性（如果两条边共享一个端点，则它们就是相邻的）。每个顶点自同构 g 通过将每条边 (u,v) 映射到 (g(u), g(v)) 来产生边自同构。文中同样构造了边自同构群，并推导了边集合在边轨道上的划分

。

2.2 Weisfeiler-Leman tests

WL test 是判断两个图是否同构的快速启发式，每个顶点 v 最初被分配一个颜色，并通过聚合邻居信息迭代改进：

其中：

表示一个多重集（允许元素重复的集合），N(v) 表示节点 v 的邻居。WL 算法在颜色停止变化时停止，并输出颜色的直方图。具有不同直方图的两个图不是同构的，但如果直方图相同，这两个图也有可能不同构。

实验过程

图由具有重复结构角色的节点或者边组成，但是 GNNs 中的节点被当做同样的角色进行操作，因此不知道节点的不同结构角色。尽管最初直觉认为 GNNs 可以通过构造更深层的架构来发现这些角色的不同，但实际上 GNNs 并不能达到这个目的，并且无视结构的属性，例如三角形或者更大的循环。因此，文中显式的将结构角色编码为消息传递的一部分。