Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The authors propose an efficient algorithm for dynamic influence maximization in the incremental setting where only nodes and edges in the graph can be added over time.  For the fully dynamic setting where the nodes and edges can be deleted as well, they give a hardness result.
main_review: The paper is well-written and easy to follow.  Even as the results for the incremental version are interesting, the incremental setting does not accurately represent a social network.   The result of Wang et. al, 2017 gives a \eps (1 - \beta)/2 approximation by keeping O(log N/\beta) sampled nodes  in a sliding window of size N.  Even as the use of a sliding window in their paper suffers from the same drawback of supporting only additions to the network, they do present an algorithm that looks similar to the algorithm for the dynamic max-k coverage  in this paper.  A clearer comparison with the earlier work will help position this work.

Read the authors' feedback and updating my score slightly higher.  My concerns about the incremental setting still remain.
limitations_and_societal_impact: None.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper provides a theoretical study on the dynamic influence maximization problem, that is finding the top k seed nodes in a social network that has the largest influence spread while the social network is changing (nodes and edges could be added or deleted over time). The paper considers two dynamic models: the incremental model where only node and edge additions are allowed, and fully dynamic model, where both additions and deletions are allowed. For the incremental model, the paper provides an algorithm that guarantees finding an approximately optimal seed set solution for all networks during the network evolution, while the amortized update cost is much smaller than the re-computation cost at every time step. For the fully dynamic model, the authors provide a strong negative result, showing that under a commonly adopted complexity assumption SETH, the fully dynamic influence maximization problem cannot be solved, more specifically, to achieve even slightly better than a nontrivial 1/n approximation ratio, one need almost linear amortized running time.

The contribution of the paper is on the systematic study on dynamic influence maximization. From the theory side, it is much better than existing studies on dynamic influence maximization, which is mostly heuristic based and does not provide speedup in amortized running time.
main_review: The strength of the paper is its theoretical contribution to the dynamic influence maximization problem. This is the first study I see that provide strong theoretical results on two important dynamic models. On the incremental model, it provides the first theoretical algorithm that has significant speedup in terms of the amortized running time, where the existing studies usually do not provide any theoretical results and any speedup in amortized running time. To achieve this theoretical result, the proposed algorithm is nontrivial, and it combines several techniques to address several issues that arises due to the dynamic changes in the network. For the fully dynamic model, it provides a strong inapproximation result, which is the first such hardness result and also provides inside into the hardness of this setting.

In general, the paper has good original results, built upon recent research on dynamic submodular maximization and certain hardness results. It would be very useful for the community to understand these theoretical results, and since dynamic setting is very realistic, this could be important for practical considerations too. The paper also tries to explain the algorithm and proof ideas in a clean way, and in general the paper is well structured.

The weakness of the paper is that the key algorithm explanations have several unclear points and typos, making it hard to fully understand the algorithm and its novelty. I will list these issues below in the detailed comment section. I believe most of these issues can be addressed in the next revision, and I am looking forward to the authors' feedback to answer these issues and clean up the presentation. I did not check the details of the analysis, but has reasonable confidence that the martingale based analysis is mainly correct.


Detailed comments on the presentation issues:

- Line 12. For the hardness result, the approximation ratio uses the expression that is greater than 1, while for the algorithm, it uses the approximation ratio of 1-1/e, which is less than 1. This should be made consistent.

- Line 99. It uses V and E to denote the set of nodes and edges, and their size to be n and m. Since the network is dynamic, the authors should clearly state what V, E, n and m means. I believe it means the largest possible set of nodes and edges and their values. Please clarify. Also, later V is also used as the instant node set, and that could be confusing. I suggest that the authors always use $V_t$ to represent the current node set at some time t. 

- Line 169-170. It says the amortized running time matches the state-of-the-art offline algorithm up to poly-logarithmic factors. This statement is unclear to me. If we totally have T updates, the total running time of their dynamic algorithm should be much faster than re-run the offline algorithm at each update. The state-of-the-art offline algorithm for each update is in time $O(k(n+m) \log n/\epsilon^2)$. So what does it mean by matching the algorithm? I just realized the authors perhaps mean by growing a graph from an empty graph in n+m steps, their algorithm would achieve almost the same running time. Please explain this in a better way to convey the idea that their algorithm is much faster than re-run the offline algorithm at each update.

- Line 220. $OPT_i$ is not explained in the context, should directly say it is $(1+\epsilon)^i$.

- Section 3.1. The explanation of the algorithm in the text as well as the algorithm pseudocode should be improved. There are number of points that are unclear to me in the first reading. The following is a list of such issues.

- Line 240. Variable $R$ and $m_0$ are not explained in the context. One has to read the pseudocode to get some idea.

- Algorithm 1, line 2, notation V and E is better changed to dynamic notations, such as V_t or E_t, to avoid confusing with the largest node and edge set notation. For example, in line 3 of Algorithm 2, when it says uniformly over V, I initially thought it is uniformly over the largest node set, but I guess it means uniform over the current node set V.

