10 papers
A Unifying Relational Perspective on Expressive Lottery Tickets
Lorenz Kummer, Samir Moustafa, Anatol Ehrlich +4
Graph neural networks (GNNs) are widely used, but how parameter sparsity affects the expressivity of relational (RGNNs) and temporal (TGNNs) variants is poorly understood. The Stro…
Goal-Driven Reasoning in DatalogMTL with Magic Sets
Shaoyu Wang, Kaiyue Zhao, Dongliang Wei +4
DatalogMTL is a powerful rule-based language for temporal reasoning. Due to its high expressive power and flexible modeling capabilities, it is suitable for a wide range of applica…
Structural Preservation and the Logical Expressiveness of Graph Neural Networks
PrzemysÅaw Andrzej WaÅÄga, Bernardo Cuenca Grau
Bridges between graph neural networks (GNNs) and logical formalisms have been established by fixing architectural choices, such as the types of aggregation, combination, and activa…
Parity, Sensitivity, and Transformers
Alexander Kozachinskiy, Tomasz Steifer, PrzemysÅaw WaÅÈ©ga
Understanding what neural architectures can and cannot compute is a central challenge in the theory of AI. One of the fundamental problems in this context is the PARITY task, which…
The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logic
Bernardo Cuenca Grau, Eva Feng, PrzemysÅaw Andrzej WaÅÄga
Graph Neural Networks (GNNs) address two key challenges in applying deep learning to graph-structured data: they handle varying size input graphs and ensure invariance under graph…
Preservation Theorems for Unravelling-Invariant Classes: A Uniform Approach for Modal Logics and Graph Neural Networks
PrzemysÅaw Andrzej WaÅÄga, Bernardo Cuenca Grau
We study preservation theorems for modal logics over finite structures with respect to three fundamental semantic relations: embeddings, injective homomorphisms, and homomorphisms.…