Logic, Learning, and Explanation: Theoretical and Applied Perspectives on Machine Reasoning

This dissertation explores the interface between logic and machine learning, focusing on both theoretical foundations and applications to interpretability. It is structured around three main themes: the logical expressivity of Graph Neural Networks (GNNs), interpretability methods for GNNs, and the use of Large Language Models (LLMs) in legal reasoning. The first part develops a novel Ehrenfeucht-Fraïssé game tailored to counting logic with a bounded number of variables, which characterizes formula size. This provides the first known formula size lower bound in counting logic and extends existing results from three-variable first-order logic to three-variable counting logic. This work informs the theoretical limits of GNN expressivity, since a fragment of counting logic has been shown to characterize the distinguishing power of certain GNN architectures. The second part addresses the challenge of explaining GNN predictions. One paper introduces COMRECGC, a novel method for producing global counterfactual explanations through common recourse: minimal, interpretable sets of graph modifications that reliably flip predictions across a dataset. A second paper in this section presents LOGIC, a framework that combines GNN embeddings with LLMs to generate natural language explanations grounded in both the graph structure and node attributes. The third part applies LLMs to the domain of legal reasoning. Using context augmentation and Chain-of-Thought prompting, this work generates structured legal arguments in landlord-tenant scenarios. The generated arguments are evaluated for factual accuracy, legal relevance, and comprehensiveness, offering insights into how LLMs can support legal professionals and expand access to justice.