Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposed a method that could learn the structure of Markov Network given the variable domains are mixed. The learning algorithm makes no assumption on the parametric form of the probability distribution. To achieve this, author proposed to learn a density estimator using the score metrics framework. In addition, author proposed a method to estimate the "dependency" among variables with mixed domain from an arbitrary density model. The dependency score allows author 1) to recover the edges in a Markov Network given an arbitrary probability distribution 2) to introduce a differentiable regularization loss term during training to promote graph sparsity.  
strength_and_weaknesses: Strength:
1. In the experiment, author demonstrated that the proposed method is efficient and can scale to large number of variables in a network and large number of examples. At the same time, the performance in small domain is comparable to other more expansive baseline.
2. Compared to existing literature, the proposed dependency metrics are generalized to discrete and mixed domain. This generalization not only expand the application of the work, but also leads to a simple structure learning algorithm based on the score matching framework.

Weakness:
1. The experiment is limited. Author has only explored ground truth structure that are r iid pairs of random variables. 
* The evaluation would be stronger if author could explore different MN structures, e.g. different tree structures. 
*  Currently author is only demonstrating the quality of the learned structure, it would be interesting to know how accurate of the learned Markov Model as well. For discrete Markov Network structure learning literature, e.g. [1], learning algorithm was evaluated based on log likelihood on the test set.  This enables some other application of utilizing the work to perform density estimation on the mixed domain. 

[1] Van Haaren, J., & Davis, J. (2021). Markov Network Structure Learning: A Randomized Feature Generation Approach. Proceedings of the AAAI Conference on Artificial Intelligence, 26(1), 1148-1154.


clarity,_quality,_novelty_and_reproducibility: The paper is clearly written. Some notation in the paper can be better explained. For example, it was difficult to understand the super script [c], [d] and [m]. After quite a while, I think they are referring to continuous, discrete and mixed. It would be appreciated if author could add a one. On the setup section of the experiment 5, is W_i independent Q_i a typo? Does author mean P_i independent of Q_i ?

On the theory side, author did great work demonstrate various property of the proposed metrics. On the evaluation, I think there are still some room to improve. e.g. evaluating the method with more benchmarks and metrics. 

Questions:
1. How does author models the p_theta in the experiment. 
2. In section 2.2,  does the model m has to be a normalized distribution? From the equation 4, it does not seem that the partition function Z will be canceled out. 
3. on equation 6, is the formula inside log(*) representing p(x_j, z, x_i1; \theta)? What is the motivation to factor it as p(x_j, z | x_i1) * p(x_i1) ?



summary_of_the_review: I like the paper as it demonstrate an elegant solution to learn structure for mixed data. I would like the paper more if the evaluation could be more comprehensive to convince me on its applicability to more complex problem. 

==== After rebuttal ===
It is appreciated that author prepared additional experiments to justify the utility of the algorithm in a more complex setting. It does make me feel more confident on the proposed method.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors introduce an algorithm capable of learning very general Markov network structures, from general data-types including continuous, discrete and mixed.
strength_and_weaknesses: # Strengths

- The speed of the algorithm is very impressive and exciting. Further details need to be provided of course, of the experimental setup but the experiments are encouraging indeed.
- There is good mathematical rigour throughout.


# Weaknesses

- The sheer amount of results which are in the appendix, I find problematic. I understand, as ever, that there is not enough space but proofs are not trivial, they are results. At the very least, a sketch of the proof should be included in the body of the paper. The authors will be aware that reviewers are exceedingly busy and many of us do not have time to read all the appendices that come with the papers we are asked to review. You even have a lemma in the appendix. This venue may be inappropriate for such a large body of work, and a journal may be more suitable. 
- There is a common theme where the authors like to spell out the acronym or some relevant method/algorithm/idea but not actually telling the reader what it stands for which is very bad practice.
- The English is lacking in places, prepositions not there and general sentence construction is off.
clarity,_quality,_novelty_and_reproducibility: The review is organised according to the sections in the paper.

# Abstract

- Type, first line, should be: _A_ Markov network characterises...

# Introduction

- A Markov network does not have to be the same as an undirected graphical model - if the latter has the Markov property then yes they are the same thing, but if it does not, it is a different model altogether. Fix this, this is currently incorrect.
- The last sentence of your first paragraph is very unambiguous, you say "However, methods for Gaussian graphical models might fail to correctly capture dependencies between variables deviating from Gaussian or including nonlinearity" - what do you mean by 'might', in what cases does this happen? This is too imprecise. Give examples of when it fails and when it doesn't and why.
- Spell out what "SING" stands for instead of just stating the acronym - we as readers do not yet know what it stands for even if you do.

# GENERALIZED CHARACTERIZATION OF CONDITIONAL INDEPENDENCE

