Timezone: »
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.
Author Information
Daniel D. Johnson (Google Research, Brain Team)
Hugo Larochelle (Google Brain)
Danny Tarlow (Google Research, Brain Team)
Related Events (a corresponding poster, oral, or spotlight)
-
2020 Poster: Learning Graph Structure With A Finite-State Automaton Layer »
Thu. Dec 10th 05:00 -- 07:00 PM Room Poster Session 5 #1708
More from the Same Authors
-
2021 : A Unified Few-Shot Classification Benchmark to Compare Transfer and Meta Learning Approaches »
Vincent Dumoulin · Neil Houlsby · Utku Evci · Xiaohua Zhai · Ross Goroshin · Sylvain Gelly · Hugo Larochelle -
2021 Spotlight: Learning Generalized Gumbel-max Causal Mechanisms »
Guy Lorberbom · Daniel D. Johnson · Chris Maddison · Daniel Tarlow · Tamir Hazan -
2022 : Teaching Algorithmic Reasoning via In-context Learning »
Hattie Zhou · Azade Nova · aaron courville · Hugo Larochelle · Behnam Neyshabur · Hanie Sedghi -
2022 : Teaching Algorithmic Reasoning via In-context Learning »
Hattie Zhou · Azade Nova · aaron courville · Hugo Larochelle · Behnam Neyshabur · Hanie Sedghi -
2021 : Invited Talk - Hugo Larochelle »
Hugo Larochelle -
2021 Poster: Structured Denoising Diffusion Models in Discrete State-Spaces »
Jacob Austin · Daniel D. Johnson · Jonathan Ho · Daniel Tarlow · Rianne van den Berg -
2021 Poster: Learning to Combine Per-Example Solutions for Neural Program Synthesis »
Disha Shrivastava · Hugo Larochelle · Daniel Tarlow -
2021 Poster: Learning Generalized Gumbel-max Causal Mechanisms »
Guy Lorberbom · Daniel D. Johnson · Chris Maddison · Daniel Tarlow · Tamir Hazan -
2020 Poster: Your GAN is Secretly an Energy-based Model and You Should Use Discriminator Driven Latent Sampling »
Tong Che · Ruixiang ZHANG · Jascha Sohl-Dickstein · Hugo Larochelle · Liam Paull · Yuan Cao · Yoshua Bengio -
2020 Poster: Learning to Execute Programs with Instruction Pointer Attention Graph Neural Networks »
David Bieber · Charles Sutton · Hugo Larochelle · Danny Tarlow -
2020 Poster: Gradient Estimation with Stochastic Softmax Tricks »
Max Paulus · Dami Choi · Danny Tarlow · Andreas Krause · Chris Maddison -
2020 Oral: Gradient Estimation with Stochastic Softmax Tricks »
Max Paulus · Dami Choi · Danny Tarlow · Andreas Krause · Chris Maddison -
2020 Poster: Curriculum By Smoothing »
Samarth Sinha · Animesh Garg · Hugo Larochelle -
2020 Spotlight: Curriculum By Smoothing »
Samarth Sinha · Animesh Garg · Hugo Larochelle -
2020 Poster: Direct Policy Gradients: Direct Optimization of Policies in Discrete Action Spaces »
Guy Lorberbom · Chris Maddison · Nicolas Heess · Tamir Hazan · Danny Tarlow -
2020 : Discussion Panel: Hugo Larochelle, Finale Doshi-Velez, Devi Parikh, Marc Deisenroth, Julien Mairal, Katja Hofmann, Phillip Isola, and Michael Bowling »
Hugo Larochelle · Finale Doshi-Velez · Marc Deisenroth · Devi Parikh · Julien Mairal · Katja Hofmann · Phillip Isola · Michael Bowling -
2018 : TBA 3 »
Hugo Larochelle -
2018 Poster: Latent Gaussian Activity Propagation: Using Smoothness and Structure to Separate and Localize Sounds in Large Noisy Environments »
Daniel D. Johnson · Daniel Gorelik · Ross E Mawhorter · Kyle Suver · Weiqing Gu · Steven Xing · Cody Gabriel · Peter Sankhagowit -
2017 Workshop: Workshop on Meta-Learning »
Roberto Calandra · Frank Hutter · Hugo Larochelle · Sergey Levine -
2017 Poster: Modulating early visual processing by language »
Harm de Vries · Florian Strub · Jeremie Mary · Hugo Larochelle · Olivier Pietquin · Aaron Courville -
2017 Spotlight: Modulating early visual processing by language »
Harm de Vries · Florian Strub · Jeremie Mary · Hugo Larochelle · Olivier Pietquin · Aaron Courville -
2017 Poster: A Meta-Learning Perspective on Cold-Start Recommendations for Items »
Manasi Vartak · Arvind Thiagarajan · Conrado Miranda · Jeshua Bratman · Hugo Larochelle -
2014 Session: Oral Session 3 »
Hugo Larochelle -
2014 Poster: An Autoencoder Approach to Learning Bilingual Word Representations »
Sarath Chandar · Stanislas Lauly · Hugo Larochelle · Mitesh Khapra · Balaraman Ravindran · Vikas C Raykar · Amrita Saha -
2013 Workshop: Deep Learning »
Yoshua Bengio · Hugo Larochelle · Russ Salakhutdinov · Tomas Mikolov · Matthew D Zeiler · David Mcallester · Nando de Freitas · Josh Tenenbaum · Jian Zhou · Volodymyr Mnih -
2013 Session: Spotlight Session 10 »
Hugo Larochelle -
2013 Session: Spotlight Session 9 »
Hugo Larochelle -
2013 Session: Spotlight Session 8 »
Hugo Larochelle -
2013 Session: Spotlight Session 7 »
Hugo Larochelle -
2013 Session: Spotlight Session 6 »
Hugo Larochelle -
2013 Session: Spotlight Session 5 »
Hugo Larochelle -
2013 Poster: RNADE: The real-valued neural autoregressive density-estimator »
Benigno Uria · Iain Murray · Hugo Larochelle -
2013 Session: Spotlight Session 4 »
Hugo Larochelle -
2013 Session: Spotlight Session 3 »
Hugo Larochelle -
2013 Session: Spotlight Session 2 »
Hugo Larochelle -
2013 Session: Spotlight Session 1 »
Hugo Larochelle -
2012 Poster: A Neural Autoregressive Topic Model »
Hugo Larochelle · Stanislas Lauly -
2012 Poster: Practical Bayesian Optimization of Machine Learning Algorithms »
Jasper Snoek · Hugo Larochelle · Ryan Adams -
2010 Oral: Learning to combine foveal glimpses with a third-order Boltzmann machine »
Hugo Larochelle · Geoffrey E Hinton -
2010 Poster: Learning to combine foveal glimpses with a third-order Boltzmann machine »
Hugo Larochelle · Geoffrey E Hinton -
2006 Poster: Greedy Layer-Wise Training of Deep Networks »
Yoshua Bengio · Pascal Lamblin · Dan Popovici · Hugo Larochelle -
2006 Talk: Greedy Layer-Wise Training of Deep Networks »
Yoshua Bengio · Pascal Lamblin · Dan Popovici · Hugo Larochelle