3 citations · 5 across the 6 of their papers we have counts for
8 papers
Satisfiability for Knowing How over Linear Plans is NP-complete
Carlos Areces, Pablo Barceló, Valentin Cassano +3
We study the satisfiability problem for a modal logic expressing knowing-how assertions, which captures an agent's ability to achieve a given goal under the standard semantics base…
How Expressive are Knowledge Graph Foundation Models?
Xingyue Huang, Pablo Barceló, Michael M. Bronstein +4
Knowledge Graph Foundation Models (KGFMs) are at the frontier for deep learning on knowledge graphs (KGs), as they can generalize to completely novel knowledge graphs with differen…
Ehrenfeucht-Haussler Rank and Chain of Thought
Pablo Barceló, Alexander Kozachinskiy, Tomasz Steifer
The notion of \emph{rank} of a Boolean function has been a cornerstone in PAC learning theory, enabling quasipolynomial-time learning algorithms for polynomial-size decision trees.…
Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations
Pablo Barceló, Alexander Kozachinskiy, Miguel Romero Orth +2
Despite the wide use of -Nearest Neighbors as classification models, their explainability properties remain poorly understood from a theoretical perspective. While nearest neigh…
A Neuro-Symbolic Framework for Answering Graph Pattern Queries in Knowledge Graphs
Tamara Cucumides, Daniel Daza, Pablo Barceló +4
The challenge of answering graph queries over incomplete knowledge graphs is gaining significant attention in the machine learning community. Neuro-symbolic models have emerged as…
On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters
Matthias Lanzinger, Pablo Barceló
Seminal research in the field of graph neural networks (GNNs) has revealed a direct correspondence between the expressive capabilities of GNNs and the -dimensional Weisfeiler-Le…
Separating Automatic Relations
Pablo Barceló, Diego Figueira, Rémi Morvan
We study the separability problem for automatic relations (i.e., relations on finite words definable by synchronous automata) in terms of recognizable relations (i.e., finite union…
Three iterations of -WL test distinguish non isometric clouds of -dimensional points
Valentino Delle Rose, Alexander Kozachinskiy, Cristóbal Rojas +2
The Weisfeiler--Lehman (WL) test is a fundamental iterative algorithm for checking isomorphism of graphs. It has also been observed that it underlies the design of several graph ne…