# User Trust Inference in Online Social Networks: A Message Passing Perspective
## 3 The Proposed Model
### Probabilistic Model Inference and Interpretation  
From the above-mentioned model construction, we know that there will be loops in the probabilistic graph if bidirectional trust relations exist. That means if [PERSON] and [PERSON] trust each other, which is common in the real world, then the graph containing only the two users and their trust relationships is no longer a linear-chain or a tree, as shown in Figure 3.  
For the probabilistic model inference, collectively predicting all needed trust relationships from the online social network involves iterating through an exponential number of possible label combinations, and thus requires exponential time. Furthermore, as the probabilistic graph contains loops, and exact inference on such a general graphical model is thus intractable, approximations are employed. We propose to solve the inference problem using the _loopy belief propagation_ (LBP) technique. As a _belief propagation_ (BP) method variant, the LBP is a _message passing_ algorithm but requires a slightly different schedule of message updating rules from the vanilla BP method. It is worth noting that each pairwise structure in the probabilistic graph only connects two random variable nodes, and a unitary structure can be viewed as if there is a dummy node linked to it so that a pseudo-pairwise structure exists. Therefore, we can safely skip the factor graph framework and send messages directly between each pair of nodes connected by an edge. This way of handling message passing is equivalent to the original BP algorithm. We chose to update messages synchronously, i.e., in each time epoch, each pair of nodes exchange messages, if they are connected by an edge. In the iterative message updates, each node's belief is normalized so that the normalized belief approximates the node's marginal probability and is further considered as the new local evidence (also called compatibility or potential) at this node. Similarly, for an edge and the two nodes connected by it, we use the normalized belief of the pairwise structure as its local evidence. In the model inference, passing messages, calculating node/edge beliefs, and updating messages are repeated until message convergence or an allowed maximum number of iterations is reached. When the LBP is done, we normalize each node's belief so that it approximates the node's marginal distribution. Through the marginal probabilities of all possible labels for a selected trustRelation node, the trust relationship indicated by this node can be determined by Equation (1). Such probabilities for the trustRelation node can be further interpreted from the message passing perspective. Let \(m_{ji}\) denote a message sent from node \(i\)'s neighboring node \(j\) to it, \(x_{i}\) be the random variable at node \(i\), and \(\varphi_{i}(x_{i})\) and \(\varphi_{ij}(x_{i},x_{j})\) be the local evidence at node \(i\) (unitary structure) and edge \(\langle i,j\rangle\) (and its connected nodes \(i\) and \(i\), pairwise structure). According to BP, the belief \(b_{i}(x_{i})\) at a node \(i\) before normalization, which will then approximate the variable's marginal probability, is proportional to the product of the local evidence at this node and all the messages coming to it:  
\[b_{i}(x_{i})\propto\varphi_{i}(x_{i})\prod_{j\in N(i)}m_{ji}(x_{i}), \tag{7}\]  
where \(N(i)\) denotes the set of nodes directly neighboring node \(i\). The messages are determined by message update rules as follows,  
\[m_{ji}(x_{i})\leftarrow\sum_{x_{j}}\varphi_{j}(x_{j})\varphi_{ji}(x_{j},x_{i}) \prod_{k\in N(j)\setminus i}m_{kj}(x_{j}). \tag{8}\]  
Analogously to Equation (7), the pairwise belief \(b_{ij}(x_{ij})\) at a pairwise structure will be  
\[b_{ij}(x_{ij})\propto\varphi_{ij}(x_{i},x_{j})\varphi_{i}(x_{i})\varphi_{j}(x _{j})\prod_{k\in N(i)\setminus j}m_{ki}(x_{i})\prod_{k\in N(j)\setminus i}m_{ kj}(y_{j}), \tag{9}\]  
Without loss of generality, we take Figure 5 as an example for the following discussion.