

![0_image_0.png](0_image_0.png) 

Figure 3: The Relational Affinity Propagation proposed in this paper: (a) a schematic diagram of the matrix of binary hidden variables(circles), and variables within the green shade corresponding to some leaf nodes; while those within the pink shade corresponding to some root nodes of some saplings. (b) incoming and outgoing messages of a hidden variable node from/to its associated factor nodes. There are two more messages σ and τ. Note that for (a), we omit E, I
and S factors simply for the sake of clarity.

Let pa(.) be a function that returns the index of the parent node of its argument, and **explr**(.) be a function that return the index of the argument's exemplar. The factor F,
"single parent constraint", checks the violation of multiple parent concepts pointing to a given concept. The constraint is formally defined as follows:

is formally defined as follows.  $$F_{j}(c_{1j},\cdots,c_{Nj})=\left\{\begin{array}{ll}-\infty&\exists i,k:c_{ij}=1;c_{kj}=1;\\ &explr(pa(i))\neq explr(pa(k)),\\ 0&\mbox{otherwise.}\end{array}\right.\tag{2}$$  From 2(a) all together the same as above.  
Figure 3(a) illustrates the way we impose the new constraint on the binary variable matrix. The configuration shown in the figure is valid since both C and D belong to the same exemplar E and their respective parents, A and B, belong to the same exemplar A. However, if cBB = 1, then the configuration is invalid, because parents of nodes in the cluster of exemplar E will belong to different exemplars. This constraint is imposed only on leaf nodes, because merging root nodes will never lead to multiple parents. The global objective function for Relational Affinity Propagation is basically Eq. (1) plus Pj Fj (c1j , · · · , cNj ).

We modify the equations for updating the messages ρ, β and also derive σ and τ to take into account this additional constraint. Following the max-sum message update rule from a variable node to a factor node (cf., eq. 2.4 in Chapter 8 of (Bishop 2006)), the message update formulas for ρ, β and σ are simply:
to consider two cases: i = j and i 6= j, i.e., the τ message to the nodes on the diagonal and τ for the others. For simplicity, we also assume that all leaf nodes have their index numbers less than any roots. Let L be a number of leaf nodes. Hence, leaf node indices run from 1 to L.

$$\rho_{ij}=S(i,j)+\eta_{ij}+\tau_{ij},\tag{3}$$ $$\beta_{ij}=S(i,j)+\alpha_{ij}+\tau_{ij},$$ (4) $$\sigma_{ij}=S(i,j)+\alpha_{ij}+\eta_{ij}.\tag{5}$$  For deriving the message update equation for $\tau$, we have 
For the case i = j (for the diagonal nodes cjj ), we have to consider the update message for τ in two possible settings:
cjj = 1 and cjj = 0 (or, they can be written as τjj (1) and τjj (0) respectively), and then find the best configuration for these settings. Following the max-sum message update rule from a factor node to a variable node (cf., eq. 2.5 in Chapter 8 of (Bishop 2006), when cjj = 1:

$$\tau_{j j}(1)=\operatorname*{max}_{\mathbb{S}^{j}}\{\sum_{k\in\mathbb{S}^{j};k\neq j}\sigma_{k j}(1)+\sum_{l\not\in\mathbb{S}^{j};l\neq j}\sigma_{l j}(0)\}.$$  For $c_{j j}=0$, we have 

$$(6)$$
$$\tau_{jj}(0)=\sum_{k=1:L;k\neq j}\{\sigma_{kj}(0)\},\tag{7}$$

where S
j ∈ T; T ⊃ {1, · · · , L}; j ∈ S
jand all k in S
jshares the same parent exemplar. Eq. (6) will favor the "valid" configuration (the assignments of ckj ), which maximizes the summation of all incoming messages to the factor node Fj .

For Eq. (7), since no other nodes can belong to j, the valid configuration is simply setting all ckj to 0. Note that we omit Fj from the above equations since invalid configurations are not very optimal, so that they will never be chosen. Thus, Fj is always 0.

From Eq. (6) and Eq. (7), the scalar message τjj is simply:

$$\begin{array}{l}{{\tau_{1}(k)\,\tau_{2}=\tau_{1}(k)\,\tau_{2}(k)\,\tau_{3}(k)\,\tau_{4}(k)}}\\ {{\tau_{j j}=\operatorname*{max}\left\{\begin{array}{l l}{{\operatorname*{max}_{\mathbf{S}^{j}}\sum_{k\in\mathbf{S}^{j},k\neq j}\sigma_{k j}}}\\ {{0}}\end{array}\right.}}\end{array}$$
$$({\mathfrak{s}})$$
$${\mathrm{(9)}}$$

For i 6= j, we also have to consider two sub cases in the same way as to the previous setting, when cij = 1:

when $c_{ij}=1$:  $\tau_{ij}(1)=\underset{\mathbb{S}^{j}}{\max}\{\sum_{k\in\mathbb{S}^{j};k\neq i}\sigma_{kj}(1)+\sum_{l\notin\mathbb{S}^{j};l\neq i}\sigma_{lj}(0)\}.$  For $c_{ij}=0$, we have 

$$\pi_{ij}(0)=\max_{S}\{\sum_{k\in S;k\neq i}\sigma_{kj}(1)+\sum_{l\notin S;l\neq i}\sigma_{lj}(0)\},\tag{10}$$

where S ∈ T; T ⊃ {1, · · · , L}, and all k in S shares the same parent exemplar without the restriction that S must contain j. In particular, the best configuration may or may not have j as the exemplar, which is different from the cij = 1 case that requires the best configuration necessarily having j as the exemplar.

The scalar message τij , which is a difference between τij (1) (Eq. (9)) and τij (0) (Eq. (10)) is as follows:

$$\tau_{ij}=\sum_{k\in\mathbb{S}^{j};k\neq i}\sigma_{kj}-\sum_{l\notin\mathbb{S};l\neq i}\sigma_{lj}.\tag{11}$$

The inference of exemplars and cluster assignments starts by initializing all messages to zero and keeps updating all messages for each nodes iteratively until convergence. One possible way to determine the convergence is to monitor the stability of the net similarity value, Pi,j Sij (cij ), as in the original AP.

Recovering MAP exemplars and cluster assignments can be done as in the original AP with one extra step, in order to