# Learning Graph Structure With A Finite-State Automaton Layer

arXiv: https://arxiv.org/abs/2007.04929 · HTML: https://mlsanity.com/paper/2007.04929/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jul 2020.

## Built on by (most cited first, 10 of 10)

- [Generating Useful Accident-Prone Driving Scenarios via a Learned Traffic Prior](https://mlsanity.com/paper/2112.05077/) (2021)
- [SLAPS: Self-Supervision Improves Structure Learning for Graph Neural Networks](https://mlsanity.com/paper/2102.05034/) (2021)
- [Federated Graph Machine Learning: A Survey of Concepts, Techniques, and Applications](https://mlsanity.com/paper/2207.11812/) (2022)
- [Convergent Graph Solvers](https://mlsanity.com/paper/2106.01680/) (2021)
- [A Library for Representing Python Programs as Graphs for Machine Learning](https://mlsanity.com/paper/2208.07461/) (2022)
- [Learning to Extend Program Graphs to Work-in-Progress Code](https://mlsanity.com/paper/2105.14038/) (2021)
- [Robust Graph Structure Learning via Multiple Statistical Tests](https://mlsanity.com/paper/2210.03956/) (2022)
- [COMEX: A Tool for Generating Customized Source Code Representations](https://mlsanity.com/paper/2307.04693/) (2023)
- [Bridging Graph Position Encodings for Transformers with Weighted Graph-Walking Automata](https://mlsanity.com/paper/2212.06898/) (2022)
- [GraphFSA: A Finite State Automaton Framework for Algorithmic Learning on Graphs](https://mlsanity.com/paper/2408.11042/) (2024)

## Abstract (arXiv)

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.