Selection of the Regularization Parameter in Graphical Models Using Network Characteristics

Gaussian graphical models represent the underlying graph structure of conditional dependence between random variables, which can be determined using their partial correlation or precision matrix. In a high-dimensional setting, the precision matrix is estimated using penalized likelihood by adding a penalization term, which controls the amount of sparsity in the precision matrix and totally characterizes the complexity and structure of the graph. The most commonly used penalization term is the L1 norm of the precision matrix scaled by the regularization parameter, which determines the trade-off between sparsity of the graph and fit to the data. In this article, we propose several procedures to select the regularization parameter in the estimation of graphical models that focus on recovering reliably the appropriate network structure of the graph. We conduct an extensive simulation study to show that the proposed methods produce useful results for different network topologies. The approaches are also applied in a high-dimensional case study of gene expression data with the aim to discover the genes relevant to colon cancer. Using these data, we find graph structures, which are verified to display significant biological gene associations. Supplementary material is available online.     

High-Dimensional Mixed Graphical Models

While graphical models for continuous data (Gaussian graphical models) and discrete data (Ising models) have been extensively studied, there is little work on graphical models for datasets with both continuous and discrete variables (mixed data), which are common in many scientific applications. We propose a novel graphical model for mixed data, which is simple enough to be suitable for high-dimensional data, yet flexible enough to represent all possible graph structures. We develop a computationally efficient regression-based algorithm for fitting the model by focusing on the conditional log-likelihood of each variable given the rest. The parameters have a natural group structure, and sparsity in the fitted graph is attained by incorporating a group lasso penalty, approximated by a weighted lasso penalty for computational efficiency. We demonstrate the effectiveness of our method through an extensive simulation study and apply it to a music annotation dataset (CAL500), obtaining a sparse and interpretable graphical model relating the continuous features of the audio signal to binary variables such as genre, emotions, and usage associated with particular songs. While we focus on binary discrete variables for the main presentation, we also show that the proposed methodology can be easily extended to general discrete variables.     

��˹ͼģ�͵Ļ����������Ľ���IPSP�㷨

The IPSP algorithm is an efficient algorithm for computing maximum likelihood estimation of Gaussian graphical models. It first divides clique marginals of graphical models into several groups, and then it adjusts clique marginals in each group locally. This paper uses the IIPS algorithm on junction tree to replace local adjustment on each group in the IPSP algorithm and propose a resulting algorithm called IPSP-JT to reduce the complexity of the IPSP algorithm. Moreover, we give a graph with minimum edges used by IIPS to adjust locally, and we prove its existence and uniqueness and construct a local junction tree. Numerical experiments show that the IPSP-JT algorithm runs faster than the IPSP algorithm for large Gaussian graphical models.     

Graphical Frobenius representations

A Frobenius group is a transitive permutation group that is not regular and such that only the identity fixes more than one point. A graphical Frobenius representation (GFR) of a Frobenius group G is a graph whose automorphism group, as a group of permutations of the vertex set, is isomorphic to G. The problem of classifying which Frobenius groups admit a GFR is a natural extension of the classification of groups that have a graphical regular representation (GRR), which occupied many authors from 1958 through 1982. In this paper, we review for graph theorists some standard and deep results about finite Frobenius groups, determine classes of finite Frobenius groups and individual groups that do and do not admit GFRs, and classify those Frobenius groups of order at most 300 having a GFR. Because a Frobenius group, as opposed to a regular permutation group, has a highly restricted structure, the GFR problem emerges as algebraically more complex than the GRR problem. This paper concludes with some further questions and a strong conjecture.     

Graphical designs and gale duality

Mathematical Programming - A graphical design is a subset of graph vertices such that the weighted averages of certain graph eigenvectors over the design agree with their global averages. We use...     

Decomposition of Covariate-Dependent Graphical Models with Categorical Data

Graphical models are wildly used to describe conditional dependence relationships among interacting random variables. Among statistical inference problems of a graphical model, one particular interest is utilizing its interaction structure to reduce model complexity. As an important approach to utilizing structural information, decomposition allows a statistical inference problem to be divided into some sub-problems with lower complexities. In this paper, to investigate decomposition of covariate-dependent graphical models, we propose some useful definitions of decomposition of covariate-dependent graphical models with categorical data in the form of contingency tables. Based on such a decomposition, a covariate-dependent graphical model can be split into some sub-models, and the maximum likelihood estimation of this model can be factorized into the maximum likelihood estimations of the sub-models. Moreover, some sufficient and necessary conditions of the proposed definitions of decomposition are studied.     

Graphical Models for Ordinal Data

