4 papers
How (and when) can you fit examples to logic-based hypothesis classes over infinite structures?
Michael Benedikt, Alessio Mansutti
We study fitting problems, sometimes called ``training problems'', where we have a finite sample consisting of inputs and outputs, and we want to know whether there is a function i…
Robustness Verification of Graph Neural Networks Via Lightweight Satisfiability Testing
Chia-Hsuan Lu, Tony Tan, Michael Benedikt
Graph neural networks (GNNs) are the predominant architecture for learning over graphs. As with any machine learning model, an important issue is the detection of attacks, where an…
Analysis of logics with arithmetic
Michael Benedikt, Chia-Hsuan Lu, Tony Tan
We present new results on finite satisfiability of logics with counting and arithmetic. One result is a tight bound on the complexity of satisfiability of logics with so-called loc…
Decidability of Graph Neural Networks via Logical Characterizations
Michael Benedikt, Chia-Hsuan Lu, Tony Tan
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 f…