Coincidence of the sets of minimal and irreducible join graphs over primary structure of algebraic Bayesian networks

An algebraic Bayesian network (ABN) is a probabilistic-logic graphical model of bases of knowledge patterns with uncertainty. A primary structure of an ABN is a set of knowledge patterns, that are ideals of conjunctions of positive literals except the empty conjunction endowed with scalar or interval probability estimates. A secondary ABN structure is represented by a graph constructed over the primary structure, which is called a join graph. From the point of view of learning of a global ABN structure, of interest are join graphs with the minimum number of edges and irreducible join graphs. A theorem on the coincidence of the sets of minimal and irreducible join graphs over the same primary structure is proved. A greedy algorithm constructing an arbitrary minimal join graph from a given primary structure is described. A theorem expressing the number of edges in a minimal join graph as the sum of the ranks of the incidence matrices of strong restrictions of a maximal join graph minus the number of significant weights is stated and proved. A generalized graph of maximal knowledge patterns (GGMKP) is a graph with the same vertex set as the join graph which is not subject to any constraints concerning the possibility of joining two vertices by an edge. It is proved that the pair consisting of the edge set of a maximal GGMKP and the set of all subsets of this graph such that the subtraction of any such subset from the maximal GGMKP yields an edge of the join graph on the same vertex set is a matroid.