Global Relational Models of Source Code
Authors: Vincent J. Hellendoorn
Charles Sutton
Rishabh Singh
Petros Maniatis
David Bieber
Venue:  (2020)
Keywords: Models of Source Code
Graph Neural Networks
Structured Learning

Abstract: Models of code can learn distributed representations of a program's syntax and semantics to predict many non-trivial properties of a program. Recent state-of-the-art models leverage highly structured representations of programs, such as trees, graphs and paths therein (e.g. data-flow relations), which are precise and abundantly available for code. This provides a strong inductive bias towards semantically meaningful relations, yielding more generalizable representations than classical sequence-based models. Unfortunately, these models primarily rely on graph-based message passing to represent relations in code, which makes them de facto local due to the high cost of message-passing steps, quite in contrast to modern, global sequence-based models, such as the Transformer. In this work, we bridge this divide between global and structured models by introducing two new hybrid model families that are both global and incorporate structural bias: Graph Sandwiches, which wrap traditional (gated) graph message-passing layers in sequential message-passing layers; and Graph Relational Embedding Attention Transformers (GREAT for short), which bias traditional Transformers with relational information from graph edge types. By studying a popular, non-trivial program repair task, variable-misuse identification, we explore the relative merits of traditional and hybrid model families for code representation. Starting with a  graph-based model that already improves upon the prior state-of-the-art for this task by 20%, we show that our proposed hybrid models improve an additional 10-15%, while training both faster and using fewer parameters.

Published as a conference paper at ICLR 2020
GLOBAL RELATIONAL MODELS OF SOURCE CODE
Vincent Hellendoorn, Petros Maniatis, Rishabh Singh, Charles Sutton, David Bieber Google Research
(vhellendoorn, maniatis, rising, charlessut ott.://tttooo.bbbbbeeeooooo.....
ABSTRACT
Models of code can learn distributed representations of a program's syntax and semantics to predict many non-trivial properties of program. Recent state-of- the-art models leverage highly structured representations of programs, such as trees, graphs and paths therein (e.g., data-flow relations), which are precise and abundantly available for code. This provides a strong inductive bias towards se- mantically meaningful relations, yielding more generalizable representations than classical sequence- based models. Unfortunately. these models primarily rely on graph-based message passing to represent relations in code, which makes them de facto local due to the high cost of message-passing steps, quite in contrast to modern, global sequence-basee models, such as the Transformer. In this work. we bridge this divide between global and structured models by introducing two new hybrid model families that are both global and incorporate structural bias: Graph Sandwiches, which wrap traditional (gated) graph nessage-passing layers in sequential message-passingg layers; and Graph Relational Embedding Atten- tion Transformers (GREAT for short), which bias traditional Transformers with relational information from graph edge types. By studying a popular, non-trivial program repair task, variable-misuse idenrification, traditional and hybrid model families for code representation. Starting with a graph-based model that already improves upon the prior state-of-the-ar for this task by 20% we show that our proposed hybrid models improve an additional 10-15%, while training both faster and using fewer parameters.
explore the relative merits
INTRODUCTION
Well-trained models of source code can learn complex properties of a program, such as its implicit type structure (Hellendoorn et al. 2018), naming conventions (Allamanis et al.) 2015). and potential bugs and repairs (Vasic et al. 2219). This requires learning to represent a program 's latent, semantic properties based on its source. Initial representations of source code relied on sequential models from natural-language processing, such n-gram language models (Hindle al. [012] Allamanis & Sutton 2013 Hellendoorn & Devanbul (017) and Recurrent Neural Networks (RNNs) (White al. 2015), but these models struggle to capture the complexity of source code.
Source code is rich in structured information, such as program's 's abstract syntax tree, data and control flow. Allamanis al. (2018b) proposed to model some of this structure directly, provid- ing powerful inductive bias towards semantically meaningful relations in the code. Their Gated Graph Neural Network (GGNN) model for embedding programs was shown to learn better, more generalizable representations faster than classical RNN-based sequence models.
However, the debate on effective modeling of code far from settled. Graph neural networks typ- ically rely on synchronous message passing, which makes them inherently local, requiring many iterations of message passing to aggregate information from distant parts of the code. However, state-of-the-art graph neural networks for code often use few eight message-passing iterations (Allamanis et al.] 2018b] Fernandes et al., 2018), primarily for computational reasons: program graphs can be very large, and training time grows linearly with the number of message passes. This is in contrast to, e.g., Transformer models (Vaswani et al. 2017). which allow program-wis wide infor- mation flow at every step, yet lack the powerful inductive bias from knowing the code's structure.

---