This article considers a graphical model for ordinal variables, where it is assumed that the data are generated by discretizing the marginal distributions of a latent multivariate Gaussian distribution. The relationships between these ordinal variables are then described by the underlying Gaussian graphical model and can be inferred by estimating the corresponding concentration matrix. Direct estimation of the model is computationally expensive, but an approximate EM-like algorithm is developed to provide an accurate estimate of the parameters at a fraction of the computational cost. Numerical evidence based on simulation studies shows the strong performance of the algorithm, which is also illustrated on datasets on movie ratings and an educational survey.     

Menus of kuratowski subgraphs

Motivated by heuristic embedding algorithms, this paper is concerned with the organization of potentially large lists of Kuratowski subgraphs of an arbitrary nonpianar graph. A graphical structure called a "nearly Hamiltonian" graph is defined. It is shown that lists of Kuralowski subgraphs can be lexicographically organized in such structures. It is shown that any nonpianar graph contains such structures and at least one such structure with a nonempty list of Kuratowski subgraphs can be located in linear time in ihe edges of the graph.     

Learning the Structure of Mixed Graphical Models

We consider the problem of learning the structure of a pairwise graphical model over continuous and discrete variables. We present a new pairwise model for graphical models with both continuous and discrete variables that is amenable to structure learning. In previous work, authors have considered structure learning of Gaussian graphical models and structure learning of discrete models. Our approach is a natural generalization of these two lines of work to the mixed case. The penalization scheme involves a novel symmetric use of the group-lasso norm and follows naturally from a particular parameterization of the model. Supplementary materials for this article are available online.     

Bayesian Ising Graphical Model for Variable Selection

In this article, we propose a new Bayesian variable selection (BVS) approach via the graphical model and the Ising model, which we refer to as the “Bayesian Ising graphical model” (BIGM). The BIGM is developed by showing that the BVS problem based on the linear regression model can be considered as a complete graph and described by an Ising model with random interactions. There are several advantages of our BIGM: it is easy to (i) employ the single-site updating and cluster updating algorithm, both of which are suitable for problems with small sample sizes and a larger number of variables, (ii) extend this approach to nonparametric regression models, and (iii) incorporate graphical prior information. In our BIGM, the interactions are determined by the linear model coefficients, so we systematically study the performance of different scale normal mixture priors for the model coefficients by adopting the global-local shrinkage strategy. Our results indicate that the best prior for the model coefficients in terms of variable selection should place substantial weight on small, nonzero shrinkage. The methods are illustrated with simulated and real data. Supplementary materials for this article are available online.     

Probabilistic compositional models: Solution of an equivalence problem

Probabilistic compositional models, similarly to graphical Markov models, are able to represent multidimensional probability distributions using factorization and closely related concept of conditional independence. Compositional models represent an algebraic alternative to the graphical models. The system of related conditional independencies is not encoded explicitly (e.g. using a graph) but it is hidden in a model structure itself. This paper provides answers to the question how to recognize whether two different compositional model structures are equivalent – i.e., whether they induce the same system of conditional independencies. Above that, it provides an easy way to convert one structure into an equivalent one in terms of some elementary operations on structures, closely related ability to generate all structures equivalent with a given one, and a unique representative of a class of equivalent structures.     

Positive Semidefinite Rank-Based Correlation Matrix Estimation With Application to Semiparametric Graph Estimation

Many statistical methods gain robustness and flexibility by sacrificing convenient computational structures. In this article, we illustrate this fundamental tradeoff by studying a semiparametric graph estimation problem in high dimensions. We explain how novel computational techniques help to solve this type of problem. In particular, we propose a nonparanormal neighborhood pursuit algorithm to estimate high-dimensional semiparametric graphical models with theoretical guarantees. Moreover, we provide an alternative view to analyze the tradeoff between computational efficiency and statistical error under a smoothing optimization framework. Though this article focuses on the problem of graph estimation, the proposed methodology is widely applicable to other problems with similar structures. We also report thorough experimental results on text, stock, and genomic datasets.     

Graphical regular representations of free products of groups

If X is a Cayley graph of a group G possessing a normal subgroup N, then there is a quotient graph of X which is a Cayley graph of $\text{G}\text{N}$. With the aid of this result, it is shown that the free product of at least two and at most countably many groups, each of which is at most countably generated, admits a graphical regular representation.     

Positivity for Gaussian graphical models

Gaussian graphical models are parametric statistical models for jointly normal random variables whose dependence structure is determined by a graph. In previous work, we introduced trek separation, which gives a necessary and sufficient condition in terms of the graph for when a subdeterminant is zero for all covariance matrices that belong to the Gaussian graphical model. Here we extend this result to give explicit cancellation-free formulas for the expansions of non-zero subdeterminants.     

