Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: In this paper, the authors consider using learning-based method for Influence Estimation and Influence Maximization. The author proposed a GNN-based to estimate influence (as an upper bound). Based on the estimated influence, the authors use CELF optimization to find the optimal seed set. To further improve the efficiency, the authors proposed (1) a RL DQN based method and (2) a simplified influence function with only one layer. The author carries out experiments on several synthetic and real-world datasets. 
main_review: Strength
1. It is an interesting and practical idea to consider learning-based approach for cascade problems on social networks.
2. The authors carry out experiments on several networks (both synthetic and real-world) with reasonable large number of nodes (>1M).

Weakness
1. Some of the writing in the paper is not clear or misleading. First, it is not clear what is the input to the GNN. It mentioned that H_0 \in R ^{n*d}. If just whether the node is in seed set is encoded, only 1 dimension is needed. Second, it would be better for the authors to clarify that the monotonicity and submodularity of only (12) is proved. There is no guarantee for (6) but only qualitative evaluation for (6). As a result, the usage of CELF may not be well justified.
2. The method with best performance PUN has little to do with the learning method. It is just a diffusion function with 1 step. Also, the network is actually not trained for the target. One possible reason is that the activation probabilities are really small (1/ avg degree) setting such that the cascade depth are really shallow. In this case, the authors should compare their method to some heuristics.
3. The empirical evaluation is not very convincing. First, RSS-based methods are not included in the influence estimation part. Second, running time comparison on GPU based method and CPU method is not a fair comparison. Third, as mentioned above, heuristic-based method should be included in the comparison as in Table 5.
4. One strength of learning-based approach is to generalize beyond one given diffusion model. It would be interesting to see (1) experiment on real-world cascades; (2) generalization under diffusion model misspecification. 

summary_of_the_review: Though the idea of using learning-based approach for IM problem is interesting, the proposed method did not demonstrate advantage over existing methods (the best performing one is more like existing heuristics). Also, there are a few missing pieces in the evaluation.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper considers using learning methods to solve the well-known influence maximization problem. The paper proposes to estimate the upper bound of the influence by using graph neural networks, which can be used in subsequent steps for selecting the seed nodes through either Q-learning or a greedy algorithm based on the learned representation. Experiments on various datasets have been provided to evaluate the accuracy of influence estimation as well as the effect of influence maximization.  
main_review: I would proceed by saying that I was one of the reviewers of this paper in its previous submission to another conference. First of all, I appreciate the efforts made by the authors to improve the previous version. I am willing to increase my score if the author could address my concerns.

$\textbf{Strength:}$ 
-	Using GNN for learning representations is a reasonable choice
-	This paper is technically sound. 
-	Constructing a submodular score function based on the learned representation is also an interesting idea. 

$\textbf{Weakness:}$

Using learning methods for estimating influence or influence maximization have been extensively studied (e.g., [a]-[d] listed below and their references). Using GNN and Q-learning is reasonable but not novel.  

[a] Li, Hui, Mengting Xu, Sourav S. Bhowmick, Changsheng Sun, Zhongyuan Jiang, and Jiangtao Cui. "DISCO: influence maximization meets network embedding and deep learning." arXiv preprint arXiv:1906.07378 (2019).

[b] Du, Nan, Yingyu Liang, Maria Balcan, and Le Song. "Influence function learning in information diffusion networks." In International Conference on Machine Learning, pp. 2016-2024. PMLR, 2014.

[c] Xia, Wenwen, Yuchen Li, Jun Wu, and Shenghong Li. "DeepIS: Susceptibility Estimation on Social Networks." In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pp. 761-769. 2021.

[d] Liu, Qi, Biao Xiang, Enhong Chen, Hui Xiong, Fangshuang Tang, and Jeffrey Xu Yu. "Influence maximization over large-scale social networks: A bounded linear approach." In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, pp. 171-180. 2014.

The experiments do not demonstrate a strong need for learning-based methods for influence estimation or influence maximization. 

- The influence estimation problem is only challenging when the cascade can spread for a large number of hops. The presented experiments consider influence estimation from small seed sets. Under such settings, even MC is not time-consuming. For the same reason, the independent cascade model (with uniform probability) is a better model to study, as it in general results in a much larger influence than the WC model – for dense graphs, the WC model tends to give low propagation probability.

- Notice that IMM might be the state-of-the-art method with approximation guarantees, but efficient heuristics are possible (as discussed in [e]). It is well-known that heuristic methods can provide solutions with qualities similar to the (1-1/e)-approximation. Therefore, to demonstrate the efficiency of the proposed method, it is better to also compare it with fast heuristics. 

[e] Debunking the myths of influence maximization: An in-depth benchmarking study

- The testing size appears to be too small to draw results that are statistically significant. In addition, there is no information about std to demonstrate the robustness.

The proposed learning model essentially uses a diffusion process of bounded steps to estimate the entire diffusion process. Since the layer number is 2, this means that only two steps of diffusion are considered. Under the WC model, it is likely that the majority of the nodes are activated within two steps, and therefore it is not very surprising that the estimate is accurate. Notice that the #p-hardness only holds for general diffusion steps, and assuming that only two diffusion steps are considered, many existing methods can be modified to be more efficient (e.g., IMM with two-hop reverse sampling). 

