On expressiveness of the chain graph interpretations

In this article we study the expressiveness of the different chain graph interpretations. Chain graphs is a class of probabilistic graphical models that can contain two types of edges, representing different types of relationships between the variables in question. Chain graphs is also a superclass of directed acyclic graphs, i.e. Bayesian networks, and can thereby represent systems more accurately than this less expressive class of models. Today there do however exist several different ways of interpreting chain graphs and what conditional independences they encode, giving rise to different so-called chain graph interpretations. Previous research has approximated the number of representable independence models for the Lauritzen–Wermuth–Frydenberg and the multivariate regression chain graph interpretations using an MCMC based approach. In this article we use a similar approach to approximate the number of models representable by the latest chain graph interpretation in research, the Andersson–Madigan–Perlman interpretation. Moreover we summarize and compare the different chain graph interpretations with each other. Our results confirm previous results that directed acyclic graphs only can represent a small fraction of the models representable by chain graphs, even for a low number of nodes. The results also show that the Andersson–Madigan–Perlman and multivariate regression interpretations can represent about the same amount of models and twice the amount of models compared to the Lauritzen–Wermuth–Frydenberg interpretation. However, at the same time almost all models representable by the latter interpretation can only be represented by that interpretation while the former two have a large intersection in terms of representable models.     

Pair-Copula Bayesian Networks

Pair-copula Bayesian networks (PCBNs) are a novel class of multivariate statistical models, which combine the distributional flexibility of pair-copula constructions (PCCs) with the parsimony of conditional independence models associated with directed acyclic graphs (DAGs). We are first to provide generic algorithms for random sampling and likelihood inference in arbitrary PCBNs as well as for selecting orderings of the parents of the vertices in the underlying graphs. Model selection of the DAG is facilitated using a version of the well-known PC algorithm that is based on a novel test for conditional independence of random variables tailored to the PCC framework. A simulation study shows the PC algorithm’s high aptitude for structure estimation in non-Gaussian PCBNs. The proposed methods are finally applied to modeling financial return data. Supplementary materials for this article are available online.     

Marginal AMP chain graphs

We present a new family of models that is based on graphs that may have undirected, directed and bidirected edges. We name these new models marginal AMP (MAMP) chain graphs because each of them is Markov equivalent to some AMP chain graph under marginalization of some of its nodes. However, MAMP chain graphs do not only subsume AMP chain graphs but also multivariate regression chain graphs. We describe global and pairwise Markov properties for MAMP chain graphs and prove their equivalence for compositional graphoids. We also characterize when two MAMP chain graphs are Markov equivalent.For Gaussian probability distributions, we also show that every MAMP chain graph is Markov equivalent to some directed and acyclic graph with deterministic nodes under marginalization and conditioning on some of its nodes. This is important because it implies that the independence model represented by a MAMP chain graph can be accounted for by some data generating process that is partially observed and has selection bias. Finally, we modify MAMP chain graphs so that they are closed under marginalization for Gaussian probability distributions. This is a desirable feature because it guarantees parsimonious models under marginalization.     

Decomposition of two classes of structural models

The conditional independence structure of a common probability measure is a structural model. In this paper, we solve an open problem posed by Studeny [Probabilistic Conditional Independence Structures, Theme 9, p. 206]. A new approach is proposed to decompose a directed acyclic graph and its optimal properties are studied. We interpret this approach from the perspective of the decomposition of the corresponding conditional independence model and provide an algorithm for identifying the maximal prime subgraphs in a directed acyclic graph.     

Partial inversion for linear systems and partial closure of independence graphs

We introduce and study a calculus for real-valued square matrices, called partial inversion, and an associated calculus for binary square matrices. The first, applied to systems of recursive linear equations, generates new sets of parameters for different types of statistical joint response models. The corresponding generating graphs are directed and acyclic. The second calculus, applied to matrix representations of independence graphs, gives chain graphs induced by such a generating graph. Chain graphs are more complex independence graphs associated with recursive joint response models. Missing edges in independence graphs coincide with structurally zero parameters in linear systems. A wide range of consequences of an assumed independence structure can be derived by partial closure, but computationally efficient algorithms still need to be developed for applications to very large graphs. AMS subject classification (2000) 00A71, 15A09, 15A23, 05C99, 62H99, 62J05     

Identification of graphical models for nonignorable nonresponse of binary outcomes in longitudinal studies

In this paper, we use directed acyclic graphs (DAGs) with temporal structure to describe models of nonignorable nonresponse mechanisms for binary outcomes in longitudinal studies, and we discuss identification of these models under an assumption that the sequence of variables has the first-order Markov dependence, that is, the future variables are independent of the past variables conditional on the present variables. We give a stepwise approach for checking identifiability of DAG models. For an unidentifiable model, we propose adding completely observed variables such that this model becomes identifiable.     

