Abstract: Graph-based neural network models are producing strong results in a number of domains, in part because graphs provide flexibility to encode domain knowledge in the form of relational structure (edges) between nodes in the graph. In practice, edges are used both to represent intrinsic structure (e.g., abstract syntax trees of programs) and more abstract relations that aid reasoning for a downstream task (e.g., results of relevant program analyses). In this work, we study the problem of learning to derive abstract relations from the intrinsic graph structure. Motivated by their power in program analyses, we consider relations defined by paths on the base graph accepted by a finite-state automaton. We show how to learn these relations end-to-end by relaxing the problem into learning finite-state automata policies on a graph-based POMDP and then training these policies using implicit differentiation. The result is a differentiable Graph Finite-State Automaton (GFSA) layer that adds a new edge type (expressed as a weighted adjacency matrix) to a base graph. We demonstrate that this layer can find shortcuts in grid-world graphs and reproduce simple static analyses on Python programs. Additionally, we combine the GFSA layer with a larger graph-based model trained end-to-end on the variable misuse program understanding task, and find that using the GFSA layer leads to better performance than using hand-engineered semantic edges or other baseline methods for adding learned edge types.
Introduction
Graph Neural Networks (GNNs) have demonstrated significant success across various domains by leveraging the relational structure of data. However, the effectiveness of these models is often contingent on the quality of the input graph's edges. In complex domains like program understanding, researchers frequently augment basic structures, such as Abstract Syntax Trees (ASTs), with manually engineered "semantic" edges representing control flow or data dependencies. While effective, these hand-coded relations require substantial domain expertise and may not be optimal for every task.
This work introduces the Graph Finite-State Automaton (GFSA) layer, a differentiable module designed to learn these abstract relations directly from intrinsic graph structure in an end-to-end manner. By framing edge discovery as a reachability problem governed by a learnable finite-state automaton, the model can automatically rediscover complex relationships and outperform hand-engineered features.
The GFSA Layer
The GFSA layer treats the graph as a rewardless Partially Observable Markov Decision Process (POMDP).
- Agent and Policy: An agent traverses the graph, making movement decisions based on local node observations and an internal finite-state memory. This behavior is governed by a learnable Finite-State Automaton (FSA) policy that decides whether to move, stop, or backtrack.
- Differentiable Reachability: To enable training via gradient descent, the discrete transitions of the FSA are relaxed into a continuous distribution. The layer computes "absorbing probabilities"—the likelihood of an agent starting at node $A$ and terminating at node $B$—to define a new weighted adjacency matrix.
- Implicit Differentiation: Calculating these probabilities involves solving a large linear system. To maintain memory efficiency and support long-range dependencies, the authors utilize implicit differentiation (via JAX). This approach allows the model to backpropagate through the steady-state solution without storing every intermediate step of the agent's trajectory.
Experimental Results
The GFSA layer was evaluated across three distinct domains: spatial navigation, synthetic program analysis, and real-world variable misuse.
- Grid-World Navigation: Tested on LabMaze environments, the GFSA layer successfully learned "shortcut" edges that significantly reduced the average path length required for navigation from 40.1 to 11.5 steps.
- Synthetic Program Analysis: The model was tasked with rediscovering standard program analysis relations (
NextControlFlow,LastRead,LastWrite) in synthetic Python programs. GFSA achieved near-perfect F1 scores (~99%) and demonstrated superior generalization compared to Transformers and standard GNNs, particularly when trained on limited data. - Variable Misuse Task: Integrated into a state-of-the-art Transformer (RAT) for the ETH 150k Python benchmark, the GFSA layer improved accuracy from 88.22% to 89.63%. Notably, this learned-edge approach outperformed models using hand-engineered semantic edges (88.50%).
Discussion and Conclusion
The GFSA layer provides a strong inductive bias for learning structural rules. Unlike global attention mechanisms that consider all node pairs, GFSA is constrained to follow paths, which mirrors the logic of many formal language and program analysis tasks. This path-based constraint allows the model to learn policies that generalize from small training graphs to much larger test instances.
While the current implementation produces dense adjacency matrices—which may pose scalability challenges for massive graphs—the GFSA layer represents a significant step toward automating the discovery of complex relational structures. Future work may explore sparse implementations and applications in other structured domains such as molecular modeling or massive software repositories.
Summary updated