
Submitted by Assigned_Reviewer_6
Q1: Comments to author(s). First provide a summary of the paper, and then address the following criteria: Quality, clarity, originality and significance. (For detailed reviewing guidelines, see http://nips.cc/PaperInformation/ReviewerInstructions)
This paper presents a bound on the "influence" from a given (or random) set of nodes on a graph, under a number of popular influence propagation models. The bound is in terms of the largest eigenvalue of the hazard matrix. I read the accompanying proofs and they seem reasonable, although I did not check them completely. The paper compares the bounds to existing bounds in epidemiology and percolation and shows ways in which the new bounds are more general or better. Finally, experimental results are given showing the tightness (or slack) in the bounds for randomly generated networks from a variety of random network models.
The paper appears to have been written in haste and the notation is not as clean as desired. Some quantities (scriptA as an adjacency matrix) are reintroduced. Others (see below) are not given the best notation. The proofs are only given in supplementary material (yet, they are critical to be reviewed and understood and the bulk of the novelty).
The work, if one is interested in such results, is useful, good, and, I believe, correct. While the presentation could be improved, the intellectual contribution is good and worthy of publication.
My main concern (aside from the presentation) is the suitability for the NIPS audience. NIPS has always cast a wide net and this paper may well fall within the net, especially given current trends. However, it relationship to "learning" is nebulous, and the results demonstrate the bound is not close to being tight for preferential attachment networks. I leave this decision to the program committee, however. Personally, I found the paper interesting.
specific comments: pf of Proposition 1: I don't follow equation 13. In particular, I'm uncertain what the notation \rho_c(Z^TZ  n_0) means. \rho_c appears to only apply to A (or at least only to a matrix, if we drop the _c part). Z^TZ  n_0 is a scalar, I think. In general, the steps around this area appear to have been written in a haste and perhaps not presented as well as possible.
Why is \rho_c not something more related to its form, like \rho_H to reminder the reader that the argument is "pushed through" H first?
Corollary 2 uses \rho_c instead of \rho_c(A); I don't think there is a distinction.
Just before Lemma 2: Having H not be the same as H(A) is very confusing. It isn't clear at first why \rho_c(A) is not the same as \rho(H).
In the experimental results, the "preferential attachment" networks are quite far from the bound, and rather random, suggesting that \rho_c(A) is not a good characterization of them. This is a very popular social network model (social networks being the motivating factor of the introduction). Q2: Please summarize your review in 12 sentences
The paper, although it could be presented better, presents new results bounding the influence of propagation in a network. The paper is worthy of publication; my only concern is whether NIPS is the right venue (although I think it probably is). Submitted by Assigned_Reviewer_33
Q1: Comments to author(s). First provide a summary of the paper, and then address the following criteria: Quality, clarity, originality and significance. (For detailed reviewing guidelines, see http://nips.cc/PaperInformation/ReviewerInstructions)
The authors present novel theoretical upper bounds on the total number of nodes that are eventually activated/influenced in the Indepnedent Cascade (IC) model in terms of spectral properties of the "hazard matrix" (defined in terms of the edge probabilities). They first present a worst case bound where the initial influencers are chosen to maximize the influence, and then present an average case bound where the initially influencers are chosen at random. In each case, the bounds demonstrate subcritical and supercritical behavior. In particular, the subcritical regime occurs when the spectral radius of the appropriate matrix is less than one, and gives bounds of O(sqrt(n)) infected nodes in the worst case and O(1) in the average case. The show how their general results can apply to improve results on SIR epidemic models and characterizing giant components in random graphs. They also give results for particular families of graphs and demonstrate the accuracy of their bounds empirically.
The analysis of the paper is sophisticated and rigorous and gives detailed upper bounds that seem to match or beat existing bounds in a number of areas. The paper is wellwritten and clear.
While the flavor of the results is not incredibly surprisingthere are many similar results relating giant components, epidemic spread, etc. to the spectral radius of some matrixthese results are significant because of their tightness, broad applicability, and quality of the analysis. They could potentially have algorithmic significance by providing upper bounds for the influence maximization problem (provided that the upper bounds are tighter than those given by the approximation guarantee of the algorithm).
The paper is atypical for NIPS in that it is a theoretical analysis of a mathematical model without a real algorithmic component. Since it sheds light on models that are actively being researched by the NIPS community and makes interesting connections between those and other models I believe it is within scope.
Comments / questions:
* I believe the statement of Lemma 1 can be strenghtened to say that the distribution of the final set of infected nodes is identical under each of these processes (not just that the marginal probability of each node i being infected is the same).
* I think there is a minor problem with the proof of Lemma 1 in the supplementary material. Eq. (1) gives a system of equations that must be satisfied by the random variables {X_i}, but it does not uniquely define the random process because there are also other solutions to the set of equations. In particular, one can set X_i = 1 for all nodes in some cycle that is *not* reachable from from A and still satisfy these equations. So, showing that all three processes give random variables that satisfy these equations doesn't prove their equivalence. It should be easy to fix the proof, e.g., by using Eq. (8) instead as the characterization of the process.
* The difference between O(sqrt(n)) and O(1) in the subcritical regimes for worst and average cases is interesting. Can you provide any more intuition for this? Are there any other phase transitions in the average case behavior?
* Can you say anything about lower bounds in the supercritical cases?
* The applicability of DTIC to undirected graphs in Lemma 3 was a minor confusion DTIC was defined for directed graphs. The supplementary material makes it clear that this this can be interpreted as DTIC in the bidirected graph where p_{ij} = p_{ji}. Perhaps this can be clarified in the main paper.
* In the experiments, how are the edge probabilities set? What parameter(s) are tuned to vary the spectral radius? More details would help understand the experiments better.
* Is each point in your plots the result of a single simulation or the average over multiple trials? An average over multiple trials would be a cleaner match to your bounds on the expected value. Error bars would also help illustrate the variability. On that note (assuming data points are individual trials), in Figure 3(a) it looks like the variance of the number of infected nodes is higher in the subcritical regime. Can you say anything about this theoretically?
Q2: Please summarize your review in 12 sentences
This is a strong theoretical paper that gives spectral bounds on the expected number of nodes influenced in the Independent Cascade model and demonstrates the applicability of these bounds the SIR model in epidemiology and giant components in random graphs.
Submitted by Assigned_Reviewer_35
Q1: Comments to author(s). First provide a summary of the paper, and then address the following criteria: Quality, clarity, originality and significance. (For detailed reviewing guidelines, see http://nips.cc/PaperInformation/ReviewerInstructions)
Paper Summary: This paper provides new theoretical bounds for the longterm influence of a node under the wellknown independentcascade model (ICM), with applications to different types of networks and with experimental results on simulated networks that confirm the theoretical results.
Quality Note to authors: this paper is somewhat outside my area of expertise, so I apologize for that in advance and as a consequence will keep my comments brief and somewhat high level. In addition I have gives a low weight under "confidence" on the review form so that the reviews of the other reviewers (who are hopefully more informed about the topic) can be given more weight.
With the caveat above, I liked the paper. The problem is of broad interest and the authors appear to do have some interesting new results here. The bounds that they derive appear to be applicable to a fairly wide range of networks (see Section 5) and to provide some nice insights about influence propagation in these different networks. Section 6 on simulation results provides confirmation of the theoretical results across a range of simulated network types: although this section is fairly short this seems fine for a paper that is primarily theoretical in nature.
Originality As far as I can tell the work appears to be original. I like the idea of the hazard matrix, which appears (according to the authors at least) to be novel.
Significance As far as I can tell the paper would appear to have potentially broad impact.
Clarity The paper is wellwritten and clear  it was easily the bestwritten paper in my batch of 4 papers to review (although the bar was set pretty low by the other papers). Q2: Please summarize your review in 12 sentences
The paper appears to be a nice contribution to the set of known theoretical results for influence maximization in network models and would appear to worth considering for acceptance (note however that this is an educated guess on my part). Q1:Author rebuttal: Please respond to any concerns raised in the reviews. There are no constraints on how you want to argue your case, except for the fact that your text should be limited to a maximum of 6000 characters. Note however, that reviewers and area chairs are busy and may not read long vague rebuttals. It is in your own interest to be concise and to the point. We thank the reviewers for their positive evaluation and their useful comments. Our reply to the main points they have raised follows:
1. Improvement of Lemma 1 and its proof:
We agree with Reviewer 33 that the result should be strengthened in the paper “to say that the distribution of the final set of infected nodes is identical under each of these processes”, although we only used the fact that the marginal probabilities are equal in the rest of the paper. We also agree that the proof of Lemma 5 should rely on equation (8) and not equation (1). The arguments in the proof of Lemma 5 actually prove equation (8) for all processes which uniquely defines the infection behavior. We will make this minor correction in the final version of the paper if accepted.
2. Insights on the different behavior between worstcase (O(sqrt(n))) and averagecase behavior (O(1)):
A good example of this behavior is a starshaped network of size n with transition probabilities 1/sqrt(n1). When influence spreads from the central node, the bound in Prop. 1 is tight and gives the true value of influence (see section 5.1): 1+sqrt(n1). However, when influence spreads from a peripheral node, influence is 1+(1/sqrt(n1))*(1+(n2)/sqrt(n1))=2+o(1). Therefore, the overall averagecase influence is O(sqrt(n)/n+1)=O(1). This illustrates the following intuition: when the network is inhomogeneous and contains highly central nodes (e.g. scalefree networks), there will be a significant difference between specifically targeting the most central nodes and random targeting (which will most probably target a peripheral node). A possible experiment in order to validate this behavior would be to compute the worst case influence over preferential attachment networks, instead of targeting a node at random as in our experiments (figures 1 and 3).
3. On lower bounds in the supercritical case:
We have reached the following conclusions: a) upper bounds on influence can rely on global features of the graph: wherever the infection starts, it will not spread to many nodes if the graph is not sufficiently infectious and connected “on average”, b) however, lower bounds depend on the local structure of the zone where the infection starts. For instance, a complete subgraph of size sqrt(n) with nsqrt(n) isolated nodes will have O(1) average influence for any value of rho_c. Therefore, lower bounds usually depend on isoperimetric constants eta(m), that basically control the minimum number of outgoing edges for any subset of at most m nodes in the graph (see e.g (Draief et al., 2006), reference [15] of our paper). But as the cornerstones of our results are Lemmas 8 and 9 which do not easily express with respect to these constants we think that our approach is not suited for the derivation of lower bounds for the supercritical regime.
4. On the possible existence of other phase transitions in the average case behavior:
We think that there should be only one phase transition because, to our knowledge, all results on specific graphs exhibit only one transition (note that the existence of a giant component of size a * N implies an averagecase influence of at least a^2 * N and therefore all results on sizes of giant components can be used here). However, because our results are upper bounds, they only ensure that a phase transition will occur after \rho_c = 1.
5. Precisions about numerical experiments:
a) In our experiments, except for totally connected networks, edge probabilities are set to the same value p for each edge. When p varies from 0 to 1, the spectral radius of the Hazard matrix varies from 0 to +infinity. We thus used the edge probability as a parameter to tune the spectral radius. b) all points of the plots are averages over 100 simulations. We will include this information in the article. For totally connected networks, we did not display all the simulation points, as the purpose of these very particular networks was to show that the bound was tight. We thus restricted to simulation points close to the upper bound, in order to leave space for other network types.
6. Explanation about equation (13):
There is indeed a notation error in the equation. In the righthand side, \rho_c(Z^T Z  n_0) is actually \rho_c(A) * (Z^T Z  n_0). The equation follows from (12) with u_i = 1_{i \notin A} * Z_i and the following steps:
u^T Z = Z^T Z  n_0
u_1 = Z_1n_0
Z^T H u = Z^T H(A) Z since for all i,j, H_ij u_j = H(A)_ij Z_j
Therefore, (12) implies Z^T Z  n_0 <= (Z_1n_0) (1exp((Z^T H(A) Z / (Z_1n_0))) which is the lefthand side of (13). Now Z^T H(A) Z <= \rho_c(A) Z^T Z yields the righthand side.
We agree with the reviewer that this step and others in this area of the paper should be more detailed in order to improve clarity.
7. On misleading notation for H and rho:
We agree that notations could be improved and we shall introduce some slight changes in the revision in order to avoid misinterpretations. In particular, we will take into account the advice of reviewer 6 to use \rho_H instead of \rho_c “to remind the reader that the argument is "pushed through" H first”, for the sake of clarity.
8. About the experimental results for preferential attachment networks:
Our understanding is that our upper bound in Theorem 1 is not highly dependent on the set of influencer nodes, and is rather closer to the maximum influence in the considered network. Thus, inhomogeneous networks with a heavy tailed degree distribution will contain many nodes for which the upper bound will be far from their influence (since peripheral nodes will have a very low influence compared to central nodes). However, some simulation points for preferential attachment networks are close to our bound, which may indicate that the bound is tight for the maximum influence in a network.
 