CodeTrek: Flexible Modeling of Code using an Extensible Relational Representation
Authors: Pardis Pashakhanloo
Aaditya Naik
Yuepeng Wang
Hanjun Dai
Petros Maniatis
Mayur Naik
Venue: ICLR 2022 Poster (2022)
Keywords: relational database
code representation
knowledge graph reasoning
program understanding

Abstract: Designing a suitable representation for code-reasoning tasks is challenging in aspects such as the kinds of program information to model, how to combine them, and how much context to consider. We propose CodeTrek, a deep learning approach that addresses these challenges by representing codebases as databases that conform to rich relational schemas. The relational representation not only allows CodeTrek to uniformly represent diverse kinds of program information, but also to leverage program-analysis queries to derive new semantic relations, which can be readily incorporated without further architectural engineering. CodeTrek embeds this relational representation using a set of walks that can traverse different relations in an unconstrained fashion, and incorporates all relevant attributes along the way. We evaluate CodeTrek on four diverse and challenging Python tasks: variable misuse, exception prediction, unused definition, and variable shadowing. CodeTrek achieves an accuracy of 91%, 63%, 98%, and 94% on these tasks respectively, and outperforms state-of-the-art neural models by 2-19% points.

Published as a conference paper at ICLR 2022
CODETREK: FLEXIBLE MODELING OF CODE USING AN EXTENSIBLE RELATIONAL REPRESENTATION
Pardis Pashakhanloo University of Pennsylvania
Aaditya Naik
Yuepeng Wang Simon Fraser University
University of Pennsylvania
Hanjun Dai Google Research
Petros Maniatis Google Research
Mayur Naik University of Pennsylvania
ABSTRACT
Designing suitable representation for code-reasoning tasks is challenging in aspects such as the kinds of program information to model, how to combine them, and how much context to consider. We propose CodeTrek, deep learning approach that addresses these challenges by representing codebases as databases that conform to rich relational schemas. The relational representation not only allows Code'Tre to uniformly represent diverse kinds of program information, but also to leverage program-analle analysis queries to derive new semantic relations, which can be readily incorporated without further architectural engineering. Code'Trek embeds this relational representation using set of walks that can traverse different relations in an unconstrained fashion, and incorporates all relevant attributes along the way. We evaluate CodeTrek on four diverse and challenging Python tasks: variable misuse, exception prediction, unused definition, and variable shadowing. CodeTTrek achieves an accuracy of 91 %, 63%, 98%, and 94% on these tasks respectively, and outperforms saate-of-the-ars art neural models by 2-19% points.
INTRODUCTION
Deep learning techniques are increasingly applied to code-reasoning tasks, including bug detection (Allamanis al. 2018). type inference (Hellendoorn et al., 2018). code summarization (Alon et al.) 2019b), program repair (Dinella et al. 2020), and code generation (Alon et al., 2020), among many others. The successful application these techniques to a given task depends heavily on the program representation that encompasses relevant program features and model architecture.
There are many crucial choices involved in designing a suitable representation for a new task. Consider the example in Figure which depicts instance of an axception-predictionn task (Kanade al. 2020), whose goal is to predict the exception type in the placeholder "[??]" in the highlighted statement. Predicting the correct type AssertionError from range of 20 pre-defined exception types in Python requires understanding the implementation of the check() function, which is defined in a different class (TestObject). Thus, the desirable context for the model goes beyond the immediate lexical neighborhood of the placeholder, possibly inside a chain of called functions.
The richness of information and extended scope inevitably imply that the relevant context may be very large. Models tackling such tasks are challenged to either reduce the scope of a task-e.g.. a single function, or few contiguous lines of code text-or heuristically sample from larger scope to produce small enough input to fit inside the memory of a GPU. For example, Transformers learn to reason about code from a sequence of tokens in the program; and GNNs with n layers a which, for pessaag-passing architectures, determines how much of the graph is reachable from some immediately adjacent context to the task example-pree prune nodes that are further than n graph hops away from the placeholder. However, distance is not always the determining factor in collecting relevant information. For instance, when trying to decide which exception type is applicable, it may be more important to follow control flow edges until they meet the raising of an exception than, say, fetching all adjacent statements without exception handling.
We outline two key design goals motivated by these considerations. First, observe that pro- gramming languages have well-defined semantics, which ensures that relevant information (module imports such as pickle, class inheritance, inter-procedural control flow and data flow, deeper analyses

---

Published as a conference paper at ICLR 2022
Input Python Program
Schema of Python Programs
(base relations)
Semmle Compller
TABLE
WARCHARID) PRIMARY NULL,
piddi
VARCHARIS) NOT NULL, FOREIGN REFERENCES scoper())
lippott piskie ded stanch (u
Relational Reprosentation
coluy
solf.z
TABLE
I
XISpI
VARCHARIS) PRIMARY KEY, (2RDHAR(128)
Eaze Belntions
Scspe
NOT NUIL
Scopi
log Py
21
20oept
Kind
CD
c
5oooe
Program Analysis Queries (derived relations)
+7
12
beet py 4-:1
VIEW [SI, Var AS
project
131:
Tee (itjeeo
FCT
module
Derived
FROM simt varv
dependinncy
check
appand)
[P1)
def
SDD
CHll
Coisel
WHERE KE exces/esgr (edelinessy) and geiSubFi)) =
VIEW Calor, Callee) AS
Example showing how CODETREK translates an exception-predicee sample in a Python program into a feature-rich representation that consists of base relations that capture the program's ' syntax and derived relations that capture semantic information computed by program analysis queries.
Figure I:
like def/use chains and object escape, etc.) can be extracted via a number of deterministic analyses. So, instead of learning this kind of information indirectly from labeled data, can make it directly available to the model. The model can thus focus on learning the information that can only be discovered from rich contexts. Second, even when rich information is easily accessible, making well-informed predictions in sode-reasoning tasks requires intelligent context collection to fit the needs of the task. So, instead of solely considering the model's technical constraints, must capture relevant context in a task-specific manner.
In this paper, we propose CODETREK, deep learning approach that realizes these goals. CODETREK leverages a declarative program analysis framework to produce a rich, easily extensible representation of context as a relational database, and biased graph-walk mechanism for pruning that context in a task-specific way before presenting it to a model based on Transformers and DeepSets (Zaheer) al. 2017). CODETREK builds upon Semmle (Avgustinov et al. 2016), which converts codebases in C, Java, Python, etc., into relational databases that capture the underlying structure and semantics of code, as well as a query language, CodeQL, for specifying program analyses compute new semantic information. CODETREK brings little modelling innovation the architecture is reminiscent of neural techniques for knowledge-graph reasoning (Das et al. 2018 (Perozzi et al., 2014). However, it is useful both as a relation generator and a task generator. As the former, it can harness existing and new analyses to add more inductive bias for hard tasks. As the latter, it can help benchmark neural techniques more challenging tasks, and generate auxiliary training objectives to pre-train unsupervised unde-underst models (Feng et al., 2020 Guo et al. 2020 Kanade et al.) 2020).
We evaluate CODETREK four diverse tasks real-world Python programs. They include two existing tasks, variable misuse and exception prediction, as well as two newer ones, unused definition and variable shadowing. The newer tasks are sophisticated CodeQL queries, written by program analysis experts, and enable testing the power of neural models: they both involve complex logical reasoning, and only 1.6% of the unused definition samples contain bugs, which is more in line with real-world settings. CODETREE achieves an accuracy of 1%, 63%. 98%, and 94% on these tasks respectively. which is 2- 199 points higher than sfate-of-the--ee GGNN, and Code2Seq. We also demonstrate the robustness of CODETREK in two out-of-distribue scenarios: real-world variable misuse samples from GutHubb and unused definition samples involving subtle code perturbations introduced using a systematic test- rest-generation framework, Skeletal Program Enumeration (Zhang et al., (017)) CODE COdeTREE REK achieves an accuracy of 57% and ROC-AUC of 78%, respectively in these scenarios, which is 6-11% points and 14-36% points higher than the basclines.
neural models CuBERT, GREAT,
In summary, this paper makes the following contributions:
1. We propose represent programs as relational databases that make rich context readily available for sode-reasoning tasks using deep learning.
2. We present graph-walk mechanism that prunes the unrelated context in task-specific manner.
3. We propose techniques to enable task designers to easily tailor and stress-test their models via program analysis queries, walk specifications, and systematic test-program generation.
2

---

