Learning Graph Representations for Influence Maximization
Authors: George Panagopoulos
Nikolaos Tziortziotis
Fragkiskos D. Malliaros
Michalis Vazirgiannis
Venue: ICLR 2022 Submitted (2022)
Keywords: influence maximization
graph neural networks

Abstract: As the field of machine learning for combinatorial optimization advances, traditional problems are resurfaced and readdressed through this new perspective. The overwhelming majority of the literature focuses on small graph problems, while several real-world problems are devoted to large graphs. Here, we focus on two such problems: influence estimation, a #P-hard counting problem, and influence maximization, an NP-hard problem. We develop Glie, a Graph Neural Network (GNN) that inherently parameterizes an upper bound of influence estimation and train it on small simulated graphs. Experiments show that Glie provides accurate influence estimation for real graphs up to 10 times larger than the train set. More importantly, it can be used for influence maximization on considerably larger graphs, as the predictions ranking is not affected by the drop of accuracy. We develop a version of Cost Effective Lazy Forward optimization with Glie instead of simulated influence estimation, surpassing the benchmark for influence maximization, although with a computational overhead. To balance the time complexity and quality of influence, we propose two different approaches. The first is a Q-network that learns to choose seeds sequentially using Glie's predictions. The second defines a provably submodular function based on Glie's representations to rank nodes fast while building the seed set. The latter provides the best combination of time efficiency and influence spread, outperforming SOTA benchmarks.

Under review as a conference paper at ICLR 2022
LEARNING GRAPH REPRESENTATIONS FOR INFLU- ENCE MAXIMIZATION
Anonymous authors Paper under double-bling review
ABSTRACT
As the field of machine learning for combinatorial optimization advances, tra- ditional problems are resurfaced and readdressed through this new perspective. The overwhelming majority of the literature focuses on small graph problems, while several real-world problems are devoted to large graphs. Here, we focus on two such problems: influence estimation, #P-hard counting problem, and influence maximization, an NP-hard problem. We develop GLIE, a Graph Neu- ral Network (GNN) that inherently parameterizes an upper bound of influence estimation and train it small simulated graphs. Experiments show that GL.IE provides accurate influence estimation for real graphs up the train set. More importantly, it can be used for influence maximization on considerably larger graphs, as the predictions ranking is not effected by the drop of accuracy. We develop version of Cost Effective Lazy Forward optimization with GLIE instead of simulated influence estimation, surpassing the benchmark for influence maximization, although with computational overhead. To balance the time complexity and quality of influence, we propose two different approaches. The first Q-network that learns choose seeds sequentially using GLIE'S predictions. The second defines provably submodular function based on GLIE'S representations rank nodes fast while building the seed set. The latter provides the best combination of time efficiency and influence spread, outperforming SOTA benchmarks.
times larger than
INTRODUCTION
Several real-world problems can be cast a combinatorial optimization problem over graph. From distributing packages (Mathew et al. 2015) to improving the general health (Wilder et al. 2018) and vehicles' management (Touati-Ne Mouati-Moungla & Jost 2012). optimization on graphs lies in the of many real-world applications that are vital to our way of living. Unfortunately, the majority of these problems NP-hard, and hence we can only approximate their solution in satisfactory time limit that matches the real world requirements. Recent machine learning methods have emerged promising solution develop heuristic methods that provide fast and accurate approximations (Bengio et al. 2020). The general idea is to train supervised or unsupervised learning model to infer the solution given an unseen graph and the problem constraints. The models tend to consist of Graph Neural Networks (GNNs) to encode the graph and the nodes, Q-learning (Watkins & Dayan 1992, [Sttton Barto (018)) to produce sequential predictions, or combination of both. The practical motivation behind learning to solve combinatorial optimization problems, is that inference time is faster than running an exact combinatorial solver (Joshi et al. 2019). That said, specialized combinatorial algorithms like CONCORDE for the Traveling Salesman Problem (TSP) or GUROBI in general, cannot be surpassed yet (Kool et al. 2018).
Though many such methods have been proposed for plethora of problems, influence maximization (IM) has not been addressed yet extensively. IM addresses the problem of finding the set of nodes in network that would maximize the number of nodes reached by starting diffusion from them (Kempe et al. 2003). The problem is proved to be NP-hard, from a reduction to the set-cover problem. Moreover, the influence estimation (IE) problem that is embedded in IM, i.e., estimating the number of nodes influenced by given seed set, is #P-hard as it is analogous to counting s-t connectedness and would require E1 possible combinations to compute exactly, where |E| is the number of network edges (Wang et al. 2012). Typically, influence estimation is approximated using

---

