GRAPHIX: A Pre-trained Graph Edit Model for Automated Program Repair
Authors: Thanh V Nguyen
Srinivasan H. Sengamedu
Venue: ICLR 2022 Submitted (2022)
Keywords: Program Repair
Graph Neural Networks
Pre-training

Abstract: We present GRAPHIX, a pre-trained graph edit model for automatically detecting and fixing bugs and code quality issues in Java programs. Unlike sequence-to-sequence models, GRAPHIX leverages the abstract syntax structure of code and represents the code using a multi-head graph encoder. Along with an autoregressive tree decoder, the model learns to perform graph edit actions for automated program repair. We devise a novel pre-training strategy for GRAPHIX, namely deleted sub-tree reconstruction, to enrich the model with implicit knowledge of program structures from unlabeled source code. The pre-training objective is made consistent with the bug fixing task to facilitate the downstream learning. We evaluate GRAPHIX on the Patches in The Wild Java benchmark, using both abstract and concrete code. Experimental results show that GRAPHIX significantly outperforms a wide range of baselines including CodeBERT and BART and is as competitive as other state-of-the-art pre-trained Transformer models despite using one order of magnitude fewer parameters. Further analysis demonstrates strong inductive biases of GRAPHIX in learning meaningful structural and semantic code patterns, both in abstract and concrete source code.

Under review as a conference paper at ICLR 2022
GRAPHIX: A PRE-TRAINED GRAPH EDIT MODEL FOR AUTOMATED PROGRAM REPAIR
Anonymous authors Paper under double-blind review
ABSTRACT
We present GRAPHIX, pre-trained graph edit model for automatically detecting and fixing bugs and code quality issues in Java programs. Unlike sequence-to sequence models, GRAPHIX leverages the abstract syntax structure of code and represents the code using a multi-head graph encoder. Along with an autoregressive tree decoder, the model learns to perform graph edit actions for automated program repair. We devise a novel pre-training strategy for GRAPHIX, namely deleted sub-tree reconstruction, to enrich the model with implicit knowledge of program structures from unlabeled source code. The pre-training objective is made consis- tent with the bug fixing task to facilitate the downstream learning. We evaluate GRAPHIX on the Patches in The Wild Java benchmark, using both abstract and concrete code. Experimental results show that GRAPHIX significantly outperforms a wide range of baselines including CodeBERT and BART and is as competitive as state-of-ther offtthe-rrt pre-trained Transformer models despite using fewer parameters. Further analysis demonstrates strong inductive biases of GRAPHIX in learning meaningful structural and semantic code patterns, both in abstract and concrete source code.
INTRODUCTION
Detecting bugs and code quality issues in programs and fixing them is an important task in software development. Oftentimes, this two-step process is manual and iabor-intensive. In order to ease the burden on developers and reduce the development cost, several automated tools are developed and integrated with development environments (IDEs) and/or code review systems. There exist many program analysis techniques (Sadowski et al.) 2015) that use hand-written rules to provide linter-style recommendations while others (Paletov et al. 2018 are able to detect specific bug types (c.g., crypto API uses) but leave them to the developer to fix. In the recent years, advances in deep learning have appealed researchers to move to data-driven approaches (Vasic et al. 2018) that learn to detect and fix bugs from data. Henceforth, we refer to the problem of automatically detecting and fixing bugs as automated program repair (Goues et al. 2019).
One main challenge with using machine learning for automated program repair is the lack of large human-labeled datasets. Several works (Tufano et af. 2019b ab propose heuristics to extract bug-fix data from code changes. Code changes are represented pairs mostly at the method level, and typically pertain to feature enhancements, bug fixes and code refactoring. Code changes relating bug fixes are identified through the presence of keywords such as "bug" in commit messages, through the size of changes or both. An advantage of using code change data that there are plenty of code changes available in source code repositories.
(code before, code after)
Based on code change data, the learning of bug fixes has been taken in three main directions. The first line of work regards the bug-fix learning problem as sequence- -based code generation and harnesses models with RNN (Hata et al., 2018) Chen et al. 2019 Tufano 2019b al and more recently with pre-traines Transformer models (Feng et al. 22200] Guo et al.
the power of sesquence-t--sqqueee
ctt al.
2021 Ahmad et al.) 2021 Wang al. [202 Berabi et al., 202 l). Secondly, instead of generating the
fixed code from scratch, Zhao et al. (2019); Chakraborty et al. (2020); Li et al. (2020); Panthaplackel eet al.] (2021) extend sequence models and propose generate edits on the buggy code. Lastly,
Yin et al. (2018); Tarlow et al. (2019); Dinella et al. (2020); Yao et al.] (202T) deviate from the token-based representation of code and leverage the hierarchical structure in the abstract syntax tree

---

