summaries: 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. 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.  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.   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 
abstractText: 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 effected 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.
references.authors: Albert-László Barabási Réka Albert
references.title: Emergence of scaling in random
references.venue: networks. science,
references.authors: Irwan Bello Hieu Pham Quoc V Le Mohammad Norouzi Samy Bengio
references.title: Neural combinatorial optimization with reinforcement learning
references.venue: arXiv preprint arXiv:1611.09940,
references.authors: Yoshua Bengio Andrea Lodi Antoine Prouvost
references.title: Machine learning for combinatorial optimization: a methodological tour d’horizon
references.venue: European Journal of Operational Research,
references.authors: Shishir Bharathi David Kempe Mahyar Salek
references.title: Competitive influence maximization in social networks
references.venue: In International workshop on web and internet economics,
references.authors: Christian Borgs Michael Brautbar Jennifer Chayes Brendan Lucier
references.title: Maximizing social influence in nearly optimal time
references.venue: In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms,
references.authors: Ceren Budak Divyakant Agrawal Amr El Abbadi
references.title: Limiting the spread of misinformation in social networks
references.venue: In Proceedings of the 20th international conference on World wide web,
references.authors: Wei Chen Yajun Wang Siyu Yang
references.title: Efficient influence maximization in social networks
references.venue: In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining,
references.authors: Wei Chen Tian Lin Cheng Yang
references.title: Real-time topic-aware influence maximization using preprocessing
references.venue: Computational social networks,
references.authors: Hanjun Dai Elias B Khalil Yuyu Zhang Bistra Dilkina Le Song
references.title: Learning combinatorial optimization algorithms over graphs
references.venue: arXiv preprint arXiv:1704.01665,
references.authors: Pedro Domingos Matt Richardson
references.title: Mining the network value of customers
references.venue: In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining,
references.authors: Nan Du Yingyu Liang Maria Balcan Le Song
references.title: Influence function learning in information diffusion networks
references.venue: In International Conference on Machine Learning,
references.authors: Changjun Fan Li Zeng Yizhou Sun Yang-Yu Liu
references.title: Finding key players in complex networks through deep reinforcement learning
references.venue: Nature Machine Intelligence,
references.authors: Daniel Golovin Andreas Krause
references.title: Adaptive submodularity: Theory and applications in active learning and stochastic optimization
references.venue: Journal of Artificial Intelligence Research,
references.authors: Petter Holme Beom Jun Kim
references.title: Growing scale-free networks with tunable clustering
references.venue: Physical review E,
references.authors: Gareth James Daniela Witten Trevor Hastie Robert Tibshirani
references.title: An introduction to statistical learning, volume
references.authors: Chaitanya K Joshi Thomas Laurent Xavier Bresson
references.title: On learning paradigms for the travelling salesman problem
references.venue: arXiv preprint arXiv:1910.07210,
references.authors: Kyomin Jung Wooram Heo Wei Chen. Irie
references.title: Scalable and robust influence maximization in social networks
references.venue: In 2012 IEEE 12th International Conference on Data Mining,
references.authors: Nikolaos Karalias Andreas Loukas
references.title: Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs
references.venue: arXiv preprint arXiv:2006.10643,
references.authors: David Kempe Jon Kleinberg Éva Tardos
references.title: Maximizing the spread of influence through a social network
references.venue: In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining,
references.authors: Wouter Kool Herke Van Hoof Max Welling
references.title: Attention, learn to solve routing problems
references.venue: arXiv preprint arXiv:1803.08475,
references.authors: Jure Leskovec Andreas Krause Carlos Guestrin Christos Faloutsos Jeanne VanBriesen Natalie Glance
references.title: Cost-effective outbreak detection in networks
references.venue: In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining,
references.authors: Hui Li Mengting Xu Sourav S Bhowmick Changsheng Sun Zhongyuan Jiang Jiangtao Cui
references.title: Disco influence maximization meets network embedding and deep learning
references.authors: Zhuwen Li Qifeng Chen Vladlen Koltun
references.title: Combinatorial optimization with graph convolutional networks and guided tree search
references.venue: arXiv preprint arXiv:1810.10659,
references.authors: Andrey Y Lokhov David Saad
references.title: Scalable influence estimation without sampling
references.venue: arXiv preprint arXiv:1912.12749,
references.authors: Fragkiskos D Malliaros Christos Giatsidis Apostolos N Papadopoulos Michalis Vazirgiannis
references.title: The core decomposition of networks: Theory, algorithms and applications
references.venue: The VLDB Journal,
references.authors: Sahil Manchanda Akash Mittal Anuj Dhawan Sourav Medya Sayan Ranu Ambuj Singh
references.title: Gcomb: Learning budget-constrained combinatorial algorithms over billion-sized graphs
references.venue: Advances in Neural Information Processing Systems,
references.authors: Neil Mathew Stephen L Smith Steven L Waslander
references.title: Planning paths for package delivery in heterogeneous multirobot teams
references.venue: IEEE Transactions on Automation Science and Engineering,
references.authors: Azalia Mirhoseini Anna Goldie Mustafa Yazgan Joe Wenjie Jiang Ebrahim Songhori Shen Wang Young-Joon Lee Eric Johnson Omkar Pathak Azade Nazi
references.title: A graph placement methodology for fast chip
references.venue: design. Nature,
references.authors: Volodymyr Mnih Koray Kavukcuoglu David Silver Andrei A Rusu Joel Veness Marc G Bellemare Alex Graves Martin Riedmiller Andreas K Fidjeland Georg Ostrovski
references.title: Human-level control through deep reinforcement learning
references.authors: George Panagopoulos Fragkiskos Malliaros Michalis Vazirgiannis
references.title: Multi-task learning for influence estimation and maximization
references.venue: IEEE Transactions on Knowledge and Data Engineering,
references.authors: Marcelo Prates Pedro HC Avelar Henrique Lemos Luis C Lamb Moshe Y Vardi
references.title: Learning to solve np-complete problems: A graph neural network for decision tsp
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Richard S Sutton Andrew G Barto
references.title: Reinforcement learning: An introduction
references.venue: MIT press,
references.authors: Youze Tang Xiaokui Xiao Yanchen Shi
references.title: Influence maximization: Near-optimal time complexity meets practical efficiency
references.venue: In Proceedings of the 2014 ACM SIGMOD international conference on Management of data,
references.authors: Youze Tang Yanchen Shi Xiaokui Xiao
references.title: Influence maximization in near-linear time: A martingale approach
references.venue: In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data,
references.authors: Shan Tian Songsong Mo Liwei Wang Zhiyong Peng
references.title: Deep reinforcement learning-based approach to tackle topic-aware influence maximization
references.venue: Data Science and Engineering,
references.authors: Nora Touati-Moungla Vincent Jost
references.title: Combinatorial optimization for electric vehicles management
references.venue: Journal of Energy and Power Engineering,
references.authors: Sijing Tu Cigdem Aslay Aristides Gionis
references.title: Co-exposure maximization in online social networks
references.venue: Advances in Neural Information Processing Systems,
references.authors: Hado Van Hasselt Arthur Guez David Silver
references.title: Deep reinforcement learning with double qlearning
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Chi Wang Wei Chen Yajun Wang
references.title: Scalable influence maximization for independent cascade model in large-scale social networks
references.venue: Data Mining and Knowledge Discovery,
references.authors: Bryan Wilder Amulya Yadav Nicole Immorlica Eric Rice Milind Tambe
references.title: Uncharted but not uninfluenced: Influence maximization with an uncertain network
references.venue: In AAMAS,
references.authors: Bryan Wilder Han-Ching Ou Kayla de la Haye Milind Tambe
references.title: Optimizing network structure for preventative health
references.venue: In AAMAS,
references.authors: Chuan Zhou Peng Zhang Wenyu Zang Li Guo
references.title: On the upper bounds of spread for greedy algorithms in social network influence maximization
references.venue: IEEE Transactions on Knowledge and Data Engineering,
references.authors: Zhou
references.title: For every pv ≤ 1
references.authors: James
references.title: as the set of indices of non zero rows in a matrix such as Xi. Finally let R represent ReLU and btr, sttr the mean and standard deviation computed by the batchnorm
references.venue: Each step is justified further below. Proof. Monotonocity,
references.authors: Xi (Boyd
references.title: We multiply both sides by a real matrix W ∈ Rd×hd 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 Xi and Xj and hence cannot interfere with the support of Xj over Xi. The statement becomes more obvious for X
references.venue: 1}n×1 and W ∈ R1×1
sections.heading: 1 INTRODUCTION
sections.text: Several real-world problems can be cast as a combinatorial optimization problem over a graph. From distributing packages (Mathew et al., 2015) to improving the general health (Wilder et al., 2018) and vehicles’ management (Touati-Moungla & Jost, 2012), optimization on graphs lies in the core of many real-world applications that are vital to our way of living. Unfortunately, the majority of these problems are NP-hard, and hence we can only approximate their solution in a satisfactory time limit that matches the real world requirements. Recent machine learning methods have emerged as a promising solution to develop heuristic methods that provide fast and accurate approximations (Bengio et al., 2020). The general idea is to train a 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; Sutton & Barto, 2018) to produce sequential predictions, or a 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 a plethora of problems, influence maximization (IM) has not been addressed yet extensively. IM addresses the problem of finding the set of nodes in a network that would maximize the number of nodes reached by starting a 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 a given seed set, is #P-hard as it is analogous to counting s-t connectedness and would require 2|E| possible combinations to compute exactly, where |E| is the number of network edges (Wang et al., 2012). Typically, influence estimation is approximated using
  repetitive Monte-Carlo (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 an at least (1− 1e ) 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 Borgs et al. (2014); Tang et al. (2015) and heuristics Chen et 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 advantages 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 GLIE, a GNN that provides efficient IE for a given seed set and a graph with influence probabilities. It 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-art algorithm and previous GNN-RL methods for IM. In addition, we develop GRIM, a Q-learning architecture that utilizes GLIE’s representations and predictions to obtain seeds sequentially, while minimizing the number of influence estimations throughout steps. Finally, we propose PUN, a method that uses GLIE’s representations to compute the number of neighbors predicted to be uninfluenced and uses it as an approximation to the marginal gain. We prove PUN’s influence spread is submodular and monotone, and hence can be optimized greedily with a guarantee, in contrast to prior learning-based methods. The experiments indicate that PUN provides the best balance between influence quality and computational efficiency.
  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 the contribution and presents future steps.
sections.heading: 2 RELATED WORK
sections.text: The first approach to solving combinatorial optimization (CO) using neural networks was based on attention-based NNs for discrete structures, POINTERNETS (Vinyals et al., 2015), 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), usingSTRUCT2VEC to encode the states of the nodes and the graph, and training a Q-learning model that chooses the right node to add in a 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 et al., 2019). The model, named FINDER, uses a deep Q-learning architecture where the representations are derived by three GRAPHSAGE 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 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 a 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 a large
  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 of 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 to a 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 CELF-GLIE, CELF Leskovec et al. (2007) with GLIE as influence estimator, GRIM, a Q-network that learns how to choose seeds using the GLIE’s estimations and hidden representations, and PUN, an adaptive IM method that optimizes greedily a submodular influence spread using GLIE’s representations.
  We note here that the majority of the relevant literature on DL for CO address small graphs (Vinyals et al., 2015; Dai et al., 2017; Kool et al., 2018; Prates et 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).
