{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T05:29:45Z","timestamp":1772774985560,"version":"3.50.1"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>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?<\/jats:p>\n          <jats:p>\n            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)\n            <jats:italic>Generality<\/jats:italic>\n            : It works on heterogeneous graphs with multiple types of nodes and edges; (2)\n            <jats:italic>Closed-form solution:<\/jats:italic>\n            ZooBP gives a closed-form solution as well as convergence guarantees; (3)\n            <jats:italic>Scalability:<\/jats:italic>\n            ZooBP is linear on the graph size and is up to 600\u00d7\n            <jats:italic>faster<\/jats:italic>\n            than BP, running on graphs with\n            <jats:italic>3.3 million edges<\/jats:italic>\n            in a few seconds. (4)\n            <jats:italic>Effectiveness:<\/jats:italic>\n            Applied on real data (a F\n            <jats:sc>lipkart<\/jats:sc>\n            e-commerce network with users, products and sellers), ZooBP identifies fraudulent users with a near-perfect precision of\n            <jats:italic>92.3 %<\/jats:italic>\n            over the top 300 results.\n          <\/jats:p>","DOI":"10.14778\/3055540.3055554","type":"journal-article","created":{"date-parts":[[2017,3,15]],"date-time":"2017-03-15T14:27:29Z","timestamp":1489588049000},"page":"625-636","source":"Crossref","is-referenced-by-count":41,"title":["ZooBP"],"prefix":"10.14778","volume":"10","author":[{"given":"Dhivya","family":"Eswaran","sequence":"first","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephan","family":"G\u00fcnnemann","sequence":"additional","affiliation":[{"name":"Technical University of Munich"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos","family":"Faloutsos","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Disha","family":"Makhija","sequence":"additional","affiliation":[{"name":"Flipkart, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohit","family":"Kumar","sequence":"additional","affiliation":[{"name":"Flipkart, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,1]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"2","volume-title":"ICWSM","author":"Akoglu L.","year":"2013","unstructured":"L. Akoglu , R. Chandy , and C. Faloutsos . Opinion fraud detection in online reviews by network effects . In ICWSM , pages 2 -- 11 , 2013 . L. Akoglu, R. Chandy, and C. Faloutsos. Opinion fraud detection in online reviews by network effects. In ICWSM, pages 2--11, 2013."},{"key":"e_1_2_1_2_1","volume-title":"Schaum's outline of theory and problems of matrices","author":"Ayres F.","year":"1962","unstructured":"F. Ayres . Schaum's outline of theory and problems of matrices . McGraw-Hill , 1962 . F. Ayres. Schaum's outline of theory and problems of matrices. McGraw-Hill, 1962."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339726"},{"key":"e_1_2_1_4_1","volume-title":"Transductive Inference and Semi-Supervised Learning","author":"Chapelle O.","unstructured":"O. Chapelle , B. Sch\u00f6lkopf , and A. Zien . Transductive Inference and Semi-Supervised Learning . MIT Press . O. Chapelle, B. Sch\u00f6lkopf, and A. Zien. Transductive Inference and Semi-Supervised Learning. MIT Press."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/9780262033589.001.0001","volume-title":"Semi-supervised learning","author":"Chapelle O.","year":"2006","unstructured":"O. Chapelle , B. Sch\u00f6lkopf , A. Zien , Semi-supervised learning . 2006 . O. Chapelle, B. Sch\u00f6lkopf, A. Zien, et al. Semi-supervised learning. 2006."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1978942.1978967"},{"key":"e_1_2_1_7_1","first-page":"165","volume-title":"UAI","author":"Elidan G.","year":"2006","unstructured":"G. Elidan , I. McGraw , and D. Koller . Residual belief propagation: Informed scheduling for asynchronous message passing . UAI , pages 165 -- 173 , 2006 . G. Elidan, I. McGraw, and D. Koller. Residual belief propagation: Informed scheduling for asynchronous message passing. UAI, pages 165--173, 2006."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-006-7899-4"},{"key":"e_1_2_1_9_1","article-title":"Reduced complexity iterative decoding of low-density parity check codes based on belief propagation","author":"Fossorier M. P.","unstructured":"M. P. Fossorier , M. Mihaljevic , and H. Imai . Reduced complexity iterative decoding of low-density parity check codes based on belief propagation . IEEE Transactions on communications, pages 673--680. M. P. Fossorier, M. Mihaljevic, and H. Imai. Reduced complexity iterative decoding of low-density parity check codes based on belief propagation. IEEE Transactions on communications, pages 673--680.","journal-title":"IEEE Transactions on communications, pages 673--680."},{"key":"e_1_2_1_10_1","first-page":"482","volume-title":"Allerton Conference on Communications, Control and Computing","author":"Frey B. J.","year":"1996","unstructured":"B. J. Frey and F. R. Kschischang . Probability propagation and iterative decoding . In Allerton Conference on Communications, Control and Computing , pages 482 -- 493 , 1996 . B. J. Frey and F. R. Kschischang. Probability propagation and iterative decoding. In Allerton Conference on Communications, Control and Computing, pages 482--493, 1996."},{"key":"e_1_2_1_11_1","volume-title":"ar Xiv preprint arXiv:1502.04956","author":"Gatterbauer W.","year":"2015","unstructured":"W. Gatterbauer . The linearization of pairwise markov networks. ar Xiv preprint arXiv:1502.04956 , 2015 . W. Gatterbauer. The linearization of pairwise markov networks. ar Xiv preprint arXiv:1502.04956, 2015."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735490"},{"key":"e_1_2_1_13_1","first-page":"271","volume-title":"The vec-permutation matrix, the vec operator and kronecker products: A review. Linear and multilinear algebra","author":"Henderson H. V.","year":"1981","unstructured":"H. V. Henderson and S. R. Searle . The vec-permutation matrix, the vec operator and kronecker products: A review. Linear and multilinear algebra , pages 271 -- 288 , 1981 . H. V. Henderson and S. R. Searle. The vec-permutation matrix, the vec operator and kronecker products: A review. Linear and multilinear algebra, pages 271--288, 1981."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014125"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/2034117.2034134"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.909166"},{"key":"e_1_2_1_17_1","first-page":"467","volume-title":"UAI","author":"Murphy K. P.","year":"1999","unstructured":"K. P. Murphy , Y. Weiss , and M. I. Jordan . Loopy belief propagation for approximate inference: An empirical study . In UAI , pages 467 -- 475 , 1999 . K. P. Murphy, Y. Weiss, and M. I. Jordan. Loopy belief propagation for approximate inference: An empirical study. In UAI, pages 467--475, 1999."},{"key":"e_1_2_1_18_1","first-page":"13","volume-title":"AAAI Workshop on Learning Statistical Models from Relational Data","author":"Neville J.","year":"2000","unstructured":"J. Neville and D. Jensen . Iterative classification in relational data . In AAAI Workshop on Learning Statistical Models from Relational Data , pages 13 -- 20 , 2000 . J. Neville and D. Jensen. Iterative classification in relational data. In AAAI Workshop on Learning Statistical Models from Relational Data, pages 13--20, 2000."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242600"},{"key":"e_1_2_1_20_1","first-page":"133","volume-title":"AAAI","author":"Pearl J.","year":"1982","unstructured":"J. Pearl . Reverend bayes on inference engines: A distributed hierarchical approach . In AAAI , pages 133 -- 136 , 1982 . J. Pearl. Reverend bayes on inference engines: A distributed hierarchical approach. In AAAI, pages 133--136, 1982."},{"key":"e_1_2_1_21_1","volume-title":"Morgan Kaufmann","author":"Pearl J.","year":"2014","unstructured":"J. Pearl . Probabilistic reasoning in intelligent systems: networks of plausible inference . Morgan Kaufmann , 2014 . J. Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufmann, 2014."},{"key":"e_1_2_1_22_1","volume-title":"Siam","author":"Saad Y.","year":"2003","unstructured":"Y. Saad . Iterative methods for sparse linear systems . Siam , 2003 . Y. Saad. Iterative methods for sparse linear systems. Siam, 2003."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2003.1206509"},{"key":"e_1_2_1_24_1","volume-title":"Fast random walk with restart and its applications","author":"Tong H.","year":"2006","unstructured":"H. Tong , C. Faloutsos , and J.-Y. Pan . Fast random walk with restart and its applications . 2006 . H. Tong, C. Faloutsos, and J.-Y. Pan. Fast random walk with restart and its applications. 2006."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974348.58"},{"key":"e_1_2_1_26_1","first-page":"236","volume-title":"Understanding belief propagation and its generalizations","author":"Yedidia J. S.","year":"2003","unstructured":"J. S. Yedidia , W. T. Freeman , and Y. Weiss . Understanding belief propagation and its generalizations . pages 236 -- 239 . 2003 . J. S. Yedidia, W. T. Freeman, and Y. Weiss. Understanding belief propagation and its generalizations. pages 236--239. 2003."},{"key":"e_1_2_1_27_1","volume-title":"Citeseer","author":"Zhu X.","year":"2002","unstructured":"X. Zhu and Z. Ghahramani . Learning from labeled and unlabeled data with label propagation. Technical report , Citeseer , 2002 . X. Zhu and Z. Ghahramani. Learning from labeled and unlabeled data with label propagation. Technical report, Citeseer, 2002."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3055540.3055554","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:12:15Z","timestamp":1672225935000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3055540.3055554"}},"subtitle":["belief propagation for heterogeneous networks"],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":27,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.14778\/3055540.3055554"],"URL":"https:\/\/doi.org\/10.14778\/3055540.3055554","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}