summaries: 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. 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).  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. 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.
abstractText: We present GRAPHIX, a pre-trained graph edit model for automatically detecting and fixing bugs and code quality issues in Java programs. Unlike sequence-tosequence 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 state-of-the-art 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.
references.authors: Wasi Ahmad Saikat Chakraborty Baishakhi Ray Kai-Wei Chang
references.title: Unified pre-training for program understanding and generation
references.venue: In NAACL,
references.authors: Miltiadis Allamanis Marc Brockschmidt Mahmoud Khademi
references.title: Learning to represent programs with graphs
references.venue: International Conference on Learning Representations,
references.authors: Uri Alon Roy Sadaka Omer Levy Eran Yahav
references.title: Structural language models of code
references.venue: In International Conference on Machine Learning,
references.authors: Berkay Berabi Jingxuan He Veselin Raychev Martin Vechev
references.title: Tfix: Learning to fix coding errors with a text-to-text transformer
references.venue: In International Conference on Machine Learning,
references.authors: Pavol Bielik Veselin Raychev Martin Vechev
references.title: Phog: probabilistic model for code
references.venue: In International Conference on Machine Learning,
references.authors: Marc Brockschmidt Miltiadis Allamanis Alexander L Gaunt Oleksandr Polozov
references.title: Generative code modeling with graphs
references.venue: In International Conference on Learning Representations,
references.authors: Saikat Chakraborty Yangruibo Ding Miltiadis Allamanis Baishakhi Ray
references.title: Codit: Code editing with tree-based neural models
references.venue: IEEE Transactions on Software Engineering (TSE),
references.authors: Zimin Chen Steve James Kommrusch Michele Tufano Louis-Noël Pouchet Denys Poshyvanyk Martin Monperrus
references.title: Sequencer: Sequence-to-sequence learning for end-to-end program repair
references.venue: IEEE Transactions on Software Engineering (TSE),
references.authors: J. Devlin Ming-Wei Chang Kenton Lee Kristina Toutanova. Bert
references.title: Pre-training of deep bidirectional transformers for language understanding
references.venue: In NAACL-HLT,
references.authors: Elizabeth Dinella Hanjun Dai Ziyang Li Mayur Naik Le Song Ke Wang
references.title: Hoppity: Learning graph transformations to detect and fix bugs in programs
references.venue: In International Conference on Learning Representations (ICLR),
references.authors: Dawn Drain Chen Wu Alexey Svyatkovskiy Neel Sundaresan
references.title: Generating bug-fixes using pretrained transformers
references.venue: arXiv preprint arXiv:2104.07896,
references.authors: Zhangyin Feng Daya Guo Duyu Tang Nan Duan Xiaocheng Feng Ming Gong Linjun Shou Bing Qin Ting Liu Daxin Jiang
references.title: Codebert: A pre-trained model for programming and natural languages
references.venue: In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: Findings,
references.authors: Justin Gilmer Samuel S. Schoenholz Patrick F. Riley Oriol Vinyals George E. Dahl
references.title: Neural message passing for quantum chemistry
references.venue: In International Conference on Machine Learning,
references.authors: Claire Le Goues Michael Pradel Abhik Roychoudhury
references.title: Automated program repair
references.venue: Commun. ACM,
references.authors: Daya Guo Shuo Ren Shuai Lu Zhangyin Feng Duyu Tang Shujie Liu Long Zhou Nan Duan Alexey Svyatkovskiy Shengyu Fu
references.title: Graphcodebert: Pre-training code representations with data flow
references.venue: In International Conference on Learning Representations,
references.authors: Hideaki Hata Emad Shihab Graham Neubig
references.title: Learning to generate corrective patches using neural machine translation
references.venue: arXiv preprint arXiv:1812.07170,
references.authors: Vincent J Hellendoorn Charles Sutton Rishabh Singh Petros Maniatis David Bieber
references.title: Global relational models of source code
references.venue: In International Conference on Learning Representations,
references.authors: Weihua Hu Bowen Liu Joseph Gomes Marinka Zitnik Percy Liang Vijay Pande Jure Leskovec
references.title: Strategies for pre-training graph neural networks
references.venue: International Conference on Learning Representations,
references.authors: Hamel Husain Ho-Hsiang Wu Tiferet Gazit Miltiadis Allamanis Marc Brockschmidt
references.title: Codesearchnet challenge: Evaluating the state of semantic code search
references.authors: Thomas N Kipf Max Welling
references.title: Semi-supervised classification with graph convolutional networks
references.venue: In International Conference on Learning Representations,
references.authors: M. Lewis Yinhan Liu Naman Goyal Marjan Ghazvininejad Abdelrahman Mohamed Omer Levy Veselin Stoyanov Luke Zettlemoyer
references.title: Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension
references.authors: Yi Li Shaohua Wang Tien N Nguyen
references.title: Dlfix: Context-based code transformation learning for automated program repair
references.venue: In Proceedings of the ACM/IEEE 42nd International Conference on Software Engineering,
references.authors: Yujia Li Oriol Vinyals Chris Dyer Razvan Pascanu Peter Battaglia
references.title: Learning deep generative models of graphs
references.venue: International Conference on Machine Learning,
references.authors: Chris Maddison Daniel Tarlow
references.title: Structured generative models of natural source code
references.venue: In International Conference on Machine Learning,
references.authors: Rumen Paletov Petar Tsankov Veselin Raychev Martin Vechev
references.title: Inferring crypto api rules from code changes
references.venue: ACM SIGPLAN Notices,
references.authors: Sheena Panthaplackel Miltiadis Allamanis Marc Brockschmidt
references.title: Copy that! editing sequences by copying spans
references.authors: Maxim Rabinovich Mitchell Stern Dan Klein
references.title: Abstract syntax networks for code generation and semantic parsing
references.venue: In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers),
references.authors: Alec Radford Karthik Narasimhan Tim Salimans Ilya Sutskever
references.title: Improving language understanding by generative pre-training, 2018
references.authors: Caitlin Sadowski Jeffrey Van Gogh Ciera Jaspan Emma Soderberg Collin Winter
references.title: Tricorder: Building a program analysis ecosystem
references.venue: In 2015 IEEE/ACM 37th IEEE International Conference on Software Engineering,
references.authors: Daniel Tarlow Subhodeep Moitra Andrew Rice Zimin Chen Pierre-Antoine Manzagol Charles Sutton Edward Aftandilian
references.title: Learning to fix build errors with graph2diff neural networks
references.authors: Michele Tufano Jevgenija Pantiuchina Cody Watson Gabriele Bavota Denys Poshyvanyk
references.title: On learning meaningful code changes via neural machine translation
references.venue: IEEE/ACM 41st International Conference on Software Engineering (ICSE),
references.authors: Michele Tufano Cody Watson Gabriele Bavota Massimiliano Di Penta Martin White Denys Poshyvanyk
references.title: An empirical study on learning bug-fixing patches in the wild via neural machine translation
references.venue: ACM Transactions on Software Engineering and Methodology (TOSEM),
references.authors: Marko Vasic Aditya Kanade Petros Maniatis David Bieber Rishabh Singh
references.title: Neural program repair by jointly learning to localize and repair
references.venue: In International Conference on Learning Representations,
references.authors: Ashish Vaswani Noam M. Shazeer Niki Parmar Jakob Uszkoreit Llion Jones Aidan N. Gomez Lukasz Kaiser Illia Polosukhin
references.title: Attention is all you need
references.venue: Neural Information Processing Systems,
references.authors: Petar Veličković Guillem Cucurull Arantxa Casanova Adriana Romero Pietro Lio Yoshua Bengio
references.title: Graph attention networks
references.venue: In International Conference on Learning Representations,
references.authors: Yu Wang Ke Wang Fengjuan Gao Linzhang Wang
references.title: Learning semantic program embeddings with graph interval neural network
references.authors: Yue Wang Weishi Wang Shafiq Joty Steven CH Hoi
references.title: Codet5: Identifier-aware unified pre-trained encoder-decoder models for code understanding and generation
references.venue: arXiv preprint arXiv:2109.00859,
references.authors: Keyulu Xu Weihua Hu Jure Leskovec Stefanie Jegelka
references.title: How powerful are graph neural networks
references.venue: International Conference on Learning Representations,
references.authors: Ziyu Yao Frank F. Xu Pengcheng Yin Huan Sun Graham Neubig
references.title: Learning structural edits via incremental tree transformations
references.venue: In International Conference on Learning Representations (ICLR),
references.authors: Michihiro Yasunaga Percy Liang
references.title: Graph-based, self-supervised program repair from diagnostic feedback
references.venue: In International Conference on Machine Learning,
references.authors: Pengcheng Yin Graham Neubig
references.title: A syntactic neural model for general-purpose code generation
references.venue: In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers),
references.authors: Pengcheng Yin Graham Neubig Miltiadis Allamanis Marc Brockschmidt Alexander L Gaunt
references.title: Learning to represent edits
references.venue: In International Conference on Learning Representations,
references.authors: Rui Zhao David Bieber Kevin Swersky Daniel Tarlow
references.title: Neural networks for modeling source code edits
sections.heading: 1 INTRODUCTION
sections.text: 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 labor-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 (e.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 al., 2019b;a) propose heuristics to extract bug-fix data from code changes. Code changes are represented as (code before, code after) pairs mostly at the method level, and typically pertain to feature enhancements, bug fixes and code refactoring. Code changes relating to 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 is that there are plenty of code changes available in source code repositories.
  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 the power of sequence-to-sequence models with RNN (Hata et al., 2018; Chen et al., 2019; Tufano et al., 2019b;a) and more recently with pre-trained Transformer models (Feng et al., 2020; Guo et al., 2021; Ahmad et al., 2021; Wang et al., 2021; Berabi et al., 2021). Secondly, instead of generating the fixed code from scratch, Zhao et al. (2019); Chakraborty et al. (2020); Li et al. (2020); Panthaplackel et al. (2021) extend sequence models and propose to generate edits on the buggy code. Lastly, Yin et al. (2018); Tarlow et al. (2019); Dinella et al. (2020); Yao et al. (2021) deviate from the token-based representation of code and leverage the hierarchical structure in the abstract syntax tree
  (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 a 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 Transformer-based 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, a pre-trained graph edit model for automated program repair. Inspired by HOPPITY (Dinella et al., 2020), we design GRAPHIX as a sequential decision process with a multi-head graph 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 an 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 a novel pre-training 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 et al., 2018; Brockschmidt et al., 2018) for expression generation and the structural language model (Alon et al., 2020) for any-code completion.
  We evaluate GRAPHIX on both concrete and abstract versions of the Patches in The Wild Java benchmark (Tufano et al., 2019b). We show that GRAPHIX significantly outperforms edit-based and Transformer models, and the performance is as competitive as recent state-of-the-art 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 as 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 examples such as fixing off-by-one errors, possible null pointer exceptions, etc. in our analysis.
  In summary, we make the following main contributions in this work:
  1. GRAPHIX is a 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-1 exact match accuracy on the Patches in the Wild benchmark even without pre-training. Using an explicit graph representation on the abstract syntax tree, our model is as 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 tree-sitter1. 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.
  1https://tree-sitter.github.io/tree-sitter/
