The descriptive complexity of graph neural networks

DOI10.1109/LICS56636.2023.10175735MaRDI QIDQ6851645zbMATH OpenFDO

Authors Martin Grohe

Publication date 27 February 2026

Full work available at URL https://doi.org/10.1109/LICS56636.2023.10175735

Mathematics Subject Classification ID

Logic in computer science (03B70)

Cited in

(8)

• Descriptive complexity for neural networks via Boolean networks
• Decidability of graph neural networks via logical characterizations
• Descriptive complexity for distributed computing with circuits
• A characterisation theorem for two-way bisimulation-invariant monadic least fixpoint logic over finite structures
• Are targeted messages more effective?
• Descriptive complexity for neural networks via Boolean networks
• Foundations of graph neural networks (a logician's view) (invited paper)
• From monotonic graph neural networks to Datalog and back: expressive power and practical applications

This page was built for publication: The descriptive complexity of graph neural networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6851645)