A logical approach to context-specific independence

Directed acyclic graphs (DAGs) constitute a qualitative representation for conditional independence (CI) properties of a probability distribution. It is known that every CI statement implied by the topology of a DAG is witnessed over it under a graph-theoretic criterion of d-separation. Alternatively, all such implied CI statements are derivable from the local independencies encoded by a DAG using the so-called semi-graphoid axioms. We consider Labeled Directed Acyclic Graphs (LDAGs) modeling graphically scenarios exhibiting context-specific independence (CSI). Such CSI statements are modeled by labeled edges, where labels encode contexts in which the edge vanishes. We study the problem of identifying all independence statements implied by the structure and the labels of an LDAG. We show that this problem is coNP-hard for LDAGs and formulate a sound extension of the semi-graphoid axioms for the derivation of such implied independencies. Finally we connect our study to certain qualitative versions of independence ubiquitous in database theory and teams semantics.     

Lattices generated by Chip Firing Game models: Criteria and recognition algorithms

It is well-known that the class of lattices generated by Chip Firing Games (CFGs) is strictly included in the class of upper locally distributive lattices (ULD). However a necessary and sufficient criterion for this class is still an open question. In this paper we settle this problem by giving such a criterion. This criterion provides a polynomial-time algorithm for constructing a CFG which generates a given lattice if such a CFG exists. Going further we solve the same problem on two other classes of lattices which are generated by CFGs on the classes of undirected graphs and directed acyclic graphs.     

A branch and bound algorithm for minimizing the number of crossing arcs in bipartite graphs

Acyclic directed graphs are widely used in many fields of economic and social sciences. This has generated considerable interest in algorithms for drawing “good” maps of acyclic diagraphs. The most important criterion to obtain a readable map of an acyclic graph is that of minimizing the number of crossing arcs. In this paper, we present a branch and bound algorithm for solving the problem of minimizing the number of crossing arcs in a bipartite graph. Computational results are reported on a set of randomly generated test problems.     

一类因果模型的可识别性条件

因果问题在近代医学,生物学,社会科学的研究中占有非常重要的地位。通过因果关系预见某些行为或策略对研究对象的影响已经成为一些实际研究的最终目的。Rubin(1978)提出了解决因果问题的虚拟事实模型,建立了因果推断统计分析的基本框架。虚拟事实模型的因果效应是以实际观测数据为研究对象的,但又不完全由数据之间的相关性决定,因此在讨论因果效应时存在可识别性问题。如果因果效应可识别,则有可能利用观测数据直接计算因果效应。但是,众 所周知:在不加任何假设或限制的条件下,虚拟事实模型的因果效应是不可识别的。若要研究变量间的因果效应就必须对虚拟事实模型加入某些必要的限制,使因果效应在这些限制下可识别。郑忠国,张艳艳,童行伟在“因果模型因果效应的可识别性研究”中针对控制变量与协变量相互独立的一类模型的可识别性进行了研究,指出在某些特定的可替换性假设之下,模型的因果效应具有可识别性。该文将针对控制变量作用于协变量的虚拟事实模型进行可识别性研究。作者将指出:控制变量是否作用于协变量并不影响因果效应的可识别性和可替换性假设。并给出:此类模型因果效应可唯一确定的充要条件 。      

Planar acyclic oriented graphs

A plane Hasse representation of an acyclic oriented graph is a drawing of the graph in the Euclidean plane such that all arcs are straight-line segments directed upwards and such that no two arcs cross. We characterize completely those oriented graphs which have a plane Hasse representation such that all faces are bounded by convex polygons. From this we derive the Hasse representation analogue, due to Kelly and Rival of Fary's theorem on straight-line representations of planar graphs and the Kuratowski type theorem of Platt for acyclic oriented graphs with only one source and one sink. Finally, we describe completely those acyclic oriented graphs which have a vertex dominating all other vertices and which have no plane Hasse representation, a problem posed by Trotter.     

Identifiability of causal effect for a simple causal model

Counterfactual model is put forward to discuss the causal inference in the directed acyclic graph and its corresponding identifiability is thus studied with the ancillary information based on conditional independence. It is shown that the assumption of ignorability can be expanded to the assumption of replaceability,under which the causal efiects are identifiable.     

基于VAR和DAG的中国经济增长实证研究

本文利用近年来新发展的DAG方法对我国的GDP、投资、消费和出口的因果关系进行研究.与以前的研究方法相比较,DAG方法可为宏观经济变量的结构VAR模型的过度识别提供限制,同时能给出经济变量的同期和动态因果关系.实证研究表明,投资和消费既是我国GDP增长的同期原因,又是经济增长的短期和长期原因,而且实证结论不支持我国的出口导向型经济增长假设.     