sections.heading: 2 RELATED WORK
sections.text: 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 Translation, Hata et al. (2018); Chen et al. (2019); Tufano et al. (2019b;a) regard code as a sequence of tokens and use sequence-to-sequence models to “translate” the buggy code into the fixed code. More recently, pre-trained Transformer-based models such as CodeBERT (Feng et al., 2020), GraphCodeBERT (Guo et al., 2021), PL-BART (Ahmad et al., 2021) and most recently CodeT5 (Wang et al., 2021) achieve state-of-the-art results on “Patches in the Wild” Java benchmark (Tufano et al., 2019b) for program repair. A series of edit-based approaches model the code edits made on the buggy code as opposed to the “translation”-based counterparts. Zhao et al. (2019); Chakraborty et al. (2020); Li et al. (2020); Panthaplackel et al. (2021) extend sequence-to-sequence 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 as graph convolutional networks (Kipf & Welling, 2016), graph attention networks (Veličković 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); Hellendoorn 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); Tarlow et al. (2019); Dinella et al. (2020); Yasunaga & Liang (2020); Yao et al. (2021) use graph models based on ASTs for program repair and editing tasks in C, C# and Javascript, separately. Particularly, Brockschmidt et al. (2018); Dinella et al. (2020); Yao et al. (2021) use graph representations with treebased decoders for AST generation by editing the partial AST one node at a time. Brockschmidt et al. (2018); Yao et al. (2021) further equip the decoder with an Abstract Syntax Description Language (ASDL) to ensure the syntactic correctness of the generated code. Our work advances HOPPITY (Dinella et al., 2020) and (Yao et al., 2021) 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 et al., 2019; Lewis et al., 2020) 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-training GRAPHIX to learn hierarchical tree structures of code for program repair rather than on generating code.
sections.heading: 3 MOTIVATING EXAMPLES
sections.text: We begin by motivating the graph edit approach with two examples of code changes. Listing 1 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 ExpressionStmt at the same position, (iv) copy the AssignExpr 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 as node deletion, addition or 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
  public static List<String> getDomains(String consumerKey) throws APIManagementException { String list = ApiMgtDAO.getAuthorizedDomainsByConsumerKey(consumerKey);
  if ((list != null) || && (!(list.isEmpty()))) {
  return Arrays.asList(list.split(",")); } return null;
  }
  Object void setData(Object newData) {
  return data = newData; }
  Listing 1: Two bug-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 NullPointerException 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 is best seen with color.
  instead of decoding from scratch. Second, the edit sequence is often much shorter than the code sequence per se. Finally, with the structural edits, the decoding can be guided by an underlying syntax language. For example, the child of ExpressionStmt must be an expression (e.g., AssignExpr in the second bug fix) and must not be other production rules such as 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 is buggy and localize the bug more precisely.
