Generalized Precision Matrix for Scalable Estimation of Nonparametric Markov Networks
Authors: Yujia Zheng
Ignavier Ng
Yewen Fan
Kun Zhang
Venue: ICLR 2023 poster (2023)
Keywords: Structure learning
Markov networks
graphical models
score matching
model selection

Abstract: A Markov network characterizes the conditional independence structure, or Markov property, among a set of random variables. Existing work focuses on specific families of distributions (e.g., exponential families) and/or certain structures of graphs, and most of them can only handle variables of a single data type (continuous or discrete). In this work, we characterize the conditional independence structure in general distributions for all data types (i.e., continuous, discrete, and mixed-type) with a Generalized Precision Matrix (GPM). Besides, we also allow general functional relations among variables, thus giving rise to a Markov network structure learning algorithm in one of the most general settings. To deal with the computational challenge of the problem, especially for large graphs, we unify all cases under the same umbrella of a regularized score matching framework. We validate the theoretical results and demonstrate the scalability empirically in various settings.

GENERALIZED PRECISION MATRIX FOR SCALABLE Es- TIMATION OF NONPARAMETRIC MARKOV NETWORKS
Yujia Zheng': 1 Ignavier Ng', Yewen Fan', Kun Zhang!
1 Carnegie Mellon University
2 Mohamed bin Zayed University of Artificial Intelligence
(yujiazh, ignavierng, yewenf, kunz1 (ecmu.eu
ABSTRACT
A Markov network characterizes the conditional independence structure, or Markov property, among set of random variables. Existing work focuses on specific fami- lies of distributions (e.g., exponential families) and/or certain structures of graphs, and most of them can only handle variables of single data type (continuous discrete). In this work, we characterize the conditional independence structure general distributions for all data types (i.c., continuous, discrete, and mixed-type) with a Generalized Precision Matrix (GPM). Besides, we also allow general func- tional relations among variables, thus giving rise Markov network structure learning algorithm in one of the most general settings. To deal with the computa- tional challenge of the problem, especially for large graphs, we unify all cases under the same umbrella of a regularized score matching framework. We validate the theoretical results and demonstrate the scalability empirically in various settings.
INTRODUCTION
Markov nelworks (also known Markov random fields) represent conditional dependencies among random variables. They provide clear semantics in a graphical manner to cope with uncertainty in probability theory, with wide application in fields including physics (Cimini al., 2019), chemistry (Dodani et al.. 2016), biology (Jaimovich et al., 2006), and sociology (Carrington et al., 2005). The undirected nature of edges also allows cyclie, overlapping, or hierarchical interactions (Shen et al., 2009). To estimate the Markov network from observational data, existing work focuses on certain parametric families of distributions, a majority of which study the Gaussian case. By assuming that the variables are from multivariate Gaussian distribution, the dependencies can be well represented by the support of the precision, or inverse covariance, matrix according to Hammersley-Cliftee CCiiffrd theorem (Besag. 1974; Grimmett, 1973). Together with various statistical estimators (c.g., the graphical lasso (Friedman et al., 2008) and neighborhood selection (Meinshausen & Bühlmann, 2006)), this connection between the precision matrix and graphical structure has been well exploited in the Gaussian case in the past decades (Yuan, 2010; Ravikumar et al., 201 1). However, methods for Gaussian graphical models fail to correctly capture dependencies among variables deviating from Gaussian or including nonlinearity (Raskutti et al., 2008; Ravikumar et al., 2011).
While non-Gaussianity is more common in real-world data generating process, few results are applicable to Markov network structure learning on non-Gaussian data. In the discrete setting, Ravikumar al. (2010) showed that binary Ising model can be recovered by neighborhood selection using & penalized logistic regression. Loh & Wainwright (2013) encoded extra structural relations in the proposed generalized covariance matrix to model the dependencies for Markov networks with certain structures (e.g., tree structures or graphs with only singleton separator sets) among variables from exponential families. Several approaches allowed estimation for non-Gaussian continuous variables while most of them assumed parametric assumptions such as the exponential families (Yang et al., 2015; Lin et al., 2016; Suggala et al., 2017) or Gaussian copulas (Liu et al., 2009; 2012; Harris & Drton, 2013). These methods illustrate the possibility of reliable Markov network estimations in several Non-Gaussian cases, but still, the models are restricted to specific parametric families of distributions and/or structures of conditional independencies.

---

Concerned with describing Markov properties of non- non-Gaussian data with general continuous distribu- tions, Morrison et al. (2017) used the second-order derivatives to encode the conditional independence structure. Specifically, their approach is based theorem that the zero pattern in the Hessian matrix of the log-density determines the conditional independencies between non-Gaussian continuous variables (Spantini et al., 2018). A method based on transport map, i.e., Sparsity Identification in Non-Gan non-Gaussian distributions (SING) (Baptista et al., 2021), is then designed to estimate the data density from samples, and the structure is derived from the estimated density. This approach achieves consistent Markov network structure recovery in general non- Gaussiann continuous setting. However, methods relying on the Hessian matrix cannot cope with discrete or mixed-typs -tpp data. In addition, density estimation, especially for non-Gaussian data, can be computationally challenging for large graphs, limiting the scalability of this approach. Kernel-based Conditional Independence test (KCI) (Zhang et al., 2012) and Generalized Score (GS) (Huang et al., 2018) can handle the mixed-type case for structure learning, but as kernel-based methods, they are computationally challenging since the complexity scales cubically in the number of samples.
To deal with these remaining obstacles, we explore a Generalized Precision Matrix (GPM) for nonparametrie Markov networks learning. Based the necessary and sufficient conditions for the conditional independence among structures in continuous, discrete, and mixed-type cases, GPM characterizes the Markov network structures with arbitrary data types. Moreover, our work does not constrain the distribution to be of specific families, such as exponential families, or has been normalized. Besides, it is also noteworthy that there are no specific assumptions on the functional relations among variables. To the best of our knowledge, the proposed GPM illustrates the feasibility of Markov network structure learning in one of the most general nonparametric settings.
Furthermore, we put all these cases under the same umbrella of the estimation framework based on regularized score matching, as an extension of the score matching framework (Hyvärinen Dayan, 2005). Different from the previous approach (SING) that applies a transport map to estimate the data density for general continuous distributions, our framework allows us to only estimate the model score function parameterized by deep model, from which the characterization matrix of the Markov network structure can be directly calculated. To facilitate the estimation process, we also exploit suitable penalties on the characterization matrix to encourage constantly sparse entries. Besides, we adopt recent advancements on score matching (Song et al., 2020) to further scale up the process. Our method therefore narrows the gap between reliable structure learning and scalable deep learning techniques. We validate the theoretical results experimentally, and the scalability has been illustrated.
2 GENERALIZED PRECISION MATRIX
Suppose that we observe a collection of random variables X = (X1....,XX, Xa). Our goal is to discover the underlying Markov network structure. Specifically, it is an undirected graph & comprising a set of vertices V {1,...,d) d) and edges E. The edges E encode the conditional independence relations or the global Markov property: for any disjoint subsets A, B, and C in the vertices set V such that C separates A and B, XA and XB are conditionally independent given Xc, i.e., XA XB Xc. Throughout this paper, we use an uppercase letter to denote a random variable and a lowercase letter with subscripts denote the value of a random variable (e.g., X; I, for the value of X,). For ZiM, }, where M, is its cardinality.
a discrete variable, say X,, we denote its support by
As an alternative characterization of the conditional independence relations encoded by the graph, the pairwise Markov property requires that every pair of non-ad adj-adjccent variables in the graph is conditionally independent given the remaining variables. That is, for any i * j, an edge between X; and X, is absent if and only if X; and X; are conditionally independent given the remaining variables, i.c., X; T Xj Xv The conditioning set consisting of all remaining variables is essential. According to Lauritzen (1996), the pairwise Markov property is equivalent to the global one when the density is strictly positive. In order to estimate nonparametric Markov networks in this setting, we explore generalized characterizations of conditional independence in all types of data (i.e., continuous, discrete, and mixed-type without distributional constraints. We start from learning conditional independence structures in continuous data with a procedure inspired by Spantini et al. (2018), 8), and then propose new characterizations for discrete and mixed-type data.
For any set S C V, we write Xş {Xe:de S}.
2

---

