Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper presents an ensemble approach for graph predictions.
It consists in an algorithm that finds the graph that have the most nodes and edges matching, among different graphs produced by different systems or different checkpoints of the same system.
The authors tested the system on AMR graphs produced by state of the art AMR parsers.
Even if the problem is NP-hard the authors made it tractable using heuristics

The proposed ensemble models outperform the single-model approaches the authors compare with in two used AMR benchmarks in both in-distribution and out-of-distribution setting.

UPDATE
Thanks for the complete response, I think the paper is much stronger now.
main_review: The paper is easy to read and the approach is simple (which is good, it only has one hyperparameter) and effective. It will be likely used to boost performances of the next generation of AMR-parsers.

I liked the explanation the authors give on how the algorithm work in Section 4.4.

Since the authors only tested the model on AMR graphs, they should mention it in the title. The approach is clearly general and it would be interesting see its application on other graph prediction tasks.

The main thing missing in this paper in my opinion is an ensemble baseline.
For example, the transition base parser could be easily ensembled.
Another type of ensembling could be stacking in sequence to sequence, where the output of a model is used as input for another model.

I understand that the way the authors proposed to merge graphs is novel, but I would also like to see a comparison with more "standard" ensembling approaches.


limitations_and_societal_impact: There is no discussion on the limitations of the work and societal impact, but I am not sure it can apply to this paper.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Ensemble learning is a popular machine learning practice, in which predictions from multiple models are blended to create a new one that is usually more robust and accurate. Lots of work show the benefits of ensemble learning on regression or classification problems but there is a lack of investigation on the problem of graph ensemble which is more complicated. The paper collects the predictions from four state-of-the-art AMR parsers and shows the proposed ensemble method's effectiveness on the standard benchmark datasets.
main_review: 1. The motivation of the paper to study ensemble learning over graphs (specifically on the AMR task) is quite clear and the tackling problem is very important and crucial. 

2. The proposed method which aims to figure out the largest supported common subgraph makes sense to me. 

3. The experimental results of this paper show massive numbers to show the effectiveness of the proposed method in ensembling graphs. The performance improvement from the proposed method is consistent and promising.
limitations_and_societal_impact: 1. I didn't see too many experiments on model analysis that could reveal the insights of the proposed model.

2. Minor: The title of section 3, 'Please correct me if I am wrong', is quite interesting to me. It reflects the model's behavior and explicitly concludes the proposed method in a straightforward way. However, there is one more meaning that corrects you if you have something wrong in this section. I am not sure if you imply this meaning or not. (Although I really like this title, I suggest you use a conventional title to avoid any ambiguity)
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors proposed a new method for ensemble graph prediction. They formalized this problem as "mining the largest subgraph that is the most supported by a collection of graph predictions". Furthermore, they introduced an efficient heuristic algorithm to approximate the optimal solution given that the original problem is NP-Hard. They tested the algorithm in the AMR parsing problems. The experimental results demonstrate that the proposed approach can combine the strength of the state-of-the-art AMR parsers and the ensemble model outperforms individual models in five standard benchmark datasets.
main_review: The work is innovative as previous work focuses on dealing with multiple predictions where nodes are the same but the current work deals with the situation where both graph nodes and edges can be different among base predictions. Furthermore, previous ensemble approaches require models to be of the same type such as sequence models, transition-based or graph-based models. But the current approach is model-agnostic in the sense that it can combine predictions from different models.

 The submission is relatively sound. The authors demonstrate that their ensemble approach outperforms individual models not only in the In-distribution setting but also in the Out-of-distribution setting. I do have two concerns. First, in section 4.4, the authors claim that "From Table(4), the total support is highly correlated to the Smatch score. " Without seeing the statistical test of the correlation coefficients, I'm not entirely convinced that the conclusion is true. Even in Table 4, there're cases in which the average support is high but the Smatch score is low (e.g., BIO in row 3). It would be nice if the author could report correlation coefficients and the p-values to support their claim. Also, the authors mention that they set the hyperparameter theta so that theta divided by the number of models is greater than 0.5 (Line 180). I was wondering how changing this hyperparameter would affect the results and whether tuning this hyperparameter would lead to any further improvement.

The submission is clearly written and well organized. The results are important in the sense that it provides a way to obtain the ensemble prediction from multiple models, even when the models being combined have different architectures. I was wondering if the authors have any intuitions on how to generalize their work to graphs more complicated than the AMR parsing trees. It seems that their heuristic algorithms only work for a subset of graphs. Therefore naming the paper as "ensemble graph prediction" seems to be a bit overselling.