sections.heading: 4 APPROACH
sections.text: At a high level, we want to model p(gf |θ, gb) where gb is the buggy code and gf is the fixed code. Instead of encoding gb and generating gf from scratch, we learn a sequence of T tree-edit actions {at}Tt=1 that transforms gb to gf as motivated in Section 3. Indirectly, we learn the model p(a1:T |gb) from a labeled dataset of samples, each with buggy code and the corresponding ground-truth edit, by minimizing a cross-entropy loss. Figure 1 illustrates the overall architecture. 5/26/2021 graph-edit-example
  1/2
  One may recover the original token-based generation model when each action corresponds to adding a new token and T is the length of gb. The key departure from such a model is a more hierarchical program representation that allows shorter and more structural edits between the input gb and the output gf . Inspired by (Dinella et al., 2020; Yao et al., 2021) which build on syntax structures and
  4
  tree differencing-based edits, we represent the buggy code as graph gb that is constructed from the program’s syntax tree and extra data flow edges between certain leaf nodes.
  Our model is sequential in nature with a multi-head graph encoder and an autoregressive tree decoder. At each time step t, the encoder encodes the current graph state gt, and the decoder computes the graph edit history st. Conditioned on 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 A. Next, we elaborate more on the multi-head graph encoder and our proposed pre-training strategy.
sections.heading: 4.1 MULTI-HEAD GRAPH ENCODER
sections.text: Earlier work (Yin et al., 2018; Allamanis 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., 2020) 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 a 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-head attentions in (Vaswani et al., 2017; Veličković et al., 2018), we propose a multi-head graph encoder for the graph encoding in which each head is a GIN and the head outputs are 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 (Veličković et al., 2018) as well as multiple towers in message passing neural networks (Gilmer et al., 2017). 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 depth. We choose to concatenate the resulting GIN representations at the end as an ensemble model and find such a strategy effective in our ablation study (c.f. Appendix E).
  The graph encoder is the component with the most parameters. The encoder’s size is 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.
