[1910.10860] Structure Learning of Gaussian Markov Random Fields with False Discovery Rate Control
Although some extensions are possible [59], it would be desirable to consider a general framework, for example, based on Bayesian inference considering the posterior distribution derived from the loss and the regularizer [75,76], which enables us to evaluate the uncertainty of edge discovery and to find values from data

Abstract: In this paper, we propose a new estimation procedure for discovering the
structure of Gaussian Markov random fields (MRFs) with false discovery rate
(FDR) control, making use of the sorted l1-norm (SL1) regularization. A
Gaussian MRF is an acyclic graph representing a multivariate Gaussian
distribution, where nodes are random variables and edges represent the
conditional dependence between the connected nodes. Since it is possible to
learn the edge structure of Gaussian MRFs directly from data, Gaussian MRFs
provide an excellent way to understand complex data by revealing the dependence
structure among many inputs features, such as genes, sensors, users, documents,
etc. In learning the graphical structure of Gaussian MRFs, it is desired to
discover the actual edges of the underlying but unknown probabilistic graphical
model-it becomes more complicated when the number of random variables
(features) p increases, compared to the number of data points n. In particular,
when p >> n, it is statistically unavoidable for any estimation procedure to
include false edges. Therefore, there have been many trials to reduce the false
detection of edges, in particular, using different types of regularization on
the learning parameters. Our method makes use of the SL1 regularization,
introduced recently for model selection in linear regression. We focus on the
benefit of SL1 regularization that it can be used to control the FDR of
detecting important random variables. Adapting SL1 for probabilistic graphical
models, we show that SL1 can be used for the structure learning of Gaussian
MRFs using our suggested procedure nsSLOPE (neighborhood selection Sorted L-One
Penalized Estimation), controlling the FDR of detecting edges.

beta_hat == arg min_(beta in mathds(R)**p) * frac12 * norm_2(b - A beta)**2 + J__lambda(beta)

Figure 1. Quality of estimation. Top: empirical false discovery rate (FDR) levels (averaged over 25 repetitions) and the nominal level of q = 0.05 (solid black horizontal line). Bottom: mean square error of diagonal and off-diagonal entries of the precision matrix. p = 500 was fixed for both panels and n = 100, 200, 300 and 400 were tried. (“nsSLOPE”: nsSLOPE without symmetrization, “+symm”: with symmetrization and gLASSO.) (Structure Discovery)Figure 2. Examples of structure discovery. Top: a covariance matrix with block diagonal structure. Bottom: a hub structure. True covariance matrix is shown on the left and gLASSO and nsSLOPE estimates (only the nonzero patterns) of the precision matrix are shown in the middle and in the right panels, respectively. (Structure Discovery)›