A Scalable Approach to Probabilistic Neuro-Symbolic Robustness Verification
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909709689159680 |
|---|---|
| author | Manginas, Vasileios Manginas, Nikolaos Stevinson, Edward Varghese, Sherwin Katzouris, Nikos Paliouras, Georgios Lomuscio, Alessio |
| author_facet | Manginas, Vasileios Manginas, Nikolaos Stevinson, Edward Varghese, Sherwin Katzouris, Nikos Paliouras, Georgios Lomuscio, Alessio |
| contents | Neuro-Symbolic Artificial Intelligence (NeSy AI) has emerged as a promising direction for integrating neural learning with symbolic reasoning. Typically, in the probabilistic variant of such systems, a neural network first extracts a set of symbols from sub-symbolic input, which are then used by a symbolic component to reason in a probabilistic manner towards answering a query. In this work, we address the problem of formally verifying the robustness of such NeSy probabilistic reasoning systems, therefore paving the way for their safe deployment in critical domains. We analyze the complexity of solving this problem exactly, and show that a decision version of the core computation is $\mathrm{NP}^{\mathrm{PP}}$-complete. In the face of this result, we propose the first approach for approximate, relaxation-based verification of probabilistic NeSy systems. We demonstrate experimentally on a standard NeSy benchmark that the proposed method scales exponentially better than solver-based solutions and apply our technique to a real-world autonomous driving domain, where we verify a safety property under large input dimensionalities. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_03274 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Scalable Approach to Probabilistic Neuro-Symbolic Robustness Verification Manginas, Vasileios Manginas, Nikolaos Stevinson, Edward Varghese, Sherwin Katzouris, Nikos Paliouras, Georgios Lomuscio, Alessio Artificial Intelligence Neuro-Symbolic Artificial Intelligence (NeSy AI) has emerged as a promising direction for integrating neural learning with symbolic reasoning. Typically, in the probabilistic variant of such systems, a neural network first extracts a set of symbols from sub-symbolic input, which are then used by a symbolic component to reason in a probabilistic manner towards answering a query. In this work, we address the problem of formally verifying the robustness of such NeSy probabilistic reasoning systems, therefore paving the way for their safe deployment in critical domains. We analyze the complexity of solving this problem exactly, and show that a decision version of the core computation is $\mathrm{NP}^{\mathrm{PP}}$-complete. In the face of this result, we propose the first approach for approximate, relaxation-based verification of probabilistic NeSy systems. We demonstrate experimentally on a standard NeSy benchmark that the proposed method scales exponentially better than solver-based solutions and apply our technique to a real-world autonomous driving domain, where we verify a safety property under large input dimensionalities. |
| title | A Scalable Approach to Probabilistic Neuro-Symbolic Robustness Verification |
| topic | Artificial Intelligence |
| url | https://arxiv.org/abs/2502.03274 |