Published as a conference paper at ICLR 2022
4. We identify two challenging tasks for neural code reasoning, unused definition and variable shadowing; although sophisticated, non-neurd static-analysis tools can solve them, these tasks pose useful litmus test for neural code-reasoning frameworks and demonstrate the ability of CODETREK to generate hard tasks that follow real-world program distributions with modest effort.
5. We extensively evaluate our approach and demonstrate that deeper relational information about code helps neural models outperform the state-of-the-art in terms of accuracy and robustness.
CODETREK is publicly available olttte////tthaacccoo/ssssssaallr
THE CODETREK FRAMEWORK
2.1 BACKGROUND
Inspired by the idea of storing codebases as databases, CODETREK represents a program as relational database. Specifically, CODETREK leverages the per-language schema defined by Semmle to uniformly store lexical, syntactic, and semantic program information as base relations in the database-we focus on Python in this paper, but the approach language-agnostic, as long as Semmle supports the language. Each relation contains information-2 in the form of tuples-about a particular kind of program element, such as expressions, statements, and so on. The columns of relation specify its attributes. For instance, in Figure tuple (s1, except, c1) in the stmt relation specifies that s1 an except statement contained in a scope with identifier c1, and tuple (s4, o) in the def relation specifies that variable o is defined in some statement with identifier s4, The schema also defines referential integrity constraints of the form R.A - S.B where A is called a foreign key of referencing relation R. and B is unique attribute (e.g. primary key) of referenced relation S. For example, in Figure I. we have stmt.Cl - scope.ID.
2.2 A BIRD'S-EYE VIEW OF CODETREK
Facilitated by CODETREK's 's uniform representation of programs, task developers can easily obtain new semantic information by writing program-analysin analysis queries CodeQL, an SQL-like language. The newly derived information is also in the form of derived relations, which maintains the uniformity of the relational representation. The derived information is stored in def, which, together with call, can bias the prediction of the best variable to replace placeholder. A task developer need not be machine-learning expert to bring in more semantic information about programs: All they need do is write CodeQL query. and the resulting derived information will be added to the existing richness of the program's 's available features CODETREK.
id: 53
id: c1 kinds Gal
kinds
Id: scepel bust py:3-10
kinds
600pe1 cI
ceat.py:130-122
acrpp, xtmie
strit
EVDY STITT
expr
stml
strit
a2 Callecd
Scope
kindi assert ecape:
horeer _all_ckk
scope: O2
Scope sim
simt
func
caller Lacii
call
callen func 1
func
Figure 2: A partial illustration of graph generated by CODETREK.
CODETREK translates a relational database to a graph whose nodes correspond to tuples, and whose edges follow referential integrity constraints. An example of such graph is illustrated in (Figure 2] where each node is depicted as circle along with its type (e.g., func) in white font. Orange and green nodes correspond tuples of base and derived relations, respectively. The attributes (e.g.. name, kind, etc.) of the node are shown in box at the corner of the node. For each referential integrity constraint R.A S.B, an edge type R.A.S.B defined, connecting the tuples of the two relations with the same value on the edge attributes R.A and S.B. For brevity of presentation in Fngiuure 2 when there is single such constraint between a pair of relations and S, we omit the attributes from the edge type. But we do not omit them when there are multiple such constraints, such as in the case between relations func and call, namely, call.caller + func.id and call.callee + func.id. This graph view of program semantics helps extract succinct context as input to model. Context extraction from the resulting CoDETREK graph is done via biased random walks of the graph, in a fashion specified by the task definition. The starting node-whiee we call anchor node- may be example-specift (e.g., the node containing the placeholder) or task-specific (e.g., all nodes holding a variable declaration). In Figure the node that represents tuple stmt(s1, except, w corresponds the statement on
3

---

Published as a conference paper at ICLR 2022
(N)
node types
(M)
node values
(V-1)
edge types
stmt
scope
func
call
except
tast.py
call chk
Scope strit func scope call func
call func
Bublokenize
nade vocabulary (E()
edge vocabulary (Eg)
test Py
chkk
summation
& ambed using Ev
positional
pastiional
positional
encoding
encodinng
encoding
concal
Transformer Encoder
(3N- 1)
(3)
Pooling
Figure 3: Embedding of the walk highlighted in Figure
line 137 in Figure (lefft) the anchor because the goal of the task is to predict a suitable exception type in the except statement. The walk generator traverses the graph by biasing traversal of edges according to each neighbor's node type. If no bias is specified, walks are simply fair random walks. Different probability mixes for different node types encourage the model to sample walks more relevant to a task. An example of such a walk is shown in Figure 2 usiig circles with thicker borders. This walk reaches the "assert" node which in fact determines the exception type that should be used in the except statement. For instance, to spend more time traversing longer-range dependencies in other functions, the developer higher probabilities to nodes of types stmt and expr. We could achieve improved accuracy for the tasks compared baselines by only modifying the probabilities of up to 4 types of nodes. Learning the walk specification given the task without human input is exciting future work.
assign higher value to call nodes. In our evaluation, assign
Finally, to convert random walks distributed representation. CODETREK embeds each walk (including the types and attributes of each node and edge in the walk) using Transformer encoder, and then produces an order-invariant representation of the set of walks using the Deep Set architec- ture (Zaheer et al. 2017). The resulting hidden representation can then be used by to make predictions for the particular rede-nnns task.
Random walks to embed a graph are perhaps regressive choice, compared to more modern solutions such as GNNs or relational Transformers. For instance, DeepWalk (Perozzi et al. 2014) uses random walks for rerbbbuteeddrepresenttttioo learning in a transductive setting, and Code2Seq (Alon et al.) 2019a) uses shortest paths between pairs of AST leaf nodes. We chose biased random walks for several reasons. First, this enables CODE REK to choose task-specific strategies to heuristically fetch relevant context for a task, rather than choosing to embed all tokens of a function or class in lexical order. Second, in contrast to GNNs, this enables CODETREK potentially follow much longer chains through the semantic graph than what would be possible in a message-passing GNN of tractable number of layers-this was, in fact, the motivation behind the model architectures by Hellendoorn et al. (2020). Finally, in contrast to other walk-based approaches such as Code2Seq and AnyCodeGen, which share some of our motivation, our graph structure has much richer connectivity and is larger. For instance, those approaches only consider paths ending at token beeennberiig leaf nodes, with only AST interior nodes in between, whereas CODETREE admits arbitrary paths through the graph. In our example, paths with more than two token nodes, e.g., the walk illustrated in FFiuure 2] using circles with thicker borders is admissible for CODETREK but not for Code2Seq. CODETREK builds upon the above techniques and extends to relational graphs, with different sampling strategies and neural architectures that would suit database representation better.
2.3 BUILDING BLOCKS OF CODETREK
We now describe briefly the building blocks of CODETREK, Pre- Tre-processing consists of two steps: (a) turning the codebase into a relational database (Code2Rel), using pre-existing set of analyses and the developer's ss own analyses, and (b) mapping the relational database to graph (Rel2Graph). Then, graph is processed into sets of graph walks to present to a model. Finally, we train using a cross-entropy loss to implement a particular task.
Codebases as Relational Databases. Code2Rel applies to the codebase the system's 's base program analysis queries, which make up the base relations, as well those provided by the developer, which
4

---

