Nonbacktracking Bounds on the Influence in Independent Cascade Models
This paper develops upper and lower bounds on the influence measure in a network, more precisely, the expected number of nodes that a seed set can influence in the independent cascade model. In particular, our bounds exploit nonbacktracking walks, Fortuin-Kasteleyn-Ginibre type inequalities, and are computed by message passing algorithms. Nonbacktracking walks have recently allowed for headways in community detection, and this paper shows that their use can also impact the influence computation. Further, we provide parameterized versions of the bounds that control the trade-off between the efficiency and the accuracy. Finally, the tightness of the bounds is illustrated with simulations on various network models.
The paper develops upper and lower bounds, using correlation inequalities, on the value of the influence function (expected influenced set size) under the Independent Cascade model. The work is a clear improvement on the upper bounds of Lemonnier et al., NIPS 2014. The theoretical results are a solid contribution towards a bound-based analysis of influence computation and maximization, though the evaluation could be improved to better evaluate and communicate the impact of the results. 
1) As future work building on this line of bounds, It would be interesting to see work connecting them to actual influence maximization, e.g. running a greedy IM procedure, and comparing the seed sets under greedy IM vs. seed sets returned by greedy maximization over the UB or LB measures. It would have been nice to see some dialogue with maximization as part of the work, but it would have been difficult to fit into the short format.
2) In the Experimental Results (Section 4), it would be preferable to see the evaluation decomposed over the two main sources of randomness being studied, the graph and the seed node {s]. It would be interesting to dig into properties of the seed nodes for which the bounds are tighter or looser (degree? Centrality? etc.) It would also be preferable to see an evaluation of larger seed sets, as part of the difficulty with computing influence is interactions between seed nodes.
3) An obvious omission is the study of real world graphs, which have higher degrees and contain many more triangles than any of the simulated graphs considered in the paper. The higher degrees make backtracking steps in random walks less frequent. The triangles and other cycles generally impede message passing algorithms. It’d be worth evaluating and commenting on these considerations. 
4) The state of the art for fast IM computation with approximation guarantees is, I believe, (Tang-Xiao-Shi, SIGMOD 14). Worth including in the citations to IM papers. Furthermore, the use of the word “heuristic” on Line 20 is usually reserved for algorithms without formal guarantees. The methods in the citation block [10, 17, 3, 7, 20] almost all feature formal guarantees for IM in terms of worst-case approximation ratios (some in probabilistic senses). To call all these papers “heuristic” feels overly dismissive. As a related comment on the literature review, on Line 32 "A few exceptions include” makes it sound like there is going to be more than one exception, but only one is given. Fine to rewrite to only expect on exception, better to give more cites.