Normalized graph Laplacians for directed graphs

We consider the normalized Laplace operator for directed graphs with positive and negative edge weights. This generalization of the normalized Laplace operator for undirected graphs is used to characterize directed acyclic graphs. Moreover, we identify certain structural properties of the underlying graph with extremal eigenvalues of the normalized Laplace operator. We prove comparison theorems that establish a relationship between the eigenvalues of directed graphs and certain undirected graphs. This relationship is used to derive eigenvalue estimates for directed graphs. Finally we introduce the concept of neighborhood graphs for directed graphs and use it to obtain further eigenvalue estimates.     

Representing Sparse Gaussian DAGs as Sparse R-Vines Allowing for Non-Gaussian Dependence

Modeling dependence in high-dimensional systems has become an increasingly important topic. Most approaches rely on the assumption of a multivariate Gaussian distribution such as statistical models on directed acyclic graphs (DAGs). They are based on modeling conditional independencies and are scalable to high dimensions. In contrast, vine copula models accommodate more elaborate features like tail dependence and asymmetry, as well as independent modeling of the marginals. This flexibility comes however at the cost of exponentially increasing complexity for model selection and estimation. We show a novel connection between DAGs with limited number of parents and truncated vine copulas under sufficient conditions. This motivates a more general procedure exploiting the fast model selection and estimation of sparse DAGs while allowing for non-Gaussian dependence using vine copulas. By numerical examples in hundreds of dimensions, we demonstrate that our approach outperforms the standard method for vine structure selection. Supplementary material for this article is available online.     

Feasibility of motion planning on acyclic and strongly connected directed graphs

Motion planning is a fundamental problem of robotics with applications in many areas of computer science and beyond. Its restriction to graphs has been investigated in the literature, for it allows one to concentrate on the combinatorial problem abstracting from geometric considerations. In this paper, we consider motion planning over directed graphs, which are of interest for asymmetric communication networks. Directed graphs generalize undirected graphs, while introducing a new source of complexity to the motion planning problem: moves are not reversible. We first consider the class of acyclic directed graphs and show that the feasibility can be solved in time linear in the product of the number of vertices and the number of arcs. We then turn to strongly connected directed graphs. We first prove a structural theorem for decomposing strongly connected directed graphs into strongly biconnected components. Based on the structural decomposition, we show that the feasibility of motion planning on strongly connected directed graphs can be decided in linear time.     

Acyclic directed graphs representing independence models

In this paper we study the problem of representing probabilistic independence models, in particular those closed under graphoid properties. We focus on acyclic directed graph (DAG): a new algorithm to build a DAG, given an ordering among random variables, is described and peculiarities and advantages of this approach are discussed. Moreover, we provide a necessary and sufficient condition for the existence of a perfect map representing an independence model and we describe an algorithm based on this characterization.     

The graded structure of Leavitt path algebras

A Leavitt path algebra associates to a directed graph a ?-graded algebra and in its simplest form it recovers the Leavitt algebra L(1, k). In this note, we first study this ?-grading and characterize the (?-graded) structure of Leavitt path algebras, associated to finite acyclic graphs, C _n -comet, multi-headed graphs and a mixture of these graphs (i.e., polycephaly graphs). The last two types are examples of graphs whose Leavitt path algebras are strongly graded. We give a criterion when a Leavitt path algebra is strongly graded and in particular characterize unital Leavitt path algebras which are strongly graded completely, along the way obtaining classes of algebras which are group rings or crossed-products. In an attempt to generalize the grading, we introduce weighted Leavitt path algebras associated to directed weighted graphs which have natural ⊕?-grading and in their simplest form recover the Leavitt algebras L(n, k). We then show that the basic properties of Leavitt path algebras can be naturally carried over to weighted Leavitt path algebras.     

Volume requirements of 3D upward drawings

This paper studies the problem of drawing directed acyclic graphs in three dimensions in the straight-line grid model so that all directed edges are oriented in a common (upward) direction. We show that there exists a family of outerplanar directed acyclic graphs whose volume requirement is super-linear. We also prove that for the case of directed trees a linear-volume upper bound is achievable.     

On Sturmian graphs

In this paper we define Sturmian graphs and we prove that all of them have a certain “counting” property. We show deep connections between this counting property and two conjectures, by Moser and by Zaremba, on the continued fraction expansion of real numbers. These graphs turn out to be the underlying graphs of compact directed acyclic word graphs of central Sturmian words. In order to prove this result, we give a characterization of the maximal repeats of central Sturmian words. We show also that, in analogy with the case of Sturmian words, these graphs converge to infinite ones.