Published as a conference paper at ICLR 2022
form the derived relations. The result is database comprising of a number of named tuples for each relation type. For Python, we collect 95 base relations and 277 derived relations. although adding more derived relations is simply exercise in writing few lines of CodeQL. Optionally, this step can limit the resulting database to only those relations that are reachable (through query-to-query dependencies) from some program analyses marked required by the developer. Appendix D.1 provides further details.
Constructing Relational Graphs from Databases. Re12Graph interprets the relations produced by Code2Rel as a graph, as follows. Each named tuple is represented by a node with the values of the tuple attributes as its features. Edges are added between these nodes as described in (uusecttio 2.2 such that the edge type R.A.S.B is defined for each referential integrity constraint RLA- - S.B between nodes representing tuples of relations and S.
Representing Code as a Set of Walks. Given a code datahase that is converted to graph G via the above Re12Graph, procedure Graph2 Walks. Graph2Walks projects a code graph as produced by Re12Graph to a set of walks, according the task-specific walk specification (anchor node predicate, traversal bias, and target walk length). Graph2Walks samples from the distribution of such random walks, by repeatedly picking node satisfying the anchor predicate, and traversing up to a maximum number of neighbors, following the transition probabilities specified. The resulting walks are collected as token sequences of relation types of nodes, their attribute values, and the edge types traversed, in the order of traversal. Figure 3 row (1) shows such a walk representation corresponding to the walk highlighted in Figure 2]
propose to represent it by the embedding of set of walks W, via the
Appendix D.3 specifies Graph2Walks precisely.
Embedding the Set of Sampled Walks. Given a walk w = [no, CD. 12,, c1...... -2 of length
N steps consisting of N nodes and N - 1 edges, we produce an initial embedding X.,. E RRN (3 where d is the embedding dimension. It consists of three segments. The first N rows of the embedding tensor represents the N node types (relation names), using an embedding lookup in E,, E R where is the number of relations. The next N rows represent the attribute values of the N nodes; we subtokenize attribute values (using a Visized WordPiece vocabulary for attribute values), embed each subtoken using E, E RV xd and mean-pool the subtoken embeddings into each node's 's attribute embedding. The last segment represents the - edge types (recall that edge type is a tuple of two relation names and
attributes), using an embedding lookup in E, E R xd where is the number of referential-integrie constraints in the database. All three embedding matrices En, Ev,, E, are learnable parameters. Each individual part of the embedding tensor gets its own sinusoidal positional encoding (denoted as PE.,, E RR(3--1)x4) We use a Transformer encoder to (ransfommer(xx+PPE..
represent the embedding of walk w as e = pooling where after the last layer of Transformer we do mean-pooling over all 3NV - 1 elements of the walk, to obtain a d-dimensional e The steps for embedding of walk sampled from the graph in Figure is illustrated in Figure 3
: IR 11xx + Rd.
Training and Inference. An example consists of set of walks and a ground-truth label, (W, 9)- Given an unordered set of walk embeddings (cw wwew. we build classifier by using the construction MLP MLe(Seepeet(fee J wew)), where denotes the predicted label and we optimize for cross entropy loss. However, for a binary classification task, we can obtain a more interpretable model via exp MLP(e..) y Ewew o o (MLP(c.)), where a-)) is the sigmoid function, and aw = > w'EW exp MI This way, we can inspect the individual walks that contributed the most (i.e., the highest aw) to the positive or negative predictions, and see if that aligns with human reasoning. We refer to o as the walk score. We train using the Adam optimizer with 8 GPUs for distributed synchronized SGD training (see Appendix(A A for details).
EVALUATION
Tasks. We consider two main criteria in selecting tasks. The first is locality, which is determined by whether reasoning within function typically suffices, whether inter-procedural reasoning is required. The second is eeetaraaiviyywhettie be solved using declarative queries. For declarative tasks, we write queries in CodeQL (detailed in Appendix C); for non-declarative tasks, we rely on available datasets. We treat the following tasks:
the task can be stated as a logic problem that can
1. VARMISUSE. Given a function and a variable accessed in it, predict whether the variable is misused. We also consider variation of this task, VARMISUSE--FUN (Kanade et al. 2020), that
5

---

Published as a conference paper at ICLR 2022
Task
CODETREK
GGNN
Code2Seq
GREAT
CuBERT
VARMISUSE
0.91 1 0.003
0.69 0.004
0.82 - 0.002
0.89 1 0.003
VARMISUSE-FUX
0.70
0,54 0.004
0.52 + 0.005
0.89 = 0.003
0.84 = 0.003
EXCEPTION
0.003
0.28 0.02
0.30
0,44 = 0.008
0.42 = 0,008
EXCEPTION FUN
0.65 0.01
0.51 0.02
0.51
0.68 0.007
0.69 = 0.007
DEFUSE
0.98 0.002
0.76 0.07
0.84 0.05
0.76 = 0.01
DEFUSE-FUN *
0.91 + 0.005
0.77 0.07
0.66 -
0.82 = 0.007
0.71 + 0.01
VARSHADOW
0.94 + 0.007
0.71 + 0.01
0.70 + 0.01
0.93 0.008
0.91 + 0.008
Table I:
Accuracy results of CODETREK. Rows that are marked by * measured by ROC-AUC, and the rest are measured by accuracy. The best performance in each row is denoted in boldface.
takes only function and predicts whether all variables are used correctly in the function. Note that neither variation is declarative: given a well-formed program, no logic query can deterministically decide that a variable is misused, since that decision depends on the intended semantics.
2. EXCEPTION. Given module containing a masked exception type in an except clause, predict the most appropriate built-in exception type out of 20 choices. We also consider variation of this task, EXCEPTION-FUS (Kanade et al. 2020), that is similar to EXCEPTION but takes a single function scope. Although EXCEPTION needs inter- nnter-procedural reasoning, neither variation is declarative, since the choice of the appropriate exception type is subjective in Python.
3. DEFUSE. Given a function and a variable definition in its scope, predict whether the definition is used. We also consider a variation of this task, DEFUSE-FUM that takes a function as its input and predicts whether any definitions are unused. This task is especially interesting because the real-world distribution of programs that contain unused definitions is skewed. Both variations are declarative (see Appendix C.1) and require only intra- reasoning.
VARSHADOW. Given a module, predict whether any variable defined within a certain scope has the same name as a variable defined in an enclosing outer scope, thereby shadowing that latter variable. Similar to EXCEPTION, this task requires inter-procedural analysis order to reason over both local as well as global variables. It has declarative query (see Appendix
Benchmark. We use the ETH Py150 Open corpus consisting of 125K Python modules It is de-duplicated and redistributable subset of ETH 1y15( Specifically, for the non-declarative tasks, use the datasets released by Kanade et al. 2020). Since these are function-levw samples but the EXCEPTION task is module-level, we augment the function in each sample with the entire containing module for this task. For the declarative tasks, we use analyses written in CodeQL to annotate all functions (or modules, as applicable) in ETH py 150 Open. All datasets consist of real examples, except for VARMISUSE-FFN and VARMISUSE where variable misuses are synthetically introduced into real code. We collected number of apparent variable misuses from GitHub commits to test our models and baselines on realistic dataset. Dataset details are available in Appendix H
Baselines. To compare CODETREK's performance with tffte-of-the-at techniques, we select four baselines: we implement GGNN by bylAllamanis et al. (2018) and Code2Seq by Alon et al. (2019a), build classifiers on top of the GREAT encoder by Hellendoorn et al. (2020), and fine-tune the pre-trained Python model for CuBERT by Kanade et al. (2020), which is essentially the Transformer- based classifier implementation of BERT. For Code2Seq we use ASTs as base program structures as described by Alon et al. (201a). We sample leaffto-lleat paths from these ASTs. The number of paths we sample is the same as the number of walks we sample for training CODETREK models. For GGNN and GREAT, we compute the data flow, control flow, and lexical information described by Allamanis et al. (2018) and Hellendoorn et al. (2020), respectively, using Semmle CodeQL and augment program ASTs with those edges. We detail baseline hyperparameters in Appendix A and fine-grained information about the size of AST-based versus CODE TREK graphs in Appendix G.I
3.1 ACCURACY OF CODETREK
We evaluate the performance of CODETREK and the baseline techniques on all the tasks described in section 3] all presented as classification tasks. We perform 10-fold cross-validation and report the average of the metric that we use to measure the performance of each task. We use ROC-AUC as the metric for DEFUSE and FUFUSE-FUN tasks due to their unbalanced datasets, and accuracy for the
https://qithub. https///h////tttoooooooooooorrer hatpaarrtrndaaaatttsesssstet http://th.....ooooooo.oooeooooor
550_pppen
https://www. inf ethz. cttp.chhpyl550

---

Published as a conference paper at ICLR 2022
Task AARMISUSE-REAL
CODETREK
GGNN
Code2Seq
GREAT
CuBERT
0.57
0.51
0.50
0.49
0.46
DEFUSE-SPE:
0.78
0,53
0.63
0.41
0.47
Table 2: Robustness results of CODETREK.
remaining tasks. The results are reported in Table 1 In 5 out of 7 tasks, CODETREK outperforms
GGNN, Code2Seq, GREAT, and CuBERT by 2-19% points.
There are various reasons why CODETREK performs better than these approaches. First, declarative tasks such as DEFUSE-FUr (or DEFUSE) require complex reasoning about the interactions between program variables. For instance, one needs to reason about the uses and definitions of variables in a flow-sensitive manner to determine whether any unused definitions exist in a program. Consider the code snippet in Figure 4 The definition of the variable month line 2 is unused but that at line 3 is used in line 4. CODETREK gives a majority of the walks sampled using the definition at line a high score (around 0.99). indicating the existence of use of that definition. However, most of the walks sampled from the dcfinition of month at line 2 were given lower score, and so CODETREK determines that this definition is unused. We observe that both CuBERT and GREAT fail to distinguish between the definitions on lines 2 and 3, and so they predict both to be used.
Additionally, some tasks such as EXCEPTION require rea- soning beyond the boundaries of a single function to make informed predictions. Functions in the chain of function calls can be lexically far from each other, thus rendering the limited context size of CuBERT and GREAT insuffi- cient. We observe that GGNN fails in the presence of such long call chains on par with findings of Alon & Yahay (0021) CODETREK addresses this kind of mispredictions by readily using call graph relation to connect the chain of function calls. This enables CODETREK to traverse a long distance without the need consider other statements in the program that have no effect in raising some exception.
I. def get_month (self, t):
2. month, -
def validate (month):
return is s__valid (month)
5 return self.month
Figure 4: Example DEFUSE-FUN task.
However, CODETREK performs worse than CuBERT in EXCEPTION- FUN. This could be attributed to the fact that CuBERT is pre-trained around 7 million Python programs, and therefore is able to memorize tokens from several instances of try-except blocks, An example of a heuristic that it learns is that in presence of tokens such as request response in the context, it suggests catching HTTPError, which is usually the correct choice. However, its prediction is not robust against changes in the variable names. For instance, changing the names of a few nearby variables to request or response forces CuBERT to predict HTTPError regardless of the semantics. CODETREK on the other hand, does not rely on memorizing the tokens, but learns to assign high probabilities to walks that correctly traverse chain of function calls starting from the try blocks to locations in programs (or their libraries) where the exception is originally raised.
CODETREK also performs worse than GREAT in VARMISUSE-FUL FUN. This is because every node that corresponds to a variable is selected to be an anchor for this task. The total number of walks (500 in this task) is divided among these variables. However, there can be hundreds of variables in some programs, resulting in few walks generated for each variable in such cases, diminishing the ability of CODETREK learn sufficient information about each variable.
3.2 ROBUSTNESS OF CODETREK
We evaluate the robustness of CODETREK on additional test data that does not follow the distribution of the training data. This data includes two new datasets: one representing real-world bugs for the VARMISUSE-FUN task and the other consisting of programs mutated using a systematic test- generation framework for the DEFUSE-FUr task. The results are reported in Table 2]
Real-world bugs. We manually collect 199 real-world instances containing VARMISUSEE-FUN bug and their corrected counterparts (a total of 398 samples) from commits on GitHub and use them as testing data for the VARMISUSE-FUN task. We define a VARMISUSE- bug as the occurrence of a misused variable that is changed to another in-scope variable in the commit. We evaluate the baselines using this real-world set of bugs. CODETREK outperforms baselines in detecting wollworld variable misuse bugs (VARMISUSE (EALLL by achieving accuracy of 57% which is 6% points better than the second best result obtained by GGNN.
Mutated programs. There are several approaches to mutating existing datasets, including trans- forming existing data (Yang et al. (1922)) generating synthetic programs, and fuzzing. A representa-
7

---

Published as a conference paper at ICLR 2022
tive approach that has been used to systematically evaluate the robustness of compilers is Skeletal Program Enumeration (SPE), proposed by Zhang et al. (2017). SPE parameterizes each program by set of its variables, and replaces each variable name exhaustively with other in-scope variable names. We generate variations of the DEFUSE-FUN testing data using this technique, and evaluate this mutated dataset (DRFUSE-SPE)) CODETREK outperforms all baselines in
the baselines classifying these perturbed programs by achieving the ROC-AUC score of 78% which is 15% points better than the second best result obtained by Code2Seq.
The poor performance of the baselines can be explained by the fact that the code generated by SPE is occurs frequently in SPE-generated samples. Despite this, the inductive bias borne by rich relational information during training remains applicable and prevails over the unusual-looking token sequences, thus explaining CODETREK performance.
For example, the assignment a = a + unusual in real code, but
These results suggest that sampling walks can be a promising strategy for robustness. Interestingly, the runner-up in this study is (ile2Seq-another walk-based approach. We inspected the paths in both approaches to understand the reason behind the difference in performance of Code2Seq and CODETREK despite their similarities. We identified two reasons: 1) the kinds of program information that can be captured from an AST are limited compared to the program graph we propose, and 2) several walks that CODETREK prioritizes for this task cannot be embedded by Code2Seq.
3.3 EFFECTIVENESS ON BANGER-RANGE TASKS
We evaluate the effectiveness of CODETREK on tasks that require reasoning beyond function bound- aries. CODETREK achieves this ability by readily incorporating relations that capture inter- procepproceural or mnter-modular dependencies such as call graphs. To demonstrate this, we compare CODETRER performance on EXCEPTION with vs. without incorporating the call graph information at training time. CODETREK achieves an accuracy of 52% when call graph information is not provided, which increases to 63% after providing the call graph information between functions within a module.
To illustrate the kinds of mistakes that the baselines (and also CODETREK in the absence of call graph information) make, consider the representative example in Figure 5 snipped and simplified from the zipfile package. In this example, the model predicts the exception type that should be caught on line 11. However, to make an informed pre- diction, the model must consider the exceptions that may be raised when calling the ZipFile constructor (line 10). Hence, the definition of the constructor (line 2) must be taken into consideration. This constructor calls another function check compression in which a Notimplement- edError is raised on line 5. This chain of function dependence can be easily represented using call graph. Therefore, CODETREK, once provided with call graph, will eventually traverse the path that reaches this raise statement from the exception statement through the call graph edges.
class ZipFile:
2 def inii (...):
salf. www.chhockhhe
stheck_coppoossion...
det _ (...))
5 raise Not NoLImplementedB..c
4 ...000 lines of code...
7 clans restRipFile:
def teat (path):
9
try:
10
zf 7ipFi la (path)
11
except 172]:
12
log.wazning!) 1)
Figure 5: Example EXCEPTION task.
3.4 SENSITIVITY TO NUMBER OF SAMPLED WALKS
We evaluate the sensitivity of CODETREK at test time to the number of walks that are sampled from program graphs. All the models for the considered tasks are trained on 100 sampled walks per program. The results are reported in Figure 6 We observe that the accuracies of the models increase with the number of sampled walks. some tasks, such DEFUSE and VARMISUSE that involve local reasoning about one point in the program, reducing the number of walks from 100 to 50 reduces the accuracies of the models by a very small amount. On the other hand, for tasks that require reasoning about numerous points in the program (e.g., DEFUSE-FUN or reasoning globally (c.g., EXCEPTION) decreasing the number of sampled walks has a bigger impact on the accuracy.
3.5 IMPACT OF PROGRAM REPRESENTATION
To evaluate the impact of different code representations, train two models for each task using CODETREK's 's architecture: for one set of models, the walks are sampled from relational graphs whereas for the other set of models, the walks are sampled from ASTs. The performance results are reported in Table Notably, the models trained on walks sampled from relational graphs are about 3 3-35% points more accurate than models trained on walks sampled from ASTs.
8

---

Published as a conference paper at ICLR 2022
1.0
VarMisuse
Task
Relational
AST
0.9
Exception
VARMISUSE
0.91
0.63
ExcestionFun
VARMISUSE-FUN
0.70
0.55
0.8
DefUse
Peformance
DefUseFun
EXCEPTION
0.63
0.37
0.7
VarShadow
EXCEPTION-FUN
0.65
0.62
0.6
DEFUSE
0.98
0.63
DEFUSE-FUN 0.91
0.67
VARSHADOW
0.94
0.73
9.4
25
100
Table 3: Impact of Program Representa- tion on Accuracy. (Rows marked by * are evaluated by ROC-AUC score.)
Number of Sampled Waks
Figure 6: Sensitivity to the number of walks.
We also evaluate the usefulness of the ability to bias random walks in CODETREK. The accuracy results that reported in Table aare all trained biased random walks. Specifically, in all of the tasks, nodes with types stmt, expr, and variable are biased such that they are 5 times more likely to be traversed compared other kinds of neighboring nodes. In addition, in the EXCEPTION task, we decrease the bias assigned to nodes of type module to 0 to avoid traveling from one function to another through the module node they have in common. (See Appendix for more details about specification of the tasks.) This forces the walks to only go to other functions by taking call graph edges between them. We select one of the tasks, EXCEPTION-FUS to measure the accuracy in the absence of said biases. We re-train EXCEPTION-FUR using uniformly sampled walks and observe that the accuracy reduces from 65% to 58% as a result.
4 RELATED WORK
Learning to represent code. There is a rich literature using neural networks for code reasoning.
At the token sequence level, the Transformer and its variants (Hellendoorn et al. 2020 Dowdell &
Zhang 2020) have been widely used (Berabi et al. 222 Ahmad et al. 2020 Zügner al.
2021 Kim
it al. 2021 Wang et al., 2020). Their performance can be further boosted via pretraining (eng et al.
2020 Guo al. 2020 Kanade al. 2020 Wang al. 102 Peng et al. 2021: Liu et al. (020)
Others have proposed to represent programs with ASTs and additional semantic edges (Allamanis al. 2018 Brockschmiddt al. 2018) learned abstract relations (Johnson al., 2020), using GNN
or lcaf-to-leaf sequence embeddings (Alon et al. 2019a b). Our work enables adding much richer semantic information while reducing the dependency on syntax structures. Additionally, CODETREK can take advantage of program analysis queries on relational databases to eliminate the engineering burden of augmenting program graphs with additional semantic edges.
Graph representation learning. Our work on learning program representations via relational databases is closely related to inductive representation learning on graphs (Hamilton et al. 2017) with graph neural networks (GNNs) (Xu et al., 2018) or Transformers (Ying et al.) 2021). Although scalable GNNs via sampling (Chen et al.) [017]] /Zhou et al., 2020) have been proposed in the transductive setting, it is still challenging represent large database graphs with 100k nodes in this inductive setting (Clement et al. [202 Yang & Kuang |uang||02I], Techniques from transductive graph embedding based skip gram (Perozzi et al. [204]] Grover & Leskovec 2016) general knowledge graph embedding (Das et al. directly applicable for inductive setting. CODETREK achieves good balance between modeling for large codebases and efficiency.
et al.) 2018 Zheng et al. 2020) are scalable but not
Feature selection techniques. There are efforts in the data-mining literature to minimize human effort in feature augmentation and selection. Chepurko et al. (2020) discover joins that can improve the prediction accuracy for single data table whereas CODETREK operates on multiple tables.
CONCLUSIONS
We proposed CODETREK, a technique that represents programs as relational databases to make rich semantic information available to deep learning models for code-reasoning tasks. We also introduced flexible walk-based based mechanism to sample relevant contexts from large graphs which are constructed from relational databases. We evaluated CODETREK on a variety of real-world tasks and datasets, and showed that it outperforms sfate-of-the-ar neural models.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
We thank the anonymous reviewers, David Bieber, Rishabh Singh, Charles Sutton, and Daniel Tarlow for their valuable feedback. This research was supported by grants from ONR 1-000014-88--200- and NSF (#2107429 and #1 #1836936).
REFERENCES
Wasi Uddin Ahmad, Saikat Chakraborty, Baishakhi Ray, and Kai-Wei Chang. A transformer-based approach for source code summarization. arXiv preprint arXiv:200S. 2020.
Miltiadis Allamanis, Mare Brockschmidt, and Mahmoud Khademi. Learning represent programs with graphs. In International Conference on Learning Representations (ICLR). OpenReview.net, 2018.
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations (ICLR). OpenReview.net, 2021.
Uri Alon, Shaked Brody, Omer Levy, and Eran Yahav. code2seq: Generating sequences from structured representations of code. In International Conference Learning Representations (ICLR). OpenReview.net, 2019a.
Uri Alon, Meital Zilberstein, Omer Levy, and Eran Yahav, code2vec: Learning distributed rep- resentations of code. Proceedings of the ACM on Programming Languages, 3(POPL):1-29, 2019b.
Uri Alon, Roy Sadaka, Omer Levy, and Eran Yahav. Structural language models of code. In International Conference on Machine Learning, pp. 256. PMLR, 2020.
Pavel Avgustinov, Oege de Moor, Michael Peyton Jones, and Max Schäfer. QL: object-oriented queries on relational data. In Shriram Krishnamurthi and Benjamin Lerner (eds.), European Conference on Pobject-Orientie Programming (ECOOP), volume 56 of L/Plcs, pp- 2:1-2:25. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2016.
Berkay Berabi, Jingxuan He, Veselin Raychev, and Martin Vechev. Tfx:: Learning to fix coding errors with a text-to-text transformer. In International Conference on Machine Learning, pp. 780-791. PMLR, 2021.
Mare Brockschmidt, Miltiadis Allamanis, Alexander L Gaunt, and Oleksandr Polozov. Generative code modeling with graphs. arXiv preprint
2018
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. arXiv preprint 1rXiv:1710.10560 2017.
Nadiia Chepurko, Ryan Marcus, Emanuel Zgraggen, Raul Castro Fernandez, Tim Kraska, and David Karger. Arda: Automatic relational data augmentation for machine learning. arXiv preprint arXiv:2003.09758, 2020.
Colin B Clement, Shuai Lu, Xiaoyu Liu, Michele Tufano, Dawn Drain, Nan Duan, Neel Sundaresan, and Alexey Svyatkovskiy, Long-range modeling source code files with ewash: Extended window access by syntax hierarchy. arXiv preprint
2021.
Rajarshi Das. Shehzaad Dhuliawala, Manzil Zabeer, Luke Vilnis, Ishan Durugkar, Akshay Krishna- murthy, Alex Smola, and Andrew McCallum. Go for walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning. arXiv preprint arXiv: 1.1.05.7, 2017.
Rajarshi Das, Shehzaad Dhuliawala, Manzil Zaheer, Luke Vilnis, Ishan Durugkar, Akshay Krishna- murthy, Alex Smola, and Andrew McCallum. Go for walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning. In International Conference on Learning Representations, 2018
10

---

Published as a conference paper at ICLR 2022
Elizabeth Dinella, Hanjun Dai, Ziyang Li, Mayur Naik, Le Song, and Ke Wang. Hoppity: Learning graph transformations to detect and fix bugs in programs. In International Conference on Learning Representations (ICLR). OvenReview.net, 2020.
Thomas Dowdell and Hongyu Zhang. Language modelling for source code with transformer-xi. arXiv preprini arXiv:2007. 150007 2020.
Zhangyin Feng, Daya Guo, Duyu Tang, Nan Duan, Xiaocheng Feng, Ming Gong, Linjun Shou, Bing Qin, Ting Liu, Daxin Jiang, et al. Codebert: A pre-trained model for programming and natural languages. arXiv preprint arXiv:2002.08115. 2020.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp- 865-864, 2016.
Daya Guo, Shuo Ren, Shuai Lu, Zhangyin Feng, Duyu Tang, Shujie Liu, Long Zhou, Nan Duan, Alexey Svyatkovskiy, Shengyu Fu, et al. Graphcodebert: Pre-training code representations with data flow. arXiv preprint arXiv:2009.08360 2020.
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 1025-1035, 2017.
William L Hamilton, Payal Bajaj, Marinka Zitnik, Dan Jurafsky, and Jure Leskovec. Embedding logical queries on knowledge graphs. arXiv preprint 1rXiv:1806.014 2018.
Vincent J. Hellendoorn, Christian Bird, Earl T. Barr, and Miltiadis Allamanis. Deep learning type inference. In Proceedings of the ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE), 2018.
Vincent J. Hellendoorn, Charles Sutton, Rishabh Singh, Petros Maniatis, and David Bieber. Global relational models of source code. International Conference on Learning Representations (ICLR). OpenReview.net, 2020.
Daniel D Johnson, Hugo Larochelle, and Daniel Tarlow. Learning graph structure with finite-state automaton layer. arXiv preprint arXiv:2007. 04999,, 2020.
Aditya Kanade, Petros Maniatis, Gogul Balakrishnan, and Kensen Shi. Learning and evaluating contextual embedding of source code. In Proceedings of the International Conference on Machine Learning (ICML), volume 119 of Proceedings of Machine Learning Research, pp. 5110-5121. PMLR, 2020.
Seohyun Kim, Jinman Zhao, Yuchi Tian, and Satish Chandra. Code prediction by feeding trees to transformers. In 2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE), pp. 162-162. IEEE, 2021.
Fang Liu, Ge Li, Yunfei Zhao, and Zhi Jin. Multi-task learning based pre-trained language model for code completion. In Proceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering, pp. 473 485, 2020.
Dinglan Peng, Shuxin Zheng, Yatao Li, Guolin Ke, Di He, and Tin-Yan Liu. How could neural networks understand programs? arXiv preprint arXiv:2105.0422 2021.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710, 2014.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
Wenhua Wang, Yuqun Zhang, Zhengran Zeng, and Guandong Xu. trans?: A mansformer-based framework for unifying code summarization and code search. arXiv preprint arXiv:2003.032300 2020.
11

