Carnegie Mellon University, 2015
$$\hat{\mathbf{b}}_t = \hat{\mathbf{H}}^k \sum_{p \in P_t^k} w_p\hat{\mathbf{e}}_p$$
where
The main memory implementation of LinBP is up to 600 times faster than BP, and the SQL implementation of SBP is more than 10 times faster than LinBP.
SBP needs fewer iterations to converge and requires fewer calculations for each iteration, on average.
In the experiments, it was faster to update SBP when less than $\approx$ 50% of the final explicit beliefs are new.
BP, LinBP, LinBP$^∗$, and SBP give almost identical top belief assignments (depending on $\epsilon_H$). However, ties can drop the quality of SBP to $\leq$ 95%.
Goal: propagate multi-class heterophily from labels
Problem: How to solve BP convergence issues ☹
Solution: Center & linearize BP ⇒ convergence & speed 🙂
Linearized Belief Propagation (LinBP): Matrix Algebra, convergence, closed-form SQL (w/ recursion) with standard aggregates
Single-pass Belief Propagation (SBP) Myopic version, incremental updates