Under review as a conference paper at ICLR 2022
(AST). The high level idea is to learn a graph edit model to iteratively transform the AST of the buggy code into the AST of the fixed code. The learning is supervised by tree differencing edits via cross-entropy loss. Despite the benefits of more precise bug localization, shorter tree edits and natural graph representations of programs, existing graph-based models have been less competitive than wransformer-basee models thus far.
In this paper, we pursue the direction of representing explicit program structures with graphs and make contributions toward source code understanding using machine learning. Specifically, we present GRAPHIX, pre-trained graph edit model for automated program repair. Inspired by HOPPITY (Dinella et al., 2020). we design GRAPHIX as sequential decision process with a encoder and an autoregressive tree decoder. Conditioned on the graph state and the edit history at each step, the decoder iteratively makes primitive actions (e.g., adding a node) on the graph corresponding to the input AST. Unlike HOPPITY (Dinella et al. 2020), we enhance the encoder with multiple graph heads to capture diverse aspects of hierarchical code structures. In addition, we guide the decoder with underlying Abstract Syntax Description Language (ASDL). Owing to the syntax language, the graph structure and semantic edits, GRAPHIX exhibits strong inductive biases in learning generic fixing and refactoring patterns from code changes. Moreover, we devise novel pre- wre-tranning strategy, namely deleted sub-tree reconstruction, that enables GRAPHIX to learn implicit program structures from unlabeled data. Here, the model is pre-trained to reconstruct a randomly deleted sub-tree given other code context, using the same cross-entropy loss as the program repair task. Our pre-training task generalizes the masked language model and denoising objectives (Devlin et al., 2019 Lewis et al. 2020) in sequence models to the AST representation of source code. Our idea shares the conceptual principle with generative models of code (Li al.) 2018 Brockschmidt et al.) 2018) for expression generation and the structural language model (Alon et al. (020) for any-code completion.
graph
We evaluate GRAPHIX on both concrete and abstract versions of the Patches in The Wild Java benchmark (Tufano et al. (019b)) We show that GRAPHIX significantly outperforms edit- bastd and Transformer models, and the performance as competitive as recent state-of-the-arr pre-trained baselines despite using fewer parameters. Our in-depth analysis of the generated patterns demonstrates the ability of GRAPHIX to learn a wide range of meaningful and generic bug fixing and code refactoring patterns. Compared to HOPPITY, which merely learns short edits such modifying access keywords (private to public), adding break, or removing redundant type arguments, etc., GRAPHIX is able to handle longer, more complicated structural and semantic edits (up to 20 graph edits). We showcase a variety of bug-fix fix examples such as fixing off- onf- errors, possible null pointer exceptions, etc. in our analysis.
In summary, we make the following main contributions in this work:
1. GRAPHIX is medium-scale graph edit model that can be pre-trained with the deleted sub-tree reconstruction objective for automated program repair.
2. GRAPHIX significantly outperforms the edit-based models and is able to achieve high top- I exact match accuracy on the Patches in the Wild benchmark even without pre-training. Using explicit graph representation the abstract syntax tree, our model is competitive as large-scale Transformer models.
3. Unlike previous work, which only focused on the abstract version of the benchmark, we evaluate GRAPHIX on both abstract and concrete code and show the effectiveness of our model in both settings. This also suggests that the code abstraction may not be necessary.
4. Our in-depth analysis of the generated fixes demonstrates that GRAPHIX exhibits strong inductive biases in learning to both structural and semantic code patterns, leading many meaningful bug fixes.
Despite our focus on Java, our model and the pre-training strategy can be extended further to work with multiple languages for universal source code understanding using a language-agnostic abstract language and parser such as trte-sittey"] In addition, the syntax tree structure is highly amenable to program dependencies. We hope our work will inspire the community to advance the area further by incorporating more program dependencies, designing efficient graph learning algorithms with large model architectures and datasets.
2

---

Under review as a conference paper at ICLR 2022
2 RELATED WORK
Deep learning for program repair Advances in machine learning in the past decade have drastically changed the landscape of research for automated program repair. Inspired by Neural Machine Transla- tion, Hata et al. (2018); Chen et al. (2019); Tufano et al. (2019) a regard code as a sequence of tokens and use wwwpueenceett-seueeeee
models to "translate" the buggy code into the fixed code. More recently,
pre-trained Transformer-based models such as CodeBERT (Feng et al. (2020), GraphCode
(Guo et al. (02T), PL-BART (Ahmad et al., (202)) and most recently CodeT5 (Wang et al.] (20T))
achieve sfate-of-the-ant results on "Patches in the Wild" Java benchmark (Tufano et al. (209b) for
program repair. A series of edit-based approaches model the code edits made on the buggy code as
opposed the "translation" labaalttooo"---ddddd counterparts. (Zhao et al.) (2019); Chakraborty et al. (2020); Li et al. (2020); Panthaplackel et al. (2021) extend sequence-to-Seee -e-eueeeee RNN models to predict the sequence of edits given the buggy code. Unlike these works, we build GRAPHIX on the inherent abstract syntax structure of code instead of its token-based representation.
Graph neural networks GNNs such graph convolutional networks (Kipf & Welling 2016). graph attention networks (Velišković et al.] 2018) provide a set of powerful tools for learning graph-structured data. Source code with rich graph structures in abstract syntax trees and program dependency graphs naturally fits to the GNN toolbox. Yin et al. (2018); Allamanis et al. (2018); Hellendoom et al. 2019);; Wang et al. (2020) augment the AST with additional data flow edges between variables and use GNNs for tasks such as variable name prediction. Yin et al. (2018); Tar lollow cet al. (2019) Dinella et al. [2020); Yasunaga & Liang (2020); Yao et al. (2021) use graph models based on A for program repair and editing tasks in C, C# and Javascript, separately. Particularly, Brockschmidt et al. 2018); Dinella et al. 2020): Yao et al. (202T) use graph representations with tree-
based decoders for AST generation by editing the partial AST one node at time. |Brockschmidt et al.
(2018) Yao et al. (202T) further equip the decoder with an Abstract Syntax Description Language (ASDL) ensure the syntactic correctness of the generated code. Our work advances HOPPITY
(Dinella et al. 2020) and (Yoo et al.] (021)) with multi-head graph encoding and pre-training and demonstrates the benefits of program structures on learning bug-fix patterns in Java code.
Pre-training Transformer (Vaswani et al. 2017) and large-scale pre-training (Radford et al. 2018 Devlin al. 2019 Lewis al. (020) have gained much traction in the broader field of natural language processing (NLP). Sequence-based pre-training with Transformer has also proven to be effective in learning source code representations. In contrast, techniques for pre-training with graphs are less well-developed, especially for learning graph representations of source code. Existing work on graph pre-training are mainly based on attribute and edge prediction (see (Hu et al. 2020) and references therein). Distinct from these works, our pre-training task is conceptually related to
structural generative modeling of source code (Brockschmidt et al. 2018 Alon et al. 2020) for tree generation, just as pre-training techniques in BERT and BART derived from language modeling and denoising for sequence generation in NLP. However, we focus on pre- pre-training GRAPHIX to learn hierarchical tree structures of code for program repair rather than generating code.
MOTIVATING EXAMPLES
We begin by motivating the graph edit approach with two examples of code changes. Listing | displays two test samples from the Patches in the Wild benchmark, which are real-world Java code extracted from GitHub repositories.
In both examples, we can see that the code changes are much smaller compared to the method bodies. The fix of the first bug is straightforward with one edit that replaces inside the condition with & to prevent the program from crashing. For the second bug, the change is more structural and hierarchical than merely replacing the token Object with void and removing return keyword. Rather, the corresponding fix can be summarized by a sequence of four tree edits: (i) replace the return type Object with void type, (ii) remove the ReturnStmt. (iii) add an Expres s ionstmt at the same position, (iv) copy the Ass i Enprr in the original code over the child of the newly added expression statement. More generally, each edit is associated with a specific node and consists of several primitive actions such node deletion, addition copy and type or value prediction.
These examples illustrate the benefits of the edit- based approach over the pure translation based approach in three aspects. First, by modeling the edits, the model maintains the global code context
3

---

Under review as a conference paper at ICLR 2022
public static List<SLring> ge.Domaine (St:ing consumerKeyl throws AP APIanageeeeeLExxeee (sonsumerKey)
String List gettttttteettthorriee.o.o wethaatoorseeeeadnnnnnyeeeeee
if ((list 1- mull) 66
(! (1ist, Seret.ieBian LeEmpty 1131
return Arreys asList (list. (*) ")
null;
object
void
setData (Object newData)
retucn
data
newDatar
Two bug-fix fix examples in the test Patches in the Wild benchmark Tufano et al. (2019b) GRAPHIX can detect and fix. In each method, we highlight added text in green and deleted text in red. We also remove package names from APIs and change the long name of the first method for readability. (top) A bug that may cause Nul weelloonneerteeeeeeee exinter ion when list null in the sample medium/8390. (bottom) A code quality issue detected in the sample small/8616 where the setter has redundant return statement and type. The figure best seen with color.
Listing 1:
instead of decoding from scratch. Second, the edit sequence often much shorter than the code sequence per Finally, with the structural edits, the decoding be guided by underlying syntax language. For example, the child of Express sionStmt must be an expression (c.g., As aassignExp in the second bug fix) and must be other production rules such as Ret ReturnStmt. Another advantage is in terms of an end-to-end framework for bug detection and fixing in the sense that such an edit model can predict whether or not a program buggy and localize the bug more precisely.
APPROACH
At a high level, we want model p(grl6, gb) where Jb is the buggy code and g is the fixed code. Instead of encoding and generating 9ʃ from scratch, we learn a sequence of T tree-edit actions {ar)== that transforms 9b to g, as motivated in Section 3 Indirectly, we learn the model p(a p(a1.r)g)) from a labeled dataset samples, each with buggy code and the corresponding ground-truth edit, by minimizing a cross-entropy loss. Figure T illlustrates the overall architecture.
Concet
LSTM
(akks Predicions
LSTT
Nade Iakku Pradictors
LSTN
Foods, Tikle Pladiccsos
LSTM
Mode: Uskas Predictions
GIN haad
Mull-bead GhN
Mutt-head CAN
Uult-hoad GWN
Clanciion
Wirtlppe
DETeER
PrarType
AetignDgg
Andgytigg
DunDuta
Saep Recows
oayar and cuuoeyer
Step Remoon Peturatte
B&C: Sepaonanii pww.enaaaaaaaa stali
cogy Kasi Rago
Figure 1: The overall architecture of GRAPHIX with illustration of the edit sequence the second buggy code in Listing T For readability, we show the partial AST with only two children the root node. The graph encoder and decoder components are repeated for the illustration purpose.
One may recover the original token-based generation model when each action corresponds to adding new token and T is the length of 9b. The key departure from such model is more hierarchical program representation that allows shorter and more structural edits between the input 9b. and the output gy- Inspired by (Dinella et al. 2020 Yao et al., 2021) which build syntax structures and
4

---

Under review as a conference paper at ICLR 2022
tree differencing-basee based edits, we represent the buggy code graph gb that is constructed from the program's 's syntax tree and extra data flow edges between certain leaf nodes.
Our model is sequential in nature with multi-head graph encoder and an autoregressive tree decoder. At each time step t, the encoder encodes the current graph state 9t, and the decoder computes the graph edit history &t. Conditioned
the current state, the decoder then predicts and performs tree edit actions. We discuss the baseline encoder, edit operations and ASDL-guided decoder in greater details in Appendix AA] Next, we elaborate more on the multi-head graph encoder and our proposed pre-training strategy.
4.1 HEAD GRAPH ENCODER
Earlier work (Yin et al. 2018 Alammnnis et al. 2018 Brockschmidt et al. 2018 Hellendoorn et al. 2019) has explored graph neural networks on rich graph structures of programs including syntax trees and dependency graphs for program representations. We follow (Dinella et al., (220) and represent each program using its abstract syntax tree: the core graph is built upon the syntax tree with bidirectional edges between parent and child nodes, edges between adjacent leaf nodes and additional edges between value nodes to partially capture data flow information (Dinella et al. 2020 Allamanis et al.] 2018). Then, we use graph isomorphism network (GIN, Xu et al. (2019)) to compute a vector representation for each node and an aggregate graph representation. Motivated by the success of multi attentions in (Vaswani et al. [017] Veličković et al.. (2018), we propose
multi-head graph encoder for the graph encoding in which each head is a GIN and the head outputs concatenated into corresponding node and graph embeddings. Using multiple graph heads allows the model to encode diverse aspects of the input program.
Our architecture is different from the per-layer multi-head attention in Transformer (Vaswani et al. 2017) and graph attention networks (Veličković et al.) 2018) as well as multiple towers in message passing neural networks (Gilmer et al. (017)) We do not have cross-attention, hence having multiple heads per graph network layer is equivalent to adding more linear projections, which merely increase the GIN's s depth. We choose to concatenate the resulting GIN representations at the end as an ensemble model and find such strategy effective in our ablation study (c.f. Appendix E..
The graph encoder is the component with the most parameters. The encoder's 's size the function of the number of layers, the latent dimension and the number of heads. We mainly experiment with a multi-head model that has 4 layers, 8 heads and the latent dimension d = 256, which amounts to 32M parameters.
4.2 PRE-TRAINING OBJECTIVE
We have described the architecture of GRAPHIXX as graph-based, autoregressive model. GRAPHIX is a supervised model and trained on labeled bug-fix fix data using the teacher-forcing technique. Since the labeled dataset is relatively small, in order for the model to learn more inherent program structures, we devise novel strategy to pre-train GRAPHIX on unlabeled source code and allow the knowledge to be transferred the downstream program repair task.
Pre-training task. Generalizing the masked language model pre-training idea in NLP (Devlin et al. 2019; Lewis Lewis et al. 22020), we devise a pre-training technique for the tree-structured data, namely deleted sub-tree reconstruction. To that end, we take the ASTs from a collection of unlabeled source code. For each AST, we randomly select sub-tree of a certain size rooted node n. We replace with dummy node, and remove all the subsequent nodes and edges in the sub-tree. Given the dummy node's 's location, GRAPHIX is then trained to reconstruct the sub-tree using the other code context in the sequential manner. The decoder expands the partial AST one node at time in the depth-fire first traversal order (Maddison & Tarlow 2014 Bielik et al. 2016), using the production rules in the underlying abstract language. Similar to one tree edit in bug- fixing task, each expansion step corresponds to a classification problem, and therefore we use the same cross-entropy objective for training without changing the network architecture.
Our pre- tre-training task can be viewed as a generalization of the masked language model objective in BERT (Devlin al.) 2019) and specialization of the denoising objective in BART (Lewis et al. 2020) to the tree structure of code. The graph reconstruction task is conceptually similar to the graph generative models (Li et al. 2018 Brockschmidt et al. 2018) for expression generation and the
5

---

Under review as a conference paper at ICLR 2022
structural language model of code (Alon al. 2020) for any-code completion. Unlike these works, we are interested in pre- treiiiinnng rather than code seneratiioncoomlltionn Note that our pre-training technique is specific ASTs with underlying syntax language and not applicable to arbitrary graph structures. The pre-training strategy, however, can be extended to work with other types of graph corruptions such as multiple sub-tree additions and replacements well objectives such as link prediction and so on. We defer these directions to future work.
EXPERIMENTS
We evaluate GRAPHIX on the Patches in the Wild benchmark and compare its performance to existing wranslationbbase and edit-based baselines. We conduct series of experiments and studies on the network architectures (i.c., model size and single vs. multiple heads) and the data types (short vs. long function, and abstract concrete code) to strengthen our evaluation.
5.1 DATASET
We use the Patches in the Wild Java bug-fix fix benchmark, which was curated and popularized by MyyTufee Tufano et al. (2019b). The dataset consists of 123,804 bug-fix fix pairs extracted from GitHub repositories. It has two subsets: the small subset contains 58,350 methods/functions with less than 50 tokens whereas each of the 65,454 medium functions is between 50 and 100 tokens. To build the final dataset, the authors extracted about 10M GitHub commits whose messages textually match one of these ("fix", "bug", "error", and "exception") " patterns. Finally, the pair of code before and after each commit is considered one bug-fix sample with duplicates being removed. Each subset was originally divided into training, validation and test buckets, and we use the same splits in our evaluation.
Code abstraction. Tufano et al. 2019b) promoted the code abstraction idea where they abstracted away types, names and literal values in each method with generic names such as METHOD VAR_2 INT _. Most existing work employs this abstracted code benchmark with an only exception of (Drain al. 202T). For convenience, we call it abstract benchmark. We also conduct extensive experiments on the concrete version that comes from the same dataset (Tufano et al. 2019b) without performing the code abstraction procedure.
5.2 DATA PROCESSING FOR GRAPHIX
Our proposed model GRAPHIX and its baseline HOPPITY (Dinella et al.) 2020) operate on the AST level, so we need two additional processing steps: code parsing and ground-truth graph edit construction. Given each pair of buggy and fixed methods, we run JavaParse to parse the source code into pair of ASTs and serialize the output ASTs into JSON format. We discarded 120 samples (out of 123,804 samples) that JavaParser was unable to parse. Those few samples should not affect the evaluation.
Ground-truth edit construction. Ground-truth edit sequences are the sole supervision signals that enable the learning of our graph edit model. Each edit includes a pre-defined operation type (see Appendix A.2 for more details), the edit location, the node type and value. HOPPITY (Dinella et al.) 2020) uses JSON differencing algorithm to create the ground-truth tree edit sequence for each pair of buggy and fixed code. Since GRAPHIX a grammar-driven tree transformation (Yao et al.) 2021). 1), we implement grammar-awar and shortest distance tree differencing algorithm, inspired by a dynamic program in Yao et al. 2022 l (Algorithm 3). One could also use the GumTree differencing too We show an example of two types of ground-truth edit sequences from the two differencing algorithms and statistics highlighting the advantages of the grammar-awan tree differencing in Appendix B
Pre-training data. We use the CodeSearchNet dataset released by Husain et al. (019)) for our pre-training purpose. The entire dataset consists of 6.4M functions in six programming languages extracted from public non-fork GitHub repositories. Since our focus is on the Patches in the Wild Java
benchmark, use the Java portion of NodeSearchNet with total of 1.5M functions. We filter out
httts::/tavaparserr.t
2https://www npm is. com bac htt.so//aacccaaaaaaaaaiooo
https://github: com/ Gu/ /ftp://ccooooccmm/eeeefff///////