Ideally, aim to construct Generalized Precision Matrix Q that satisfies the following desiderata:
a. For any + j. if Di.5 = O, then X; X3 Xvv(a):
b. The probability measure is not restricted to be from specific families but only needs to be strictly positive;
The undirected graph G is not restricted to be of certain structures;
d. For continuous variables, the density has continuous derivatives up to second order w.r.t the Lebesgue measure;
c. For discrete variables, the cardinality not restricted:
f. To enable practical estimation procedure, Ω is differentiable w.r.t X.
Property (a) is the characterization the pairwise Markov property. Properties (b) and (c) differentiate work from most previous works that assumes Gaussianity or/and certain structures of the conditional independence. Properties (d) and (c) further raise the difficulty of our task, because, in addition not being restricted specific family of distributions,
characterization f has to be available for all data types (i.e., continuous, discrete, and mixed-type) with mild assumptions. For discrete variables, Property (e) removes the limitation of cardinality, thus differentiating our work from those focusing on the binary Ising model. Property (f) allows us to incorporate an & regularization term in the estimation procedure and make use gradient based optimization.
2.1 CHARACTERIZATION FOR CONTINUOUS DATA
We aim to find the necessary and sufficient conditions for X, I X, X By definition, if X; is conditionally independent of Xj given all remaining variable Xv((l)> we can factor the probability density function (PDF) px as follows
px (x) p(a; Xvyss))p(a; xxxaa)))(xxxa..
(1)
Together with the assumption that has continuous derivatives up to second order w.r.t. the Lebesgue measure, we have
8 log
0.
Ōr,Ūx, Conversely, the solution Eq. (2) is given by log (1111-1,, + I1 for some functions g. h Rd-1 F. It thus follows X, X; Xv.( This connection between pairwise conditional independence and cross derivatives of the log density has been observed in Spantini (2018). Methods based on this connection have also been proposed recently (Morrison al., 2017: Baptista et al., 2021). Following Baptista et al. (2021), one can characterize conditional independence between X; and X, the continuous distribution as
1dd 2 Epx [
(x))))
where (-) denotes the LHS of Eq. (2) and [e] denotes continuous data as type label. In practice, Px is the empirical PDF. The group structure of it could help achieve simultaneous sparse approximation (Yuan & Lin, 2006; Huang & Zhang, 2010) when being applied as an é regularizer in the estimation, which we will describe Sec. 3. We also apply the same group structures both the discrete and mixed-type cases, but will skip the reintroduction for brevity. The characterization of the Markov property is as follows.
Corollary 1. Assume
X = (X1,... Xa) is set of continuous variable.
i. The PDFs of X are strictly positive and smooth.
iii. The characterization matrix Q21el is defined according to Eq. (3).
Then for any i + j. s2. implies X, L Xx, Xv((t))-
The proof is shown in Appx. A.1. It is worth noting that Cor. I also covers the Gaussian case, where the cross-derivatives of the log-density correspond to entries in the precision or inverse covariance matrix (Drton al., 2008), thus generalizing previous work assuming Gaussianity. Hence, the support of Ω characterizes conditional independence among continuous variables for general distributions.
3

---

2.2 CHARACTERIZATION FOR DISCRETE DATA
Since most of the previous work focuses on the Gaussian setting, and works for non- nan-Gausiian distribution are mostly restricted to the exponential family, the characterization for continuous data discussed in Sec. 2.1 has broadened the scope of reliable Markov network learning. However, the characterization is not applicable to discrete data as the gradient does not exist. In this section, we provide such a characterization of Markov network structure in the discrete case. Similar to the continuous case, a key ingredient of the proposed characterization is the necessary and sufficient conditions of conditional independence for discrete data, which we establish in the following theorem.
Theorem 1, Denote V as a set of discrete variables and X, E V. For brevity, denote (y,,,,y} as Z. Let (Iii....,, L,M, J and [Zj1...., [TMM,] be the support of variables X, and x.. Denote z as any value(s) of Then, X, X, Z if and only if. for all i E [M.] and E [M]] with & & 1 and 1 + 1, we have
(log m(=a: Fy1, 2) log m( F, 2)) (221, 2) log m( Fzt, 2)) 0. (4)
Proof sketch. For the sufficient condition, we want to show that the general solution to Eq. has no term that takes the values of both X; and Xy. We first iterate all possible differences w.r.t X, get the discrete score function of X,, which does not take the value of Xj as the argument. Then we obtain the desired solution by summation over all possible differences w.r.t. X,, For the necessary condition, we decompose the PMF according to the conditional independence to obtain Eq. 4.
The full proof is provided in Appx. A.2. Note that we denote m(2 Byt. 2) the joint probability mass function (PMF) of {X,, x,, Z}, simplified from m...X, z (Tikk Zyt. 2). Based on Thm. 1, we propose the characterization matrix of conditional independence for discrete data 22/5) as follows:
24 = Emxx
Σ flul (I11, Tek, Fy1 (it Fst. 2) hd
(5)
where f( (1 Tik. T5t, 2) denotes the LHS of Eq. (4) and [d] is a type label denoting discrete data. The support of the matrix above satisfies the pairwise Markov property and characterizes the Markov network structure, formally stated below with its proof in Appx. A.3.
Corollary 2. Assume
X (X Xa)) is set of discrete variable.
ii The PMFs of X are strictly positive.
The characterization matrix 2244 is defined according to Eq. (5).
Then for any i + j. S.. = implies X; T X2) XVV
Therefore, we have a characterization matrix Qld! to represent the conditional independence structure for discrete data. It worth noting that, unlike the generalized covariance matrix in Loh & Wainwright (2012) that only applies to certain structures among variables from exponential families, the proposed characterization matrix 244 encodes the Markov properties for general discrete distribu- tions without any structural constraints. Also, compared with Ravikumar al. (2010), Thm. can be applied to general graphical models apart from binary Ising models and does not rely on the structural condition. It also does not limit the cardinalities of discrete variables. Hence, Theorem I sheds light on characterizing arbitrary conditional independence structures for general discrete distributions.
2.3 CHARACTERIZATION FOR MIXED-TYPE DATA
In the previous sections, we have presented characterizations of conditional independence structures for both general continuous and discrete distribution. However, it is common for real-world datasets to have mixture of continuous and discrete variables. Unfortunately, most works focus on either continuous discrete data, and previous results for mixed-type data are mostly based conditional Gaussian distribution (Lauritzen et al., 1989; Edwards, 1990; Lauritzen, 1996; Fellinghauer et al., 2013; Lee & Hastie, 2015; Cheng al., 2017). Similar to the continuous and discrete settings,
4

---

