Case 1: u = ∅: To get a value of ∅, the property should fire neither at c, nor up to or at any of the ci**'s. That**
is, we need p(x, yc, c) = ∅ and incoming messages at c whose value arguments are also ∅**. Thus** Ic→c
′ (ys, ∅**) is**
computed as:

$$\operatorname*{max}_{{\bf y}_{c}\sim{\bf y}_{s}}\quad\phi_{c}({\bf y}_{c})+\sum_{j=1}^{l}I_{c_{j}\to c}({\bf y}_{s_{j}},\emptyset)$$

Case 2: u ∈ Rp: In this case, p(x, yc, c**) the value arguments of its incoming messages should be one of** u and ∅, with at least one of them being u (otherwise all of them will be ∅ and we will get ∅ at c**). This will hold**
if the predicate V1(yc, v1, . . . , vl**), defined below, is true.**

$$V_{1}(\mathbf{y}_{c},v_{1},\ldots,v_{l})\triangleq(\forall j:v_{j}\in\{u,\emptyset\})\wedge(p(\mathbf{x},\mathbf{y}_{c},c)\in\{u,\bot\})\wedge(p(\mathbf{x},\mathbf{y}_{c},c)=u\ \vee\ \exists v_{j}=u)\tag{16}$$

Here v1, . . . , vl denote value arguments of the incoming messages at c excluding the one from c′**. If the set**
{v1, . . . , vl, p(x, yc, c)} contains two distinct values from Rp, then they will conflict and create ⊥ at c on composition. Thus, V1 precisely and completely represents the set of valid combinations for producing u**. Using** V1 we can compute Ic→c
′ (ys, u**) as:**

$$\operatorname*{max}_{\mathbf{y}_{c}\sim\mathbf{y}_{s},v_{1},...,v_{l}}\phi_{c}(\mathbf{y}_{c})+\sum_{j=1}^{l}I_{c_{j}\to c}(\mathbf{y}_{s_{j}},v_{j})$$
$$(17)$$

Case 3: u =⊥: We can produce ⊥ **when either (a) value arguments of two or more incoming messages at** c conflict or (b) the property value at c conflicts with the value argument of one of the incoming messages or (c)
either the property value at c or any one of the value arguments is ⊥. The predicate V2(yc, v1, . . . , vl**) returns**
true if any one of the above outcomes hold:

$V_{2}(\mathbf{y}_{c},v_{1},\ldots,v_{l})=(\exists j:v_{j}=\perp)\ \vee(p(\mathbf{x},\mathbf{y}_{c},c)=\perp)\vee(\exists j,k:v_{j}\neq v_{k}\wedge v_{j},v_{k}\in\mathcal{R}_{p})$  $\vee\ \ (p(\mathbf{x},\mathbf{y}_{c},c)=v_{0},\ v_{0}\in\mathcal{R}_{p})\wedge(\exists j:v_{j}\neq v_{0},\ v_{j}\in\mathcal{R}_{p})$
The outgoing message Ic→c
′ (ys, u**) is then:**

$$I_{c\to c^{\prime}}(\mathbf{y}_{s},\bot)=\max_{\begin{subarray}{c}\mathbf{y}_{c}\sim\mathbf{y}_{s},v_{1},\ldots,v_{l}\\ V_{2}(\mathbf{y}_{c},v_{1},\ldots,v_{l})\end{subarray}}\phi_{c}(\mathbf{y}_{c})+\sum_{j=1}^{l}I_{c_{j}\to c}(\mathbf{y}_{s_{j}},v_{j})\tag{1}$$
$$(18)$$
$$(19)$$
$$(21)$$

After completing the internal message passing schedule, we can compute the final aggregated message M(u)
by sending a message from the last clique (wlog, say c′**) to a dummy root clique** r:
M(u) , Ic
′→r( , u) **(20)**
where the separator labeling is irrelevant because the message is to **a dummy clique** r.

If |K| = 1, then the message mi→p(v) is simply M(v**). This treatment generalizes nicely to the case when**
|K| > 1. We extend the internal message vector I(.) for each combination of values of the |K| **properties. Call it**
Ic→c
′ (ys, u1, . . . u|K|) where uj ∈ R′pj**. Let the final aggregated message at a dummy root clique inside instance**
i be M(u1, . . . u|K|). The outgoing message mi→p(v) to property p **can now be computed as:**

$$m_{i\to p}(v)=\operatorname*{max}_{u_{1},\ldots,u_{|K|}:\atop u_{p}=v}M(u_{1},\ldots u_{|K|})+\sum_{p^{\prime}\neq p}m_{p^{\prime}\to i}(u_{p^{\prime}})$$

The overhead for |K| > 1 is that we have to absorb the incoming messages from the other |K| − **1 properties,**
shown in Figure 3 in the red portion.

## 5.1.2 Approximations

Various approximations are possible to reduce the number of value combinations for which messages have to be maintained.

other $|K|=1$ p. 