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。
为了理解具体计算方法,首先引入直积图的概念:
基于这个公式,我们可以计算两个输入图之间的 kernel 值。
注:为了和原论文中公式标号保持一致,本文中出现的公式标号不连续。
KerGNN 是根据以节点为中心的子图而非以节点为根的子树来更新节点表示。本文中的子图,如果不是其他特定情况,是指由中心节点和 1-跳邻居构成的子图。这一小节主要是给出 2 个定义:
受到 CNN 中 filters 的启发,作者定义了 graph 上的 graph filters,用于提取输入 graph 中每个节点周围的局部结构信息。
这个小节讲每一层内的计算方式,以第 1 层为例。
其中,我们用 p-步随机游走核作为 ,计算公式(来自 Preliminary公式(3))是:
其中 是 和 的直积图的邻接矩阵,, 表示 Kronecker 积;,, 表示将矩阵按照堆叠列的方式铺平为向量。
为了避免计算直积图,我们对公式(3)进行变换【来自论文附录】:
已知:
和:
代入(3)中:
图表示的获取方法:在每一层内,将所有节点的特征向量加和得到这一层的图表示;然后将所有层的表示拼接得到最终的图表示:
获取的图表示用于图分类任务。
送福利啦!
PaperWeekly独家周边盲盒
限量 200 份,免费包邮送
周边盲盒将随机掉落
众多读者要求返场的爆款贴纸
炼丹师必备超大鼠标垫
让你锦鲤护体的卡套组合
扫码回复「盲盒」
立即免费参与领取
👇👇👇
更多阅读
#投 稿 通 道#
让你的文字被更多人看到
如何才能让更多的优质内容以更短路径到达读者群体,缩短读者寻找优质内容的成本呢?答案就是:你不认识的人。
总有一些你不认识的人,知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁,促使不同背景、不同方向的学者和学术灵感相互碰撞,迸发出更多的可能性。
PaperWeekly 鼓励高校实验室或个人,在我们的平台上分享各类优质内容,可以是最新论文解读,也可以是学术热点剖析、科研心得或竞赛经验讲解等。我们的目的只有一个,让知识真正流动起来。
📝 稿件基本要求:
• 文章确系个人原创作品,未曾在公开渠道发表,如为其他平台已发表或待发表的文章,请明确标注
• 稿件建议以 markdown 格式撰写,文中配图以附件形式发送,要求图片清晰,无版权问题
• PaperWeekly 尊重原作者署名权,并将为每篇被采纳的原创首发稿件,提供业内具有竞争力稿酬,具体依据文章阅读量和文章质量阶梯制结算
📬 投稿通道:
• 投稿邮箱:[email protected]
• 来稿请备注即时联系方式(微信),以便我们在稿件选用的第一时间联系作者
• 您也可以直接添加小编微信(pwbot02)快速投稿,备注:姓名-投稿
△长按添加PaperWeekly小编
🔍
现在,在「知乎」也能找到我们了
进入知乎首页搜索「PaperWeekly」
点击「关注」订阅我们的专栏吧
·
关键词
节点
神经网络
方法
向量
邻接矩阵
最新评论
推荐文章
作者最新文章
你可能感兴趣的文章
Copyright Disclaimer: The copyright of contents (including texts, images, videos and audios) posted above belong to the User who shared or the third-party website which the User shared from. If you found your copyright have been infringed, please send a DMCA takedown notice to [email protected]. For more detail of the source, please click on the button "Read Original Post" below. For other communications, please send to [email protected].
版权声明:以上内容为用户推荐收藏至CareerEngine平台,其内容(含文字、图片、视频、音频等)及知识版权均属用户或用户转发自的第三方网站,如涉嫌侵权,请通知[email protected]进行信息删除。如需查看信息来源,请点击“查看原文”。如需洽谈其它事宜,请联系[email protected]。
版权声明:以上内容为用户推荐收藏至CareerEngine平台,其内容(含文字、图片、视频、音频等)及知识版权均属用户或用户转发自的第三方网站,如涉嫌侵权,请通知[email protected]进行信息删除。如需查看信息来源,请点击“查看原文”。如需洽谈其它事宜,请联系[email protected]。