in this section, introduce novel characterization of the pairwise Markov property for general distributions with mixed data-types. We first provide necessary and sufficient conditions of conditional independence for mixed-type data in the following theorem, with full proof given in Appx. A.4.
Theorem 2. Denote V as a set of mixed-type variables and X X3 E V, where X; is discrete and Xj is continuous. Let (zil....,Tay
be the support of variables X,. For brevity, denote ( X as Z. Denote as any value(s) of Z and Ij as any value of the continuous variable X₁. Then, X; 11 X3 Z if and only if. for all k [M,] with k + 1, we have
a log 2Ix, (1), Na m,x) (2a))
a Olog (IX, (xg, 2 with (ax (1iak) 0.
(6)
dr,
Proof sketch. Similar to the proof sketch of Thm. 1, we consider X, and X, separately to construct the desired general solution of Eq. 6 for the sufficient condition. For the necessary condition, decompose the density function according to the conditional independence to obtain Eq. 6.
Based Thm. 2, propose to characterize the conditional independence between X, and X, given all remaining variables with the GPM P!m), of which the element is defined as
E xx
(x)
if E XX, EX.
Ω [m]
E Exx
Σx.1 ff (I Pake T,1, 2)²
if E X,, E Xx
(7)
Exx
Ex f flmm
F51. (2. 2)
if E Xc, E X
Exx
Ex f fi (Z,,, Tzl 2)
if E Xa, E Xe,
where fiml denotes LHS of Eq. (6) and xx is the probability function. The type label [m] de- notes mixed-type data. X, and X are sets of continuous and discrete variables, respectively. Its characterization of Markov property is as follows
Corollary 3. Assume
X = (X...... Xa) is set of variables containing both continuous and discrete variables.
i.. For continuous variables, the PDFs are strictly positive and smooth.
ii. For discrete variables, the PMFs are strictly positive.
iv. The characterization matrix Q1mm) is defined according to Eq. (7).
Then for any i i j. m2mll implies X, I1 X, X
The proof is given in Appx. A.5. The GPM Qlml encodes the pairwise Markov property for mixed-type data. More general than previous works, it does not require specific families of distributions, structures of the underlying graph, or cardinality of discrete variables.
3 SCALABLE ESTIMATION WITH REGULARIZED SCORE MATCHING
In Sec. 2, we provide characterizations of conditional independencies for general distribution in continuous, discrete, and mixed-type settings. Based on the introduced necessary and sufficient conditions, these characterizations generalize previous work and establish one of the foundations for nonparametric estimation of Markov network structures with minimal assumptions.
In addition general characterizations of the Markov property with theoretical guarantees (i.e., GPM), a scalable estimation framework necessary for reliable and practical structure learning. Ideally, we would like to exploit the advancements scalable deep learning models. Hence, introduce regularized score matching-baat based framework for all considered settings (i.c., general distributions of continuous, discrete, and mixed-type variables).
5

---

3.1 ESTIMATION FOR CONTINUOUS DATA
We start with the continuous setting. Denote p(x; 0) as a parameterized density model with a parameter vector f. The goal is estimate parameter from the observation x. We aim to optimize the following objective function, which is based on Fisher divergence:
Oc(0) = 2 XER"
p(x) Vx logpo( 0) Vx logp(x))] px
(8)
where px(-) denotes a sparsity penalty function and is the penalty parameter with domain [0, 1]. Q is defined in Eq. 3 as our characterization of the conditional independence structure for continuous data. If we assume the model not degenerate, where different values of I correspond to different PDFs, the asymptotic consistency of the optimization has been shown in Thm. 2 by Hyvärinen & Dayan (2005). We impose a sparsity penalty to encounter for finite-sampling errors in practice.
Also with strategy in Hyvärinen & Dayan (2005); Pham & Garat (1997), one can remove the data log-density logps px from Eq. (8) by optimizing the following equation, which is equivalent to Eq. (8):
logp(x; 0)12 + H2, (logp(x;; 01) dx + px
02(0)
((x)
2E 2
XER
i=1
where H denotes the Hessian. The proof is directly based on Hyvärinen & Dayan (2005) and we worth noting that previous work on
include it (Lemma 1) in Appx. A. for completeness. Markov network structure learning with general continuous distribution (SING (Morrison et al., 2017; Baptista et al., 2021)) applies a transport map to estimate data density from samples, which can be computationally challenging for non- non-Gaussian data with large number of variables. Thus, it may not be scalable as suggested by Fig. 1 and Table 1. To avoid this, the proposed regularized score matching allows us to optimize the objective function by only estimating the model score function. Moreover, the estimated model score function directly leads to the characterization matrix Ω by taking further derivatives, thus efficiently giving rise the estimated Markov network structure. After training, the expectation in Equation is computed over the parameterized model p(x; #).
3.2
ESTIMATION FOR DISCRETE DATA
For the estimation in the discrete case, one cannot directly apply the method introduced for the continuous case since the gradient, on which the continuous score function is based, is not defined for discrete data. An intuitive solution is replace the gradient with general linear operator L (Lyu, 2012). Of course, one also needs to replace integration with summation and PDF with PMF For instance, Eq. (8) can be reformulated follows
1 Σ mx (x) Oa(0) =
[(m(x; 0)) [(mx((x)) m(x:0) 0) mx(x)
? (x(14))
(10)
where m denotes PMF. In this formulation, 2(-) is generalized version of the score function for discrete data. As shown in Lyu (2012), Oa(0) keeps the computational advantages of score matching for continuous data, i.e., the normalizing partition is canceled out and the formulation can be transformed to expectation of functions of the unnormalized model. In order to guarantee the consistency of score matching based on Eq. (10), the linear operator L(.) needs to be complete according to the following definition.
Definition (Completeness (Lyu, 2012)). A linear operator L()) is complete if L(p(x)) Elg(x)) implies p(x) q(x) almost everywhere, where p(x) and q(x) are two PMFs.
p(x) 9(x)
According to Defn. 1, Lyu (2012) used the marginalization operator M(-) F Jrd choice for C(.,, which is defined as
M(f(x)) (arron) )
Ex Ex((x)
(1I)
6

---

where f E Fl. We can observe that Mx) is the marginal density of x where x' denotes the vector x after dropping the i-th element (i.e., marginalization). The completeness of M(-) has been shown in Brook (1964), and included Lemma 3 in Lyu (2012). We have
M(m(x: 0)) M(mx(x)) 2 m(x;0)
O₂(0) - Σ mx
+ PX
(12)
mx(x)
Thus, it is plausible for us to replace the gradient with M(-) for discrete data. However, one key advantage of regularized score matching that it does not have explicitly estimate the data density (i.e., px (x) in Theorem 1). As shown by Lyu (2012), we can also optimize Eq. (12) in a similar way, which is equivalent optimizing the following equation
0a(0) =
1 Σ mx (x)
Σ
[
(Mi(m(x00)) 2 m(x;0)
2M; (MMimni [m(x:0 0)
+ PA(1)))). (13)
The simplification is directly from results in Lyu (2012), of which the corresponding lemma (Lemma 2) is formalized with its proof in Appx. A.6.2 for completeness. Based on Thm. and Thm. 2. similar the continuous case, can estimate Markov network structures for general distributions in the discrete setting under the same umbrella of regularized score matching.
3.3 ESTIMATION FOR MIXED- TYPE DATA
For mixed-type data, we define the objective function as follows
O = Exx
Σ (x
+ (x(smm)))
(14)
where
1 I1 R., log (x; - Ha,
X; E X.
(x 0)
(15)
M.(m(xx)) M; (M
(
X; E Xd,
Here, the density æ is strictly positive. Basically, Om is regularized version of the combination of the objective functions for the continuous and discrete cases. Because [[m]] also encodes the dependencies between continuous and discrete variables, we can estimate its support for mixed- type data without assuming group structures of data types. The following corollary guarantees the consistency, where we define O', (0) as O (0) (x(1mm)).
Corollary 4. Assume
The data density Tx(.) is equal to T(:;0") (0)0")orr some 0*.
it. The data density xx(+) and model density T(:; 0) are strictly positive. πx(.) and x(: 0) is differentiable and twice-differentiable respectively, w.r.t. continuous variables. For some 8", xx(+) = =(=;0*) and no other parameter value gives a density that is equal to π T(:;6*) almost everywhere.
The expectations Eax [I] log (xx; 0)][a] and Eax [Mlog x (x)]]] are finite for any and T x (x) log π (xx; 0) goes to zero for any 0 when ||x] -
Then O (0) 0 implies 0 = 0".
Cor. 4 follows from Lemma (Hyvärinen & Dayan, 2005) and Lemma (Lyu, 2012), which included in Appx. A.6. Together with Thm. 2, one can estimate Markov network structures for mixed-type data in general setting.
3.4 SPARSITY REGULARIZATION
By minimizing the objective function O(0) (O.(0), O. (O)), our goal is essentially perform model selection task, i.e., to learn of the support of Ω S2lel,224 Qiml3. Here, using
7

---

to penalty may be computationally infeasible because it leads to discrete optimization problem that is difficult to solve. Following previous works (Tibshirani, 1996), we adopt the ( regularizer (x() = X||22|1 In particular, the high-dimensional support recovery of & regularizer has been extensively studied in the literature; for instance, see Wainwright (2009) for variable selection and Ravikumar et al. (2008) for Gaussian graphical model selection. Although & regularizer induces sparsity, it may lead to bias in the resulting solution and thereby worsen the performance (Fan & Li, 2001; Breheny & Huang, 2011). This is because the E norm increases linearly with the absolute value of nonzero entries, which is different from En norm that is constant for nonzero entries. Therefore, we experiment with smoothly clipped absolute deviation (SCAD) penalty (Fan & Li, 2001), minimax concave penalty (MCP) (Zhang, 2010), and adaptive l penalty (Zou, 2006) in this work, which helps remedy the bias issue of & regularization. Specifically, SCAD and MCP penalties may be interpreted as hybrid of lo and l penalties, while adaptive & penalty reweighs the penalty coefficient À by the initial estimate of S2 without regularization. Furthermore, the support recovery of & penalty relies on the incoherence condition in various cases (Wainwright, 2009; Ravikumar et al., 2008; 2011), 1), which may be a rather strong assumption in practice, whereas the SCAD and MCP penalties do not (Loh & Wainwright, 2017). Thus, we adopt the SCAD penalty according to experimental results (Fig. 7 in Appx. B). We integrate the SCAD penalties for all cases but only introduced here for brevity.
4 EXPERIMENTS
Setup. We conduct experiments on two sets of distributions: (1) Butterfly distributions (Morrison
et al., 2017: Baptista et al., 2021) and (2) distributions from random graphs. For Butterfly distribution in the continuous setting, we have r i.i.d. pairs of random variables (P,, Qi) defined as P; ~ No,, 1) and Q; W.P; with W; ~ (N00) 1) and W; 1. P.. We replace the Gaussian distribution with the Multinomial distribution for the discrete case and mix the two different types of pairs for the mixed-type case with uniformly sampled proportion. For distributions from random graphs, first generate a random decomposable directed acyclic graph. Then, for the continuous case, the data are sampled from nonlinear structural equation models (SEMs) with exogenous noises from an exponential distribution. We employ a multilayer perceptron (MLP) with randomly generated weights as the nonlinear function. For the discrete case, variables generated via randomly parameterized Multinomial distributions of the variable being simulated and the discrete parents (Andrews et al., 2018). For the mixed-type case, we simulate data with the process described in Andrews et al. (2018), of which the details are included in Appx. B. Finally, we moralize all random decomposable DAGs to obtain the ground-truth Markov network structures. We use the deep kernel exponential family (DKEF) during estimation and optimize the objective function by gradient descent with the Adam optimizer. All experiments are on 12 CPU cores with 24 GB RAM.
Considered methods. We consider the following representative methods for comparison: (KCI) We adopt Kernel-based Conditional Independence test (KCI) (Zhang et al., 2012) with the Incremental Association Markov Blanket (IAMB) algorithm (Tsamardinos et al., 2003) to learn the Markov net- work structure in our settings. (GS) We denote GS as Greedy Equivalence Search (GES) (Chickering, 2002) with Generalized Score (GS). Because this procedure estimates causal structures represented by completed partially DAGs (CPDAGs), we moralize the results to obtain the Markov network struc- tures. (SING) Sparsity Identification in Non-Gaussiaa distributions (SING) (Morrison al., 2017; Baptista et al., 2021) is an algorithm designed for the estimation of Markov networks in non-Gaussian continuous distributions. It applies transport map to estimate the data density. (GLASSO) Graphical Lasso (GLASSO) is a classical sparse penalized estimator for the inverse covariance matrix. (NPN) GLASSO with the nonparanormal transformation (Liu al., 2009).
Results. We first conduct comparisons in general distributions for all data types (i.c.. discrete, continuous, and mixed-type) with different numbers of variables and a sample size of 1000. Among the considered methods, both KCI and GS are available for the estimation of Markov network structures for general distributions with all data types. SING can only deal with continuous data and is therefore only applied in the continuous setting. We also include (semi)parametrrc methods (GLASSO and NPN) for baselines in the considered general settings. We use Hamming distance between the estimated graph and the ground truth graph as the metric. All results are from trials with different random seeds. The missing results are either due timeout (i.e., > day) or OOM.
Table 1: Running time for 12 variables.
Method
Ours
KCI
GS
SING
GLASSO
NPN
Time (s)
62.9
247
9536.5
4020.3
4.4
20.8
8

---

140
100
160-
120
KCI
KCI
KCI
Hamming distance
200
distance
65
Hammine distance
GLASSO
200
NPN
60-
60
40
40
20
12 Dim
14
16
10
20
Dim
Dim
(a) Continuous
(b) Discrete
(c) Mixed-typp
Figure 1: Hamming distances for Butterfly distributions.
140
Durs
60
Durs
Ours
KCI
KG
Hamminng distacce
120
GS
Homminng distance
50
Hammming distance
GS
SING
GLASSO
80
GLASSO
40
a0-
10-
12
16
20
6
8
10
12 Dim
14
16
18
20
10
12
14
16
18
20
Continuous
(b) Discrete
(c) Mixed-type
Figure 2: Hamming distances for distributions from random graphs.
For the Butterfly distributions (Fig. 1), one can observe that KCI, GS, and our method can almost recover true structures with all data types.
same time, in the more complex setting (i.e., dis- tributions from random graphs, Fig. 2), it is clear that our method outperforms others in most datasets. This suggests that, compared to baselines, our method may have more obvious advantages more complicated scenarios. Mcanwhile, the rumning times of KCI, GS, and SING are significantly longer than that our method (Table. 1). Besides, SING and GS cannot scale with more than 12 and 18 vari- ables, respectively. GLASSO and NPN remarkably fast but fail to accurately recover the structure in the general setting. NPN performs worse than GLASSO in structure recovery, which may be due its misaligned hypothesis of the nonparanormal transformation in the general mixed-type setting.
We also conduct experiments on large graphs, with (250, 500,.... 5000) continuous variables from Butter- fly distributions. Other settings are identical to those for smaller graphs. From Fig. 3, observe that the running time is approximately linear w.r.t. the number of variables. Besides, all experiments are conducted on CPUs while our framework could be easily deployed on GPUs. This suggests the potential of taking advantage of recent advances in computation, especially for deep models, to even further improve the scalability.
2500
1500
500
Dm
Figure 3: Running time for large graphs.
5 CONCLUSION
We provide scalable estimation framework based on regularized score matching for nonparametric Markov network structures. We first introduce necessary and sufficient conditions of conditional independence among variables in general distributions for all data types (i.e., continuous, discrete, and mixed-type) without specific assumptions on functional relations among variables, thus giving rise to the corresponding characterizations of the structure, i.e., Generalized Precision Matrix. Then, unify all these cases under the same umbrella of the estimation framework based on regularized score matching. Appropriate penalties on the characterization matrix introduced to promote constantly sparse entries for stable estimation. We validate our theoretical claims experimentally various settings. Future work includes exploring the connection between Markov networks and causal graphs.

---

6 ACKNOWLEDGMENT
We thank the anonymous reviewers for their constructive comments. This project was partially supported by the National Institutes of Health (NIH) under Contract ROIHL159805, by the NSF- Convergence Accelerator Track-D award #2134901, by a grant from Apple Inc., grant from KDDI Research Inc, and generous gifts from Salesforce Inc., Microsoft Research, and Amazon Research.
REFERENCES
Bryan Andrews, Joseph Ramsey, and Gregory F Cooper. Scoring bayesian networks of mixed variables. International journal of data science and analytics, 6(1):3-18 18, 2018.
Ricardo Baptista, Youssef Marzouk, Rebecca E Morrison, and Olivier Zahm. Learning non-gaussian graphical models via hessian scores and triangular transport. arXiv preprint arXiv:2 200.v:2001.0303. 10100309, 2021.
Julian Besag. Spatial interaction and the statistical analysis of lattice systems. Journal of the Royal Statistical Society: Series B (Methodological), 36(2): 1974.
Patrick Breheny and Jian Huang. Coordinate descent algorithms for nonconvex penalized regression, with applications to biological feature selection. The Annals of Applied Statistics, 5(1):232-253, 2011.
D Brook. On the distinction between the conditional probability and the joint probability approaches in the specification of nearest-neighhour systems. Biometrika, 51(3/4):481-45) 1964.
Peter J Carrington, John Scott, and Stanley Wasserman. Models and methods in social network analysis, volume 28. Cambridge university press, 2005.
Jie Cheng, Tianxi Li, Elizaveta Levina, and Ji Zhu. High-dimensional mixed graphical models. Journal of Computational and Graphical Statistics, 26(2):367-378, 2017.
David M. Chickering. Optimal structure identification with greedy search. Journal of Machine Learning Research, 3(Nov):507-55) 2002.
Giulio Cimini, Tiziano Squartini, Fabio Saracco, Diego Garlaschelli, Andrea Gabrielli, and Guido Caldarelli, The statistical physics of real-world networks. Nature Reviews Physics, 1(1):58-71, 2019.
Sheel C Dodani, Gert Kiss, Jackson KB Cahn, Ye Su, Vijay S Pande, and Frances H Amold. Discovery of a regioselectivity switch in nitrating p450s guided by molecular dynamics simulations and 2016.
markov models. Nature chemistry, 8(5):419
Mathias Drton, Bernd Sturmfels, and Seth Sullivant. Lectures on algebraic statistics, volume 39.
Springer Science & Business Media, 2008
David Edwards. Hierarchical interaction models. Journal of the Royal Statistical Society: Series (Methodological), 52(1):3-20, 1990.
Jianqing Fan and Runze Li. Variable selection via nonconcave penalized likelihood and its oracle properties. Journal of the American statistical Association, (14456):1348-1366 2001.
Bernd Fellinghauer, Peter Bühlmann, Martin Ryffel, Michael Von Rhein, and Jan Reinhardt. Stable graphical model estimation with random forests for discrete, continuous, and mixed variables. Computational Statistics & Data Analysis, 64:132-152, 2013.
Jerome Friedman, Trevor Hastie, and Robert Tibshirani. Sparse inverse covariance estimation with the graphical lasso. Biostatistics, 9(3):432-441 2008
Geoffrey R Grimmett. A theorem about random fields. Bulletin of the London Mathematical society, 5(1):81-84, 1973.
Naftali Harris and Mathias Drton. Pe algorithm for nonparanormal graphical models. Journal of Machine Learning Research, 14(11), 2013.
10

