Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: ## Summary

This paper presents an approach to learn a model over incremental structural tree edits, that takes as input a partially formed tree and applies a sequence of transformations that edit the tree into a final form.  They focus on abstract syntax trees as used to represent expressions in programming languages, where the grammar is specified using the ASDL formalism.

They demonstrate their approach on two datasets: the GitHubEdits dataset and C#Fixers, showing improved performance relative to some baselines.

## Overview

The motivation for this work is weakly specified.  Analogies are made to the fact that humans seem to edit objects in sequence, but not much more than that is provided.  The authors would do well to specify, or at least hypothesize as to what the benefits of sequences of edits over the alternative.

Writing-wise, it is hard to tell what this paper actually contributes from the abstract or introduction.  Now, I would characterize it as presenting a template in which neural networks can be composed such that graph transformation sequences can be learned from data.

The claimed advantages over existing approaches are:
- Supports general tree edits, whereas previous approaches are somehow more restricted
- Language agnostic due to use of ASDL
- Supports longer sequences of edits in practice

A major problem is that these advantages are only weakly demonstrated, if at all: 

- What is a general tree edit?  One answer could be that any graph transformation can be encoded as an action in theri framework, or is it that it can be achieved through a sequence of steps?  The paper focuses on a very particular set of tree edits, so it is very unclear what is being claimed here.
- Longer edit sequences.  No evidence is provided to support this claim.
- Language agnosticism through ASDL is a valid claim, and useful.  It's not clear that generalizing any of the existing work to work with a general grammar would require much work though. 

Moreover, the work closest to this work (Dinella et al) is not compared against, neither experimentally, nor are the differences in the approaches detailed.  Why?

Overall while I think a useful software package could be made based on this work (which the authors suggest is forthcoming and which itself could be presented as a publication of a much different kind), the delta over existing work has not been demonstrated enough for me to recommend publication.

## Questions

- In the LSTM encoding of an edit sequence, you have these four transformations to produce a_stop, a_Delete, a_Add, and a_CopySubTree.  What is the advantage of doing these transformations prior to having the LSTM read the result?
- I cannot see where the embedding function $\text{emb}$ is defined.  Is this learned, or fixed?



review_title: Useful tool perhaps, but claims of paper not demonstrated and novelty unclear.

