Reviews: The Importance of Communities for Learning to Influence

This work marries influence maximization (IM) with recent work on submodular optimization from samples. The work salvages some positive results from the wreckage of previous impossibility results on IM from samples, by showing that under an SBM model of community structure in graphs, positive results for IM under sampling are possible with a new algorithm (COPS) that is a new variation on other greedy algorithms for IM. It's surprising that the removal step in the COPS algorithm is sufficient from producing the improvement seen between Margl and COPS in Figure 2 (where Margl sometimes does worse than random). Overall this is a strong contribution to the IM literature. Pros: - Brings IM closer to practical contexts by studying IM under learned influence functions - Gives rigorous analysis of this problem for SBMs - Despite simplicity of SBMs, solid evaluation shows good performance on real data Cons: - The paper is very well written, but sometimes feels like it oversimplifies the literature in the service of somewhat overstating the importance of the paper.