---------------

Updated: I've read the authors' responses to my review as well as the ones to the other reviewers'. I think their responses address my concerns, especially the additional details on the correlation analysis and the justification for choosing the hyper-parameter theta. I don't have a strong preference for adding "AMR" to the title, since I'd like to keep the paper appealing to a broad audience. I'm looking forward to seeing more work in the future which could verify that this ensemble approach is not limited to AMR graphs but can be applied to other graphs as well. Given the improvements and the limitation of the paper, I decided to keep my score unchanged as it reflects my best judgment of the work.
limitations_and_societal_impact: There's no foreseeable negative societal impact of this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors present a heuristic to combine several graphs, obtained by specialised linguistic parsers, to obtain a single more accurate parse graph. 
main_review: The main concern with this work lies in the benchmarking design. Specifically:  
1. Size of the improvement:  the authors claim that since their proposal is deterministic they do not need to report the variance in the experimental results, however one should simply sample the training set to observe the variability of the proposed approach. All improvements reported in the result section are around the 1% mark, and is therefore difficult to exclude a random effect. 
2. No base line is offered: for example one could propose the "median" graph as a representative of the set, or one could select the best graph by formulating a re-ranking task (i.e. learn a preference score on the set of alternatives). The efficacy of the approach (i.e. deriving an adjusted graph from a set of graphs) is not compared against any approach or baseline that has in input a set of graphs and outputs a single graph. 
3. The algorithm (which is heavily based on prior work to solve the vertex matching problem) does not offer any guarantee of being able to preserve some characteristics of the graph set: for example if one is working on trees, the algorithm is not guaranteed to output a tree, if one was working on molecular graphs, the algorithm would not yield valid molecular graphs (the valence would not be guaranteed). However no mention of the necessity to check or compensate for the feasibility  of the resulting graph is mentioned in this work. It is not clear in this specific domain what characteristics of the graphs are responsible for the efficiency of the algorithm, it is also not clear if this approach could be applied effectively to other domains and hence be of broader interest for the community. 
4. Not self contained: the authors do not provide any description of what an Abstract Meaning Representation graph is (apart from a single example figure); the datasets are not described; even the evaluation metric uses terms that are domain specific and not introduced. 

###After the authors' reply
Many thanks to the authors for the their response. Given the new experimental data provided by the authors I am inclined to improve the score. While the issues at points 1 and 2 regarding the effect size of the improvement achieved by their proposal and the baseline comparisons are somewhat addressed by the additional experiments, the concern regarding the generality of the method is not, as it is not sufficient to say that one can always introduce constraints to select the the non-violating examples (in fact in many important cases it can become exponentially hard to find viable candidates and hence a generate and test strategy would became infeasible). The generality problem could be easily addressed by specifying that the proposal is tailored for AMR graphs rather than for general graphs (given also that all experiments are in this very domain).
limitations_and_societal_impact: The authors have not addressed the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: This paper details the problem of (labeled) graph ensembling, in particular for the task of semantic (AMR) parsing, and proposes a heuristic algorithm for solving it. 

This is a challenging problem of interest. The reviewers find the work well-motivated and well explained, and raised some issues about comparisons, which the authors satisfactorily addressed with additional experiments in the discussion period. One outstanding point would be to clarify early on the scope of graphs for which the method works, more clearly. (However, the reviewers do not feel strongly that title should mention AMR, as the work is indeed more general.) Indeed, in some settings like link prediction, averaging of arc weights can be much simpler, and it might not be clear for all readers right away why and when the problem gets harder, based on the readers' background.

The reviewers made plenty of editing suggestions that I strongly encourage the authors to implement. In addition, I would like to add a few:

 - while I agree with the reviewer that it's better to rename the title of Section 3, the idiom provides helpful context so I would encourage you to keep it in the body (if not in the section title.)
 - line 83 and on: `$support$` should be styled as `$\operatorname{support}$` or defined as a macro with `$\DeclareMathOperator{\support}{support}$`.
 - line 146, the subscript `$g_{pivot}$` should be `$g_\text{pivot}$` -- same everywhere else.
 - all tables: try to align numbers on their decimal point (e.g. by right-alinging with a tabular font.)
 - Check the capitalization and formatting in your references. (e.g. "Amr" should be "AMR", "Machine learning" should be "Machine Learning" etc.)
Decision: Accept (Poster)