final_score: rating: 7: Good paper, accept
review_content: The paper presents a neural autoregressive model that learns to incrementally or iteratively perform edit actions on structured data. The authors focus specifically on abstract syntax tree representation of programs (e.g., C#). The model has two main parts:

(1) Neural editor models p(a|) that iteratively performs tree edit actions such as sub-tree deleting or adding;
(2) Edit encoder learns edit representations f_Delta by encoding the sequence of ground truth tree edit actions.

The authors also propose an imitation learning algorithm to train the editor and evaluate the model on source code edit datasets.

The idea of incremental tree transformation pretty much follows that of Hoppity by Dinella et al, ICLR 2020 for bug fixing of Javascript programs. Unlike Hoppity where each transformation step is done on a single node, this work extends to support sub-tree operations. However, adding a subtree is nothing but performing a sequence of single-node actions. The difference is that to ensure the syntactic validity of the tree at any point, the authors use a grammar specified a priori. This mechanism was proposed in semantic parsing by Yin et al., ACL 2017. Compared to Hoppity, this model has another SubTreeCopy operation, but it is a somewhat straightforward extension of the copy mechanism from Yin et al. 

Although the whole idea is not new, I think the paper presents a valued extension to existing work. The running example is intuitive, making the paper easy to follow. However, there are a number of parts that are unclear and need more clarity. I hope the authors address these during the rebuttal phase.

1. The authors should be clear (e.g., before Equation 1 and in Section 3) about where the sequence actions {a_t} comes from and how sub-tree actions are represented (e.g., decomposed into single-node actions). Later in this experiment, the authors mention dynamic programming to compute the shortest tree edit sequence, but I feel that substantial discussion or an algorithmic description is needed.

2. It is not clear to me whether f_Delta is learned jointly or separately from the parameters of p(a|). In Figure 1 and Equation 1, f_Delta does not depend on t and seems to be fixed.

3. In the last paragraph of page 3, this sentence “the operator selects a dummy node (e.g. node Dummy) and replaces it with the added node” is not clear. Is there always at least one dummy node at any time? What is “the added node”?

4. Another question about Add operation: if an Add operation is given and there is currently no dummy node, would it make more sense to specify the added location with respect to a parent node and its children?

5. How does the model know when to stop adding a right sibling for constructor fields with *sequential* cardinality? Similarly, for an *optional* cardinality field, what does the model do on the attached dummy node if the field is indeed optional?

6. It may be more natural to predict the node location n_t before the operation op_t. Equation 2 does the other way. Does this change the model in any way? 

7. To what extent this framework is language-agnostic? Despite the ASDL, even for the same language, different parsers can have different grammar specifications, so how easy is it to apply this framework for other languages? On the same note, since Hoppity is directly related, I am curious how this work compares to it on a same bug fixing task.

Finally about the experiments, the authors compare to Graph2Tree and CopySpan. But it does not look like the source code for the baselines are available. Releasing the source code with that of the baselines would be helpful.


Minor typos

“Arbitary”: Section 3.1.1 paragraph 2.

========== After discussion =============

I have increased my score from 6 to 7.
review_title: Official Review #2

final_score: rating: 7: Good paper, accept
review_content: ## Summary

The paper proposes a general model for incremental editing of tree-structured
data such as abstract syntax trees. The editing operations include adding a
node, deleting a subtree, or copying a subtree. They also propose a novel edit
encoder to learn to represent edits, and an imitation learning method to make
the model more robust.

## Pros

- The work has several interesting and valuable contributions:
  + Compared to previous work, the model is much more general: it supports
    general tree edits, is language agnostic, and can handle much longer edit
    sequences.
  + The novel edit encoder which directly encodes the edit actions is more
    intuitively correct and also performs better than previous approaches.
  + Imitation learning to make the model more robust is a natural idea that
    suits incremental edits very well.
- The source code will be released which -- given the general nature of the
  model -- could enable further interesting research.

## Concerns

- The explanation for the results in Table 1 could be improved upon.
  + I don't think the results support the claim that Seq Edit Encoder memorizes
    specific patterns with the baselines as the micro average of Graph2Tree for
    Fixers-one shot is very close to Graph2Edit.
  + Even if we accept the claim, that would not explain the CopySpan >
    Graph2Tree > Graph2Edit results on GHE-gold and Fixers-gold. The authors
    state that Seq Edit memorizes specific patterns, TreeDiff Edit learns more
    generalizable information, and Graph2Edit makes Seq Edit learn more
    generalizable information. But they state that in order to solve GHE-gold,
    we need specific patterns instead of generalization. So why does increasing
    generalization by switching Seq Edit to TreeDiff Edit improve performance of
    Graph2Edit on GHE-gold and Fixers-gold (which doesn't need generalization),
    and decrease performance on Fixers-one shot (which needs generalization)?
- Some of the contributions are not demonstrated clearly:
  + The method's applicability to much longer edit sequences is not clearly
    demonstrated, although the length of the edit sequences is mentioned briefly
    in the Appendix.
  + The imitation learning method is demonstrated only on "Graph2Edit with Seq
    Edit Encoder", which is the less interesting case compared to "Graph2Edit
    with TreeDiff Edit Encoder". From the previous experiment it's clear that
    the TreeDiff encoder version is the practically relevant one and the one the
    paper's about. As the Seq Edit encoder makes more mistakes and so it's
    easier to improve, we don't know whether imitation learning helps in the
    relevant case of the TreeDiff encoder. In my opinion this makes imitation
    learning more of a digression and a less of an organic part of the paper.
- The writing could be more precise at times. For example, the authors state
  that they are adding subtrees as an edit operation, but as far as I
  understand, they are adding individual nodes.

## Reasons for ranking

I believe that the model is an important step in learning to represent edits.
However there are some problems with the experiments: some of the claims are not
adequately supported and the explanations could be improved upon.

## Minor comments

- I found Figure 1 confusing at first, because there is essentially no caption
  and the description of the figure comes much later in parts. It would be good
  to either have a more substantial caption or to move the figure closer to the
  explanations.
- Table 2 precedes Table 1, which is confusing
- It should be "general", not "generic", like "general model for incremental editing"
- Page 3: Delete operators take a tree node ... and remove
- The algorithms in the Appendix should be DaggerSampling and PostRefineSampling (missing "l").

review_title: Impressive general model with some problems in the experiments

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: ### Summary ###
The paper presents an approach for predicting edits in programs, by modeling the programs as trees. The approach is mainly an extension of Yin et al. (2019), with the main difference that the model is required to predict only the output **actions**, instead of generating the entire output tree as in Yin et al. (2019). This difference of predicting only output actions is shared with other previous work though.
The most interesting part in my opinion is the "imitation learning" improvement: during training, the model is trained to correct its own mistakes by "imitating" an expert that fixes the incorrect predictions.

Overall, I vote for acceptance. Although the technical contribution is limited, the paper presents strong empirical results and a combination of interesting ideas. I think that the paper could be easily further improved, as detailed below.

### Strengths ###
1. The paper presents improved results over the Graph2Tree model (Yin et al. 2019) and over CopySpan (Panthaplackel et al., 2020a).

2. The imitation learning part is very interesting, and its applicability for programs is novel as far as I know. I feel like maybe this should have been the main focus of the paper.

### Weaknesses ###
1. Limited novelty - the encoder, as far as I understand, is identical to the edit encoder of Graph2Tree (Yin et al. 2019). The decoder ("editor") is better, empirically and conceptually, than the decoder of Graph2Tree, but its main novelty is the prediction of the edit action itself, rather than generating the entire output tree. To me, this idea is not novel, as it was used in Tarlow et al. (2019), Dinella et al. (2020), and Brody et al. (2020).

2. A conceptual comparison with previous work is missing. First, the work of Tarlow et al. (2019) is not cited at all (although their application is different, the approach is very similar). Second, a comparison to Hoppity (Dinella et al., 2020) and to C3PO (Brody et al., 2020) is presented in a single paragraph and contains the following arguments:

(a) “While some recent works have examined models that make changes to trees for specific applications such as program bug fixing (Dinella et al., 2020) or edit completion (Brody et al., 2020), our method is designed to be generic and flexible in nature”
-- I don't think that this is a fair argument. These previous works are as general as this paper, they were just demonstrated on slightly different datasets.

(b) “it supports general tree edits including adding new tree nodes or copying a subtree, which are not fully allowed by previous work”
-- Can't Hoppity add new tree nodes? Can you clarify the classes of edits that previous works could not express and that this paper can express?

(c) “all tree edit operations are language-agnostic owing to the adoption of Abstract Syntax Description Language (ASDL; Wang et al. (1997)), which allows us to process arbitrary tree-based languages”
-- I don't think that this is a fair argument. These previous works are language-agnostic as well, they just use a different AST "format". 

(d) “unlike the short edit sequences handled in previous work (e.g. up to three edits in Dinella et al. (2020)), we demonstrate our method’s applicability to much longer edit sequences”
-- The fact that Hoppity was evaluated with 3 edit actions does not mean that it is not applicable for longer action sequences. This argument would have been valid if it was demonstrated empirically that Hoppity's accuracy decreases as the length of the sequence increases.  In that case, the imitation learning part might be a very natural fix (which was good! but not shown).


3. Evaluation - it is unclear which datasets should we _really_ care about, and which are the main results. It seems that the proposed Graph2Edit model outperforms the Graph2Tree model (Yin et al. 2019) only in the "gold" datasets (GHE-gold and Fixers-gold), which expose (indirectly) the labels to the input. That is, these serve as "intrinsic" tasks that cannot really be compared across models. As far as I understand, Yin et al. (2019) argued that the "Fixers-one shot" is the dataset that really matters, and that GHE-gold and Fixers-gold are just "intermediary"/"intrinsic" training objectives. 
In the "intermediary" datasets, Graph2Edit outperforms Graph2Tree, but it is not compared to "Seq2seq encoder+editor" which performed best in these datasets in Yin et al., 2019 (Table 4 in Yin et al., 2019).
In the one-shot dataset (Fixers one-shot) - Graph2Tree performs better than the proposed Graph2Edit model.
So, I am not sure what are the main results that the readers should focus on and what is the correct baseline. See question 1 below.

### Questions for Authors ###
1. Is the accuracy on the "gold" datasets (GHE-gold and Fixers-gold) really meaningful? Isn't this accuracy just an intermediary accuracy? 
As far as I understand, when trained on these gold datasets: $f_{\Delta}$ depend on $C_{+}$, and then $f_{\Delta}$ is *used* in the prediction of $C_{+}$. I saw the footnote that says that  $f_{\Delta}$ does not *directly* expose $C_{+}$. So it means that it *indirectly* expose $C_{+}$, right? Section 3.3 explicitly says that "given an input tree $C_{-}$ and an edit representation  $f_{\Delta}$ (calculated either from $<C_{-}, C_{+}>$ or another edit pair $<C'_{-}, C'_{+}>$), we generate one tree edit at a time step...". 
So, since in the gold dataset  $<C_{-}, C_{+}>$=$<C'_{-}, C'_{+}>$ , the authors model the "actions leading to $C_{+}$" given "an encoding of $C_{+}$"? 
I.e., are the output labels (indirectly) encoded in the input? 

This is fine if we consider the gold datasets as intermediary/intrinsic objectives, and consider Fixers one-shot as the "important", downstream task. 
If so, Graph2Tree (Yin et al., 2019) performs best on the Fixers one-shot dataset (which is the "important" dataset).
If not, and the gold datasets are meaningful on their own, then why there is no comparison to the seq2seq editor+decoder that Yin et al., 2019 found to perform best on the gold datasets?

2. The paper states that the graph edit encoder of Yin et al. (2019) does "not explicitly express the differences between the input and the output trees". As it looks in Yin 2019 (Section 3.2), it seems that they represent the difference between the trees pretty explicitly, using edges such as "Removed", "Added" and "Replaced" between the old and the new tree. So, what is the main novelty compared to Yin et al. (2019) in this area?

3. The main novelty in this paper compared to previous work, in my opinion, is the imitation learning training (Section 4). I wish the authors elaborated more on this, give examples, show how the parameter values affect the performance, etc.

4. How long are the edit sequences, average, in the Fixers dataset? (in comparison to Hoppity's 3 edits per sequence)

### Improving the Paper ###
The paper could be improved in the following ways:
1. A conceptual discussion of the differences from previous work (Tarlow, Dinella, Brody).

2. Is it possible to perform an empirical comparison with Hoppity? 

3. Other strong baselines would be Transformer+copy and bidirectional LSTM seq2seq+attention+copy mechanism, that copy individual tokens rather than spans as in CopySpan (Panthaplackel et al., 2020a). 
Even Section 5.2 of the paper says that the CopySpan baseline, which can copy large spans, memorizes too much.
Another straightforward baseline is a sequential **tagger**, that tags each individual token in $C_{-}$ with tags like KEEP/SWAP/DELETE, as in Malmi et al. (2019), and as Brody et al. (2020) adapted to code as their baseline.
 
4. Adding more interesting examples in which the model succeeds (and fails). The paper claims "applicability to much longer edit sequences" (Section 1), but the example in Figure 1 converts `list.ElementAt(i+1)` to `list[i+1]`   (which might be syntactically-long, but not that "difficult") and the example in Table 2 only converts a `VAR2.ToString()` to `VAR2`  (which is also not very "difficult" or "interesting", because a simple sequence-tagger that is trained to delete tokens can produce such examples).  Ideally, the appendix could contain many additional examples like Table 2 (but also with longer edit sequences).

### Minor questions and comments ###
5. The paper's title contains the phrase "*Incremental* Tree Transformations". 
What is "incremental" about it? Doesn't the model mainly model a single "action" or "transformation" at a time? Doesn't the "incrementality" come from an LSTM "decoder" that sequentially predicts these actions? 

6. In Section 3.2 - Why is $a_{Stop}$ computed as $W_{Stop}emb(Stop)+b_{Stop}$, instead of just learning a single embedding vector, if all its components are trainable and used only in $a_{Stop}$?

7. Typo in Section 4, Algorithm 1 and Algorithm 2:  "Samping" -> "Sampling"






review_title: Interesting paper with strong empirical results

Meta-review: This paper proposes a model for predicting edits to trees given an edit specification that comes either from the ground truth before-after state (“gold” setting, like reconstruction error of auto-encoder) or from the before-after state of an analogous edit. The problem setting follows mostly from Yin et al (2019). 

There are several shortcomings of this paper:

1. The technical novelty of the model is somewhat limited, as it’s an assembly of components that have been used in related work. Authors insist in the discussion on the novelty of the tree edit encoder (Sec 3.2), but I think this is overstated. The related tree-edit models (e.g., Tarlow et al (2019)) perform a very similar encoding *in the decoder* when training with teacher-forcing. While it’s true that decoders are typically thought of as monolithic entities that generate a sequence of edits from a state, inside the teacher-forced training, the models are computing a representation of a prefix of ground truth edits, which are then repeatedly used to predict next edits. AFAIU, the proposal is basically to use this hidden representation as the edit encoder. 

2. The claim that the approach is more language agnostic than Dinella et al (2020) also seems shaky, as the authors admit in their response that language-specific grammars need to be handled specially. E.g., I expect that the authors of Dinella et al would find it easier to extend their existing code to use a new language than to adapt this approach.

3. The submission relies too heavily on the “gold” setting (where the target output is fed as an input), and I’m skeptical of their characterization of Yin et al’s intentions when the authors say in comments, “Because of this, models that are able to reproduce the desired output effectively have a demonstrably better inductive bias that allows them to do so efficiently. This was the original motivation expressed by Yin et al. (2019).”  I don’t see this stated in the Yin et al paper. I see Yin et al. characterizing this setting as an upper bound and saying “better performance with the gold-standard edit does not necessarily imply better (more generalizable) edit representation.” (Yin et al., 2019). It’s worrying that the proposed model only seems to do better in this setting, which would be very easy to game if one were aiming to directly optimize for it. 

Having said this, (1) is not a standard way to think about encoding edits, (2) is debatable, and we can hope that future work does not treat improvements in the “gold” setting as a valid research goal. Further, there is another contribution around imitation learning that the reviewers appreciate. In total, reviewers did an excellent job and generally believe the paper should be accepted. I won’t go against that recommendation.
Decision: Accept (Poster)