Title: OPEN VOCABULARY LEARNING ON SOURCE CODE WITH A GRAPH-STRUCTURED CACHE Anonymous

Abstract: Machine learning models that take computer program source code as input typically use Natural Language Processing (NLP) techniques. However, a major challenge is that code is written using an open, rapidly changing vocabulary due to, e.g., the coinage of new variable and method names. Reasoning over such a vocabulary is not something for which most NLP methods are designed. We introduce a Graph-Structured Cache to address this problem; this cache contains a node for each new word the model encounters with edges connecting each word to its occurrences in the code. We find that combining this graph-structured cache strategy with recent Graph-Neural-Network-based models for supervised learning on code improves the models' performance on a code completion task and a variable naming task -with over 100% relative improvement on the latter -at the cost of a moderate increase in computation time.

1. INTRODUCTION:

Computer program source code is an abundant and accessible form of data from which machine learning algorithms could learn to perform many useful software development tasks, including variable name suggestion, code completion, bug finding, security vulnerability identification, code quality assessment, or automated test generation. But despite the similarities between natural language and source code, deep learning methods for Natural Language Processing (NLP) have not been straightforward to apply to learning problems on source code (Allamanis et al., 2017) .

There are many reasons for this, but two central ones are:

1. Code's syntactic structure is unlike natural language. While code contains natural language words and phrases in order to be human-readable, code is not meant to be a read like a natural language text. Code is written in a rigid syntax with delimiters that may open and close dozens of lines apart; it consists in great part of references to faraway lines and different files; and it describes computations that proceed in an order often quite distinct from its written order.

2. Code is written using an open vocabulary. Natural language is mostly composed of words from a large but closed (a.k.a. fixed-size and unchanging) vocabulary. Standard NLP methods can thus perform well by fixing a large vocabulary of words before training, and labeling the few words they encounter outside this vocabulary as "unknown". But in code every new variable, class, or method declared requires a name, and this abundance of names leads to the use of many obscure words: abbreviations, brand names, technical terms, etc.1 A model must be able to reason about these newly-coined words to understand code.

The second of these issues is significant. To give one indication: 28% of variable names contain out-of-vocabulary words in the test set we use in our experiments below. But more broadly, the open vocabulary issue in code is an acute example of a fundamental challenge in machine learning:

how to build models that can reason over unbounded domains of entities, sometimes called "openset" learning. Despite this, the open vocabulary issue in source code has received relatively little attention in prior work.

The first issue, in contrast, has been the focus of much prior work. A common strategy in these works is to represent source code as an Abstract Syntax Tree (AST) rather than as linear text. Once in this graph-structured format, code can be passed as input to models like Recursive Neural Networks or Graph Neural Networks (GNNs) that can, in principle, exploit the relational structure of their inputs and avoid the difficulties of reading code in linear order (Allamanis et al., 2018) .

Our contribution: In this paper we extend such AST-based models for source code in order to address the open vocabulary issue. We do so by introducing a Graph-Structured Cache (GSC) to handle out-of-vocabulary words. The GSC represents vocabulary words as additional nodes in the AST as they are encountered and connects them with the edges to where they are used in the code.

We then process the AST+GSC with a GNN to produce outputs. See Figure 1 .

We empirically evaluated the utility of a Graph-Structured Cache on two tasks: a code completion (a.k.a. fill-in-the-blank) task and a variable naming task. We found that using a GSC improved performance on both tasks at the cost of an approximately 30% increase in training time. More precisely: even when using hyperparameters optimized for the baseline model, adding a GSC to a baseline model improved its accuracy by at least 7% on the fill-in-the-blank task and 103% on the variable naming task. We also report a number of ablation results in which we carefully demonstrate the relative importance of each model component to a model's performance.

2. PRIOR WORK REPRESENTING CODE AS A GRAPH:

Given their prominence in the study of programming languages, Abstract Syntax Trees (ASTs) and parse trees are a natural choice for representing code and have been used extensively. Often models that operate on source code consume ASTs by linearizing them (usually with a depth-first traversal) as in Amodio et al. (2017) , Liu et al. (2017) , or Li et al. (2017) or by using AST paths as input features as in Alon et al. (2018) , but they can also be processed by deep learning models that take graphs as input, as in White et al. (2016) and Chen et al. (2018) who use Recursive Neural Networks (RveNNs) (Goller & Kuchler, 1996) on ASTs. RveNNs are models that operate on treetopology graphs, and have been used extensively for language modeling (Socher et al., 2013) and on domains similar to source code, like mathematical expressions (Zaremba et al., 2014; Arabshahi et al., 2018) . They can be considered a special case of Message Passing Neural Networks (MPNNs) in the framework of Gilmer et al. (2017) : in this analogy RveNNs are to Belief Propagation as MPNNs are to Loopy Belief Propagation. They can also be considered a special case of Graph Networks in the framework of Battaglia et al. (2018) . ASTs also serve as a natural basis for models that generate code as output, as in Maddison & Tarlow (2014) , Yin & Neubig (2017) , Rabinovich et al. (2017) , Chen et al. (2018), and Brockschmidt et al. (2018) .

Data-flow graphs are another type of graphical representation of source code with a long history (Krinke, 2001) , and they have occasionally been used to featurize source code for machine learning (Chae et al., 2017) .

Most closely related to our work is the work of Allamanis et al. (2018) , on which our model is heavily based. Allamanis et al. (2018) combine the data-flow graph and AST representation strategies for source code by representing code as an AST augmented with extra labeled edges indicating semantic information like data-and control-flow between variables. These augmentations yield a directed multigraph rather than just a tree,2 so in Allamanis et al. (2018) a variety of MPNN called a Gated Graph Neural Network (GGNN) (Li et al., 2016) is used to consume the Augmented AST and produce an output for a supervised learning task.

Graph-based models that are not based on ASTs are also sometimes used for analyzing source code, like Conditional Random Fields for joint variable name prediction in (Raychev et al., 2015) .

REASONING ABOUT OPEN SETS:

The question of how to gracefully reason over an open vocabulary is longstanding in NLP.

Character-level embeddings are a typical way deep learning models handle this issue, whether used on their own as in Kim et al. (2016) , or in conjunction with word-level embedding Recurrent Neural Networks (RNNs) as in Luong & Manning (2016) , or in conjunction with an n-gram model as in Bojanowski et al. (2017) . Another approach is to learn new word embeddings on-the-fly from context (Kobayashi et al., 2016) . Caching novel words, as we do in our model, is yet another strategy (Grave et al., 2017) and has been used to augment N-gram models for analyzing source code (Hellendoorn & Devanbu, 2017) .

In terms of producing outputs over variable-sized input and outputs, also known as open-set learning, attention-based pointer mechanisms were introduced in Vinyals et al. (2015) and have been used for tasks on code, e.g. in Bhoopchand et al. (2016) . Such methods have been used to great effect in NLP in e.g. Gulcehre et al. (2016) and Merity et al. (2017) . The latter's pointer sentinel mixture model is the direct inspiration for the readout function we use in the Variable Naming task below.

Using graphs to represent arbitrary collections of entities and their relationships for processing by deep networks has been widely used (Johnson, 2017; Bansal et al., 2017; Pham et al., 2018; Lu et al., 2017) , but to our knowledge we are the first to use a graph-building strategy for reasoning (at train and test time) about an open vocabulary of words.

3. PRELIMINARIES:



3.1. ABSTRACT SYNTAX TREES:

An Abstract Syntax Tree (AST) is a graph -specifically an ordered tree with labeled nodes -that is a representation of some written computer source code. There is a 1-to-1 relationship between source code and an AST of that source code, modulo comments and whitespace in the written source code.

Typically the leaves of an AST correspond to the tokens written in the source code, like variable and method names, while the non-leaf nodes represent syntactic language constructs like function calls or class definitions. The specific node labels and construction rules of ASTs can differ between or within languages. The first step in Figure 1 shows an example.

3.2. GRAPH NEURAL NETWORKS:

The term Graph Neural Network (GNN) refers to any deep, differentiable model that takes graphs as input. Many GNNs have been presented in the literature, and several nomenclatures have been proposed for describing the computations they perform, in particular in Gilmer et al. (2017) and Battaglia et al. (2018) . Here we give a brief recapitulation of supervised learning with GNNs using the Message Passing Neural Network framework from Gilmer et al. (2017) .

A GNN is trained using pairs (G, y) where G = (V, E) is a graph defined by its vertices V and edges E, and y is a label. y can be any sort of mathematical object: scalar, vector, another graph, etc. In the most general case, each graph in the dataset can be a directed multigraph, each with a different number of nodes and different connectivity. In each graph, each vertex v ∈ V has associated features x v , and each edge (v, w) ∈ E has features e vw .

A GNN produces a prediction ŷ for the label y of a graph G = (V, E) by the following procedure:

1. A function S is used to initialize a hidden state vector h 0 v for each vertex v ∈ V as a function of the vertex's features (e.g., if the x v are words, S could be a word embedding function):

h 0 v = S(x v ) 2.

For each round t out of T total rounds: (a) Each vertex v ∈ V receives the vector m t+1 v , which is the sum of "messages" from its neighbors, each produced by a function M t :

m t+1 v = w∈neighbors of v M t (h t v , h t w , e vw ).

(b) Each vertex v ∈ V updates its hidden state based on the message it received via a function

U t : h t+1 v = U t (h t v , m t+1 v ). 3. A function

R, the "readout function", produces a prediction based on the hidden states generated during the message passing (usually just those at from time T ):

ŷ = R({h t v |v ∈ V, t ∈ 1, ..., T }).

GNNs differ in how they implement S, M t , U t , and R. But all these functions are differentiable and most are parameterized, so the model is trainable via stochastic gradient descent of a loss function on y and ŷ.

4. MODEL:

Our model consumes an input instance of source code and produces an output for a supervised learning task via the following five steps, sketched in Figure 1 :

1. Parse the source code (snippet, file, repository, version control history, etc.) into an Abstract Syntax Tree.

2. Add edges of varying types (details in Appendix Table 8 ) to this AST that represent semantic information like data-and control-flow, in the spirit of Allamanis et al. (2018) . Also add the reversed version of all edges with their own edge type. This results in a directed multigraph called an Augmented AST.

3. Further augment the Augmented AST by adding a Graph-Structured Cache. That is, add a node to the Augmented AST for each vocabulary word encountered in the input instance. Then connect each such "cache node" with an edge (of edge type WORD USE) to all variables whose names contain its word.

4. Vectorize the Augmented AST + GSC graph into a form suitable for a GNN. (I.e. perform

Step 1 from Section 3.2.) Each AST node that doesn't represent a variable is vectorized as a learned embedding of the language construct it represents, e.g. Parameter, Method Declaration, etc. Each cache node and each node that represents a variable is vectorized as a learned linear map of the concatenation of a type embedding and a name embedding.

The name embedding is a Character-Level Convolutional Neural Network (CharCNN) (Zhang et al., 2015) embedding of the word/name the node contains. The type embedding is a learned embedding of the name of the Java type of the token it contains, e.g. int, a user-defined class, etc., with cache nodes having their own unique Cacher Node type.

5. Process the graph with a GNN, as per Section 3.2. (I.e. perform Steps 2 and 3 from Section 3.2.) The readout functions differ depending on the task and are described in the Experiments section below.

Our main contribution to previous works is the addition of Step 3, the Graph-Structured Cache step. The combination of relational information from the cache nodes' connections and lexical information from these nodes' CharCNN embeddings allows the model to, in principle, flexibly reason about words it never saw during training, but also recognize words it did. E.g. it could potentially see a class named "getGuavaDictionary" and a variable named "guava dict" and both (a) utilize the fact that the word "guava" is common to both names despite having never seen this word before, and (b) exploit learned representations for words like "get", "dictionary", and "dict" that it has seen during training.

5. EXPERIMENTS:

