A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening

本文介绍了一种新的子图图神经网络(Subgraph Graph Neural Networks, Subgraph GNNs)框架，通过将图表示为一组子图，增强了信息传递图神经网络(message-passing GNNs)的表达能力。尽管Subgraph GNNs在多个任务上表现出色，但其复杂性限制了其在更大图上的应用。以往的方法建议仅处理子图的子集，这些子集是通过随机选择或可学习采样选择的。然而，它们进行了次优的子图选择，或者只能处理非常小的子集大小，不可避免地会导致性能下降。本文提出了一种新的Subgraph GNNs框架来解决这些问题。我们使用图缩减函数将节点聚类成具有诱导连通性的超级节点。缩减图与原始图的乘积揭示了一种隐含结构，其中子图与特定的节点集相关联。通过在这种图乘积上运行广义信息传递，我们的方法有效地实现了一种高效而强大的Subgraph GNN。控制缩减函数可以有意义地选择任意数量的子图，而与以往的方法不同的是，它完全兼容标准训练技术。值得注意的是，我们发现生成的节点特征张量具有新的、未被探索的置换对称性。我们利用这种结构，表征相关的线性等变层，并将它们合并到我们的Subgraph GNN架构的层中。在多个图学习基准测试上的广泛实验表明，我们的方法比以往的方法更加灵活，因为它可以无缝地处理任意数量的子图，同时始终优于基准方法。

本论文旨在解决Subgraph GNNs在处理大型图时复杂度高、子图选择不佳等问题。

通过使用图粗化函数将节点聚类成超级节点，并在其与原始图的乘积中运行广义消息传递，实现了高效而强大的Subgraph GNN。控制粗化函数可实现对任意数量的子图进行有意义的选择，并且与标准训练技术完全兼容。

论文发现生成的节点特征张量具有新的置换对称性，将其用于线性等变层的特征提取。在多个图学习基准测试上进行了广泛的实验，证明了该方法比现有方法更加灵活且能够无缝处理任意数量的子图。

近期的相关研究包括：《Graph Neural Networks with Generated Parameters for Relation Learning》、《Graph Neural Networks with Convolutional ARMA Filters》等。