Reconstructing Parameters of Spreading Models from Partial Observations
Spreading processes are often modelled as a stochastic dynamics occurring on top of a given network with edge weights corresponding to the transmission probabilities. Knowledge of veracious transmission probabilities is essential for prediction, optimization, and control of diffusion dynamics. Unfortunately, in most cases the transmission rates are unknown and need to be reconstructed from the spreading data. Moreover, in realistic settings it is impossible to monitor the state of each node at every time, and thus the data is highly incomplete. We introduce an efficient dynamic message-passing algorithm, which is able to reconstruct parameters of the spreading model given only partial information on the activation times of nodes in the network. The method is generalizable to a large class of dynamic models, as well to the case of temporal graphs.
The paper deals with the problem of diffusion graph weighting, from activity data observed from the studied networks. More specifically, it focus on an adaptation of NetRate (which corresponds to an extension of the Independent Cascade model with  delays of infection, here in the discrete case, following a geometric law on these  transmission delays) to the case where only the activity of a subset of the nodes of the network can be monitored. The claim is that non observed nodes shouldn't be ignored when learning the transmission probabilities of the diffusion graph.     
Very interesting and well written paper, which deals with an important problem when learning diffusion models: it may be impossible to observe the activity of every node of the network. For instance, if the source is Twitter, the streaming API only allows one to monitor the activity of about 4000 users over several millions.   The proposed approach is elegant and well sounded. I enjoyed to review this paper that brought me new knowledge about learning in such complex situations. The proposal is maybe not too much innovative since it mostly employs already published techniques, but from my point of view the followed methodology deserves to be published in some main machine learning venue, at least for its pedagogical aspect. Moreover, a good theoretical analysis of the algorithm is given for the case of tree network  structures.    I have two concerns about the applicability of the method in real-world scenarios:      - The model is based (as NetRate and a lot of other models) on the hypothesis that the earlier a node is infected the more likely it is to be. This is induced by the fact that a single parameter controls the activation probability and the time of this activation. In such models, the non-infected nodes are usually considered as infected at a horizon time T. My experience is that this parameter $T$ has a very great impact on the results and is very difficult to tune. However, considering asynchronous diffusion models such as Saito's ones leads to greatly more complex likelihood formulations. I do not know if the present work could be transposed in such a setting.        - The model considers a geometric law for the time delays of transmission between nodes. This is a strong assumption about the regularities on transmission dynamics that may not hold in  real life.   Three questions/coments about the experiments:      - What is the MonteCarlo method used for HTS ? From my point of view this should be an MCMC, such as Gibbs Sampling, since it has to consider activation times of observed infected nodes.     - How are generated the cascades from the real world graph? Using a IC model with a geometric law on diffusion delays as considered in the paper ? I regret that real "real world" data have not been used here, as this does not allow to assess the model for real life tasks...     - Only very small networks have been considered here. It would be nice to experiment it on greatly larger networks to assess how it scales  For me the paragraph "missing information in time" should be removed since it presents very few interest: it appears as obvious that the algorithm can be easily adapted with a different discretization of the time. At least, it should be reworked (I spent more time to understand this small paragraph than the whole rest of the paper!):    - what is the difference between $\cal K$ and k here ? For me, $k$ should be used in place of $\cal K$ everywhere    - for me $\delta_k$ should be noted $\delta_i^c$, it is the interval in which $\tau_i^c$ is included. Then, it would allow one to skip the indicator function in the following equations, by giving $\Delta_{k_i^c}$ that would be more clear     - line 215: the upperbound of $\tau_i^c$ should be $\tau^{k+1}$ rather than $\tau^{k}$   - Last but not least: I do not understand why non-infections are ignored here. It is claimed that, provided the final time T is not included in the observations, the second term of (9) can be ignored. I disagree with this: every non infected node at the end of the last observed step should be considered as not infected. Thus, a term $P_S^i$ should be given for them. Else, every probability is likely to be greatly over-estimated.. No ?     Minor comments:     - "Using expression (11)" line 199 is somewhat misleading (at least it confused me a little for the comprehension of the proof). From my point of view, it would be more clear without this indication.     - Formula (9): \leq T-1 rather than \leq T in the first term, no ? (or strict inequality)    - Line 75: "the its"    - Formula 4 : I have some problems with the notation of the sum. For me the subscript notation for "each possible set of hidden activation times" is not correct here.     - I would add a $\cal O$ as a subscript of \Sigma in formula (9)       - Line 282: overestimated => underestimated (and if I am right the opposite operation line 280)