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.     

Performance analysis of asynchronous parallel Jacobi

The directed acyclic graph (DAG) associated with a parallel algorithm captures the partial order in which separaT.L.cal computations are completed and how their outputs are subsequently used in further computations. Unlike in a synchronous parallel algorithm, the DAG associated with an asynchronous parallel algorithm is not predetermined. Instead, it is a product of the asynchronous timing dynamics of the machine and cannot be known in advance, as such it is best thought of as a pseudorandom variable. In this paper, we present a formalism for analyzing the performance of asynchronous parallel Jacobi’s method in terms of its DAG. We use this app.roach to prove error bounds and bounds on the rate of convergence. The rate of convergence bounds is based on the statistical properties of the DAG and is valid for systems with a non-negative iteration matrix. We supp.ort our theoretical results with a suit of numerical examples, where we compare the performance of synchronous and asynchronous parallel Jacobi to certain statistical properties of the DAGs associated with the computations. We also present some examples of small matrices with elements of mixed sign, which demonstrate that determining whether a system will converge under asynchronous iteration in this more general setting is a far more difficult problem.     

CONVERGENCE OF BACKPROPAGATION WITH MOMENTUM FOR NETWORK ARCHITECTURES WITH SKIP CONNECTIONS

We study a class of deep neural networks with architectures that form a directed acyclic graph(DAG).For backpropagation defined by gradient descent with adaptive momentum,we show weights converge for a large class of nonlinear activation functions.'The proof generalizes the results of Wu et al.(2008)who showed convergence for a feed-forward network with one hidden layer.For an example of the effectiveness of DAG architectures,we describe an example of compression through an AutoEncoder,and compare against sequential feed-forward networks under several metrics.     

Upward straight-line embeddings of directed graphs into point sets

In this paper we study the problem of computing an upward straight-line embedding of a planar DAG (directed acyclic graph) G into a point set S, i.e. a planar drawing of G such that each vertex is mapped to a point of S, each edge is drawn as a straight-line segment, and all the edges are oriented according to a common direction. In particular, we show that no biconnected DAG admits an upward straight-line embedding into every point set in convex position. We provide a characterization of the family of DAGs that admit an upward straight-line embedding into every convex point set such that the points with the largest and the smallest y-coordinate are consecutive in the convex hull of the point set. We characterize the family of DAGs that contain a Hamiltonian directed path and that admit an upward straight-line embedding into every point set in general position. We also prove that a DAG whose underlying graph is a tree does not always have an upward straight-line embedding into a point set in convex position and we describe how to construct such an embedding for a DAG whose underlying graph is a path. Finally, we give results about the embeddability of some sub-classes of DAGs whose underlying graphs are trees on point set in convex and in general position.     

Ontology concepts and tools for statistical genomics

In computer science, an ontology is any formally structured vocabulary covering a conceptual domain. Gene Ontology (GO) is a structured collection of terms defining biological processes, cellular components, or molecular functions for the purpose of characterizing gene products and functions. The structure of GO is a directed acyclic graph (DAG) with typed edges. We describe a simple formalism for working with ontologies for statistical purposes, and define object-ontology complexes, which encode the usage of the vocabulary to label objects under analysis. Recently developed concepts of information content and semantic similarity are evaluated and used to explore the association between LocusLink loci and GO. We investigate relations between GO DAG structure, association evidence codes and term information content, illustrate computation of semantic similarities of genes within and between clusters discovered in a microarray, and describe a more general ontology and its use in inference on genetic network structure.     

Interval Analysis on Directed Acyclic Graphs for Global Optimization

A directed acyclic graph (DAG) representation of optimization problems represents each variable, each operation, and each constraint in the problem formulation by a node of the DAG, with edges representing the flow of the computation. Using bounds on ranges of intermediate results, represented as weights on the nodes and a suitable mix of forward and backward evaluation, it is possible to give efficient implementations of interval evaluation and automatic differentiation. It is shown how to combine this with constraint propagation techniques to produce narrower interval derivatives and slopes than those provided by using only interval automatic differentiation preceded by constraint propagation. The implementation is based on earlier work by L.V. Kolev, (1997), Reliable Comput., 3, 83–93 on optimal slopes and by C. Bliek, (1992), Computer Methods for Design Automation, PhD Thesis, Department of Ocean Engineering, Massachusetts Institute of Technology on backward slope evaluation. Care is taken to ensure that rounding errors are treated correctly. Interval techniques are presented for computing from the DAG useful redundant constraints, in particular linear underestimators for the objective function, a constraint, or a Lagrangian. The linear underestimators can be found either by slope computations, or by recursive backward underestimation. For sufficiently sparse problems the work is proportional to the number of operations in the calculation of the objective function (resp. the Lagrangian). Mathematics Subject Classification (2000). primary 65G40, secondary 90C26     

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.     

