4 papers
Certification from Examples is Hard for Circuits and Transformers under Minimal Overparametrization
Artur Back de Luca, Kimon Fountoulakis
As state-of-the-art neural networks are deployed on reasoning and algorithmic tasks, exactness guarantees become increasingly important. However, high average-case accuracy can sti…
Learning to Execute Graph Algorithms Exactly with Graph Neural Networks
Muhammad Fetrat Qharabagh, Artur Back de Luca, George Giapitzakis +1
Understanding what graph neural networks can learn, especially their ability to learn to execute algorithms, remains a central theoretical challenge. In this work, we prove exact l…
Simulation of Graph Algorithms with Looped Transformers
Artur Back de Luca, Kimon Fountoulakis
The execution of graph algorithms using neural networks has recently attracted significant interest due to promising empirical progress. This motivates further understanding of how…
Local Graph Clustering with Noisy Labels
Artur Back de Luca, Kimon Fountoulakis, Shenghao Yang
The growing interest in machine learning problems over graphs with additional node information such as texts, images, or labels has popularized methods that require the costly oper…