©作者 | 焦子豪
单位 | 南京邮电大学
来源 | MIND Laboratory
论文标题：
From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness
收录会议：
ICLR 2022
论文链接：
https://arxiv.org/pdf/2110.03753.pdf
代码链接：
https://github.com/LingxiaoShawn/GNNAsKernel
本文介绍
MPNN 作为 GNN 的一种，通过递归地聚合某结点星状图邻居的表示信息，以生成该结点的表示信息。MPNN 的表达能力上界是 1-WL test。本文提出了一种能提升任意 MPNN 模型表达能力的通用框架 GNN-AK (GNN As Kernel)。实现的途径是将 MPNN 模型中的星状图替换为如 k-egonets 的子图结构。即某结点的表示将通过其导出子图而不是与其直接相连的邻居所组成的子图（即星状图）来计算。本文通过理论证明，GNN-AK 表达能力强于 1&2-WL，不弱于 3-WL。
问题描述
与 1-WL 表达能力相当的 GNN 还不够强大，因为无法捕捉某些结构性信息，比如像圆圈和三角形之类的 motif。鉴于 k-WL 的表达能力严格大于 1-WL，目前的许多工作寻求将 k-WL 整合并设计为更强大的 GNN。然而现有的大部分工作为了达到 k-WL 的表达能力，使用了 O(k) 阶张量。这导致这些工作在大规模的图上难以应用并扩展。现有的其他工作也缺乏可泛化性。
本文提出的模型拟提高任意 GNN 的表达能力。思路是将常见的 MPNN 中的star graph 替换为灵活定义的 subgraph，并将 injective aggregator 替换为 GNN。换句话说，本模型利用 GNN 来计算某结点所处的子图，来生成该结点的新表示。将 GNN 作为 base model 计算每个子图而不是整个输入图是本文的一个创新点。1. 提出了 GNN-AK (&GNN-AK+) 框架，通过使用 GNN 对子图编码，提升任意 GNN 的表现力；2. 提供了理论支撑：GNN-AK 的表现能力强于 1&2-WL，不弱于 3-WL；3. 高效的实现方式。设计了能够节约内存和时间开销的子图采样方法；
模型方法
3.1 From stars to subgraphs
其中， 是一开始的 feature，L 是层数， 和 分别是第 l 层的 update 和 aggregation 函数。当 和 以及 POOL 函数都是 injective 时，MPNN 达到最大表达能力，与 1-WL 相当。
值得注意的是，1-WL 有个 bug 之处在于，无法区分两个 unlabeled（所有结点拥有相同的 label）的不同构正则图。这也显示出采用星状图的 MPNN 表达能力有限。因此，本文提出将 泛化到 subgraph 上，比如 egonet 以及 k-hop egonet ，本文称这种方法为 Subgraph-1-WL。
由于 HASH 可能是 non-trivial 的，导致总时间开销大，因此用 1-WL 作为弱化版的 HASH。
注意：HASH 和 1-WL 都是对一个 subgraph 进行操作的。
将 GNN 作为 HASH 便得到了 GNN-AK：
原因是 MPNN 内部的各函数都是 injective 的，所以 MPNN 表达能力 =1-WL。
其中 1-WL 和 2-WL 被认为表达能力相同。
通过 GNN 计算结点 v 的 subgraph 中各节点 i 的 embedding，通过 POOL 函数得出整个子图的表示作为结点 v 的表示，成为 subgraph encoding。
提出了 context encoding，将结点 v 所在的所有根结点不同的子图的 embedding 整合成 multiset，用 POOL 函数计算得到 v 的表示。
对式 (5) 添加基于 distance to centroid 变量的门控函数，变为：
其中 FUSE 是串联或求和函数， 是第 l 层 i 到 j 的距离， 是将门控函数引入式 (3) 得到的。
实验&结果
GNN-AK 表达能力的验证、子图计数问题和图性质回归：
通过 SubgraphDrop 验证模型的泛化性：
结论
本文介绍了 GNN-AK 和 GNN-AK+，通过在输入图的导出子图上部署 GNN 作为 kernel，以做到提升任意 GNN 的表达能力。并提供了理论证明。同时设计了 SubgraphDrop，减少了子图采样的运行时间和内存占用。在数据集上的实验取得了 SOTA 的表现，并具有良好的泛化性。
#投 稿 通 道#
让你的文字被更多人看到
如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。
总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。
PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学术热点剖析、科研心得或竞赛经验讲解等。我们的目的只有一个，让知识真正流动起来。
📝 稿件基本要求：
• 文章确系个人原创作品，未曾在公开渠道发表，如为其他平台已发表或待发表的文章，请明确标注
• 稿件建议以 markdown 格式撰写，文中配图以附件形式发送，要求图片清晰，无版权问题
• PaperWeekly 尊重原作者署名权，并将为每篇被采纳的原创首发稿件，提供业内具有竞争力稿酬，具体依据文章阅读量和文章质量阶梯制结算
📬 投稿通道：
• 投稿邮箱：hr@paperweekly.site
• 来稿请备注即时联系方式（微信），以便我们在稿件选用的第一时间联系作者
• 您也可以直接添加小编微信（pwbot02）快速投稿，备注：姓名-投稿
△长按添加PaperWeekly小编
🔍
现在，在「知乎」也能找到我们了
进入知乎首页搜索「PaperWeekly」
点击「关注」订阅我们的专栏吧