# Geometric neighborhood for Bayesian network structures over three and four variables

##### The method
As it is described in a draft paper

M. Studený, J. Vomlel (2008). Geometric View on Learning Bayesian Network Structures.

the first step was to use the computer package

M. Franz (2006). Convex – a Maple package for convex geometry, version 1.1,
available at http://www.math.uwo.ca/~mfranz/convex/

to compute the facets of the standard imset polytope P. They are characterized by facet-defining inequalities. The result is summarized in the first table, which depicts whether a vertex (= standard imset) belongs to a facet (characterized by a facet-defining inequality), named shortly
vertex-facet table.

The method for obtaining the geometric neighborhood is based on the following two observations:

• First, every face F of P is uniquely determined by the list of vertices of P contained in F. This follows from Proposition 2.3(i) in
G.M. Ziegler (1995). Lectures on Polytopes New York:Springer-Verlag.
• Second, every proper face can be obtained as the intersection of all facets containing it. See the observation (14) on page 102 in
A. Schrijver (1986). Theory of Linear and Integer Programming/ Chichester:John Wiley.

We got the geometric neighborhood on the basis of the vertex-facet table. The procedure was as follows (the code written in R is available here).

• For every pair of distinct vertices u and v of P, we found the least face F(u,v) of P containing {u,v} as the intersection of all facets containing them. Of course, if there is no facet containing {u,v} then F(u,v)=P
• We characterized F(u,v) by the list R of vertices contained in F(u,v). Thus, we „obtained“ it as the „intersection“ of all columns of the vertex-facet table containing both u and v
• Finally, we recognized the geometric neighbors as those pairs \$[u ,v]\$ for which the face F(u,v) is en edge, that is, for which R={u,v}.
• The result is summarized in the other table, which depicts whether a vertex (= standard imset) is a geometric neighbor of another vertex, named shortly the vertex-vertex table.
• The table also indicates inclusion neighbors (the R code of this procedure is available here). They were determined as those pairs of standard imsets u, v for which the differential imset u-v is an elementary imset or its multiple by (-1). We confirmed for N={1,2,3,4} the conjecture that the inclusion neighborhood is contained in the geometric neighborhood (the code used to confirm the hypothesis was written in R and is available here).
##### Convention
In the vertex-facet tables we describe facet-defining inequalities in the form <m,u> +c >=  0,
where <.,.> denotes the scalar product, m is the vector of coefficients, u is the
standard imset, and c a constant (scalar).

In the vertex-facet tables the left margin defines the standard imset values for subsets A, |A| > 1 of N={1,2,3} and N={1,2,3,4}, respectively. The top margin defines the coefficients in m of the inequalities that define facets.

In the vertex-vertex table the left and top margins define the standard imset values for subsets A, |A| > 1 of N={1,2,3} and N={1,2,3,4}, respectively.
##### R code and the input files
For the computations we have used the following code written in the R language and the following two input files:

# Geometric neighborhood for Bayesian network structures over five variables

As concerns the case of 5 variables the geometric neighborhood has been computed by another method. More specifically, if V denotes vertices of a polytope P and if u,v are vertices then the line segment [u,v] is an edge of P iff v-u is not a non-negative linear combination  of the vectors w-u, where w belongs to V but differs from u and v. This was tested for every pair u,v of standard imsets by the linear program software Cplex.

Because of the size of the resulting matrix it has no sense to put on the web the whole vertex-vertex table. Instead, we provide the text files containing the relevant information that can be processed by a computer program. The geometric neighborhood for five variables is described in the text file S5.edges, which has 142 lines each having 8782 zero-one entries. Each line corresponds to a representative u of permutation equivalence of standard imsets, each entry to standard imset v. Value 1 of the entry means that u and v are geometric neighbors, value 0 means they are not. The list of permutation equivalence representatives u is the file S5.rep, while the list of all standard imsets is in the S5.ver.