Learning Graph Structure With A Finite-State Automaton Layer

Daniel D. Johnson, Hugo Larochelle, Daniel Tarlow

Introduction

Graph Neural Networks (GNNs) are highly effective, but their performance heavily depends on the quality of the input graph's edges. In domains like software engineering, researchers often manually add "semantic" edges—such as data flow or control flow—to a program's Abstract Syntax Tree (AST) to help the model reason over long distances. However, hand-coding these edges is labor-intensive and requires deep domain expertise. While some models attempt to learn these edges from scratch (e.g., via self-attention), they often lack the inductive bias to capture the multi-hop, rule-based logic inherent in program structure.

The Graph Finite-State Automaton (GFSA) layer is a novel neural network component designed to bridge this gap. It learns to "rewire" graphs by discovering complex, path-based relationships automatically. By treating a graph as a navigation environment and parameterizing an agent's policy as a differentiable finite-state machine, the model can automatically learn sophisticated program analyses or navigation shortcuts that previously required manual engineering.

Methodology

The authors frame the problem as learning a policy in a rewardless Partially Observable Markov Decision Process (POMDP):

  1. Graph as Environment: Each node in the graph represents a state. An agent can move along existing edges (e.g., "go to parent," "go to left child").
  2. Learnable Automaton: The agent is equipped with a finite-state memory. Its policy—deciding where to move and when to stop—is defined by a learnable Finite-State Automaton (FSA).
  3. Differentiable "Acceptance": Instead of sampling discrete paths (which is noisy and difficult to train), the layer computes the absorbing probabilities of the automaton. It calculates the probability that an agent starting at node $A$ will eventually "accept" a path and stop at node $B$. This results in a weighted adjacency matrix representing a new, learned edge type.
  4. Implicit Differentiation: To make this process efficient, the authors solve the underlying linear system using iterative methods and apply implicit differentiation. This keeps the memory cost constant regardless of how many "steps" the automaton takes, making it feasible for large graphs.

Key Insights and Visualizing Logic

A core insight of this work is that many program analyses are essentially reachability problems under formal language constraints. By using an FSA, the model is equipped with the exact inductive bias needed to learn "regular language" patterns over graphs. Furthermore, unlike Transformers that compute pairwise attention across all nodes, GFSA is constrained to follow valid paths. This constraint prevents the model from "cheating" by looking at unreachable nodes, thereby improving generalization to larger graphs.

Because the GFSA is state-based, its learned logic is highly interpretable. As shown in the figure below, the model learns to backtrack through a while loop, split its attention to check conditions, and handle break statements—all without explicit instructions on Python's control flow.

Visualization of learned behaviors for program analysis and grid-world navigation.

Experimental Setup and Results

The model was evaluated across three distinct tasks:

  • Synthetic Program Analysis: On a custom dataset of Python programs, the goal was to replicate standard static analyses like LastRead (finding the previous time a variable was used). The GFSA layer achieved nearly perfect results (>99% F1 score) and generalized to programs twice as large as those seen during training, whereas standard GNN and Transformer baselines struggled.
  • Variable Misuse Detection: On a real-world task using a subset of the ETH 150k Python dataset, the model had to identify incorrect variable usage and suggest corrections. A model using a GFSA layer achieved 89.63% accuracy, outperforming a baseline model that relied on hand-engineered semantic edges (88.50%).
  • Grid-World Navigation: Using the LabMaze generator, the GFSA successfully discovered "shortcut" edges (diagonal jump edges) to speed up pathfinding, reducing the average steps needed to reach a goal from 40.1 down to 11.5.

Limitations and Future Work

Despite its strong performance, the GFSA layer introduces computational overhead. While memory-efficient, solving a linear system for every graph makes it computationally more expensive than a standard GNN layer. Additionally, FSAs are limited to "regular" languages and cannot handle "context-free" patterns like deeply nested parentheses or recursive function calls. Finally, the layer often produces "soft" continuous weights rather than discrete binary edges; while beneficial for training, this may not perfectly align with the strict logic of traditional compiler theory. Future work may explore applying GFSA to other structured domains, such as molecular graphs or large-scale software repositories.

Summary updated

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.
BibTeX
@inproceedings{johnson2020learning,
  author = {Daniel D. Johnson and Hugo Larochelle and Daniel Tarlow},
  title = {{Learning Graph Structure With A Finite-State Automaton Layer}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=SUc4qL5t6-q},
}
Figure