查看原文
其他

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

王兆慧 PaperWeekly 2022-07-04


©作者 | 王兆慧
单位 | 中科院计算所
研究方向 | 图分类
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」

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



·

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存