Under review as a conference paper at ICLR 2022
repetitive Monte-Carke (MC) simulations of the independent cascade (IC) diffusion model. In general, the seed set is built greedily, taking advantage of the submodularity of the influence function which guarantees at least (1 - )) approximation to the optimal. Although the latter lacks of efficiency as one still has to estimate influence for every candidate seed in every step of building the seed sets. Hence, several scalable algorithms(Borg
al. (2014); [Tang al. (2015) and heuristies Chen iet al. (2009); Jung et al. (2012) were developed capitalizing on sketches or the structure of the graph to produce more efficient solutions. IM can be applied on a plethora of real-world tasks, such as epidemic containment (Wilder et al., 2017), diminishing fake news (Budak et al., 2011), and running viral marketing campaigns (Domingos & Richardson 2001).
We address IM using neural networks, to capitalize on the aforementioned udvantages as well as their ability to easily incorporate contextual information such as user profiles and topics (Tian et al. 2020). a task that remains unsolvable for non-specialized IM algorithms and heuristics. We propose GI.IE, a
GNN that provides efficient IE for given seed set and graph with influence probabilities. can be used as a standalone influence predictor with competitive results for graphs up to 10 times larger than the train set. Moreover, we leverage GLIE for IM, combining it with CELF (Leskovec et al. 2007). that typically does not scale beyond networks with thousands of edges. The proposed method runs in networks with millions of edges in seconds, and exhibits better influence spread than a state-of-the-an algorithm and previous GNN-RL methods for IM. In addition, architecture that utilizes GLIR's representations and predictions to obtain seeds sequentially, while minimizing the number of influence estimations throughout steps. Finally, we propose PUN, method that uses GLIE'S representations to compute the number of neighbors predicted to be uninfluenced and uses an approximation to the marginal gain. We prove PUN's influence spread is submodular and monotone, and hence can be optimized greedily with guarantee, in contrast to prior learning -assed methods. The experiments indicate that PUN provides the best balance between influence quality and computational efficiency.
develop GRIM, Q-learning
The paper is organized as follows. Section 2 presents an overview of relevant approaches and clarifies the advantage of the proposed models. Section 3 describes the proposed methods, starting with IE and advancing progressively towards faster methods for IM. Section 4 exhibits and interprets the experimental results for IE and IM. Finally, Section 5 summarizes 5ummarriss the contribution and presents future steps.
RELATED WORK
The first approach to solving combinatorial optimization (CO) using neural networks was based on attention based NNs for discrete structures, POINTERNETS (Vinyals et al. 2013), followed by an architecture that combines POINTERNETS with an actor-critic training to find the best route for TSP (Bello et al., 2016). The first architecture that utilized graph-based learning was S2N-DQN (Dai et al., 2017), SrinnSTTRCT2VER V EC to encode the states of the nodes and the graph, and training a Q-learning model that chooses the right node to add in solution given the current state.
Based on S2v-DQN, a DQN (Mnih et al. 2015) for the network dismantling problem was recently proposed (Fan et al. 2020) (Li ct al. 2019). The model, named FINDER, uses deep Q-learning architecture where the representations are derived by three GRAPHS layers. The reward is based on size of the giant connected component size, i.e., every new node (seed) chosen, aims to dismantle the network as much as possible. Some of the main advantages of FINDER is that it is trained on small synthetic data, which are easy to make, and can extrapolate to relatively large graphs. On the other hand, one of the core disadvantages is that it can not work with directed graphs and weighted edges. Another recent supervised deep learning approach on IM, GCOMB (Manchanda et al. 2020). utilizes a probabilistic greedy to produce scores on graphs and trains a GNN to predict them. A Q-network receives the scores along with an approximate calculation of the node's 's neighborhood
correlation with the seed set, to predict the next seed. This approach, though scalable and comparable to SOTA in accuracy, has to be trained on a large random subset of the graph (30% of it) and tested on the rest. This makes the model graph-specific, i.e., it has to be retrained to perform well on new graph. This imposes a serious overhead, considering the time required for training, subsampling and labeling these samples using the probabilistic greedy method with traditional IE. As shown in (Manchanda et al., 2020) Appendix G. it takes at least hundreds of minutes and is thus out of our scope. Finally, recent works on learning approximations to submodular policies? require large
2

---

Under review as a conference paper at ICLR 2022
number of ground truth evaluation to create the training trajectories, which rendering the training too time consuming. Moreover, such methods require a novel neural network encoding to capture the state of IM, which has not been developed yet.
In this paper, we propose an approach that combines the advantages the aforementioned methods, in that it is only trained on small simulated data once and generalizes to larger graphs, and it addresses the problem of IM in weighted directed networks. Furthermore, the approach can be broken down GNN for influence estimation and three IM methods. The former can act alone as influence predictor and be competitive with relevant methods, such as DMP (Lokhov & Saad 2019) for graphs up to one scale larger than the train set. GLIE is used to propose SELF-GLIE, CELF Leskovec et al.) (2077) with GLIE as influence estimator, GRIM, a Q-network that learns how to choose seeds using the GI.IE's estimations and hidden representations, and PUN, an adaptive IM method that optimizes greedily submodular influence spread using GLIE'S 's representations.
We note here that the majority of the relevant literature on DL for CO address small graphs (Vinyals al.] 2015 Dai et al. 2017 Kool et al. (2018) 8; Prates al. 2019)) which makes them not applicable to our task. More scalable, unsupervised methods (Karalias Loukas 2020) are tailored to specific problems and is non-trivial to adjust them to our problem, with the exception of (Li et al. 2018) which was found significantly worse than the SOTA algorithm we compare with in Manchanda et al. (2020).
METHODOLOGY
3.1 GRAPH LEARNING FOR INFLUENCE ESTIMATION (GLIE)
In this section, we introduce GLIE (GNN Learning Influence Estimation), which aims to learn how to estimate the influence of a seed set over graph = (V, E). Let A E R be the adjacency matrix and X E Rn be the features of nodes, representing which nodes belong to the seed set by 1 and otherwise:
{
{1}d [0]4,
uES u 5
X
(I)
For the derivation of the corollary, we set = More dimensions will become meaningful when parameterize the problem. If we normalize A by each row, we form row-stochastic transition matrix, as:
E (u) V N())
A. Pou
deg(a)+ 0,
(2)
where deg(u) the in-degree of node u and (()) is the set of neighbors of u. Based on the weighted cascade (Kempe et al. 2003), each row u stores the probability of node being influenced by each of the other nodes that are connected to it by a directed link v - u. Note that, in case of directed influence graphs, A should correspond to the transpose of the adjacency matrix. The influence probability p(u .5 resembles the probability of node u getting influenced if its neighbors belong in the seed set, i.e., during the first step of the diffusion. We can message passing to compute well-known upper bound S(u[S) of S( for node w:
p(u|S) A.
Σ rEA(U))S
Pvu 21
II (1- = p(u)S), (3) vEA(s))S
deg(u)
rEA(s)
where the second equality stems from the definition of the weighted cascade and the incquality from the proof in Zhou et al.) (2015), App. A. As the diffusion covers more than one-hop, the derivation requires repeating the multiplication to approximate the total influence spread. To be specific, computing the influence probability of nodes that are not adjacent to the seed set requires estimating recursively the probability of their neighbors being influenced by the seeds. If we let H A X, and we assume the new seed set S to be the nodes influenced in the step / - 1, their probabilities are stored in H,, much like diffusion in discrete time. We can then recompute the new influence probabilities with H,t1 = A H.
Corollary 3.0.1. The repeated product H4+1 = A H. computes an upper bound to the real influence probabilities of each infected node at step ( 1.
3

---

Under review as a conference paper at ICLR 2022
The proof can be found in Appendix A.1. In reality, due to the existence of eycles, two problems arise with this computation. Firstly, if the process is repeated the influence of the original seeds may increase again, which comes in contrast with the independent cascade model. This can be controlled by minimizing the repetitions, e.g. four repetitions cause the original seeds to be able to reinfect other nodes in network with triangles. To this end, leverage up to three neural network layers. Another problem due to cycles pertains to the probability of neighbors influencing each other. In this case, the product of the complementary probabilities in Eq. (3) does not factorize for the non-independent neighbors. This effect was analyzed extensively in Lokhov & Saad (2019). App. B, and proved that the influence probability computed by p(u]S) is itself an upper bound on the real influence probability for graphs with cycles. Intuitively, the product that represents non-independent probabilities is larger than the product of independent ones. This renders the real influence probability, which is complementary to the product, smaller than what we compute.
We can thus contend that the estimation f(u(S) provides an upper bound on the real influence probability- and we can use it to compute an upper bound to the real influence spread of given seed set i.e., the total number of nodes influenced by the diffusion. Since message passing can compute inherently an approximation of influence estimation, we can parameterize it to learn function that tightens this approximation based on supervision. In our neural network architecture, each layer consists of GNN with batchnorm and dropout omitted here, and starting from Hg- = X E Raxd we have:
H H ReL Wo)
(4)
The readout function that summarizes the graph representation based on all nodes' representations is a summation over all the final representations with skip connections:
H
= H. D H.
(5)
DEV
This representation captures the probability of all nodes being active throughout each layer. The output that represents the predicted influence spread is derived by:
a(S) ReL.
Note that, the derived representations of each layer Hi, untrained, are the upper bound of the influence probability of seed set's the t-hop neighbors. The parameters of the intermediate layers W, are trained such that the upper bound is reduced and the final layer W, can combine the probabilities to derive a cumulative estimate for the total number of influenced nodes. We empirically verify this by examining the layer activations which can be seen in Fig. and the heatmaps indicate difference between columns (nodes) expected to he influenced, meaning we could potentially predict not only the number but also who will be influenced. However, since à is derived by multiple layers, the relationships and thresholds to determine the exact influenced set is not straight forward. Below we experiment with different such sets extracted from /l for the purpose of IM.
3.2 COST EFFECTIVE LAZY FORWARD WITH GLIE (CELF-GLIE)
The original Cost Effective Lazy Forward (Leskovec et al. 2007) is an acceleration to the original greedy algorithm that is based on the constraint that seed's spread will never get bigger in subsequent steps. The influence spread is computed for every node in the first iteration and kept in a sorted list. In each step, the marginal gain computed for the node with the best influence spread in the previous round. If it is better than the previously second node, it is chosen as the next seed because it necessarily bigger than the rest. This property stems from submodularity, i.e.. the marginal gain can never increase with the size of the seed set. If the first node's 's current gain is smaller than the second previous gain, the list is resorted and the process repeated until the best node found. The worst-case complexity is similar to greedy but in practice it can be hundreds of times faster, while retaining greedy's ' original guarantee.
In our case, we propose straight forward adaptation where we substitute the original CELF IE based on MC IC with the output of GLIE. We redirect the reader in the Appendix B, where we show that the estimations of GLIE monotonous and submodular in practice, and hence & is suitable for optimizing with CELF. Since we do not prove the submodularity of ô, we can not contend that the theoretical guarantee is retained. CELF-GLIE has two main computational bottlenecks. First,
4

