Learning Bayesian and Markov Networks with an Unreliable Oracle

• URL: http://arxiv.org/abs/2603.09563v1
• Date: Tue, 10 Mar 2026 12:07:53 GMT
• Title: Learning Bayesian and Markov Networks with an Unreliable Oracle
• Abstract summary: We study constraint-based structure learning of Markov networks and Bayesian networks.<n>We show that one cannot tolerate any errors to always identify the structure even when many commonly used graph parameters like treewidth are bounded.
• Score: 10.284830265068795
• License: http://creativecommons.org/licenses/by-sa/4.0/
• 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.

Related papers

• Variational Bayesian Flow Network for Graph Generation [54.94088904387278]
  We propose Variational Bayesian Flow Network (VBFN) for graph generation.<n>VBFN performs variational lifting to a tractable joint Gaussian variational belief family governed by structured precisions.<n>On synthetic and molecular graph datasets, VBFN improves fidelity and diversity, and surpasses baseline methods.
  arXiv  Detail & Related papers  (2026-01-30T03:59:38Z)
• Semantic Loss Functions for Neuro-Symbolic Structured Prediction [74.18322585177832]
  We discuss the semantic loss, which injects knowledge about such structure, defined symbolically, into training. It is agnostic to the arrangement of the symbols, and depends only on the semantics expressed thereby. It can be combined with both discriminative and generative neural models.
  arXiv  Detail & Related papers  (2024-05-12T22:18:25Z)
• Formal Verification of Graph Convolutional Networks with Uncertain Node Features and Uncertain Graph Structure [7.133681867718039]
  Graph neural networks are becoming increasingly popular in the field of machine learning.<n>They have been applied in safety-critical environments where perturbations inherently occur.<n>This research addresses the non-passing gap by preserving the dependencies of all elements in the underlying computations.
  arXiv  Detail & Related papers  (2024-04-23T14:12:48Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• ARISE: Graph Anomaly Detection on Attributed Networks via Substructure Awareness [70.60721571429784]
  We propose a new graph anomaly detection framework on attributed networks via substructure awareness (ARISE) ARISE focuses on the substructures in the graph to discern abnormalities. Experiments show that ARISE greatly improves detection performance compared to state-of-the-art attributed networks anomaly detection (ANAD) algorithms.
  arXiv  Detail & Related papers  (2022-11-28T12:17:40Z)
• Latent Hierarchical Causal Structure Discovery with Rank Constraints [19.61598654735681]
  We consider a challenging scenario for causal structure identification, where some variables are latent and they form a hierarchical graph structure. We propose an estimation procedure that can efficiently locate latent variables, determine their cardinalities, and identify the latent hierarchical structure.
  arXiv  Detail & Related papers  (2022-10-01T03:27:54Z)
• Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold [3.6052935394000234]
  Block model is a canonical random graph model for clustering and community detection on network-structured data. No estimator based on the network topology can perform substantially better than chance on sparse graphs if the model parameter is below a certain threshold. We prove that with an arbitrary fraction of the labels feasible throughout the parameter domain.
  arXiv  Detail & Related papers  (2022-05-24T00:03:25Z)
• Hybrid Bayesian network discovery with latent variables by scoring multiple interventions [5.994412766684843]
  We present the hybrid mFGS-BS (majority rule and Fast Greedy equivalence Search with Bayesian Scoring) algorithm for structure learning from discrete data. The algorithm assumes causal insufficiency in the presence of latent variables and produces a Partial Ancestral Graph (PAG) Experimental results show that mFGS-BS improves structure learning accuracy relative to the state-of-the-art and it is computationally efficient.
  arXiv  Detail & Related papers  (2021-12-20T14:54:41Z)
• Structure Learning of Contextual Markov Networks using Marginal Pseudo-likelihood [5.364120183147694]
  We introduce the marginal pseudo-likelihood as an analytically tractable criterion for general contextual Markov networks. Our criterion is shown to yield a consistent structure estimator.
  arXiv  Detail & Related papers  (2021-03-29T12:13:15Z)
• Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning [50.24174211654775]
  We present a novel contrastive self-supervised learning framework for anomaly detection on attributed networks. Our framework fully exploits the local information from network data by sampling a novel type of contrastive instance pair. A graph neural network-based contrastive learning model is proposed to learn informative embedding from high-dimensional attributes and local structure.
  arXiv  Detail & Related papers  (2021-02-27T03:17:20Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  "Graph Substructure Networks" (GSN) is a topologically-aware message passing scheme based on substructure encoding. We show that it is strictly more expressive than the Weisfeiler-Leman (WL) graph isomorphism test. We perform an extensive evaluation on graph classification and regression tasks and obtain state-of-the-art results in diverse real-world settings.
  arXiv  Detail & Related papers  (2020-06-16T15:30:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.