Reasoning Algorithmically in Graph Neural Networks

Artificial intelligence (AI) research has long focused on developing systems capable of advanced reasoning. Early work centered on symbolic approaches with hand-coded knowledge and rules. The rise of machine learning shifted the focus to systems that learn directly from data. Neural Algorithmic Reasoning (NAR) seeks to blend the strengths of both, allowing neural networks to learn and execute rule-based algorithms. This dissertation explores NAR's theoretical and practical contributions. It examines fundamental concepts, provides an overview of key NAR principles, and investigates the connection between neural networks and tropical algebra. This connection leads to neural architectures provably capable of approximating certain dynamic programming algorithms. The work also demonstrates how these neural reasoners can learn advanced concepts like strong duality in combinatorial optimization. Extensive empirical studies demonstrate the real-world value of NAR networks. These networks are successfully applied to tasks including planning, classifying large-scale graphs, and learning approximate solutions to difficult combinatorial optimization problems. The research highlights the exciting potential of integrating algorithmic reasoning into machine learning models.