---

Biwei Huang, Kun Zhang. Yizhu Lin, Bernhard Schölkopf, and Clark Glymour. Generalized score functions for causal discovery. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 1551-1560, 2018.
Junzhou Huang and Tong Zhang. The benefit of group sparsity. The Annals of Statistics, 38(4): 1978-2004, 2010.
Aapo Hyvärinen and Peter Dayan. Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research, 6(4), 2005.
Ariel Jaimovich, Gal Elidan, Hanah Margalit, and Nir Friedman. Towards integrated protein- protein interaction network: A relational markov network approach. Journal of Computational Biology, 13(2):145-164, 2006.
Steffen L Lauritzen. Graphical models, volume 17. Clarendon Press, 1996.
Steffen L Lauritzen, Anders Holst Andersen, David Edwards, Karl G Jöreskog, and Søren Johansen. Mixed graphical association models [with discussion and reply]. Scandinavian Journal of Statistics, pp. 273 306, 1989.
Jason D Lee and Trevor J Hastie. Learning the structure of mixed graphical models. Journal of Computational and Graphical Statistics, 24(1):230-22 253,,53,, 2015.
Lina Lin, Mathias Drton, and Ali Shojaie. Estimation of high-dimensional graphical models using regularized score matching. Electronic journal of statistics, 10(1):806, 2016.
Han Liu, John Lafferty, and Larry Wasserman. The nonparanormal: Semiparametric estimation of high dimensional undirected graphs. Journal of Machine Learning Research, 10(10). 2009.
Han Liu, Fang Han, and Cun-hui Zhang. Transelliptical graphical models. Advances in neural information processing systems, 25, 2012.
Po-Ling Loh and Peter Bühlmann. nigh-dimensional learning of linear causal networks via inverse covariance estimation. Journal of Machine Learning Research, 15(88)33065-3105 2014.
Po-Ling Loh and Martin J Wainwright. Structure estimation for discrete graphical models: General- ized covariance matrices and their inverses. Advances in Neural Information Processing Systems, 25, 2012.
Po-Ling Loh and Martin Wainwright. Structure estimation for discrete graphical models: General- ized covariance matrices and their inverses. The Annals of Statistics, (6):3022233)49 2013.
Po-Ling Loh and Martin J. Wainwright. Support recovery without incoherence: A case for nonconvex regularization. The Annals of Statistics, 45(6):2455-2482. 2017.
Siwei Lyu. Interpretation and generalization score matching. arXiv preprint arXiv:1205.2629. 2012.
Nicolai Meinshausen and Peter Bühlmann. figh-dimensional graphs and variable selection with the lasso. The annals of statisties, 34(3):1436- 1466,,162,410 2006.
Rebecca Morrison, Ricardo Baptista, and Youssef Marzouk. Beyond normality: Learning sparse probabilistic graphical models in the non-gaussian setting. Advances in neural information processing systems, 30, 2017.
Ignavier Ng, Yujia Zheng, Jiji Zhang, and Kun Zhang. Reliable causal discovery with improved exact search and weaker assumptions. In Advances in Neural Information Processing Systems, 2021.
Dinh Tuan Pham and Philippe Garat. Blind separation of mixture of independent sources through quasi-mane munsi-maximum likelihood approach. IEEE transactions on Signal Processing, 4527) 1997.
Garvesh Raskutti, Bin Yu, Martin J Wainwright, and Pradeep Ravikumar. Model selection in gaussian graphical models: High-dimensional consistency of reguuaagea mle. Advances in Neural Information Processing Systems, 21, 2008
11

