深度同态网络可精准建模关系数据库中的复杂查询，提升数据推理能力。
Expressive Power of Deep Homomorphism Networks over Relational Databases
- 基于一阶逻辑框架，揭示深度同态网络与SQL子集的表达等价性
- 在含计数、比例等量化操作时，表达能力超越传统图神经网络
- 适用于需精确逻辑推理的关系数据任务，如数据库查询验证
消息传递图神经网络（GNNs）在关系数据库上的表达能力受限，促使研究者提出更强大的架构。本文倡导深度同态网络（DHNs），因其与SQL中重要片段（如合取查询）的紧密联系，特别适合关系数据库学习。通过将DHNs与一阶逻辑（FO）的各种自然片段和扩展关联，我们证明：使用max、sum、mean聚合的DHNs对应于带一元否定的逻辑片段（UNFO），并可扩展至含计数量词和比例量词的变体；使用sum聚合的DHNs则对应于一阶逻辑中一元量词交替片段及具表达性计数的扩展。借助经典的FO与SQL对应关系，这些结果揭示了DHNs与SQL之间的深层联系。此外，我们进一步研究了两类关键静态分析问题的可判定性：空性问题与蕴含问题。实验表明，所建立的表达能力差异确实在特定预测任务中体现为性能差别。
原文摘要 · Abstract (English)
The expressive limitations of message-passing Graph Neural Networks (GNNs) have motivated a wide range of more powerful graph learning architectures. We advocate Deep Homomorphism Networks (DHNs) as a model particularly well-suited for learning over relational databases, due to their close connection to important fragments of SQL such as conjunctive queries. We study the precise expressive power of DHNs by relating them to various natural fragments and extensions of first-order logic (FO). For DHNs with max, sum, and mean aggregations, we establish connections to the unary negation fragment (UNFO) and to the extensions of UNFO with counting quantifiers and with ratio quantifiers. We further relate sum-aggregation DHNs to the unary quantifier alternation fragment of FO and to an extension of FO with expressive counting. Through the classical correspondence between FO and SQL, these results also illuminate the relation between DHNs and SQL. They also enable us to study the decidability of two fundamental static analysis problems for DHNs, the emptiness problem and the subsumption problem. Finally, we confirm through experiments that the established differences in expressive power are reflected in the performance on suitable prediction tasks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。