On Learning a Hidden Directed Graph with Path Queries
In this paper, we consider the problem of reconstructing a directed graph using path queries. In this query model of learning, a graph is hidden from the learner, and the learner can access information about it with path queries. For a source and destination node, a path query returns whether there is a directed path from the source to the destination node in the hidden graph. In this paper we first give bounds for learning graphs on $n$ vertices and $k$ strongly connected components. We then study the case of bounded degree directed trees and give new algorithms for learning "almost-trees" -- directed trees to which extra edges have been added. We also give some lower bound constructions justifying our approach.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Learning undirected models via query training
Typical amortized inference in variational autoencoders is specialized for a single probabilistic query. Here we propose an inference network architecture that generalizes to unseen probabilistic queries. Instead of an e…
DecoderQuery Training: Learning a Worse Model to Infer Better Marginals in Undirected Graphical Models with Hidden Variables
Probabilistic graphical models (PGMs) provide a compact representation of knowledge that can be queried in a flexible way: after learning the parameters of a graphical model once, new probabilistic queries can be answere…
Learning Linear Non-Gaussian Graphical Models with Multidirected Edges
In this paper we propose a new method to learn the underlying acyclic mixed graph of a linear non-Gaussian structural equation model given observational data. We build on an algorithm proposed by Wang and Drton, and we s…
Entropic Inequality Constraints from $e$-separation Relations in Directed Acyclic Graphs with Hidden Variables
Directed acyclic graphs (DAGs) with hidden variables are often used to characterize causal relations between variables in a system. When some variables are unobserved, DAGs imply a notoriously complicated set of constrai…
Indexing Graph Search Trees and Applications
We consider the problem of compactly representing the Depth First Search (DFS) tree of a given undirected or directed graph having $n$ vertices and $m$ edges while supporting various DFS related queries efficiently in th…