AAAI 2022 | KerGNNs：基于图核方法的可解释图神经网络

©作者 |  王兆慧

单位 |  中科院计算所

研究方向 |  图分类

KerGNNs 发表于 AAAI 2022，是一个非常有趣的工作。本文尝试梳理其动机和做法。

论文题目：

KerGNNs: Interpretable Graph Neural Networks with Graph Kernels

论文链接：

https://arxiv.org/pdf/2201.00491.pdf

代码链接：

https://github.com/asFeng/kergnns

Motivation：利用图核方法，自然地将CNN框架扩展到graph上

图核（Graph Kernels）方法是图分类任务中应用最广泛的一类传统方法。然而，由于图核方法本质是在手工提取图特征，这类方法性能受限。近年，基于信息传递（MPNN）框架的图神经网络（GNNs）已经在图相关的任务中成为 SOTA 方法了。然而，这类方法在图同构测试中的能力无法超过 WL 算法。

为解决图核方法不够灵活的问题，并提升 GNNs 的表达能力，本文通过结合 graph kernels 和 GNNs 提出了新的 GNN 框架，叫做 Kernel Graph Neural Networks (KerGNNs)。一方面，对于邻居节点的聚合，我们将图核应用在由节点邻居组成的子图上，（1-WL 利用的是邻居节点的 multiset），使得表达能力不受限于 1-WL 算法。另一方面，我们让 graph kernels 的特征构建过程可学习，带来更广泛的适用性。

Preliminary

由于 KerGNN 利用 p-步随机游走图核与 GNN 结合，我们在本小节简单介绍随机游走图核并给出 p-步随机游走图核的计算方法。随机游走图核是一类被广泛研究和使用的图核方法，核心思想是通过数两个输入图中的共同路径的数量，来计算这两个图的相似度。p-步随机游走是指随机游走形成的路径长度不超过 p。 

为了理解具体计算方法，首先引入直积图的概念：

即直积图 中的节点是由 和 中各取一个节点组成的 pair，当且仅当对应节点在原图中均有边存在时，直积图中的节点间有边。举例说明：

图 中有 3 个节点，图 中有 4 个节点，各取 1 个节点组成 pair 作为直积图 中的节点，共有 12 个节点。图 中节点 1 和 2 之间有连边， 图 中 1’ 和 2‘ 之间有连边，因此直积图 中节点 11’ 和 22‘ 之间有连边。随机游走图核的计算中，有个结论是：在直积图 上进行随机游走，等价于同时在图 和图 上随机游走。随机游走图核的计算方法是：

其中， 表示直积图的邻接矩阵， 中第 个元素表示的是 中第 个节点和第 个节点之间长度为 的路径的个数。

为了将随机游走图核泛化到节点具有连续多维属性的场景下，我们定义了直积图节点的属性，表示为 ，其中 ， 分别是图 和图 的属性矩阵。 中第 个元素表示的是 中第 个节点和 中第 个节点之间的相似度。我们把矩阵 铺平为向量 ，并合并到公式（2）中：

基于这个公式，我们可以计算两个输入图之间的 kernel 值。

注：为了和原论文中公式标号保持一致，本文中出现的公式标号不连续。

Method

3.1 KerGNN 框架

KerGNN 是根据以节点为中心的子图而非以节点为根的子树来更新节点表示。本文中的子图，如果不是其他特定情况，是指由中心节点和 1-跳邻居构成的子图。这一小节主要是给出 2 个定义：

首先是节点和图的特征映射。分别表示为 。对于 层的神经网络，在第 层，输入为无向图 ，每个节点有一个特征向量 ，输出也是图 ，此时每个节点的特征向量为 。

受到 CNN 中 filters 的启发，作者定义了 graph 上的 graph filters，用于提取输入 graph 中每个节点周围的局部结构信息。

模型的第 层，有 个 graph filters，使得节点的输出维度也是 。其中第 个 filter 表示为 ，它包括可训练的邻接矩阵 和属性矩阵 ，属性矩阵的维度和输入图节点特征向量 的维度一样。

3.2 KerGNN层

这个小节讲每一层内的计算方式，以第 1 层为例。

输入： 无向图 ，每个节点的特征向量就是节点属性，表示为 ，每个节点为中心形成的子图表示为 ，特征向量包括邻居节点特征向量组成的集合 。

参数： 个 graph filters 。

输出： 每个节点更新后的特征向量 。

计算方法： 以 为中心的子图的特征向量和 graph filters 共同作用，获取节点更新后的特征向量。

具体地，我们分别用第 个 graph filter 将子图 的初始特征向量 映射到更新后特征向量 的第 个维度上，i.e.,

其中，我们用 p-步随机游走核作为 ，计算公式（来自 Preliminary公式（3)）是：

其中 是 和 的直积图的邻接矩阵， ， 表示 Kronecker 积； ， ， 表示将矩阵按照堆叠列的方式铺平为向量。

为了避免计算直积图，我们对公式（3）进行变换【来自论文附录】：

已知：

和：

代入（3）中：

其中， 表示 Hadamard 积（元素对位相乘）。公式（11）的最后一行就是公式（5）的具体计算方法，其中 分别表示 graph filter 的属性矩阵和邻接矩阵， 分别表示子图的属性矩阵和邻接矩阵。

3.3 多层的KerGNN模型

这个小节讲不同层间的堆叠和图表示的获取，以第 层为例。

输入： 图 ，节点特征向量 ；

参数： 个 graph filters ；

输出： 每个节点更新后的特征向量 ；

计算方法： 输出向量的第 维计算方法：

因此，可以得到节点 在 层的特征向量 。其中 的计算方式同 3.2 节。

图表示的获取方法：在每一层内，将所有节点的特征向量加和得到这一层的图表示；然后将所有层的表示拼接得到最终的图表示：

获取的图表示用于图分类任务。

送福利啦！

PaperWeekly独家周边盲盒

限量 200 份，免费包邮送

周边盲盒将随机掉落

众多读者要求返场的爆款贴纸

炼丹师必备超大鼠标垫

让你锦鲤护体的卡套组合

扫码回复「盲盒」 

立即免费参与领取 

👇👇👇

更多阅读

#投 稿 通 道#

 让你的文字被更多人看到 

如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。

总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 

PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学术热点剖析、科研心得或竞赛经验讲解等。我们的目的只有一个，让知识真正流动起来。

📝 稿件基本要求：

• 文章确系个人原创作品，未曾在公开渠道发表，如为其他平台已发表或待发表的文章，请明确标注 

• 稿件建议以 markdown 格式撰写，文中配图以附件形式发送，要求图片清晰，无版权问题

• PaperWeekly 尊重原作者署名权，并将为每篇被采纳的原创首发稿件，提供业内具有竞争力稿酬，具体依据文章阅读量和文章质量阶梯制结算

📬 投稿通道：

• 投稿邮箱：hr@paperweekly.site 

• 来稿请备注即时联系方式（微信），以便我们在稿件选用的第一时间联系作者

• 您也可以直接添加小编微信（pwbot02）快速投稿，备注：姓名-投稿

△长按添加PaperWeekly小编

🔍

现在，在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧

·