 NSFPAR ID:
 10253360
 Date Published:
 Journal Name:
 Proceedings of the AAAI Conference on Artificial Intelligence
 Volume:
 35
 Issue:
 13
 ISSN:
 21595399
 Page Range / eLocation ID:
 1133411342
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

The classical ErdösGallai theorem kicked off the study ofgraph realizability by characterizing degree sequences. We extend this line of research by investigating realizability of directed acyclic graphs (DAGs)given both a local constraint via degree sequences and a global constraint via a sequence of reachability values (number of nodes reachable from a given node). We show that, without degree constraints, DAG reachability realization is solvable in linear time, whereas it is strongly NPcomplete given upper bounds on indegree or outdegree. After defining a suitable notion of bicriteria approximation based on consistency, we give two approximation algorithms achieving O(logn)reachability consistency and O(logn)degree consistency; the first, randomized, uses LP (Linear Program) rounding, while the second, deterministic, employs aksetpacking heuristic. We end with two conjectures that we hope motivate further study of realizability with reachability constraints.more » « less

null (Ed.)Many program analyses need to reason about pairs of matching actions, such as call/return, lock/unlock, or setfield/getfield. The family of Dyck languages { D k }, where D k has k kinds of parenthesis pairs, can be used to model matching actions as balanced parentheses. Consequently, many programanalysis problems can be formulated as Dyckreachability problems on edgelabeled digraphs. Interleaved Dyckreachability (InterDyckreachability), denoted by D k ⊙ D k reachability, is a natural extension of Dyckreachability that allows one to formulate programanalysis problems that involve multiple kinds of matchingaction pairs. Unfortunately, the general InterDyckreachability problem is undecidable. In this paper, we study variants of InterDyckreachability on bidirected graphs , where for each edge ⟨ p , q ⟩ labeled by an open parenthesis ”( a ”, there is an edge ⟨ q , p ⟩ labeled by the corresponding close parenthesis ”) a ”, and vice versa . Languagereachability on a bidirected graph has proven to be useful both (1) in its own right, as a way to formalize many programanalysis problems, such as pointer analysis, and (2) as a relaxation method that uses a fast algorithm to overapproximate languagereachability on a directed graph. However, unlike its directed counterpart, the complexity of bidirected InterDyckreachability still remains open. We establish the first decidable variant (i.e., D 1 ⊙ D 1 reachability) of bidirected InterDyckreachability. In D 1 ⊙ D 1 reachability, each of the two Dyck languages is restricted to have only a single kind of parenthesis pair. In particular, we show that the bidirected D 1 ⊙ D 1 problem is in PTIME. We also show that when one extends each Dyck language to involve k different kinds of parentheses (i.e., D k ⊙ D k reachability with k ≥ 2), the problem is NPhard (and therefore much harder). We have implemented the polynomialtime algorithm for bidirected D 1 ⊙ D 1 reachability. D k ⊙ D k reachability provides a new overapproximation method for bidirected D k ⊙ D k reachability in the sense that D k ⊙ D k reachability can first be relaxed to bidirected D 1 ⊙ D 1 reachability, and then the resulting bidirected D 1 ⊙ D 1 reachability problem is solved precisely. We compare this D 1 ⊙ D 1 reachabilitybased approach against another known overapproximating D k ⊙ D k reachability algorithm. Surprisingly, we found that the overapproximation approach based on bidirected D 1 ⊙ D 1 reachability computes more precise solutions, even though the D 1 ⊙ D 1 formalism is inherently less expressive than the D k ⊙ D k formalism.more » « less

Abstract Motivation Modern problems of concept annotation associate an object of interest (gene, individual, text document) with a set of interrelated textual descriptors (functions, diseases, topics), often organized in concept hierarchies or ontologies. Most ontology can be seen as directed acyclic graphs (DAGs), where nodes represent concepts and edges represent relational ties between these concepts. Given an ontology graph, each object can only be annotated by a consistent subgraph; that is, a subgraph such that if an object is annotated by a particular concept, it must also be annotated by all other concepts that generalize it. Ontologies therefore provide a compact representation of a large space of possible consistent subgraphs; however, until now we have not been aware of a practical algorithm that can enumerate such annotation spaces for a given ontology.
Results We propose an algorithm for enumerating consistent subgraphs of DAGs. The algorithm recursively partitions the graph into strictly smaller graphs until the resulting graph becomes a rooted tree (forest), for which a lineartime solution is computed. It then combines the tallies from graphs created in the recursion to obtain the final count. We prove the correctness of this algorithm, propose several practical accelerations, evaluate it on random graphs and then apply it to characterize four major biomedical ontologies. We believe this work provides valuable insights into the complexity of concept annotation spaces and its potential influence on the predictability of ontological annotation.
Availability and implementation https://github.com/shawnpeng/countingconsistentsubDAG
Supplementary information Supplementary data are available at Bioinformatics online.

Francisco Ruiz, Jennifer Dy (Ed.)Graphical models such as Markov random fields (MRFs) that are associated with undirected graphs, and Bayesian networks (BNs) that are associated with directed acyclic graphs, have proven to be a very popular approach for reasoning under uncertainty, prediction problems and causal inference. Parametric MRF likelihoods are wellstudied for Gaussian and categorical data. However, in more complicated parametric and semiparametric set tings, likelihoods specified via clique potential functions are generally not known to be congenial (jointly wellspecified) or nonredundant. Congenial and nonredundant DAG likelihoods are far simpler to specify in both parametric and semiparametric settings by modeling Markov factors in the DAG factorization. However, DAG likelihoods specified in this way are not guaranteed to coincide in distinct DAGs within the same Markov equivalence class. This complicates likelihoods based model selection procedures for DAGs by “sneaking in” potentially un warranted assumptions about edge orientations. In this paper we link a density function decomposition due to Chen with the clique factorization of MRFs described by Lauritzen to provide a general likelihood for MRF models. The proposed likelihood is composed of variationally independent, and nonredundant closed form functionals of the observed data distribution, and is sufficiently general to apply to arbitrary parametric and semiparametric models. We use an extension of our developments to give a general likelihood for DAG models that is guaranteed to coincide for all members of a Markov equivalence class. Our results have direct applications for model selection and semiparametric inference.more » « less

Agostino Dovier, Andrea Formisano (Ed.)Explainable artificial intelligence (XAI) aims at addressing complex problems by coupling solutions with reasons that justify the provided answer. In the context of Answer Set Programming (ASP) the user may be interested in linking the presence or absence of an atom in an answer set to the logic rules involved in the inference of the atom. Such explanations can be given in terms of directed acyclic graphs (DAGs). This article reports on the advancements in the development of the XAI system xASP by revising the main foundational notions and by introducing new ASP encodings to compute minimal assumption sets, explanation sequences, and explanation DAGs.more » « less