Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a deep generative model for sequence data, where the relational constraints between components in the sequence are modeled as latent variables. The overall framework is largely the same as Young et al. (2019) that is designed for image domain, while in the sequence data like text new challenges need to be addressed since the relationation constraints are different. The authors consider binary relations for the poetry and music domain, such as whether two lines of the poetry should rhyme. The model is learned with a VAE objective while being somewhat more complicated due to the symbolic relation variable. Specifically, the relational constraints need to be pre-extracted through solving a constrained optimization problem, then a separate VAE is learned on the relational constraints, and finally the authors propose three different approaches to model the data conditioned on the relation variable and the normal VAE latent variable. The model is overall interesting as a neurosymbolic deep model, which is claimed to model the global coherence better than typical sequence neural models and users could more or less control the generation through specifying the constraints. Experiments including human study confirm its superiority over normal NNs on generation such as MusicAutobot and GPT2. 
strengths_and_weaknesses: ### Strengths:

1. I think the authors make an attempt to address an important and difficult problem in sequence modeling by modeling symbolic relational constraints. Even though the method is not perfect (e.g. much more complicated than non-symbolic baselines), I would like to see such papers appear in the conference.  
2. The method is novel (at least in the application to sequence data) and interesting. For example, extracting prototype subcomponents to obtain linear complexity for paired relations is clever, and solving it as a constrained optimization problem is a nice contribution.   
3. Empirical results look strong, though I do have some concerns (see below).

### Weaknesses:

1. The method is much more complicated both methodologically and practically than the baselines, thus the empirical impact of the proposed method could be limited in reality – I guess not many people would use it practically. This is an important weakness that I have to mention here, yet I don’t think it is a sufficient reason to reject this paper since I think we should encourage this kind of work. The complexity of the method is expected since modeling symbolic variables in NNs is not easy. However, I think this paper should spare more space to discuss such complexity and limitations of this work. There are many limitations that need a discussion and many details are missing from the paper:  
(1) There are many hyperparameters added by the method which the baselines do not have. How do you choose those hyperparams? How sensitive are the results to them? In fact, I cannot find the values of many hyperparams, e.g. $k_{min/max}, \lambda_{1/2/3}$.  
(2) What is the overall computational cost and how does it compare to the baselines? How different are the efficiencies of the three approaches in Section 4.2? For example, the rejection sampling in Approach 1 may be slow. I think the efficiency aspect of the proposed method warrants a separate paragraph of discussion (at least in the appendix)  
2. The paper is not well-presented. My overall feeling is that the authors try to compact too much content into the main body of the paper and therefore many details are missing and sometimes it could be difficult to follow. This is particularly true for Section 4 and 5.   
3. Evaluation is important. Because of the lack of details as mentioned above, I am not sure whether the automatic evaluation in the paper is properly done. For example,  
  (1) When you compute NLL, did you directly use one sample to estimate ELMO or use importance weighting to compute a tighter lower bound? The former is known to be inaccurate as a surrogate to NLL  
  (2) When you train classifiers, what is the evidence to ensure that they are trained properly? What hyperparams did you try to train those classifiers? Did you try to tune them?   
There is no need to tell too much on these details, but a paragraph in the appendix to convince readers that you did try to make evaluation convincing is much better.   
4. I appreciate the user study evaluation, but I would like to know more details than the given ones in the appendix, for example, how many users score each example? If multiple users score the same example, do you have the agreement score for them (like variance)? – giving more details would make your results more convincing.

```
After author response:  
The author response and the update of the paper addressed most of concerns, and I would like to increase my score to 6.
```

questions: Questions: Is $f$ in Line 143 pre-known? I feel it is known from Eq. (1), right? If so, do you use prior knowledge/heuristics to obtain the paired relations in advance and compute $f$?

Suggestions: I think many details and the limitations should be included as mentioned in the weaknesses above, the presentation could also be improved.  

limitations: The authors discussed the potential negative societal impact in the work but I don’t think the limitations were adequately discussed.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes a method for generating sequences with relational structure. Specifically, the authors study the generation of poetry and music, where different lines of a poem have rhyme or equal meter constraints, and different measures of music have rhythm or pitch class constraints, etc. They represent these relational constraints as a bipartite graph, where the vertices on the left are the prototype subcomponents (i.e., lines or measures), the vertices on the right are the subcomponents to be generated, and the edge labels indicate the relations that the right endpoints need to satisfy with respect to the left endpoints.

To extract the relational constraints of a training example, the authors formulate it as a combinatorial optimization problem and use Z3 to solve it. To generate a sequence, they first use a VAE to generate relational constraints, and then generate subcomponents that satisfy these constraints, for which the authors provide three approaches: rejection sampling, conditional VAE, and combinatorial optimization.

