Clique tree propagation [23,19,32] has a compilation step that transforms a BN into a secondary structure called clique tree or junction tree. The secondary structure allows CTP to compute the answers to all queries with one query variable and a fixed set of observations in twice the time needed to answer one such query in the clique tree. For many applications this is a desirable property since a user might want to compare the posterior probabilities of different variables.
CTP takes work to build the secondary structure before any observations have been received. When the Bayesian network is reused, the cost of building the secondary structure can be amortized over many cases. Each observation entails a propagation though the network.
Given all of the observations, VE processes one query at a time. If a user wants the posterior probabilities of several variables, or for a sequence of observations, she needs to run VE for each of the variables and observation sets.
The cost, in terms of the number of summations and multiplications, of answering a single query with no observations using VE is of the same order of magnitude as using CTP. A particular clique tree and propagation sequence encodes an elimination ordering; using VE on that elimination ordering results in approximately the same summations and multiplications of factors as in the CTP (there is some discrepancy, as VE does not actually form the marginals on the cliques, but works with conditional probabilities directly). Observations make VE simpler (the observed variables are eliminated at the start of the algorithm), but each observation in CTP requires propagation of evidence. Because VE is query oriented, we can prune nodes that are irrelevant to specific queries [13,22,2]. In CTP, on the other hand, the clique tree structure is kept static at run time, and hence does not allow pruning of irrelevant nodes.
CTP encodes a particular space-time tradeoff, and VE another. CTP is particularly suited to the case where observations arrive incrementally, where we want the posterior probability of each node, and where the cost of building the clique tree can be amortized over many cases. VE is suited for one-off queries, where there is a single query variable and all of the observations are given at once.
Unfortunately, there are large real-world networks that CTP cannot deal with due to time and space complexities (see Section 10 for two examples). In such networks, VE can still answer some of the possible queries because it permits pruning of irrelevant variables.