在这篇论文中，我们探讨了图神经网络（GNNs）与逻辑形式之间的桥梁，特别是通过固定架构选择（如聚合、组合和激活函数的类型）来定义受限的GNN类别。这些选择使得逻辑公式可以被转换为等效的GNN，并且反之亦然。
我们从语义角度出发，明确了在结构属性下保持的GNN分类器的逻辑表达能力，包括嵌入（扩展）、单射同态和同态。针对每种属性，我们展示了一个分级模态逻辑片段，表征GNN类别。
具体而言，嵌入、单射同态和同态的保持分别对应于存在性分级模态逻辑、其存在性-正片段和存在性-正模态逻辑。这些结果独立于特定的架构选择，表征了广泛类别的GNN的表达能力。
此外，我们还证明每个类别都承认具有相同表达能力的GNN架构。技术上，我们的方法利用了一个针对有界高度树的新良序结果，从而得出可解开不变类的有限表示。
博主点评： 本文通过将GNN与逻辑形式结合，揭示了其在结构保持下的表达能力，为图神经网络的研究提供了新的视角。尤其是在逻辑与网络架构之间的相互转换，展示了深度学习与逻辑推理之间的潜在联系。此研究有助于推动GNN在更广泛应用中的发展。