- Algorithm 2, line 5, "step" is a technical term that is not explained precisely. What is exactly a step? Moreover, in earlier description (see line 131), it refers to one time step t as the step for adding a node or edge (or delete a node or edge). I believe these two steps are different, but the authors do not provide clarification. I suggest that for network change, we may call it round, and in each round, there is one network change. The time step is reserved for computational steps within a round. Please specify what one step really means. Is it that randomly selecting one reverse edge in the RR set generation process one step?

- Algorithm 3, line 2. Constant c is not explained. What is its purpose?

- Algorithm 3, line 4. This is to set a probability p. What if $K > n_0$ and the $p$ is not a probability? I never see an explanation here. Actually, I believe this is a very important point. If $p < 1$ and it is indeed a probability, then line 5-11 only samples one RR set for each node $v$. Is it enough? In the RIS approach for the classical IM problem, it is possible that on average each node $v$ would have many RR set samples, otherwise, the estimation may not be accurate. Therefore, I feel that there is some gap here. Is it possible that $K > n_0$ and this suggests that each node $v$ should have multiple RR set samples? 

- Algorithm 3, line 9, INSERT-EDGE-COV(u,v), this routine is not explained in Section 3.1 and only explained in Section 3.2, but it is important to understand this routine in order to understand Algorithm 1-5. 

- Algorithm 4, line 6. Notation $V_{L,est}$ is not explained, so do the notations in the next three lines. I have to guess that it means the left-side nodes in the bipartite graph H_{est}. Please clarify. Moreover, the left-side of H_{est} should be the nodes while the right-side of H_{est} should be RR sets, so technically, for line 8 and 9, it should be RR sets $\{u\}$ with a single node, not the single node $u$ itself.

- Algorithm 5, line 7 and line 15. There is no explanation of what these augmentation operations do. Please clarify. This is actually the important incremental step of the model. Is it just simply revisiting all the RR sets to consider adding the edge $(u,v)$? How to control the time complexity? This time complexity is also related to the time step estimation in line 9. 

- Algorithm 5, line 15 and 16. Why the subscript est appears in the notations? Is it a typo, and should it be cv? Also, for all $v$ \in R^{new}_{v,cv} \setminus R_{v,cv} looks strange to me, since $v$ appears both on the left and as the subscripts in the right-hand side.

- Line 306. It is strange to return a value. I think it should return argmax among $S_i$, where $i \in I$.

- Algorithm 6 to 8. Function $f$ is used in these algorithms. What is exactly the $f$? Should it be $f_{cv}$ derived from the coverage graph $\mathcal{H}_{cv}$?

- Line 490. "Xi Chen" should be "Wei Chen"

Overall, the above listed issues are mostly presentation issues. If the authors can satisfactorily address all these issues in the rebuttal, my rating on the paper could be further increased.

There are also a few other studies on dynamic influence maximization. Although they are not directly related to the theoretical study of the current paper, they are early studies in this area that should be cited:

- Aggarwal C, Lin S, and Yu P S. On influential node discovery in dynamic social networks. In Proceedings of SIAM International Conference on Data Mining (SDM), Anaheim, USA, Apr 2012

- Liu X, Liao X, Li S, Zhang J, Shao L, Huang C, and Xiao L. On the shoulders of giants: incremental influence maximization in evolving social networks. Complexity 2017

============ Post rebuttal comments ==================

The authors feedback has addressed my comments and concerns, which are mostly on the presentation and clarity of the paper. In particular, the treatment of p in Algorithm 3 is clear now --- it is not just a probability, and could allow multiple samples. 

limitations_and_societal_impact: The work is purely theoretical, and no perceived negative societal impact exists.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper presents new algorithms and hardness results for dynamic influence maximization, where dynamics come from one of two models: (1) the incremental model, which consider only the addition of new nodes and edges in a graph, and (2) the fully dynamic model, where nodes and edges can also be removed. Previous work has considered only heuristics that satisfy certain approximation guarantees but do not come with good amortized cost for updating the see set in the dynamic case. This paper provides a (1-1/e-eps) approximation for the optimal solution with k*poly(log n, 1/eps) approximation for the incremental model. For the fully dynamic model, the paper presents a hardness of approximation result if the Strong Exponential Time Hypothesis is true.

The proof for the approximation algorithm for the incremental model is based on two major pieces. First, the paper provides a reduction from dynamic influence maximization to dynamic MAX-k coverage. Then, a new algorithm for dynamic Max-k coverage is given. This follows a previous strategy for the static version of the problem, though a significant amount of theoretical work is required to extend both parts to the dynamic case.

The work is primarily theoretical and no implementations or experimental results are given.