- It will probably help if you, in the second paragraph, talk about 'forks' and 'colliders' etc. to let the reader know the graphical topological structure you are referring to (in addition to your present discussion on conditional independence).
- I realise you are constrained for space, but it would be helpful if you could put (a) to (f) inside an itemized list to aid the exposure of your procedure. It is very dense at the moment and does not flow well.
- Notation: your notation is incorrect for $\mathbf{V} \setminus (I,j)$ it should be $\mathbf{V} \setminus \{I,j\}$ since you are removing the _set_ $\{i,j\}$.
- You variously refer to $\Omega$ as the characterisation as well as the matrix - which is to be? Stick to one, you are being inconsistent.
- The notation for equation 1 is _very_ busy and cluttered. You do not need that level of detail to make your point about the PDF: it is a fairly common idea and most will have seen it before. 
- I do not understand where equation 2 comes from, explain that better alongside your smoothness assumption - right now you're just saying that $p_X$ is smooth. A smooth function is a function that has continuous derivatives up to some desired order over some domain. Perhaps you can be a bit more precise than just saying 'smooth'. 
- Ok. You cannot just launch into the paragraph that follows equation 2. That will not doe. What is $g$, what is $h$ what is $n$ - where do they come from? Why do they have that structure? I understand that it is a result from Lauritzen, 1996, but it is not enough to just state without an explaining narrative to go along with it. Again, your readers do not know as much as you do, you have to explain basic things to us (like the aforementioned) and not assume that this is a known result.
- What is $c$ in equation 3? Why is it inside square braces (or should that be an Iversion bracket)? Which $p$ are we discussing here in the subscript of the expectation?
- "the gradient is undefined" - you make it sound like someone made a mistake in this case; the gradient doesn't exist at all.
- The last line of corollary 2, why are you using notation $\textbf{x}_i$ instead of $X_i$ and so on? I do not follow.
- I take it that you mean that $d$ in equation 5 is to stand for "discrete" and presumably too "c" for continuous? Just state that somewhere and further explain why these basic labels are inside braces.

# SCALABLE ESTIMATION WITH REGULARIZED SCORE MATCHING

- Why is the limit 5000 nodes? What happens if we use 10,000 nodes?
- How strong is the assumption of degeneracy?
- What is the domain of the penalty parameters, I assume [0,1]?
- You should perhaps be a bit less informal that to call something a "trick" and use less colloquial terms to refer to results from previous works.
- I am on page six and I still don't know what 'SING' stands for.
- Where does equation 10 come from? You say that it can be reformulated, but how? Through what means?
- I am not sure what you mean by saying that $\mathcal{L}$ is '"complete"' (your quote, not mine) - is the implication that it doesn't have to be?
- I find your notation a bit questionable, where you have used $\tilde$.

# TOWARDS NONPARAMETRIC CAUSAL DISCOVERY

- In your penultimate sentence of this section you say "our proposed procedure could potentially be used" - do you actually go on and use it for this?
- In your final sentence you say: "this may help reduce the running time and improve the scalability of these methods" - well, does it?

Implication alone is not a very powerful device if you do not demonstrate said implication in the paper. Certainly, many methods and ideas have lots of implications, but if they are not empirically or otherwise shown, they hold little value beyond the idea itself. Given that ML is a rather practical field, this is not very useful.

# EXPERIMENTS

- Finally, we are told what 'SING' stands for on page 8.
- If I have read your results correctly, the following is true: 1(a) GS wins on all dimensions; 1(b) it is unclear if GS or your method is better in all dimensions; 1(c) GS wins again 1(d): yours wins by a mile 1(e) you win against the only other method you are comparing against, a method which is only efficient on Gaussian distributions. Same with 1(f).
- I would recommend you scale your results with the figures in table 1 - this way your method will look far more impressive. At the moment, it looks like you are 'beaten' in half of your own experiments. 

summary_of_the_review: There are many parts that I find questionable and I did not check the maths in detail (time constraints). I am willing to update my score should my concerns be adequately addressed. But as it stands this is a dense paper which lacks an adequate narrative to make it legible let alone understandable. There are too many unsupported claims, too many undefined acronyms and missing proofs (or even sketches) to make this (as it stands) a good paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper introduces a novel technique to estimate Markov networks from data, that is, discovering conditional independence relations between variables. While previous approaches could only be applied to either continuous or discrete random variables, the paper presents a framework which applies to both and to mixed type data. The resulting algorithm is also faster compared to those in the literature. The approach used is based on regularized score matching. In the case of continuous data the paper uses a method already established in the literature, while for discrete type data the method itself presents some novel aspects. Some numerical experiments are presented to validate the claim of better scalability.
strength_and_weaknesses: 
Strengths
1. Sections 1 and 2 are well written and clear. Same for section 3 except for some minor problems (see below).
2. The characterization of conditional independence for discrete and mixed type variables in section is novel and has potential to be used also in different algorithms (not necessarily based on score matching)
3. Potentially much faster method of discovering conditional independence relations (but must be verified with further numerical experiments) compared to what exists in the literature.

