Learning to Represent Programs with Graphs

By Miltiadis Allamanis, Marc Brockschmidt, Mahmoud Khademi. 2017

919 citations recorded by the source corpus.

Learning tasks on source code (i.e., formal languages) have been considered recently, but most work has tried to transfer natural language methods and does not capitalize on the unique opportunities offered by code's known syntax. For example, long-range dependencies induced by using the same variable or function in distant locations are often not considered. We propose to use graphs to represent both the syntactic and semantic structure of code and use graph-based deep learning methods to learn to reason over program structures. In this work, we present how to construct graphs from source code and how to scale Gated Graph Neural Networks training to such large graphs. We evaluate our method on two tasks: VarNaming, in which a network attempts to predict the name of a variable given its usage, and VarMisuse, in which the network learns to reason about selecting the correct variable that should be used at a given program location. Our comparison to methods that use less structured program representations shows the advantages of modeling known structure, and suggests that our models learn to infer meaningful names and to solve the VarMisuse task in many cases. Additionally, our testing showed that VarMisuse identifies a number of bugs in mature open-source projects.

Subfields: Artificial Intelligence, Computer Networks and Communications, Information Systems, Graph Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Information Systems

In Graph Learning

Citations in the corpus

Show Your Work: Scratchpads for Intermediate Computation with Language Models (2021, neutral): “Neural networks that accurately represent the semantics of programs could enable a variety of downstream tasks, including program synthesis (Devlin et al., 2017), program analysis (Allamanis et al., 2018), and other algorithmic reasoning tasks (Velickovic & Blundell, 2021).”
Program Synthesis with Large Language Models (2021, methodology): “Many learning methods have been proposed for program repair [Allamanis et al., 2018b, Tarlow et al., 2019, Hellendoorn et al., 2019, Dinella et al., 2019, Yasunaga and Liang, 2020, Chen et al., 2019b, Pradel and Sen, 2018].”
Graph-based, Self-Supervised Program Repair from Diagnostic Feedback (2020, methodology): “Compared to AST-based graph representations (Allamanis et al., 2018; Tarlow et al., 2019), our program-feedback graph is more relaxed and robust to errors in source code.”
SPoC: Search-based Pseudocode to Code (2019, methodology): “When a program ˆ y = ( c 1 j [1] , . . . , c Lj [ L ] ) fails to compile, the compiler will report error messages along with the line numbers where the errors occur.”
The adverse effects of code duplication in machine learning models of code (2018, methodology): “tion. Since the authors provided the output of their model, we use it directly to compute the performance, instead of performing our own training. Additionally, we considered the Variable Misuse task [2] which is the task of predicting which type-correct, in-scope variable to use at a given variable”
A Survey of Machine Learning for Big Code and Naturalness (2017, background): “[8], who design a neural network based on the output of data flow analysis.”
CodeXGLUE: A Machine Learning Benchmark Dataset for Code Understanding and Generation (2021, background): “• code-code (clone detection [65, 84, 46, 80, 9, 89, 86], defect detection [91, 55, 51, 42, 78, 79], cloze test [15], code completion [57, 1, 56, 66, 67, 8, 27, 7], code repair [69, 4, 23, 26, 71, 73], and code-to-code translation [48, 37, 10, 41]) • text-code (natural language code search [32, 20, ”
Relational inductive biases, deep learning, and graph networks (2018, background): “, 2018), program representation and verification (Allamanis et al., 2018; Li et al., 2016), modeling cellular automata and Turing machines (Johnson, 2017), and performing inference in graphical models (Yoon et al.”
code2seq: Generating Sequences from Structured Representations of Code (2018, methodology): “Allamanis et al. (2018) represent code with Gated Graph Neural Networks.”
code2vec: learning distributed representations of code (2018, methodology): “Such an approach was performed by Allamanis et al. [2018] who presented a Gated Graph Neural Network, in which program elements are graph nodes and semantic relations such as ComputedFrom and LastWrite are edges in the graph.”
A Comprehensive Survey on Graph Neural Networks (2019, background): “There have been explorations of applying GNNs to a variety of problems such as program veriﬁcation [17], program reasoning [166], social inﬂuence prediction [167], adversarial attacks prevention [168], electrical health records modeling [169], [170], brain networks [171], event detection [172], and…”
GraphCodeBERT: Pre-training Code Representations with Data Flow (2020, background): “kschmidt et al., 2018), code clone detection (Wei & Li, 2017; Zhang et al., 2019; Wang et al., 2020), code summarization (Alon et al., 2018; Hu et al., 2018) and so on (Nguyen & Nguyen, 2015; Allamanis et al., 2018; Hellendoorn et al., 2019). Nguyen & Nguyen (2015) propose an AST-based l”
DeepBugs: a learning approach to name-based bug detection (2018, background): “A recent survey discusses more approaches [Allamanis et al. 2017a].”
LambdaNet: Probabilistic Type Inference using Graph Neural Networks (2020, background): “For all other tokens, unlike Allamanis et al. (2017), which maps them all into one single <Unknown> token, we randomly mapped them into one of the <Unknown-i> tokens, where i ranges from 0 to 50 in our current implementation.”
Neural Program Repair by Jointly Learning to Localize and Repair (2019, methodology): “In recent work, Allamanis et al. (2018) proposed the problem of variable misuse (V AR M ISUSE ): given a program, ﬁnd program locations where variables are used, and predict the correct variables that should be in those locations.”
Learning to Fix Build Errors with Graph2Diff Neural Networks (2019, methodology): “[3] propose learning to repair variable misuse errors, such as the one in Figure 1A, using a graph neural network.”
Devign: Effective Vulnerability Identification by Learning Comprehensive Program Semantics via Graph Neural Networks (2019, methodology): “For instance, [18] proposed to generate logical formulas for program veriﬁcation through gated graph recurrent networks, and [27] aimed at prediction of variable names and variable miss-usage.”
Learning semantic program embeddings with graph interval neural network (2020, methodology): “Note that GINN’s scalability-enhancing approach is fundamentally dierent from the existing techniques (Allamanis et al. 2018), where extra edges are required to link nodes that are far apart in a graph.”
Teaching Temporal Logics to Neural Networks (2020, background): “Other works focused on recurrent neural networks or graph neural networks for code analysis, e.g. [30,14,5,48,1].”