Venue: NeurIPS 2022 Conference

Reviews:

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 work presents concrete score matching which generalizes score matching to discrete distributions. This is not the first work to attempt to generalize score matching to discrete domains. Lyu 2012, does this first, but defines a discrete ''score'' using the dimension-wise marginals of each dimension in the input. Conversely, here the ''score'' is created by defining a graph over states in the support of the distribution. The score is defined as the likelihood ratio between neighboring states in this graph. The authors provide sufficient conditions to ensure that learning the concrete score is equivalent to learning the desired distribution. This setup is more flexible than prior generalizations and can be applied to inputs which cannot be embedded into {1, ..., k}^D.

The authors present two learning methods taking advantage of the concrete score; concrete score matching and denoising concrete score matching -- generalizations of score matching and denoising score matching respectively. As well, they present an efficient training procedure for both and an MCMC sampling procedure which utilizes the concrete scores.

They present experimental results on some toy discrete distributions, non-toy discrete distributions and binary MNIST. The presented results in dictate that CSM performs favorably. 
strengths_and_weaknesses: Strengths:

I enjoyed reading this paper. I think the method is an elegant generalization of score matching and synthesizes prior attempts to generalize score matching to discrete domains. The method makes sense, is easy to understand, and seems to be well justified. The paper is not bogged down with unnecessary theory, but the theory presented is useful in helping the reader build understanding and intuition about the method.

The experimental results in the paper were nice. I liked the use of the MADE model for section 4.2 although I have some thoughts that I will elaborate on in the next section. The MNIST results are also quite nice. It is very difficult (even on MNIST) to obtain such nice results using (non-de noising) score matching, so I was quite impressed. 


Weaknesses:

I think the main weaknesses with the paper are in the empirical study of the method. I think there are a number of simple things that could have been done which would have greatly improved this. For example, there could have been a study of the impact of the choice of neighborhood structure. As well, there could have been a maximum likelihood baseline presented in section 5.4. Further, while denoising concrete score matching was presented, there were no empirical results shown. All of these things could have pretty easily been added and would have greatly improved the quality of the results section.


questions: While I enjoyed the work, I am left with quite a few questions.

Neighborhood structure: I know you mention that the neighborhood structure should be an important design choice. This makes sense. Did you perform any ablations on this? It would be really nice to see a likelihood based experiment like the section 5.4 using different neighborhoods. This would give the reader some intuition on how this should be chosen.

Section 5.4: I like that you used a normalized model to test these various approaches. This enables likelihood based evaluation which you used. I was somewhat curious as to why there was no maximum likelihood baseline presented in the table. I think this should be put in the table. No one would ever expect a method like this (which does not require a normalized model) to outperform ML training but it can provide a good ceiling on the performance of a model under ideal circumstances. This would greatly improve the impact of these results. 

Efficient Training: In section 4.2 you present an efficient training scheme where you sample neighbors in the graph uniformly. Have you considered using a gradient-based importance sample scheme as in [1, 2]? I know that may be outside the scope of the work but I think it could be a nice extension that would be worth noting on here. 

Denoising concrete score matching: I like that you propose two learning methods for the concrete score. Unfortunately it seems that you present no experiments using this method. It would be nice to present some result (even a toy result) indicating that this method, in practice, can be used to train a model.

Evaluation: Have you considered using something like AIS or RAISE to evaluate these models? I don't see why you couldn't do that to provide a bound on log-probability for your MNIST models, for example. Even if you don't present these results, it might be nice to add a note in section 3.3

[1] https://openreview.net/pdf?id=IEKL-OihqX0
[2] https://arxiv.org/abs/2102.04509
limitations: Yes, I believe the authors have adequately addressed the limitations of their work.
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 proposes a discrete counterpart to continuous score
matching. The main idea is to build a neighboring graph for each point
and replace the gradient of the log-likelihood with a vector
containing the likelihood ratios between a datapoint and its
neighbors. This vector is called the concrete score. The paper
proposes a training scheme to learn the concrete score from data, and
shows that in the limit of infinite data and infinite capacity the
model can recover the true data likelihood. An efficient
implementation is demonstrated empirically on simple discrete datasets.