Minor questions:
- What does negative sample mean in Sec4.1?

- It is quite surprising that PUN can produce high-quality solutions to large graphs with a very small computation cost. This essentially means that the #p-hardness could be overcome by a one-step influence estimation, which looks too ambitious. If this is the case, $\sigma^m$ should be a nice method for influence estimation, which could be verified by experiments. In a related issue, for the running time of the proposed methods, I am wondering if the time used for computing the representations is included. For large graphs, computing the representation involves multiplications of large matrices. 

summary_of_the_review: The proposed technique is not very novel, and its practical utility needs better justification.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Authors propose several neural network model-based approaches to influence maximization (IM). First, GLIE estimates influence using a GNN, which can be plugged into optimization algorithms like CELF. Second, GRIM avoids the cost of having to estimate the influence of every candidate by approximating the marginal gain with a two-layer MLP. Finally, PUN avoids the cost of having to estimate the influence for every seed node by approximating the influence with features from GNN hidden states. Experiments demonstrate that the proposed method can generalize to graphs significantly different from training data. Also, PUN provides solution quality close to the strongest baseline with a fraction of compute time.
main_review: While the use of GNNs for combinatorial optimization has become quite popular in recent years, their application to Influence Maximization (IM) is not straightforward, as it is quite different from previous GNN applications. The IM problem has a strong structure (submodularity), and strong non-learning algorithms are already established for the problem. Therefore, it is quite surprising and encouraging to see that GNNs can actually be quite competitive on this problem.

Another strength of the paper is the thoroughness of the approach. The paper proposes three levels of gradual transition from traditional approach (CELF) to completely estimation-based approach (PUN). Compared to simply providing a single approach that works, this gradual approach allows readers to better understand why a simpler approach does not suffice and more techniques need to be introduced.

One notable weakness of the paper is their lack of reference to Alieva et al https://openreview.net/forum?id=ac288vnG_7U . Since this paper also proposes a learning-based approach for submodular optimization, this approach should've been discussed and compared against as a baseline.

Also, in (7), $O(S, s)$ and (10), authors heuristically construct features from frozen GLIE models. Authors provide some intuition about them, saying the hidden state $H_t^i$ can be considered as "a label for each node whose sign indicates if it is predicted to be influenced." However, this seems like an overstatement: $H_t^i$'s are intermediate hidden states from the GLIE model, and there does not seem to be any mechanism (like a loss function) which encourages these intermediate hidden states to be the "influence label". Many design choices like why (7) sums over $T$ and normalize by $d_t$ are unclear. (10) is even more confusing because it only uses the first layer of the GNN- does it mean that additional GNN layers are not needed? Actually, it doesn't seem like authors share an analysis of the impact of GNN layers.

Lastly, it wasn't sure $\sigma^m(S)$ can be interpreted as a submodular function in a standard sense. For a submodular function, we should be able to evaluate for any set in the domain of the function. However, definition (12) assumes the given input $S$ can be associated with the sequence of seed sets $S_1, S_2, \ldots, S_{|S|}$. In other words, the function is only well-defined for the sequence of sets $S_1, S_2, \ldots$ observed during the execution of the greedy algorithm. Therefore, I am not sure (1-1/e) approximation guarantee of greedy monotone submodular maximization applies here.
summary_of_the_review: Influence Maximization is a quite surprising application of GNNs. Authors employ a systematic approach to build multiple methods with more departure to the traditional approach and increasing levels of computational advantage. Some of modeling decisions look heuristic, however, and at least requires a better explanation.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a neural network approach (GLIE) for estimating the influence of a given seed in a given graph. More importantly, the authors propose three different methods to use the proposed Influence Estimation method for Influence Maximization. The authors show the superior performance of their proposed method in comparison with baselines and 
main_review: The paper studies an important problem data mining problem, i.e., Influence Maximization. The proposed network for approximating the influence is interesting on its own. The paper is overall well-written as easy to follow. However, the paper can benefit from polishing: for instance, the braces in Eq. (5) are a bit confusing. Also, the experimental section is rushed. For example, in Sec. 4.1. it is not clear to me how the graph neural network is trained. Is it trained only on BA graphs? If so, how did the authors use that network for other graphs, when the network weights are clearly dependant on graph node size? Also, it seems that the main novelty of the paper is in proposing to estimate the influence via graph neural networks and the proposed influence maximization methods use already existing techniques in combination with this influence estimation method. In that sense, the theoretical contributions of the paper are marginal. However, combining these techniques is still non-trivial.  
summary_of_the_review: Overall, the paper proposes novel methods for Influence Estimation and Influence Maximization. In my opinion, the main weakness of the paper is the missing details in the experimental section.
review_title: null

Meta-review: This paper revisits the problem of influence maximization and suggests using graph neural networks to estimate an upper bound on the influence, which can then be used to find good seed sets. The paper gives a variety of experimental evidence that the methods improve on various algorithms in the literature. There was a wide variation in opinions. Some reviewers felt that the overall idea was not particularly novel, as methods that combine graph embeddings and reinforcement learning to solve influence maximization have already been proposed in the literature. Additionally some reviewers felt that the experiments were missing important comparisons, particularly to learning-based methods, without which it is difficult to argue that these methods really do advance the state of the art.
Decision: Reject