Submodular Variational Inference for Network Reconstruction

In real-world and online social networks, individuals receive and transmit information in real time. Cascading information transmissions (e. g. phone calls, text messages, social media posts) may be understood as a realization of a diffusion process operating on the network. The process only traverses and thereby reveals a limited portion of the edges. The network reconstruction/inference problem is to estimate the unrevealed connections. Most existing approaches derive a likelihood and attempt to find the network topology maximizing the likelihood, yielding a highly intractable problem. In this paper, we focus on the network reconstruction problem for a broad class of real-world diffusion processes, exemplified by a network diffusion scheme called respondent-driven sampling (RDS). We prove that under realistic and general models of network diffusion, the posterior distribution of an observed RDS realization is a Bayesian logsubmodular model. We then propose V INE, a novel, accurate, and computationally efficient variational inference algorithm, for the network reconstruction problem under this model. Crucially, we do not assume any particular probabilistic model for the underlying network. V INE recovers any connected graph with high accuracy as shown by our experimental results on real-life networks.

Authors

• Lin Chen 0003
• Forrest W. Crawford
• Amin Karbasi

Keywords

No keywords are indexed for this paper.