Submodular Variational Inference for Network Reconstruction

Lin Chen, Forrest W. Crawford, Amin Karbasi
Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, PMLR R15:770-779, 2017.

Abstract

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 log-submodular model. We then propose VINE, 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. VINE recovers any connected graph with high accuracy as shown by our experimental results on real-life networks.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR15-chen17c, title = {Submodular Variational Inference for Network Reconstruction}, author = {Chen, Lin and Crawford, Forrest W. and Karbasi, Amin}, booktitle = {Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence}, pages = {770--779}, year = {2017}, editor = {Elidan, Gal and Kersting, Kristian}, volume = {R15}, series = {Proceedings of Machine Learning Research}, month = {11--15 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r15/main/assets/chen17c/chen17c.pdf}, url = {https://proceedings.mlr.press/r15/chen17c.html}, abstract = {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 log-submodular model. We then propose VINE, 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. VINE recovers any connected graph with high accuracy as shown by our experimental results on real-life networks.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Submodular Variational Inference for Network Reconstruction %A Lin Chen %A Forrest W. Crawford %A Amin Karbasi %B Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2017 %E Gal Elidan %E Kristian Kersting %F pmlr-vR15-chen17c %I PMLR %P 770--779 %U https://proceedings.mlr.press/r15/chen17c.html %V R15 %X 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 log-submodular model. We then propose VINE, 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. VINE recovers any connected graph with high accuracy as shown by our experimental results on real-life networks. %Z Reissued by PMLR on 04 October 2026.
APA
Chen, L., Crawford, F.W. & Karbasi, A.. (2017). Submodular Variational Inference for Network Reconstruction. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R15:770-779 Available from https://proceedings.mlr.press/r15/chen17c.html. Reissued by PMLR on 04 October 2026.

Related Material