Reasoning Algorithmically in Graph Neural Networks
Danilo Numeroso
The development of artificial intelligence systems with advanced reasoning
capabilities represents a persistent and long-standing research question.
Traditionally, the primary strategy to address this challenge involved the
adoption of symbolic approaches, where knowledge was explicitly represented by
means of symbols and explicitly programmed rules. However, with the advent of
machine learning, there has been a paradigm shift towards systems that can
autonomously learn from data, requiring minimal human guidance. In light of
this shift, in latest years, there has been increasing interest and efforts at
endowing neural networks with the ability to reason, bridging the gap between
data-driven learning and logical reasoning. Within this context, Neural
Algorithmic Reasoning (NAR) stands out as a promising research field, aiming to
integrate the structured and rule-based reasoning of algorithms with the
adaptive learning capabilities of neural networks, typically by tasking neural
models to mimic classical algorithms. In this dissertation, we provide
theoretical and practical contributions to this area of research. We explore
the connections between neural networks and tropical algebra, deriving powerful
architectures that are aligned with algorithm execution. Furthermore, we
discuss and show the ability of such neural reasoners to learn and manipulate
complex algorithmic and combinatorial optimization concepts, such as the
principle of strong duality. Finally, in our empirical efforts, we validate the
real-world utility of NAR networks across different practical scenarios. This
includes tasks as diverse as planning problems, large-scale edge classification
tasks and the learning of polynomial-time approximate algorithms for NP-hard
combinatorial problems. Through this exploration, we aim to showcase the
potential integrating algorithmic reasoning in machine learning models.