sections.heading: 4.2 PRE-TRAINING OBJECTIVE
sections.text: We have described the architecture of GRAPHIX as a graph-based, autoregressive model. GRAPHIX is a supervised model and trained on labeled bug-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 a novel strategy to pre-train GRAPHIX on unlabeled source code and allow the knowledge to be transferred to the downstream program repair task.
  Pre-training task. Generalizing the masked language model pre-training idea in NLP (Devlin et al., 2019; Lewis et al., 2020), 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 a sub-tree of a certain size rooted at node n. We replace n with a dummy node, and remove all the subsequent nodes and edges in the sub-tree. Given the dummy node’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 a time in the depth-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 our 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-training task can be viewed as a generalization of the masked language model objective in BERT (Devlin et al., 2019) and a 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
  structural language model of code (Alon et al., 2020) for any-code completion. Unlike these works, we are interested in pre-training rather than code generation/completion. Note that our pre-training technique is specific to ASTs with an 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 as well as objectives such as link prediction and so on. We defer these directions to future work.
sections.heading: 5 EXPERIMENTS
sections.text: We evaluate GRAPHIX on the Patches in the Wild benchmark and compare its performance to existing translation-based and edit-based baselines. We conduct a series of experiments and studies on the network architectures (i.e., model size and single vs. multiple heads) and the data types (short vs. long function, and abstract vs. concrete code) to strengthen our evaluation.
sections.heading: 5.1 DATASET
sections.text: We use the Patches in the Wild Java bug-fix benchmark, which was curated and popularized by Tufano et al. (2019b). The dataset consists of 123,804 bug-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_1, VAR_2, INT_3. Most existing work employs this abstracted code benchmark with an only exception of (Drain et al., 2021). 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.
sections.heading: 5.2 DATA PROCESSING FOR GRAPHIX
sections.text: 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 JavaParser2 to parse the source code into a pair of ASTs and serialize the output ASTs into a 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 algorithm3 to create the ground-truth tree edit sequence for each pair of buggy and fixed code. Since GRAPHIX is a grammar-driven tree transformation (Yao et al., 2021), we implement a grammar-aware and shortest distance tree differencing algorithm, inspired by a dynamic program in Yao et al. (2021) (Algorithm 3). One could also use the GumTree differencing tool4. 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-aware tree differencing in Appendix B.
  Pre-training data. We use the CodeSearchNet dataset released by Husain et al. (2019) 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, we use the Java portion of CodeSearchNet with a total of 1.5M functions. We filter out
  2https://javaparser.org/ 32https://www.npmjs.com/package/fast-json-patch 4https://github.com/GumTreeDiff/gumtree
  those functions that are not parsable or have more than 600 AST nodes. The remaining functions can be considered fixed code and are used the pre-training task. During pre-training, we select sub-trees between 2 and 6 descendants for the deletion and construct a sequence of addition operations as the ground-truth edits. More details on implementation are provided in Appendix C.
sections.heading: 5.3 BASELINES AND METRICS
sections.text: We compare GRAPHIX to translation-based models including an LTSTM model (Tufano et al., 2019b) as well as state-of-the-art pre-trained Transformer models including notably PL-BART (Ahmad et al., 2021) and CodeT5 (Wang et al., 2021). We also compare our model against edit-based models including Copy That! (Panthaplackel et al., 2021) and HOPPITY (Dinella et al., 2020) of which the latter is directly related to our work. HOPPITY applies to Javascript and only works on short single-node edits (up to 3). That is, it does not handle a non-trivial sub-tree addition. For comparison, we modify its implementation to handle Java source code, and in order to add a sub-tree, we flatten 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 so that at 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.
  Metrics. 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 test sets. Note that EMs for eHOPPITY and GRAPHIX are computed based on AST matching, which is equivalent to sequence matching in the other models. For GRAPHIX and e-HOPPITY, we use beam search of size 5 during inference and select the candidate with the highest score normalized by the edit sequence length.
sections.heading: 5.4 RESULTS
sections.text: In this section, GRAPHIX refers to the 8-head model with 32M parameters that is not pre-trained. GRAPHIX-P refers to GRAPHIX that is pre-trained and then fine-tuned on the respective datasets. We present the results on the abstract and concrete benchmark in Table 1 and Table 2, respectively. Each table consists of three groups of results: the first group represents the translation-based methods without pre-training, the second group is for edit-based methods and the last group includes pretrained models including GRAPHIX-P. Note that DeepDebug (Drain et al., 2021) was not evaluated on the abstract code while most were not on the concrete code.
  From Table 1, we can see that our models significantly outperform the other edit-based baselines and are on a par with larger pre-trained models. Specifically, without pre-training GRAPHIX improves CodeBERT by 1.8% on the small subset and 4% on the medium subset. We observe a similar improvement of GRAPHIX over BART. When pre-trained on CodeSearchNet Java, GRAPHIX-P slightly outperforms PL-BART, CodeT5-small on the small but underperforms them on the medium. CodeT5-base with 220M parameters is currently the state-of-the-art performance on both datasets.
  Table 2 shows the results of the models on the concrete benchmark. The PL-BART result, which was not reported in the original paper, is obtained by fine-tuning the released pre-trained PL-BART model on the concrete code. We observe a similar improvement on 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) on the small set but worse on the medium. Compared to PL-BART, GRAPHIX-P performs comparably on the small dataset and outperforms PL-BART by a good margin on the medium set. In short, our model works comparably to DeepDebug and PL-BART on the concrete benchmark despite much fewer parameters.
  Comparing the results in Table 1 and Table 2, we see a negligible drop about 0.2 – 0.5% in accuracy of GRAPHIX from the abstract to concrete code. On the contrary, the accuracy of GRU with span copy (Panthaplackel et al., 2021) 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 is 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.