---

Pradeep Ravikumar, Garvesh Raskutti, Martin Wainwright, and Bin Yu. Model selection in Gaussian graphical models: High-dimensional consistency of & f1-reuularized MLE. In Advances in Neural Information Processing Systems, 2008.
Pradeep Ravikumar, Martin J Wainwright, and John Lafferty. High-dimensional ising model selection using 1-regularized logistic regression. The Annals of Statistics, 38(3):1287-1319, 2010.
Pradeep Ravikumar, Martin Wainwright, Garvesh Raskutti, and Bin Yu. High-dimensional covari- ance estimation by minimizing & (1-penalized -eg-determinant divergence. Electronic Journal of Statistics, 5:935-980, 2011.
Huawei Shen, Xueqi Cheng, Kai Cai, and Mao-Bin Hu. Detect overlapping and hierarchical community structure in networks. Physica A: Statistical Mechanics and its Applications, 388(8): 1706-1712, 2009.
Yang Song. Sahaj Garg, Jiaxin Shi, and Stefano Ermon. Sliced score matching: A scalable approach to density and score estimation. In Uncertainty in Artificial Intelligence, pp. 574-584. PMLR, 2020.
Alessio Spantini, Daniele Bigoni, and Youssef Marzouk. Inference via low-dimensional couplings. The Journal of Machine Learning Research, 19(1):2639-2700 2018.
Peter Spirtes and Clark Glymour. An algorithm for fast recovery of sparse causal graphs. Social Science Computer Review, 9:62-72, 1991.
Arun Suggala, Mladen Kolar, and Pradeep K Ravikumar. The expxorcist: Nonparametric graphical models via conditional exponential densities. Advances in neural information processing systems, 30, 2017.
Robert Tibshirani. Regression shrinkage and selection via the Lasso. Journal of the Royal Statistical Society. Series B (Methodological), 58(1):267-288, 1996.
loannis Tsamardioos, Constantin Aliferis, Alexander R Statnikov, and Er Statnikov. Algorithms for large scale markov blanket discovery. In FLAIRS conference, volume 2, pp. 376-380. St. Augustine, FL, 2003.
Martin J. Wainwright. Sharp thresholds for high-dimensions and noisy sparsity recovery using I -constrained quadratic programming (Lasso). IEEE Transactions on Information Theory, 55()): 2183-2202. 2009.
Eunho Yang, Pradeep Ravikumar, Genevera I Allen, and Zhandong Liu. Graphical models via univariate exponential family distributions. The Journal of Machine Learning Research, 16(1): 3813-3847, 2015.
Ming Yuan. High dimensional inverse covariance matrix estimation via linear programming. The Journal of Machine Learning Research, 11:2261-2286, 2010.
Ming Yuan and Yi Lin. Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society: Series (Statistical Methodology). 68(1 (874)) 2006.
Cun-Hui Zhang. Nearly unbiased variable selection under minimax concave penalty. The Annals of Statistics, 38(2):894 942, 2010.
Kun Zhang, Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Kernel-based conditional independence test and application in causal discovery. arXiv preprint UrXiv:1202.3777 2012.
Hui Zou. The adaptive lasso and its oracle properties. Journal of the American statistical association. 101(476):141 1418 418444184444 1429, 2006.
12

---

