Lune

NeurIPS2020Top-tier venue

Learning Graph Structure With A Finite-State Automaton Layer

Daniel D. Johnson, Hugo Larochelle, Daniel Tarlow

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. 1 For instance, the AST for print(x + y) contains nodes for print, x, y, x + y, and the call as a whole.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

6 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • RAT-SQL: Relation-Aware Schema Encoding and Linking for Text-to-SQL Parsers cites Global Relational Models of Source Code
  • CodeTrek: Flexible Modeling of Code using an Extensible Relational Representation cites Global Relational Models of Source Code
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers6

  1. SLAPS: Self-Supervision Improves Structure Learning for Graph Neural NetworksBahare Fatemi, Layla El Asri, Seyed Mehran KazemiNeurIPS 2021 · 220 citations
  2. Generating Useful Accident-Prone Driving Scenarios via a Learned Traffic PriorDavis Rempe, Jonah Philion, Leonidas J. Guibas, Sanja Fidler et al.CVPR 2022 · 123 citations
  3. My Body is a Cage: the Role of Morphology in Graph-Based Incompatible ControlVitaly Kurin, Maximilian Igl, Tim Rocktäschel, Wendelin Boehmer et al.ICLR 2021 · 105 citations
  4. Convergent Graph SolversJunyoung Park, Jinhyun Choo, Jinkyoo ParkICLR 2022 · 17 citations
  5. CodeTrek: Flexible Modeling of Code using an Extensible Relational RepresentationPardis Pashakhanloo, Aaditya Naik, Yuepeng Wang, Hanjun Dai et al.ICLR 2022 · 15 citations

Builds on2

  1. Global Relational Models of Source CodeVincent J. Hellendoorn, Charles Sutton, Rishabh Singh, Petros Maniatis et al.ICLR 2020 · 252 citations
  2. RAT-SQL: Relation-Aware Schema Encoding and Linking for Text-to-SQL ParsersBailin Wang, Richard Shin, Xiaodong Liu, Oleksandr Polozov et al.ACL 2020 · 39 citations

Related papers

  1. Learning Differentiable Programs with Admissible Neural HeuristicsAmeesh Shah, Eric Zhan, Jennifer J. Sun, Abhinav Verma et al.NeurIPS 2020 · 56 citations
  2. Graph Differentiable Architecture Search with Structure LearningYijian Qin, Xin Wang, Zeyang Zhang, Wenwu ZhuNeurIPS 2021 · 52 citations
  3. Learning Graph Cellular AutomataDaniele Grattarola, Lorenzo Livi, Cesare AlippiNeurIPS 2021 · 54 citations
  4. Typilus: neural type hintsMiltiadis Allamanis, Earl T. Barr, Soline Ducousso, Zheng GaoPLDI 2020 · 92 citations
  5. Neural Execution of Graph AlgorithmsPetar Velickovic, Rex Ying, Matilde Padovano, Raia Hadsell et al.ICLR 2020 · 192 citations
Dusk over the sea between two cliffs drawn in fine vertical lines