sections.heading: 6 ANECDOTAL EXAMPLES
sections.text: In addition to several state-of-the-art results in EM accuracy, GRAPHIX demonstrates strong inductive biases in learning complex bug-fix patterns. In this section, we showcase several bug examples that GRAPHIX is able to detect and fix. We show more such examples in Appendix F.
  public void stopLocationUpdates() throws SecurityException { if ((locationManager) != null) {
  locationManager.removeUpdates(this); }
  }
  public static Throwable getRootCause(Throwable t) { if (t == null) return null;
  Throwable rootCause = t; Throwable cause = rootCause.getCause(); while ((cause != null) && (cause != rootCause)) {
  rootCause = cause; cause = cause.getCause();
  } return rootCause;
  }
  Listing 2: Missing null check bugs in the samples small/11219 (top) and medium/10509 (bottom).
  @Override public void resolveAnaphora() {
  List<Proposition> props = VariableStorage.getPopostionList(); int i = 0; for (CQuantifer quant : this.getQuantifers()) {
  if (i < = (props.size())) props.get(i).setLinkedId(((String) (quant.getVar().getSourceId())));
  i++; }
  }
  public static int mul(int n1, int n2) { return n1 + * n2; }
  Listing 3: (top) Off-by-one error in sample medium/11874 (including = may cause an index-out-ofbound exception) and (bottom) logical bug in sample small/8295.
  We manually analyze the generated fixes of GRAPHIX on 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-likelihood 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 in 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 to recognize interesting bug-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 on. Here, we show some exemplary samples of fix patches that match the ground-truth in the benchmark. Listing 2 displays two examples of potential bugs where the developers fail to validate the input/a class field. GRAPHIX can 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 an 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.
sections.heading: 7 DISCUSSION AND FUTURE WORK
sections.text: In this paper, we consider the problem of generating bug fixes using a neural model. We present GRAPHIX, a 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 a diverse set of bugs and program issues. In particular, GRAPHIX is about 2× smaller than state-of-the-art Transformer models. Finally, GRAPHIX performs equally well on generating abstract as well as concrete fixes.
  Practical use. The problem of bug detection is nuanced, and several times ML models can be replaced by simple rules. We have shown that GRAPHIX can capture semantic bug fixes through dozens of anecdotal examples (see Appendix F for more). In addition, we demonstrate in Appendix D that one can calibrate the model score to achieve an increased precision up to 57% by trading-off the coverage of bug detection.
  We anticipate several directions in the future work: (i) pre-train based on multiple sub-tree additions and replacements (ii) incorporate more program dependencies into the graph representation and (iii) leverage Transformer and GNNs in a unified architecture for the global code context in the sequence.
sections.heading: Appendix
sections.heading: A ENCODER AND DECODER
sections.text: 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., 2021).
sections.heading: A.1 SINGLE-HEAD ENCODER
sections.text: Formally, given a graph g = (V,E) with a set of nodes V and edges E, a single-head graph encoder gives a d-dimensional representation of the graph g and representations of individual nodes v ∈ V . Similar to (Dinella et al., 2020), we compute the graph presentations for each edge type (i.e., AST edges, last-variable-use edges and successive edges) as follows:
  h(l+1,k)v = σ  ∑ u∈Nk(v) W l,k1 h (l) u  ,∀k ∈ {1, 2, . . . ,K} (1) h(l+1)v = σ ( W l2 [ h(l+1,1)v , h (l+1,2) v , . . . , h (l+1,K) v ] + h(l)v ) , (2)
  where K denotes the total number of edge types, L is the number of propagations. W l,k1 ∈ Rd×d and W l,k2 ∈ RdK×d are the network weights. Nk(v) denotes a set of neighbors of v that are connected to v with the edge type k. These formulae give the node embeddings n = {h(L)v }v∈V for all nodes v ∈ V while the graph representation is an aggregation of h(l)v for all l. More precisely, we use max pooling to combine h(l)v for each l and average the L+ 1 resulting vectors to compute the final graph representation g.
  The initial embedding h(0)v 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.