---

Published as a conference paper at ICLR 2022
Xin Wang, Yasheng Wang. Pingyi Zhou, Meng Xiao, Yadao Wang, Li Li, Xiao Liu, Hao Wu, Jin Liu, and Xin Jiang. Clsebert: Contrastive learning for syntax enhanced code pre-trained model. arXiv preprint arXiv:2108.0453 2021.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? arXiv preprint 1rX.v:1810.00826, 2018.
Hao Yang and Li Kuang. Come: Code completion with memory mechanism and copy mechanism. In Evaluation and Assessment Software Engineering, pp. 129-138, 2021.
Wuu Yang, Susan Horwitz, and Thomas Reps. A program integration algorithm that accommo- dates semantics- prreeerriinseeeeeinngggn transformations. ACM Transactions on Software Engineering and Methodology (TOSEM), 133):10-334, 1992.
Chengxuan Ying, Tianle Cai. Shengjie Luo. Shuxin Zheng, Guolin Ke. Di He, Yanming Shen, and Tin Liu. Do transformers really perform bad for graph representation? arXiv preprint MrXiv:2106.0523: 2021.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan Salakhutdinov, and Alexander Smola. Deep sets. arXiv preprint arXiv: (eXivv/703.061 14, 2017.
Qirum Zhang, Chengnian Sun, and Zhendong Su. Skeletal program enumeration for rigorous compiler testing. In Proceedings of the ACM SIGPLAN Conference Programming Language Design and Implementation (PLDI), pp. 347-361. ACM, 2017.
Da Zheng, Xiang Song, Chao Ma, Zeyuan Tan, Zihao Ye, Jin Dong, Hao Xiong, Zheng Zhang, and George Karypis. Dgl-ke: Training knowledge graph embeddings at scale. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 739-748, 2020.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changeheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. Al Open, 1:57-81, 81, 2020.
Daniel Züigner, Tobias Kirschstein, Michele Catasta, Jure Leskovec, and Stephan Günnemann. Language-agnostic representation learning of source code from structure and context. arXiv preprint arXiv:2103.11318, 2021.
12

---

Published as a conference paper at ICLR 2022
A TRAINING PARAMETERS AND HYPERPARAMETERS
In this section, we describe details on parameters and hyperparameters we used.
Coek We train CODETREK models with learning rate of 10-1, 4 transformer layers, an embedding size of 256, 8 attention heads, and 512 hidden units. We sample 100 walks with lengths of up to 24 in each graph for every task, except for the VARMISUSE-- FUN task for which sample 500 such walks per graph. The reason is that the anchors we select for VARMISUSE- task are all the variables in the given program which can be well over 100 variables. So, increase the total number of walks to include more random walks starting from each variable.
We fine-tune the CuBERT pre-trained model that is provided by Kanade et al. (2020) with learning rate of 10-1, 4 transformer layers, and 512 hidden units. We use the checkpoint that is pre-trained on examples of size 512 tokens.
CuBERT
GREAT We train GREAT models with learning rate of 10-4, transformer layers, 8 attention heads and 512 hidden units. The example size in 512 tokens.
Code2Seq We train Code2Seq models with learning rate of 10-3, layers, 512 hidden units, and embedding size of 256. We sample 100 paths in each AST.
GGNN We train GGNN models with learning rate of 10-4, 5 layers, latent dimension of size 128, and a message dimension of size 128.
B MORE EXPERIMENNTS
Increasing the Number of Layers in Baselines We repeat the experiments that are reported in
Table 1 for GREAT and GNN with 10 layers. We report the results in Table 4
Task VARMISUSE
GNN
GREAT
0.72
0.84
VARMISUSE-FUN
0.58
0.86
EXCEPTION
0.30
0.45
EXCEPTION-FUN
0.53
0.68
DEFUSE*
0.78
0.87
DEFUSE-FUR
0.77
0.84
VARSHADOW
0.74
0.94
Table 4: The performance of GNN and GREAT with 10 layers.
Ablation Study We measure the contribution of the positional encoding which is used in embedding walks, the contribution of derived relations in improving the accuracy, and the effect of the biases assigned to node types. We report the results in Table Every row in this table shows different configuration indicated by 1-4.
We train model for the EXCEPTION task using the Positional Encoding in embedding the components of each walk, the call relation that shows the relationships between functions and their callers, and the biases which are assigned nodes of type stmt, expr". and variable (Config 1). This setting is similar to that of Table iin the paper. With this setting, CODETREK achieves an accuracy of 63. 03.83% on the EXCEPTION task. If remove the Positional Encoding (Config 2), we see small drop of 1.77% points in the accuracy. The effect of further removing the biases (Config 3) is much higher: CODETREK 's accuracy drops 6.3% points from 62.06% to 55.76% points. This aligns with our intuition that adding biases to the aforementioned node types results in generating walks that are more relevant to the task. Finally, we obtain the largest drop in the accuracy by further removing the derived call relation (Config 4). This component contributes significant amount of 10.57% points to the accuracy of the task, and it obtains a low accuracy of 45.19% points in absence all three components.
13

---

Published as a conference paper at ICLR 2022
Config #
Positional Encoding
Derived Relations
Biases
Accuracy (%)
63.83
62.06
3
x
55.76
X
X
45.19
Table 5: Contribution of different factors to the accuracy of EXCEPTION task.
# Steps
4
18
24
30
Accuracy
0.41
0.49
0.60
0.63
0.64
0.65
Table 6: Sensitivity the length of walks.
Different Pooling Mechanisms. We examine the effect of mean pooling versus attention pool- ing on the performance of CODETREK models. Attention pooling increases the accuracy of the EXCEPTION task from 63.83% 66.43%.
Different Positional Encoding Techniques. We also explore different positional encoding options. The current setting CODETREK gives an accuracy of 63.83% in the EXCEPTION task. Substituting the sinusoidal positional encoding with a learned one improves the accuracy less than 1 % points. This result in line with findings of Vaswani et al. (2017). which report nearly identical results using both positional encoding techniques.
Sensitivity to the Length of Walks To measure the sensitivity of CODETREK to the length (i.e., number of steps) of walks, we train number of models for the EXCEPTION task with walks of length 4-30 steps. We report accuracy changes in Table 6 Longer walks tend to improve accuracy. Walks that are too short (4 hops) result in models with low accuracy (42% and 51%, respectively) because they not able to capture enough information to make predictions. There is, however, a point when enough context captured (e.g., hop walks) and longer walks do not improve performance significantly.
C CODEQL QUERIES USED FOR LABELING
In this section, present the CodeQL queries that used label the examples for newly added tasks. Both queries are adapted from CodeQL's query repository at https: htttps:/giithub.oo rithub/codeq]
C.I DEFUSE-FUN QUERY
Import pythos
2 Import Definition
predicate uncaed_ local (Name unused, Localvariabs v) Forex (Detinition deč deI.getNode unused def. VetVariibble 7 and def, sert.attussed not exisis geLA. and not exists waw.ooaaiiooo.itotttosssoaaoooga (v))
def.isRalevane
11 and not v any (Nonlocal -.getaarrablll
and not exisis (deS. ().ge(aa))eel)ee (i gelPaarentNode(
(BunctionDeE) wewtDefinedPuneeiio.. (egeriinnntggeteeeeeesteee ())
14
and not teifs getNode () w.g.eParennNode (1. (ClaseDef) www.teeineddlassset....... .etADeecraater ())
16
18
private AnnAssiga ionotatioo_wille wwt.:wwthhhhtssteeeeeeeeeeeeeeee aesignmmtt (LocalVeriable v)
tesult.getlarget getAAStozee and not axista testltttosultt
from unused, Tocal Variabla
14

---

Published as a conference paper at ICLR 2022
26 unused_las lacal (unused, and
forall (Name el unssed.-ectTarenttooee (Tuple), (eoppee.geettee getAnnE1 () unused_local (el, _
select unused, v.getId!)
C.2 VARSHADOWW QUERY
import pythor
Import semm hew.ee..ppp..eeeee..ee. typea. Builtins
predicate optintiingg_praaaae pan_paaaetterr (Parameter p1
exists (string name, glob p.getDefault glob
glob.getId() name
p.asName ggezid()
name
11 predicate shadowa (ttme d, Globa IVariable 9, Punction scope, int Line) S-getScope() scope. getScope 13 and d. getecope scope exists flcaalarribll 15 d.defines (1) and
16 1.getIa() g.getId())
18 and not exists (Inport 11, Import ig, Name qd defines))))))
cl.contains
20
and ig. agg.contaiasighe (gd)
and not axi (Assign
a.getATarget
and gee () g.gettnnccoesaa) and not exists :bb::::i::::iiiliinnng.::::: and Legetoottion gegttttttintt line
25 and exista (Nane defa | defn,defines Ig)
not exists (If i.isNNameiqtain
i.contains (dafr)))
and not opt pargpparrmtt
Actründe crrest_fixtur__tee
22
exists (NoduleValue pytes:
result.gettbjeee wtw.eetttetettttteeeeeeeeeeeeeee ("Eixture") pooplce))))oottseeppttssse
34
Value exists [CallNede call
{
27
sall.get//mmesion/ pytest_ffxtture fixturf.ueeeeee fixtu_e__tttttxt attr()
coll.getFunation))) (CallNoda) ggtFuncctinn() Fittos__ixturr_attttr
29
call.pointsle (zess))
41
predicate assigned_oytett_Eiituee (GlobalVeriable exists (NameNode def daf daf.defiresite and def, (nefinitionkode) get () pointato (pytest__ fixture
46
48
predicate btzst_ehadowing_deeiie cetninddeeiiiiiiiiieiiii (Name d, @lobelVariable g). scistslins first, Scope
shadowa (d, 3. scape, first]
first mnn shadows 9, acope, Line)
53
55
from Name 4, GlobelVariable g, Name def
where
first_shsdon socdoowing__dee definitioond, gl
exists 60 and def.defines ig)
n.deletes (g))
and not Besiigee__yteet__ftttree and not g.getId() "
select d, g.getid(), def
15

