Learnability of Influence in Networks
We show PAC learnability of influence functions for three common influence models, namely, the Linear Threshold (LT), Independent Cascade (IC) and Voter models, and present concrete sample complexity results in each case. Our results for the LT model are based on interesting connections with neural networks; those for the IC model are based an interpretation of the influence function as an expectation over random draw of a subgraph and use covering number arguments; and those for the Voter model are based on a reduction to linear regression. We show these results for the case in which the cascades are only partially observed and we do not see the time steps in which a node has been influenced. We also provide efficient polynomial time learning algorithms for a setting with full observation, i.e. where the cascades also contain the time steps in which nodes are influenced.
The paper studies PAC learnability of three commonly used network influence models, namely linear threshold model, independent cascade model and voter model. The authors study both the fully observed model where the time steps of the influence events are included, and the partial observation model, where only the set of influenced nodes is given. The authors are able to show PAC learnability of the influence models in all the above cases, and polynomial time optimisation for the fully observed linear threshold and independent cascade models and both fully and partial observed voter model. Quality: I think the paper is of a good quality, in sofar I have been able to judge. I could not perform detailed check of the proofs in the supplementary material.Clarity:The paper is readable after some effort. There are some notation and presentation issues which I list below.Originality: The idea of providing the PAC analysis is original and welcomed. The proofrequire considerable insight to come up with as different setups are required (neural network, Vcdim for LT model, covering numbers, log likelihood for IC, regression for voter model), albeit the proof as such use standard tools.Significance: The results are significant, because they provide the learning theoretic justification for the widely studies influence function models. It is also foreseeable that the work can lead to new approaches in studying influence in complex networks. Is it for example possible to analyse the context-sensitive case (Su et al. ICML 2014, pp. 442-450) where the influence depends on the type of stimulus, not just the topology and the initial set?Details:- line 49-53:I don't get the purpose of the footnote. In the following you show that the models are PAC-learnable. Here, you wish to imply that they are hard to learn? You do not return to this kind of analysis later to this footnote is not connected to the rest of the paper. I would use the limited space allowed by NIPS by making your main arguments clear(er). - line 61-76: I am not sure this summary is needed, the contributions are clear, perhaps the space would be better used later- line 69: independent CASCADE model - line 167: You are overloading the subscript of set Y: here Y_t denotes time points, below Y_u denotes a node. This confused me a lot. I would be of great help to the reader if you used some other notation for one of the cases. - line 198: I don't think the subscripts _u should be there on the left-hand side of the equation (or, then I really don't understand) - line 245-246: you ... show ... provably ...=> you prove - line 251: subscripts _u on the left hand side again... - line 253: why does \bar{Y}_u^i need to defined through the union of time points.Isn't it so hat the last time point contains all actives nodes so the union should always equal Y_n^i? Or perhaps I miss something. - line 270: I am not completely satisfied with the description. There is not literature reference to the computational hardness and you do not hint how this is established. Why do sigmoidal activations and back-propagation help in resolving the time-points?- line 416: I would appreciate a literature reference to the standard results