We evaluated our model, described in Section 4, on two supervised tasks: a Fill-In-The-Blank task and a Variable Naming task. For each task, we compare our model to others that differ in how they parse the code and how they treat the words they encounter. randomly selected 18 of the 100 most popular Java repos from the Maven repository5 to serve as training data. (See Appendix Table 7 for the list.) Together these repositories contain about 500,000 non-empty, non-comment lines of code. We checked for excessive code duplication in our dataset (Lopes et al., 2017) using CPD6 and found only about 7% of the lines to be contiguous, duplicated code blocks containing more than 150 tokens.

We randomly chose 3 of these repositories to sequester as an "Unseen Repos" test set. We then separated out 15% of the files in the remaining 15 repositories to serve as our "Seen Repos" test set.

The remaining files served as our training set, from which we separated 15% of the datapoints to act as a validation set.

Our data preprocessor builds on top of the open-source Javaparser7 library to generate ASTs of our source code and then augment the ASTs with the edges described in Appendix Table 8 . We used Apache MXNet8 as our deep learning framework. All hidden states in the GNN contained 64 units; all GNNs ran for 8 rounds of message passing; all models were optimized using the Adam optimizer (Kingma & Ba, 2015) ; all inputs to the GNNs were truncated to a maximum size of 500 nodes centered on the <FILL-IN-THE-BLANK> or <NAME-ME> tokens. About 53% of input graphs were larger than 500 nodes before truncation. The only regularization we used was early stopping -early in our experiments we briefly tried L 2 and dropout regularization, but saw no effects.

We performed only a moderate amount of hyperparameter optimization, but all of it was done on the baseline models to avoid biasing our results in favor of our model. Specifically, we tuned all hyperparameters on the Closed Vocab baseline model, and also did a small amount of extra learning rate exploration for the Pointer Sentinel baseline model to try to maximize its performance.

5.2. THE FILL-IN-THE-BLANK TASK:

In this task we randomly selected a single usage of a variable in some source code, replaced it with a <FILL-IN-THE-BLANK> token, and then asked the model to predict what variable should have been there. An example instance from our dataset is shown in Figure 2 . The models indicate their prediction for what variable should go in the blank by pointing with neural attention over all the nodes in the AugAST. This means all training and test instances only considered cases where the obfuscated variable appears somewhere else in the code. Single uses are rare however, since in Java variables must be declared before they are used. It also means there are sometimes multiple usages of the same, correct variable to which a model can point to get the right answer. In our dataset 78% of variables were used more two times, and 33% were used more than four times.

The models compute the attention weightings y i for each Augmented AST node i differently depending on the readout function of the GNN they use. Models using a GGNN as their GNN component, as all those in Table 2 do, compute the attention weightings as per Li et al. (2016) :

ŷi = σ f 1 (h T v , h 0 v ) f 2 (h T v )

, where the f s are MLPs, h t v is the hidden state of node v after t message passing iterations, σ is the sigmoid function, and is elementwise multiplication. The DTNN and RGCN GNNs compute the attention weightings as per Schütt et al. ( 2017):

ŷi = f (h T v )

, where f is a single hidden layer MLP. The models were trained using a binary cross entropy loss computed across the nodes in the graph.

The performance of models using our GSC versus those using other methods is reported in Table 2 . For context, a baseline strategy of random guessing among all variable nodes within an edge radius of 8 of the <FILL-IN-THE-BLANK> token achieves an accuracy of 0.22. We also compare the performance of different GNNs in Table 3 .

5.3. THE VARIABLE NAMING TASK:

