Summary: In real-world and online social networks, individuals receive and transmit information in real time. Cascading information transmissions – phone calls, text messages, social media posts – may be understood as a realization of a diffusion process operating on the network, and its branching path can be represented by a directed tree. One important feature of dynamic real-world diffusion processes is that the process may not traverse every edge in the network on which it operates. When the network itself is unknown, the path of the diffusion process may reveal some, but not all, of the edges connecting nodes that have received the diffusing information. The network reconstruction/inference problem is to estimate connections that are not revealed by the diffusion processes. This problem naturally arises in many disciplines. Most existing approaches to network reconstruction derive a likelihood function for the realized diffusion process given full knowledge of the network on which it operates, and attempt to find the network topology that maximizes this likelihood. The major challenge in this work is the intractability of the optimization problem. In this seminar, 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) that is widely used in epidemiology. We prove that under a reasonable model of network diffusion, the likelihood of an observed RDS realization is a Bayesian log-submodular model. We propose a novel, accurate, and computationally efficient variational inference algorithm for the network reconstruction problem under this model. In this algorithm, we allow for more flexibility for the possible deviation of the subjects’ reported total degrees in the underlying graphical structure from the true ones. Experimental results show this algorithm achieves very high reconstruction accuracy.