Dynamic Network Model from Partial Observations
Can evolving networks be inferred and modeled without directly observing their nodes and edges? In many applications, the edges of a dynamic network might not be observed, but one can observe the dynamics of stochastic cascading processes (e.g., information diffusion, virus propagation) occurring over the unobserved network. While there have been efforts to infer networks based on such data, providing a generative probabilistic model that is able to identify the underlying time-varying network remains an open question. Here we consider the problem of inferring generative dynamic network models based on network cascade diffusion data. We propose a novel framework for providing a non-parametric dynamic network model-based on a mixture of coupled hierarchical Dirichlet processesbased on data capturing cascade node infection times. Our approach allows us to infer the evolving community structure in networks and to obtain an explicit predictive distribution over the edges of the underlying network-including those that were not involved in transmission of any cascade, or are likely to appear in the future. We show the effectiveness of our approach using extensive experiments on synthetic as well as real-world networks.
Existing models, however, aim to model a fully observed network [4,5,8,9] but in many realworld problems, the underlying network structure is not known. What is often known are partial observations of a stochastic cascading process that is spreading over the network. A cascade is created by a contagion (e.g., a social media post, a virus) that starts at some node of the network and then spreads like an epidemic from node to node over the edges of the underlying (unobserved) network. The observations are often in the form of the times when different nodes get infected by different contagions. A fundamental problem, therefore, is to infer the underlying network structure from these partial observations. In recent years, there has been a body of research on inferring diffusion networks from node infection times. However, these efforts mostly rely on a fixed cascade transmission model-describing how nodes spread contagions-to infer the set of most likely edges [2,10,11,12]. More recently, there have been attempts to predict the transmission probabilities from infection times, either by learning node representations [13], or by learning diffusion representations using the underlying network structure [13,14,15]. However, it remains an open problem to provide a generative probabilistic model for the underlying network from partial observations.
Here we propose a novel online dynamic network inference framework, DYFERENCE, for providing non-parametric edge-exchangeable network models from partial observations. We build upon the non-parametric network model of [8], namely MDND, that assumes that the network clusters into groups and then places a mixture of Dirichlet processes over the outgoing and incoming edges in each cluster while coupling the network using a shared discrete base measure. However, our framework is easily extended to arbitrary generative models replacing the MDND with other choices of latent representations, such as network models presented in [9,16,17,18]. Given a set of cascades spreading over the network, we process observations in time intervals. For each time interval we first find a probability distribution over the cascade diffusion trees that may have been involved in each cascade. We then calculate the marginal probabilities for all the edges involved in the diffusion trees. Finally, we sample a set of edges from this distribution and provide the sampled edges to a Gibbs sampler to update the model variables. In the next iteration, we use the updated edge probabilities provided by the model to update the probability distributions over edges supported by each cascade. We continue the above iterative process until the model does not change considerably. Extensive experiments on synthetic and real-world networks show that DYFERENCE is able to track changes in the structure of dynamic networks and provides accurate online estimates of the time-varying edge probabilities for different network topologies. We also apply DYFERENCE for diffusion prediction and predicting the most influential nodes in Twitter and MemeTracker datasets, as well as bankruptcy prediction in a financial transaction network.
The authors propose a framework for modeling dynamic network cascade diffusion and contrast the approach in particular to InfoPath but also several more recent static network estimation procedures. The model is probabilistic and extends the work of Williams (ref 7) to cascade diffusion by learning the latent network structure solely based on the nodes observed contamination times within a cascade. The framework uses the partial observational framework discussed in ref 27 and inference of determinantal point processes as discussed in ref 28 in order to establish a distribution of plausible edges given the observed cascades. The MDMN model of ref 7 is then used as a latent representation of this unobserved network representation. The framework is extended to the modeling of dynamic networks considering a time interval w and updating the model at time t+1 using the model at time t as a starting point.   Quality: The manuscript is well written, the experimentation solid, and the approach well motivated improving upon current state-of-the-art of network quantification based on observed cascades.  Clarity: The manuscript is generally well written and well rooted in the existing literature. There are a few typos that should be corrected, i.e. “is the |Rk x Rk| is the restriction…” -> “is the |Rk x Rk| restriction…” “and and” -> “and” I would further recommend that the section “Related Work” be integrated into the existing introduction as there are quite some overlaps between the introduction and related work section. In particular, remarks such as “Our work is different in nature to the existing methods in that we aim at providing a generative probabilistic  model for the underlying dynamic network from diffusion data.” and “However, these models assume that networks are fully observed. In contrast, our work here considers the network is unobserved but what we observe are node infection times of a stochastic cascading process spreading over the network.” These points are already remarked in the introduction also discussing some of the current state of the art. It could on related work also be worth mentioning probabilistic generative dynamic models assuming fully observed networks, see for instance as part of the related work Ishiguro, Katsuhiko, et al. "Dynamic infinite relational model for time-varying relational data analysis." Advances in Neural Information Processing Systems. 2010.  Originality: The novelty of the paper is combining the use of latent network modeling based on the mixture of   Dirichlet network distributions (MDND) modeling framework ref 7 to operate not directly on an observed network but a latent network defined though cascades using results from ref. 27 and 28 in order to define a distribution over latent edges. In ref 7 the MDND was established as a competitive link-prediction framework and it is thus reasonable to use this as a starting point of latent variable modeling of the network structure. However, other competitive probabilistic link prediction modeling approaches choices could also have been relevant choices, such as:  Palla, Konstantina, David Knowles, and Zoubin Ghahramani. "An infinite latent attribute model for network data." arXiv preprint arXiv:1206.6416 (2012). And within the framework of Fox and Carron the extension to modeling block structure Herlau, Tue, Mikkel N. Schmidt, and Morten Mørup. "Completely random measures for modelling block-structured sparse networks." Advances in Neural Information Processing Systems. 2016. It would improve the paper to discuss how the present framework extends to arbitrary generative models replacing the MDND with other choices of latent representations which would expand the scope of the present framework. That being said there are many merits of the MDND and this is a sound and strong starting point. Combining generative network models for modeling cascades is an interesting and useful novel contribution.  Significance: The proposed framework is a fine extension of the MDND framework to the modeling of network structure based on observed cascades and form a new and powerful tool for analyzing network dynamics. In particular, the experimental results emphasizes the utility of the proposed framework outperforming existing approaches while providing a nice probabilistic generative modeling framework for the extraction of dynamic network structure.  It is unclear to me why the network needs to be discretized in time segments w as the cascades are in continuous time. Furthermore, the dynamic modeling stemming from updating the model from previous timesteps seem a bit heuristic and to hinge on how much the sampling procedure changes the model across the time steps which in turn also reflect the ability of the sampler to properly mix and for how long the inference procedure is run (i.e., how many samples are drawn at each time step). It would improve the manuscript to clarify these aspects. It would also be good to include a discussion of the stability of the inferred parameters and thus reliability of the inference procedure. Furthermore, it would be good to clarify how the predictions are made, i.e. InfoPath rely on point estimates but the current procedure I assume is based on averaging samples. This should be clarified, and if averaging samples it would be good to also demonstrate what the performance of a corresponding point estimate (by highest likelihood sample) would provide to assess the merits of simply providing Bayesian averaging as compared to a more advanced MDND model.  I have read the authors rebuttal and find that they satisfactorily discuss the raised concerns. I argue for accepting this paper.