Graphical modelling of multivariate time series

We introduce graphical time series models for the analysis of dynamic relationships among variables in multivariate time series. The modelling approach is based on the notion of strong Granger causality and can be applied to time series with non-linear dependences. The models are derived from ordinary time series models by imposing constraints that are encoded by mixed graphs. In these graphs each component series is represented by a single vertex and directed edges indicate possible Granger-causal relationships between variables while undirected edges are used to map the contemporaneous dependence structure. We introduce various notions of Granger-causal Markov properties and discuss the relationships among them and to other Markov properties that can be applied in this context. Examples for graphical time series models include nonlinear autoregressive models and multivariate ARCH models.     

A Graphical Approach to Diagnosing the Validity of the Conditional Independence Assumptions of a Bayesian Network Given Data

Bayesian networks (BNs) have attained widespread use in data analysis and decision making. Well-studied topics include efficient inference, evidence propagation, parameter learning from data for complete and incomplete data scenarios, expert elicitation for calibrating BN probabilities, and structure learning. It is common for the researcher to assume the structure of the BN or to glean the structure from expert elicitation or domain knowledge. In this scenario, the model may be calibrated through learning the parameters from relevant data. There is a lack of work on model diagnostics for fitted BNs; this is the contribution of this article. We key on the definition of (conditional) independence to develop a graphical diagnostic that indicates whether the conditional independence assumptions imposed, when one assumes the structure of the BN, are supported by the data. We develop the approach theoretically and describe a Monte Carlo method to generate uncertainty measures for the consistency of the data with conditional independence assumptions under the model structure. We describe how this theoretical information and the data are presented in a graphical diagnostic tool. We demonstrate the approach through data simulated from BNs under different conditional independence assumptions. We also apply the diagnostic to a real-world dataset. The results presented in this article show that this approach is most feasible for smaller BNs—this is not peculiar to the proposed diagnostic graphic, but rather is related to the general difficulty of combining large BNs with data in any manner (such as through parameter estimation). It is the authors’ hope that this article helps highlight the need for more research into BN model diagnostics. This article has supplementary materials online.     

Graphical Representations of Speed: Obstacles Preservice K‐8 Teachers Experience

This study examines the difficulties college students experience when creating and interpreting graphs in which speed is one of the variables. Nineteen students, all preservice elementary or middle school teachers, completed an upper‐level course exploring algebraic concepts. Although all of these preservice teachers had previously completed several mathematics courses, including calculus, they demonstrated widespread misconceptions about the variable speed. This study identifies four cognitive obstacles held by the students, provides excerpts of their graphical constructions and verbal interpretations, and discusses potential causes for the confusion. In particular, misconceptions arose when students interpreted the behavior and nature of speed within a graphical context, as well as in situations where they were required to construct a graph involving speed as a variable. The study concludes by offering implications for the teaching and learning of speed and its interpretation within a graphical setting.     

Modeling Relationships among Multiple Graphical Structures

Many researchers have investigated the social and cognitive processes underlying organizational behavior, with particular interest in understanding the interaction between the social and cognitive dimensions. Because of the widespread use of graphs as models of social and cognitive structures, these studies frequently encounter the problem of analyzing collections of graphical structures. Such analyses have used a variety of approaches to address specific aspects of such structures. However, no single unified approach has emerged that supports the several different types of analyses required. The purpose of this paper is to define such an approach, based on a mathematical model for capturing the relationships among multiple graphs, and to demonstrate its application to the investigation of social and cognitive structures in organizations.     

An efficient algorithm for finding the largest chain graph according to a given chain graph

Chain graph (CG) is a general model of graphical Markov models. Some different chain graphs may describe the same conditional independence structure, then we say that these CGs are Markov equivalent. In 1990 Frydenberg showed that every class of Markov equivalent CGs has a CG which is called the largest chain graph with the greatest number of lines. This paper presents an efficient algorithm for finding the largest chain graph of the corresponding Markov equivalent class of a given CG. The computational complexity of the algorithm is O(n3). It is more efficient than the complexity O(n!) of the present algorithms. Also a more intuitive graphical characterization of the largest chain graph is provided based on the algorithm in this paper.     

Efficient Distributed Estimation of High-dimensional Sparse Precision Matrix for Transelliptical Graphical Models

In this paper,distributed estimation of high-dimensional sparse precision matrix is proposed based on the debiased D-trace loss penalized lasso and the hard threshold method when samples are distributed into different machines for transelliptical graphical models.At a certain level of sparseness,this method not only achieves the correct selection of non-zero elements of sparse precision matrix,but the error rate can be comparable to the estimator in a non-distributed setting.The numerical results further prove that the proposed distributed method is more effective than the usual average method.