sections.heading: A.2 TREE EDIT OPERATIONS
sections.text: GRAPHIX is a sequential decision process that iteratively performs tree edits on the partial tree at each step. Following (Brockschmidt et al., 2018; Yao et al., 2021), we employ a grammar-based tree decoder to ensure the grammatical correctness of each edit action. To that end, we construct an abstract language based on JavaParser5. The grammar includes a set of primitive and composite types (c.f. (Rabinovich et al., 2017; Yin & Neubig, 2017)). Each composite type (e.g., stmt) has a collection of production rules such as ExpressionStmt(expr expression) where each rule is represented as a constructor with a list of field arguments. Each argument has the field type (e.g., expr), the field name (e.g., expression) 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:
  DELETE operator takes a tree node n and removes it from the tree. As a result, the corresponding sub-tree and the node n are removed. However, removing a node that corresponds to a single field results in a grammatically invalid tree. For instance, removing node ClassType in step 1 of Figure 1 causes 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 a new child to a parent node of a sequential field. For example, the node of type (stmt* statements) may have an arbitrary number of children. In this case, adding a 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 a non-terminal node ExpressionStmt in Figure 1 in step 4). Similarly to
  5https://javaparser.org/
  the DELETE operation, once adding a non-terminal node, we 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 to 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 in Figure 1 at t = 2 is copied to the new position in step 6.
  Finally, the NO_OP action is used to automatically terminate the iterative tree editing procedure. After this step, the remaining dummy nodes will be pruned.
sections.heading: A.3 AUTOREGRESSIVE TREE DECODER
sections.text: Given the graph representation gt of the program at step t and the edit history st−1 from the previous step, we use an LSTM-based tree decoder to update the state st = LSTM(gt|st−1). Based on the updated state st, the model predict edit actions where each node edit includes a node selector, an operator predictor and a type/value predictor. The node selector selects node loct, then the operator predictor decides which operator opt to apply the edit on loct among the four possible operators {DELETE, ADD, COPY, NO_OP}. For the ADD operation, the type predictor further determines the node type/label typet for the newly added node. For terminal nodes, the value predictor computes the node value valuet. The probability of an edit is then decomposed as
  p(at|st) = p(loct|st)p(opt|st, loct)p(typet|st, opt, loct)p(valuet|st, opt, loct, typet). (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 a sequential-field 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(loct|st) = p(siblingt|st, parentt)p(loct|st, parentt). If parentt does not have any children, the left sibling node is considered as parentt itself. We compute the logits by taking inner product between the edit history st and the node embeddings nt. We select the node that maximizes the inner product. After selecting the node, we update the state with an additional LSTM call st = LSTM(emb(loct)|st) where emb(loct) is the node embedding of the selected node loct.
  Operator prediction: The operator prediction is a regular classification problem with four labels {DELETE, ADD, COPY, NO_OP}. We calculate the probability of operator opt using a softmax layer such that p(opt|st, loct) = softmax(Wopst + bop). After that, we again update the state via st = LSTM(emb(opt)|st) where emb(opt) is the embeding of the selected operator opt. Type prediction. This module assigns a type typet 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 opt using a softmax layer such that p(typet|st, loct) = softmax(Wtypest + btype). We update the state via st = LSTM(emb(typet)|st) where emb(typet) is the embedding of the newly predicted type typet.
  Value Prediction. If the newly added node is a terminal node, the value predictor assigns to it a value valuet. The possible values are chosen from the union of the local values present in the input (i.e., local value table) and the global values that frequently appear in other programs. The local value embeddings are 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 st and the value embeddings and select the one maximizing the score. Finally, we update the state via st = LSTM(emb(valuet)|st) where emb(valuet) is the embedding of the value valuet. The decoding process stops once it encounters NO_OP or reaches the maximum number edits.
sections.heading: B COMPARISON OF TREE DIFFERENCING ALGORITHMS
sections.text: Table 3 shows the advantages of structural, grammar-aware tree differencing with copy operations in GRAPHIX over JSON differencing used in HOPPITY.
  medium/6715
  1 @Override 2 public boolean create(POJO.User user) throws SQLException { 3 stmt = connect.prepareStatement("INSERT INTO User ..."); 4 stmt.setString(1, user.getPseudo()); 5 stmt.setString(2, user.getPassword()); 6 stmt.setString(3, user.getEmail()); 7 stmt.executeUpdate(); 8 stmt.close(); 9 System.out.println(...);
  10 return true; 11 }
sections.heading: JSON differencing edits
sections.text: 1. Remove the statement in line 10: return true; 2. Remove the scope: System.out 3. Remove the arguments in println 3. Remove the name println 4. Replace the remaining MethodCallExpr with BooleanLiteralExpr 5. Add true 6. Replace ExpressionStmt with ReturnStmt
sections.heading: Grammar-aware differencing edits
sections.text: 1. Remove the statement in line 9: System.out.println(...);
  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 9 to re-add the return true statement.
  We can see that the structural edit differencing results in much shorter edit sequences on average. Examination of edits shows that structural edits also more meaningful. We show an example of code change and edits in Listing 4.
  C IMPLEMENTATION AND TRAINING DETAILS
  We implement GRAPHIX with PyTorch based on the open source implementation of HOPPITY (Dinella et al., 2020). We train GRAPHIX on a machine with 8 V100 GPUs, each with 32GB memory. We use batch size 5 on each GPU both in pre-training and fine-tuning. We use the Adam optimizer
  and a linear learning rate scheduler, used in Transformer (Vaswani et al., 2017). We set the initial learning rate 10−4 and the warmup steps corresponding to 1 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 on the medium set. We choose the best model checkpoint using the validation set and report its top-1 accuracy on the test set.
sections.heading: D HIGH PRECISION REGIME FOR GRAPHIX
sections.text: As shown previously and in Appendix F, GRAPHIX is able to learn meaningful and interpretable code patterns, leading to a 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 an increased precision. To demonstrate that, we show the impact of calibrating the prediction scores to achieve such a trade-off.
  Table 4 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, at the threshold 0.7 on the prediction score.
sections.heading: E ABLATION STUDIES
sections.heading: E.1 EFFECTS OF THE GRAPH MODEL SIZE AND PRE-TRAINING
sections.text: In Table 5, we compare GRAPHIX with HOPPITY using about 1M parameters. Here, GRAPHIXB refers to the proposed GRAPHIX model with 1M parameters. The results show that GRAPHIX is significantly better than HOPPITY because of the ASDL-guided decoding and the grammaraware shortest edit differencing. To be specific, GRAPHIX edits are significantly shorter and more meaningful than JSON differencing edits (see Table 3 and Listing 4 in Appendix B for the comparison). Moreover, the grammar-constrained decoder reduces the uncertainty of predicting edit properties at each decoding step.
  We also study the effects of the graph model size and pre-training on GRAPHIX. Table 5 suggests that the multi-head encoding leads to about 50% relative boost in accuracy on the small, abstract subset and almost 2× boost on the abstract, medium. The improvements are consistent on the concrete code. It 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 our future work.
  Next, we study the role of our proposed multi-head architecture.
sections.heading: E.2 ROLE OF THE MULTI-HEAD ARCHITECTURE
sections.text: 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 are comparable. It 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 d increases from 128 to 256 while the model with d = 566 tends to overfit the training data and performs poorly on the test set. In summary, our experiments show the benefits of the proposed multi-head architecture.
sections.heading: E.3 PER-LAYER VERSUS LAST-LAYER MULTI-HEAD
sections.text: We implement a per-layer multi-head architecture with head averaging and GIN, following the idea in GAT (Veličković et al., 2018). In this architecture, each head computes a linear projection of the input before it is fed to the respective GIN layer, so without attention having multiple heads per 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 a fixed weight and computes average. We take the average of the head outputs instead of the concatenation for a computational reason.
  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 H = 4 and H = 8 heads). The results and configuration of each model are shown in Table 7.
  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 at 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.
