Learning Bayesian and Markov Networks with an Unreliable Oracle

Juha Harviainen; Pekka Parviainen; Vidya Sagar Sharma

cs.LGMar 10, 2026

Learning Bayesian and Markov Networks with an Unreliable Oracle

Authors: Juha Harviainen, Pekka Parviainen, Vidya Sagar Sharma

Organizations: University of Helsinki, Finland · University of Bergen, Norway · Indian Institute of Technology Madras, India

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.

Figures & tables

Panel of Figure 1 — Figure 1: Two sparse graphs whose d-separation disctance is 1.

Nr of edges	Nr of MECs	Min	Mean	Max
0	1	8	8	8
1	10	8	8	8
2	75	4	4.8	8
3	350	2	4.7	6
4	1120	1	3.8	7
5	2130	1	2.3	6

Table 1: Distances to the nearest neighbor in MECs with

5

vertices. MECs are grouped by the number of edges and the table shows minimum, mean and maximum distance to the nearest neighbor MECs with a specific number of edges.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 2 — Figure 2: Skeletons of $D$ and $D^{\prime}$ .

Panel of Figure 3 — Figure 3: Examples of $D$ and $D^{\prime}$ .

Panel of Figure 4 — Figure 4: Possible skeletons of $D^{\prime\prime}$ .

Graph Structure Learning

Graph structure learning infers or adapts network connections from data for statistical discovery and downstream prediction.

See all 138 papers

KG-SoftMAP: Soft Knowledge-Graph Priors for Bayesian Network Structure Learning from Sparse Discrete Data
Jun 9, 2026Guoliang Xu, James E. CorterGraph Structure Learning Bayesian Network Structure Learning
Columbia University
High-Order Markov Blanket Discovery via a k-Order Relaxation of the Faithfulness Assumption
Jul 29, 2026Loong Kuan Lee, Ragavi Krishnamoorthy, Nico PiatkowskiBayesian Networks
Hybrid Intelligence, Fraunhofer IAIS, Sankt Augustin, Germany
ABSOL: Aggregated Bayesian Subsampling Orchestrated with LLMs
Sep 14, 2026Jackson Hassell, Chen Shen, Estevam HruschkaGraph Structure Learning Bayesian Network Structure Learning
Megagon Labs

Jun 9, 2026J/K move · Enter open · S save

KG-SoftMAP: Soft Knowledge-Graph Priors for Bayesian Network Structure Learning from Sparse Discrete Data

Guoliang Xu, James E. Corter

Columbia University

Graph Structure Learning Bayesian Network Structure Learning Bayesian Networks Bayesian Inference Causal Structure Learning

Open paper AskPDF arXiv

Learning Bayesian network (BN) structure from sparse discrete data is hard: when each instance records only a few variables, most variable pairs lack the joint observations needed for reliable scoring, and data-only methods recover little structure. Imperfect domain knowledge, expressible as a weighted directed knowledge graph (KG), is often available. KG-SoftMAP encodes such a KG as a finite-strength, confidence-weighted edge prior and maximizes a MAP objective that adds this logit-form prior to the BDeu score. With an informative but imperfect KG, KG-SoftMAP recovers partial directed structure even at observation rate rho=0.05, with directed F1 (DF1) of 0.19-0.32 across benchmarks. At higher observation rates within this sparse grid, DF1 reaches 0.44-0.66 at rho=0.20 and 0.46-0.64 at rho=0.40. Across the same three rates, KG-SoftMAP without the KG prior averages DF1 0.00, 0.19, and 0.21. Stress tests that corrupt, remove, or blur the KG signal, together with checks on LLM-extracted graphs beyond canonical benchmarks, show that recovery rises and falls with KG quality. On three real sparse educational datasets without ground-truth DAGs, we evaluate prediction, calibration, and KG-consistency. On Short Answer Feedback (SAF), KG-SoftMAP+VE reaches Fail-class F1 0.75 versus 0.78 for logistic regression while also providing an inspectable concept graph, calibrated Fail probabilities, and posterior queries from partially observed concept evidence. The remaining datasets sharpen the operating picture: weak heuristic KG signal leaves prediction unchanged, while an independent expert ontology moves the learned graph toward expert relatedness.

Abstract

Graph Structure Learning

Explore similar work

KG-SoftMAP: Soft Knowledge-Graph Priors for Bayesian Network Structure Learning from Sparse Discrete Data

High-Order Markov Blanket Discovery via a k-Order Relaxation of the Faithfulness Assumption

ABSOL: Aggregated Bayesian Subsampling Orchestrated with LLMs