Paper Info
Title
ZooBP: Belief Propagation for Heterogeneous Networks.
Abstract
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 Flipkart 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.
Year
DOI
Venue
2017
10.14778/3055540.3055554
PVLDB
Field
DocType
Volume
Convergence (routing),Data mining,Computer science,Inference,Exploit,Theoretical computer science,Graphical model,Heterogeneous network,Database,Generality,Scalability,Belief propagation
Journal
10
Issue
ISSN
Citations 
5
2150-8097
10
PageRank 
References 
Authors
0.56
13
5
Name
Order
Citations
PageRank
Dhivya Eswaran1274.27
Stephan G眉nnemann283369.26
Christos Faloutsos3279724490.38
Disha Makhija4100.89
mohit kumar5693.19