---

Published as a conference paper at ICLR 2022
D CODEBASES AS DATABASES
D.1 TRANSLATING CODE TO RELATIONAL, DATABASE
CODETREK views program information relations. ?? shows the number of relations in three common programming languages. There is a directed acyelic graph F that represents the dependencies between these relations. For example, in F Python represents the dependencies between 95 base relations plus 277 derived relations.
Example D.I. A certain Python However, in Pythen. depends on derived relation D, which in turn depends on base relations {B, C}. Therefore, Code2Rel computes all five relations: A, B, C, D, E in order.
task requires base relations {A, B} and derived relation {E}.
Algorithm (Code2Rel) Given program P. set of base relation names RB, and set of derived relation names RQ. construct and return database D. Note that the term node in this algorithm refers nodes the relation dependency graph, not nodes in the program graph (e.g., Algorithm that the model will see.
1. Initialize D the set of all base relations in R3 by translating program P.
2. Let Rg be the set of relation names reachable from Rę in relation dependency graph F:
(a) Rq S Rs
(b) i E Rs and r' Edges(E)) then r' Rss
3. Let F be the sub-graph of induced by set of nodes Rss:
(a) Nodes(F)) F)) = Rs
(b) Edges(Fi F) = { r' E Edges( (F) r, rr,' Nodes F)
4. Compute a topological ordering [f Nodess())) of
For each r in L in order:
Evaluate the query for computing relation r on datahase and add the result to D.
D.2 TRANSLATING RELATIONS TO GRAPII
Algorithm (Rel2Graph) Given database D, construct program graph
Construct an undirected and labeled graph G follows:
(a) Nodes(G)) D
(b) Add Edges(G) each (11, 12, that satisfies the following conditions:
i. R. [aIa.....a. - S. ..., bR] referential integrity constraint in the schema of database D
ii. t is tuple of relation named R in D
iil. l2 is a tuple of relation named 5 in D
iv. for all [1..A] t1.a, = b2.b,
D.3 TRANSLATING GRAPH TO A SET OF WALKS
Definition D.I (Walk specification). A walk specification S = (C, B, min, max) is a tuple in which C is conditional expression that filters walk anchors from the set of nodes Nodes(G). B a map of bias values that correspond to each relation name, and min, max E R specify the minimum and maximum length of the walks generated by the specification.
Example D.2. An example of walk specification is as follows.
C {t]t E Nodes(G) A f E expr A t.kind = name) B {stmt: expr 5)
mün = 3, max = 16
16

