Linearized and Single-Pass Belief Propagation

摘要: How can we tell when accounts are fake or real in a social network? And how which belong to liberal, conservative centrist users? Often, answer such questions and label nodes network based on the labels of their neighbors appropriate assumptions homophily ("birds feather flock together") heterophily ("opposites attract"). One most widely used methods for this kind inference is Belief Propagation (BP) iteratively propagates information from few with explicit throughout until convergence. main problem BP, however, that there no known exact guarantees convergence graphs loops. This paper introduces Linearized (LinBP), linearization BP allows closed-form solution via intuitive matrix equations and, thus, comes guarantees. It handles homophily, heterophily, more general cases arise multi-class settings. Plus, it compact implementation SQL. The also Single-pass (SBP), "localized" version LinBP across every edge at once final class assignments depend only nearest labeled neighbors. In addition, SBP fast incremental updates dynamic networks. Our runtime experiments show orders magnitude faster than standard