Yu He

What exactly is Neural Algorithmic Reasoning (NAR)? We propose a working definition and position NAR among neighboring fields such as differentiable programming and neural combinatorial optimization. We discuss where NAR should and should not be applied, and propose a neuralization test to help make this distinction. Furthermore, we lay out a research agenda with theoretical goals and benchmarking standards, and invite the NAR community to help shape where the field goes next.

Structural reasoning—the ability to understand and manipulate relationships—underpins many problem-solving processes. For example, when planning a trip, an LLM needs to reason about connectivity between places, rank priorities, and work out temporal relationships. We propose DSR-Bench, a benchmark for evaluating such abilities through synthetic data structure tasks, providing deterministic verification, automated evaluation, and fine-grained insights into which types of relationships LLMs struggle with.

Neural Algorithmic Reasoning (NAR) teaches neural networks to simulate classical algorithms, applying algorithmic thinking to real-world data. However, prior work has mostly focused on algorithms for polynomial-time-solvable problems, while many real-world problems are NP-hard. We propose PDNAR, a general NAR framework for NP-hard problems based on primal-dual approximation algorithms, demonstrating strong size and OOD generalization.

Message passing in GNNs is known to be limited by long-range dependencies and oversquashing. We propose two rewiring strategies based on shortcut sets and edge connectivity to tackle these challenges, respectively.

Most neural algorithmic reasoning models use a fixed number of steps or a termination network to predict when to stop. Ideally, the model should learn to stop upon reaching a fixed-point equilibrium. We explore this idea using deep equilibrium models and discuss several challenges that arise along the way.

Expander graphs are highly connected sparse graphs with low diameters, making them an ideal template for message passing in GNNs. To tackle oversquashing in higher-order interactions, we introduce higher-order expander graph propagation, a rewiring strategy based on bipartite expanders.

Positional encodings are essential for graph transformers and for disambiguating local neighborhoods in GNNs. We propose a novel set of positional encodings based on sheaf theory. The sheaf Laplacian can be learned from node features, allowing it to encode both structural and semantic information.

We extend XLVIN, which leverages a graph neural network to simulate the value iteration algorithm in deep reinforcement learning, from control tasks with discrete action spaces to continuous action spaces. We introduce several selective expansion policies to efficiently handle the resulting large planning graphs.