---

Under review as a conference paper at ICLR 2022
those functions that are not parsable have more than 600 AST nodes. The remaining functions be considered fixed code and are used the pre-tra pre-training task. During pre-training, we select sub-trees between 2 and 6 descendants for the deletion and construct sequence of addition operations the ground-truth edits. More details on implementation are provided in Appendix C
5.3 BASELINES AND METRICS
We compare GRAPHIX to translation-basee models including an LTSTM model (Tufano et al. 2019b) as well state-of oftt--of-the-art art pre-traines Transformer models including notably PL-BART (Ahmad et al.) (021) and CodeTT (Wang et al., ) We also compare our model against edit-based models including Copy That! (Panthaplackel et al.) 202T) and HOPPITY (Dinella et al.) 2020) of which the latter is directly related to our work. HOPPITY applies to Javascript and only works short single-node edits (up to 3). That is, does not handle non non-trivial sub-tree addition. For comparison, modify its implementation the sub-tree from its root in the top-down and left-right order and create a series of single-node addition edits. To train the model, we use the teacher forcing technique that each intermediate step of the addition, the model is given the location of the parent node as well as type and value in the previous step. We name this enhanced baseline e-HOpPITY for convenience.
handle Java source code, and in order to add sub-tree, flatten
Metries. We use the standard top-1 exact match accuracy (EM) as the metric and compare the performance of all the above models on the small and medium sets. Note that EMs for HOPPITY and GRAPHIX are computed based on AST matching, which is equivalent to sequence matching the other models. For GRAPHIX and e HOPPITY, we use beam search of size during inference and select the candidate with the highest score normalized by the edit sequence length.
5.4 RESULTS
In this section, GRAPHIX refers to the 8-head model with 32M parameters that is not pre-trained. GRAPHIX-D refers to GRAPHIX that is pre-trained and then fine-tuned on the respective datasets. We present the results the abstract and concrete benchmark in Table and Table respectively. Each table consists of three groups of results: the first group represents the translation- without pre-training, the second group for edit-based methods and the last group includes pre- trained models including GRAPHIX-P P. Note that DeepDebug (Drain et al. 2021 | was not evaluated on the abstract code while most were not on the concrete code.
methods
Table 1: Top-1 I exact match (EM) accuracy on the abstract benchmark with and without pre-training.
Model
Pre-trained Data
Sizc
Small
Medium
LSTM
Tufano el al.
2019b
10M
9.22%
3.22%
GRU Token Copy
(Panthaplacker el al.
2021
None
250K
14.80%
7.00%
Transformer Dram al
60M
11.10%
2.70%
GRU + Span Copy Panthaplackel et
2021
250K
17.70%
8.00%
e-HOPPITY Dinella et al.
2020
None
IM
7.30%
1.21%
GRAPHIX
32M
18.20%
9.19%
CodeBERT [Feng et al. 2020
CodeSearchNet
180M
16.40%
5.20%
BraR (Guo al. 2021
CodeSearchNet
110M
17.30%
9.10%
BART (Drain ct al. 2202
Large (54GB)
400M
16.70%
6.70%
PL-BART (Ahmad ct al
(BARa(AAmad
2021
Large (655GB)
140M
19.21%
8.98%
ModeTS-small Wang
2021
CodeSearchNet+
60M
19.06%
10.92%
CodeTS-base (Wag et al. GRAPHIX-P
2021
CodeSearchNet+
220M
21.61%
13.96%
CodeSearchNet Java
32M
19.81%
8.81% %
From T we can see that our models significantly outperform the other edit-based baselines and on par with larger pre-trained models. Specifically, without pre-training GRAPHIIX improves CodeBERT by 1.8% on the small subset and 4% on the medium subset. We observe similar improvement of GRAPHIX over BART. When pre-trained on CodeSearchNet Java, GRAPHIX-P slightly outperforms PL-BART, C--eal on the small but underperforms them on the medium. C5deT5--basl with 220M parameters currently the state-of-the-aar performance on both datasets.
7

---

Under review as a conference paper at ICLR 2022
Table 2: Top-1 exact match (EM) accuracy on the concrete benchmark with and without pre-training
Model
Pre-trained Data
Size
Small
Medium
Transformer DDain et al.
2021
60M
14.60%
3.70%
GRU + Token Copy (Panthaplacke el a.
2021
None
10M
6.80%
N/A
DeepDebug (T5) (Drain ct al
2021
400M
13.90%
3.60%
GRU + Span Copy Panthaplackel
2021
250K
9.20%
e-HOPPITY (Dinella et al.
2020
None
1M
7.28%
1.51%
GRAPHIX
32M
17.87%
9.01%
DeepDebug (T5) Drain et al. 2021
Java (54GB)
400M
16.80%
6,30%
DeepDebug (TS) DDann et al. PL-BART (See below)
2021
English and Java
400M
18. 78%
11.40% %
Large (655GB)
140M
19.81 %
6.37%
GRAPHIX-P
CodeScarchNet Java
32M
19.31%
8.69%
Tableesshows the results of the models on the concrete benchmark. The PL-BART result, which was not reported the original paper, obtained by fine-tuning released pre-trained PL-BART model on the concrete code. We observe similar improvement the concrete benchmark for GRAPHIX- P over GRAPHIX, which is significantly better the edit baselines, LSTM and the Transformer model. GRAPHIX-P is slightly better than DeepDebug (Drain et al. 2021 the small set but worse the medium. Compared to PL--BRRT, GR APHIX-PP performs comparably on the small dataset and outperforms PL-BART by good margin the medium In short, our model works comparably to DeepDebug and PL-BART on the concrete benchmark despite much fewer parameters.
Comparing the results in Table and Table 2 see negligible drop about 0.2 122-0.5 00.5% in accuracy of GRAPHIX from the abstract to concrete code. On the contrary, the accuracy of GRU with span copy (Panthaplackel et al. 202I) decreases by almost half. This demonstrates that GRAPHIX is insensitive to the naming of variables, types and APIs. We also observe a similar trend for PL-BART. These observations suggest that the code abstraction may not be necessary. Additionally, we notice that while the pre-training provides an additional 10% relative gain on the small subsets, GRAPHIX-P does not achieve similar gains on the medium set, which inherently longer and harder. We hypothesize that the synthetic edits used for pre-training might be more aligned with the small dataset than the medium, and more sampling strategies may be needed to bridge the gap.
ANECDOTAL EXAMPLES
In addition to several state-of-the-ant results in EM accuracy, GRAPHIX demonstrates strong inductive biases learning complex bug-fix patterns. In this section, we showcase several bug examples that GRAPHIX is able detect and fix. We show more such examples in Appendix F
public void atoptoo i tontiddttes throws Seour:
It ([Locat LonManager) 1- mull)
locationn lacationWanager. renoveupdates (this);
public static Throwable geURooL (Throwable
null;
Chrowable rootCause
chrowable cause foottanse.gesCausee
(leause null) teause != mootCause)) rootCause cause; cause cause.ge:Cause
return ccotCause;
Listing Missing null check bugs in the samples small/11219 (top) and medium/10509 (bottom).
8

---

Under review as a conference paper at ICLR 2022
Boverride
public void reaol
List-PeoposiLion props "eeieabieeeorrggeeeeeeeooooo int for (cQuantifer quan: this. Shiee.geQQuattteessse {
(pxops.size
props.get setlinkeddd (String) (quant. gptaarg getsourceldd))11) 1-+
public static int mul lint ni, int n2)
return
Listing (top) Off-by-one error in sample medium/11874 (including may cause index-out-of- bound exception) and (bottom) logical bug in sample small/8295.
We manually analyze the generated fixes of GRAPHIX the test concrete benchmark. Since longer edits tend to have lower probability, we normalize the prediction score of each generated fix by the length of the corresponding generated edit sequence. More specifically, we divide the negative log- le-llikiiihod by the edit length and exponentiate the result to obtain the normalized score. Then, we manually check 500 correct and incorrect fixes with highest scores each of the small and medium sets. By inspecting the generated edits, we can easily spot out the code changes in each case. We find that similar fixes have similar edits and scores. This analysis enables us recognize interesting bug-fix fix patterns as well as noises in the data. The patterns range from syntactic fixes such as using equals () instead of or simplifying logic statements to semantic ones such as like adding null check conditions, fixing variable misuses and so Here, we show some exemplary samples of fix patches that match the ground-trutt -tuth in the benchmark. Listing 2 displays two examples of potential bugs where the developers fail to validate the input/a class field. GRAPHIX
not only detect missing input validations (i.e., checking null), it can also return an intended behavior in the second example when the input is null). Listing 3] shows two other examples where GRAPHIX fixes off-by-one error and a logical bug by apparently understanding the method name mul.
We show several instances of incorrect fixes generated by GRAPHIX in Appendix G We note that extra enclosed parentheses () in the examples are artifacts of our parser. Finally, GRAPHIX and GRAPHIX-P share similar inductive biases and hence share similar sets of bug-fix patterns.
DISCUSSION AND FUTURE WORK
In this paper, consider the problem of generating bug fixes using neural model. We present GRAPHIX. multi-head graph edit model that is pre-trained based on deleted sub-tree reconstruction. GRAPHIX establishes the high performance on a Java benchmark. Anecdotal fixes demonstrate that the model is able to detect and suggest fixes for diverse set of bugs and program issues. In particular, GRAPHIX is about 2x smaller than tfate-of-hhe-art Transformer models. Finally, GRAPHIX performs equally well on generating abstract well concrete fixes.
Practical use. The problem of bug detection nuanced, and several times MI. models can be replaced by simple rules. We have shown that GR APAIP can capture semantic bug fixes through dozens anecdotal examples (see Appendix F for more). In addition, we demonstrate in Appendix that can calibrate the model score to achieve increased precision up to 57% by trading-offf the coverage of bug detection.
We anticipate several directions in the future work: (i) pre-train based multiple sub-tree additions and replacements (ii) incorporate more program dependencies into the graph representation and (iii) leverage Transformer and GNNs in unified architecture for the global code context in the sequence.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Wasi Ahmad, Saikat Chakraborty, Baishakhi Ray, and Kai-Wei Chang. Unified pre-training for program understanding and generation. In NAACL, 2021.
Miltiadis Allamanis, Mare Brockschmidt, and Mahmoud Khademi. Learning to represent programs with graphs. International Conference on Learning Representations, 2018.
Uri Alon, Roy Sadaka, Omer Levy, and Eran Yahav. Structural language models of code. In International Conference on Machine Learning, 2020.
Berkay Berabi, Jingxuan He, Veselin Raychev, and Martin Vechev. Thi: Learning to fix coding errors with a text-to-text transformer. In International Conference on Machine Learning, 2021.
Pavol Bielik, Veselin Raychev, and Martin Vechev. Phog: probabilistic model for code. In Interna- tional Conference on Machine Learning, pp. 2933-2942, PMLR, 2016.
Marc Brockschmidt, Miltiadis Allamanis, Alexander L Gaunt, and Oleksandr Polozov. Generative code modeling with graphs. In International Conference on Learning Representations, 2018.
Saikat Chakraborty, Yangruibo Ding, Miltiadis Allamanis, and Baishakhi Ray. Codit: Code editing with tree- breed neural models. IEEE Transactions on Software Engineering (TSE), 2020.
Zimin Chen, Steve James Kommrusch, Michele Tufano, Louis-Noël Pouchet, Denys Poshyvanyk, and Martin Monperrus. Sequencer: Sequence-to-sequuenee learning for end-to-end program repair. IEEE Transactions on Software Engineering (TSE), 2019.
Devlin, Ming-Wor Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In NAACL-HLT, 2019.
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 Learning Representations (ICLR), 2020.
Dawn Drain, Chen Wu, Alexey Svyatkovskiy, and Neel Sundaresan. Generating bug-fixes using pretrained transformers. arXiv preprint (eXXx:2204.078800 2021.
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. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language 2020.
Processing:
Findings, pp.
Justin Gilmer, Samuel Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry, In International Conference Machine Learning, pp. 1263-1272. PMLR, 2017
Claire Le Goues, Michael Pradel, and Abhik Roychoudhury. Automated program repair. Commun. ACM, 2019.
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. International Conference on Learning Representations, 2021.
Hideaki Hata, Emad Shihab, and Graham Neubig. Learning to generate corrective patches using neural machine translation. arXiv preprint arXiv:1812.07170. 2018
Vincent J Hellendoorn, Charles Sutton, Rishabh Singh, Petros Maniatis, and David Bieber. Global relational models of source code. In International Conference on Learning Representations, 2019.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitmik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. International Conference on Learning Represen- fations, 2020.
10

---

Under review as a conference paper at ICLR 2022
Hamel Husain, Ho- Hlo-Hiiang Wu, Tiferet Gazit, Miltiadis Allamanis, and Mare Brockschmidt. Code- searchnet challenge: Evaluating the state of semantic code search. arXiv preprint arXiv:1909.0943:. 2019.
Thomas Kipf and Max Welling. Semi- Semi-supervised classification with graph convolutional networks In International Conference on Learning Representations, 2016.
M. Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension. ArXiv, abs/1910.155 13461, 2020.
Yi Li, Shaohua Wang, and Tien N Nguyen. Difix: Context-based code transformation learning for automated program repair. In Proceedings of the ACM/IEEE 42nd International Conference on Software Engineering, pp. 602-614, 2020.
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. International Conference Machine Learning, 2018.
Chris Maddison and Daniel Tarlow. Structured generative models of natural source code. In International Conference on Machine Learning, pp. 649-657. PMLR, 2014.
Rumen Paletov, Petar Tsankov, Veselin Raychev, and Martin Vechev. Inferring crypto api rules from code changes. ACM SIGPLAN Notices, 53(4):450-464, 2018.
Sheena Panthaplackel, Miltiadis Allamanis, and Marc Brockschmidt. Copy that! editing sequences by copying spans. AAAI, 2021.
Maxim Rabinovich, Mitchell Stern, and Dan Klein. Abstract syntax networks for code generation and semantic parsing. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics ( (Volume I: Long Papers), pp. 1139-1149, 2017.
Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language under- standing by generative pre-training, 2018.
Caitlin Sadowski, Jeffrey Van Gogh, Ciera Jaspan, Emma Soderberg, and Collin Winter. Tricorder: Building program analysis ecosystem. In 2015 IEEE/ACM 37th IEEE International Conference on Software Engineering, pp- 598-608, 2015.
Daniel Tarlow, Subhodeep Moitra, Andrew Rice, Zimin Chen, Pierre-Antoine Manzagol, Charles Sutton, and Edward Aftandilian. Learning build errors with graph2diff neural networks. arXiv preprint / 2019.
Michele Tufano, Jevgenija Pantiuchina, Cody Watson, Gabriele Bavota, and Denys Poshyvanyk. On learning meaningful code changes via neural machine translation. In 20/9 IEEE/ACM 41st International Conference on Software Engineering (ICSE), pp. 25-36. IEEE, 2019a
Michele Tufano, Cody Watson, Gabriele Bavota, Massimiliano Di Penta, Martin White, and Denys Poshyvanyk. An empirical study on learning bug- mixinining patches in the wild via neural machine translation. ACM Transactions Software Engineering and Methodology (TOSEM), 28(4):1229, 2019b.
Marko Vasic, Aditya Kanade, Petros Maniatis, David Bieber, and Rishabh Singh. Neural pro- gram repair by jointly learning to localize and repair. In International Conference on Learning Representations, 2018
Ashish Vaswani, Noam M. Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Neural Information Processing Systems, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova. Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations. 2018.
11

---

Under review as a conference paper at ICLR 2022
Oriol Vinyals. Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Neural Information Processing Systems, 2015.
Yu Wang, Ke Wang, Fengjuan Gao, and Linzhang Wang. Learning semantic program embeddings with graph interval neural network. 2020.
Yue Wang, Weishi Wang, Shafiq Joty, and Steven CH Hoi. Codet5: Identifier-aware unified pre-trained encoder-decoder models for code understanding and generation. arXiv preprint arXiv:2109.00859, 2021.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2019.
Ziyu Yao, Frank F. Xu, Pengcheng Yin, Huan Sun, and Graham Neubig. Learning structural edits via incremental tree transformations. In International Conference on Learning Representations (ICLR), 2021. URL https::/
net ottp://wwweee/tmtmmeeeee/----
Michihiro Yasunaga and Percy Liang. Graph-based, self-supervised program repair from diagnostic feedback. In International Conference on Machine Learning, pp. 10799-10808. PMLR, 2020.
Pengcheng Yin and Graham Neubig. A syntactic neural model for general-purpose code generation. In Proceedings of the 55th Anmual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 440-450 2017.
Pengcheng Yin, Graham Neubig, Miltiadis Allamanis, Marc Brockschmidt, and Alexander Gaunt. Learning to represent edits. In International Conference on Learning Representations, 2018.
Rui Zhao, David Bieber, Kevin Swersky, and Daniel Tarlow. Neural networks for modeling source code edits. 2019.
12

---

Under review as a conference paper at ICLR 2022
Appendix
A
ENCODER AND DECODER
This section describes the technical formulation of the single-head encoder and the auto-regressive decoder. For more details into these two components, we refer the reader to (Dinella et al., 2020 Yao
et al.
202T
A.1
SINGLE-HEAD ENCODER
Formally, given a graph = (V,E) with a set of nodes V and edges E, a single-head graph encoder gives d-dimensional representation of the graph 9 and representations of individual nodes V. Similar to (Dinella et al., (2020), we compute the graph presentations for each edge type (i.e., AST edges, vassabaiible--se edges and successive edges) as follows:
h 1111,,)) =o
Σ
w/Th
Ak E 21,2..... .K]
(1)
(ENN(M)
-(-1== =0 (W3) (P((n "aRt,,0,,4111 (041.2)
"..,,,,.-.,,,,,, 10 + nn))
(2)
where K denotes the total number of edge types, L is the number of propagations. wi' E Raxd and w.'k E Rdd xd are the network weights. (v) denotes set of neighbors of e that are connected to with the edge type k. These formulae give the node embeddings
(1! Joev for all nodes v E V while the graph representation is an aggregation of h for all More precisely, we use max pooling to combine h for each I and average the L + 1 resulting vectors to compute the final graph representation g.
The initial embedding h vector of node v is set as the sum of the embedding of its node type and node value if the value exists. The node type and value embeddings are stored in separate tables.
A.2 TREE EDIT OPERATIONS
GRAPHIX is sequential decision process that iteratively performs tree edits on the partial tree at each step. Following (Brockschmidt et al. 2018 Yao et al. (02T), we employ a grammar-based tree decoder to ensure the grammatical correctness of each edit action. To that end, construct an abstract language based on JavaParser 5 The grammar includes a set of primitive and composite types (c.f. (Rabinovich et al. 2017 Yin & Neubig 2017)). Each composite type (c.g., stmt) has a collection of production rules such as Expressi onStmt (expr express i on) where each rule is represented (e.g., expr), the field name (c.g., express in) and the cardinality of the field as single, optional, or sequential. The cardinality indicates the number of children a node accepts as grammatically valid children. Based on the grammar, we define the following primitive operations:
constructor with list of field arguments. Each argument has the field type
DELETE operator takes tree node n and removes it from the tree. As a result, the corresponding sub-tree and the node n are removed. However, removing node that corresponds to single field results in grammatically invalid tree. For instance, removing node ClassType in step of Figure caausss the AST to have no type, which is invalid. To ensure the syntax validity at each edit step, after the removal, we add a Dummy node as a placeholder with no node type or value. Another benefit of Dummy node is to reduce the uncertainty of the node selection in the subsequent step.
ADD operator adds a node to the graph. Under the grammar and the dummy node mechanism, the addition of a new node occurs in two cases. In the first case, we add new child to parent node of a sequential field. For example, the node of type (stmt* * stat ements) s) may have an arbitrary number of children. In this case, adding node requires the location of the parent node and the position to be added in its children list. In the second case, we add a new node into the position of a Dummy node (adding non-terminal node Express ionStmt in Figure I in step 4). Similarly to
https::/joraparser.orgg
13

---

Under review as a conference paper at ICLR 2022
the DELETE operation, once adding non-terminal node, follow the underlying grammar specified by the added production rule and instantiate the set of dummy, child nodes at the newly added node. The ADD operator is also used to populate empty terminal nodes with actual node types and possible values. Note that while constructing the original tree, we also add Dummy at the empty fields.
COPY operator is introduced simplify and shorten the edit sequence. While making code changes, the developer often moves code one place to another. Such changes can be translated directly on the AST by copying the corresponding sub-tree from the input AST. In essence, this operator locates the target position similarly to the ADD operation and then copies the sub-tree from the original tree to the target position of the current tree in one single step. For example, the subtree for the assignment expression data newData a in Figure I at = 2 is copied to the new position in step 6.
Finally, the _O_OP action is used to automatically terminate the iterative tree editing procedure. After this step, the remaining dummy nodes will be pruned.
A.3 AUTOREGRESSIVE TREE DECODER
Given the graph representation gr of the program at step / and the edit history #;-1 from the previous step, an LSTM-based tree decoder to update the state s, (L8TM(g(((t1)). Based on the updated state 8;, the model predict edit actions where each node edit includes a node selector, an operator predictor and type/value predictor. The node selector selects node loc,, then the operator predictor decides which operator op; to apply the edit on (oc, among the four possible operators (DELETE, ADD, COPY, NO_OP). For the ADD operation, the type predictor further determines the node type/label type, for the newly added node. For terminal nodes, the value predictor computes the node value value, The probability of an edit is then decomposed as
p(as) st) = p(locy|ss))) )p( op, 1oc))) ttype,/s, op,, loca loca)) ((aaa))psaaeeessss.. op,: loca, type,). (3)
We provide more details into one decoding step below:
Node selection. For node selection, we employ a pointer network (Vinyals et al. 2015) since different graphs have different number of nodes. For ADD, the selector either selects sequential-fiet -felld node or a Dummy node. In the first case, it determines the parent of the node to be added and its left sibling. Therefore, we further decomposte p(loca| [x)) p(siblinge 8r, parente) (aoe)))(((cc, (loc////r (8t, parente). If parent, does not have any children, the left sibling node is considered as parent, itself. We compute the logits by taking inner product between the edit history 8; and the node embeddings nu- We select the node that maximizes the inner product. After selecting the node, we update the state with additional LSTM call s, = (esSM((b((ooc))) where amb(loce) is the node embedding of the selected node locz-
The operator prediction regular classification problem with four labels (DELETE, ADD, COPY, NO_OP}. We calculate the probability of operator op, using a softmax layer such that p( op, [ loc,) = softmax (W 8; + bop). After that, we again update the state via s, LSTM(cmbb
Operator prediction:
( where emb(op) is the embeding of the selected operator op..
Type prediction. This module assigns a type type, to the newly added node in the AST. Since the number of types is specified a priori by the underlying syntax language, we simply treat the type predictor as a classification problem over all possible types while masking out the impossible choices. We calculate the probability of operator op, using a softmax layer such that p( type,, st loc;) = softmax W &t + D We update the state via 8, = LSTM(emb( (type,))as [s:)) where emb (type,) is the embedding of the newly predicted type type,-
Value Prediction. If the newly added node is terminal node, the value predictor assigns to it a value value, The possible values are chosen from the union of the local values present in the input (i.c., local value table) and the global values that frequently appear in other programs. The local value embeddings computed by the graph encoder while the global value embeddings are stored globally in the value embedding table. We compute the scores by simply taking inner product between the state s, and the value embeddings and select the one maximizing the score. Finally, we update the state via 8; = LeST(eembl vulue;){s7) where emb( value:) is the embedding of the value valuez.
The decoding process stops once encounters NO_OP reaches the maximum number edits.
14

---

Under review as a conference paper at ICLR 2022
B COMPARISON OF TREE DIFFERENCING ALGORITHMS
Table 3 shows the advantages of structural, grammar-aware tree differencing with copy operations in GRAPHIX over JSON differencing used in HOPPITY.
Table 3: Comparison of the edit sequence length between JSON differencing and grammar-aware
differencing algorithms.
Differencing
Type
No. of tokens
Mcan
Median
75th quantile
Small
< 50
14.1
6
20
JSON differencing
Medium
50-100
35.2
14
41
Combined
100
25.2
9
31
Small
50
5.4
2
7
Grammar-aware differencing
Medium
50-100
8.5
Combined
100
7.1
3
9
medium/6715
80verride
2
public boolean create (FOJO. user) throws SQLException
stmt connect. pronecttpreparrettteemme (" INISRTRT INTO User ...")>
stmt stmt.aetString( (1, user.getPseudo )));
stmt semt. (2, user.getPassword()
6
stmt stmt.setString (3, user.getEmail(1) (
7
stmt stmt.exxcute@ppdatee
stmt cont.clloee))
System, out. pwintt.ininnee..m...mm. return true;
JSON differencing edits
Remove the statement in line 10: return true;
Remove scope: System.out
Renove the arguments in printin
3.
Renove the name printin
4. Replace the remaining MethodCallExpt with BooleanLitera exxr
5. Add true
6. Replace ExpressionStnt with ReturnStmt
Grammar-aware differencing edits
1. Remove the statement in line 9: System. out pwinttriint.....
Listing 4:
An example of code change where the println statement in line 9 is removed. The structural edit is straightforward with one remove step. The JSON differencing edits are less natural: the algorithm first removes line 10 and gradually changes line to re-add the return true statement.
We can see that the structural edit differencing results in much shorter edit sequences average. Examination of edits shows that structural edits also more meaningful. We show an example of code change and edits in Listing
C IMPLEMENTATION AND TRAINING DETAILS
We implement GRAPHIX with PyTorch based the open source implementation of HOPPITY (Dinella et al. 2020). train GRAPHIX on a machine with 8 V100 GPUs, each with 32GB memory. We batch size 5 on each GPU both in pre-training and fine-tuning. We the Adam optimizer
15

---

Under review as a conference paper at ICLR 2022
and linear learning rate scheduler, used in Transformer (Vaswani et al. 2017). We set the initial learning rate 10 and the warmup steps corresponding to epoch. We pre-train GRAPHIX for 10 epochs for 10 days. We fine-tune GRAPHIX for 20 epochs with the maximum number of edit steps being 20. The fine-tuning takes about 2 hours per epoch on the small subset and about 3.5 hours per epoch the medium set. We choose the best model checkpoint using the validation set and report its top-1 accuracy on the test set.
D HIGH PRECISION REGIME FOR GRAPHIX
As shown previously and in Appendix F GRAPHIX is able to learn meaningful and interpretable code patterns, leading to wide range of interesting bug fixes. Indeed, the actual kinds of fixes have not been studied thoroughly for the pre-trained Transformer models. Moreover, we show that our model can be of potential use in practice by trading-off the recall for increased precision. To demonstrate that, we show the impact of calibrating the prediction scores to achieve such a trade-off.
Table 4: A trade-off between the accuracy and bug detection coverage.
Theshold 0.5
0.6
0.7
0.8
0.9
Accuracy 29.27%
38.12%
47.37%
56.59%
52.38%
No. predictions 1882
926
418
129
21
Table suggests that we can achieve higher accuracy at the cost of lower prediction frequency. For example, the model can suggest 418 most probable bug fixes at 47.37% correct patches, the threshold 0.7 on the prediction score.
E ABLATION STUDIES
E. EFFECTS OF THE GRAPH MODEL SIZE AND PRE-TRAINING
In Table 5 we compare GRAPHIX with HOPPITY using about 1M parameters. Here, GRAPHIX- B refers to the proposed GRAPHIX model with 1M parameters. The results show that GRAPHIX significantly better than HOPPITY because of the ASDL-guided decoding and the grammar- aware shortest edit differencing. To be specific, GRAPIIIX edits are significantly shorter and more meaningful than JSON differencing edits (see Tableßaand Listing in Appendix[Bi [Bor the comparison). Moreover, the ceammar-constraing decoder reduces the uncertainty of predicting edit properties each decoding step.
Table 5: Effects of the graph model size and pre-training GRAPHIX.
Abstract Small
Concrete
Setting
Model
Size
Medium
Small
Medium
No pre-training
e-HOPPITY
1M
7.30%
1.21%
7.28%
1.51%
No pre-training
GRAPHIX-B
1M
12.40%
5.34%
11.21%
4.31%
No pre-training
GRAPHIX
32M
18.20%
9.19%
17.87%
9.01 %
With pre-training GRAPHIX-P
32M
19.81 %
8.81%
19.31 %
8.69%
We also study the effects of the graph model size and pre-training GRAPHIX. Table suggests that the multi-head encoding leads to about 50% relative boost accuracy on the small, abstract subset and almost 2x boost the abstract, medium. The improvements consistent code. can be seen that the pre-training gives an additional 10% relative gain on the small subsets but does not help on the medium sets. We explore more pre-training options and model sizes in future work.
the concrete
Next, study the role of our proposed multi-head architecture.
16

---

Under review as a conference paper at ICLR 2022
E.2
ROLE OF THE MULTI-HEAM ARCHITECTURE
Table 6: Role of the multi-head architecture when the dimension d and the number of heads H vary.
Abstract
Concrete
Model
H
Size
Small
Medium
Small
Medium
GRAPHIX-B B
1
128
1M
12.40%
5.34%
11.21%
4.31%
256
4M
14.94%
7.07%
16.58%
7.79%
4
128
4M
15.37%
7.88%
16.79%
8.34%
1 566
32M
14.63%
6.52%
15.95%
6.63%
GRAPHIX
8
256
32M
18.20%
9.19%
17.87%
9.01
Following (Dinella et al. 2020), we use the GIN depth of 4 for all the experiments. To understand the the impact of the number of heads compared to the latent dimension, we experiment with the latent dimension d and the number of heads H such that the corresponding model sizes comparable. can be seen from Table 6 that the multi-head models outperform the corresponding single-head counterparts with comparable sizes, for both 4M and 32M models. Moreover, increasing the model capacity with d improves the performance as increases from 128 to 256 while the model with d 566 tends overfit the training data and performs poorly on the test In summary, our experiments show the benefits of the proposed multi-head architecture.
E.3 PER-LAYER VERSUS LAST-LAYER MULTI-HEAD
We implement par-layer multi-head architecture with head averaging and GIN, following the idea in GAT (Veličković et al. 2018). In this architecture, each head computes a linear projection of the input before layer is the same as adding two more consecutive linear layers before that GIN layer: the first layer stacks the linear projection matrices into one weight matrix whereas the second has fixed weight and computes average. We take the average of the head outputs instead of the concatenation for computational reason.
fed to the respective GIN layer, so without attention having multiple heads per
We compare this new model with a single-head model of the same latent dimension (d = 256), and our ensemble-style multi-head models (with 4 and = heads). The results and configuration of each model are shown in Table 7
Table 7: Effects of the per-layer versus last-layer multi- head architectures.
Abstract
Concrete
Head type
H
Agg.
d
Size
Small
Medium
Small
Medium
Single-head
N/A
256
4M
14.94%
7.07%
16.58%
7.79%
Last-layer MH
4
Concat
128
4M
15.37%
7.88%
16.79%
8.34%
Per-layer MH
Average
256
6M
15.78%
7.40%
16.18%
7.93%
Last-layer MH
Concat
256
32M
18.20%
9.19%
17.87%
9.01%
(GRAPLII)
We can see this model performs slightly better than the single-head model thanks to the additional multi-head layers across the datasets, but it is worse than GRAPHIX with 4 heads the end and 2M fewer parameters, except for the abstract, small dataset. Along with the previous empirical study on the width, this experiment demonstrates the benefits of the proposed multi-head architecture over purely increasing the graph neural network's depth or width.
F MORE ANECDOTAL EXAMPLES
show some more bug fixing and code refactoring patterns learned by GRAPHIX. In some cases, we show the pairs of buggy code and fixed code. In other cases, we only highlight the changes with added text in green and deleted text in red. A few long statements replaced with "..."
17

---

Under review as a conference paper at ICLR 2022
F.1 SIMPLIFYING LOGIC EXPRESSIONS
Before
After
small/6886
public boolean isEmpty if ((first) == null) return true;
public boolean isEmpty ()
return (first) == null;
return false;
medium/7382
80verride
public boolean onTouchEvent (android, view. MotionEvent veee ev)
super.onTouchEvent (ev);
dragielper. prapieeepepproossseeeeeee pro.essTouchhverreeeeeeee (ev);
ViewGroup parent = ((ViewGroup) (findBottomvies (this, y) getearrent ());
return
false II (parent == (this))
F.2 FIXING OFF-BY-ONE ERRORS
Before
After
small/6229
@0verride
8Override
public boolean hasNext () { return ((cursor) + 1) (batches);
public boolean basNext ()
return (cursor) < (batches);
small/9321
public boolean hasNext () {
public boolean hasNext ()
return (FrameIndex) < (ccontt - 1); return (frameIndex) < (count)
medium/11106
public static boolean isFowerOfTwo (long number)
if (number 0) {
throw new
(...);
if ((aumber & (-rumber)) number) {
return true;
return false;
18

---

Under review as a conference paper at ICLR 2022
medium/10998
public int run() () {
int exponent 1000;
BigInteger base E.glnteger..allpe ;
BigInteger value = BigInteger.2BNe 2ERO;
int sum = 0;
value base. (exponent);
String str value. wostringgtggnnoo O)
for (int i 0; i ((str. length - 1)
(str. length i++)
sum += ((int) ( ((ttr,charA) (1)) (0"));
return sum;
F.3 USING EQUALS INSTEAD OF FOR STRING COMPARISON
small/9253
public TimelineConfig BB ia)
for (TimelineConfig channed : channels)
if (channel.get () Lequals (id) return channol;
return null;
small/6752
private Customer FindCustomer (String customerCode) {
for (Customer : eustomers)
if (c. (e.getCode () lequals (custome return o;
return null;
small/10790
public boolean checkUsername (String username)
for (Model.Use) usezieqpaitorr.fiineee ())
if (user. Name () eequls (username)
return false;
return true;
19

---

Under review as a conference paper at ICLR 2022
F.4 CORRECTING RETURNED OBJECTS
medium/7800
private static Grouuaaaaa generateGroups (int count) Gist<GGrupDaaa>> groups new ArrayListt {
for (int i 0; i count; i++) { groups. add (new GroupData () withNNme (...));
return
null
groups;
medium/11925
80verride
public String toString () {
String str "Symbol Table list:";
for (int nestinglevel; (-1) < (nestinglevel); i+4) {
str += ("Nesting level i) ":\n";
str += tables ()Stringg);
str;
F.5 FIXING CONDITIONS
medium/9887
public View getviewiithConf (String viewName)
if (vviewamee null) & (viewName- 1sEmpty())) (1))) { for (fi. oskooskkk..... dom.:il.oooaaa..mmoooom......o map, viww. View item list)
if TrtewName.equar Attem.geNName )))) return item;
return null;
medium/9181
private double get.StepMovmment
(gg.eetics..ussschhennoooeeeeeee p) {
double steps = 0; double intervalCount 0; for atsaa..tll.Arraylissse
measure p.melodyIntervals)
for (int interval measure)
interval = Math.aba (interval);
intervalCount
if ((interval >= 1) II (interval <= 2)) {
steps += 1;
if (intervalCourt 0) { return 0;
return steps / interval Count;
20

---

Under review as a conference paper at ICLR 2022
medium/11246
public boolean insertBudget (final String name, final int max) {
android. database wtt.tte..liieeeaaaaaaaaaaaaeeeaa
db getWritableDatabase ()
ContentValues contentValues new ContentValues contentValues. put hrtpe//all...ppttttteleeeeeeeeee contentvalues. put (DBlelper.. (DBielpper. Budge:DDieedee MMX max); final long newId
name);
db. db.insert htw.:pper..uuggttDDD.... TABLE, null,
contentValues);
return newld
G NEGATIVE EXAMPLES
While learning meaningful frequent change patterns, GRAPHIX also confidently suggests incomplete and/or incorrect bug fixes. We provide three such examples below. For each example, we show the buggy input, the generated fix by GRAPHIX and the ground-truth fixed code.
In Listing 5 GRAPHIX suggests quick fix that replaces with but does not go beyond adding logical to the second condition. Since GRAPHIX can add ! in medium/9887. Section [55 when trained the medium dataset, we suspect that the model might not have seen many i s Empty patterns on the small set. Note that, even if the model could do that, the generated fix and the ground-truth label with two nested if conditions would match, despite the logical equivalence.
Buggy code
80verride
protected void unSaweeinstancceetttaoaaaaoaao (androdd, os. Bundle savedInstance) super.onSavee aeperr.onSeeensttarcetttttt (tarraannnsStttttaaaaaaaaaaaaaaa (savedInst
if (((listData) != null) (Lis:Data. ())
ptaeeennsstanceepttssiilla ("HEADER" listData);
Generated fixed code
80verride protected void aa (androidd, Bundie Bundle savedInstance)
supor.onSaaeiIntaacceet (ag.aaeeettttttttttotaaaaaeaaaan (savedInstance)) if (((listData) I= mull) & 1sEmpty {
savedInstance putserial aareeddittanco.pptttalalaalall ("HEADER", listData);
Ground-truth fixed code
80verride
protected void anSaaeenstanneeSsateeeee (androod.. Bundle savedInstance)
auper..nnSavenntaareee aasereeetttttttttttaaaaaaeeettte (savedInstance))
if ((listData) != null) {
if (! (1istData 1eEmpty ) {
savedInstance wtwp:aannc...ttttsaaallaaaaaaaaa ("HEADER", listData);
Listing 5: Test sample small/6783 in the benchmark.
Listing 6 shows another incorrect fix by GRAPHIX. This example is nuanced because could be difficult to know in the first place whether the original code is buggy
without more information.
The last example, shown in Listing 7 is similar to the pattern GRAPHIX correctly learns in small/6886, Section F. and many others observe in manual analysis. In this case, the model simplifies the
21

---

Under review as a conference paper at ICLR 2022
logical return expression in the input code, but that does match with the correct fix. Again, it difficult to fix this kind of issues unless we have a way to represent the global context in the class and more broadly the whole project.
"Buggy" code
private boolean isvalidInieng (android. text Editable 8)
return (! trespectatteeennennnhh)) II ( ((s lestte ()) <= (maxiength))
Generated fixed code
private boolean isvalidInLength (android, tet..ttttabe.eeeeeeee s) return (! (respectaattermleenghh)) & ((s. ()) <- (maxliength))
Ground-truth fixed code
private boolean isvalidInLength (android, text Editable s)
if (coapocPattoornonngth & ((8.length ()) (maxLength)) ) return false;
return true;
Listing Test sample small/9672 the benchmark.
Buggy code
@0verride
public boolean onkeyUp (int keyCode, KeyEvent event) if ((keyCode (KEYCODR_ (OL.LKK__OOOOO
|1 (keyCode (XEYCODE, VOLUME (F) return true;
return false;
Generated fixed code
80verride
public boolean onkeyUp (int keyCode, KeyEvent event. {
return (keyCode EEPCODR_VOLUMM__DN
(keyCode IKRYCODE_VOLUR__LE
Ground-truth fixed code
80verride
public boolean onKeyUp (int keyCode, KeyEvent event)
if ( (KkyyCode = (XEYCODE_ LOVODDE_VOLUME_DOMA
|I (keyCode = (KEYCODE_ (XSYCOB__VLLMEE_U)) VOLUME_UP))) return true;
return super. onKeyUp (keyCode, event);
Listing 7: Test sample small/7677 in the benchmark.
H EXAMPLES OF HOPPITY
Finally, show representative examples learned by e-HOPPITY in the decreasing order of the scores.
22

---

Under review as a conference paper at ICLR 2022
small/11245
protected
public final int getRetsyMaxtteentts ()
return retryNaxAttempts;
small/6034
public java.lang, Prra.lang.Strinn String [] getText {
return this. text;
small/10646
80verride
public projectx. prejeexxxpersistencee www.ssttenneeeetiiii..........ee entities enteties..aatgooyy findByid (long id)
return db. db. E....aaaatteeeyyyyaaadl))
small/5862
public models. IlEntity save (models. IiEntity entity)
throws CxientExooption, ParseException {
if (entity == null) return null; if (atuuhhettcctte() return null;
models. TIEntilyy response postService, save (entity))
return responsej
return post.Servi ce save int.ity)
small/11352
80verride
public float computelionus] () {
float bonus (athis. (this. ) 1000;
return bonus;
medium/10324
@java.lang.a .igg.Ovee Override
public boolean onOptions twe.melllel.....ee...e...ee ected (android view. Men.. Item item)
boolean retval true;
switch (item.get Ieee iteml
and
onBackPressed();
break;
case R. R. 8.id.chhngg__pssworr.
cbangekcountPeeevrraccccom
break;
case R.id. pe..d.deeete_accoom
break; default
retval super. suppr..nngr.ioosteeeeeeeeee... (item);
break;
return retval;
23


Reviews:
[{"review_id": "nFbMJvYc0Yp", "reviewer": "Reviewer_AZoW", "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": "Strengths:\n+ The problem formulation of mapping a graph to a series of AST edits lends itself naturally to modeling source code, and repairs in particular.\n+ Incorporating a large set of baselines and variations helps contextualize Graphix' performance.\n\nWeaknesses:\n- Contributions over prior work are relatively slim and hard to assess because the work lacks a comprehensive comparison.\n- The efficacy of the proposed multihead GNN scheme is not adequately ablated.\n- Some concerns about the scalability given the need to encode the entire tree at each intermediate step.\n\nThis work explores a promising direction, injecting richer inductive bias into neural models of source code and its edits. The scope of its technical contributions is rather narrow and although the paper includes a fair set of comparisons and ablations, their practical usefulness is difficult to assess because several key comparisons are missing. Please focus on these in the response/future revisions.\n\nThe first main contribution over Hoppity is the use of a multi-head scheme in the GNN encoder. While the name might suggest otherwise, this is an ensemble of 8 independently trained GNNs whose final states are concatenated. This naturally increases the parameter cost of the GNN by a factor 8, which requires ablations with models of the same size. The paper only offers a few such comparisons, all of which compensate by equipping the non-multi-head model with a larger hidden dimension, which is somewhat naturally prone to overfitting. This really calls for another variant that instead increases the layer count; that number is set to a surprisingly low number (4) in this work, and it seems entirely plausible that using an ensemble would compensate for this depth rather than width. This hypothesis needs to be tested. Also consider combinations of increasing both depth and width.\n\nThe second contribution is the ASDL-guided decoder. This aspect is only ablated through comparison with a small instantiation of Hoppity in Table 5 (E.2., where it should be made more clear that GRAPHIX-B refers to a single-headed model). This points to a larger problem: Hoppity is never analyzed with more than 1M parameters, despite Graphix using 32M by default. Comparisons with Graphix-B (also using 1M parameters) need not translate to the higher parameter domain. This is especially relevant since the multi-head idea discussed earlier does not seem quite as impactful, perhaps especially when properly ablated, nor does the pretraining (as evidenced later), as the ASDL contribution here. A similar problem is present in E.3. where the per-layer and last-layer performance is virtually identical in the middle two rows, so why was per-layer not evaluated at 32M parameters? (And why only using averaging?). On a smaller note, the runtime cost of operating Graphix vs. Hoppity should be reported and considered as well.\n\nOverall, the paper uses a natural approach to this task, but much of it is similar to prior work, and the new components feel inadequately analyzed. Please provide at least equal comparisons of Hoppity and one or more deeper non-multihead Graphix models in the 32M parameter domain. Besides these salient issues, several more problems, some minor and others moderately significant, are identified below.\n\nDetailed Comments:\n- The first contribution on page 2 seems to claim a very specific \"first\". Was the goal to claim it as the \"first medium-scale graph edit model\" and list the rest of the sentences as its properties?\n- The motivational example is rather generic and does not really articulate why Graphix should work better than other edit-based methods. That edits (and graphs) are a better formalism has been shown quite extensively in prior work (e.g., Ding et al., ASE'20, or many of the cited works).\n- The idea of using multiple heads in graph encoders is naturally reminiscent of Transformers, and more specifically of relationally biased attention such as proposed in RAT (Wang et al., ACL'20) or GREAT (Hellendoorn et al., ICLR'20). This probably deserves a comparison.\n- Reinstantiating and encoding the program graph on every edit would seem to present major scalability problems, especially on longer chains of edits. Please analyze and discuss.\n- It is not quite clear whether the ensemble-of-graphs model is meant to be a contribution in general or just for source code; the former would naturally require more analysis on different datasets, but the latter probably calls for a discussion of why we expect this to just/primarily be relevant for code.\n- The contribution of pretraining seems quite slim; performance only increases a little on the Small dataset and actually decreases on the Medium data. The latter probably deserves more analysis if this is to be considered a part of the contribution of this work: did you attempt to pretrain with removing larger subtrees?\n- The introduction and conclusion decidedly overpromise on performance, claiming that Graphix performs well and is 10x smaller than recent models -- those recent models also significantly outperform it in many settings, and models like PL-BART are just 4 times larger than Graphix (much less than the 32x difference of Graphix with Hoppity).\n- The examples in section 6 suffer from the same problem as the motivation: they do not shed any light on why the specific additions of Graphix over comparable models are helpful.\n- Why are most baselines in Table 1 not evaluated on the concrete setting?", "summary_of_the_paper": "Automated program repair benefits from knowledge of its many properties, which includes its inherent (parse-)tree structure and graphical properties such as data-flow. This work proposes a graph-based encoder coupled with a tree-edit decoder, and optionally pretrained on a tree-based objective comparable to masked language modeling. The resulting model efficiently leverages relatively few parameters to achieve near-SOTA performance on a benchmark compiled from real-world bug fixes.", "summary_of_the_review": "The work proposes two modeling contributions over prior work, neither of which is ablated quite carefully enough, primarily in terms of comparing models of more reasonable size. The eventual results are not particularly strong compared to many other baselines, which, while equipped with more parameters, also use models that scale better with larger parameter budgets.", "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": "63rwv9BXF84", "reviewer": "Reviewer_iXHo", "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": "## Comments\n* It is unclear to me what it means that the state of the art was not beaten. I am missing a discussion on why the presented work is still relevant despite that.\n* The anecdotal examples are not compared to the kind of results other approaches give, so it is unclear what to make of them. \n* Repeatedly, the claim is made that the model is more than 10x smaller than “current large scale sequence models” but out of the evaluated baselines only “BART” is that much larger. The presented approach is even outperformed by CodeT5-small, which is less than 2x as large.\n* I would have liked a short discussion on how accurate you think it is to detect bug fixes by filtering for “fix”, “bug”, “error” and ”exception” (page 6).\n* “To build the final dataset, the authors extracted about 10M GitHub commits whose messages textually match one of these (“fix”, “bug”, “error”, and “exception”) patterns.” -- Remove “,” before the “and” (page 6)\n* What is the reasoning behind having exactly 600 nodes (page 7)?\n* Table 1 might benefit from a visual separation between edit based and sequence based approaches, maybe using color?\n* “Additionally, we notice that while the pre-training provides an additional 10% relative gain on the small subsets, GRAPHIX-P does not achieve similar gains on the medium set, which is inherently longer and harder.” Seems a bit euphemistic as the results got slightly worse.\n", "summary_of_the_paper": "The paper proposes a new approach to abstract syntax tree-based automatic program repair. The novel technique called deleted-subtree reconstruction is based on dropping parts of the syntax tree and training the model to grow them back. The method is evaluated against edit-based and sequence-based approaches, where it outperforms only the edit-based ones.", "summary_of_the_review": "## Strengths:\n* very well written and clearly structured text\n* good motivating example\n* interesting approach in scope of the conference\n* gives a concise intro to previous work and ties back throughout the paper\n* achieves respectable performance at comparable small model size\n\n## Weaknesses:\n* underperforms in terms of the state of the art\n* anecdotal examples offer very limited insights in current form\n* approach mostly orchestrates existing architectural concepts with little actual novelty\n", "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": "5i0QMUgu3t", "reviewer": "Reviewer_z3GX", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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 is an ambitious paper that tries to pack a lot in: between the main paper and the appendix, the authors introduce a (non-trivial, graph-aware) model; a pre-training regime for the code repair problem; quantitative evaluations against many benchmark models; and qualitative examples of some code repair predictions. I really do admire and appreciate the effort that went into this work, which seems significant!\n\nHowever, the net effect is of many, many parts to this paper without a convincing demonstration of model novelty or of significant improvement to the SOTA on the provided baseline. I provide more details below: \n\nStrengths:\n1. Important and interesting application. Program repair is clearly useful, and the structured task also bears close relation to other tree and graph structured tasks (knowledge graph and structured schema editing; protein editing; language and grammar correction) that are clearly of interest to many. \n2. Model is structure aware and predicts graph edits - an interesting choice with downstream possibilities. The authors present comparisons both to SOTA models that are not generally graph-aware (code pre-trained versions of BERT, Transformers, and T5) and at least two explicitly graph/AST-based models (GraphCodeBERT , HOPPITY). Unlike all the models evaluated except HOPPITY, the authors model is both structure-aware and predicts explicit edits to graphs, which feels like an interesting feature that may allow it to integrate more easily with other, non-neural systems (like a linter). It also outperforms the HOPPITY baseline by a large margin.\n3. Extensive evaluation efforts against many comparable models. The authors compare their model against many SOTA models on two versions of the same dataset; and provide additional ablations on several parts of the model (eg. number of graph encoder heads) in the appendix.\n\nWeaknesses and/or concerns:\n1. Model novelty. The model architecture seems very closely based on the HOPPITY baseline: the primary change seems to be to the multi-head graph encoder (which itself uses an existing GIN network for each head). While it’s exciting that this addition improves over the original, the resulting model therefore doesn’t seem to introduce a fundamentally new idea: it also encodes graphs, and predicts edits to them. As a presentation nit, the bulk of the model architecture itself (beyond the ‘multi-head’ change) is described in the appendix.\n2. Quantitative evaluations show marginal improvement at best in comparison to the large pre-trained models. I’d further break down some comments on the qualitative results section:\n* The authors heavily emphasize that the ‘smaller number of parameters’ of their model in comparison to the best-performing SOTA. This feels marginally interesting -- and the ‘CodeT5-small’ model seems to perform very similarly to the model in this paper, with about the same order of magnitude of parameters. In fact, all of the best performing pre-trained models seem to perform about the same.\n* The evaluation omits a comparison to the closely related Yao 2021 model that is cited throughout the paper.\n* The pre-training regime, which is presented as a contribution of this paper, does not seem to produce markedly stronger results. Further, for a fair comparison, it might seem valid to apply the same pre-training regime to some of the other models (like HOPPITY; or the Yao 2021 model if that was added.)\n* Presentationally, a good deal of space is taken up by discussing a quirk of the particular dataset evaluation chosen (the abstract vs. concrete versions of the dataset.) As it turns out, the performance of all of the better-performing pre-trained models seems to be about the same between these. This is useful knowledge for future users of this dataset, but not particularly enlightening for this paper. It seems like this space might have been better used with evaluation on another code repair dataset or domain. \n\n3. Qualitative evaluation is intriguing but doesn’t yield clear conclusions. In particular, I’d be looking for evidence that ‘GRAPHIX demonstrates strong inductive biases in learning complex bug-fix patterns’ - or otherwise, some conclusion on the kinds of bugs that GRAPHIX tends to fix (largely syntactic or catchable by a linter? Requiring multiple edits in graph-space? Concentrated on specific kinds of operators?). One possibility is hand-coding the analyzed edits to categorize them and summarizing the results: without that, these examples are interesting but inconclusive.\n\n4. Pre-training regime is not particularly novel. The authors suggest deleting elements of subtrees from existing code and reconstructing them. This is perhaps given more space in the paper than necessary, and offered as a contribution. The significance of this is a matter of reviewer opinion; I did not personally find it sufficiently novel.\n", "summary_of_the_paper": "This paper presents a model over sequential structural tree edits, used for program repair based on ASTs. The model itself uses a graph encode and decoder to predict the sequential tree edits. The authors also introduce a method for pretraining the model on existing (non program repair) code data: they delete subtrees of arbitrary size from the code, and predict their reconstruction. The resulting model performs comparably to several other state of the art code repair models on the Patches in the Wild Java repair dataset, but with fewer parameters than several of the best-performing pre-trained models (CodeBERT, CodeT5).\n", "summary_of_the_review": "In short, while I appreciate the significant effort that went into this paper, I found it comprised of many parts that fell just short of convincing execution. The model architecture presents only minor changes over an existing one; the quantitative evaluations show only minor improvements over the SOTA (and the authors rely heavily on the qualified claim that they are the best performing ‘mid sized model’ to distinguish themselves, a claim only somewhat supported, given the t5-small model); and present inconclusive and hard to interpret qualitative results. ", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4zYW0y-PnE", "reviewer": "Reviewer_V4AB", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "### Pros\n\n- The paper tackles the task of program repair, which is relatively new and can have practical impact. Although solving a very hard problem, the work is able to outperform various baselines and have on-par performance with very large models.\n- The proposed architecture is able to generate longer graph edits which can inherently fix more programs.\n- Empirical study covers many recent works and is fairly comprehensive.\n- The anecdotal examples as well as the examples provided in the Appendix are indeed interesting.\n\n### Cons\n\nMajor\n\nA. Although claimed to be a novel pre-training task, it is not THAT novel. Moreover, although \"masking tokens\" is natural in pre-training sequence encoders, \"masking sub-trees\" on AST is essentially just asking the model to do \"missing code prediction\", encompassing only a small subset of general program repair samples. The pre-training task would be far more \"novel\" if more thoughts has been put into generating the pre-training dataset. For example, how to generate data for pre-training other edits such as copy, remove, and update.\n\nB. Empirically, pre-training is costly (according to the Appendix) but not giving a lot of performance gain (<2%). The problem is much worse on medium sized data. Here are two questions:\n\t 1. Why is pre-training only done on \"sub-trees between 2 and 6 descendants\"? How about increasing the size in order to cover longer edit sequences during pre-training? Is it possible to add such an experiment?\n\t 2. (Related to A) Is it because the pre-training task only asks the model to predict a sequence of addition operations? Can we add more diverse tasks to let the model to predict a variety of edits?\n\nC. Multi-head graph encoder does not sound too novel to me.\n\n\nOther Issues\n\n. Miss related works: \n\nTFix: Learning to Fix Coding Errors with a Text-to-Text Transformer\n\nLearning semantic program embeddings with graph interval neural network\n\n. The last paragraph in Section 4.1 shows that there is a single-head \"base\" model, which is not mentioned in any experiment in the main paper. I found the \"base\" in Appendix but it would be better if you move this description into Appendix as it is not that relevant. Alternatively you can also put the \"base\"  model and its performance inside Table 1/2.\n\n. Listing 2 Top: the code is not valid if the highlighted green part is removed. What is actually the before and after of that code snippet?\n\n. The paper claims \"these observations suggest that the code abstraction may not be necessary\". Despite finding that the argument is pretty weak, I also don't think \"code abstraction is necessary\" in the first place. For example, with abstraction one would not find the fix for Listing 3 (bottom example).\n\n### Nitpicks\n\n- Highlight colors (green and red) used in code snippets are too intense. Can be toned down for ease of read\n- Listing 2 Bottom: trailing whitespace is also included in the highlight.\n- Table 1 and 2 are hard to decode. Maybe try separating them into multiple tables (with pre-train and without pre-train).", "summary_of_the_paper": "The paper presents GRAPHIX, a graph edit model for program repair. The work is directly related to Hoppity (Dinella et. al. 2020) which proposed using a sequence of graph edit for program repair. GRAPHIX employs multi-head graph encoder which improves upon Hoppity in terms of accuracy and complexity. Notably GRAPHIX is able to learn longer edit sequence and thus work on more program repair samples. The work has also proposed a pre-training task to improve model performance. Empirically the authors evaluated GRAPHIX on the *Patches in the Wild* Java bug-fix benchmark. It outperforms various baselines without pre-training. With pre-training, GRAPHIX-P stays roughly on par despite having much smaller model.", "summary_of_the_review": "Overall, I think the paper has merits. Program repair in the wild using end-to-end neural network is inherently a difficult problem. The proposed architecture shows a good performance while using a much smaller model, and can spawn further discussion of algorithms using graph edits for program repair. The paper has also shown a pretty comprehensive evaluation. However, the paper will be in a much better shape if the pre-training task is designed more throughly. We would also hope there is a better performance gain from incorporating pre-training. I lean towards accepting the paper.\n", "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": {}}]

Author rebuttal:

Meta-review: This paper presents an approach for machine learning to fix programming errors via edits to abstract syntax trees. The main contributions are a pretraining scheme based on masking out subtrees and some minor architectural modifications compared to previous work. Reviewers found the paper to contain a significant amount of work, but there are some questions about significance relative to previous work that framed the problem similarly, and about experimental methodology. Authors did a great deal of work in the rebuttal to address many of the experimental methodology questions, but this also introduced substantial unreviewed changes to the model, the pretraining approach, and the experiments. In total, the remaining concerns about significance and the substantial changes lead us to recommend that this paper be revised and resubmitted to the next conference.
Decision: Reject