In this task we replaced all usages of a name of a particular variable, method, class, or parameter in the code with the special token <NAME-ME>, and asked the model to produce the obfuscated Table 2 : Accuracy on the Fill-In-The-Blank task. Our model is the AugAST-GSC. The first number in each cell is the accuracy of the model, where a correct prediction is one in which the graph node that received the maximum attention weighting by the model contained the variable that was originally in the <FILL-IN-THE-BLANK> spot. The second, parenthetical numbers are the top-5 accuracies, i.e. whether the correct node was among those that received the 5 largest attentions weightings from the model. See Table 1 name (in the form of the sequence of words that compose the name). An example instance from our dataset is shown in Figure 3 . . . . To produce a name from the output of the GNN, our models used the readout function of Allamanis et al. (2018) . This readout function computes the mean of the hidden states of the <NAME-ME> nodes and passing it as the initial hidden state to a 1-layer Gated Recurrent Unit (GRU) RNN (Cho et al., 2014) . This GRU is then unrolled to produce words in its predicted name, in the style of a traditional NLP decoder. We used a fixed length unrolling of 8 words, as 99.8% of names in our training set were 8 or fewer words long. The models were trained by cross entropy loss over the sequence of words in the name.

To decode each hidden state output of the GRU h into a probability distribution P vocab (w|h) over words w, the Closed Vocab and CharCNN models pass h through a linear layer and a softmax layer with output dimension equal to the number of words in their closed vocabularies (i.e. a traditional decoder output for NLP). In contrast, the GSC model not only has access to a fixed-size vocabulary but can also produce words by pointing to cache nodes in its Graph-Structured Cache. Specifically, it uses a decoder architecture inspired by the Pointer Sentinel Mixture Model of Merity et al. (2017) : the probability of a word w being the GSC decoder's output given that the GRU's hidden state was h is P (w|h) = P graph (s|h)P graph (w|h) + (1 -P graph (s|h))P vocab (w|h)

where P graph (•|h) is a conditional probability distribution over cache nodes in the GSC and the sentinel s, and P vocab (•|h) is a conditional probability distribution over words in a closed vocabulary. P graph (•|h) is computed by passing the hidden states of all cache nodes and the sentinel node through a single linear layer and then computing the softmax dot-product attention of these values with h. P vocab (•|h) is computed as the softmax of a linear mapping of h to indices in a closed vocabulary, as in the Closed Vocab and CharCNN models. If there is no cache node for w in the Augmented AST or if w is not in the model's closed dictionary then P graph (w|h) and P vocab (w|h) are 0, respectively.

The performance of our GSC versus other methods is reported in Table 4 . More granular performance statistics are reported in Appendix Table 6 . We also compare the performance of different GNNs in Table 5 . 

6. DISCUSSION:

As can be seen in Tables 2 and 4 , the addition of a GSC improved performance on all tasks. Our full model, the AugAST-GSC model, outperforms the other models tested and does comparatively well at maintaining accuracy between the seen and unseen test repos on the Variable Naming task.

To some degree the improved performance from adding the GSC is unsurprising: its addition to a graph-based model is essentially just adding extra features and doesn't remove any information or flexibility. Under a satisfactory training regime, a model could simply learn to ignore it if it is unhelpful, so its inclusion should never hurt performance. The degree to which it helps, though, especially on the Variable Naming task, suggests that a GSC is well worth using for some tasks. Moreover, the fact that the Pointer Sentinel approach shown in Table 4 performs noticeably less well than the full GSC approach suggests that the relational aspect of the GSC is key: simply having the ability to output out-of-vocabulary words without relational information about their usage appears to be much less helpful.

The downsides of using a GSC are thus primarily computational. Our GSC models ran about 30% slower than the Closed Vocab models. Since we capped the graph size at 500 nodes, the slowdown is presumably due to the large number of edges to and from the graph cache nodes. Better support for sparse operations on GPU in deep learning frameworks would be useful for alleviating this downside.

In the near term, there remain a number of design choices to explore regarding AST-and GNNmodels for processing source code. Adding information about word order to the GSC might improve performance, as might constructing the vocabulary out of subwords rather than words. It also might help to treat variable types as the GSC treats words: storing them in a GSC and connecting them with edges to the variables of those types; this could be particularly useful when working with code snippets rather than fully compilable code. For the Variable Naming task, there are also many architecture choices to be explored in how to produce a sequence of words for a name: how to unroll the RNN, what to use as the initial hidden state, etc.

