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, in- dividuals receive and transmit information in real time. Cascading information transmis- sions (e.g. phone calls, text messages, social media posts) may be understood as a realiza- tion of a diffusion process operating on the net- work. 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 maxi- mizing the likelihood, yielding a highly in- tractable problem. In this paper, we focus on the network reconstruction problem for a broad class of real-world diffusion processes, exem- plified by a network diffusion scheme called respondent-driven sampling (RDS). We prove that under realistic and general models of net- work 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 net- work reconstruction problem under this model. Crucially, we do not assume any particular probabilistic model for the underlying net- work. 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, in- dividuals receive and transmit information in real time. Cascading information transmis- sions (e.g. phone calls, text messages, social media posts) may be understood as a realiza- tion of a diffusion process operating on the net- work. 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 maxi- mizing the likelihood, yielding a highly in- tractable problem. In this paper, we focus on the network reconstruction problem for a broad class of real-world diffusion processes, exem- plified by a network diffusion scheme called respondent-driven sampling (RDS). We prove that under realistic and general models of net- work 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 net- work reconstruction problem under this model. Crucially, we do not assume any particular probabilistic model for the underlying net- work. 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, in- dividuals receive and transmit information in real time. Cascading information transmis- sions (e.g. phone calls, text messages, social media posts) may be understood as a realiza- tion of a diffusion process operating on the net- work. 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 maxi- mizing the likelihood, yielding a highly in- tractable problem. In this paper, we focus on the network reconstruction problem for a broad class of real-world diffusion processes, exem- plified by a network diffusion scheme called respondent-driven sampling (RDS). We prove that under realistic and general models of net- work 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 net- work reconstruction problem under this model. Crucially, we do not assume any particular probabilistic model for the underlying net- work. 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