Points of improvement
1. In page 3 line 6. It is unclear what it means that $\Omega$ is differentiable (i.e. differentiable with respect to what?)
2. In equation 9 should the integral be over $\mathbb R^d$ ?
3. The way to recover the matrix $\Omega$ once the score matching has been run is not immediate to see. Some comments about this are necessary (for example the average over $p$ in (3) is over $p_x(x)$ or over the fitted model $p(x|\theta)$? )
4. Typo regualrized  pag 9.
5. The novelty of an algorithm that infers Markov networks from mixed type data is unclear. One is in fact confused when, in the setting of mixed variables, the algorithm developed in this paper is compared with two other algorithms: KCI and GS. To make a stronger point about the novelty of the method one should comment on these two algorithms and, if relevant, mention them among the previous works.
6. For clarity I would suggest specifying that in a practical setting $p_x(x)$ is the the empirical data distribution given by $n$ samples, sampled from the data distribution.
7. The Markov Random Field considered in the experiments (Butterfly model) is very simple: the associated MRF is just a collection of r disconnected pairs of variables. This makes it hard to evaluate the potential of the method on more complex random fields. I would suggest using something like a random graph as MRF (for example following what is done in [Zhang et al. 2012]) 
8. Several details are missing in the numerical experiments. This information is critical to understand how the results were obtained and to appreciate their significance:

    (a) What are the parameters \theta used in the experiments? In other words what is the parametric family that is being fitted to the butterfly model?

    (b) How is the loss optimized? (e.g. gradient based methods,…) 

    (c) Is the optimization guaranteed to reach the global minimum? Is the problem convex?

    (d) In the context of mixed type data the meaning of «mix the two types of pairs for the mixed type case» as a way of specifying how the data were generated is not clear. The description of the generative process for discrete data should also be made more precise.

    (e) When saying «we also conduct experiments on large graphs» all the details about these experiments must be provided.


clarity,_quality,_novelty_and_reproducibility: The theoretical part of the paper is written in a clear way and contains novel elements such as a characterisation of conditional independence for discrete and mixed type variables. 
Moreover a new algorithm which is able to infer a Markov network from (mixed type) data is introduced.
The novelty of an algorithm that infers the MRF from mixed type data (as opposed to only continuous or discrete data) is unclear.  This is due to the fact that, for mixed type data, the authors benchmark their algorithm against two other algorithms.
In the current state not enough details about the numerical experiments are provided for them to be reproducible. 
The true potential of the algorithm is at this point unclear, due to the very simple setting in which the authors test it.
summary_of_the_review: The paper contains some interesting results about the characterisation of conditional independence. Moreover a new algorithm is proposed to infer Markov networks from data. While the theoretical results seem sound, it is very difficult to evaluate the algorithm due to several missing details. A revision of the experimental part is needed to accept the paper.

In the rebuttal the authors have satisfactorily addressed the totality of the points I raised, for this reason I recommend that the paper be accepted.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a scalable estimation method for non-parametric Markov network structures, using regularized score matching. 
They first introduce necessary and sufficient conditions of conditional independence between variables in general distributions for all data types (i.e., continuous, discrete, and mixed-type) without specific assumptions on functional relations among variables. 
They also introduce appropriate penalties on the characterization matrix, to promote constantly sparse entries for
stable estimation. 
strength_and_weaknesses: Strength ：
It is the first attempt to estimate Markov networks for all data types (i.e.,continuous, discrete, and mixed-type)
The esitmation method is scalable ( up to 5000 nodes within one hour on CPUs )

Weaknesses ：
- There's no experiments on real-world examples except only some comparisons are conducted on synthetic examples.

Questions:
-  why do not consider comparing the method of [1] in your final experiments, for mixed-type data ?

[1] Liu, H., La erty, J. D., and Wasserman, L. (2009). The nonparanormal: Semiparametric estimation of high dimensional undirected graphs. The Journal of Machine Learning Research, 10:2295–2328.
clarity,_quality,_novelty_and_reproducibility: Overall, the paper is well written and the most technical parts are easy-to-follow.
 


summary_of_the_review: This paper presents a scalable estimation method for non-parametric Markov network structures.
It addresses the limitations of previous related methods in handling all data types (i.e., continuous, discrete, and mixed-type).
To me, it should be accepted based on its high quality and novelty.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: All reviewers agree this paper should be accepted. I think the reviews summarize very well the strengths and weaknesses of the paper as well as points that the authors should include in the revised version. I think this will be a great addition to the conference.
justification_for_why_not_higher_score: While this is a very nice paper I did not see any particular reason for a highlight. But would not be against either. 
justification_for_why_not_lower_score: No reason to reject.
Decision: Accept: poster