|
Learning to Count Isomorphisms with Graph Neural Networks论文链接： https:///pdf/2302.03266.pdf代码链接： https://github.com/Starlien95/Count-GNN论文录用： 作者主页： 
子图同构计数是图上的一种重要任务，其目标是在图上寻找重复的子图模式。子图同构计数在许多基于图的任务中都有应用，例如社交网络分析、生物信息学和化学。传统的方法通常基于回溯框架，需要遍历一个巨大的搜索空间，计算代价非常高。一些最近的研究利用图神经网络（GNN）来学习一个低维向量表示，用于估计子图出现的次数。 传统 GNN 采用基于节点的消息传递机制，接收和聚合节点上的消息，当要处理同构计数这样需要将复杂图结构进行配对的任务时，存在表达能力不足的问题。此外，在输入图上，可能的查询图的空间是巨大的，并且输入图的不同局部结构将被触发以匹配不同的查询图。因此，使用一个固定表征的输入图来匹配不同结构的查询图是不现实的。 在本文中，我们提出了一种名为 Count-GNN 的新型 GNN，来解决子图同构计数任务中的上述挑战。在边级别上，考虑到边是编码图结构的原子单元，我们提出了一个基于边的消息传递机制，基于边的邻接关系传递和聚合消息，以保留细粒度的结构信息。在图级别上，我们调节输入图表征，使其自适应于每个查询图，以提高同构计数准确率。最后，我们在多个公开数据集上进行了实验，结果表明 Count-GNN 在子图同构计数任务上优于现有方法。 对于子图同构计数问题，捕获精细的结构信息对于查询图和输入图之间的更精确的结构匹配至关重要。因此，我们利用基于边的消息传播，其中每条边接收并聚合相邻边的消息。 具体地，我们首先初始化边的初始化特征，将起点、边、终点原始特征拼接： 在获得边的初始化特征后，我们设计了一个以边为中心的 GNN 层，其中每条边接收并聚合邻居边上的信息。基于边的消息传播可以通过堆叠多层来实现递归。形式上，在第 l 层中，边上信息的更新方式如下： 
上述消息传播机制被用于学习查询图和输入图的特征表示。
2.2 以查询图为条件的图表示
在边级别之外，Count-GNN 将边上的特征表示读出为图上的特征表示，以促进查询图和输入图之间的结构匹配。 在查询图上，我们采用了经典的图特征读出方法。 
不同的查询图通常具有不同的结构，这意味着输入图的不同子图（部分）将被触发以匹配不同的查询图。因此使用固定的图读出表示方法来表示输入图无法很好地适应每个查询图来进行有效的结构匹配。我们在输入图中的边特征表示上利用 Feature-wise Linear Modulation（FiLM），以查询图为条件来进行图编码，来保留特定于查询图的局部结构。 首先，我们利用 FiLM 来基于查询图改变输入图的边的特征表示： 
然后通过读出函数进一步融合调整后的边的特征表示，生成调整后的输入图表示，针对每个查询图进行定制，以实现输入图和查询图之间更精确的匹配。 我们基于查询图和输入图之间的结构匹配性来估计子图同构数目。 这里 MATCH 可以是任何函数，我们使用的是一个全连接层。 2.4 损失函数 基于同构计数模块，我们设计了整体的训练损失函数。 第二项为 FiLM 上的正则项，第三项为模型参数上的 L2 正则项。具体而言，FiLM 正则项旨在通过以下方式鼓励更少的缩放和平移，从而减少过拟合。
我们在两个合成数据集（SMALL, LARGE）和两个公共数据集（MUTAG, OGB)上进行了同构计数实验。 我们可以得到以下三个结论： - Count-GNN 相对于经典的 VF2 算法实现了 65-324 倍的加速，相对于 Peregrine 实现了 8-26 倍的加速。
- 相比其他基于 GNN 的同构计数模型，Count-GNN 更加高效。
- 在大多数情况下，Count-GNN 的准确性比传统的 GNN 模型提高了至少30％。
3.2 消融实验 为了评估 Count-GNN 中设计的模块的有效性，我们进行了消融实验。Count-GNN\E 是传统的基于节点的消息传播，Count-GNN\M 不考虑查询图直接将输入图读出。
结论 本文提出了新的模型 Count-GNN，用于在带标签的图上近似解决子图同构计数问题。在模型方面，我们设计了两个关键模块，即基于边的消息传播和基于查询图的图表示，以提高查询图和输入图之间的结构匹配性。在理论方面，我们证明基于边的消息传播比基于节点的消息传播信息表达能力更强。在实验方面，我们在几个基准数据集上进行了大量实验，以展示 Count-GNN 的有效性和效率。
|