sections.heading: F MORE ANECDOTAL EXAMPLES
sections.text: We 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 are replaced with “. . . ”.
sections.heading: F.1 SIMPLIFYING LOGIC EXPRESSIONS
sections.text: Before After
  small/6886
  public boolean isEmpty() { if ((first) == null) {
  return true; } return false;
  }
  public boolean isEmpty() { return (first) == null; }
  medium/7382
  @Override public boolean onTouchEvent(android.view.MotionEvent ev) {
  super.onTouchEvent(ev); dragHelper.processTouchEvent(ev); ViewGroup parent = ((ViewGroup) (findBottomView(this, x, y).getParent())); return false || (parent == (this));
  }
sections.heading: F.2 FIXING OFF-BY-ONE ERRORS
sections.text: Before After
  small/6229
  @Override public boolean hasNext() { return ((cursor) + 1) < (batches); } @Override public boolean hasNext() { return (cursor) < (batches); }
  small/9321
  public boolean hasNext() { return (frameIndex) < ((count) - 1); } public boolean hasNext() { return (frameIndex) < (count);
  medium/11106
  public static boolean isPowerOfTwo(long number) { if (number < = 0) {
  throw new IllegalArgumentException(...); } if ((number & (-number)) == number) { return true; } return false;
  }
  medium/10998
  public int run() { int exponent = 1000; BigInteger base = BigInteger.valueOf(2); BigInteger value = BigInteger.ZERO; int sum = 0; value = base.pow(exponent); String str = value.toString(); for (int i = 0; i < ((str.length()) - 1) (str.length() ; i++)
  sum += ((int) ((str.charAt(i)) - '0'));
  return sum; }
  F.3 USING EQUALS INSTEAD OF == FOR STRING COMPARISON
  small/9253
  public TimelineConfig findChannelById(String id) { for (TimelineConfig channel : channels) {
  if (channel.getId() .equals(id) ) return channel;
  } return null;
  }
  small/6752
  private Customer findCustomer(String customerCode) { for (Customer c : customers) {
  if (c.getCode() .equals(customerCode) ) { return c;
  } } return null;
  }
  small/10790
  public boolean checkUsername(String username) { for (Model.User user : userRepository.findAll()) {
  if (user.getName() .equals(username) ) { return false;
  } } return true;
  }
  F.4 CORRECTING RETURNED OBJECTS
  medium/7800
  private static List<GroupData> generateGroups(int count) { List<GroupData> groups = new ArrayList<GroupData>(); for (int i = 0; i < count; i++) {
  groups.add(new GroupData().withName(...)); } return null groups;
  }
  medium/11925
  @Override public String toString() {
  String str = "Symbol Table list:"; for (int i = nestinglevel; (-1) < (nestinglevel); i++) {
  str += ("Nesting level " + i) + ":\n"; str += tables[i].toString();
  } return str;
  }
  F.5 FIXING CONDITIONS
  medium/9887
  public View getViewWithConf(String viewName) { if ((viewName != null) && ( ! (viewName.isEmpty()))) {
  for (fi.nls.oskari.domain.map.view.View item : list) { if (viewName.equals(item.getName())) {
  return item; }
  } } return null;
  }
  medium/9181
  private double getStepMovement(genetics.MusicPhenotype p) { double steps = 0; double intervalCount = 0; for (java.util.ArrayList<Integer> measure : p.melodyIntervals) {
  for (int interval : measure) { interval = Math.abs(interval); intervalCount++; if ((interval >= 1) || && (interval <= 2)) {
  steps += 1; }
  } } if (intervalCount == 0) { return 0; } return steps / intervalCount;
  }
  medium/11246
  public boolean insertBudget(final String name, final int max) { android.database.sqlite.SQLiteDatabase db = getWritableDatabase(); ContentValues contentValues = new ContentValues(); contentValues.put(DBHelper.BudgetDbIds.NAME, name); contentValues.put(DBHelper.BudgetDbIds.MAX, max); final long newId = db.insert(DBHelper.BudgetDbIds.TABLE, null,
  contentValues); return newId != 1 (-1) ;
  }
sections.heading: G NEGATIVE EXAMPLES
sections.text: 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 a quick fix that replaces || with && but does not go beyond adding logical ! to the second condition. Since GRAPHIX can add ! in medium/9887, Section F.5 when trained on the medium dataset, we suspect that the model might not have seen many !.isEmpty() 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 not match, despite the logical equivalence.
  Buggy code
  @Override protected void onSaveInstanceState(android.os.Bundle savedInstance) {
  super.onSaveInstanceState(savedInstance); if (((listData) != null) || (listData.isEmpty())) { savedInstance.putSerializable("HEADER", listData); }
  }
  Generated fixed code
  @Override protected void onSaveInstanceState(android.os.Bundle savedInstance) {
  super.onSaveInstanceState(savedInstance); if (((listData) != null) && (listData.isEmpty())) { savedInstance.putSerializable("HEADER", listData); }
  }
  Ground-truth fixed code
  @Override protected void onSaveInstanceState(android.os.Bundle savedInstance) {
  super.onSaveInstanceState(savedInstance); if ((listData) != null) {
  if (!(listData.isEmpty())) { savedInstance.putSerializable("HEADER", listData);
  } }
  }
  Listing 5: Test sample small/6783 in the benchmark.
  Listing 6 shows another incorrect fix by GRAPHIX. This example is nuanced because it could be difficult to know in the first place whether the original code is buggy or not, without more information.
  The last example, shown in Listing 7, is similar to the pattern GRAPHIX correctly learns in small/6886, Section F.1 and many others we observe in our manual analysis. In this case, the model simplifies the
  logical return expression in the input code, but that does not match with the correct fix. Again, it is 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 isValidInLength(android.text.Editable s) { return (!(respectPatternLength)) || ((s.length()) <= (maxLength)); }
sections.heading: Generated fixed code
sections.text: private boolean isValidInLength(android.text.Editable s) { return (!(respectPatternLength)) && ((s.length()) <= (maxLength)); }
sections.heading: Ground-truth fixed code
sections.text: private boolean isValidInLength(android.text.Editable s) { if ((respectPatternLength) && ((s.length()) > (maxLength)))
  return false;
  return true; }
  Listing 6: Test sample small/9672 in the benchmark. Buggy code
  @Override public boolean onKeyUp(int keyCode, KeyEvent event) {
  if ((keyCode == (KEYCODE_VOLUME_DOWN)) || (keyCode == (KEYCODE_VOLUME_UP))) { return true; } return false;
  Generated fixed code
  @Override public boolean onKeyUp(int keyCode, KeyEvent event) {
  return (keyCode == (KEYCODE_VOLUME_DOWN)) || (keyCode == (KEYCODE_VOLUME_UP))
  Ground-truth fixed code
  @Override public boolean onKeyUp(int keyCode, KeyEvent event) {
  if ((keyCode == (KEYCODE_VOLUME_DOWN)) || (keyCode == (KEYCODE_VOLUME_UP))) { return true; } return super.onKeyUp(keyCode, event);
  }
  Listing 7: Test sample small/7677 in the benchmark.
sections.heading: H EXAMPLES OF HOPPITY
sections.text: Finally, we show representative examples learned by e-HOPPITY in the decreasing order of the scores.
  small/11245
  protected public final int getRetryMaxAttempts() { return retryMaxAttempts;
  }
  small/6034
  public java.lang.String[] getText() { return this. text; }
  small/10646
  @Override public projectx.persistence.entities.Category findByid(long id) { return db.findCategoryById(id); }
  small/5862
  public models.T1Entity save(models.T1Entity entity) throws ClientException, ParseException {
  if (entity == null) return null; if (!(isAuthenticated())) return null;
  models.T1Entity response = postService.save(entity);
  return response;
  return postService.save(entity); }
  small/11352
  @Override public float computeBonus() {
  float bonus = ((this.salary) * (this.pctBonus)) + 1000; return bonus;
  }
  medium/10324
  @java.lang.Override public boolean onOptionsItemSelected(android.view.MenuItem item) {
  boolean retval = true; switch (item.getItemId()) {
  case android.R.id.home : onBackPressed(); break; case R.id.change_password : changeAccountPassword(account); break; case R.id.delete_account : openAccountRemovalConfirmationDialog(account); break; default : retval = super.onOptionsItemSelected(item); break;
  } return retval;
  }
title: GRAPHIX: A PRE-TRAINED GRAPH EDIT MODEL FOR AUTOMATED PROGRAM REPAIR