Developing artificial intelligence systems with advanced reasoning capabilities is a long-standing research problem. Traditionally, the main strategy for addressing this challenge involves the use of symbolic methods, where knowledge is explicitly represented through symbols and implemented through explicitly programmed rules. However, with the emergence of machine learning, systems have shifted towards being able to learn autonomously from data with minimal human guidance. In light of this shift, increasing interest and effort have been devoted to endowing neural networks with reasoning capabilities to bridge the gap between data-driven learning and logical reasoning. In this context, Neural Algorithm Reasoning (NAR) has emerged as a promising research area that aims to integrate the structured and rule-based reasoning of algorithms with the adaptive learning capabilities of neural networks, often achieved by allowing neural models to mimic classical algorithms. In this paper, we provide theoretical and practical contributions to this research field. We explore the connection between neural networks and tropical algebra, deriving a powerful architecture aligned with algorithm execution. Furthermore, we discuss and demonstrate the ability of such neural reasoners to learn and manipulate complex algorithms and combinatorial optimization concepts, such as the strong duality principle. Finally, in our empirical efforts, we validate the practical utility of NAR networks in various real-world scenarios. This includes diverse tasks such as planning problems, large-scale edge classification tasks, and learning polynomial-time approximation algorithms for NP-hard combinatorial problems. Through this exploration, we aim to demonstrate the potential of integrating algorithmic reasoning into machine learning models.
This paper aims to explore the potential of neural algorithm reasoners, particularly regarding their ability to learn to execute classical algorithms and the effectiveness of using trained algorithm reasoners as relevant inductive priors for downstream tasks. The main contributions of this paper aim to address these two research questions, particularly in the context of graphs, given that many classical algorithms of interest were developed and designed for structured data (Cormen et al., 2009). Additionally, we seek to provide evidence for the aforementioned problems from both theoretical and empirical perspectives. To address the learnability of classical algorithms, we propose a theoretical framework that maps the connections between graphs, neural networks, and tropical algebra (Landolfi et al., 2023). In this setup, an equivalence will be established between algorithms (particularly dynamic programming algorithms) and neural networks. We will also demonstrate how to derive a powerful neural network architecture suitable for learning algorithms based on this connection. Stepping outside the context of dynamic programming algorithms, we propose to effectively demonstrate how we can draw on concepts from various fields related to algorithms, such as combinatorial optimization, to enhance the degree to which algorithmic reasoning can be encoded into neural networks (Numeroso et al., 2023). This contribution also serves as the first practical example of using algorithms as inductive priors to more accurately solve standard machine learning tasks. Building on this, we propose two additional contributions: an algorithmic reasoner for learning consistent heuristic functions for planning problems (Numeroso et al., 2022); and an extensive study on the effectiveness of transferring algorithmic knowledge to NP-hard combinatorial optimization problems (Georgiev et al., 2023). Furthermore, as an additional goal, this paper also strives to serve as an introductory guide to the world of neural algorithm reasoning, particularly tailored for those unfamiliar with NAR through its third chapter.
Convenient Access
Easy Download, please followSpecial Knowledge public account (click the above blue Special Knowledge to follow)
Reply or send a message “A135” in the backend to obtain the download link for “[Doctoral Thesis] Graph Neural Network Algorithm Reasoning, 135-page pdf” from Special Knowledge
Click “Read the Original” to learn about using Special Knowledge, and view over 100000 AI-themed knowledge materials