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

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:

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). 

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.
Results for three variables
Results for four variables
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.