Average-case analysis of incremental topological ordering

Many applications like pointer analysis and incremental compilation require maintaining a topological ordering of the nodes of a directed acyclic graph (DAG) under dynamic updates. All known algorithms for this problem are either only analyzed for worst-case insertion sequences or only evaluated experimentally on random DAGs. We present the first average-case analysis of incremental topological ordering algorithms. We prove an expected runtime of under insertion of the edges of a complete DAG in a random order for the algorithms of Alpern et al. (1990) [4], Katriel and Bodlaender (2006) [18], and Pearce and Kelly (2006) [23].     

Hierarchical multilabel classification based on path evaluation

Multi-label classification assigns more than one label for each instance; when the labels are ordered in a predefined structure, the task is called Hierarchical Multi-label Classification (HMC). In HMC there are global and local approaches. Global approaches treat the problem as a whole but tend to explode with large datasets. Local approaches divide the problem into local subproblems, but usually do not exploit the information of the hierarchy. This paper addresses the problem of HMC for both tree and Direct Acyclic Graph (DAG) structures whose labels do not necessarily reach a leaf node. A local classifier per parent node is trained incorporating the prediction of the parent(s) node(s) as an additional attribute to include the relations between classes. In the classification phase, the branches with low probability to occur are pruned, performing non-mandatory leaf node prediction. Our method evaluates each possible path from the root of the hierarchy, taking into account the prediction value and the level of the nodes; selecting the path (or paths in the case of DAGs) with the highest score. We tested our method with 20 datasets with tree and DAG structured hierarchies against a number of state-of-the-art methods. Our method proved to obtain superior results when dealing with deep and populated hierarchies.     

DAG‐Width and Circumference of Digraphs

We prove that every digraph of circumference l has DAG‐width at most l. This is best possible and solves a recent conjecture from S. Kintali (ArXiv:1401.2662v1 [math.CO], January 2014).¹ As a consequence of this result we deduce that the k‐linkage problem is polynomially solvable for every fixed k in the class of digraphs with bounded circumference. This answers a question posed in J. Bang‐Jensen, F. Havet, and A. K. Maia (Theor Comput Sci 562 (2014), 283–303). We also prove that the weak k‐linkage problem (where we ask for arc‐disjoint paths) is polynomially solvable for every fixed k in the class of digraphs with circumference 2 as well as for digraphs with a bounded number of disjoint cycles each of length at least 3. The case of bounded circumference digraphs is still open. Finally, we prove that the minimum spanning strong subdigraph problem is NP‐hard on digraphs of DAG‐width at most 5.     

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.     

Enumeration of labelled chain graphs and labelled essential directed acyclic graphs

A chain graph is a digraph whose strong components are undirected graphs and a directed acyclic graph (ADG or DAG) G is essential if the Markov equivalence class of G consists of only one element. We provide recurrence relations for counting labelled chain graphs by the number of chain components and vertices; labelled essential DAGs by the number of vertices. The second one is a lower bound for the number of labelled essential graphs. The formula for labelled chain graphs can be extended in such a way, that allows us to count digraphs with two additional properties, which essential graphs have.     

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

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

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.     

DAG reversal is NP-complete

Runs of numerical computer programs can be visualized as directed acyclic graphs (DAGs). We consider the problem of restoring the intermediate values computed by such a program (the vertices in the DAG) in reverse order for a given upper bound on the available memory. The minimization of the associated computational cost in terms of the number of performed arithmetic operations is shown to be NP-complete. The reversal of the data-flow finds application, for example, in the efficient evaluation of adjoint numerical programs. We derive special cases of numerical programs that require the intermediate values exactly in reverse order, thus establishing the NP-completeness of the optimal adjoint computation problem. Last but not least we review some state-of-the-art approaches to efficient data-flow reversal taken by existing software tools for automatic differentiation.     