Appendix
Table of Contents
Proofs
A.1 Proof of Corollary
13
A.2 Proof of Theorem
14
A.3 Proof of Corollary 2
15
A.4 Proof of Theorem 2
15
A.5 Proof of Corollary 3
17
A.6 Proof of Corollary 4
18
B Experiments
20
Generating process for mixed-lype data
20
B.2 Influence of sample size
20
B.3 Influence of different penalty functions
22
C Discussion
22
C.I Towards nonparametric causal discovery
22
A PROOFS
A.1 PROOF OF COROLLARY
Corollary 1. Assume
(XI,..., is set of continuous variable.
it. The PDFs X X are strictly positive and smooth.
ii The characterization matrix Qiel is defined according to Eq. (3).
Then for any i + j. s2. O implies X; 1 XX, Xv((i>>-
Proof. According to Eq. (3), it is clear that when 260 0, we have 8 loggx O, which is de,de, necessary and sufficient condition x; 1 x, vv for strictly positive, smooth, and continuous distributions shown in Sec. 2.1.
is worth noting that it also applies the Gaussian case, where X N Σ) is Gaussian vector with mean and non-singular covariance E. In this case, we have
(xx (x
p1)
T (x 11) 111)
Px(x) x exp
(16)
2
which implies
8 log Px Or,On. (Σ 12
(17)
where 2 denotes the corresponding entry of the inverse covariance matrix. This well-known property of Gaussian distribution was also shown in Baptista et al. (2021); Drton et al. (2008).
Because the inverse covariance matrix encodes the conditional independence structure when variables
from Gaussian distributions, Qle) characterizes the Markov property for the Gaussian case. n
13

---

A.2 PROOF OF THEOREM 1
Theorem 1. Denote V set of discrete variables and X,,X, E V. For brevity, denote
VX,,, as Let (Tal...., TiM. } and
-.]MM)) be the support of variables X; and
x. Denote as any value(s) o. Then, X, 1. X, Z if and only if. for all & E [M.] and E [M] with & + and + 1, we have
(log m(x1 JJ, 2) - log m(aak 251, 2)) (logm(z., Tyt, z) log m(xsk Eyt. 2)) = O.
(4)
Proof. Sufficient condition. Without loss of generality, let us consider three discrete variables, ie., {X,,X, Z}. Let ( (zn1....,TEM., and f be the support of variables X; and Xj. respectively.
Consider the case that the finite difference of the discrete score function of X, w.r.t. X, equals zero
When X; Fı1, X, = 2y1, and differences are considered w.r.t. Pike and B3,, we have
(log m(Za1, 2y1, 2) log ,
(18)
(1ogm(aan Eyt', z) log m(aae Fy, 2)) 0,
where ( 2) is the joint PMF simplified from mx, (111, F51, By iterating all possible differences w.r.t. X,, for all { M3J. we have
(log m(za, Tai, x) log m(Iww, Tzl, =)) -log (0ogm Tyt, =) log m(aw Fjl: 2)) 0.
(19)
Define the discrete score function of X; g(ra Tak, 7) log (x.1, log m(wa 7), where denotes other variables. Eq. 19 means ( Tik 7) doe not take the value of X, as an argument when the LHS of Eq. 19 equals zero. As result, Eq. 19 could be formulated as
log m( F,,, 2) = log m(ray, 2) + ( ,)).
(20)
Then by iterating all possible differences w.r.t. X for all l: in Iz. = 12....,M we have logm( 0(mzz,,211122 log m(au, F51, + g( o4k:
(21)
By summation, have
(N - 1) log mo TJ1, =
(log (2gm + + x(,,))
kET
(22)
Σ
(1g + Σ
g( Tak,
KE
kET.,
which implies that
M,
M, log (ana,,
Σ
log m (I + Σ
1=1
ke
(23)
Mi log 231
log (11,,
1
Σ kelz
M,
Because Dd.. log m m( 3yy1 covers all possible values of X,, this term does not depend the specific value of X,. Besides, the other term E O( 7) does not depend on Xy. It is could see that when the finite
worth noting that X₁ could be any value of X, w.o.l.g.. Therefore, difference of the discrete score function of X; w.r.t. to X, equal to zero (after some aggregation of samples), X; 11. X, Z.
14

---

Necessary condition. When X; TT X, Z, could decompose 11,, as m mx,iz(as =)mx, (2 z)mz(22. This implies that, for all & in (2...., Mj} and in (2....: Mj). we have
(log m(#n, 2y1 2) log TTI,
(Iog Z5t 2) log (z M3l. z))
(log (mxx|z(za (" 2)mxx 2)mz(3))
log (mx,
(2 22)z((2)
(log (mxxi
2 2)mxx
(zyz 2)mz(22)
llog (m,,j 2)mxx
2)mz(zz)
(24)
(llgmx,,zz(z; 2) log (z 2) mog)z(z))
(z, log mx m2 + log mz(z)))
((lggmx,/z(1))
log lxg
2) + log mzz(2)
(log xx (Z
2) + mx, 2) + log mz))))
=0. 0.
Therefore, when X; IL Xj Z. the finite difference of the discrete score function of X, w.r.t. to X3 equals zero.
The proof is complete.
A.3 PROOF OF COROLLARY
Corollary 2. Assume
X = (X1, Xa) is set of discrete variable.
ii The PMFs of X are strictly positive.
ii. The characterization matrix Qid is defined according to Eq. (5).
Then for any i + j. 5 implies X; X2 Xv Proof. According to Eq. (5), we have
2 Emx
Σ pld (2n 22
(25)
where (z Ty1, Ftt, 2) denotes the LHS of Eq. (4), i.c..
p (wa T3,
= (log (( Fy1, - log ( T51, 2)) (log m (211, log (Fikk Fyt. (2))))) 2))
(26)
Thus. if 52. 0, we must have
(logm(z,1, Ty1, 2) - log m ( T51, 2)) -log m( Fzt, 2) log m (2 Tztz 2))
(27)
for all & E [M.] and E [M3]. where M, and Mj denote the cardinalities of X; and Xj, respectively. Based on Theorem. 1, we have X; X, Z.
The proof is complete.
A.4 PROOF OF THEOREM 2
Theorem 2. Denote V as a set of mixed-type variables and X,,X, E V, where X₃ is discrete and X; is continuous. Let FiM.. be the support of variables Xt. For brevity, denote
15

---

vXX,, Xy} Z. Denote any value(s) of Z and 2; as any value of the continuous variable X,- Then, X; 11 Xj Z if and only if. for all [M,] with # 1, we have
i Oog (px, 2, (z 2 In m (2n)
Olo (px,,zix, (zz, 2ikk mx (Fst)) O.
(6)
dzj
dz,
Proof. Sufficient condition.
Without loss of generality, let us consider three variables, i.e..
(X,, (x,
2, E {ae1 J,M,
(28)
Ty IR
where X; = x; as the discrete variable and X, I. the continuous variable w.l.o.g. Note that we do not constraint the type of Z = z here but set Z as continuous for brevity.
Consider the case that the finite difference of the score function of X; w.r.t X; equals zero. Also, define as the p.d.f. and m as the p.m.f.. We first consider the difference between I2 and Twk.
i log (Ix, (Iz, ra m (2n)) log ZIx, (T )m (1a11)
(29)
dr,
By iterating all possible differences w.r.t. Iú, for all l: in L,, ,,,..., M). we have Ø log (Px, (z,, = an )mx (ra)) 0 log (Px,, ( = aaw m, (1rxe) 0, (30)
Ør,
Ov.
which is equivalent
log (Px,, (zy, aa m (xa))
alog (Ix,, (1z) mam)m, (2rx))
(31)
Ozj
Ory
Then by integrating on both sides w.r.t. Xj. we have
log (Px, 2I, (zz, 2 mx)mx, (ra)) log (xx, & mx)) (2me)) Ok.
(32)
where C2 is constant. We then apply summation as follows
(M: - 1) log (px, (Iz, | (a))x;
Σ
(log (Px,,21x, (D,, za)mx, (Fa)) + Ck)
(33)
KET.:
which implies that
log (px, 2|x, (Z,, (m))xx(xa
M. log (px;.2xx, (2,, Issk ), (Iik)) + Σ Cx
(34)
M
A=1
KELL
Because ΣM, k=1 log (Px,, 2|x, (Iz, Jik )mx, (xw)) covers all possible values of k, this term does depend on the specific value of X.. Besides, Cs does depend on Xj. Therefore, by iterating all possible differences of X,, we could see that when the finite difference of the score function of X, w.r.t. X; equals zero (after some aggregation of samples). X; 1L X, Z.
Mr
It is noteworthy that another "symmetric" case, where the derivative of the discrete score function of X; w.r.t. X, equals zero, follows
(log ((xx, (1z, va m (2a1) - log
(Zj5 Fak )mx (Ixx
(35)
dz,
which is equivalent to
@ log (px, 2Ix,
ix (æj, 2 Ial )mn, (xra) dr,
a log (p.x, (Iz, z mmx)m (wra)) = 0. (36)
Ox.
16

---

Thus, only need consider Eq. 36, which is the case that the finite difference of the discrete score function of X, w.r.t X, equals zero.
Necessary condition. When X, TT X5 Z, could decompose 2x,. (2,,, 2 Ia )mxx (2x1) as mx,1z ( 1))xx,12(x) (z). This implies that, for all & in {2, .2,.... Mi}. we have
à log (px,.2(x, (z), 2 an mmx, (εa))
a log (px,, (1x,, (1,, 2 ag dx.
(2xx))
dx, Olog (mx 2)px, (00 z)pz(z))
dxy
Olog (Tx, =))xx11( 1 [=)p((z))
0x; a (log (oggxx 2) + log px (zy 2) + log p2
(37)
dr,
a (log (logmX,|2(24
22) log PX (x, 2) + log log P2()))
dx, i log xx, 2 2)
a log Pxg px, 2(2 2)
Ozj
-0.
Therefore, when X; 11. X, Z, the finite difference of the score function of X, w.r.t. to X; equal to zero.
The proof is complete.
A.5 PROOF OF COROLLARY
Corollary 3. Assume
X (X1,..., Xa) is set of variables containing both continuous and discrete variables.
ii For continuous variables. the PDFs are strietly positive and smooth.
iii. For discrete variables, the PMFs are strictly positive.
iv. The characterization matrix Qimll is defined according to Eq. (7).
Then for any i + j. S2.77 Proof. According Eq. (7), have
implies X; 11 X2 Xv
T
5 (x)
ifX, EX EX
g/mll
Exx
Ex.1 ff (x 2sk B51,
EXX,
(38)
Exx
Σx fmmm (2x, Ty Fzkk 2
if E X,, X
Exx
Ee fl fmmm (zz,, Fel. 2.k 2)
if E X,, E X.,.
where X, and X are the sets of continuous and discrete variables, respectively. We have already proved the first two cases (i.e., {X, E Xx, X, X.} and (X, X,, X, Xa)) in the proofs of Cor. and Cor. 2, respectively. So here we will focus on the other two cases, We start from the third case, where (X; X., X3 E Xa). We have
Ölog (Px, (r,, 2 1111) )m (x,1))
fllm TTR,,
Or: log (px, (r, 1x (zzx))
(39)
Or,
17

---

Thus, if 1 0 for (Xi E X., X, Xa). we must have
log (xx, (I,, 2 (z)))m (Iz1))
dz,
(40)
Ölg (px, 2|, (I 2 2zx)m (I5k)) 0,
dz,
for all & E [M,], where M, denotes the cardinality of Xj. Thus, according Theorem have X; IL X, Z if s2.77) O for {X; E Xx, X, E Xa).
The similar derivation applies for the last case, where {X; E Xx, E X
A.6 PROOF OF COROLLARY
We first introduce the following lemmas and their proofs for completeness.
A.6.1 PROOF OF LEMMA
Lemma 1. [directly from Thm. I in (Hyvärinen & Dayan, 2005)] Assume
x= (X1,..., Xa) is set of continuous variables.
it. The data PDF px (x) is differentiable. The model PDF (xx0) is twice-difeerentiabl. Both of them are strictly positive.
ii The expectations Ex {Il log p(x; 0)] and Ex { [x)ggx((x]]+ are finite for any 0, and (x(x) log p(x; 0) goes to zero for any when ||x|| + oc.
Then Eq. (8) is equivalent to
1 IV log p(gp(x;))11== He, (logp(x dx pa(Slle).
(+) px (x(x) Σ
(41)
XER"
Proof. Based on Eq. (8), we have
(0(
2 V log:(x;;0)) 0) Vx lo (x) ?dx + (X
1
(42)
where px(+) denotes sparsity penalty function and À the penalty parameter. This is equivalent
(0) - f (x(x) (I| log 1)
V (x)]
(43)
2 vVx (xg)x(x)) (V logp(x fx) (2
We first consider the integral for the following part
f px(xx) (Vx (oxlogxx(x)) log 1og dx,
(44)
by which we could obtain
-| (x((x logpx (Va, log p(x: 0)) dx
= --E / (V) (V., logp(x;)))) dx
= Σ/ // V Vx.Px(x) (Va, log 0)) dai d(xi...., Id)
(45)
Σ
lim
[xx (a, F2 Ia) Vz, log,(a, 22, 0)
a-000
-PX (b, x2 I2..... xxn Va, log ,2, 8)
-f
02 log
Px (x)do
d(sg...., s.))
dr,²
18

---

where Eq. (+) is because if we assume f and g both differential, have
0f(x)g(x) s(x) Ox.
0g(x) da
0f(x)
g(x)
(46)
Zz
For # 1, the cases follow similarly. Because assume px (x) log p(:; 0) goes to zero for any when x|| - oc, the limit is zero. Thus, we have proven that
Σ px px( Ve logpx(x) Va, log 0)) dx) dx
82 log px(x))xx
(47)
Or,²
i
By injecting it into Eq. (43), obtain
0c(0) / px(x) 1/2 Vx log [)12
VV (x))
(48)
(Hx tHx + tr
(logp(x dx + (2(())
Because V log px (x) does not depend on 0, could ignore it. Then we have
0c(0)
Σ
v., p(: 0)12 Ha, p(x)((x)))) dx (X((
(49)
2
Thus, the proof is complete.
A.6.2 PROOF OF LEMMA
Lemma 2. [directly from (Lyu, 2012)] Assume
X (X1,-.. X is set of discrete variables.
i. The data PMF mx (x) and the model PMF mlx;;) are stricily positive.
Then Eq. (12) is equivalent
- 2M;
M.(m(x;; 01) m(x; 0)
(Mi(m(x:0)) 0))
Oa(0)= = Σ mix (x Σ
+ (221
(50)
m(x: 0)
Proof. Based on Eq. (12), we have
M(mm(x;))
M(mx(x))
Oa(0) = Σ mx())
+ (2
(51)
m(x;0)
mx
x
which implies
Mi(m(x;0))
Mi(mx(xs))
O2(0) Σ (x Σ
+
m(x;0) 0)
mx(xx)
(52)
mx(x)) (x) Σ
(Mi(m(x:))) 0))
2M,
(M)(m(x:0))
)
+ P2((1)))
m(x;0) 0)
m(x;0) 0)
2 does not take as an argument.
where Eq. (+) is due to the fact that
mx(x))
The proof is complete.
Then the corollary follows from these lemmas, which is included as follows.
Corollary 4. Assume
The data density Tx(.) is equal T[; 0*) for some 0*.
19

---

it. The data density xx(+) and model density T(=;0) are strictly positive. πx(.) and <(:; is
differentiable and wiice-diffrrntiable, respectively, w.r.t. continuous variables. For some 8", xx)()) =(=;0) and other parameter value gives a density that is equal to π )*) almost everywhere.
ii. The expectations Eax log (x; 0)]1"] and Eax [|log x (x)]l² are finite for any 0, and x (x) log πT (x; 0) goes to zero for any 0 when ||x] + 0c.
Then Oz, (0) = implies 0 = 0"
Proof. The O (0) is defined as follows
(m) = -Enx Σ (x(x:
(53)
where
1 xa log x 0)12 Ha, (log (x:
X; X.
8, (x 0)
(54)
M.(m(x)))) m=(:9)
Mi
(m((xx))
X; Xt,
mxx;0)
where the probability function is strictly positive. According Lemma I and Lemma 2, both cases of s;(::) in O² (f) are equivalent to _E,
g(m(=11)
g(z(-)) where g denotes the gradient
x()0)
x(
operator for continuous variables or the marginalization operator for discrete variables. If O (0) 0. <<;;; 8) must equal zero for any i. Because of Brook's Lemma (Brook, 1964), which is also included in Lyu (2012) as Lemma 3, the marginalization operator M is complete (Defn. 1). Thus, for the discrete variables, we could replace the gradient in the continuous score function with the marginalization operator while preserving local consistency as that for the continuous variables, which is shown by Theorem in Hyvärinen & Dayan (2005).
B EXPERIMENTS
B.1 GENERATING PROCESS FOR MIXED-TYPE DATA
For the mixed-type case, simulate data with the process described in Andrews al. (2018), of which the details are included here for completeness. After generating a random decomposable discrete) each variable with equal probability.
DAG, we first assign a data type (continuous For variables without parents in the ground- -ruth graph, we sample their values from Gaussian and Multinomial distributions, respectively. Then for each continuous variable, discretized version by applying equal frequency binning. The number of bins is uniformly chosen between and including and The cardinality of each discrete variable is uniformly chosen between and including 2 and 4. The randomly generated decomposable DAGs are moralized to obtain the ground-truth Markov network structures.
create temporary
Next, for variables with parents in the ground-truth graph, we sample the values of them as follows. For continuous variables, we first adopt partitioning according to its discrete variables. Then the values of these continuous variables generated by randomly parameterizing the coefficients of a regression for each partition. For discrete variables, we generate the values them by randomly parameterizing Multinomial distributions of the variables of the target variable and its discrete parents (temporary or not). After the simulation, all temporary discretized variables are removed.
B.2 INFLUENCE OF THE SAMPLE SIZE
In this section, we report additional experimental results with a larger sample size. We conduct experiments for all settings (continuous, discrete, and mixed-type) with different numbers of variables (d E [4. 6.... 20}) and 10000 samples. The results are summarized in Fig. 4, Fig. 5, and Fig. One can observe that both KCI and GS fail in all settings, indicating that they cannot scale well with large sample sizes. It is because the complexities of KCI and GS grow cubically in the number of samples, which is one of the motivations for the development of method. Besides, SING cannot
20

---

scale with more than 6 variables because of OOM. At the time, method works well across all datasets without any scalability issues. Together with the better performance illustrated in Sec. (note that one even go beyond 5000 variables, e.g., it takes 7725 seconds for 10,000 variables in our setting), we believe the potential of our method is not only theoretically exciting but also empirically clear in both consistency and scalability.
Ours
60
SING
Hamming distance
GLASSO
40
30
20
10
4
8
10
12 Dim
14
18
20
Figure 4: Hamming distances for continuous data, 10000.
30
Ours
GLASSO
Hamming distance
25
20
10
10
14
18
Dim
Figure 5: Hamming distances for discrete data, n 10000.
40
Ours
GLASSO
Hamming distance
20
10
10
14
16
18
20
Dim
Figure Hamming distances for mixed-type data, n 10000.
21

---

SCAD
h
Hamming distance
Adaptive
MCP
6
8
10
12
14
16
18
20
Figure 7: Hamming distances w.r.t. different sparsity penalty functions and numbers of variables.
B.3 INFLUENCE OF DIFFERENT PENALTY FUNCTIONS
To explore the effect of different regularization functions, we compare the results of our method with different sparsity penalties, which are shown in Fig. 7. The experiments are conducted Butterfly distributions with the number of continuous variables ranging from to 20 and sample size of 1000. One could observe that SCAD and MCP outperform other penalties, while SCAD performs slightly better than MCP in general. Adaptive & (Zou, 2006) also illustrates its advantage compared to the original penalty. This suggests the importance of appropriate penalty functions.
C DISCUSSION
C.I TOWARDS NONPARAMETRIS CAUSAL DISCOVERY
In this section, we briefly discuss the implication of our proposed Markov network estimation method in causal discovery, of which the goal to learn graphical models with causal interpretations.
The major classes of approaches for causal discovery are constraint- baseed approaches that utilize conditional independence tests and score-based approaches that optimize specific score function. Among them, PC (Spirtes& & Glymour, 1991) with kernel-based conditional independence test (Zhang al., 2012) and GES (Chickering, 2002) with generalized score (Huang et al., 2018) are able to handle nonparametric cases with assumptions such as causal sufficiency. Both of these approaches rely on kernel methods whose computational complexity is cubic w.r.t. the number of samples. Therefore, the running time could be long if the sample size is large. Furthermore, when the number of variables is large, the search procedure may involve computing the dernel-based conditional independence test score function many times, which therefore may also increase the running time.
As shown by Loh & Bühlmann (2014); Ng et al. (2021) in the linear Gaussian case, the Markov network (i.e., the support of the inverse covariance matrix of the distribution) is guaranteed be the super-structure the ground truth directed acyelic graph (DAG) under a specific type faithfulness assumption. That is, the super-structure contains all edges of the true DAG. Using this idea, they showed that the Markov network may be used to restrict the search space of score-based approaches for causal discovery, which improves the scalability. Their works focus only on the linear case and adopt classical methods like graphical Lasso (Friedman et al., 2008) to estimate the Markov network. In this work, the nonparametrie Markov network estimated by our proposed procedure could potentially be used discovery methods, i.e., (aaenel-based) PC and GES. Similar to (Loh Bühlmann, 2014; Ng et al., 2021), this may help reduce the running time and improve the scalability of these methods.
super-structure to restrict the search space for nonparametric causal
22


Reviews:
[{"review_id": "wNeNT1I-Mw", "reviewer": "Reviewer_RUet", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.", "strength_and_weaknesses": "# Strengths\n\n- 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.\n- There is good mathematical rigour throughout.\n\n\n# Weaknesses\n\n- 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. \n- 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.\n- The English is lacking in places, prepositions not there and general sentence construction is off.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "K_8dtKR9hE", "reviewer": "Reviewer_XHnf", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.\n\nIn the rebuttal the authors have satisfactorily addressed the totality of the points I raised, for this reason I recommend that the paper be accepted.", "strength_and_weaknesses": "\nStrengths\n1. Sections 1 and 2 are well written and clear. Same for section 3 except for some minor problems (see below).\n2. 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)\n3. Potentially much faster method of discovering conditional independence relations (but must be verified with further numerical experiments) compared to what exists in the literature.\n\nPoints of improvement\n1. In page 3 line 6. It is unclear what it means that $\\Omega$ is differentiable (i.e. differentiable with respect to what?)\n2. In equation 9 should the integral be over $\\mathbb R^d$ ?\n3. 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)$? )\n4. Typo regualrized  pag 9.\n5. 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.\n6. 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.\n7. 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]) \n8. Several details are missing in the numerical experiments. This information is critical to understand how the results were obtained and to appreciate their significance:\n\n    (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?\n\n    (b) How is the loss optimized? (e.g. gradient based methods,…) \n\n    (c) Is the optimization guaranteed to reach the global minimum? Is the problem convex?\n\n    (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.\n\n    (e) When saying «we also conduct experiments on large graphs» all the details about these experiments must be provided.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JFgczuixJ3X", "reviewer": "Reviewer_nCND", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.  ", "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. \n\n==== After rebuttal ===\nIt 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. \n", "strength_and_weaknesses": "Strength:\n1. 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.\n2. 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.\n\nWeakness:\n1. The experiment is limited. Author has only explored ground truth structure that are r iid pairs of random variables. \n* The evaluation would be stronger if author could explore different MN structures, e.g. different tree structures. \n*  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. \n\n[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.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5nv-F0Hyc79", "reviewer": "Reviewer_ircN", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a scalable estimation method for non-parametric Markov network structures, using regularized score matching. \nThey 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. \nThey also introduce appropriate penalties on the characterization matrix, to promote constantly sparse entries for\nstable estimation. ", "summary_of_the_review": "This paper presents a scalable estimation method for non-parametric Markov network structures.\nIt addresses the limitations of previous related methods in handling all data types (i.e., continuous, discrete, and mixed-type).\nTo me, it should be accepted based on its high quality and novelty.", "strength_and_weaknesses": "Strength ：\nIt is the first attempt to estimate Markov networks for all data types (i.e.,continuous, discrete, and mixed-type)\nThe esitmation method is scalable ( up to 5000 nodes within one hour on CPUs )\n\nWeaknesses ：\n- There's no experiments on real-world examples except only some comparisons are conducted on synthetic examples.\n\nQuestions:\n-  why do not consider comparing the method of [1] in your final experiments, for mixed-type data ?\n\n[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.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster