Decidability of Graph Neural Networks via Logical Characterizations
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929691375435776 |
|---|---|
| author | Benedikt, Michael Lu, Chia-Hsuan Tan, Tony |
| author_facet | Benedikt, Michael Lu, Chia-Hsuan Tan, Tony |
| contents | We present results concerning the expressiveness and decidability of a popular graph learning formalism, graph neural networks (GNNs), exploiting connections with logic. We use a family of recently-discovered decidable logics involving "Presburger quantifiers". We show how to use these logics to measure the expressiveness of classes of GNNs, in some cases getting exact correspondences between the expressiveness of logics and GNNs. We also employ the logics, and the techniques used to analyze them, to obtain decision procedures for verification problems over GNNs. We complement this with undecidability results for static analysis problems involving the logics, as well as for GNN verification problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_18151 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Decidability of Graph Neural Networks via Logical Characterizations Benedikt, Michael Lu, Chia-Hsuan Tan, Tony Logic in Computer Science We present results concerning the expressiveness and decidability of a popular graph learning formalism, graph neural networks (GNNs), exploiting connections with logic. We use a family of recently-discovered decidable logics involving "Presburger quantifiers". We show how to use these logics to measure the expressiveness of classes of GNNs, in some cases getting exact correspondences between the expressiveness of logics and GNNs. We also employ the logics, and the techniques used to analyze them, to obtain decision procedures for verification problems over GNNs. We complement this with undecidability results for static analysis problems involving the logics, as well as for GNN verification problems. |
| title | Decidability of Graph Neural Networks via Logical Characterizations |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2404.18151 |