In the longer term, given that all results above show that augmenting ASTs with data-and controlflow edges improves performance, it would be worth exploring other static analysis concepts from the Programming Language and Software Verification literatures and seeing whether they could be usefully incorporated into Augmented ASTs. Better understanding of how Graph Neural Networks learn is also crucial, since they are central to the performance of our model and many others. Additionally, the entire domain of machine learning on source code faces the practical issue that many of the best data for supervised learning on source code -things like high-quality code reviews, integration test results, code with high test coverage, etc. -are not available outside private organizations.

Table 8 : Edge types used in Augmented ASTs. The initial AST is constructed using the AST and NEXT TOKEN edges, and then the remaining edges are added. In other words, the the "AST" model from Table 1 uses a graph that contains only the AST and NEXT TOKEN edge types (and WORD USE if it also uses a GSC), while the "AugAST" model contains all the edge types below. The reversed version of every edge is also added as its own type (e.g. reverse AST, reverse LAST READ) to let the GNN message passing occur in both directions.

Edge Name Description:



AST:

The edges used to construct the original AST.

NEXT TOKEN:

Edges added to the original AST that specify the left-toright ordering of the children of a node in the AST. These edges are necessary since ASTs have ordered children, but we are representing the AST as a directed multigraph.

COMPUTED FROM:

Connects a node representing a variable on the left of an equality to those on the right. (E.g. edges from y to x and z to x in x = y + z.) The same as in Allamanis et al. (2018) .

LAST READ:

Connects a node representing a usage of a variable to all nodes in the AST at which that variable's value could have been last read from memory. The same as in Allamanis et al. (2018) .

LAST WRITE:

Connects a node representing a usage of a variable to all nodes in the AST at which that variable's value could have been last written to memory. The same as in Allamanis et al. (2018) .

RETURNS TO:

Points a node in a return statement to the node containing the return type of the method. (E.g. x in return x gets an edge pointing to int in public static int getX(x).) LAST SCOPE USE Connects a node representing a variable to the node representing the last time this variable's name was used in the text of the code (i.e. capturing information about the text, not the control flow), but only within lexical scope. This edge exists to try and give the non-GSC models as much lexical information as possible to make them as comparable with the GSC model. LAST FIELD LEX Connects a field access (e.g.

