Linearized and Single-Pass Belief Propagation
Wolfgang Gatterbauer
Business Technologies and Computer Science
Carnegie Mellon University
Friday, April 1, 2016
10:30am
EBII 3211 — NCSU Centennial Campus
(Directions to Centennial campus and parking information)
This talk is part of the Taming the Data invited-speaker series, held in the Department of Computer Science at NC State University.
Talk Title: Linearized and Single-Pass Belief Propagation
Talk abstract:
How can we tell when accounts are fake or real in a social network? And how can we tell which accounts belong to liberal, conservative or centrist users? Often, we can answer such questions and label nodes in a network based on the labels of their neighbors and appropriate assumptions of homophily (“birds of a feather flock together”) or heterophily (“opposites attract”). One of the most widely used methods for this kind of inference is Belief Propagation (BP) which iteratively propagates the information from a few nodes with explicit labels throughout a network until convergence. A well-known problem with BP, however, is that there are no known exact guarantees of convergence in graphs with loops.
This talk describes Linearized Belief Propagation (LinBP), a linearization of BP that allows a closed-form solution via intuitive matrix equations and, thus, comes with exact convergence guarantees. It handles homophily, heterophily, and more general cases that arise in multi-class settings. Plus, it allows a compact implementation in SQL (Structured Query Language). The talk also proposes Single-pass Belief Propagation (SBP), a “localized” version of LinBP that propagates information across every edge at most once and for which the final class assignments depend only on the nearest labeled neighbors. In addition, SBP allows fast incremental updates in dynamic networks. Our experiments show that LinBP and SBP are leading to similar node labels while being by orders of magnitude faster than standard BP.
(Talk based on joint work with Stephan Günnemann, Danai Koutra, and Christos Faloutsos from VLDB 2015.)
About the speaker:
Wolfgang Gatterbauer is an Assistant Professor in Business Technologies and Computer Science at CMU. His main research focus is on scalable approaches to inference over large and uncertain data. He got his PhD in Computer Science from Vienna University of Technology and then did a Post-Doc in the Database group at University of Washington. In earlier times, he won a Bronze medal at the International Physics Olympiad, worked in the steam turbine development department of ABB Alstom Power, and in the German office of McKinsey & Company.
This invited-speaker series has been made possible thanks to generous support from:
Please send your comments to Rada Chirkova