---

Under review as a conference paper at ICLR 2022
S
Action Frow secal
GLI
1 LAVER
GLIE
(8 6(8)
SUM
Za
(S))
Setinneenc
2d LAVE
ao mafo]
BEADOCY
infuence net l.s
Overitp
Q-Ner
LL,,, ((i))
Score far mikkig
Btal
(- I.....
Seed influnce
OUTTPUT
Condicato seeds
(0(S), O(Ls,
PUN
INFLUENCE ESTIMATION
GRIM
Campute For candidate seed before Conatwork
Figure I: A visual depiction of the pipeline for GRIM and PUN. The layers of GLIE are depicted by a heatmap of an actual seed during inference time, showing how the values vary through different nodes (columns).
although it alleviates the need to test every node in every step, in practice it still requires IE for more than one nodes in each step. Second, requires computing the initial IE for every node the first step. We will try to alleviate both with the two subsequent methods.
3.3 GRAPH REINFORCEMENT LEARNING FOR INFLUENCE MAXIMIZATION (GRIM)
We develop a method that computes only one IE in every step, along with the initial IE for all nodes. We first utilize the activations mentioned above to define the influence set representation Lg E {0, 1)", which can be computed by adding the activations of each layer Hμ, summing along the axis of the hidden layer size, and thresholding to get a binary vector:
de
H
Ls
de
where T is the number of layers, and H; Raxx is column from H₃. This vector contains label for each node whose sign indicates if it is predicted to be influenced. We compute the average representation because d, varies throughout layers, and since we add all layer's outputs, we need an equal contribution from each layer's dimension to the final output. We utilize this to compute the difference between the influence of the current seed set and the initial influence of cach other node.
We aim to build a method that learns how to pick seeds sequentially. The model needs to receive information from GLIE regarding the state (graph and seed set), and decide on the next action (seed). Note that, GLIE can not provide direct estimate of new candidate's ' marginal gain without rerunning GLIE(S S U s, G). which is what we try to avoid. To this end, we utilize a double Q-network (Van Hasselt al., 2016) and the model is depicted in Fig. [ During the first step, GLIE provides an IE for all candidate seeds, and the node with the highest is added to the seed set, similar to L.. Subsequently, the Q-network produces a Q-value for each node using as input the estimated influence of the current seed set (S), the initial influence of the node (s)), and the interaction between them. The interaction is defined as the difference between their corresponding influence sets OSS E 1 (L' - L3 2 0). as predicted by GLIE The latter aims to measure how different is the candidate node from the seed set, in order to quantify the potential gain of adding it. The Q-network is called Graph Reinforcement for Influence Maximization (GRIM), and its architecture composed by two layers:
(middle and right part).
We also keep a list of each node's initial influence set
Quu, S,G) = ReL.U o., 0(S, 8) W
where W E R and hd is the hidden layer size. We utilize a greedy policy to choose the next seed, similar to Dai et al. (2017): (u][)) = arg max.es Qu,, S, G). Given the chosen action u, the reward is computed based on the marginal gain, i.e., the estimated influence of the new seed set minus the influence of the seed set before the action, as computed by GLIE in:
r ā(S u)) -(S).
5

---