strengths_and_weaknesses: Strengths:

1) The paper is well written and the ideas are clearly explained.
2) The proposed concrete score is simple and elegantly converges to the
  Stein score in the limit of neighboring graph shrinking.
3) The paper derives a training objective that is in the same spirit as
  in continuous score matching.

Weaknesses:

1) I found the paper dedicates very little attention to how the
   neighborhoods are actually built in practice for the different
   datasets. In particular for the high-dimensional datasets, this
   seems to be a crucial aspect of the method that was disregarded
   (unless I missed something).
2) The method has scaling issues for high-dimensional data and large
  datasets. Theorem 1 requires a fully connected graph which is
  impractical for large datasets, and the approximated loss will
  certainly suffer from high variance. Although the authors mentioned
  this, it is not entirely clear what are the practical limitations
  for scaling up.
3) The experimental evaluation is limited. The paper only compares to
   two baseline methods. The gains do not seem significant, and the performance
   comparison was limited to log-likelihood, without taking efficiency into account. These
   baseline methods were unknown to me, and I felt more detail was
   required to understand what is being compared to.  I wonder how the method would compare to other
   discrete generative models such as D3PM [Austin et al.], [43], to
   name a few, and in particular the very related method of finite
   differences FSDM [27].

questions: Please see the weaknesses points above.
limitations: The authors do mention the limitations in scaling to higher dimensions and larger datasets. I agree this is the main limitation and the paper could be improved by conveying a better understanding of what these limits are in practice.
review_title: null

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 comprehensive framework of score matching on discrete data. The papers proposes a clever surrogate of the score function, and proves its completeness for practical usage. After establishing the concrete score, this paper proposes the concrete score matching to estimate it, as well as a denoising version. To leverage the concrete score, this paper also proposes a MCMC algorithm to sample based on the score. Experiments show effectiveness of the concrete score matching.
strengths_and_weaknesses: Strengths:

The author carefully extends the score matching to discrete data. This extension finds counterparts of continuous score matching in both theory (i.e., the completeness), training (i.e., concrete score match and its denoising version), inference (i.e., MCMC). It also allows directly estimate the concrete score, instead of the probability mass function. It seems many benefits in the continuous score matching also exist in the concrete score matching.

Weakness \& Questions:

1. Why $J_1$ requires Monte Carlo on $i$? It seems that the summation on $i$ can be directly calculated, since $c_\theta(x; N)$ is the output of the neural network, and simply summing each dimension of the (square of) output is exactly the summation on $i$.

2. In Line 221, the author claims that the concrete score $c_{\tilde{p}}(\tilde{x}; N)$ captures how close $\tilde{x}$ is to x. However, the concrete score is only related to $\tilde{x}$? How to understand the closeness?

3. Does the concrete score of $\tilde{q}(\tilde{x}|x)$ have a closed form expression as the continuous case?

4. Is the neighbor in L 203 and L 220 suitable choices? Since $|N(x)|$ = $2^D$ and $3^D$ respectively, which are too large to model using a neural network when $D$ is large.

5. The author also uses annealed noise as [21]. Is the concrete score matching able to scale up to more complex data as [21]? For example, CIFAR10 and ImageNet. If not, what is the gap between this work and [21]? 

6. Missing related works on score matching: [1*] and [2*] are related works, which also enlarge the scope of score matching.

[1*] Bao et al., Bi-level score matching for learning energy-based latent variable models

[2*] Bao et al., Variational (gradient) estimate of the score function in energy-based latent variable models
questions:  
limitations:
review_title: null

Meta-review: metareview: All reviewers are positive about the paper. 

- The paper is well-written / sound and the experiments are convincing
- It's true that the neighborhood selection and lack of scalability w.r.t. dimension are limitations but they are acknowledged. 
- Reviewers raised valid concerns but the rebuttal addressed many of them. 

Overall, the formulation presented here is quite general and could have a great deal of application and impact especially given the explosion of work on score-based models in continuous domains.

We recommend acceptance.
confidence: Certain
Decision: Accept