Timezone: »
Graph neural networks (GNNs) have emerged as a powerful tool for learning software engineering tasks including code completion, bug finding, and program repair. They benefit from leveraging program structure like control flow graphs, but they are not well-suited to tasks like program execution that require far more sequential reasoning steps than number of GNN propagation steps. Recurrent neural networks (RNNs), on the other hand, are well-suited to long sequential chains of reasoning, but they do not naturally incorporate program structure and generally perform worse on the above tasks. Our aim is to achieve the best of both worlds, and we do so by introducing a novel GNN architecture, the Instruction Pointer Attention Graph Neural Networks (IPA-GNN), which achieves improved systematic generalization on the task of learning to execute programs using control flow graphs. The model arises by considering RNNs operating on program traces with branch decisions as latent variables. The IPA-GNN can be seen either as a continuous relaxation of the RNN model or as a GNN variant more tailored to execution. To test the models, we propose evaluating systematic generalization on learning to execute using control flow graphs, which tests sequential reasoning and use of program structure. More practically, we evaluate these models on the task of learning to execute partial programs, as might arise if using the model as a heuristic function in program synthesis. Results show that the IPA-GNN outperforms a variety of RNN and GNN baselines on both tasks.
Author Information
David Bieber (Google Brain)
Charles Sutton (Google)
Hugo Larochelle (Google Brain)
Danny Tarlow (Google Research, Brain Team)
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 : Type Inference as Optimization »
Eirini V. Pandi · Earl Barr · Andrew Gordon · Charles Sutton -
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: Learning Semantic Representations to Verify Hardware Designs »
Shobha Vasudevan · Wenjie (Joe) Jiang · David Bieber · Rishabh Singh · hamid shojaei · C. Richard Ho · Charles Sutton -
2021 Poster: Learning to Combine Per-Example Solutions for Neural Program Synthesis »
Disha Shrivastava · Hugo Larochelle · Daniel Tarlow -
2021 Poster: A Bayesian-Symbolic Approach to Reasoning and Learning in Intuitive Physics »
Kai Xu · Akash Srivastava · Dan Gutfreund · Felix Sosa · Tomer Ullman · Josh Tenenbaum · Charles Sutton -
2020 : closing talk »
Augustus Odena · Charles Sutton -
2020 : Panel »
Augustus Odena · Charles Sutton · Roopsha Samanta · Xinyun Chen · Elena Glassman -
2020 : Satish Chandra Talk »
Satish Chandra · Augustus Odena · Charles Sutton -
2020 : Spotlight Session 2 »
Augustus Odena · Kensen Shi · David Bieber · Ferran Alet · Charles Sutton · Roshni Iyer -
2020 : Spotlight Session 1 »
Augustus Odena · Maxwell Nye · Disha Shrivastava · Mayank Agarwal · Vincent J Hellendoorn · Charles Sutton -
2020 Workshop: Workshop on Computer Assisted Programming (CAP) »
Augustus Odena · Charles Sutton · Nadia Polikarpova · Josh Tenenbaum · Armando Solar-Lezama · Isil Dillig -
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 Graph Structure With A Finite-State Automaton Layer »
Daniel D. Johnson · Hugo Larochelle · Danny Tarlow -
2020 Spotlight: Learning Graph Structure With A Finite-State Automaton Layer »
Daniel D. Johnson · 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: Learning Discrete Energy-based Models via Auxiliary-variable Local Exploration »
Hanjun Dai · Rishabh Singh · Bo Dai · Charles Sutton · Dale Schuurmans -
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 : Panel on research process »
Zachary Lipton · Charles Sutton · Finale Doshi-Velez · Hanna Wallach · Suchi Saria · Rich Caruana · Thomas Rainforth -
2018 : Charles Sutton »
Charles Sutton -
2018 Poster: HOUDINI: Lifelong Learning as Program Synthesis »
Lazar Valkov · Dipak Chaudhari · Akash Srivastava · Charles Sutton · Swarat Chaudhuri -
2017 Workshop: Workshop on Meta-Learning »
Roberto Calandra · Frank Hutter · Hugo Larochelle · Sergey Levine -
2017 Poster: VEEGAN: Reducing Mode Collapse in GANs using Implicit Variational Learning »
Akash Srivastava · Lazar Valkov · Chris Russell · Michael Gutmann · Charles Sutton -
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 -
2016 Workshop: Towards an Artificial Intelligence for Data Science »
Charles Sutton · James Geddes · Zoubin Ghahramani · Padhraic Smyth · Chris Williams -
2015 Poster: Latent Bayesian melding for integrating individual and population models »
Mingjun Zhong · Nigel Goddard · Charles Sutton -
2015 Spotlight: Latent Bayesian melding for integrating individual and population models »
Mingjun Zhong · Nigel Goddard · Charles Sutton -
2014 Poster: Semi-Separable Hamiltonian Monte Carlo for Inference in Bayesian Hierarchical Models »
Yichuan Zhang · Charles Sutton -
2014 Poster: Signal Aggregate Constraints in Additive Factorial HMMs, with Application to Energy Disaggregation »
Mingjun Zhong · Nigel Goddard · Charles Sutton -
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: Continuous Relaxations for Discrete Hamiltonian Monte Carlo »
Zoubin Ghahramani · Yichuan Zhang · Charles Sutton · Amos Storkey -
2012 Spotlight: Continuous Relaxations for Discrete Hamiltonian Monte Carlo »
Zoubin Ghahramani · Yichuan Zhang · Charles Sutton · Amos Storkey -
2012 Poster: Practical Bayesian Optimization of Machine Learning Algorithms »
Jasper Snoek · Hugo Larochelle · Ryan Adams -
2011 Poster: Quasi-Newton Methods for Markov Chain Monte Carlo »
Yichuan Zhang · Charles Sutton -
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