Published as a conference paper at ICLR 2020
This leads us to a basic research question: is there a fundamental dichotomy between global, un- structured and local, structured models? Our answer is an emphatic no. Our starting point is the sequence-to-pone pointer model of Vasic et al.] (2019), which is state-of-the-ars for the task of localizing and repairing a particular type of bug. As sequence model, their architecture can (at least poten- tially) propagate information globally, but it lacks access the known semantic structure of code. To this end, we replace the sequence encoder of Vasic et al. (2019) with GGNN, yielding new model. Remarkably, this model alone yields 20% improvement over the state of the art, though at the cost of being significantly larger than the sequence model.
praph-to-matliheate
Motivated by this result, we propose two new families of models that efficiently combine longer- distance information, such as the sequence model can represent, with the semantic structural in- formation available to the GGNN, One family, the Graph Sandwich, alternates between message passing and sequential information flow through chain of nodes within the graph; the other, the Graph Relational Embedding Attention Transformer (GREAT), generalizes the relative position em- beddings in Transformers by (hhaw et al. (2018) to convey structural relations instead. We show that our proposed model families outperform all prior results, as well as our new, already stronger base- line by an additional 10% each, while training both substantially faster and using fewer parameters.
2 RELATED WORK
Distributed Representation of Programs: There has been increasing interest in modeling source code using machine learning (Allamanis et al.) (0188). Hindle et al. (2012) model programs as se- quences of tokens and use an n-gram model for predicting code completions. Raychev et al. (2015) use conditional random fields (CRFs) to predict program properties over a set of pairwise program features obtained from the program's 's dependency graph. Many approaches use neural language models to embed programs sequences of tokens (Bhoopchand et al. 2016 White et al. 2015 Some techniques leverage the ASTs of programs in tree-structured recurrent models (Piech et al. 2015 Parisotto al. 2016 Chen et al., 2018). code2vec (Alon al., 2018) and code2seq (Alon et al. 2019) model programs as a weighted combination of a set of leaf-to-leaf paths in the ab- stract syntax tree. Finally, Allamanis al. (2018b) proposed using GGNNs for embedding program graphs consisting of AST's together with control-flow and data-flow edges, Some recent models of code embed run-time information of programs, e.g, program traces, besides syntactic informa- tion (Wang et al. 2018). In this paper, we explore the space of combining sequence- based and graph-based representationn of programs, as well as introduce a Transformer-bar based model with ad- ditional program-edge information to learn program representations. |eennndde et al. (2018) also combine an RNN and a GNN architecture, achieving slight improvements over a GGNN. However, they only consider a single RNN layer inserted at the start; we include larger and more diverse hybrids, as well as entirely different combinations of structural and sequential features.
Neural Program Repair: Automatically generating fixes to repair program bugs is active field of research with many proposed approaches based on genetic programming, program analysis and formal methods, and machine learning (Monperrus) 2018 Gazzola et al. (2019). In this paper, we fo- cus on a specific class of repair task called VarMisuse as proposed by Allamanis et al. (2018b), who use graph-based embedding of programs predict the most likely variable at each variable-use location and generate a repair prediction whenever the predicted variable is different from the one present, using an enumerative approach. Vasicc et al. (2019) improved this approach by jointly pre- dicting both the bug and repair locations using a two-headed pointer mechanism. Our multi-headed pointer graph, graph-sandwich and GREAT models significantly outperform these approaches.
SEMI-STRUCTURED MODELS OF SOURCE CODE
Models of code have so far either been structured (GNNs) or unstructured (RNNs, Transformers). Considering the grsph-based models' substantially superior performance compared to RNNs despite their locality limitations, we may ask: to what extent could global information help GNNs, and to what extent could structural features help sequence-based models?
2

---

Published as a conference paper at ICLR 2020
3.1 MODELS
We address the questions of combining local and global information with two families of models.
Graph-sandwich Models Let T = (f1, ,'? denote a program's 's token sequence and g = (V. E) denote the corresponding program graph, where V is the set of node vertices and & is the list of edge sets for different edge types. In both graph and sequence based models, the nodes u maintain a state vector (*))) that is initialized with initial node embedding x=)) E ER...
In GGNN layer, messages of type k are sent from each node V to its neighbors computed as m (v) = Linearlayyrr,((h)))) (h(+)). After the message passing step, the set messages at each node
aggregated as mn()) (e)(E, m (w) Finally, the state vector of node e is updated as (e) = G"U ((())) In an RNN layer, the state of node (corresponding to a terminal leaf token I, in T) updated as hie = f(,,, (())))) corresponding to a query, key and value for each token |
Transformer compute 4, + qt. ke: Vt- Each token then computes its attention to all other tokens using eij (qikk T) 1///NP which can be soft-maxed to yield attention probabilities
az = -xp((ty)) exp(ea.).
Our first class of models follows from the observation that T C V; i.e. the source code tokens used by sequence models, like RNNs, are by definition also nodes in the program graph, so GGNNs update their state with every message pass. We can thus envision combined model that uses each of these as building block; for instance, assuming initial node features x(()) E RD, the formula [RNN, G3NN(3), RNN] describes a model in which we first run an RNN on all tokens E T (in lexical ordering), then, using these as initial states for E T while using the default node-type embeddings for all other nodes, run three message passing steps using a GGNN, after which we again gather the nodes corresponding T and update their state with an additional RNN pass.
The resulting family of models alternates GGNN-style message passing operations and layers of sequence- based models. By varying the number and size of sequential layers and blocks of GGNN- style message passing, this variant particularly provides insight into the first question above (how can global information help GNNs?), by showing the transition in performance potential of models that increasingly incorporate sequential features. We refer to this class of models as sandwich models.
Graph Relational Embedding Attention Transformer The above family of models still rely on explicit message passing for their structural bias, thereby only indirectly combining struc- tural and global information to the model. We may wish instead directly encode structural bias into a sequence-based model, which requires relaxation of the 'hard' inductive bias from the GGNN. For Transformer-basee architectures, [Sha et al. (2018) show that relational features can be incorporated directly into the attention function by changing the attention computation to ei (qi + }kj //N where qi and kj correspond to the query and key vectors described above, bij is an added bias term for the specific attention weight between tokens and j, and is the per-head attention dimension. In our case, we compute bij = W e + b.. where W. E RR- be E IR, and e E R-N is an embedding of the edge type connecting nodes i and j. if any. If multiple edge types are present between two nodes, the resulting biases are simply added. We name this model GREAT, for Graph Relational Embedding Attention Transformer.
3.2 ARCHITECTURAN DETAILS
In this section, we present details of different architectures we compare and their hyperparameters.
General: All of our models follow the structure proposed by Vasic et al. (019), stacking an ini- tial token-embedding layer, a 'core' model that computes a distributed representation of the code under inspection (in their case, an LSTM), followed by projection into two pointers for the local- ization and repair tasks (see Section 4. This core model is the part varied in our work. We use
'Transformers introduce several more components, including multi-heades attention, feed-forward blocks in every layer and layer-normalization (Vaswani et al. (017).
Where the / N term is used to scale the attention weights
Note that, although equivalent, Shaw al. 2018) add the relational bias the 'key" computation instead.
3

---

Published as a conference paper at ICLR 2020
SubwordText Encodez from Tensor2Tensor (Vaswani et al. 2018) to generate 10K sub-token vocabulary from training data and embed each token by averaging embeddings of its sub-token(s).
seassag--pssinng neural networks have been proposed for code, mostly differing in how a node's 's state is updated based on 'messages' sent by nodes it is connected to. Most commonly used is the gated graph neural network (GGNN) (Li et al. 2015). which uses a GRU cell (Cho et al., 2014) to update a node's state. Although other options sometimes out- perform this architecture, the improvements are generally minor, so we rely on this model for our baseline. One hyperparameter of the architecture is whether to use different transformations at each message-passing step, or to reuse one set of transformations for multiple message passes. Follow- ing Allamaniis et al. (2018b). we use blocks of two message-passingg layers, in which the first layer repeated three times, for four message passes per block. We then sweep over GGNN architectures that repeat these blocks 1 to 4 times (thus yielding 4 to 16 message passes). By default, the message dimension is set to 128, but we include an ablation with 256-dimensional messages as well.
GGNN:
Many types of graph-based
We experimented with the one-directional ontalmenn--ttteniin--bale Vasic et al. (2019), but found a simpler bi-directional RNN architecture to work even better. We use GRUs as the recurrent cells, vary the number of layers from 1 to 3, and the hidden dimension (of the concatenated forward and backward component) in { [128, 256, 512].
RNNs:
RNN proposed by
Transformers: We base our architecture on the original Transformer (Vaswani et al. 2017), varying the number of layers from I to 10 and the attention dimension in { [128, 256, 512, 1024].
Sandwich Models: We distinguish between two types of sandwich models: 'small' sandwiches, which add a single RNN or Transformer to a GGNN architecture, and 'large' sandwiches, which wrap every caassage-passingg block (as defined above) with 128 228diimensional (bi-directional) RNÖ/Transformer layer. We vary the number of message-passing blocks from I to 3 (corresponding to 4 to 12 message passes) to span a similar parameter domain the GGNNs above (ca. 1.5M 5M), increasing the number of layers to 2 and their dimension to 512 for a later ablation.
GREAT: Uses the same architectural variations as the Transformer family; edge-type embedding dimensions are fixed at the per-head attention dimension, as described above.
Global byper-parameters: We train most of our models with batch sizes of {12.5K, 25K, 50K) tokens, with the exception of the Transformer architectures; due to the quadratic nature of the atten- tion computation, 25K tokens was too large for these models, so we additionally trained these with 6.25K-toker batches" Learning rates were varied in { [Ie-3, 4-e4, lc-4, 4c-5, le-5] using an Adam optimizer, where we omitted the first option for our GGNN models and the last for our RNNs due to poor performance. Sub-tokens were embedded using 128 28-dimensional embeddings.
Hardware: all our models were trained on a single Tesla P100 GPU on 25 million samples, which required between 40 and 250 hours for our various models. However, we emphasize that overall training time not our main objective; we primarily assess the ultimated converged accuracy of models and present training behavior over time for reference of our various models' training behavior.
3.3 ABOUT GRAPH REPRESENTATIONS OF CODE
Our program graphs borrow many edge types from Allamanis et al. (2018b), such as data-flow (e.g., read & write), adjacent-token, and syntactic edges, which we further augment with edges be- tween control-flow statements and function calls. When representing programs as graphs, a key decision needs to be made regarding the Abstract Syntax Tree (AST). Typically, one of the edge types in the graphs represents syntactic parent-child relationships in the AST. Additionally, some of the edges representing relations (e.g., control-flow) are naturally represented as edges between inter- nal nodes in this tree, e.g., between two I IfStatement nodes. However, ablations often find that the effectiveness of including the AST is limited in graph-based models Allamanis et al. 201 2018b).
This raises the question of whether it possible to represent programs as graphs that include se- quential and semantic information, but not syntax. To this end, we propose leaves-only graph representation for code as follows: edges that represent semantic relationships such as control flow and data flow can easily be moved down from internal nodes which typically represent span of
Which still translates into 50+ samples per hatch on average
4

---

Published as a conference paper at ICLR 2020
multiple tokens- to those leaf nodes in the graph that represent the begin token of that span. Thus, an edge that used to connect two IfStat at ement interior AST nodes is moved down to connect the corresponding if tokens. Now, the AST can be omitted entirely, thereby removing parent-child re- lations among syntax nodes, producing what we call a leaves-only graph. This latter representation is substantially more compressed than the graphs with AST', often using 2-3x fewer nodes (while retaining most of the edges), and additionally aligns better with sequence-based models, because all edges are directly connected the original code tokens We compare both settings for each graph-based model, but unless otherwise specified, we use the 'full' graphs for the regular GGNN model and the 'laaves-only' graphs (without ASTs) for the sandwich and GREAT models.
EXPERIMENTAL SETUP
The VarMisuse Task We focus our study on the variable-misuse localization-an--rpaai task (Vasic et al. 2019): given function, predict two pointers into the function's 's tokens, one pointer for the location of a variable use containing the wrong variable (or a special no-bug location), and one pointer for any occurrence of the correct variable that should be used at the faulty location instead.
Synthetic Dataset We used the ETH Py150 dataset (Raychev et al. 2016), which is based on GitHub Python code, and already partitioned into train and test splits (100K and 50K files, respec- tively). We further split the 100K train files into 90K train and 10K validation examples and applied deduplication step on that dataset (Allamanis) 2018). We extracted all top-level function defini- tions from these files; any function that uses multiple variables can be turned into a training example by randomly replacing one variable usage with another. As there may be many candidates for such bugs in function, we limit our extraction to up to three samples per function to avoid biasing our dataset too strongly towards longer functions. For every synthetically generated buggy example, an unperturbed, fig-free example of the function is included as well, to keep our dataset balanced, yielding ca. 2M total training and 755K test samples. Finally, we train with functions with up 250 tokens; at test time, we raise this to 1,000 to study our models' generalization to longer functions.
Metries As we are mainly interested contrasting the behavior of different models of code, we fo- cus most of our results on the various models' learning curves by tracking development-set accuracy on 25K held-out samples every 250K samples as the models train. Here, we measure two accuracy metrics: localization accuracy (whether the model correctly identifies the bug's 's location for buggy samples); and (independently) repair accuracy (whether the model points to the correct variable to repair the bug). Note that these metrics focus buggy samples; the models also determine whether a function is buggy, which we discuss below. We group all models by their 'family', as categorized in Section 3.2 reporting the maximum held-out performance per family.
For deeper insight into the fully trained models' performance, we also analyze the performance of the best models in each family in more depth the test portion of our synthetic dataset. Specifically, we assess their classness-llsssiicaation accuracy (whether the model correctly identifies the method as (non-)buggy) and their joint localization and repair accuracy (for buggy samples, how often the model correctly localizes and repairs the bug). Here, we also increase the maximum function size to 1,000 tokens and analyze the impact of longer functions on our models' performance.
4.1 DATA & CODE RELEASE
We release a public implementation of the GREAT model based Tensorflow, as well as the program graphs for all samples in our training and evaluation datasets whose license permits us redistribute these at: https://doi. ottp:///...rrr/..0002//////oooo0 36683333366633333 which tracks the latest release of our Github repository at: ICLR20-Great
RESULTS
There are many degrees of freedom in our family of models, so we structure our results around a series of comparisons, which we analyze and discuss in this section. We start with our key re-
Whichh, conjecture, improves the interaction hetween the two types of models.
5

---

Published as a conference paper at ICLR 2020
sult, which compares all model families (RNNs, Transformers, GGNNs, Sandwich hybrids, and
GREAT models) across a comparable parameter domain (ca. 1.4M -.5M parameters) Figure
Localization Accuracy
Repair Accuracy
50%
30%
25%
25%
16
64
16
64
Training time (h)
Training time (h)
GGNN
GREAT
ANN Transoormer
RNN Sandwich
TRF Sendwich
Localization Accuracy,
75%
75%
Repar pair Accuracy
5.0%
50%
25%
25%
Zei05
Re
Re+06
Nr. Training Samples
Nr. Training Samples
GGNN RNN
GREAT KNN
Transformer
Sandwich
Figure 1: Comparison of top- top-performing models from all model families across comparable pa- rameter domain of 1.5M - 5M parameters. Performance visualized using the localization (left) and repair (right) accuracy Pareto fronts w.r.t. both training time (top) and number of training samples seen (bottom), both log-scaled, where an epoch is ca. 2M samples. In all cases, our proposed models substantially outperform GGNNs from early in the training process.
Although there subtle differences between the models' behavior localization and repair accu- racy, the overall picture is consistent: whereas our newly proposed els already substantially outperform RNN-based models (the previous state-of-the-art), and times Transformers, the hybrid global & structured models achieve significantly better results faster.
mod-
Time-wise (the top two figures), the GGNN models take the longest converge, continuing to improve slightly even after week of training mainly because their largest (16-layer) architecture starts dominate the 12-lryer version's 's performance after ca. 170h. The Sandwich models follow its training curve, but are more accurate and faster to converge, achieving especially good results for limited training budgets, partly because they succeeded with just layers of message passing by relying on their global components.
The Transformer architecture, although slower first, widely outperforms the RNN as a baseline model. The GREAT model tracks its learning curve, starting out slower than the models with ex- plicit message passing, but gradually overtaking them after ca. 10h, as the underlying Transformer becomes increasingly effective. We note that this model achieves cfate-oftthe-ad -ert results despite having, at the time this writing, received less training time (ca. 64h compared to up to 240h).
The bottom half of Figure I abstracts away the potentially confounding issue of implementation speed of our models by tracking performance w.r.t the number of training samples. Naturally, the end-points of the curves (the converged accuracy) are identical, but importantly the various models'

---

to benefit Published as a conference paper at ICLR 2020
training curves quite similar; even here, the GGNN is only able to outperform some of our proposed models briefly, yielding inferior performance to all within just one epoch.
The RNN and GGNN models appear to be particularly complementary; localization accuracy is very poor compared to the GGNN, the combined model still sustains a ~5% improvement the latter( However, the Transformer Sandwich does not similarly, showing virtually no difference in performance with the RNN Sandwich model. This strongly suggests that the Transformer's s ability access long-distance information overlaps in large part (though not entirely, given GREAT'S performance) with the GGNNs ability to do so using message passing. We conjecture that the Transformer learns to infer many of the same connections (e.g., data-flow, control-flow) that are encoded explicitly in the graph's message passing.
dhe even though the RNN's
To understand the behavior of the many models and combinations that may be used for code, we now explore the variations on our choices of parameters, models, and metrics.
5.1 LARGER MODELS
Model capacity is potential threat to any comparison between models of different families. We aimed ensure fair comparison in the previous section by selecting a range of hyper-parameter (which includes the number of stacked layers) for these architectures that span a similar parameter count range. For instance, 6-layer Transformer with 5 512-dimensional attention is comparable to 2-layer 512-dimensional bi-directional RNN and an 8-layer GGNN. However, all these architectures are relatively modest, having at most ~5M parameters. By increasing the number, and dimension- ality of their layers,
evaluate second family of models with ca. 5-20M parameters.
Figure 2 shows the performance for the low- and high perh-prreettrr variations for each of our best- performing model families. Overall, while providing more parameters to the GGNNs made virtually no difference, all our bybrid models increase 2-3% in both localization and repair accuracy, provid- ing further support for combining global, structured models. The best-performing instances of each model family were consistently the larger architectures, 15M parameters for the GGNN, 12.5M & 10M for the RNN and Transformer Sandwiches respectively and 7.9M for GREAT
85%
85%
Localization Ancuracy
Repair Accuracy
80%
80%
75%
75%
70%
70%
Training time (h)
Training time (h)
GGNN
GGNN
GREAT
RNN Sandwich
Sanchsich++
Transformer
Sandwich+e
Figure 2: Comparison of smaller (1.5-5M parameter) and larger (5-20M parameter, identified with '+') variants each model family, Localization and repair accuracy Pareto-front w.r.t. time.
5.2 ON SYNTACTIC INFORMATION
In the previous results, the GGNN models were trained on 'full' graphs (as described in Section 3.3 that use the code's AST structure, and the sandwich models on 'leaves-only' graphs, with only source token nodes, and edges moved to connect these directly. These settings are arguably each appropriate to the underlying model, but both models can also use the alternative setting.
'Difference up to convergence of the combined model; the accuracy gap shrinks to 2.1% 1% after ca. 10 days. Which achieves state-of-the-ar results in all settings despite having had comparatively less training time.
7

---

Published as a conference paper at ICLR 2020
Localization Accuracy
Repair Accuracy
79%
79%
50%
50%
Training time (h)
Training time (h)
GONN wlo syntas
GGNN w/ syntap
TRF Sandwich vile syntak
RF Sanduidd wi syntax
Figure 3:
Comparing impact of graph representation on GGNNs and RNN Sandwich models. Lo- calization and repair accuracy Pareto-front w.r.t time. Note: y-axis cropped to simplify comparison.
Figure 3 shows the training curves for the alternative settings. In all cases, the models that do use syntax train substantially faster because each sample's graph representation is more than twice as small, these models naturally lead in accuracy early in training. However, whereas the GGNN equipped with syntax overtakes its counter-part within ca. 48h, the sandwich models display a much longer lag, with no cross-over observed all on localization accuracy in this time window
The sandwich model on full graphs still compares favorably with the GGNN baseline, though its early training behavior is not effective. It also interesting to that the bert-performing Sandwich models in this setting were consistently architectures with more message-passing steps. This may be due to the additional distance between information propagated along the tokens and along semantic edges, which in this setting are almost universally connected to AST-innernal nodes.
5.3 RNNS IN SANDWICHES: SINGLE VS. MANY
Recent work on neural summarization also mixed RNNs and GGNNs (Fernandes et al. 2018), but did so by inserting single RNN layer into GNN architecture, before any message passing. We compare this architecture to full Sandwich model in Figure 4 Although a single RNN certainly helps compared to the GGNN, interlcaving RNNs and GGNN-style message passes performed sub- stantially better. In fact, the best performing full Sandwiches used fewer parameters than the Single models because they used message passes instead of 12, relying more heavily on the RNNs
5.4 TEST-SET ANALYSIS
Having identified our fest-performing models in each family, we now study their performance on the test data, specifically using the metrics used in Vasic al. (2019) (see Section 4) in Table [ In general, the two metrics correlated well; models that accurately determined whether a function contained bug also accurately identified the bug (and repair), as may expected. The baseline RNN model achieves a modest 44% accuracy at the latter task; this is slightly lower than reported in prior work (Vasic al. 2019), which likely due part to our dataset de-duplication. Transformers and GGNNs perform substantially better (and comparably, though the latter trained 6x longer for this performance), but still fall well short of our hybrid models' performance, which are especially much more accurate on long functions. The GREAT model shows most promise the repair task, already outperforming the sandwich models despite having so far had limited training time.
*Given the slope of the two curves, we expect reversal after 10+ days of training. Thhe same pattern held for high-parameter versions of these models, where the performance gap also grew.
8

---

Published as a conference paper at ICLR 2020
Localization Accuracy
Repair Accuracy
78%
79%
50%
50%
Training time (h)
Training time (h)
Famandes Sandwich GGNN
Figure 4: Comparison of RNN sandwiches with a single RNN vs. those with RNNs around every message-passing block ("Multi'). Localization and repair accuracy Pareto-front w.r.t time.
Table I: Test-set results of best-performing models by family, metrics of Vasic al. (019))
Grouped by maximum length; 6.5% of test set samples exceeded 250 tokens (the training limit).
Class. Accuracy
Loc & Rep Accuracy
Training
Model Family
< 250
< 1000
S. 250
< 1000
Parameters
Time
RNNI
71.8%
70.6%
44.4%
42.5%
4.3M
31.3h
Transformer
75.9%
73.2%
67.7%
63.0%
3.7M
41.5h
GGNN
81.4%
79.2%
64.0%
60.9%
5.5M
24th
RNN Sandwich
82.5%
81.9%
75,8%
73.8%
12.6M
109h
Transformer Sandwich
81.1%
78.1%
74.5%
71.4%
10M
161h
GREAT
80.1%
76.9%
76.4%
73.1%
7.9M
120h
I: a stronger version of the model proposed
Vasic et al. (2019) (previous SOTA).
5.5 REAL BUGS ANALYSIS
We want to ensure that our models can be useful for real bugs and do not simply overfit to the synthetic data generation that used. This risk exists because we did not filter our introduced bugs based on whether they would be difficult to detect, for instance because they conflate variables with similar names, usage, data types; presumably, such bugs are more likely to escape developer's notice and find their way into real code bases. is therefore expected that performance on real- world bugs will be lower for all models, but must assert that proposed models do not just outperform GGNNs on synthetic data, e.g. by memorizing characteristics of synthetic bugs.
To mitigate this threat, we collect real variable misuse bugs from code on Github. Specifically, we collect ca. I million commits that modify Python files from Github. We extracted all changes to functions from these commits, filtering these according the same criteria that we used introduce variable-min misuse bugs: we looked for commits that exclusively changed a single variable usage in function body from one variable in scope to another. We focus on functions with up 250 tokens, since all our models performed substantially better these in Table I We identified 170 such changes, which we assumed that the version before the change was buggy and the updated version correct. We removed any functions that had occurred in training data, of which we found 9 and paired the remaining functions up (correct and buggy) to create a real-world evaluation set with 322 functions, which presented our models.
T shows the results of running our various models on these bugs. In general, these were clearly substantially more difficult for all our models than the synthetic samples generated. However, see a clear difference in performance with all our proposed models performing substantially better than previous baselines, and showing favorable precision/recall trade-offs.

---

Published as a conference paper at ICLR 2020
Table 2: Results 322 paired buggy and non-buggy samples from 161 real variable misuse bugs mined from Github commits. "Class.' measures accuracy at identifying non-buggy samples; 'Prec." and 'Rec.' capture the precision and recall at identifying the correct localization and repair on the buggy samples.
All Samples
Precision at
Precision
Model Family
Class.
Prec.
Rec.
Recall 5%
Recall 10%
RNN 52.8%
13.3%
46.6%
44,4%
23.5%
Transformer
62.1%
13.8%
47.2%
33.3%
17.6%
GGNN
65.8%
17.7%
42.2%
44.4%
23.5%
RNN Sandwich
69.6%
28.6%
43.5%
77.8%
64.7% %
Trans. Sandwich
75.2%
21.5%
40.4%
33.3%
35.3%
GREAT
70.2%
23.7%
36.7%
44.4%
29.4%
CONCLUSION
We demonstrate that models leveraging richly structured representations of source code do not have to be confined to local contexts. Instead, models that leverage only limited message passing in combination with global models learn much more powerful representations faster. We proposed two different architectures for combining local and global information: sandwich models that com- bine two different message-passing schedules and achieve highly competitive models quickly, and the GREAT model which adds information from a sparse graph to Transformer to achieve state- of-the-art results. In the process, we raise the state-of-the-ard performance on the VarMisuse bug localization and repair task by over 30%.
REFERENCES
Miltiadis Allamanis. The adverse effects of code duplication in machine learning models of code. CoRR, abs/1812.066a 2018. Uttptt/p://arxi www.aaiwww..r.aaaaeeeaoee.o aalg///b//// 1811111441 06469
Miltiadis Allamanis and Charles Sutton. Mining source code repositories massive scale using language modeling. Working Conference on Mining Software Repositories (MSR), 2013.
Miltiadis Allamanis, Earl Barr, Christian Bird, and Charles Sutton. Suggesting accurate method and class names. In Proceedings of the 2015 10th Joint Meeting Foundations of Software Engineering, pp. 38-48 49. ACM, 2015.
Miltiadis Allamanis, Earl Barr, Premkumar Devanbu, and Charles Sutton. A survey of machine learning for big code and naturalness. ACM Comput. Surv., 51(4):81:1-81:37, July 2018a. ISSN 0360-0300.
Miltiadis Allamanis, Mare Brockschmidt, and Mahmoud Khademi. Learning to represent programs with graphs. In International Conference Learning Representationss 2018h. 8b.
Uri Alon, Meital Zilberstein, Omer Levy, and Eran Yahav. code2vec: Learning distributed repre- sentations of code. CoRR, abs/1 803.893377777 .04993,7 2018.
Uri Alon, Shaked Brody, Omer Levy, and Eran Yahav, code2seq: Generating sequences from struc- tured representations of code. In 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
Avishkar Bhoopchand, Tim Rocktäschel, Earl Barr, and Sebastian Riedel. Learning python code suggestion with sparse pointer network. arXiv preprint arXiv:1611.08307 2016.
Xinyun Chen, Chang Liu, and Dawn Song. Tree-to-tree neural networks for program translation. In S. Bengio, H. Wallach, Н. Larochelle, K. Grauman, N. Cesa- Besa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31. pp. 2557.. Curran Associates, Inc.. 2018. URL httlltt/ppppper...... http:/eerr..iss.c.c.pppppeee 752 1521-tree-t-- ree neura -netwrorsssttoss------o- ort.eeennnnnnaaiiooooooooooooror ora
10

---

Published as a conference paper at ICLR 2020
Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Hol- ger Schwenk, and Yoshua Bengio. Learning phrase representations using rmn encoder-decoder for statistical machine translation. arXiv preprint arXiv:1406.1073 2014.
Patrick Fernandes, Miltiadis Allamanis, and Mare Brockschmidt. Structured neural summarization. arXiv preprint arXiv: arXiv:1811.01824 2018.
Luca Gazzola, Daniela Micucci, and Leonardo Mariani. Automatic software repair: A survey. IEEE Trans. Software Eng., 45(1):34-67, 2019.
Vincent J Hellendoorn and Premkumar Devanbu. Are deep neural networks the best choice for modeling source code? In Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering, pp. (63-773. ACM, 2017.
Vincent J Hellendoom, Christian Bird, Earl T Barr, and Miltiadis Allamanis. Deep learning type inference. In Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, pp. 152-162. ACM, 2018.
Abram Hindle, Earl T. Barr, Zhendong Su, Mark Gabel, and Premkumar Devanbu. On the natural- ness of software. In Proceedings of the 34th International Conference on Software Engineering, ICSE '12, pp. 837-847, 2012.
Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. Gated graph sequence neural networks, 2015.
Martin Monperrus. Automatic software repair: A bibliography. ACM Comput. Surv., 51(1):17:1- 17:24, January 2018 ISSN 0360-0300.
Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Push- meet Kohli. Neuro-symbolic program synthesis. CoRR, abs/1611.01855, 2016. URL http:
//arxiv.org/abb//660.
Chris Piech, Jonathan Huang, Andy Nguyen, Mike Phulsuksombati, Mehran Sahami, and Leonidas Guibas. Learning program embeddings to propagate feedback on student code. In Proceedings of the 32Nd International Conference on International Conference on Machine Learning Volume 37, ICML'15, pp. 1093-1102, 2015.
Veselin Raychev, Martin Vechev, and Andreas Krause. Predicting program properties from "big code". In Proceedings of the 42Nd Annual ACM SIGPLAN-SIGACT Symposium Principles of Programming Languages, POPL 115 pp. 111-124, 2015.
Veselin Raychev, Pavol Bielik, and Martin T. Vechev. Probabilistic model for code with decision trees. Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriente Programming, Systems, Languages, and Applications, OOPSLA 2016. part of SPLASH 2016, Amsterdam, The Netherlands, October 30- November 4, 2016, pp. 731-747, 2016.
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position representa- tions. arXiv preprint arXiv:1803. 103.v1180..02155. 2018
Marko Vasic, Aditya Kanade, Petros Maniatis, David Bieber, and Rishabh Singh. Neural program repair by jointly learning to localize and repair. arXiv preprini 1904:0000 2019.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
Ashish Vaswani, Samy Bengio, Eugene Brevdo, François Chollet, Aidan N. Gomez, Stephan Gouws, Llion Jones, Lukasz Kaiser, Nal Kalchbrenner, Niki Parmar, Ryan Sepassi, Noam Shazeer, and Jakob Uszkoreit. Tensor2tensor for neural machine translation. In Proceedings of the 13th Conference of the Association for Machine Translation in the Americas, AMTA 2018, Boston, MA, USA, March 17-21. 2018 Volume 1: Research Papers, pp. 193-199, 2018. URL https: www. a web. or rg/ antho ogy W1 8 1819/

---

Published as a conference paper at ICLR 2020
Ke Wang, Rishabh Singh, and Zhendong Su. Dynamic neural program embeddings for program repair. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings, 2018.
Martin White, Christopher Vendome, Mario Linares- Linares-Vásquez, and Denys Poshyvanyk. Toward deep learning software repositories. In Proceedings of the 12th Working Conference on Mining Software Repositories, pp. 334-345-55 IEEE Press, 2015.
12


Reviews:
[{"review_id": "SJgoCH9TKB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes improvements on existing probabilistic models for code that predicts and repairs variable misuses. This is a variant of the task, proposed by Vasic et al. The task takes a dataset of python functions, introduces errors in these functions and makes a classifier that would identify what errors were introduced and effectively reconstruct the original code.\n\nThe paper claims to improve state-of-the-art results published by Vasic et al for this task, however the RNN model by Vasic et al was known to be far from optimal when the work was published. Furthermore, that task was evaluated on artificially introduced changes (the original code could contain an error), but it is not clear that the improvements would have any practical effect. In fact, I conjecture that the bug-detector is in fact worse, because the entire dataset is not sufficiently large for millions of parameters and it is not clear that bugs that were originally the dataset were not learned by the better model, making it worse at spotting them. Given the relatively thinner contribution on the rest of the paper, I think this would be a valid question to be addressed to show the effectiveness of the model beyond accuracy on the artificial task.\n\nThe paper does a number of contributions to the neural architecture. The most important change precision-wise is to use transformer model instead of RNN (the model used by Vasic et al).  This change is also what makes the work perform as well or better than GGNN-based approaches. The paper then proposes to improve the transformer model by modifying the attention where there are edges. The rest of the contributions seem to be addressing the problem of aster convergence speed.  The other contribution of the paper is by selecting which edges to include and it is also shown to improve convergence speed.\n\nGiven that most of the work talks about performance, it would also help if the authors clarify what kind of hardware was used and which optimizer.\n\nQ: Why a larger transformer model was not evaluated?\n\nMore minor issues:\n“We conjecture that the Transformer learns to infer many of the same connections”. There is no confirmation for this besides similar accuracy, but if this is the case, why would I change the architecture and not just try with initializing the vectors to values corresponding to this knowledge and get faster convergence?\npage 3, “where q and k correspond to the query and key vectors as described above,”. It seems it is q_i and k_j?\n\nUpdate after the rebuttal:\n\n - I thank the authors for running additional experiments on a short notice. I have some reservations about their correctness though (we still do not know if there were bugs fixed in these commits, their number is very low and the authors seem to have cherrypicked the numbers to show - their first updated revision had recall at 20%, then decided to show it at 10%, the RNN baseline is actually having the highest recall of all although it is not highlighted). I am not sure that data cleaning of this small evaluation sample will not show a different picture.\n\n - I actually increase my score a bit (I was torn in the beginning), because this is one of the first papers to run transformer model on code. I still think the actual contributions of the paper are minor.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "HklypX-iYH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors proposed a new method to model the source code for the bug repairing task. Traditional methods use either a global sequence based model or a local graph based model. The authors proposed a new sandwich model like [RNN GNN RNN]. The experiments show that such simple combination of models significantly improve the localization and repair accuracy. \n\nThe idea is simple, so the technical contribution is a bit low. But the message is clear. The sandwich model can benefit from GNN model that can achieve a higher accuracy at the beginning of training where transformer did a poor job. At the end of training, the sandwich model outperforms both kinds of models.\n\nHere are some detailed comments:\n1. It would be interesting to have the complete result from Transformer in Figure 1 and Figure 2 which is missing.\n2. The results from GGNN (smaller model) in Figure 1 and Figure 2 seems to be not the same.\n3. One major benefit of GNN is its efficient local computation. Some industrial applications have also used GNN for recommendation that can be trained very fast. Why GGNN is so slow in this paper? Is this because of implementation? \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "HJelNGkaKr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Strength:\n-- Interesting problem\n--The paper is well written and easy to follow\n-- The proposed approach seems very effective\n\nWeakness:\n-- the novelty of the proposed is marginal\n-- Some of the claims are not right in the paper\n\nThis paper studied learning the representations of source codes by combining sequential-based approaches (RNN, Transformers) and graph neural network to model both the local and global dependency between the tokens. Experimental results on both synthetic and real-world datasets prove the effectiveness of the proposed approach.\n\nOverall, the paper is well written and easy to follow. However, the novelty of the proposed technique seems to be marginal to me. Some of the claims in the paper are not right. In the abstract, the authors said the graph neural network is more local-based while the transformer is more global-based. The essential difference between the two approaches lie in the way of constructing the graphs since transformer used the fully-connected graph (more local dependency) while graph neural networks usually capture the long-range dependency. \n\nAnd there are actually some existing work that have already explored this idea in the context of natural language understanding, e.g.,\nContextualized Non-local Neural Networks for Sequence Learning. https://arxiv.org/abs/1811.08600\nThe authors should clarify the difference between these approaches.\n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper investigates hybrid NN architectures to represent programs, involving both local (RNN, Transformer) and global (Gated Graph NN) structures, with the goal of exploiting the program structure while permitting the fast flow of information through the whole program.

The proof of concept for the quality of the representation is the performance on the VarMisuse task (identifying where a variable was replaced by another one, and which variable was the correct one). Other criteria regard the computational cost of training and number of parameters.

Varied architectures, involving fast and local transmission with and without attention mechanisms, are investigated, comparing full graphs and compressed (leaves-only) graphs. The lessons learned concern the trade-off between the architecture of the model, the computational time and the learning curve. It is suggested that the Transformer learns from scratch to connect the tokens as appropriate; and that interleaving RNN and GNN allows for more effective processing, with less message passes and less parameters with improved accuracy.

A first issue raised by the reviewers concerns the computational time (ca 100 hours on P100 GPUs); the authors focus on the performance gain w.r.t. GGNN in terms of computational time (significant) and in terms of epochs. Another concern raised by the reviewers is the moderate originality of the proposed architecture. I strongly recommend that the authors make their architecture public; this is imo the best way to evidence the originality of the proposed solution. 

The authors did a good job in answering the other concerns, in particular concerning the computational time and the choice of the samples. I thus recommend acceptance. 
Decision: Accept (Poster)