main_review: Overall, the contributions of the paper substantially extend previous work on influence maximization in static graphs, and the paper involves a significant theoretical effort. However, the theoretical details are quite hard to parse in many places and it's hard to tell what the algorithm is actually doing and hard to verify its correctness. This is no doubt at least partially due to my own unfamiliarity with some of the related work, as well as to the inherent complexity of making key techniques for influence maximization work in a dynamic setting. Nevertheless, even in the technical overview there are a number of statements that seem overly confusing, as well as a number of technical terms and ideas that are used without proper definition or explanation. I list several examples below, in the hopes that a re-write might make this more accessible to a wider audience.

* The word "steps" is being used to mean many different things in explanations on page 4 and following. First, the graph is dynamically changing at different time *steps* t. But then in the technique overview (starting line 175), I believe "steps" also starts to be used in reference to steps taken by a random instantiation of the process for finding a reverse reachable set (though I'm not sure what a step is here!). Then "steps" is used to refer to the two stages of the algorithm (line 180). I'd recommend the authors take some time to re-write the technical overview and try to distinguish more carefully between steps/stages, and concretely what a step means in each setting. This may seem minor, but without clarification and some more technical precision, it's not clear to me what is going on even in the overview, let alone the pages following it.
* The idea of a reverse reachable set is clear in the static setting (Definition 2.1), but it's not clear to me what a Reverse Reaching Set should mean in the dynamic setting or what it might mean to sample a reverse reachable set when nodes and edges are changing. These concepts are used repeatedly, but there is no concrete explanation of what this means. A more precise explanation might help here too.
* Related to both of the above points, when we get to Algorithm 2,  what notion of "steps" is being used here and what does it means to sample an RR set?
* The definition of dynamic influence maximization at the top of page 4 to me is clear. However, this relies on some notion of a time step t, but we don't see any reference to any time step t throughout the technical overview. It's unclear what steps are happening at different t values. For example, how does this factor into what it means to sample an RR set? Does sampling an RR set somehow happen across time steps t? (I'm not sure how it could, but I can't tell!). Does sampling RR sets happen at each time step? If so, how does that work?

Overall, I'd recommend a re-write of at least the technical overview on page 4 and 5, with some added technical precision. The main results seem strong and the very high level overview of the approach makes sense (i.e., reduction from DIM to dynamic MAX-k coverage + new algorithm for dynamic MAX-k coverage), but beyond this I'm unable to parse what is actually going on in the technical details. 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies influence maximization (IM) in a dynamically evolving social network, where at each time step, one node/edge may emerge or disappear. The authors consider two evolution models: the incremental model (only node/edge insertion is allowed; e.g., the DBLP network) and the full model (both insertion and deletion are allowed; e.g., the Twitter network). 

Under the incremental model, a $(1-1/e-\epsilon)$-approximation algorithm is proposed with $k\cdot \textrm{poly}(\log n, \epsilon^{-1})$ amortized running time. This is an algorithmic breakthrough because previous dynamic IM algorithms [44, 36, 20] all need $\Omega(n)$ amortized running time in the worst cases.

Under the full model, it is proved that no algorithm can achieve a meaningful approximation ratio within $O(n^{1-o(1)})$ amortized running time under the Strong Exponential Time Hypothesis.

Both theoretical results are proved under the classical IC and LT models.
main_review: The theoretical results in this paper are novel from my perspective. The used techniques are also different from previous dynamic IM studies and dynamic submodular optimization studies. I did not check the proof correctness in the supplementary material, but the logic and intuition explained in the main paper seem to be smooth.

A few questions and concerns:
- You claim that several previous studies on dynamic IM [44, 36, 20] need $\Omega(n)$ amortized running time in the worst cases. Could you summarize their accurate running time in a table? Also, do they bear the same setting as yours? Do they allow node/edge deletion?

- The theoretical results in this paper are novel and inspiring, but I still feel empirical evaluation is needed. Unlike the general submodular optimization problem, IM is a practical task. Under the incremental model, I would suggest comparing the empirical running time and spread of the proposed model and previous studies [44, 36, 20] if they are applicable in this setting.

- In Lines 89-95, you mention the difference between your results and recent studies on dynamic submodular maximization. Specifically, their results are measured in query complexity. I feel this difference is not essential because one can multiply their complexity by the complexity of computing each query (i.e., the complexity of computing the spread given the seed set; can be accelerated using RR sets) when applying their approach to dynamic IM. Maybe the more essential difference is that in dynamic IM, $\sigma(\cdot)$ is changing when nodes/edges are inserted and deleted?

- There are many typos in the paper. I would suggest the authors carefully check their writings again. To give some examples,
Line 49: maintains -> maintain. Line 64: seminar -> seminal. Line 147: that is say -> that is to say.
limitations_and_societal_impact: Please see the main review.
review_title: null

Meta-review: The authors propose a new efficient algorithm for influence maximization in the incremental setting.  The theoretical contribution is interesting and novel and the problem is interesting and well-studied. The main limitation of the current write-up is its writing but that should be addressed by implementing the reviewers’ suggestions. Overall, the paper is a nice contribution and I suggest to accept it.
Decision: Accept (Poster)