Identifiability of intermediate variables on causal paths

We discuss the discovery of causal mechanisms and identifiability of intermediate variables on a causal path. Different from variable selection, we try to distinguish intermediate variables on the causal path from other variables. It is also different from ordinary model selection approaches which do not concern the causal relationships and do not contain unobserved variables. We propose an approach for selecting a causal mechanism depicted by a directed acyclic graph (DAG) with an unobserved variable. We consider several causal networks, and discuss their identifiability by observed data. We show that causal mechanisms of linear structural equation models are not identifiable. Furthermore, we present that causal mechanisms of nonlinear models are identifiable, and we demonstrate the identifiability of causal mechanisms of quadratic equation models. Sensitivity analysis is conducted for the identifiability.     

On the core and nucleolus of directed acyclic graph games

We introduce directed acyclic graph (DAG) games, a generalization of standard tree games, to study cost sharing on networks. This structure has not been previously analyzed from a cooperative game theoretic perspective. Every monotonic and subadditive cost game—including monotonic minimum cost spanning tree games—can be modeled as a DAG-game. We provide an efficiently verifiable condition satisfied by a large class of directed acyclic graphs that is sufficient for the balancedness of the associated DAG-game. We introduce a network canonization process and prove various structural results for the core of canonized DAG-games. In particular, we characterize classes of coalitions that have a constant payoff in the core. In addition, we identify a subset of the coalitions that is sufficient to determine the core. This result also guarantees that the nucleolus can be found in polynomial time for a large class of DAG-games.     

The geometry of matrix eigenvalue methods

This paper explores the relations between the matrix Riccati equation and the standard matrix eigenvalue methods. It is demonstrated that the mathematics of the analysis of the two objects is essentially the same; consisting of the analysis of flows on the homogeneous spaces of various Lie groups.Supported in part by DOE Contract DE-ACOL-80RA-5256.Supported in part by DOE Contract DE-ACOL-80RA-5256 and by NASA Grant DAG2-82.     

Converting suffix trees into factor/suffix oracles

Several methods to compress suffix trees were defined, most of them with the aim of obtaining compact (that is, space economical) index structures. Besides this practical aspect, a compression method can reveal structural properties of the resulting data structure, allowing a better understanding of it and a better estimation of its performances.

In this paper, we propose a simple method to compress suffix trees by merging couples of nodes. This idea was already used in the literature in a context different from ours. The originality of our approach is that the nodes we merge are not chosen with respect to their subtrees (which is difficult to test algorithmically), nor with respect to the words spelled along branches (which usually requires testing several branches before finding the good one) but with respect to their position in the tree (which is easy to compute). Another particularity of our method is it needs to read no edge label: it is exclusively based on the topology of the suffix tree. The compact structure resulting after compression is the factor/suffix oracle introduced by Allauzen, Crochemore and Raffinot whose accepted language includes the accepted language of the corresponding suffix tree.

The interest of our paper is therefore threefold:

1. A topology-based compression method is defined for (compact) suffix trees.

2. A new property of a factor/suffix oracle is established, that is, like a DAG, it results from the corresponding suffix tree after a linear number of appropriate node mergings; unlike a DAG, the merged nodes do not necessarily have isomorphical subtrees.

3. A new algorithm to transform a suffix tree into a factor/suffix oracle is given, which has linear running time and thus improves the quadratic complexity previously known for the same task.

Enumerating K best paths in length order in DAGs

We address the problem of finding the K best paths connecting a given pair of nodes in a directed acyclic graph (DAG) with arbitrary lengths. One of the main results in this paper is the proof that a tree representing the kth shortest path is obtained by an arc exchange in one of the previous (k − 1) trees (each of which contains a previous best path). An O(m + K(n + log K)) time and O(K + m) space algorithm is designed to explicitly determine the K shortest paths in a DAG with n nodes and m arcs. The algorithm runs in O(m + Kn) time using O(K + m) space in DAGs with integer length arcs. Empirical results confirming the superior performance of the algorithm to others found in the literature for randomly generated graphs are reported.