Answers are grounded in this paper and cite their sources.
Given a heterogeneous network, with nodes of different types - e.g., products, users and sellers from an online recommendation site like Amazon - and labels for a few nodes ('honest', 'suspicious', etc), can we find a closed formula for Belief Propagation (BP), exact or approximate? Can we say whether it will converge? BP, traditionally an inference algorithm for graphical models, exploits so-called "network effects" to perform graph classification tasks when labels for a subset of nodes are provided; and it has been successful in numerous settings like fraudulent entity detection in online retailers and classification in social networks. However, it does not have a closed-form nor does it provide convergence guarantees in general. We propose ZooBP, a method to perform fast BP on undirected heterogeneous graphs with provable convergence guarantees. ZooBP has the following advantages: (1) Generality : It works on heterogeneous graphs with multiple types of nodes and edges; (2) Closed-form solution: ZooBP gives a closed-form solution as well as convergence guarantees; (3) Scalability: ZooBP is linear on the graph size and is up to 600× faster than BP, running on graphs with 3.3 million edges in a few seconds. (4) Effectiveness: Applied on real data (a F lipkart e-commerce network with users, products and sellers), ZooBP identifies fraudulent users with a near-perfect precision of 92.3 % over the top 300 results.
No takes yet. Share an insight, caveat, or question.
Eswaran et al. (2017) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: