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):
- 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").
- 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).
- 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.
- 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.
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
LabMazegenerator, 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