algorithm using Ω ( 2500) converged in about 75 minutes. In Figure 8a we show a histograms of the band widths (upper minus lower bound) found for the single node marginals for all unclamped nodes. Clearly, for the majority of the marginals very tight bounds are found.

Although exact computations are infeasible for this network, one can still use approximation methods to find an estimate of the single node marginals. Therefore, we ran the cluster variation method ( CVM ) as described in (Kappen & Wiegerinck, 2002).  For the clusters needed by CVM, we simply took all node sets for which a potential is defined. For ery unclamped node we computed the relative position of the approximation for the single node marginal within the bounding interval, denoted by η . Thus η = 0 indicates an approximation equal to the lower bound, and similarly η = 1 for the upper bound. Although there is no obvious reason the approximated marginals should be inside the bounding interval, it turned out they were. A histogram of all the relative positions is shown in Figure 8b, where we split up the full histogram into three parts, each referring to a certain region of band widths. It is remarkable that the shape of the histogram does not vary much given the tightness of the bounds. Approximations tend to be in the middle, but for all band widths there are approximations close to the edge.

One can argue that we are comparing apples to pears, since we can easily improve the results of both algorithms, while it is not clear which cases are comparable.  This is certainly true, but it is not our intention to make a comparison to determine which method is the best. Approximation and bounding methods both have their own benefits. We presented Figure 8b to give at least some intuition about the actual numbers.  In general we found that approximations are usually within the bounding intervals, when computation time is kept roughly the same. This does, however, not make the bounds irrelevant. On the contrary, one could use the bounding values as a validation whether approximations are good or even use them as confidence intervals.

## 6. Discussion

We have shown that bound propagation is a simple algorithm with surprisingly good results.

It performs exact computations on local parts of the network and keeps track of the uncertainties that brings along. In this way it is capable to compute upper and lower bounds on any marginal probability of a small set of nodes in the intractable network. Currently we do not understand which network properties are responsible for the tightness of the bounds found. In Figure 6, for instance, we saw islands of worse results in a sea of tight bounds. It is obvious that one bad bound influences its direct neighbourhood, since bound propagation performs local computations in the network. We have no clue, however, why these islands are at the location we found them.  We tried to find a correlation with the size of the weights
(rewriting the network potentials to a Boltzmann distribution) or with the local frustration of the network (spin glass state), but could not explain the quality of the bounds in terms of these quantities. Here we pose it as an open question.

The computational complexity of the algorithm is mainly determined by the state space of the separator nodes one uses, which makes the algorithm unsuitable for heavily connected nnetworks such as Boltzmann machines. Nevertheless, there is a large range of aritectures for which bound propagation can easily be done. Such networks typically have a limited