Imagen de Portada

The Polynomial Counting Capabilities of Message Passing Neural Networks

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Sälzer, Marco, Bergsträßer, Pascal, Lin, Anthony W.
Formato:	Preprint
Publicado:	2026
Materias:	Machine Learning Logic in Computer Science
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Transformers are Inherently Succinct
por: Bergsträßer, Pascal, et al.
Publicado: (2025)

The Complexity of Verifying Feedforward Neural Networks in Quantised Settings
por: Alsmann, Eric, et al.
Publicado: (2026)

Verifying Quantized Graph Neural Networks is PSPACE-complete
por: Sälzer, Marco, et al.
Publicado: (2025)

Length Generalization Bounds for Transformers
por: Yang, Andy, et al.
Publicado: (2026)

A Logic for Reasoning About Aggregate-Combine Graph Neural Networks
por: Nunn, Pierre, et al.
Publicado: (2024)

Conditional Logical Message Passing Transformer for Complex Query Answering
por: Zhang, Chongzhi, et al.
Publicado: (2024)

The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logics
por: Sälzer, Marco, et al.
Publicado: (2025)

Transformer Encoder Satisfiability: Complexity and Impact on Formal Reasoning
por: Sälzer, Marco, et al.
Publicado: (2024)

Verifying Quantized GNNs With Readout Is Decidable But Highly Intractable
por: Chernobrovkin, Artem, et al.
Publicado: (2025)

Fast Ramsey Quantifier Elimination in LIRA (with applications to liveness checking)
por: Lichtner, Kilian, et al.
Publicado: (2025)

The Logical Expressiveness of Topological Neural Networks
por: Akbari, Amirreza, et al.
Publicado: (2026)

Proof Minimization in Neural Network Verification
por: Isac, Omri, et al.
Publicado: (2025)

Space Explanations of Neural Network Classification
por: Labbaf, Faezeh, et al.
Publicado: (2025)

Lecture Notes on Verifying Graph Neural Networks
por: Schwarzentruber, François
Publicado: (2025)

Logic Gate Neural Networks are Good for Verification
por: Kresse, Fabian, et al.
Publicado: (2025)

TLINet: Differentiable Neural Network Temporal Logic Inference
por: Li, Danyang, et al.
Publicado: (2024)

Branch and Bound for Piecewise Linear Neural Network Verification
por: Bunel, Rudy, et al.
Publicado: (2019)

Almost Surely Asymptotically Constant Graph Neural Networks
por: Adam-Day, Sam, et al.
Publicado: (2024)

PICID: Proof-Driven Clause Learning in Neural Network Verification
por: Isac, Omri, et al.
Publicado: (2025)

Polynomial Surrogate Training for Differentiable Ternary Logic Gate Networks
por: Damera, Sai Sandeep, et al.
Publicado: (2026)

Primitive Recursion without Composition: Dynamical Characterizations, from Neural Networks to Polynomial ODEs
por: Bournez, Olivier
Publicado: (2026)

On the Stability and Realizability of Recurrent Polynomial Surrogate Ternary Logic Gate Networks
por: Damera, Sai Sandeep, et al.
Publicado: (2026)

Nazrin: Atomic Tactics for Graph Neural Networks for Theorem Proving in Lean 4
por: Aniva, Leni, et al.
Publicado: (2026)

Slice and Explain: Logic-Based Explanations for Neural Networks through Domain Slicing
por: Queiroz, Luiz Fernando Paulino, et al.
Publicado: (2026)

Continuous Modal Logical Neural Networks: Modal Reasoning via Stochastic Accessibility
por: Sulc, Antonin
Publicado: (2026)

Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons
por: Bassan, Shahaf, et al.
Publicado: (2025)

Bound Propagation meets Constraint Simplification: Improving Logic-based XAI for Neural Networks
por: Gomes, Ronaldo, et al.
Publicado: (2026)

The Descriptive Complexity of Graph Neural Networks
por: Grohe, Martin
Publicado: (2023)

A Hybrid Real-Time Framework for Efficient Fussell-Vesely Importance Evaluation Using Virtual Fault Trees and Graph Neural Networks
por: Xiao, Xingyu, et al.
Publicado: (2024)

Neural Model Checking
por: Giacobbe, Mirco, et al.
Publicado: (2024)

Modal Logical Neural Networks
por: Sulc, Antonin
Publicado: (2025)

Neural Logic Networks for Interpretable Classification
por: Perreault, Vincent, et al.
Publicado: (2025)

Learning Concepts Definable in First-Order Logic with Counting
por: van Bergerem, Steffen
Publicado: (2019)

Learning Representations Through Contrastive Neural Model Checking
por: Krsmanovic, Vladimir, et al.
Publicado: (2025)

Hypergraph Neural Networks Accelerate MUS Enumeration
por: Ijima, Hiroya, et al.
Publicado: (2026)

Set-Based Training for Neural Network Verification
por: Koller, Lukas, et al.
Publicado: (2024)

Regional, Lattice and Logical Representations of Neural Networks
por: Preto, Sandro, et al.
Publicado: (2025)

Efficient Certified Reasoning for Binarized Neural Networks
por: Yang, Jiong, et al.
Publicado: (2025)

How (and when) can you fit examples to logic-based hypothesis classes over infinite structures?
por: Benedikt, Michael, et al.
Publicado: (2026)

Logical GANs: Adversarial Learning through Ehrenfeucht Fraisse Games
por: Mannucci, Mirco A.
Publicado: (2025)