News

Przemek Wałęga had three papers publlished in the Proceedings of the AAAI Conference on Artificial Intelligence, 2026 with the papers presented at the conference January 20–27, 2026, in Singapore.

Abstract:

Graph Neural Networks (GNNs) address two key challenges in applying deep learning to graph-structured data: they handle varying size input graphs and ensure invariance under graph isomorphism. While GNNs have demonstrated broad applicability, understanding their expressive power remains an important question. In this paper, we propose GNN architectures that correspond precisely to prominent fragments of first-order logic (FO), including various modal logics as well as more expressive two-variable fragments. To establish these results, we apply methods from finite model theory of first-order and modal logics to the domain of graph representation learning. Our results provide a unifying framework for understanding the logical expressiveness of GNNs within FO.

Reference

B. Cuenca Grau, E. Feng, P. A. Wałęga, The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logic, AAAI, 2026
ojs.aaai.org/index.php/AAAI/article/view/38987

Abstract

In recent years, there has been growing interest in understanding the expressive power of graph neural networks (GNNs) by relating them to logical languages. This research has been initialised by an influential result of Barceló et al. (2020), who showed that the graded modal logic (or a guarded fragment of the logic C2), characterises the logical expressiveness of aggregate-combine GNNs. As a "challenging open problem" they left the question whether C2 characterises the logical expressiveness of aggregate-combine-readout GNNs. This question has remained unresolved despite several attempts. In this paper, we solve the above open problem by proving that aggregate-combine-readout GNNs can express logical classifiers beyond C2. This result holds over both undirected and directed graphs. Beyond its implications for GNNs, our work also leads to purely logical insights on the expressive power of infinitary logics.

Reference

S. P. Hauke, P. A. Wałęga, Aggregate-Combine-Readout GNNs Are More Expressive Than Logic C2, AAAI, 2026
ojs.aaai.org/index.php/AAAI/article/view/39308

Abstract

Definite descriptions are expressions of the form "the unique x satisfying property C," which allow reference to objects through their distinguishing characteristics. They play a crucial role in ontology and query languages, offering an alternative to proper names (IDs), which lack semantic content and serve merely as placeholders. In this paper, we introduce two extensions of the well-known description logic ALC with local and global definite descriptions, denoted ALCiL and ALCiG, respectively. We define appropriate bisimulation notions for these logics, enabling an analysis of their expressiveness. We show that although both logics share the same tight ExpTime complexity bounds for concept and ontology satisfiability, ALCiG is strictly more expressive than ALCiL. Moreover, we present tableau-based decision procedures for satisfiability in both logics, provide their implementation, and report on a series of experiments. The empirical results demonstrate the practical utility of the implementation and reveal interesting correlations between performance and structural properties of the input formulas.

Reference

M. Sochański, P. A. Wałęga, M. Zawidzki, Description Logics with Two Types of Definite Descriptions: Complexity, Expressiveness, and Automated Deduction, AAAI, 2026
ojs.aaai.org/index.php/AAAI/article/view/39014