Supervised Belief Propagation: Scalable Supervised Inference on Attributed Networks


Given an undirected network where some of the nodes are labeled, how can we classify the unlabeled nodes with high accuracy? Loopy Belief Propagation (LBP) is an inference algorithm widely used for this purpose with various applications including fraud detection, malware detection, web classification, and recommendation. However, previous methods based on LBP have problems in modeling complex structures of attributed networks because they manually and heuristically select the most important parameter, the propagation strength. In this paper, we propose Supervised Belief Propagation (SBP), a scalable and novel inference algorithm which automatically learns the optimal propagation strength by supervised learning. SBP is generally applicable to attributed networks including weighted and signed networks. Through extensive experiments, we demonstrate that SBP generalizes previous LBP-based methods and outperforms previous LBP and RWR based methods in real-world networks.



The codes used in the paper are available. [Download]


Epinions-R189,0281,152,005 Heterogeneous network Trustlet Link
Epinions-S131,828841,372 Signed social network SNAP Link
MovieLens9,9401,000,209 Bipartite review network GroupLens Link


  • Jaemin Yoo (Seoul National University)
  • Saehan Jo (Seoul National University)
  • U Kang (Seoul National University)