---

Published as a conference paper at ICLR 2022
Algorithm 3 (Graph2Walks) Given program graph G, walk specification S (C, B, min, max), and the number of walks w, sample a set of walks W.
1. Initialize the set of walks W =
Compute the set anchors A = {tlt E Nodes(G) A conforms to S.C).
While | - wt
(a) Pick a random tuple teurr from A.
(b) Construct walk by repeating the following steps between S.min and S.max times:
i. Set (prev == leurr-
ii. Set leurr ao E Neighbors(G, (prev) with prob. proportionate to S.B(type (1prevs ceurr 1) GG)
iii. Let eeurr =
If Ccurr walk then extend walk by Ceurr- Otherwise set teurr = Eprev-
(c) If walk & then add W.
D.4 BRINGING ALL THE PIECES TOGETHER
Definition D.2 (Task specification). A task specification T = (Rg, Ro: S,n) is tuple in which Rg is set of base relation names, Ro is set of derived relation names, S is walk specification as described in Definition D.I and is the number of walks be generated.
Algorithm (Code2Walks) Given a program P and a task specification T = (R RQ. S,n.. generate of walks W.
1. D Code2Rel P, P, R.RB, T.RQ)
2. G Rel2Graph(D)
3. W Graph2Walls(C.T..S,T
E TASK SPECIFICATIONS
Using the notations defined in Appendix D we describe the specifications of each task that we used for evaluating CODETREK, In the following specifications, ellipsis (...) indicate the rest of the universe of base relations as designed in Semmle framework.
T TvARMISUSE FUN
Rg stmt, expr, variable, ssa-defn, ssa-use, successor, }..)
RQ = (}
S
C (t I Nodes(G) At expr i.Kind name),
B = {stmt 5, expr 5, variable 5}.
min 4, mar 16
}.
500
}
T TEXCEPTION.FUT FUN
RB = (stmt, expr, variable, ssa-defn, ssa-use, successor, ...}
RQ ()
S
C {t I Nodes(G) At stmt t.Kind except t.Type HoleException);
B = {stmt: 5, expr 5, variable : 5).
min 4, mar 16
17

---

Published as a conference paper at ICLR 2022
}: 7 = 100
T EXCEPTION = {
Rg = stmt,, expr, variable, ssa-defn, ssa-use, successor, ...},
RQ² (call-graph,,
S
C {1 L Nodes(G) A E stmt A t.Kind = except L.Tupe HoleException);
B {stmt 5, expr : module 0},
min 10, mar = 24
J.
n = 100
}
DEEUUSI-FUN = {
RB (stmt, expr, variable, ssa-defn, ssa-use, successor, ...),
RQ= (vaiiable-eess, local-variables),
S
C = { Nodes(G) E expr L.Kind = name AI.Collerl E (write, param)}
B (stmt 5, expr: : variable : 5),
min 4, mar = 16
J.
n 100
}
TDEFUSE and T VARMISUSE are defined similar to TDEEUSE and TyARMisusE respectively. However, in both DEPUSE and T VARMUSUSE their C has additional restriction Llocalion user selection. Also, TVRRISUSE is evaluated with n = 100.
T TARRSADOw
RB stmt, expr, variable, ssa-defn, ssa-use, successor, ...), RQ { caal-graph),
S
C (t i Nodes(G) At A t.Kind name L.is_global True),
B = {stmt 5, expr 5, variable : 5}.
min 4, mar 16
}.
100
}
F WALK FORMAT
We describe the format of walk as the model views before encoding using an example. Each walk consists of three lists for node types, node values, and edges.
"anchor": "py_stmts (415098, 6, 415072,
"trajectory";
["py_stmts", "py_scopes" "py Foy_Fuuntions", ipy_scopes", pyy_stmt"" "py_exprs", "py_expra", "py_scopes", "py_exprs", "py_variables", "v_8"],
18

---

Published as a conference paper at ICLR 2022
"node values": [["ExceptStmt")] ""
("pipe", "line"], "", " ("Assign"), ["Call"], ("Attribute"),
["Name"], ""metr","ic")"
"edgee redgess: ["dey__scoees.nndeee___eettt id)
The node, values can consist of the value of any attribute of node. For instance, ExceptStmt above the kind of the node with type py stmts, and pipeline is the name of the function that corresponds the function which is illustrated by node with type Fy_Functions. The values that identifiers, function names, etc. are subtokenized using a subword tokenizer (the tensor2tensor package). For instance, pipeline will break into [pipe,line]. Therefore, each value is encoded using the corresponding vector in the subword dictionary. If the relation name of a tuple is variable, we assign an id to it to be able distinguish between different variables. So, the type of variable node is determined by id (e.g., v_
G ADDITIONAL INFORMATION ABOUT GRAPHS
G.1 GRAPH SIZRS
Relational
EXCEPTION- FUN
EXCEPTION
VARSHADOW
VARMISUSE- DEFUSE-FUR
average
5,278
802,231
62,863
1,482
1,829
std
31,550
504,758
93,248
14,623
27,503
min
55
585
53
130
139
492,970
4,422,586
1,285,178
483,499
612,343
Table 7: Number of tuples (i.e., nodes) across relations of each file in the dataset used for each task.
AST
EXCEPTION-FIIE
EXCEPTION
VARSHADOW
VARMISUSH- FUN
DEFUSE- FUN
average std min 13,035
176
3,202
667
93
177
244
4,117
1432
126
268
20
20
10
10
max
36,808
36,786
30,729
5,243
Table 8: Number of AST nodes for each file the dataset used for each task.
G.2 EDGES IN BASELINE GRAPHS
GGNN Graphs. The edges that are represented to GGNN models are borrowed from Allamanis et al. 2018). They include
1. AST edges
2. NextToken edges
3. Lasteal//swiieeCmmmmeeee/////lla edges among variable accesses
19

---