Experiments on music and poetry generation show that the proposed method outperforms previous approaches in capturing relational structure.
strengths_and_weaknesses: $+$ Despite doing well at generating locally coherent content, large language models still struggle to capture high-level structure. This paper considers relational structure between subcomponents and proposes a novel method to extract and learn to conform to them. This approach is particularly suitable for the generation of poetry and music with explicit relational constraints.

$+$ To implement the relational constraints, this paper makes solid technical contributions, including a program synthesis algorithm and a neurosymbolic generative model.

$-$ Experiments are only conducted on two small datasets with thousands of examples.
questions: In more general, free-form essays, there are also connections between sentences or paragraphs. Can this method be extended to capture these structures to improve generation quality?

In line 196, for the objective $J_2$, should it be $\sum K_{ki}K_{kj}$ instead of $\prod K_{ki}K_{kj}$?
limitations: The proposed method seems to be suitable only for generating highly structured sequences with predefined relations. Also, the algorithm to extract the relational constraints has high time complexity.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes generative models for poetry and music which have natural relational constraints on their subcomponents -- metric/rhyme on lines for poetry, and repetition of measures. The approach is similar to a variational autoencoder where the continuous latent variable z generates a constraint sketch C, and the poem/music arrangement is generated based upon the sketch C. This sketch is defined with the assumptions that the final artifact has m subcomponents, and uses a subset of these subcomponents as prototypes to define additional relationships between the subcomponents and the prototypes. The sketch C|x is obtained deterministically by an SMT solver Z3, and rest of the model is trained to maximize the MLE via lower bound approximation. Empirical comparison is done with relevant prior work.
strengths_and_weaknesses: The paper tackles an important problem of incorporating structural constraints in otherwise opaque neural generative models and provides a clean solution to the domains explored in the paper. This kind of research is welcome in order to build more controllable and interpretable generative models. However, I feel the title/conclusion is slightly overclaiming because this approach I believe is limited only to a subset of relational constraints that are relevant to the domains explored in this paper.

The comparison is done with relevant baseline which clearly shows the effectiveness of the proposed approach over existing work.

However as mentioned earlier, this approach seems like it would work for very specific domains, where there is a clear mapping between prototypes and subcomponents and constraints are only defined on the subcomponents (Moreover, the constraints/algo in this paper only considers constraints over pairs of subcomponents). I am not sure how other kinds of constraints can be tackled in general. For example, even making the number of subcomponents (variable m) variable is not trivial practically, so a discussion about this aspect would improve the paper.
questions: -- How do you sample/generate from BERT since it is not a probabilistic model? Please describe the procedure for generation and discuss this in greater detail. 
Relevant references:
BERT has a Mouth, and It Must Speak: BERT as a Markov Random Field Language Model, Wang and Cho
Exposing the Implicit Energy Networks behind Masked Language Models via Metropolis--Hastings, Goyal et al.

-- you mention “Z3 is guaranteed to find the optimal solution”. I am not sure how is it guaranteed. On the surface this looks like a NP-hard problem but their might be simplifying assumptions I may have missed.
limitations: N/A
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies a generative model for sequential data that has relational constraints. It proposes to use a two-stage generation process to (1) generate relation constraints (2) sample/generate the examples based on the relational constraints. Two domains, music and poem, have been used as evaluation data to test the correctness of the proposed method.
strengths_and_weaknesses: To me, this paper is on the borderline: on one hand, the topic and method presented are interesting and intuitive, while experimental results and analysis might be less convincing.

Pros:
(1) The topic and method are interesting and intuitive. Generating examples based on relational constraints seems to be a promising direction to consider for future work. This could further be extended to other domains.
(2) The author has spent efforts on user studies to examine the effectiveness of the method.

Concerns:
(1) The method still requires a lot of human effort in order to work well. I am not sure how easy it is to be used for new tasks.
(2) It appears to me that there is no golden metric to be used for evaluation in this specific context. The paper proposed at least two ways: the first one is based on NLL, which I am not sure if it really reflects the model is better in terms of capturing low-level structures; and the other is based on trained models, which I suspect if it can be biased for certain groups of methods.
questions: Personally, I am hoping to see more concrete examples in the main paper to clearly show how the generated examples capture the relations with/without the proposed method.
limitations: I didn't find the section describing the limitation of this work other than the conclusion part, despite it is marked as 'Yes' in the checklist. Please correct me if I missed it.
review_title: null

Meta-review: metareview: This paper proposes a deep generative model for sequence data by extracting relational constraints from data.  The model is overall interesting as a neurosymbolic deep model, which is claimed to model the global coherence better than typical sequence neural models and users could more or less control the generation through specifying the constraints. Experiments including human study confirm its superiority over normal NNs on generation such as MusicAutobot and GPT2.
All reviewers enjoy the novel neurosymbolic approach and appreciate the user feedback. 
confidence: Certain
Decision: Accept