The Importance of Communities for Learning to Influence
We consider the canonical problem of influence maximization in social networks. Since the seminal work of Kempe, Kleinberg, and Tardos [KKT03]  there have been two, largely disjoint efforts on this problem. The first studies the problem associated with learning the generative model that produces cascades, and the second focuses on the algorithmic challenge of identifying a set of influencers, assuming the generative model is known. Recent results on learning and optimization imply that in general, if the generative model is not known but rather learned from training data, no algorithm for influence maximization can yield a constant factor approximation guarantee using polynomially-many samples, drawn from any distribution. In this paper we describe a simple algorithm for maximizing influence from training data. The main idea behind the algorithm is to leverage the strong community structure of social networks and identify a set of individuals who are influentials but whose communities have little overlap. Although in general, the approximation guarantee of such an algorithm is unbounded, we show that this algorithm performs well experimentally. To analyze its performance, we prove this algorithm obtains a constant factor approximation guarantee on graphs generated through the stochastic block model, traditionally used to model networks with community structure.
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. But it’s good work.
- The paper could use a conclusion.
1) The use of “training data” in the title makes it a bit unclear what the paper is about. I actually thought the paper was going to be about something very different, some curious application of IM to understand how training data influences machine learning models in graph datasets. Having read the abstract it made more sense, but the word “training” is only used once beyond the abstract, in a subsection title. It seemed as though the focus on SBMs and community structure deserve mentioning in the title?
2) The SBM is a very simplistic model of “communities,” and it’s important to stay humble about what’s really going on in the theoretical results: the positive results for SBMs in this work hinge on the fact that within communities, SBM graphs are just ER graphs, and the simple structure of these ER graphs is what is powering the results. 
3) With (2) registered as a minor grievance, the empirical results are really quite striking, given that the theoretical analysis assumes ER structure within the communities. It’s also notable that the COPS algorithm really does quite well even graphs from on the BA model, which is far from an SBM. In some sense, the issue in (2) sets up an expectation (at least for me) that COPS won’t "actually work". This is quite intriguing, and suggests that the parts of the analysis relying on the ER structure are not using the strongest properties of it (i.e., something close to the main result holds for models much more realistic than ER). This is a strong property of the work, inviting future exploration.
Minor points:
1) The dichotomous decomposition of the IM literature is a little simplistic, and some additional research directions deserve mention. There has been several recent works that consider IM beyond submwdular cases, notably the “robust IM” work by [HK16] (which this submission cites as focusing on submwdular IM, not wrong) and also [Angell-Schoenebeck, arxiv 2016].
2) Two broken cites in Section 3.1. Another on line 292. And I think I see at least one more. Check cites.
3) The name COPS changes to Greedy-Prune in Section 5 (this reviewer assumes they refer to the same thing). 
4) I really prefer for papers to have conclusions, even if the short NIPS format makes that a tight fit.