Learning Bayesian and Markov Networks with an Unreliable Oracle
Juha Harviainen, Pekka Parviainen, Vidya Sagar Sharma · 2026
Read Learning Bayesian and Markov Networks with an Unreliable Oracle by Juha Harviainen, Pekka Parviainen, Vidya Sagar Sharma (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-09563.txt.
Introduction
Juha Harviainen and colleagues study learning Bayesian and Markov network structure when the conditional independence oracle can err a bounded number of times. For Markov networks, few vertex-disjoint paths make the structure uniquely identifiable even when errors are moderately exponential in the vertex count. For Bayesian networks they prove no errors can be tolerated in general, even with treewidth and similar parameters bounded. They close with algorithms for the cases where the structure is uniquely identifiable.
Catalog record
| CREATOR | Juha Harviainen, Pekka Parviainen, Vidya Sagar Sharma |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67294 |
| LICENSE | http://creativecommons.org/licenses/by-sa/4.0/ |
| RIGHTS | CC BY SA |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.09563
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Learning Bayesian and Markov Networks with an Unreliable Oracle Juha Harviainen, Pekka Parviainen, Vidya Sagar Sharma Abstract We study constraint-based structure learning of Markov networks and Bayesian networks in the presence of an unreliable conditional independence oracle that makes at most a bounded number of errors. For Markov networks, we observe that a low maximum number of vertex-wise disjoint paths implies that the structure is uniquely identifiable even if the number of errors is (moderately) exponential in the number of vertices. For Bayesian networks, however, we prove that one cannot tolerate any errors to always identify the structure even when many commonly used graph parameters like treewidth are bounded. Finally, we give algorithms for structure learning when the structure is uniquely identifiable. 1 Introduction Probabilistic graphical models are used to represent joint distributions of several random variables. Typically, they consist of two parts that are a graphical structure expressing how the distribution factorizes and parameters specifying the distribution. There are several different types of probabilistic graphical models, among which this work concentrates on two commonly used models: Markov networks and Bayesian networks. The graph structure in a Markov network is an undirected graph and in a Bayesian network it is a directed acyclic graph (DAG). Both Markov and Bayesian networks are often learned from data, with the present work focusing on the constraint-based approach to learning. There, one conducts conditional independence tests and constructs a graph that expresses conditional independencies that match the test results. After one has learned the structure, the (distribution of) parameters can be estimated. We study only the first task, which is called structure learning. Typically, constraint-based structure learning algorithms such as the PC algorithm ( 9 ) are guaranteed to find the correct graph if certain assumptions hold. To make sure that a correct graph exists, one assumes that the data was generated from a distribution that is faithful to an undirected graph or a DAG for Markov and Bayesian networks, respectively. Another crucial assumption is that conditional independence tests always yield correct results. In other words, one assumes that there is infinite amount of data or one equivalently has access to a conditional independence oracle. In practice, conditional independence is evaluated with statistical tests on data. This leads to occasional errors and theoretical guarantees do not hold in practice. Motivated by this, we study theoretical properties of structure learning in a relaxed setting when we only have access to an unreliable oracle, that is, the oracle might make a small bounded number of errors. We are then interested in how many errors the oracle can be allowed to make if we want to be guaranteed to recover the hidden graph and how this affects the computational complexity of structure learning. Our first observation is that the number of allowed errors depends on the structure of the hidden graph. To this end, we introduce a property called k -identifiability . If a graph (in case of Markov networks) or a Markov equivalence class (in case of Bayesian networks) is k -identifiable then it can be identified uniquely given any oracle which makes at most k errors. We show that Markov networks with small maximum pairwise connectivity ( 6 ) are k -identifiable even when k is exponential in the number of vertices ( Theorem 1 ). The same does not hold for Bayesian networks; we rule out the possibility of bounding the number of errors by many graph parameters that have turned out to be useful in other situations ( Section 3.1.2 ). We also notice that computing exact k seems difficult and provide results for graphs whose structure is a chain ( Theorem 2 and Theorem 3 ). Finally, we study structure learning with an unreliable oracle. We show that the structure of a Markov network can be found in time n^{2k+O(1)}\cdot 2^{n} where n is the number of vertices (Theorem 4 ) and the structure of a Bayesian network in time n^{2k+O(1)}2^{n(k+O(1))} (Theorem 5 ). In contrast, Markov networks can be learned with O(n^{2}) queries and in polynomial time with an error-free oracle. Constraint-based structure learning for Bayesian networks is NP-hard even with an error-free oracle ( 1 ) . We further show that, in the worst case, one needs to query all the possible {n\choose 2}2^{n-2} conditional independence tests even when the oracle makes at most 1 error and we are promised that the hidden graph is one of two given candidates (Theorems 6 and 7 ). Related work. The presence of errors has lead to development of variants of the PC algorithms, such that robust PC ( 4 ) and conservative PC ( 7 ) , which are better suitable to handling errors. Another approach is to pose structure learning as a constraint satisfaction problem and to minimise (weighted) sum of violated test results ( 3 ) . Recently, 2 have studied error correction in structure learning. Their work concentrates on what kind of redundant tests are most useful. 2 Preliminaries We denote an undirected graph by G=(V,E) and a directed graph by D=(V,A) , where V , E , and A are the sets of vertices, undirected edges of the form \{u,v\}\subseteq V , and directed edges or arcs of the form (u,v)\in V\times V , respectively. The endpoints of both types of edges are u and v . A v_{1} – v_{\ell} path is a sequence of distinct vertices v_{1},v_{2},\dots,v_{\ell}\in V such that the graph has an edge of the form \{v_{i},v_{i+1}\} , (v_{i},v_{i+1}) , or (v_{i+1},v_{i}) for all i\in\{1,2,\dots,\ell-1\} . Vertices v_{2},v_{3},\dots,v_{\ell-1} are the internal vertices of the path. The skeleton of a directed graph is its underlying undirected graph. Throughout this paper, we use n=|V| to denote the number of vertices. In probabilistic graphical modeling, both Markov and Bayesian networks represent a set of variables as vertices and capture their conditional independencies with the structure of the network that is either an undirected graph or a DAG, respectively. For a detailed overview of probabilistic graphical modeling, see the textbook of 5 . Since we focus only structure learning and not parameter estimation, we will—with a mild abuse of terminology—use the terms Markov network and undirected graph interchangeably as well as the terms Bayesian network and DAG. To learn the structure called the hidden graph that corresponds to the data-generating process, one of the main approaches is to perform conditional independence queries for the variables and then find a graph that matches them the best. A Markov network G encodes the claim that variables u and v are conditionally independent given S\subseteq V\setminus\{u,v\} if every u – v path has an internal vertex from S , that is, they are separated by S . For a Bayesian network D , a more involved notion of d-separation is needed to encode the conditional independencies. A collider on an u – v path v_{1},v_{2},v_{3},\dots,v_{\ell-1},v_{\ell} with u=v_{1} and v=v_{\ell} is a vertex v_{i} with i\in\{2,3,\dots,\ell-1\} such that the graph has edges (v_{i-1},v_{i}) and (v_{i+1},v_{i}) . Variables u and v are then d-separated by S if for every u – v path v_{1},v_{2},v_{3},\dots,v_{\ell-1},v_{\ell} there is i\in\{2,3,\dots,\ell-1\} such that either (i) v_{i} is not a collider on the path and v_{i}\in S ;