Published as a conference paper at ICLR 2022
4. GuurdelByyGuurrdddyyeeeeeee edges between variables used in branches and their corre- sponding conditional expressions
5. ReturnsTo edges from the return statement to the method declaration, and
6. FormalArgNamt edges between method call arguments and their corresponding formal parameters.
GREAT Graphs. For GREAT models, similar to Hellendoorn et al. (2020). we borrow the edge types from Allamanis et al. 2018) and augment them with function calls.
H DATASET SIZES
The number of samples in each dataset is shown in Table The VARSIIADOW dataset consists of 49% samples with positive labels. The DEFUSE- FUN dataset more skewed, with 15% positive labels, while the DSFUSE dataset has 1.6% positive labels.
Task VARMISUSE
Training
Validation
# Testing
Avg. LoC (<max)
700,683
75,468
378,401
(3(25))
VARMISUSE-FUN
700,683
75,468
378,401
13 (<235)
EXCEPTION
18,456
2,086
10,334
528 (<7,624)
EXCEPTION-FUN
18,456
2,086
10,334
32 (<1,835)
DEFUSE
217,591
52,598
104,111
12 (<528)
DEFUSE-FUN
33,182
8,149
16,296
12 (<528)
VARSHADOW
70,183
21,794
39,845
149 (<27,228)
Table The number of samples used for training, validation, and testing and the lines of code that they contain. Lines of code (LoC) is reported as the average lines of code across samples in each dataset after removing the highest 0.1% % and lowest 0. % of the data.
I QUALITATIVE STUDY
We qualitatively discuss few examples on specific code snippets and describe the walks that contribute the most to the predictions made by the respective CODETREK TREK models. In each example, we explain how relations and the semantic edges between them enable CODETREK'S 's models to predict accurately.
I.1 EXAMPLE 1 (DEFUSE)
def write_randoo_tee ftctcsstt___ffllllee file
no zandom, 3 with open ("randon, txt " *w*) as sile: file. (str
raturn no
de write (aitterraddo(()
random_no ractte_rranonooooooooo ()
print
was written randon. Lxt
Figure 7: sample code snippet for DRFUSE.
id: 5051
5051 cbe: write
id: 4249 name:
kinds name
parent:
parent: 5320
expr
expt
access
ver
SSa-van
552 USe
Figure 8: The most important walk in simple instance of DEFUSE.
20

---

Published as a conference paper at ICLR 2022
Id: 4254 kinds parent: 4360
ex: 1300
id: 1252
var! 4252
name: file
id: 1318
4309
5520
vart 4252
svar: 4318
expr 822895
access
9C0e69 VSI
ver
5sa-ver var
553 var
5se-Use var-var
553 950-USC
Figure 9: The most important walk in a challenging instance of DEFUSE.
To understand how CODETREK uses semantic relations to determine whether a defined variable used, consider the code snippet listed in Figure In this snippet, the local variable file is defined on line 3, and then used on line 4. Intuitively, one would start from the variable definition and follow the code find access of it to prove that it is indeed used variable. More specifically, programmer which variable file is defined. She then tries to find another access to this variable that reads it, such as line 4.
starts with the expression on line
CODETREK determines that the walk illustrated in Figure 8 has the highest score among set of randomly generated walks. Interestingly, this walk shows similar behavior to that of programmer: starts at the anchor node (an expr node corresponding to the variable definition) which corresponds the expression that defines file. Then, it traverses the graph towards node that corresponds to use of this variable (a ssa-use node corresponding to the variable use).
construct_ file haadie (): file = tandller.inittalian def Saack_
file.id MIN_H:
return False
True
file = ianddeer.iittaalzee)
raturn Handler.dafeule:
Figure 10: A challenging code snippet for DEFUSE.
Even the models that do not embed semantic edges (e.g., CuBERT) are able to correctly predict that file is used, in such simple cases. However, in more complicated cases, such as the code snippet listed in Figure 10, semantic edges are needed to be able to distinguish between different definitions of variable file and to not confuse various uses of them. In this snippet. file is defined line 2, and then on line 7. The file defined on lines and are never used. To make matters more complicated, there function handle that is defined inside the top-level function construct _file handle. This function takes an argument which is named file and uses it on line 4.
In the absence of edges that make the relationship between is challenging for a model to determine that the variable named file on line 2 is different from the variable of the same name on line 4. As result, we see that GREAT and CuBERT fail to label the variable definition on line 2 as unused. CODETREK, however, takes advantage of the relationship between the variable definition and its use (an ssa-use node) and makes a robust prediction. Among the set of randomly generated walks starting from the definition on line 2 (expr node with id 4244) there are no walks with the following pattern which only occurs when a variable is used after being defined: "expr access var ssa-var ssa-use". Therefore, CODE predicts that this variable is never used. On the other hand, as illustrated in Figure 9 a walk with the mentioned pattern exists between the definition with id 4309). So, CODETREK predicts that this variable is used. It is worth emphasizing that the walks illustrated in Figure 8 and Figure 9 are very similar although they correspond to completely different code snippets.
and definitions of variable explicit,
line 3 (expr node with id 4254) to its use line 4 (ssa-use node
I.2 EXAMPLE 2 (EXCEPTION)
For the EXCEPTION task, choose code snippet from the test dataset, which is listed in Figure 11 In this code snippet, CODETREK must predict the exception to be caught by the except statement at line 36 (represented by HoleException). The correct exception is ValidationError. We know this
21

---

Published as a conference paper at ICLR 2022
claas Admisalon:
def adnit_cariseii caz):
not atr (ezz((aar.eetia
raise vallidationFror (*Index is not valid")
8
name caz-get_nuaber!!]
name-upper()
name:
10
ralse ianiidatooororr (*Humber not in capslock*)
name name.count (" "I
raise Validationésrer (tw.iarrroooruubeeeee ("Number should have 3 parts")
13
chack_nome nome neme.split("
not check_name 1al
15
raise Salidatiinneeee ("Firat part is not alpha")
not check_name (1teee11_11deeeee .1ddectmal
17
raise ValidationEee ("Second part La not decimai")
not check_aeme [2] isellha
roise validationérrer (" ("raird part is alpha")
20
owner = car.get_ (1. replane **)
owner, isalpaa
owner.istitlen
22
raise ValidationEeroo ("Owner's name is not weitten correctly")
(owner) 40:
raise Validat ionferoo ("Name Loo long")
+ number other unit functions renoved here only for presentation purposes
Leat_car_adait
29
admit admission. jet_tgetteintttee (1, *ag BOs", "ban")
card Car (4, *A", "Ian")
try:
34
admit.admit_one t_ar (carl)
assezt Palse
36
except HoleException:
ossert: True
Figure 11: A sample code snippet for EXCEPTION.
(d: 4506
id: 4452
id: 5253
id: 4436
kind: except
scope:
name: test car__dmiit
caller: 4452
name: admit_cca
scope: 3801
prc.py:93-102 93-102
scope:
callee: 4236
scope:
stmt
-cope__shb s0ml-
Scope
uncc Aunc_scope-
func
call.callerr_fucce call
callec func.id
func
func, scope
expr
stml
scope_sti _smm
Scope
4264 var:
Id: 4262
Id: 3923
name: VelidationError
kind: raise
scope:
parent: 4226
ctx: read
parent:
scope:
arc.py:20
Figure 12: The most important walk in instance of EXCEPTION.
because we observe that the function admit.car is called in the corresponding try block, and upon inspecting its definition, we see that raises the ValidationError exception.
Out of the walks sampled by CODETREK for predicting the correct exception, we illustrate the most important (highest scoring) walk in Figure 12 This walk represents the aforementioned intuitive reasoning for predicting the exception. It starts at the anchor node, which is the node of type stmt with 4506, corresponding to the except statement on line 36. It traverses to the function definition of admit_car by first traversing to the call node for admit.car with id 5253, representing the call on line 34, and then following the corresponding call graph edge to the definition admit.car. These call graph edges allow for such inter- pro-pprredurral reasoning. The walk then traverses to the stmt node for the raise statement, then to its expression, and reaches the ValidationError exception via its corresponding access node.
22

---

Published as a conference paper at ICLR 2022
1.3
EXAMPLE 3 (VARSHADOW)
enV_ eav.
plans Systamkeq:
class Utils:
@atoricmathod
10
def rev
range (1ant)
12
s|1]
ali] [1-1111
{[11111)]
15
@atoricmathod
17
def env_check 11:
env_ anviron. vars
9
return erv_vars
Figure 13: A sample code snippet for VARSHADOW.
Id: 5051 parent:
var: 4238
name: env. env__ars vars
4226
parent: 4226
expr
access expr
300855 van
module_ var
module
module scope-loc
scope: 8456
scope loc
parent:
4346
id: 4347
id:
scope sope__scoe-loc
var: 4347
name: env_vers
name:
write
parent: 4337
scope: 8456
access
acoess
Unc,_
func
fun
scope
id: 8456
scope:
src.py:93-95
Figure 14: The most important walk in an instance of VARSHADOW.
VARSHADOW is an example of a long-range task in which the model has to be able to distinguish between the global and the local scopes in order to predict whether global variable is shadowed by another variable with the same name that is defined in a local scope. We use the code snippet in Figure to explain how semantic relations help in such tasks.
To determine whether global variable is shadowed by a local variable, a programmer would look for variables that are defined in local scopes and have the same name as the global variable. The walk which is illustrated in Figure 14 captures the relationship between the global variable definition (expr node with id 5051) and local re-definition with the same name (access node with id 4346) by visiting local scope (scope node with id 8456) of the module (the module node) along the way. Interestingly, CODETREK assigns the highest importance to this walk among number of randomly generated walks, and can therefore correctly predict that env vars is shadowed global variable.
23


Reviews:
[{"review_id": "kafcCe53JHZ", "reviewer": "Reviewer_okqQ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "## Pros\n+ The proposed system shows strong empirical results.\n+ The system is compared to a variety of structural and textual baselines.\n\n## Cons\n- The paper is very difficult to understand. Many details are not well defined nor explained. See below.\n\n- Ease of use - the system has many \"moving parts\" that need to be manually designed. While this can be a good thing for experts, it limits the system's applicability to non-expert users and hinders its generalization to other domains, tasks, and languages. The authors claim that \"A task developer need not be a machine-learning expert to bring in more semantic information about programs\". However, there are many more aspects that the task developer needs to consider: which queries to write, how to write these queries, how to choose the starting node, how to bias the random walk, etc. These might make the proposed system to be very difficult to use for other tasks and languages.\n\n- The paper describes a specific system, and its contributions in terms of machine learning are relatively minor. The paper also lacks a deeper analysis or an ablation study to pinpoint the exact contributing factors and discuss their alternative, nor concrete examples which will help readers to better understand the impact of the proposed method.\n\n\n### Clarity\n\n* The paper mentioned Semmle several times and mentioned that Semmle converts codebases into relational databases. It is not explained what is Semmle? How does Semmle work? How does it convert codebases into databases? Is it a commercial product? \n\n* Figure 1 is very nice visually but is still very difficult to understand. Some details are explained at the beginning of Section 2, but are still very hard to follow. If I did not miss anything, \nother details in this very detailed figure are not explained anywhere. Some explanations that do exist are very hard to follow and to connect with the figure, for example:\n\n>\"The derived information is stored in def, which, together with call, can bias the prediction of the best variable to replace a placeholder\" \n\nI am not sure how to understand this sentence and what in Figure 1 should I look at.\nThis unclarity continues in Section 2, where no clear definitions nor explanations are provided. The paragraph \"Code as a graph\" is very unclear, and frequently uses terms that were not defined.\n", "summary_of_the_paper": "The paper presents a framework called CodeTrek for processing and learning source code. The main idea is to represent code as a graph, manually design analyses to serve as additional relations, and perform a set of random walks on the graph. These walks can also be manually guided. Finally, the set of walks is encoded to represent program elements.", "summary_of_the_review": "Overall, the paper shows strong empirical results. However, I believe that this is an application with little novelty, and few lessons to be learned for the ICLR audience. Hence, I would tend to reject this in favor of more ML-heavy papers.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "NolbM3uaIUy", "reviewer": "Reviewer_3Z8h", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "This paper is well written and the analysis of the experimental results are sufficient. But I have some questions to discuss.\n\n(1) The novelty in the network architecture is not enough. CodeTrek spends too much weight on the description of Code2Rel and Rel2Graph procedure, however, the network architecture i.e., Transformer is simple. Furthermore, the idea of sampling walks is the same with Code2seq and the difference is mainly on the constructed graph/AST is different.\n\n(2) This paper conducts some sensitivity analysis on the number of the sampled walks, however, the discussion of another important factor walk length (24 in the appendix) is missed especially for the exception task, which may be critical. So I would like to see the performance. \n\n(3) CodeTrek selects the anchor node or in other words, assign higher probabilities to some specific node types for example stmt, expr, it would be great to provide more insights on why choosing these nodes as the start point.\n\n(4) In Rel2Graph, there are two types of relations i.e., base relations and derived relations. Derived relations are customized by the program analysis queries on the base relations, so it can be regarded as another featuring engineering. Is there a way to only use the base relations to construct the graph and see the experimental results? It would be important to see how much the derived relations weigh.\n\n(5) In Table 1, the gap between GGNN and GREAT on Varmisuse is very obvious (0.69 VS 0.82), however, in the original Hellendoorn et al. [1], the gap is not obvious GGNN VS GREAT (0.792 VS 0.769). So what is the reason behind this, since the different dataset were used or the different graph structures? \n\n[1] GLOBAL RELATIONAL MODELS OF SOURCE CODE. Hellendoorn et al. \n\n", "summary_of_the_paper": "This paper proposes a new program representation approach CodeTrek, which leverages a program analysis tool (Semmle) to produce the rich representation of the context for a program. Semmle is able to convert the program into a relational database that can capture the semantics behind the program, furthermore, it also supports extracting the task-specific semantics with the query language CodeQL to represent new semantic information. Then CodeTrek utilizes a biased graph-walk mechanism for pruning the context paths and feeds them to the transformer encoder to learn the path representations and followed by deepset to get a vector representation. The extensive experiments on four diver Python tasks: variable misuse, exception prediction, unused definition and variable shadowing prove that CodeTrek can outperform the current baselines i.e., Code2seq, GGNN, GREAT, CuBERT by a significant margin.", "summary_of_the_review": "This paper proposes a new code representation technique that is based on the relational database to capture the program semantics for different tasks, however, the novelty in the model architecture is not enough and the proposed code representation approach is more like a feature engineering.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "EgaXxzOa_m7", "reviewer": "Reviewer_yHJY", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "Pros: \n* A general framework for generating a relational representation of programs for programming-related tasks\n* The use of “declarative” tasks (which can be solved without a learned model, e.g. variable shadowing) to evaluate framework/approaches.\n* A general methodology that specifies a TODO list (defining queries, random walk bias, anchors, etc.) for tackling a new task (it doesn’t mean that these steps are easy).\n* The use of long-distance and cross modules dependencies to solve the tasks.\n\n\nCons: \n* This paper uses standard neural architectures and the representation that is used is also rather low on novelty. \n* A lot of effort is required in preprocessing, before feeding the NN. This includes an expert’s knowledge to determine task-specific queries and task-specific random walk bias (although these were not used in the experiments). To conclude, it feels like that given a new task, it’s not straightforward to apply this approach. \n* This paper has less of a contribution to the ML community but has a potential impact on the SE community. The only ML novelty I can spot here is the use of the graph to represent the schema, which can be then processed by some NN. \n* This approach is limited to cases where one has the whole project in hand, and the ability to perform (potentially heavy) static analysis of the code.\n\n* Allamanis et al. have shown how to represent programs as graphs, including cases when the program information is enriched by a wide range of semantic information from program analysis. They used the resulting graph representation as input to GNNs, but there’s nothing that precludes the same input from being linearized (by standard graph walks) and used in sequential models. \n\n* Given the expressiveness of the framework, I was hoping for evaluation on tasks that require a more global and long-range kind of properties. Unfortunately, most of the paper focuses on tasks that have a local (intra-procedural) solution. While I understand this from the need to compare to existing baselines, I think that it does not play to your strengths.\n\n* In your evaluation, you only experimented with classification tasks. It will be beneficial to see other kinds of tasks such as summarization and code generation.\n\n* You mention in several places a “walk score”, but didn’t define it, and how it’s calculated and used.\n\n* Table 3 is interesting. Does it mean that the expected benefit from the deep and often complicated semantic analysis is sometimes as low as 20%? Do you think sampling more paths from the AST could have narrowed the gap? \n", "summary_of_the_paper": "The paper presents a framework for creating task-specific program representations for deep learning based on program analysis and random graph walks. The basic idea is to use program analysis to create a graph-based representation of the program, capturing both syntactic and semantic relationships between elements. This graph-based representation of the program is then encoded by embedding a set of (random) walks in the graph.\nThe paper evaluates the framework using four tasks: three tasks that only require intra-procedural program analysis (var-misuse, infer exception type, predict where a definition is used) and one that required inter-procedural analysis (variable shadowing).\nCodeTrek is shown to outperform existing techniques in most benchmarks. \n", "summary_of_the_review": "This paper proposes a general framework for applying deep learning (specifically DeepSet + Transformers) to code. The authors suggest the following steps for handling code-related tasks:\nBuilding a relational database based on the code by applying pre-defined queries and user/task-specific queries.\nConverting the database into a graph, defining some user/task-specific random walk bias and length, and user/task-specific anchor nodes.\nApplying this random walk, encoding these using Transformers, and feeding the result to some task-specific neural network.\n\nOverall I think it’s a good paper with a minor ML contribution. It shows that the use of the relational graph outperforms the common use of AST and data flow graphs. It has its drawbacks  - heavily dependent on expert knowledge per language and per task. Further, even experts can’t tell which are the best queries/random walk for the given task.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "CH4GlkgAQyy", "reviewer": "Reviewer_n7bP", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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": "I'm both excited and disappointed by this paper. The idea of using relations as obtained by the Semmle tool as intermediate representation is elegant, reasonably extensible, and opens a new path to integrating more knowledge from the expert practicioners into the ML4Code area. I believe that this is a valuable contribution that should be published.\n\nOn the other hand, the remainder of the paper has a number of substantial problems:\n1. the translation of the database of program facts into a binary graph is not described well:\n  * (Q1a) how do tuple attributes exactly contribute to the node features? how are different data types (stmt types / IDs / line spans / ...) embedded? If I understand p5 top correctly, you're simpling bag-of-words embedding WordPieces here - does this even take into account what attribute a token comes from?\n  * (Q1b) how fine-grained are edge types? Concretely, when translating something like the \"call\" relation in Fig. 1, are separate edge types generated for callees and callers? The main text says \"for any two relations R and S connected via referential integrity, an R_S edge type is defined\". Alg. 2 says \"l [...] is a referential integrity constraint\", which is an undefined term in the paper. \n  * (Q1c) have you considered representing these relations as hypergraphs (with each named relation corresponding to a hyperedge type, and each tuple from a relation instantiation corresponding to a hyperedge) and then using HyperGNN models?\n\n2. the random walk strategy is an interesting trick to break through the limitations of number of message passing steps in GNNs / number of layers in Transformers, but leaves many questions:\n  * (Q2a) You say \"each individual part of the embedding tensor gets its own learnable positional embedding\" - it's not clear to me what that actually means - are you describing an embedding lookup here, or do you mean to say that the relation names / relation attributes / edge types have separate positional encodings? How do you ensure that they are well-aligned with each other? Do you have ablations that show that your positional encodings contribute anything at all?\n  * (Q2b) You are using mean pooling to obtain the representation of a path, but that is likely to be sensitive to the length of the path. Have you considered using attentional pooling (e.g., most simple, introducing a [PATH] pseudo-token and use its final representation, or at least a gated, weighted sum)? After all, you're using a similar attentive approach for the aggregation of paths by going through DeepSet.\n\n3. the experiment section feels not well-structured (some explicit guideposting what key points you are trying to support would help with this), and the considered baselines are underdescribed and seem incomplete.\n  * (Q3a) The hypers described in App. A for the baselines are surprising in that they don't match the hyperparameters proposed by the original authors - in particular, GREAT (4 layers here vs. 6 or 10 layers), Code2Seq (4 LSTM layers here vs. 1 in original), and GGNN (4 layers here vs. 8 layers). How where these parameters chosen? In particular, the low number of layers for GREAT and GGNN substantially limits their performance, and so this is quite surprising.\n  * (Q3b) What edges are presented to the GREAT / GGNN models, which consume more than just the AST? This is not described at all.\n  * (Q3c) How sensitive are your results to different choices of the random walk specification? You list learning the spec as future work, but what is the effect of choices here? How did you arrive at your current default spec?\n\n", "summary_of_the_paper": "A method to learn to reason about programs is presented. The core novelty is an intermediate program representation as a set of relations (in the logics sense), derived from existing program analysis tools. By translating each tuple into a node, and references between relations into edges, the set of relations is transformed into a graph. Finally, graph learning techniques (from the random walk view of the world) are used to learn to predict the target label from the obtained graphs.", "summary_of_the_review": "The paper presents a novel way of automatically extracting valuable information from programs before using standard ML tools to process them. While the core idea is exciting, the writing is in some places imprecise (see above) and the experimental evaluation is missing many details and leaves many question marks on the empirical claims. I like this paper, but I think at this time, it's shortcomings are too significant to allow for acceptance at ICLR.\n\n\nUpdate after rebuttal\n----------------------------\nThe authors did a great job of responding to my concerns and answering my questions, alleviating most of my concerns.\n\nI would note that the current draft does not integrate the further explanations and results responding to my question (Q1a).\n\nThe draft also has not been updated to include the additional experimental results and ablations that the authors provided during the discussion period, and I would encourage them to include all of these in the next revision of the paper, either embedded into the main text or in an appendix.\n\nOverall, I'm now satisfied that the paper is presenting an empirically meaningful improvement over earlier works. As the reviewing discussion highlighted, constructing program graphs as proposed by Allamanis et al. (and following works based on the extraction of semantic program information) is highly non-trivial and not an off-the-shelf product. I view the core contribution of the current submission as the empirically validated insight that this can be solved by the Semmle static analysis tool. While many open questions about design choices here remain, this is a substantial step forward that deserves publication at ICLR, as I expect it to be of significant interest to the ML4Code subcommunity at the conference.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a deep learning approach encodes codebases as databases that conform to rich relational schemas. Based on this, a biased graph-walk mechanism efficiently feeds this structured data into a transformer and deepset approach. The results shown a quite good, compared to other approaches present at ICLR. Moreover, one reviewer is strongly voting for accepting the paper, arguing that "that this paper is of significance to the ML4Code research community, as it shows how to offload the engineering cost of extracting semantic information from programs to a standard tool." Overall, I have really enjoyed reading the paper, and the use of relational database as codebase together with a transformers is sweat. On the other, it also presented in a rather engineering way, as pointed out by several reviewers, suggesting that some software engineering venue might be a better place for the work. But then ICLR had similar papers, and the present paper demonstrates a benefit of using a relational encoding. Thus, I weight the leaning towards rejects borderlines votes less and suggest an accept overall. We all should keep in mind that also deep neural architecture are full of design choices.
Decision: Accept (Poster)