sections.heading: 3 METHODOLOGY
sections.heading: 3.1 GRAPH LEARNING FOR INFLUENCE ESTIMATION (GLIE)
sections.text: In this section, we introduce GLIE (GNN Learning Influence Estimation), which aims to learn how to estimate the influence of a seed set S over a graph G = (V,E). Let A ∈ Rn×n be the adjacency matrix and X ∈ Rn×d be the features of nodes, representing which nodes belong to the seed set by 1 and 0 otherwise:
  Xu = { {1}d, u ∈ S {0}d, u /∈ S . (1)
  For the derivation of the corollary, we set d = 1. More dimensions will become meaningful when we parameterize the problem. If we normalize A by each row, we form a row-stochastic transition matrix, as:
  Auv = pvu =
  { 1
  deg(u) , v ∈ N (u) 0, v /∈ N (u) , (2)
  where deg(u) is the in-degree of node u andN (u) is the set of neighbors of u. Based on the weighted cascade (Kempe et al., 2003), each row u stores the probability of node u 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|S) resembles the probability of a node u getting influenced if its neighbors belong in the seed set, i.e., during the first step of the diffusion. We can use message passing to compute a well-known upper bound p̂(u|S) of p(u|S) for node u:
  p̂(u|S) = Au ·X = ∑
  v∈N (u)∩S
  1
  deg(u) =
  ∑
  v∈N (u)∩S pvu ≥ 1−
  ∏
  v∈N (u)∩S (1− pvu) = p(u|S), (3)
  where the second equality stems from the definition of the weighted cascade and the inequality 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 H1 = A ·X, and we assume the new seed set St to be the nodes influenced in the step t− 1, their probabilities are stored in Ht, much like a diffusion in discrete time. We can then recompute the new influence probabilities with Ht+1 = A ·Ht, Corollary 3.0.1. The repeated product Ht+1 = A·Ht computes an upper bound to the real influence probabilities of each infected node at step t+ 1.
  The proof can be found in Appendix A.1. In reality, due to the existence of cycles, 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 a network with triangles. To this end, we 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 p̂(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 a 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 a function that tightens this approximation based on supervision. In our neural network architecture, each layer consists of a GNN with a batchnorm and dropout omitted here, and starting from H0 = X ∈ Rn×d we have:
  Ht+1 = ReLU([Ht,AHt]W0). (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:
  HGS = ∑
  v∈V [Hv0,H v 1, . . . ,H v t ]. (5)
  This representation captures the probability of all nodes being active throughout each layer. The output that represents the predicted influence spread is derived by:
  σ̂(S) = ReLU(HGSWo). (6)
  Note that, the derived representations of each layerHit , untrained, are the upper bound of the influence probability of seed set’s the t-hop neighbors. The parameters of the intermediate layers Wt are trained such that the upper bound is reduced and the final layer Wo 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. 1 and the heatmaps indicate a difference between columns (nodes) expected to be 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 H for the purpose of IM.
sections.heading: 3.2 COST EFFECTIVE LAZY FORWARD WITH GLIE (CELF-GLIE)
sections.text: 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 a 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 is 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 is 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 current gain is smaller than the second previous gain, the list is resorted and the process is repeated until the best node is 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 a 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 are 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,
  Under review as a conference paper at ICLR 2022
  <latexit sha1_base64="bj5/PXvRWwwvKiEDd3D4l4386No=">AAACHnicbVDLSgNBEJyNr7i+ol4EL4sh4CnsSkCPQS/ejGIekIQwO+kkQ2YfzPRKwhK/xYNX/Qxv4lW/wl9wdhMkJjbMUFR1U93lhoIrtO0vI7Oyura+kd00t7Z3dvdy+wc1FUSSQZUFIpANlyoQ3IcqchTQCCVQzxVQd4dXiV5/AKl44N/jOIS2R/s+73FGUVOd3FELYYRx+isW3wHt3kQ4mZidXN4u2mlZy8CZgTyZVaWT+251AxZ54CMTVKmmY4fYjqlEzgRMzFakIKRsSPvQ1NCnHqh2nF4wsQqa6Vq9QOrno5Wy8xMx9ZQae67u9CgO1KKWkP9pzQh7F+2Y+2GE4LOpUS8SFgZWEofV5RIYirEGlEmud7XYgErKUIdmFuZtwlGym/q10Qk5i3ksg9pZ0SkVS7elfPlyllWWHJMTckocck7K5JpUSJUw8kieyQt5NZ6MN+Pd+Ji2ZozZzCH5U8bnD7tyoyY=</latexit>
  <latexit sha1_base64="zD9WQbVg7fQXtpMLWuzDCBfHyo4=">AAACHXicbVDLSsNAFJ3UV42vqAsXboKl4KokUtBl0Y07K9gHtKFMppN26OTBzI20hHyLC7f6Ge7ErfgV/oKTNEhtvTDD4Zx7OfceN+JMgmV9aaW19Y3NrfK2vrO7t39gHB61ZRgLQlsk5KHoulhSzgLaAgacdiNBse9y2nEnN5neeaRCsjB4gFlEHR+PAuYxgkFRA+OkD3QKSf5LktzFEMWQpvrAqFg1Ky9zFdgFqKCimgPjuz8MSezTAAjHUvZsKwInwQIY4TTV+7GkESYTPKI9BQPsU+kk+QGpWVXM0PRCoV4AZs4uTiTYl3Lmu6rTxzCWy1pG/qf1YvCunIQF6igakLmRF3MTQjNLwxwyQQnwmQKYCKZ2NckYC0xAZaZXF22iabab/LVRCdnLeayC9kXNrtfq9/VK47rIqoxO0Rk6Rza6RA10i5qohQhK0TN6Qa/ak/amvWsf89aSVswcoz+lff4AVRSi+Q==</latexit>
  <latexit sha1_base64="nJ+FhxIQcnK30jjjyxZ9+atp+cM=">AAACK3icbVDLSgNBEJz1GeNr1aOXwRDwFHYloMegFw8eIpgHJDHMTjo6ODu7zPRKwrJf4Ld48Kqf4Unx6tlfcJIs4qthmKKqm+quIJbCoOe9OHPzC4tLy4WV4ura+samu7XdNFGiOTR4JCPdDpgBKRQ0UKCEdqyBhYGEVnBzMtFbt6CNiNQFjmPohexKiaHgDC3Vd8sHl2kXYYSpGmQZncHZZ3h6xsags6zYd0texZsW/Qv8HJRIXvW++9EdRDwJQSGXzJiO78XYS5lGwSVkxW5iIGb8hl1Bx0LFQjC9dHpORsuWGdBhpO1TSKfs94mUhcaMw8B2hgyvzW9tQv6ndRIcHvVSoeIEQfGZ0TCRFCM6yYYOhAaOcmwB41rYXSm/ZppxtAkWy99t4tFkN/NlYxPyf+fxFzQPKn61Uj2vlmrHeVYFskv2yD7xySGpkVNSJw3CyR15II/kybl3np1X523WOufkMzvkRznvn1aIqKQ=</latexit>
  <latexit sha1_base64="+giw3PGcCZxNLb5ydEESwpYmiks=">AAACK3icbVDJSgNBEO1xjXEb9eilMQQ8hRkJ6DHoxYOHCGaBJIaeTiVp0rPQXSMJw3yB3+LBq36GJ8WrZ3/BzoLExIKmH+9V8aqeF0mh0XHerZXVtfWNzcxWdntnd2/fPjis6jBWHCo8lKGqe0yDFAFUUKCEeqSA+Z6Emje4Guu1B1BahMEdjiJo+awXiK7gDA3VtvPufdJEGGKiMU3pFE4/zZMbNgKVptm2nXMKzqToMnBnIEdmVW7b381OyGMfAuSSad1wnQhbCVMouIQ024w1RIwPWA8aBgbMB91KJuekNG+YDu2GyrwA6YSdn0iYr/XI90ynz7CvF7Ux+Z/WiLF70UpEEMUIAZ8adWNJMaTjbGhHKOAoRwYwroTZlfI+U4yjSTCbn7eJhuPd9K+NSchdzGMZVM8KbrFQvC3mSpezrDLkmJyQU+KSc1Ii16RMKoSTR/JMXsir9WS9WR/W57R1xZrNHJE/ZX39AHkfqLg=</latexit>
  <latexit sha1_base64="tk1uIw9vnvjBFUgOSZUbAwmLSgE=">AAACBXicbVDLSsNAFL3xWeur6tJNsBQEoSRS0GXRjcsW7APaUCbTm3boZBJmJmIpXbtwq5/hTtz6HX6Fv+CkDVJbLwwczrmXc+b4MWdKO86Xtba+sbm1ndvJ7+7tHxwWjo6bKkokxQaNeCTbPlHImcCGZppjO5ZIQp9jyx/dpnrrAaVikbjX4xi9kAwECxgl2lD1i16h6JSd2dirwM1AEbKp9Qrf3X5EkxCFppwo1XGdWHsTIjWjHKf5bqIwJnREBtgxUJAQlTeZBZ3aJcP07SCS5gltz9jFiwkJlRqHvtkMiR6qZS0l/9M6iQ6uvQkTcaJR0LlRkHBbR3b6a7vPJFLNxwYQKpnJatMhkYRq002+tGgTP6bZ1K+Nachd7mMVNC/LbqVcqVeK1ZusqxycwhmcgwtXUIU7qEEDKCA8wwu8Wk/Wm/VufcxX16zs5gT+jPX5A87bmHQ=</latexit>
  <latexit sha1_base64="E5/CRARnFBrRcL4C5ES9D1Sj8NQ=">AAACBnicbVDLSsNAFL3xWeOr6tLNYCm4KokUdFl047I++oA2lMl00g6dTMLMRCyhexdu9TPciVt/w6/wF5y0QWrrhYHDOfdyzhw/5kxpx/myVlbX1jc2C1v29s7u3n7x4LCpokQS2iARj2Tbx4pyJmhDM81pO5YUhz6nLX90lemtByoVi8S9HsfUC/FAsIARrA11e2f3iiWn4kwHLQM3ByXIp94rfnf7EUlCKjThWKmO68TaS7HUjHA6sbuJojEmIzygHQMFDqny0mnSCSobpo+CSJonNJqy8xcpDpUah77ZDLEeqkUtI//TOokOLryUiTjRVJCZUZBwpCOUfRv1maRE87EBmEhmsiIyxBITbcqxy/M28WOWTf3amIbcxT6WQfOs4lYr1ZtqqXaZd1WAYziBU3DhHGpwDXVoAIEAnuEFXq0n6816tz5mqytWfnMEf8b6/AFFsJiw</latexit>
  <latexit sha1_base64="wpY2BYmCIJpnxFNMT+zgenLx/5E=">AAACGnicbVDLSsNAFJ34rPUVHzs3wVJwVRIp6LLoxo1QwT6gLWUyvW2HTiZh5kZaQ//EhVv9DHfi1o1f4S84TYvU1gszHM65l3M4fiS4Rtf9slZW19Y3NjNb2e2d3b19++CwqsNYMaiwUISq7lMNgkuoIEcB9UgBDXwBNX9wPdFrD6A0D+U9jiJoBbQneZczioZq28dNhCEm6a9ZcgtUjsdtO+cW3HScZeDNQI7Mpty2v5udkMUBSGSCat3w3AhbCVXImYBxthlriCgb0B40DJQ0AN1K0vRjJ2+YjtMNlXkSnZSdv0hooPUo8M1mQLGvF7UJ+Z/WiLF72Uq4jGIEyaZG3Vg4GDqTKpwOV8BQjAygTHGT1WF9qihDU1g2P28TDSfZ9K+Nachb7GMZVM8LXrFQvCvmSlezrjLkhJySM+KRC1IiN6RMKoSRR/JMXsir9WS9We/Wx3R1xZrdHJE/Y33+AP3iocE=</latexit>
  <latexit sha1_base64="wpY2BYmCIJpnxFNMT+zgenLx/5E=">AAACGnicbVDLSsNAFJ34rPUVHzs3wVJwVRIp6LLoxo1QwT6gLWUyvW2HTiZh5kZaQ//EhVv9DHfi1o1f4S84TYvU1gszHM65l3M4fiS4Rtf9slZW19Y3NjNb2e2d3b19++CwqsNYMaiwUISq7lMNgkuoIEcB9UgBDXwBNX9wPdFrD6A0D+U9jiJoBbQneZczioZq28dNhCEm6a9ZcgtUjsdtO+cW3HScZeDNQI7Mpty2v5udkMUBSGSCat3w3AhbCVXImYBxthlriCgb0B40DJQ0AN1K0vRjJ2+YjtMNlXkSnZSdv0hooPUo8M1mQLGvF7UJ+Z/WiLF72Uq4jGIEyaZG3Vg4GDqTKpwOV8BQjAygTHGT1WF9qihDU1g2P28TDSfZ9K+Nachb7GMZVM8LXrFQvCvmSlezrjLkhJySM+KRC1IiN6RMKoSRR/JMXsir9WS9We/Wx3R1xZrdHJE/Y33+AP3iocE=</latexit>
  <latexit sha1_base64="YCzKP8zTMuyZ/6I7z3yJbIUbg2M=">AAACFXicbVDLSsNAFJ3UV62PRl26GSyFuimJFHRZdOOygn1AE8pkOmmHzkzCzEQsod/hwq1+hjtx69qv8BectEFq64ULh3Pu5RxOEDOqtON8WYWNza3tneJuaW//4LBsHx13VJRITNo4YpHsBUgRRgVpa6oZ6cWSIB4w0g0mN5nefSBS0Ujc62lMfI5GgoYUI22ogV32xkinnqIjjmY1dT6wK07dmQ9cB24OKiCf1sD+9oYRTjgRGjOkVN91Yu2nSGqKGZmVvESRGOEJGpG+gQJxovx0HnwGq4YZwjCSZoWGc3b5I0VcqSkPzCVHeqxWtYz8T+snOrzyUyriRBOBF0ZhwqCOYNYCHFJJsGZTAxCW1GSFeIwkwtp0Vaou28SPWTb1a2Maclf7WAedi7rbqDfuGpXmdd5VEZyCM1ADLrgETXALWqANMEjAM3gBr9aT9Wa9Wx+L04KV/5yAP2N9/gCXJJ7I</latexit>
  <latexit sha1_base64="fZkAel85+LFs92T5/dbcL6b6WfM=">AAACM3icbVDLSgMxFM3UV62vUZdugqXYLlpmpKAboejGZUX7gM5QMmnahmYyQ5IRy9Cv8FtcuNWvEHfiVvwFM+0gtfVA4HDOvZyb44WMSmVZb0ZmZXVtfSO7mdva3tndM/cPmjKIBCYNHLBAtD0kCaOcNBRVjLRDQZDvMdLyRleJ37onQtKA36lxSFwfDTjtU4yUlrpmWcAL6AyRih1JBz6aFG+hg6MQypMSLC84pa6ZtyrWFHCZ2CnJgxT1rvnt9AIc+YQrzJCUHdsKlRsjoShmZJJzIklChEdoQDqacuQT6cbTb01gQSs92A+EflzBqTq/ESNfyrHv6UkfqaFc9BLxP68Tqf65G1MeRopwPAvqRwyqACYdwR4VBCs21gRhQfWtEA+RQFjpJnOF+ZjwIblN/sbohuzFPpZJ87RiVyvVm2q+dpl2lQVH4BgUgQ3OQA1cgzpoAAwewTN4Aa/Gk/FufBifs9GMke4cgj8wvn4AWkmpUA==</latexit>
  <latexit sha1_base64="9dfh5jBTW4B+e1LcsOzgr24gdbk=">AAACD3icbVDLSsNAFL3xWeOr6tJNsBRclUQKuiy6cVnBPiANZTKdtEMnM2FmIpbQj3DhVj/Dnbj1E/wKf8FJG6S2Xhg4nHMv58wJE0aVdt0va219Y3Nru7Rj7+7tHxyWj47bSqQSkxYWTMhuiBRhlJOWppqRbiIJikNGOuH4Jtc7D0QqKvi9niQkiNGQ04hipA3l90I6FJrGRNn9csWtubNxVoFXgAoU0+yXv3sDgdOYcI0ZUsr33EQHGZKaYkamdi9VJEF4jIbEN5Aj4xJks8hTp2qYgRMJaR7XzoxdvMhQrNQkDs1mjPRILWs5+Z/mpzq6CjLKk1QTjudGUcocLZz8/86ASoI1mxiAsKQmq4NHSCKsTUt2ddEmecyzqV8b05C33McqaF/UvHqtflevNK6LrkpwCmdwDh5cQgNuoQktwCDgGV7g1Xqy3qx362O+umYVNyfwZ6zPH9ienNY=</latexit>
  <latexit sha1_base64="CCEqGwEzfGQVsDkBjHs6QbEGVkg=">AAACDnicbVDLTgIxFL2DL8QX6tJNIyFxRWYMiS6JblxiIo8IhHRKBxo6nUl7x0gI/+DCrX6GO+PWX/Ar/AULTAyCN2lycs69OafHj6Uw6LpfTmZtfWNzK7ud29nd2z/IHx7VTZRoxmsskpFu+tRwKRSvoUDJm7HmNPQlb/jD66neeODaiEjd4SjmnZD2lQgEo2ipe0XaKEJuiNfNF9ySOxuyCrwUFCCdajf/3e5FLAm5QiapMS3PjbEzphoFk3ySayeGx5QNaZ+3LFTU2nTGs8QTUrRMjwSRtk8hmbGLF2MaGjMKfbsZUhyYZW1K/qe1EgwuO2Oh4gS5YnOjIJEEIzL9PukJzRnKkQWUaWGzEjagmjK0JeWKizbx4zSb+bWxDXnLfayC+nnJK5fKt+VC5SrtKgsncApn4MEFVOAGqlADBgqe4QVenSfnzXl3PuarGSe9OYY/43z+AGEXnAA=</latexit>
  <latexit sha1_base64="CCEqGwEzfGQVsDkBjHs6QbEGVkg=">AAACDnicbVDLTgIxFL2DL8QX6tJNIyFxRWYMiS6JblxiIo8IhHRKBxo6nUl7x0gI/+DCrX6GO+PWX/Ar/AULTAyCN2lycs69OafHj6Uw6LpfTmZtfWNzK7ud29nd2z/IHx7VTZRoxmsskpFu+tRwKRSvoUDJm7HmNPQlb/jD66neeODaiEjd4SjmnZD2lQgEo2ipe0XaKEJuiNfNF9ySOxuyCrwUFCCdajf/3e5FLAm5QiapMS3PjbEzphoFk3ySayeGx5QNaZ+3LFTU2nTGs8QTUrRMjwSRtk8hmbGLF2MaGjMKfbsZUhyYZW1K/qe1EgwuO2Oh4gS5YnOjIJEEIzL9PukJzRnKkQWUaWGzEjagmjK0JeWKizbx4zSb+bWxDXnLfayC+nnJK5fKt+VC5SrtKgsncApn4MEFVOAGqlADBgqe4QVenSfnzXl3PuarGSe9OYY/43z+AGEXnAA=</latexit>
  <latexit sha1_base64="BBxCLSQbs0Bgi09BthHFKIh8KSI=">AAACEHicbVDLSsNAFJ3UV62vqks3g6XgopRECroRim5cVrAPaEKZTCbt0MlMmJmIJfQnXLjVz3Anbv0Dv8JfcNIGqa0XLhzOuZdzOH7MqNK2/WUV1tY3NreK26Wd3b39g/LhUUeJRGLSxoIJ2fORIoxy0tZUM9KLJUGRz0jXH99keveBSEUFv9eTmHgRGnIaUoy0oVx65dRcFgitanxQrth1ezZwFTg5qIB8WoPytxsInESEa8yQUn3HjrWXIqkpZmRachNFYoTHaEj6BnIUEeWls8xTWDVMAEMhzXINZ+ziR4oipSaRby4jpEdqWcvI/7R+osNLL6U8TjTheG4UJgxqAbMCYEAlwZpNDEBYUpMV4hGSCGtTU6m6aBM/ZtnUr41pyFnuYxV0zutOo964a1Sa13lXRXACTsEZcMAFaIJb0AJtgEEMnsELeLWerDfr3fqYnxas/OcY/Bnr8wfsaJzW</latexit>
  <latexit sha1_base64="23SfVbqOtw1ZZiJvEHNjSo3deTc=">AAACBXicbVDLSsNAFL2pr1pfVZdugqXgqiRS0GXRjcsW7APaUCbTm3boZBJmJmIJXbtwq5/hTtz6HX6Fv+CkLVJbLwwczrmXc+b4MWdKO86XldvY3Nreye8W9vYPDo+KxyctFSWSYpNGPJIdnyjkTGBTM82xE0skoc+x7Y9vM739gFKxSNzrSYxeSIaCBYwSbaiG6hdLTsWZjb0O3AUowWLq/eJ3bxDRJEShKSdKdV0n1l5KpGaU47TQSxTGhI7JELsGChKi8tJZ0KldNszADiJpntD2jF2+SEmo1CT0zWZI9Eitahn5n9ZNdHDtpUzEiUZB50ZBwm0d2dmv7QGTSDWfGECoZCarTUdEEqpNN4Xysk38mGVTvzamIXe1j3XQuqy41Uq1US3VbhZd5eEMzuECXLiCGtxBHZpAAeEZXuDVerLerHfrY76asxY3p/BnrM8fRDKYvA==</latexit>
  <latexit sha1_base64="Fk+yZoO5t2ged73NhKug865kUn8=">AAAB9HicbVDLSgNBEJyNrxhfUY9eBoPgKexKQI9BD3qMYB6QLGF20kmGzM6uM73BsOQ7vHhQxKsf482/cZLsQRMLGoqqbrq7glgKg6777eTW1jc2t/LbhZ3dvf2D4uFRw0SJ5lDnkYx0K2AGpFBQR4ESWrEGFgYSmsHoZuY3x6CNiNQDTmLwQzZQoi84Qyv5HYQnNDy9lQKm3WLJLbtz0FXiZaREMtS6xa9OL+JJCAq5ZMa0PTdGP2UaBZcwLXQSAzHjIzaAtqWKhWD8dH70lJ5ZpUf7kbalkM7V3xMpC42ZhIHtDBkOzbI3E//z2gn2r/xUqDhBUHyxqJ9IihGdJUB7QgNHObGEcS3srZQPmWYcbU4FG4K3/PIqaVyUvUq5cl8pVa+zOPLkhJySc+KRS1Ild6RG6oSTR/JMXsmbM3ZenHfnY9Gac7KZY/IHzucPTLSScw==</latexit>
  <latexit sha1_base64="w8LxOw29hEndwhN5v8L3YiSEZW0=">AAACG3icbVDLSgNBEJyNrxhfUfHkZTEEvBh2JaDHoBdPkoB5QLKE2UknGTL7YKZXEpZ8igev+hnexKsHv8JfcDZZJCY2zFBUdVNFuaHgCi3ry8isrW9sbmW3czu7e/sH+cOjhgoiyaDOAhHIlksVCO5DHTkKaIUSqOcKaLqj20RvPoJUPPAfcBKC49GBz/ucUdRUN39S6yCMMZ79isUX94DTaTdfsErWbMxVYKegQNKpdvPfnV7AIg98ZIIq1batEJ2YSuRMwDTXiRSElI3oANoa+tQD5cSz+FOzqJme2Q+kfj6aM3bxIqaeUhPP1ZsexaFa1hLyP60dYf/aibkfRgg+mxv1I2FiYCZdmD0ugaGYaECZ5DqryYZUUoa6sVxx0SYcJ9nUr41uyF7uYxU0Lkt2uVSulQuVm7SrLDklZ+Sc2OSKVMgdqZI6YSQmz+SFvBpPxpvxbnzMVzNGenNM/ozx+QNjS6Hv</latexit>
  <latexit sha1_base64="CCEqGwEzfGQVsDkBjHs6QbEGVkg=">AAACDnicbVDLTgIxFL2DL8QX6tJNIyFxRWYMiS6JblxiIo8IhHRKBxo6nUl7x0gI/+DCrX6GO+PWX/Ar/AULTAyCN2lycs69OafHj6Uw6LpfTmZtfWNzK7ud29nd2z/IHx7VTZRoxmsskpFu+tRwKRSvoUDJm7HmNPQlb/jD66neeODaiEjd4SjmnZD2lQgEo2ipe0XaKEJuiNfNF9ySOxuyCrwUFCCdajf/3e5FLAm5QiapMS3PjbEzphoFk3ySayeGx5QNaZ+3LFTU2nTGs8QTUrRMjwSRtk8hmbGLF2MaGjMKfbsZUhyYZW1K/qe1EgwuO2Oh4gS5YnOjIJEEIzL9PukJzRnKkQWUaWGzEjagmjK0JeWKizbx4zSb+bWxDXnLfayC+nnJK5fKt+VC5SrtKgsncApn4MEFVOAGqlADBgqe4QVenSfnzXl3PuarGSe9OYY/43z+AGEXnAA=</latexit>
  <latexit sha1_base64="mkcTSQC2MCD3iLZEIWCWoydrYiA=">AAAB9HicbVDLSgNBEJyNrxhfUY9eBoPgKexKQI9BD3qMYB6QLGF20kmGzM6uM73BsOQ7vHhQxKsf482/cZLsQRMLGoqqbrq7glgKg6777eTW1jc2t/LbhZ3dvf2D4uFRw0SJ5lDnkYx0K2AGpFBQR4ESWrEGFgYSmsHoZuY3x6CNiNQDTmLwQzZQoi84Qyv5HYQnNDy91SKcdoslt+zOQVeJl5ESyVDrFr86vYgnISjkkhnT9twY/ZRpFFzCtNBJDMSMj9gA2pYqFoLx0/nRU3pmlR7tR9qWQjpXf0+kLDRmEga2M2Q4NMveTPzPayfYv/JToeIEQfHFon4iKUZ0lgDtCQ0c5cQSxrWwt1I+ZJpxtDkVbAje8surpHFR9irlyn2lVL3O4siTE3JKzolHLkmV3JEaqRNOHskzeSVvzth5cd6dj0VrzslmjskfOJ8/YgaSgQ==</latexit>
  <latexit sha1_base64="8jtdPxKGxsiYPMAcv7UMbSO+b74=">AAAB83icbVBNS8NAEJ34WetX1aOXYBE8lUQKeix68VjBfkATyma7aZduNmF3Viyhf8OLB0W8+me8+W/ctjlo64OBx3szzMyLMsE1et63s7a+sbm1Xdop7+7tHxxWjo7bOjWKshZNRaq6EdFMcMlayFGwbqYYSSLBOtH4duZ3HpnSPJUPOMlYmJCh5DGnBK0UBMieUNO8aeS0X6l6NW8Od5X4BalCgWa/8hUMUmoSJpEKonXP9zIMc6KQU8Gm5cBolhE6JkPWs1SShOkwn988dc+tMnDjVNmS6M7V3xM5SbSeJJHtTAiO9LI3E//zegbj6zDnMjPIJF0sio1wMXVnAbgDrhhFMbGEUMXtrS4dEUUo2pjKNgR/+eVV0r6s+fVa/b5ebdwUcZTgFM7gAny4ggbcQRNaQCGDZ3iFN8c4L86787FoXXOKmRP4A+fzB6yykhs=</latexit>
  <latexit sha1_base64="Fk+yZoO5t2ged73NhKug865kUn8=">AAAB9HicbVDLSgNBEJyNrxhfUY9eBoPgKexKQI9BD3qMYB6QLGF20kmGzM6uM73BsOQ7vHhQxKsf482/cZLsQRMLGoqqbrq7glgKg6777eTW1jc2t/LbhZ3dvf2D4uFRw0SJ5lDnkYx0K2AGpFBQR4ESWrEGFgYSmsHoZuY3x6CNiNQDTmLwQzZQoi84Qyv5HYQnNDy9lQKm3WLJLbtz0FXiZaREMtS6xa9OL+JJCAq5ZMa0PTdGP2UaBZcwLXQSAzHjIzaAtqWKhWD8dH70lJ5ZpUf7kbalkM7V3xMpC42ZhIHtDBkOzbI3E//z2gn2r/xUqDhBUHyxqJ9IihGdJUB7QgNHObGEcS3srZQPmWYcbU4FG4K3/PIqaVyUvUq5cl8pVa+zOPLkhJySc+KRS1Ild6RG6oSTR/JMXsmbM3ZenHfnY9Gac7KZY/IHzucPTLSScw==</latexit>
  <latexit sha1_base64="Fk+yZoO5t2ged73NhKug865kUn8=">AAAB9HicbVDLSgNBEJyNrxhfUY9eBoPgKexKQI9BD3qMYB6QLGF20kmGzM6uM73BsOQ7vHhQxKsf482/cZLsQRMLGoqqbrq7glgKg6777eTW1jc2t/LbhZ3dvf2D4uFRw0SJ5lDnkYx0K2AGpFBQR4ESWrEGFgYSmsHoZuY3x6CNiNQDTmLwQzZQoi84Qyv5HYQnNDy9lQKm3WLJLbtz0FXiZaREMtS6xa9OL+JJCAq5ZMa0PTdGP2UaBZcwLXQSAzHjIzaAtqWKhWD8dH70lJ5ZpUf7kbalkM7V3xMpC42ZhIHtDBkOzbI3E//z2gn2r/xUqDhBUHyxqJ9IihGdJUB7QgNHObGEcS3srZQPmWYcbU4FG4K3/PIqaVyUvUq5cl8pVa+zOPLkhJySc+KRS1Ild6RG6oSTR/JMXsmbM3ZenHfnY9Gac7KZY/IHzucPTLSScw==</latexit>
  <latexit sha1_base64="kFlaCuIQeTEczX6e5oHEet5TSTg=">AAAB83icbVBNSwMxEM3Wr1q/qh69BIvgqexKQY9FLx4r2g/oLiWbpm1okl2SiViW/g0vHhTx6p/x5r8xbfegrQ8GHu/NMDMvTgU34PvfXmFtfWNzq7hd2tnd2z8oHx61TGI1ZU2aiER3YmKY4Io1gYNgnVQzImPB2vH4Zua3H5k2PFEPMElZJMlQ8QGnBJwUhsCewNDs3sppr1zxq/4ceJUEOamgHI1e+SvsJ9RKpoAKYkw38FOIMqKBU8GmpdAalhI6JkPWdVQRyUyUzW+e4jOn9PEg0a4U4Ln6eyIj0piJjF2nJDAyy95M/M/rWhhcRRlXqQWm6GLRwAoMCZ4FgPtcMwpi4gihmrtbMR0RTSi4mEouhGD55VXSuqgGtWrtrlapX+dxFNEJOkXnKECXqI5uUQM1EUUpekav6M2z3ov37n0sWgtePnOM/sD7/AGvwpId</latexit>
  <latexit sha1_base64="oeEzO2upmY11zr1JHnQ9E9++kEU=">AAAB7XicbVBNS8NAEJ3Ur1q/qh69BIvgqSRS0GPVi8cK9gPaWDbbTbu62Q27E6GE/gcvHhTx6v/x5r9x2+agrQ8GHu/NMDMvTAQ36HnfTmFldW19o7hZ2tre2d0r7x+0jEo1ZU2qhNKdkBgmuGRN5ChYJ9GMxKFg7fDxeuq3n5g2XMk7HCcsiMlQ8ohTglZqXd73UCX9csWrejO4y8TPSQVyNPrlr95A0TRmEqkgxnR9L8EgIxo5FWxS6qWGJYQ+kiHrWipJzEyQza6duCdWGbiR0rYkujP190RGYmPGcWg7Y4Ijs+hNxf+8borRRZBxmaTIJJ0vilLhonKnr7sDrhlFMbaEUM3trS4dEU0o2oBKNgR/8eVl0jqr+rVq7bZWqV/lcRThCI7hFHw4hzrcQAOaQOEBnuEV3hzlvDjvzse8teDkM4fwB87nD27Djws=</latexit>
  <latexit sha1_base64="t5Z8j6uw1dDrul9BiPoeucvIxm0=">AAAB6HicbVBNS8NAEJ3Ur1q/qh69LBbBU0mkoMeiF48t2A9oQ9lsJ+3azSbsboQS+gu8eFDEqz/Jm//GbZuDtj4YeLw3w8y8IBFcG9f9dgobm1vbO8Xd0t7+weFR+fikreNUMWyxWMSqG1CNgktsGW4EdhOFNAoEdoLJ3dzvPKHSPJYPZpqgH9GR5CFn1FipqQflilt1FyDrxMtJBXI0BuWv/jBmaYTSMEG17nluYvyMKsOZwFmpn2pMKJvQEfYslTRC7WeLQ2fkwipDEsbKljRkof6eyGik9TQKbGdEzVivenPxP6+XmvDGz7hMUoOSLReFqSAmJvOvyZArZEZMLaFMcXsrYWOqKDM2m5INwVt9eZ20r6perVpr1ir12zyOIpzBOVyCB9dQh3toQAsYIDzDK7w5j86L8+58LFsLTj5zCn/gfP4A4OuM/g==</latexit>
  <latexit sha1_base64="t5Z8j6uw1dDrul9BiPoeucvIxm0=">AAAB6HicbVBNS8NAEJ3Ur1q/qh69LBbBU0mkoMeiF48t2A9oQ9lsJ+3azSbsboQS+gu8eFDEqz/Jm//GbZuDtj4YeLw3w8y8IBFcG9f9dgobm1vbO8Xd0t7+weFR+fikreNUMWyxWMSqG1CNgktsGW4EdhOFNAoEdoLJ3dzvPKHSPJYPZpqgH9GR5CFn1FipqQflilt1FyDrxMtJBXI0BuWv/jBmaYTSMEG17nluYvyMKsOZwFmpn2pMKJvQEfYslTRC7WeLQ2fkwipDEsbKljRkof6eyGik9TQKbGdEzVivenPxP6+XmvDGz7hMUoOSLReFqSAmJvOvyZArZEZMLaFMcXsrYWOqKDM2m5INwVt9eZ20r6perVpr1ir12zyOIpzBOVyCB9dQh3toQAsYIDzDK7w5j86L8+58LFsLTj5zCn/gfP4A4OuM/g==</latexit>
  <latexit sha1_base64="XP9iErG+L6qrY8EDX+rDc8RxBHg=">AAACBXicbVDLSgNBEOz1GeMr6tHLYAh4CrsS0IsQ9OIxAfOAZAmzk95kyOyDmVkxhJw9eNXP8CZe/Q6/wl9wNlkkJjYMFFXdVE15seBK2/aXtba+sbm1ndvJ7+7tHxwWjo6bKkokwwaLRCTbHlUoeIgNzbXAdiyRBp7Alje6TfXWA0rFo/Bej2N0AzoIuc8Z1YaqX/cKRbtsz4asAicDRcim1it8d/sRSwIMNRNUqY5jx9qdUKk5EzjNdxOFMWUjOsCOgSENULmTWdApKRmmT/xImhdqMmMXLyY0UGoceGYzoHqolrWU/E/rJNq/cic8jBONIZsb+YkgOiLpr0mfS2RajA2gTHKTlbAhlZRp002+tGgTP6bZ1K+NachZ7mMVNC/KTqVcqVeK1ZusqxycwhmcgwOXUIU7qEEDGCA8wwu8Wk/Wm/VufcxX16zs5gT+jPX5A+wtmIY=</latexit>
  <latexit sha1_base64="7zTrdAR4gsqi8D5fz/nDX5Zs1s0=">AAAB8HicbVA9SwNBEJ3zM8avqKXNYRCswp0EtAzaWFhENB+SHGFvs5cs2d07dueEcORX2FgoYuvPsfPfuEmu0MQHA4/3ZpiZFyaCG/S8b2dldW19Y7OwVdze2d3bLx0cNk2casoaNBaxbofEMMEVayBHwdqJZkSGgrXC0fXUbz0xbXisHnCcsECSgeIRpwSt9NgdEsxuJ737XqnsVbwZ3GXi56QMOeq90le3H9NUMoVUEGM6vpdgkBGNnAo2KXZTwxJCR2TAOpYqIpkJstnBE/fUKn03irUthe5M/T2REWnMWIa2UxIcmkVvKv7ndVKMLoOMqyRFpuh8UZQKF2N3+r3b55pRFGNLCNXc3urSIdGEos2oaEPwF19eJs3zil+tVO+q5dpVHkcBjuEEzsCHC6jBDdShARQkPMMrvDnaeXHenY9564qTzxzBHzifP814kGo=</latexit>
  <latexit sha1_base64="vx/z9SO37d1o65IRwHHfZ1wV0PE=">AAAB6nicbVDLSgNBEOyNrxhfUY9eBoPgKexKQI9BLx4jMQ9IljA7mU2GzGOZmRXCkk/w4kERr36RN//GSbIHTSxoKKq66e6KEs6M9f1vr7CxubW9U9wt7e0fHB6Vj0/aRqWa0BZRXOluhA3lTNKWZZbTbqIpFhGnnWhyN/c7T1QbpuSjnSY0FHgkWcwItk5qikFzUK74VX8BtE6CnFQgR2NQ/uoPFUkFlZZwbEwv8BMbZlhbRjidlfqpoQkmEzyiPUclFtSE2eLUGbpwyhDFSruSFi3U3xMZFsZMReQ6BbZjs+rNxf+8XmrjmzBjMkktlWS5KE45sgrN/0ZDpimxfOoIJpq5WxEZY42JdemUXAjB6svrpH1VDWrV2kOtUr/N4yjCGZzDJQRwDXW4hwa0gMAInuEV3jzuvXjv3seyteDlM6fwB97nDzC8jb4=</latexit>
  <latexit sha1_base64="CCEqGwEzfGQVsDkBjHs6QbEGVkg=">AAACDnicbVDLTgIxFL2DL8QX6tJNIyFxRWYMiS6JblxiIo8IhHRKBxo6nUl7x0gI/+DCrX6GO+PWX/Ar/AULTAyCN2lycs69OafHj6Uw6LpfTmZtfWNzK7ud29nd2z/IHx7VTZRoxmsskpFu+tRwKRSvoUDJm7HmNPQlb/jD66neeODaiEjd4SjmnZD2lQgEo2ipe0XaKEJuiNfNF9ySOxuyCrwUFCCdajf/3e5FLAm5QiapMS3PjbEzphoFk3ySayeGx5QNaZ+3LFTU2nTGs8QTUrRMjwSRtk8hmbGLF2MaGjMKfbsZUhyYZW1K/qe1EgwuO2Oh4gS5YnOjIJEEIzL9PukJzRnKkQWUaWGzEjagmjK0JeWKizbx4zSb+bWxDXnLfayC+nnJK5fKt+VC5SrtKgsncApn4MEFVOAGqlADBgqe4QVenSfnzXl3PuarGSe9OYY/43z+AGEXnAA=</latexit>
  <latexit sha1_base64="irN8HCigVzayJLyQjvL6vp5Ng2w=">AAAB8HicbVBNSwMxEJ2tX7V+VT16CRbBU9mVgl6EohePFe2HbJeSTbNtaJJdkmyhLP0VXjwo4tWf481/Y9ruQVsfDDzem2FmXphwpo3rfjuFtfWNza3idmlnd2//oHx41NJxqghtkpjHqhNiTTmTtGmY4bSTKIpFyGk7HN3O/PaYKs1i+WgmCQ0EHkgWMYKNlZ5E78EfB9ce6pUrbtWdA60SLycVyNHolb+6/ZikgkpDONba99zEBBlWhhFOp6VuqmmCyQgPqG+pxILqIJsfPEVnVumjKFa2pEFz9fdEhoXWExHaToHNUC97M/E/z09NdBVkTCapoZIsFkUpRyZGs+9RnylKDJ9Ygoli9lZEhlhhYmxGJRuCt/zyKmldVL1atXZfq9Rv8jiKcAKncA4eXEId7qABTSAg4Ble4c1Rzovz7nwsWgtOPnMMf+B8/gC7go+2</latexit>
  <latexit sha1_base64="w/5P7F8wU224ELNoNfxr0bEz9L0=">AAAB73icbVBNSwMxEJ2tX7V+VT16CRbBU9mVgl6EohePFe0HbJeSTbNtaJJdk2yhLP0TXjwo4tW/481/Y9ruQVsfDDzem2FmXphwpo3rfjuFtfWNza3idmlnd2//oHx41NJxqghtkpjHqhNiTTmTtGmY4bSTKIpFyGk7HN3O/PaYKs1i+WgmCQ0EHkgWMYKNlTqi9+CPg2u3V664VXcOtEq8nFQgR6NX/ur2Y5IKKg3hWGvfcxMTZFgZRjidlrqppgkmIzygvqUSC6qDbH7vFJ1ZpY+iWNmSBs3V3xMZFlpPRGg7BTZDvezNxP88PzXRVZAxmaSGSrJYFKUcmRjNnkd9pigxfGIJJorZWxEZYoWJsRGVbAje8surpHVR9WrV2n2tUr/J4yjCCZzCOXhwCXW4gwY0gQCHZ3iFN+fJeXHenY9Fa8HJZ47hD5zPH2HRj4s=</latexit>
  <latexit sha1_base64="hcos2bqH5uv/vPkuNcZDISCoxKo=">AAAB6nicbVBNS8NAEJ34WetX1aOXxSJ4CokU9Fj04rGi/YA2lM120y7dbMLuRCihP8GLB0W8+ou8+W/ctjlo64OBx3szzMwLUykMet63s7a+sbm1Xdop7+7tHxxWjo5bJsk0402WyER3Qmq4FIo3UaDknVRzGoeSt8Px7cxvP3FtRKIecZLyIKZDJSLBKFrpwXXdfqXqud4cZJX4BalCgUa/8tUbJCyLuUImqTFd30sxyKlGwSSflnuZ4SllYzrkXUsVjbkJ8vmpU3JulQGJEm1LIZmrvydyGhsziUPbGVMcmWVvJv7ndTOMroNcqDRDrthiUZRJggmZ/U0GQnOGcmIJZVrYWwkbUU0Z2nTKNgR/+eVV0rp0/Zpbu69V6zdFHCU4hTO4AB+uoA530IAmMBjCM7zCmyOdF+fd+Vi0rjnFzAn8gfP5A04qjSk=</latexit>
  <latexit sha1_base64="JyUCdaLoKQwfN3QRxFxal05CL3o=">AAAB6nicbVA9SwNBEJ3zM8avqKXNYhCswp0EtAzaWFhEYj4gOcLeZi5Zsrd37O4J4chPsLFQxNZfZOe/cZNcoYkPBh7vzTAzL0gE18Z1v5219Y3Nre3CTnF3b//gsHR03NJxqhg2WSxi1QmoRsElNg03AjuJQhoFAtvB+Hbmt59QaR7LRzNJ0I/oUPKQM2qs1LjvN/qlsltx5yCrxMtJGXLU+6Wv3iBmaYTSMEG17npuYvyMKsOZwGmxl2pMKBvTIXYtlTRC7WfzU6fk3CoDEsbKljRkrv6eyGik9SQKbGdEzUgvezPxP6+bmvDaz7hMUoOSLRaFqSAmJrO/yYArZEZMLKFMcXsrYSOqKDM2naINwVt+eZW0LitetVJ9qJZrN3kcBTiFM7gAD66gBndQhyYwGMIzvMKbI5wX5935WLSuOfnMCfyB8/kD/meNnQ==</latexit>
  <latexit sha1_base64="j8JGgR9d/eMOIZnIfhKu+qjG9zs=">AAACAXicbVDLSsNAFJ3UV62vqBvBzWARKkhJpKDLohsXLiq1D2hCmEwn7dCZSZiZCCXUjb/ixoUibv0Ld/6N0zYLrR64cDjnXu69J0wYVdpxvqzC0vLK6lpxvbSxubW9Y+/utVWcSkxaOGax7IZIEUYFaWmqGekmkiAeMtIJR1dTv3NPpKKxuNPjhPgcDQSNKEbaSIF94GU3QfMUekOkM0/RAUeTSvPEmwR22ak6M8C/xM1JGeRoBPan149xyonQmCGleq6TaD9DUlPMyKTkpYokCI/QgPQMFYgT5WezDybw2Ch9GMXSlNBwpv6cyBBXasxD08mRHqpFbyr+5/VSHV34GRVJqonA80VRyqCO4TQO2KeSYM3GhiAsqbkV4iGSCGsTWsmE4C6+/Je0z6purVq7rZXrl3kcRXAIjkAFuOAc1ME1aIAWwOABPIEX8Go9Ws/Wm/U+by1Y+cw++AXr4xttUZY+</latexit>
  <latexit sha1_base64="3ltARH2jlLatV8KIglOpT1eXl94=">AAACB3icbVDLSsNAFJ3UV62vqEtBBotQQUoiBV0W3bhwUcE+oAlhMp20Q2cmYWYilJCdG3/FjQtF3PoL7vwbp20WWj1w4XDOvdx7T5gwqrTjfFmlpeWV1bXyemVjc2t7x97d66g4lZi0ccxi2QuRIowK0tZUM9JLJEE8ZKQbjq+mfveeSEVjcacnCfE5GgoaUYy0kQL70MtugkwFND+F3gjpzFN0yFFeM9KJlwd21ak7M8C/xC1IFRRoBfanN4hxyonQmCGl+q6TaD9DUlPMSF7xUkUShMdoSPqGCsSJ8rPZHzk8NsoARrE0JTScqT8nMsSVmvDQdHKkR2rRm4r/ef1URxd+RkWSaiLwfFGUMqhjOA0FDqgkWLOJIQhLam6FeIQkwtpEVzEhuIsv/yWds7rbqDduG9XmZRFHGRyAI1ADLjgHTXANWqANMHgAT+AFvFqP1rP1Zr3PW0tWMbMPfsH6+AbIX5lC</latexit>
  <latexit sha1_base64="SE9o3XWOBk8ZJeepFbQiadv44wE=">AAACHHicbZDLSgMxFIYz9VbrbdSlm2ARK5QyowVdFt24KFipvUBnGDJppg3NXEgyQhnmQdz4Km5cKOLGheDbmLazsK0/BP585xyS87sRo0Iaxo+WW1ldW9/Ibxa2tnd29/T9g7YIY45JC4cs5F0XCcJoQFqSSka6ESfIdxnpuKObSb3zSLigYfAgxxGxfTQIqEcxkgo5+oWVWEMkE0vQgY/SUvOsDOeAOFXkrlR3mmVYd9TNSh29aFSMqeCyMTNTBJkajv5l9UMc+ySQmCEheqYRSTtBXFLMSFqwYkEihEdoQHrKBsgnwk6my6XwRJE+9EKuTiDhlP6dSJAvxNh3VaeP5FAs1ibwv1ovlt6VndAgiiUJ8OwhL2ZQhnCSFOxTTrBkY2UQ5lT9FeIh4ghLlWdBhWAurrxs2ucVs1qp3leLtessjjw4AsegBExwCWrgFjRAC2DwBF7AG3jXnrVX7UP7nLXmtGzmEMxJ+/4FfvSfsg==</latexit>
  <latexit sha1_base64="QBYy0hJcCGhd6ey3B86mjeNPezo=">AAAB83icbVDLSgNBEOyNrxhfUY9eBoMQQcKuBPQY9KDHiOYB2SXMTmaTIbO7wzwCIeQ3vHhQxKs/482/cZLsQRMLGoqqbrq7QsGZ0q777eTW1jc2t/LbhZ3dvf2D4uFRU6VGEtogKU9lO8SKcpbQhmaa07aQFMchp61weDvzWyMqFUuTJz0WNIhxP2ERI1hbyS8/+sQINLpAd+fdYsmtuHOgVeJlpAQZ6t3il99LiYlpognHSnU8V+hggqVmhNNpwTeKCkyGuE87liY4piqYzG+eojOr9FCUSluJRnP198QEx0qN49B2xlgP1LI3E//zOkZH18GEJcJompDFoshwpFM0CwD1mKRE87ElmEhmb0VkgCUm2sZUsCF4yy+vkuZlxatWqg/VUu0miyMPJ3AKZfDgCmpwD3VoAAEBz/AKb45xXpx352PRmnOymWP4A+fzBxUmkGo=</latexit>
  <latexit sha1_base64="Hq2FkOTYn0FfM19J2f5XONWKY7g=">AAACFXicbVA9SwNBEN3zM8avqKXNYhAsJNxJQEvRQsuIRoXccextJnFxd+/YnQuGI/4IG/+KjYUitoKd/8ZNTOHXg4HHezPMzEsyKSz6/oc3MTk1PTNbmivPLywuLVdWVs9tmhsOTZ7K1FwmzIIUGpooUMJlZoCpRMJFcn049C96YKxI9Rn2M4gU62rREZyhk+LKdohwgwUzXcVuBnHRC4WmR5SGFlAJnVt6OrilKj5t9SIaV6p+zR+B/iXBmFTJGI248h62U54r0Mgls7YV+BlGbhsKLmFQDnMLGePXrAstRzVTYKNi9NWAbjqlTTupcaWRjtTvEwVT1vZV4joVwyv72xuK/3mtHDt7USF0liNo/rWok0uKKR1GRNvCAEfZd4RxI9ytlF8xwzi6IMsuhOD3y3/J+U4tqNfqJ/Xq/sE4jhJZJxtkiwRkl+yTY9IgTcLJHXkgT+TZu/cevRfv9at1whvPrJEf8N4+AXuOnvw=</latexit>
  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, it requires computing the initial IE for every node in the first step. We will try to alleviate both with the two subsequent methods.
sections.heading: 3.3 GRAPH REINFORCEMENT LEARNING FOR INFLUENCE MAXIMIZATION (GRIM)
sections.text: 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 LS ∈ {0, 1}n, which can be computed by adding the activations of each layer Ht, summing along the axis of the hidden layer size, and thresholding to get a binary vector:
  LS = 1
  { T∑
  t=0
  ∑dt i=0 H i t dt ≥ 0 } , (7)
  where T is the number of layers, and Hit ∈ Rn×1 is a column from Ht. This vector contains a label for each node whose sign indicates if it is predicted to be influenced. We compute the average representation because dt 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 each 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 a direct estimate of a new candidate’s s marginal gain without rerunning GLIE(S ∪ s,G), which is what we try to avoid. To this end, we utilize a double Q-network (Van Hasselt et al., 2016) and the model is depicted in Fig. 1 (middle and right part). 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 GLIE-CELF. We also keep a list of each node’s initial influence set Ls. Subsequently, the Q-network produces a Q-value for each node s 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 O(S, s) = ∑n i=0 1{Lis − LiS ≥ 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 is composed by two layers:
  Q(u, S,G) = ReLU(ReLU([σ̂S , σ̂s, O(S, s)]Wk)Wq), (8)
  where Wq ∈ Rhd×1, and hd is the hidden layer size. We utilize a greedy policy to choose the next seed, similar to Dai et al. (2017): π(u|S) = argmaxu∈S Q(u, 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). (9)
  During training, we use epsilon-greedy to simulate an IM “game” and balance between exploration and exploitation. We store as a train tuple the current state-action embedding {σ̂(S), σ̂(s′), O(S, s′)}, the new state embedding along with all next possible actions {σ̂(S ∪ s), σ̂(s), O(S, s)}, s ∈ V and the reward r. Throughout the IM, we randomly sample from the memory and train the parameters of GRIM. GLIE is frozen, because apart from providing graph and node embeddings, it is only used for the computation of the reward—thus, it is not updated. The strategy to pretrain a graph encoding layer on a supervised task and use it as part of the Q-network has proven beneficial in similar works (Mirhoseini et al., 2021). In our case though we found out that without the overlapO 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.
sections.heading: 3.4 POTENTIALLY UNINFLUENCED NEIGHBORS (PUN)
sections.text: 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 a simpler influence set representation then in 7. Let L̂S , L′S ∈ {0, 1}n be the binary vectors with 1s in nodes predicted to be uninfluenced and nodes predicted to be influenced respectively:
  L̂S = 1
  { d1∑
  i=0
  Hi1 ≤ 0 } L′S = 1 { d1∑
  i=0
  Hi1 ≥ 0 }
  (10)
  L′S is simpler than LS defined in Eq. (7) and provides a more rough estimate, but it allows for a simpler influence spread which we can optimize greedily.
  σm(S) = |L′S | (11) We can use L̂S and message passing to predict the amount of a node’s neighborhood that remains uninfluenced, i.e., the Potentially Uninfluenced Neighbors (PUN), weighted by the respective probability of influence For a node u,
  mS [u] = ∑
  v∈N(u) Au,vL̂v = A
  > u · L̂S ∈ Rn×1. (12)
  For efficiency, we can compute mS = AT L̂ which can be considered an approximation to all nodes marginal gain on their immediate neighbors. We can thus optimize this using argmax(mS), as shown in Fig. (1). In order to establish that σm can be optimized greedily with a theoretical guarantee of (1− 1e )OPT, we prove its monotonocity and submodularity in Appendix A.2. Theorem 1. The influence spread σm is submodular and monotone.
  PUN can be seen in the left part of Fig. 1. We start by setting the first seed as the node with the highest degree, which can be considered a safe assumption as in practice it is always part of seed sets. We use GLIE(S,G) to retrieve L̂S , which we use to find the next node based on argmaxv∈G\S mS [v] and the new L̂S∪{v}. One disadvantage of PUN is that σm is an underestimation of the predicted influence, as can be seen in Fig. 2. Contrasted with the upper bound, DMP, σm is not as accurate as σ̂, but allows us to compute efficiently a submodular proxy for the marginal gain. This underestimation means that a part of the network considered uninfluenced in L̂S is measured as potential gain for their neighbors, hence the ranking based on mS can be effected negatively. As we observed in Fig. 2, the divergence of σm increases with the size of the seed set.
  For this purpose, we will use adaptive full-feedback selection (AFF), where after selecting a new seed node, we remove it from the network along with nodes predicted to be influenced. It has been proved in the seminal work of Golovin & Krause (2011) that an AFF greedy algorithm for a submodular and monotonic function is guaranteed to have a competitive performance with the optimal policy. In our case, we will use an AFF update every k 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 σm(S).
sections.heading: 4 EXPERIMENTS
sections.text: All the experiments are performed in a PC with an NVIDIA GPU TITAN V (12GB RAM), 256GB RAM and an Intel(R) Xeon(R) W-2145 CPU @ 3.70GHz. The python implementation can be found in the supplementary material.
sections.heading: 4.1 INFLUENCE ESTIMATION
sections.text: 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-Kim 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 probabilities are assigned based on the weighted cascade model, i.e., a node u has equal probability 1/deg(u) to be influenced by each of her N (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 et al., 2003). To label the samples, we run the CELF algorithm using 1, 000 Monte Carlo (MC) ICs for influence estimation, for up to 5 seeds. The optimum seed set for size 1 to 5 is stored, along with 30 random negative samples for each seed set 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.1.
  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 evaluate the capability of the model to generalize in networks that are larger by one factor. The third is a set of three real-world graphs, namely the Crime (CR), HI-II14 (HI), and GR collaborations (GR). More information about the datasets is given in Table 1. 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 a 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.
  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
  is violated by the weighted cascade model and the computed influence is exaggerated to the point it surpasses the nodes of the network. The average error throughout all datasets and the average influence can be seen in Table 2, 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 3, 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 3, amounts to 0.11, 0.22 and 0.19 seconds for the three datasets respectively.
sections.heading: 4.2 INFLUENCE MAXIMIZATION
sections.text: The training parameters for GRIM are analyzed in Appendix B (B.1). For comparison, we use a state-of-the-art IM method, IMM (Tang et al., 2015) which capitalizes on reverse reachable sets (Borgs et al., 2014) to estimate influence. Specifically, it produces a series of such influence sketches and uses them to 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-art and has similar influence spreads with Tang et al. (2014), while surpassing various heuristics (Jung et al., 2012). We set e = 0.5 as proposed by the authors. We also compare with FINDER, which is analyzed in 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) .
  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 are shown in Table 6. The top result is in bold and the second best is underlined. The influence spread for smaller seed sets and the time for heuristics are attached in Appendix C, along with comparisons of PUN without the use of GPU. One can see
  that GLIE-CELF exhibits overall superior influence quality compared to the rest of the methods, but is quite slower. GRIM is slightly faster than GLIE-CELF but is the second slowest method. This quantifies the substantial overhead caused by computing the influence spread of all candidate seeds in the first step. Their time difference amounts to how many more IEs GLIE-CELF performs in every step compared to GRIM, which performs only one. This is more obvious with PUN, which requires only one IE in every step and no initial computation. It 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 in both seed set sizes. We can thus contend that it provides the best accuracy-efficiency tradeoff from the examined methods. IMM is the third slowest method, but it 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 a bigger seed set than 100 nodes. Thus, we can hypothesize it is quite faster for a limited seed set, but the quality of the retrieved seeds is the least accurate among all methods.
sections.heading: 5 CONCLUSION
sections.text: 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. GLIE-CELF, an adaptation of a classical algorithm that surpasses SOTA but with significant computational overhead. GRIM, a Qlearning model that learns to 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 a balance between efficiency and accuracy.
  A typical IM algorithm needs a 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 advantage of a 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 an experiment with contextual information a natural next step, given a proper dataset. Our approach can also be utilized to address the minimum vertex cover in large graphs, as it is a problem related to influence maximization and there exists models that work well in both (Manchanda et al., 2020). Finally, we also plan to examine the potential of 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.
  Ethics and Reproducibility Our influence maximization methods can 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 on the general intent to vote. On the bright side, there has been extensive research on battling such effects (Tu et al., 2020), by producing campaigns that are equally effective and hence balancing each other (Bharathi et al., 2007). More importantly, GLIE can be used as part of the mitigation strategy (Tu et al., 2020), as a black box that substitutes the method’s RR-set based influence estimation, to 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 to other influence maximization algorithms (Budak et al., 2011).
  Regarding the reproducibility of our experiments, we have attached all codes in 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.
sections.heading: APPENDIX A
sections.text: We recall the first corollary from Sec. 3 and detail the proof below.
  Corollary 3.0.2. The repeated product Ht+1 = A·Ht computes an upper bound to the real influence probabilities of each infected node at step t+ 1.
  Proof. We have:
  p̂t(u|St) = Au ·Ht (13) = ∑
  v∈N (u)∩St p̂vpvu (14)
  ≥ ∑
  v∈N (u)∩St pvpvu (15)
  ≥ 1− ∏
  v∈N (u)∩St (1− pvpvu) (16)
  = pt(u|St) (17) (18)
  • (15) stems from Eq. 3 in the manuscript:
  p̂(u|S) = Au ·X = ∑
  v∈N (u)∩S
  1
  deg(u) =
  ∑
  v∈N (u)∩S pvu ≥ 1−
  ∏
  v∈N (u)∩S (1− pvu) = p(u|S).
  (19)
  • (16) can be proved by induction similar to Zhou et al. (2015). For every pv ≤ 1 , the base case∑ v∈X pvpvu ≥ 1− ∏ v∈X (1− pvpvu) is obvious for |X | = 1. For |X | > 1, we have:
  1− ∏
  v∈X (1− pvpvu) = 1− (1− pxpxu)
  ∏
  v∈X\x (1− pvpvu)
  = 1− ∏
  v∈X\x (1− pvpvu) + pxpxu
  ∏
  v∈X\x (1− pvpvu)
  ≤ ∑
  v∈X\x pvpvu + pxpxu
  ∏
  v∈X\x (1− pvpvu)
  ≤ ∑
  v∈X\x pvpvu + pxpxu
  = ∑
  v∈X pvpvu. (20)
  • (17) we have p(u|v) = pvpvu per definition of the independent cascade, and consequently p(u|S) = 1 −∏v∈N (u)∩S(1 − pvpvu), where pv = 1 for v ∈ S1, which are the initial seed set that are activated deterministically. We can thus contend that Eq. equation 18 stands, and the computed probabilities are an upper bound of the real influence probabilities. Hence the influence spread, which is computed as σ̂(S) = ∑ (u,v)∈E puv is also an upper bound to the real σ(S).
  Now we address the Theorem from Sec. 3.4 and detail the proof below.
  Theorem 1. The influence spread σm is submodular and monotone.
  For the purposes of the proof, Xi ∈ {0, 1}n×d is the input and Hi ∈ Rn×hd is the output of the first neural layer for the input seed set Si, and P ∈ {1}hd×1. Moreover we define the support function supp(v) = {i ∈ [1, n], vi 6= 0} James et al. (2013) as the set of indices of non zero rows in a matrix such as Xi. Finally let R represent ReLU and btr, sttr the mean and standard deviation computed by the batchnorm. Each step is justified further below.
  Proof. Monotonocity, ∀i < j, Si ⊂ Sj :
  supp(Xj) ⊃ supp(Xi) (21) supp(XjW ) ⊇ supp(XiW ) (22) supp(AXjW ) ⊇ supp(AXiW ) (23) supp(R(AXjW )) ⊇ supp(R(AXiW )) (24)
  supp
  ( R(AXjW )− btr
  sttr
  ) ⊇ supp ( (R(AXiW )− btr)
  sttr
  ) (25)
  supp(Hj) ⊇ supp(H(Si)) (26) supp(HjP ) ⊇ supp(HiP ) (27) |1>0 {HjP} | ≥ |1>0 {HiP} | (28)
  |L′j | ≥ |L′i| (29) σm(Sj) ≥ σm(Si) (30)
  (31)
  1. (21) stems by the definition of X in Eq. (1).
  2. (22) Xj is a convex hull that contains Xi (Boyd et al., 2004). We multiply both sides by a real matrix W ∈ Rd×hd 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 Xi and Xj and hence cannot interfere with the support of Xj over Xi. The statement becomes more obvious for X ∈ {0, 1}n×1 and W ∈ R1×1. Note that both can result in zero matrices so we use subset or equal.
  3. (23) A is a non-negative matrix.
  4. (24) ReLU is a non negative monotonically increasing function.
  5. (25) Subtract by the same number and divide by the same positive number.
  6. (26) Definition in Eq. (4).
  7. (27) P is positive.
  8. (28) By definition of the support.
  9. (29) By definition of L′S .
  For the proof of submodularity we have to define Xiu = XSi∪u, u ∈ V and note by the definition of the input that |Xju −Xj | = |Xiu −Xi| for the l1 norm (sum of all elements):
  Proof. Submodularity ∀i < j, Si ⊂ Sj , ,: |Xju −Xj | = |Xiu −Xi| (32)
  A|Xju −Xj | = A|Xiu −Xi| (33) |A(Xju −Xj)| = |A(Xiu −Xi)| (34) |AXju −AXj | = |AXiu −AXi| (35)
  |AXjuW −AXjW | = |AXiuW −AXiW | (36) R(|AXjuW −AXjW |)− 2btr = R(|AXiuW −AXiW | − 2btr) (37) |R(AXjuW )−R(AXjW )− 2btr| = |R(AXiuW )−R(AXiW )− 2btr| (38) supp(R(AXjuW )−R(AXjW )− 2btr) = supp(R(AXiuW )−R(AXiW )− 2btr)
  (39) supp(R(AXjuW − btr))− supp(R(AXjW )− btr) ⊆ supp(R(AXiuW − btr))− supp(R(AXiW )− btr)
  (40) supp(Hju)− supp(Hj) ⊆ supp(Hiu)− supp(Hi) (41) σm(Sj ∪ {u})− σm(Sj) ≤ σm(Si ∪ {u})− σm(Si) (42)
  (43)
  1. Distributive property
  2. (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 norm of A ,which is stochastic ,is bounded by V hence Xu can give up to the same gain to AXj and AXi, the same number btr is subtracted, and more elements are activated by Xj then Xi as shown in Eq. 29.
  4. (41) We skipped dividing by sttr for brevity.
  5. (42) Arrive with similar steps as 27 - 30.
  Regarding the approximation of the marginal gain we first show that choosing the node corresponding to the maximum mS will give the maximum L′ju: A ′ uL̂j ≥ A′v L̂i ⇒ L′ju ≥ L′iv .
  A′uL̂j = ∑
  v∈N(u) A′uvL̂j [v] =
  ∑
  v∈N(u) AuvL
  ′ j [u] =
  ∑
  v∈N(u) AuvXju (44)
  (45)
  This means that mS gives the node u that improves the biggest number of rows in AXju that are not already considered influenced. Since we know from eq. 30 that a AXiu ≥ AXiv ⇒ |L′iu| ≥ |L′iv|, 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, ∀i < j, Si ⊂ Sj , starting from (28):
  |1>0 {HjP} | ≥ |1>0 {HiP} | |1≤0 {HjP} | ≤ |1≤0 {HiP} | (46)
  A′uL̂j ≤ A′uL̂i (47) mSj [u] ≤ mSi [u] (48)
  (|L′j |+mSj [u])− |L′j | ≤ (|L′i|+mSi [u])− |L′i| (49) σm(Sj ∪ {u})− σm(Sj) ≤ σm(Si ∪ {u})− σm(Si) (50)
  1. (30) Complementarity between elements that are ≤ 0 and elements > 0. 2. (32) Definition in Eq. (10) and multiply with non-negative row u from matrix A′.
  3. (33) Definition in Eq. ( 12).
  4. (34) Adding and subtracting |Lj | and |Li|. 5. (1) By definition of σm in Eq. (11) and the marginal gain of u, we arrive at submodularity in Eq.
  (1).
sections.heading: APPENDIX B
sections.heading: B.1 TRAINING
sections.text: As mentioned in the main text each training sample for GLIE corresponds to a triple of a graph G a seed set S and a ground truth influence spread σ(S) that serves as a label to regress on. We use two different ways to come up with the seed sets S for varying sizes of S from 1 to 5. We use random 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 σ 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 a more balanced form of supervision, as you expect the crucial majority of the seed sets to have an average σ. 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 it 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.
  GRIM is trained on a dataset that consists of 50 random BA graphs of 500 – 2, 000 nodes. It is trained by choosing 100 seeds sequentially, to maximize the reward (delay = 2 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 a 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 a certain degree threshold based on the distribution, a common practice in the literature (Chen et al., 2009; Manchanda et al., 2020).
sections.heading: B.2 ADAPTIVE FULL FEEDBACK
sections.text: We see in Fig. 3 that the pattern that is prevalent in the two datasets described in Section 3.4 is retained in other graphs.
sections.heading: B.3 GLIE SUBMODULARITY AND MONOTONICITY
sections.text: In this section we design an experiment to empirically prove that GLIE’s output is submodular and monotonous. For each of the real datasets, we use the seed set retrieved by GLIE-CELF and a random seed set to quantify the differences between subsequent estimations. To be specific, we have a sequence S that represents the seed set and a sequence R that represents the random nodes, with Sj being the seed set up to jth element and sj being the jth element, and similarly rj for R. We compute the marginal gain to check for monotonicity:
  mss = σ̂(Sj ∪ sj+1)− σ̂(Sj) (51)
  msr = σ̂(Sj ∪ rj+1)− σ̂(Sj), (52)
  and for submodularity, we have , with i = j − 1 : sss = (σ̂(Si ∪ sj+1)− σ̂(Si))− (σ̂(Sj ∪ sj+1)− σ̂(Sj)) (53)
  ssr = (σ̂(Si ∪ rj+1)− σ̂(Si))− (σ̂(Sj ∪ rj+1)− σ̂(Sj)). (54) In Figures 4 to 7, we plot m and s for some of our datasets. Regarding s, since we require a constant node, we randomly sample one of the seeds sj and a random node rj and visualize the sequences of both s 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, we verify that m and s 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.
  B.4 IMM AND PUN WITH UNIFORM PROBABILITIES
  We compare IMM and PUN on the same graphs with uniform influence probabilities p = 0.01 in Figure 8. We clearly observe that PUN outperforms IMM.
sections.heading: APPENDIX C
sections.heading: C.5 RESULTS FOR SMALLER SEED SETS
sections.heading: C.6 COMPUTATIONAL TIME OF HEURISTICS
sections.heading: C.7 PUN’S COMPUTATIONAL TIME WITHOUT GPU
sections.text: We performed experiments to compare PUN without the use of GPU in Table (10), where it is visible that GPU provides a substantial acceleration, but PUN remains the faster option even without it.
sections.heading: C.8 RELATIVE ERROR OF GLIE FOR LARGER SEED SETS
sections.text: To quantify the potential of GLIE for larger seed sets, we sample 9 random seed sets and 1 with the highest degree nodes and compute the error of DMP and GLIE, with the ground truth influence
  divided by the average influence in Table (11). We see that the error does not increase significantly as the seed set increases, and that GLIE outperforms DMP in GR while the reverse happens in CR and HT.