this.whatever or Foo.whatever) node to the last use of this.whatever (or to the variable's initialization, if it's the first use). This is not lexical-scope aware (and, in fact, can't be in Java, in general).

FIELD:

Points each node representing a field access (e.g. this.whatever) to the node where that field was declared.

WORD USE:

Points cache nodes to nodes representing variables in which the vocab word was used in the variable's name.

:

We use the terminology that a name in source code is a sequence of words, split on CamelCase or snake case. E.g. the method name addItemToList is composed of the words add, item, to, and list. We also use the term variable in its slightly broader sense to refer to any user-named language construct, including function parameter, method, class, and field names, in addition to declared variable names.

This multigraph was referred to as a Program Graph inAllamanis et al. (2017) and is called an Augmented AST herein.

URL redacted to preserve review blind

URL redacted to preserve review blind

https://mvnrepository.com/

https://pmd.github.io/latest/pmd_userdocs_cpd.html

https://javaparser.org/

https://mxnet.apache.org/

Figures and Tables:

-The-Blank Readout function indicates e.g. the variable foo via attention over nodes Variable Naming Readout function unrolls RNN to produce e.g. ['add', 'foo']

Figure 1: Our model's procedure for consuming a single input instance of source code and producing an output for a supervised learning task.

Figure 2: Example of a model's procedure for completing the Fill-In-The-Blank task. Each Fill-In-The-Blank instance is created by replacing a single usage of a variable (n, in this example) with the special token <FILL-IN-THE-BLANK>. The model then processes the code as depicted in Figure1. To produce outputs, the model's readout function computes a soft-attention weighting over all nodes in the graph; the model's output is the variable at the node on which it places maximal attention. In this example, if the model put maximal attention weighting on any of the greenhighlighted variables, this would be a correct output. If maximal attention is placed on any other node, it would be an incorrect output. Only in-scope usages of a variable are counted as correct.

i = 0; i < <NAME-ME>; i++) { Object expected = Array.get(expected, i);

Figure3: Example of a model's procedure for completing the Variable Naming task. Each Variable Naming instance is created by replacing all uses of some variable (expectedLength, in this example) with a special <NAME-ME> token. The model then processes the code as depicted in Figure1. To produce outputs, the model takes the mean of the <NAME-ME> nodes' hidden states (depicted here in orange), uses them as the initial hidden state of a Recurrent Neural Network, and unrolls this RNN to produce a name as a sequence of words.

Nomenclature used in Experiments section. Each abbreviation describes a tweak/ablation to our full model as presented in Section 4. Using this nomenclature, our full model as described in Section 4 and shown in Figure1would be a "AugAST-GSC" model. In Step 4, name embeddings for nodes representing variables are produced by taking the mean of the embeddings of the words in the variable's name. Words outside this model's closed vocabulary are labeled as <UNK>. This is the strategy used in Allamanis et al. (2018). CharCNN Skips Step 3 in Section 4. Pointer Sentinel Follows Steps 3 and 4 as described in Section 4, except it doesn't add edges connecting cache nodes to the nodes where their word is used. In the Variable Naming task, this is equivalent to using the Pointer Sentinel Mixture Model of Merity et al. (2017) to produce outputs. GSC Follows Steps 3 and 4 as described in Section 4.

Table content: <table><tr><td/><td>Abbreviation</td><td>Meaning</td></tr><tr><td>Code Representation</td><td>AST AugAST</td><td>Skips Step 2 in Section 4. Performs Step 2 in Section 4.</td></tr><tr><td/><td>Closed Vocab</td><td>Skips Step 3 in Section 4, and instead maintains</td></tr><tr><td colspan="3">word-embedding vectors for words in a closed vo-Performs Step 5 in Section 4 using the Gated cabulary. Graph Neural Network Vocab Strategies GGNN Graph Neural Network of Li et al. (2016).</td></tr><tr><td/><td>DTNN</td><td>Performs Step 5 in Section 4 using the Deep Ten-</td></tr><tr><td/><td/><td>sor Neural Network of Schütt et al. (2017).</td></tr><tr><td/><td>RGCN</td><td>Performs Step 5 in Section 4 using the Relational</td></tr><tr><td/><td/><td>Graph Convolutional Network of Schlichtkrull</td></tr><tr><td/><td/><td>et al. (2017).</td></tr></table>

for explanations of the abbreviations. All models use Gated Graph Neural Networks as their GNN component. Accuracy (and top-5 accuracy) on the Fill-In-The-Blank task, depending on which type of GNN the model uses. See Table1for explanations of the abbreviations. All models use AugAST as their code representation.

Table content: <table><tr><td/><td/><td colspan="2">Closed Vocab CharCNN</td><td>GSC</td></tr><tr><td>Seen repos</td><td>AST AugAST</td><td>0.57 (0.83) 0.80 (0.90)</td><td colspan="2">0.60 (0.84) 0.89 (0.96) 0.90 (0.94) 0.97 (0.99)</td></tr><tr><td>Unseen repos</td><td>AST AugAST</td><td>0.36 (0.68) 0.59 (0.78)</td><td colspan="2">0.48 (0.80) 0.80 (0.93) 0.84 (0.92) 0.92 (0.96)</td></tr></table>

Accuracy on the Variable Naming task. Our model is the AugAST-GSC. The first number in each cell is the accuracy of the model, where we consider a correct output to be exact reproduction of the full name of the obfuscated variable (i.e. all the words in the name and then a EOS token). The second, parenthetical numbers are the top-5 accuracies, i.e. whether the correct full name was among the 5 most probable sequences output by the model. See Table1for explanations of the abbreviations. All models use Gated Graph Neural Networks as their GNN component.

Table content: <table><tr><td/><td/><td colspan="3">Closed Vocab CharCNN Pointer Sentinel</td><td>GSC</td></tr><tr><td>Seen repos</td><td>AST AugAST</td><td>0.23 (0.31) 0.19 (0.26)</td><td>0.22 (0.28) 0.20 (0.27)</td><td>0.19 (0.33) 0.26 (0.40)</td><td>0.49 (0.67) 0.53 (0.69)</td></tr><tr><td>Unseen repos</td><td>AST AugAST</td><td>0.05 (0.07) 0.04 (0.07)</td><td>0.06 (0.09) 0.06 (0.08)</td><td>0.06 (0.11) 0.08 (0.14)</td><td>0.38 (0.53) 0.41 (0.57)</td></tr></table>

Accuracy (and top-5 accuracy) on the Variable Naming task, depending on which type of GNN the model uses. See Table1for explanations of the abbreviations. All models use AugAST as their code representation.

Table content: <table><tr><td/><td>GGNN</td><td>DTNN</td><td>RGCN</td></tr><tr><td>Seen repos</td><td colspan="3">Closed Vocab 0.19 (0.26) 0.23 (0.31) 0.27 (0.34) GSC 0.53 (0.69) 0.33 (0.48) 0.46 (0.63)</td></tr><tr><td>Unseen repos</td><td colspan="3">Closed Vocab 0.04 (0.07) 0.06 (0.08) 0.06 (0.09) GSC 0.41 (0.57) 0.25 (0.40) 0.35 (0.49)</td></tr></table>

Peer review (iclr2019):
 (updated with some summaries from discussion over the initial review) The paper discusses the topics of predicting out-of-vocabulary tokens in programs abstract syntax trees. This could have application in code completion and more concretely two tasks are evaluated: - predicting a missing reference to a variable (called FillInTheBlank) - predicting a name of a variable (NameMe) Unfortunately, the paper proposes overly complex and strange formulations of these tasks, heavy implementation with unnecessary (non-motivated) neural architectures and as a result, does not demonstrate state-of-the-art performance or precision on comparable tasks. Figure 1 shows the complexity of the approach, with multiple steps of building a graph, introducing the vocabulary cache to then produce a vector at every node of the input tree of the program (instead of creating architecture for a given task), yet simple analysis over which variables can be chosen is missing. The FillInTheBlank task is badly defined already on the running example. The goal is to select a variable to fill in a blank and already in the example on Figure 2, one of the candidate variables is out of scope at the location to fill. The motivation for the proposed formulation with building a graph and then computing attention over nodes in that graph is unclear and experiments do not help it. For example, [1] (also cited in the paper) solves the same problem more cleanly by considering only the variables in the scope*. There is no good experimental comparison to that work, but it is unlikely it will perform worse. Also [1] does not suffer from vocabulary problems for that task. Summary discussion below: the experiments here are incomparable on many levels with prior works: different architecture details, different even smaller dataset than from [1]. There is a third-party claim that on a full system, the general idea improves performance, but I take it with a grain of salt as no clean experiment was yet done. The reviewer notes that the authors disagree the baselines are not meaningful. The NameMe tasks also shows the weakness of the proposed architectures. This work proposes to compute vectors at every node where a variable occurs and then to average them and decode the variable name to predict. In comparison, several prior works introduce one node per variable (not per occurrence), essentially removing the long distance relationships between occurrences of the same variable variables and removing the need to average vectors and enforcing the same name representation at every occurrence of the variable [name]. The setup here is incomparable to specialized naming prior works, one feature (a node per variable) is replaced with another (a node per subtoken), but for baselines authors choose to only to be similar to [1]. Also, while not on the same dataset, [2,3] consistently get higher accuracy on a related and more complicated task of predicting multiple names at the same time over multiple programming languages and with much simpler linear models. This is not surprising, because they propose simpler architectures better suited for the NameMe task. [1] Miltiadis Allamanis, Marc Brockschmidt, and Mahmoud Khademi. Learning to represent programs with graphs. ICLR 2017 [2] Veselin Raychev, Martin Vechev, and Andreas Krause. Predicting program properties from Big Code [3] Uri Alon, Meital Zilberstein, Omer Levy, Eran Yahav. A General Path-Based Representation for Predicting Program * corrected text