Under review as a conference paper at ICLR 2022
During training, we use epsilon-greedy to simulate IM "game" and balance between exploration and exploitation. We store as a train tuple the current state-action embedding {ō(S), (s'), (SS,, the new state embedding along with all next possible actions (Ō s), (s), (S, s)}. V and the reward r. Throughout the IM, we randomly sample from the memory and train the parameters of GRIM. GL.I. is frozen, because apart from providing graph and node embeddings, it is only used for the computation of the aeyarddthus it is not updated. The strategy to pretrain a graph encoding layer on supervised task and use it as part of the Q-network has proven beneficial in similar works (Mirhoseini et al. (021). In our case though we found out that without the overlap O and with simpler features such as the degree, the model performs rather poorly, which means we can not alleviate the burden of computing IE for every node in the first step.
3.4 POTENTIALLY UNINFLUENCED NEIGHBORS (PUN)
Computing the influence spread of every node in the first step is too computationally demanding. We thus seek a method that can surpass this hinder and provide adequate performance. We first need to redefine simpler influence set representation then in 7 Let L.s, I's {0, 13"h be the binary vectors with Is in nodes predicted to be uninfluenced and nodes predicted to be influenced respectively:
di
is =
Σ
H S.
I's
Σ
H
(10)
L's is simpler than Ls defined in Eq. and provides a more rough estimate, but it allows for simpler influence spread which we can optimize greedily.
oS)(S) = It'sl
(11)
We can use Ls and message passing to predict the amount of a node's neighborhood that remains un- influenced, i.e., the Potentially Uninfluenced Neighbors (PUN), weighted by the respective probability of influence For node
ms(u]= = Σ
An. = ATT Ls E Rax1
(12)
For efficiency, we can compute ms = L which can be considered an approximation to all nodes marginal gain on their immediate neighbors. We can thus optimize this using argmar(ms)) as shown in Fig, [T. In order to establish that 8t can be optimized greedily with theoretical guarantee of (1 -1- / OPT, we prove its monotonocity and submodularity in Appendix A.2. Theorem 1. The influence spread TThh is submodular and monotone.
PUN can be seen in the left part of Fig. ! We start by setting the first seed as the node with the highest degree, which can be considered safe assumption as in practice it always part of seed sets. We use GLIE(S, G) to retrieve Ls, which we use to find the next node based on arg max,egyy ms [u] and the new L One disadvantage of PUN is that Tt is an underestimation of the predicted influence, as can be seen in Fig. 2 Contrasted with the upper bound, DMP, Tt not as accurate as ô but allows to compute efficiently submodular proxy for the marginal gain. This underestimation means that part of the network considered uninfluenced in Ls is measured as potential gain for their neighbors, hence the ranking based on my can be effected negatively. As we observed in Fig. 2 the divergence of " increases with the size of the seed set.
For this purpose, we will use adaptive full-feedback selection (AFF), where after selecting new seed node, we remove it from the network along with nodes predicted be influenced. It has been proved in the seminal work of Golovin & Krause (201T) that an AFF greedy algorithm for submodular and monotonic function guaranteed have a competitive performance with the optimal policy. In our case, we will use an AFF update every i seeds, as it adds a small computational overhead if we do it in every step. The benefit to PUN is twofold. Firstly, as we remove the influenced node and truncate the seed set, GLIE produces a more valid estimate because it performs better when the graph and seed set are smaller. Secondly, as the neighborhood size decreases, the effect of missed influenced nodes is diminished in ms. These can be observed in the "Adaptive" plots of Fig, 2 (b), (d) and in other related figures in Appendix B, where we employ an AFF every 10 seeds and we contrast the aforementioned gap between the upper bound DMP and r²(())

---

Under review as a conference paper at ICLR 2022
4 EXPERIMENTS
All the experiments are performed in a PC with an NVIDIA GPU TITAN V (I2GB RAM), 256GB RAM and an Intel(R) Xeon(R) W-2145 CPU @ 3.70GHz. The python implementation can be found in the supplementary material.
4.1 INFLUENCE ESTIMATION
For training in the influence estimation task, we create a set of labeled samples, each consisting of the seed set S and the corresponding influence spread (S)) We create 100 Barabasi-Albert Barabási & Albert 1999) and Holme- Kime Holme & Kim (2002) undirected graphs ranging from 100 to 200 nodes and 30 from 300 to 500 nodes. 60% are used for training, 20% for validation and 20% for testing. We have used these network models because the degree distribution resembles the one of real world networks. The influence prohabilities are assigned based on the weighted cascade model, i.e., node u. has equal probability 1 /ddeg(u) to be influenced by each of her M(u) nodes. This model requires a directed graph, hence we turn all undirected graphs to directed ones by appending reverse edges. Though estimating influence probabilities is a problem on its own (Panagopoulos et al. 2020 Du et al. 2014), in the absence of extra data, the weighted cascade is considered more realistic than pure random assignments (Kempe al. 2003). To label the samples, using 1, 000 Monte Carlo (MC) ICs for intluence estimation, for up to seeds. The optimum seed set for size to 5 is stored, along with 30 random negative samples for each seed size. Each sample is accompanied with its ground truth influence spread computed with MC ICs. This amounts to a total of 20, 150 training samples. More details about the training parameters are presented in Appendix B.I
run the CELF algorithm
We evaluate the models in three different types of graphs. The first is the test set of the dataset mentioned above. The second is a set of 10 power-law large graphs (1, 000 2, 000 nodes) to evalu- ate the capability of the model to generalize in networks that are larger by one factor. The third set of three real-world graphs, namely the Crime (CR), HI-11
Graph
# Nodes
# Edges
Large Small Sim
Test/Train
100 500
950 4, 810
Large
1,000 - 2, 000
11,
19, 076
Crime (CR)
829
2, 2,946
HIIII-14 (HI)
4, 165
26, 172
.GR Colab (GR)
5.
28, 980
'Enron (EN)
33, 697
662
Facebook (FB)
63, 393
1,633, 660
Youtube (YT)
1, 134, 891
5,975, 246
14 (HI), and GR collaborations (GR). More information about the datasets is given in Table [T] The real graphs are evaluated for varying seed set sizes, from 2 to 10, to test our model's capacity to extrapolate to larger seed set sizes. Due to the size of the latter two graphs (HI and GR), we take for each seed set size the top nodes based on the degree as the optimum seed set along with 30 random seed sets for the large simulated graphs and 3 for the real graphs, to validate the accuracy of the model in non-significant sets of nodes.
Table 1: Graph datasets.
We have compared the accuracy of influence estimation with DMP (Lokhov Saad 2019). We could not utilize the influence estimation of UBLF (Zhou et al. 2015 because its central condition
Inflowece Difiwrems
Influweee Differmnce
Adaagiioe Bilferrene
Sanid bel 2loz
Sanid aul 2010
Sunid skew
(a)
(b)
(c)
(d)
Figure 2: Difference between DMP influence estimate and o in standard IM and adaptive IM with full feedback every 10 seeds, in two datasets (Crime and GR).
7

---

Under review as a conference paper at ICLR 2022
Graph
DMP
GLIE
(seeds)
MAE
Time
MAE
Time
Test (1 5)
0.076
0.05
0.046
0.0042
Large (1 5)
0.086
0.44
0.102
0.0034
CR (1 -10)
0.009
0.11
0.044
0.0029
HI (1 10)
0.041
2.84
0.056
0.0034
GR (1 10)
0.122
4.32
0.084
0.0042
Table 2: Average mean absolute error (MAE) devided by the average influence and time (in seconds) throughout all seed set sizes and samples, along with the real average influence spread.
Graph
Seed
DMP-CELF
GLIE- CELF
(seeds)
Overlap
Influence
Time
Influence
Time
CR(20)
14
221
83
229
1.0
HI((0)
13
1,235
8, 362
1, 1,281
5.49
GR(20)
12
295
16, 533
393
7.01
Table 3: Influence maximization for 20 seeds with CELF, using the proposed (GLIE) substitute for influence estimation and evaluating with 10, 000 MC independent cascades (IC).
violated by the weighted cascade model and the computed influence is exaggerated to the point surpasses the nodes of the network. The average error throughout all datasets and the average influence can seen in Table [ along with the average time. We evaluate the retrieved seed set using the independent cascade, and the results are shown in Table 3 We should underline here that this task would require more then 3 hours for the Crime dataset and days for GR using the traditional approach with 1, 000 MC IC. As we can see in Table GLIE-CELF allows for a significant acceleration in computational time, while the retrieved seeds are more effective. Moreover, in CELF, the majority of time is consumed in the initial computation of the influence spread, i.e., the overhead to compute 100 instead of the 20 seeds shown in Table amounts to 0.11, 0.22 and 0.19 seconds for the three datasets respectively.
4.2 INFLUENCE MAXIMIZATION
The training parameters for GRIM are analyzed in Appendix B (..I.. For comparison, we use state-of-the-ard arr IM method, IMM Tang et al. 2013) which capitalizes reverse reachable sets (Borgs et al. 2014) to estimate influence. Specifically. it produces a series such influence sketches and uses them approximate the influence spread without any simulation when building the seed set. This results in remarkable acceleration while retaining a theoretical guarantee with high probability. Note that, IMM is considered state-of-the-ar and has similar influence spreads with Tang et al. (2014). while surpassing various heuristics (Jung et al. 2012). We set = 0.5 as proposed by the authors. We also compare with FINDER, which analyzed Section 2 and with the most well known heuristic
methods for the Independent Cascade PMIA (Wang et al. 2012) DEGREEDISCOUNT (Chen et al.
2009 and K-CORES (Malliaros et al. 2020
Graph
GLIE-CELF
GRIM
PUN
K-CORE
PMIA
DEGDISC
IMM
FINDER
CR
522
509
521
455
520
512
516
502
GR
1,102
997
1,076
421
1,013
919
1,085
897
2,307
1,302
2,308
2, 02024
2, 2,229
2,290
2,274
EN
14,920 920
14, 022
14,912
10,918
14, 855
13, 808
14,848
12, 596
FB
8, 8,710
7,418
8,409
4,174
613
8,247
625
746
YT
189, 515
187, 808
187, 808
89,546
189, 746
194, 834
194, 521
34, 941
Table Influence spread computed by 10,000 MC ICs for 100 seeds.
The results for the influence spread of 100 and 200 seeds as computed by simulations of MC ICs can be seen in Table 4 and (5). while the time results shown in Table The top result is in bold and the second best is underlined. The influence spread for smaller seed sets and the time for heuristics attached in Appendix C, along with comparisons of PUN without the use of GPU. One can
8

---

Under review as a conference paper at ICLR 2022
Graph
CELF
GRIM
PUN
K-CORE
PMIA
DEGDISC
IMM
FINDER
CR
661
650
657
647
656
644
650
642
GR
1,617
1,502
1, 1,626
701
1, 1,566
1415
1,617
1,286
HI
2, 6.5
2,631
2, 688
2,540
685
2,614
2, 666
6.625
EN
17, 601
16, 642
17, 614
13,
17, 534
16, 500
17, 497
17. 244
FB
981
9,406
626
6, 6,431
7, 688
10,309
11, 11.007
10, 801
YT
439
000
244, 579
110, 409
242, 057
236, 726
247. 178
50, 435
Table 5: Influence spread computed by 10,000 MC ICs for 200 seeds.
seeds
200 seeds
Graph
GLIPP-CELF
FINDER
GLIF-CELF
FINDER
CR
1.25
0.91
0.15
0.13
0.41
2.00
2.03
0.25
0.19
0.41
GR
3.41
0.69
0.17
0.57
2.36
4.55
1.79
0.26
0.95
2.36
HI
1.20
2.59
0.17
0.56
1.01
2.19
0.60
0.27
1.29
1.01
EN
5.89
4.85
0.52
4.78
9.30
15.49
5.49
0.97
10.47
9.30
120.6
100.00
1.42
69.90
56.8
287.7
123.95
3.1
171.25
56,80
YT
119.00
48.00
13.20
55.40
191.00
151.33
100.00
28.92
82.13
191.00
Table 6: Computational time in seconds.
that GLIE-CELA exhibits overall superior influence quality compared to the rest of the methods, but is quite slower. GRIM is slightly faster than GLIE- CEEF but is the second slowest method. This quantifies the substantial overhead caused by computing the influence spread all candidate seeds in the first step. Their time difference amounts to how many step compared to GRIM, which performs only one. This is more obvious with PUN, which requires only one IE every step and no initial computation. is from 3 to 60 times faster than IMM while its computational overhead moving from smaller to larger graphs is less than linear to the number of nodes. In terms of influence quality, PUN is first or second in the majority of the datasets both seed set sizes. We can thus contend that it provides the best accuracy -ffrracc-fffcinccy tradeoff from the examined methods. IMM the third slowest method, but is very accurate, specially for smaller seed set sizes. FINDER exhibits the least accurate performance, which is understandable given that it solves a relevant problem and not exactly IM for IC. The computational time presented is the time required to solve the node percolation, in which case it may retrieve bigger seed set than 100 nodes. Thus, we can hypothesize it quite faster for limited seed set, but the quality of the retrieved seeds is the least accurate among all methods.
IEs GL.EE CELF performs in every
CONCLUSION
We have proposed GLIE, a GNN-based solution for the problem of influence estimation. We showcase its accuracy in that task and utilized it to address the problem of influence maximization. We developed three methods based on the representations and the predictions of GLIE. LLIE-CELF, adaptation of classical algorithm that surpasses SOTA but with significant computational overhead. GRIM, a Q- learning model that learns retrieve seeds sequentially using GLIE'S predictions and representations. And PUN, a submodular function that acts as proxy for the marginal gain and can be optimized adaptively, striking balance between efficiency and accuracy.
A typical IM algorithm needs significant contribution in order to take into account the topic of the information shared or the user's characteristics (Chen et al. 2016) i.e.. conditional diffusion. An important practical ad advantage of neural network approach is the easy incorporation of such complementary data by adding the corresponding embeddings in the input, as has been done in similar settings (Tian et al. 2020). We thus deem experiment with contextual information natural next step, given a proper dataset. Our approach can also be utilized address the minimum vertex cover in large graphs, it is problem related to influence maximization and there exists models that work well in both MManchanda et al. 2020). Finally, we also plan to examine the potential training online the reinforcement learning, i.e., receiving real feedback from each step of the diffusion that could update both, the Q-NET and GLIE. This would allow the model to adjust its decisions based on the partial feedback received during the diffusion.

---

Under review as a conference paper at ICLR 2022
Ethics and Reproducibility Our influence maximization methods potentially be used for large scale manipulation in social media. For example, targeting the right susceptible users with specific political advertisements might maximize the effect of the campaign the general intent to vote. On the bright side, there has been extensive research on batrling such effects (Tu et al.] 2020), by producing campaigns that equally effective and hence balancing each other (Bharathi al. 2007). More importantly, GLIE can be used as part of the mitigation strategy (Tu et al.] 2020). as black box that substitutes the method's RR-set based influence estimation, actually increase the balance of political exposure in the given social network for the running campaigns. Moreover, our methods can inherently be utilized in the context of limiting fake news spreading similar other influence maximization algorithms (Budak et al. 2011).
Regarding the reproducibility of our experiments, we have attached codes the supplementary files along with detailed instructions on how to reproduce the results. We also point to the codes we utilized to run the benchmarks. All data can be downloaded through an anonymous repository.
REFERENCES
Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. science, 286 (5439):509-512, 1999.
Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv: 1.09940, 2016.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d' horizon. European Journal of Operational Research, 2020.
Shishir Bharathi, David Kempe, and Mahyar Salek. Competitive influence maximization in social networks. In International workshop web and internet economics, pp. 306-311. Springer, 2007.
Christian Borgs, Michael Brautbar, Jennifer Chayes, and Brendan Lucier. Maximizing social influence in nearly optimal time. Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pp. 946-957. SIAM, 2014.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Ceren Budak, Divyakant Agrawal, and Amr El Abbadi. Limiting the spread of misinformation in social networks. In Proceedings of the 20th international conference on World wide web, pp.
665-674, 2011.
Wei Chen, Yajun Wang, and Siyu Yang. Efficient influence maximization in social networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 199-208, 2009.
Wei Chen, Tian Lin, and Cheng Yang. Real-time topec-aware influence maximization using prepro- cessing. Computational social networks, 3(1):1-19, 2016.
Hanjun Dai, Elias Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. arXiv preprint 1eX.v:/704.0160 2017.
Pedro Domingos and Matt Richardson. Mining the network value of customers. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 57-66, 2001.
Nan Du, Yingyu Liang, Maria Balcan, and Le Song. Influence function learning in information diffusion networks. In International Conference Machine Learning, pp. 2016-2024. PMLR, 2014.
Changjun Fan, Li Zeng, Yizhou Sun, and Yang- Yu Liu. Finding key players in complex networks through deep reinforcement learning. Nature Machine Intelligence, pp. 1-8, 2020.
Daniel Golovin and Andreas Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research, 42:427-445 486. 2011.
10

---

Under review as a conference paper at ICLR 2022
Petter Holme and Beom Jun Kim. Growing scale-free networks with tunable clustering. Physical review E, 65(2):026107, 2002.
Gareth James, Daniela Witten, Trevor Hastie, and Robert Tibshirani. An introduction to statistical learning, volume 112. Springer, 2013.
Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. On learning paradigms for the travelling salesman problem. arXiv preprint WrXiv:9100007200, 2019.
Kyomin Jung, Wooram Heo, and Wei Chen. Irie: Scalable and robust influence maximization in social networks. 2012 IEEE 12th International Conference on Data Mining, pp. 918-923. IEEE, 2012.
Nikolaos Karalias and Andreas Loukas. Erdos goes neural: unsupervised learning framework for combinatorial optimization on graphs. arXiv preprint arXiv:2006. 10643, 2020.
David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 137-146, 2003.
Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn to solve routing problems! arXiv preprint arXiv:1803.004 08475, 2018.
Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie Glance. Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 420 429, 2007.
Hui Li, 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.07377 2019.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. arXiv preprint arXiv: 1r0iv:1810.10659, 2018.
Andrey Y Lokhov and David Saad. Scalable influence estimation without sampling. arXiv preprint arXiv: 12749, 2019.
Fragkiskos D Malliaros, Christos Giatsidis, Apostolos N Papadopoulos, and Michalis Vazirgiannis. The core decomposition of networks: Theory, algorithms and applications. The VLDB Journal, 29 (1):61-92, 2020.
Sahil Manchanda, Akash Mittal, Anuj Dhawan, Sourav Medya, Sayan Ranu, and Ambuj Singh. Gcomb: Learning budget-constrained combinatorial algorithms over billion-sized graphs. Advances in Neural Information Processing Systems, 33, 2020.
Neil Mathew, Stephen L Smith, and Steven Waslander. Planning paths for package delivery in heterogeneous multirobot teams. IEEE Transactions Automation Science and Engineering, 12 (4):1298-1300) 2015.
Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Wenjie Jiang, Ebrahim Songhori, Shen Wang, Young-Joon Lee, Eric Johnson, Omkar Pathak, Azade Nazi, et al. A graph placement methodology for fast chip design. Nature, 594(7862)2207-212, 2021.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):529-553 -33,, 2015.
George Panagopoulos, Fragkiskos Malliaros, and Michalis Vazirgiannis. Multi-task learning for influence estimation and maximization. IEEE Transactions on Knowledge and Data Engineering, 2020.
Marcelo Prates, Pedro HC Avelar, Henrique Lemos, Luis C Lamb, and Moshe Y Vardi. Learning to solve np-complete problems: A graph neural network for decision tsp. In Proceedings of the AAA! Conference Artificial Intelligence, pp. 3731-4738. 2019.

---

Under review as a conference paper at ICLR 2022
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Youze Tang, Xiaokui Xiao, and Yanchen Shi. Influence maximization: Near-optimal time complexity meets practical efficiency. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data, pp. 75-86, 2014.
Youze Tang, Yanchen Shi, and Xiaokui Xiao. Influence maximization near-linear time: martingale approach. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, pp. 1539-15544 2015.
Shan Tian, Songsong Mo, Liwei Wang, and Zhiyong Peng. Deep reinforcement learning- -basd approach tackle topic-aware influence maximization. Data Science and Engineering, 5(1):1-11, 2020.
Nora Touati-Mounghe and Vincent Jost. Combinatorial optimization for electric vehicles management. Journal of Energy and Power Engineering. 6(5):738-743, 2012.
Sijing Tu, Cigdem Aslay, and Aristides Gionis. Co-exposure maximization online social networks. Advances in Neural Information Processing Systems, 33, 2020.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. Proceedings of the AAAI Conference on Artificial Intelligence, 2016.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. 1506003366 2015.
Pointer networks.
arXiv preprint
Chi Wang, Wei Chen, and Yajun Wang. Scalable influence maximization for independent cascade model in large-scale social networks. Data Mining and Knowledge Discovery, 25(3):545-576, 2012.
Christopher J. C. H. Watkins and Peter Dayan. Q-learning. In Machine Learning, pp. 279-292, 1992.
Bryan Wilder, Amulya Yadav, Nicole Immorlica, Eric Rice, and Milind Tambe. Uncharted but not uninfluenced: Influence maximization with uncertain network. In AAMAS, volume 17, pp. 1305-1313,2011
Bryan Wilder, Han Han-Ching Ou, Kayla de la Haye, and Milind Tambe. Optimizing network structure for preventative health. In AAMAS, pp. 841-849, 2018
Chuan Zhou, Peng Zhang, Wenyu Zang, and Li Guo. On the upper bounds of spread for greedy algorithms in social network influence maximization. IEEE Transactions on Knowledge and Data Engineering, 27(10):277--7788 2015.
12

---

Under review as a conference paper at ICLR 2022
SUPPLEMENTARY MATERIAL: LEARNING GRAPH REPRESENTATIONS FOR INFLUENCE MAXIMIZATION
Appendix A gathers the proof' of theorems and corollaries, appendix B includes the training details and plots in support of the arguments in the main text, and finally, appendix shows extra results.
APPENDIX A
We recall the first corollary from Sec. B and detail the proof below.
Corollary 3.0.2. The repeated product H4+1 = A H, computes an upper bound to the real inftuence probabilities of each infected node at step + 1.
Proof. We have:
(u(S") Aa H.
(13)
E
PoPru
(14)
(EN(w))8
Σ n
PoPeu
(15)
II vEN(u)nS'
(1 --Povaa
(16)
S*
(17)
(18)
15
stems from Eq. 3 in the manuscript:
S(u[S)= An X
Pou 21
II vEN(a))S
(1 - Pom) = p)u(S).
deg(u)
vEN(u)ns
DEN(u)nS
(19)
16) can be proved by induction similar Zhou al. (015). For every Pe 1 the base
LEx PoPeu
ΠIxx (1 PoPeu) is obvious for X 1. For | > 1, we have:
- II (1 DrPou) 1 (1 PZPru)
II (1 PuPou)
3E
vE
II (1 - PoPou) + +PPra
II (1 - PuPwu)
vEXia
II (1 PvPmu)
PoPou PzPra
a
vEX
< Σ PoPva + P=Pzu
Σ
PePea.
(20)
FE
17 we have p(ulv) PePeu per definition of the independent cascade, and consequently p(u[S) = for S1, which are the initial seed set that are
IIVENtwgns (1 PoPvu). where p. activated deterministically. We can thus contend that Eq. equation T8 stands, and the computed probabilities are an upper bound of the real influence probabilities. Hence the influence spread, which is computed d(S) Σ E(u,e)EB Pue also an upper bound the real (S)).
13

---

Under review as a conference paper at ICLR 2022
Now address the Theorem from Sec. 3.4 and detail the proof below.
Theorem 1. The influence spread t submodular and monotone.
For the purposes of the proof, X; E {0, 1 is the input and H; E R RaxAd is the output of the first neural layer for the imput seed St and P E {1] [1]idx] Moreover
define the support function the set of indices of non zero rows in matrix
supp(v) {i E [1, ra|, + 0} James et al. (2033) such as X, Finally let R represent ReLU and bir, sky the mean and standard deviation computed by the batchnorm. Each step is justified further below.
Proof. Monotonocity, Vi <. C.:
dddn kuppl (X,) 5 suppl
(21)
supp X, (WW) 3 supp(
(22)
suppl AX, () C AX
(23)
supp R(AX, ())
supp R ((AX,W)
(24)
R(AX, W) ber
(R(AX,W) - btr)
supp
(25)
279
star
Ains Hupp(Hs (H 2 suppl (S())
(26)
supp(H, (
2 supp(H,P)
(27)
oet (H,P) 2 |1>0 (H,P)
(28)
[2/] 2 14/1 th (S,) 2 om
(29)
(30)
(31)
21 stems by the definition of in Eq.
(2 Xj convex hull that contains X; (Boyd al. 2004). We multiply both sides by a real matrix W Rdxhd which can equally dilate both convex hulls in terms of direction and norm. This equal transformation cannot change the sign of the difference between the elements of X; and X, and hence cannot interfere with the support of X, over X,. The statement becomes more obvious for X {0, 1xx1 and W R1x1, Note that both result in matrices subset or equal.
23
A is non-negative matrix.
24
ReLU is a non negative monotonically increasing function.
5.
25
Subtract by the same number and divide by the same positive number.
26
Definition in Eq.
27
P is positive.
28
By definition of the support.
9.
29
By definition of I's.
For the proof of submodularity we have to define X,,, = Xs.uur u E and note by the definition of the input that Xin- X,1 X X,| for the norm (sum of all elements):
14

---

Under review as a conference paper at ICLR 2022
Proof. Submodularity vi < j.S. C Si
XX tu X51 Xi Xil
(32)
A|X,, ju Xj1 A|X X,
(33)
IA(X,u Ju - X,)1 = JA(Xia X,)
(34)
|AX - ,X,1 [AX AX;
(35)
AA W - AX,WI = |AXin W - -
(36)
R[JAX,, W AX, WI) 2brr R(JAX,,, - 2brr)
(37)
IR(AX W) - R(AXWW) - 2barl = |R(AX, W) -((X, 2brr
(38)
Supp(R(AX)) (RAXXx W) - R(AX, W) 2brr) supp( RC ((AX: W) R(AX,W)
2bbr)
(39)
supp(R(AAXuul) W- - ber)) -uupp( (((X))(())))))) - b(r) S suppl R(AX - b(T)) suppl R(AX,W)) ber)
(40)
suppl (u) supp H3) C suppl - supp Hi)
(41)
Tm (S) U
Tth (5') -" S 8Th (5* u (2)) 0 (8")
(42)
(43)
1. Distributive property
(36) Similar to multiplication by A.
3. 40
The norm of the difference is distributed equally, but the right hand difference has as least the same or more positive elements because the of which is stochastic jis bounded by V hence X, can give up to the same gain to AX, and AX, the same number bt is subtracted, and more elements are activated by Xy then X; as shown Eq. 29
We skipped dividing by st,, for brevity.
Arrive with similar steps as
30
Regarding the approximation of the marginal gain we first show that choosing the node corresponding to the maximum my will give the maximum T//u"= Ar,. 2 A' π.
A = Σ Auoiyol-
Σ AmoLilul= Σ Auu
(44)
vEN(u)
eEN(u)
vEN(u)
(45)
This means that my gives the node u that improves the biggest number of rows in AX ju that are not
already considered influenced. Since we know from eq. 30 that AX 2 AX + 1.u 2 [4
the claim concludes. Hence choosing the best node using the marginal gain approximation is as good as the real influence spread. Now we prove the submodularity of the proposed marginal gain.
Proof. Submodularity for the approximation of the marginal gain, Vi <. C Sy. starting from 28
1>> [H 2 1 (H,P)
1 1o (H,P) - [1go (H,P)
(46)
A,I, < ALL.
(47)
ms, [u] S ms.[u]
(48)
(14') ms, [w]) 14/ < ((44) + ms (u] 1471
(49)
r' (u)) ( s (
(50)
15

---

Under review as a conference paper at ICLR 2022
1.
30
Complementarity between elements that are 0 and elements >> 0.
2.
32
Definition in Eq. 10 and multiply with non-negative row from matrix A'.
33
Definition in Eq. 12
34
Adding and subtracting [4y] and [aa--
By definition of nt in Eq. and the marginal gain of u, we arrive at submodularity in Eq.
APPENDIX B
B. TRAINING
As mentioned in the main text each training sample for GLIE corresponds to triple of a graph G seed set and ground truth influence spread (S)) that serves as a label to regress on. We use two different ways come up with the seed sets 5 for varying sizes of S from to 5. We seed sets in order to capture the average influence spread expected for a seed set of about that size, This creates "average samples" which would constitute the whole dataset in other problems. In IM however, the difference in a between an average seed set and the optimum seed set can be significant, hence training solely on the random sets would render our model unable to predict larger values that correspond to the optimum. We thus add in the samples the optimum seed set for each size, taken using Celf and MC ICs for influence estimation. For each size, we have the 30 random seed sets and the optimum, which is more balanced form of supervision, as you expect the crucial majority of the seed sets to have an average a. Regarding the training procedure, we have used a small scale grid-search using the validation set to find the optimum batch size 64, dropout 0.4, number of layers 2. hidden layer size 64, and feature dimension 50. More importantly, we observed that is beneficial to decrease the hidden layer size (by a factor of 2) as the depth increases, i.e., go from 32 to 16. This means that the 1-hop node representations are more useful compared to the 2-hop ones and so on validating the aforementioned conclusion that the approximation to the influence estimation in Eq. 3 diverges more as the message passing depth increases. The training then proceeds for 100 epochs with an early stopping of 50 and learning rate of 0.01.
random
GRIM is trained on a dataset that consists of 50 random BA graphs of 500 2, 000 nodes. It trained by choosing 100 seeds sequentially, maximize the reward (delay steps) for each network. Since the immediate reward corresponds to the marginal gain, the sum of these rewards at the end of the "game" corresponds to the total influence of the seed set. An episode corresponds to completing the game for all 50 graphs; we play 500 episodes, taking roughly 40 seconds each. The exploration is set to 0.3 and declines with a factor of 0.99. The model is optimized using ADAM, as in GLIE. We store the model that has the best average influence over all train graphs in training episode. In order to diminish the computational time of the first step in GLIE-CELF and GRIM, we focus on candidate seeds that surpass certain degree threshold based on the distribution, common practice in the literature (Chen et al., 2009 Manchanda et al. 2020).
16

---

Under review as a conference paper at ICLR 2022
B.2 ADAPTIVE FULL FEEDBACK
We see in Fig. that the pattern that is prevalent in the two datasets described in Section 3 3.4 is retained in other graphs.
Influence Difference Enron
Adaptive Influence Difference Enron
5000
oth
d
12000
20000
NNdes
3000
0000
6000
1000
2000
20
100
Seed set size
Seed set size
(a)
(b)
Influence Difference
Adaptive Influence Difference HT
2000
offt
600
Nodes
Nodes
1013
1003
100
0-
20
150
100
Seed set size
Seed set size
(c)
(d)
Figure 3: Difference between DMP influence estimate and Tt in regular and adapting with full feedback every 10 seeds.
B.3 GLIE SUBMODULARIT AND MONOTONICITY
In this section we design an experiment to empirically prove that GLIE'S output submodular and monotonous. For each of the real datasets, we use the seed set retrieved by GLIE-CELF and a random seed set quantify the differences between subsequent estimations. To be specific, we have a sequence S that represents the seed set and sequence R that represents the random nodes, with S, being the seed set up to jth element and 8j being the j"h element, and similarly rj for R. We compute the marginal gain to check for monotonicity:
mss = (S, U U8)+1) - (S})
(51)
Mar = 6(S, U 11)+1) - -((S),
(52)
and for submodularity, we have, with 1
Sea (ō(S, U Us411) o(S))) (6(S) U U8j+1) - -(S)))
(53)
Sar (6(S) - (0(3)) -
(54)
In Figures too 7 we plot m and s for some of our datasets. Regarding 8, since we require constant node, we randomly sample one of the seeds s, and a random node r, and visualize the sequences of both with regard to adding them in every step. The values of these functions correspond to nodes, and range from tens to thousands, depending on the datasets. For monotonicity and submodularity. verify that m and are always more than zero. Moreover, we see that they decrease with the size of the seed set, as well as the observation that adding a random seed provides worst marginal gains ( in monotonicity plots) than adding the chosen seed.
17

---

Under review as a conference paper at ICLR 2022
Montonnicity CR
Submedularity CR
35s
15
# Nodes
*
8o Seed set size
40
Seed set size
50
Figure 4: Monotonicity and submodularity for the Crime (CR) dataset.
Monotonicity
Submodularity
160
my
120
N00065
100-
Nodes
6-
0-
40
80
Seed set size
Seed set size
Figure 5: Monotonicity and submodularity for the H1-II-14 (HI) dataset.
Monatonicity EN
Submodularity EN
250
200
NoaRS
150
100-
100
30
50-
Seed set
Seed set size
Figure 6: Monotonicity and submodularity for the Enron (EN) dataset.
Submodularty
Monotonicity
50-
Nodes
40-
3.5
132-
56-
0-
Seed sct
Seed
Figure 7: Monotonicity and submodularity for the Facebook (FB) dataset.
18

---

Under review as a conference paper at ICLR 2022
B.4 IMM AND PUN WITH UNIFORM PROBABILITIES
We compare IMM and PUN on the same graphs with uniform influence probabilities = 0.01 in Figure
We clearly observe that PUN outperforms IMM.
BA1 MUN
223
130
100
VELeco
100
100
200
(b)
CM
Bood Set
Good
SAV PUN
PMM FUN
2500
10000
2000
7500
0000
1000
500
20
100
200
20
1000
400
(c)
(f)
Figure PUN vs. IMM for with p = 0.01.
19

---

Under review as a conference paper at ICLR 2022
APPENDIX C
C.5 RESULTS FOR SMALLER SEED SETS
Graph
GLIE-CELF
GRIM
K-CORE
PMIA
DEGDISC
IMM
FINDER
CR
228
232
227
126
224
227
228
232
GR
402
208
374
184
342
272
387
379
HI
1,300
1,304
1,307
866
1,274
1,234
1,316
1,0
EN
889
8, 185
8, 2,2
5741
8, 3,041
7,988
8, 202
3, 3,964
FB
4. 4.487
4, 480
4,263
1594
2491
4,489
4,481
1, 1,823
YT
105, 897
104, 824
104, 106
67, 084
97, 622
104, 706
105, 888
799
Table 7: Influence spread computed by 10,000 MC ICs for 20.
Graph
GLIE-CELF
GRIM
PUN
K-CORE
PMIA
DEGDISC
IMM
FINDER
CR
381
371
378
263
378
368
375
367
GR
738
553
700
303
654
556
725
635
HI
1,914
1, .905
1,908
1,407
1, 199
1,824
1, 589
1,904
EN
11,819
11,
157
9, 796
11,
11,
10, 10,698 698
7.333
FB
6,631
5, 5,879
6, 6,329
2,974
6,574
4,489
6, 724
5, 6,649
YT
M7,631
148,
145, 796
78, 575
145, 863
143, 161
148, 597
9, 152
Table 8: Influence spread computed by 10,000 MC ICs for 50.
C.6
COMPUTATIONAL TIME OF HEURISTICS
100 seeds
200 seeds
Graph
PMIA
DEGDISC
K-CORE
PUN
PMIA
DEGDISC
K-CORE
PUN
CR
0.13
0.04
0.04
0.15
0.21
0.06
0.04
0.25
GR
0.70
0.12
1.5
0.17
0.80
0.13
1.5
0.26
HI
1.24
0.13
0.12
0.17
1.36
0.14
0.12
0.27
EN
24.83
1.96
2.17
0.52
26.74
2.06
2.17
0.97
FB
21.2
8.86
10.62
1.42
22.77
9.29
10.62
3.1
YT
3838.5
52.39
74.91
13.2
4006.29
54.38
74.91
28.92
Table 9: Computational time of heuristic approaches compared to PUN.
C.7
PUN'S COMPUTATIONAL TIME WITHOUT GPU
We performed experiments to compare PUN without the use of GPU in Table 10 where is visible that GPU provides substantial acceleration, but PUN remains the faster option without it.
Graph
PUN GPU
PUN CPU
IMM
CR
0.15
0.17
0.13
GR
0.17
0.27
0.57
HT
0.17
0.20
0.56
EN
0.52
2.44
4.78
FB
1.42
17.5
69.9
YT
13.2
97.5
55.4
Table 10: Comparison between PUN CPU and GPU computational times for 100 seeds.
C.8 RELATIVE ERROR OF GLIE FOR LARGER SEED SETS
To quantify the potential GLIE for larger seed sets, we sample random seed sets and with the highest degree nodes and compute the error of DMP and GLIE, with the ground truth influence
20

---

Under review as a conference paper at ICLR 2022
divided by the average influence in Table 1I the seed set increases, and that GLIE outperforms DMP in GR while the reverse happens in CR and HT.
We see that the error does not increase significantly as
Graph
Seeds
DMP
GLIE
CR
20
0.005
0.031
CR
50
0.006
0.059
CR
100
0.017
0.152
GR
20
0.161
0.029
GR
50
0.125
0.042
GR
100
0.093
0.082
HT
20
0.010
0.105
HT
50
0.004
0.062
HT
100
0.002
0.113
Table 11: Relative error for diffusion prediction of larger seed sets.
21


Reviews:
[{"review_id": "lfe7YcmxCOg", "reviewer": "Reviewer_et7w", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\n$\\textbf{Strength:}$ \n-\tUsing GNN for learning representations is a reasonable choice\n-\tThis paper is technically sound. \n-\tConstructing a submodular score function based on the learned representation is also an interesting idea. \n\n$\\textbf{Weakness:}$\n\nUsing 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.  \n\n[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).\n\n[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.\n\n[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.\n\n[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.\n\nThe experiments do not demonstrate a strong need for learning-based methods for influence estimation or influence maximization. \n\n- 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.\n\n- 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. \n\n[e] Debunking the myths of influence maximization: An in-depth benchmarking study\n\n- 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.\n\nThe 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). \n\nMinor questions:\n- What does negative sample mean in Sec4.1?\n\n- 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. \n", "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.  ", "summary_of_the_review": "The proposed technique is not very novel, and its practical utility needs better justification. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "SOzXoIMw5jZ", "reviewer": "Reviewer_GuP1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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_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 ", "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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Nqe0muKnGep", "reviewer": "Reviewer_F6tB", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nAnother 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.\n\nOne 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.\n\nAlso, 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.\n\nLastly, 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_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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "7d82RN2SI5h", "reviewer": "Reviewer_caQs", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength\n1. It is an interesting and practical idea to consider learning-based approach for cascade problems on social networks.\n2. The authors carry out experiments on several networks (both synthetic and real-world) with reasonable large number of nodes (>1M).\n\nWeakness\n1. 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.\n2. 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.\n3. 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.\n4. 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. \n", "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. ", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

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