# adaptive_influence_maximization_with_myopic_feedback__8c41cc1f.pdf

Adaptive Inﬂuence Maximization with Myopic Feedback

Binghui Peng Columbia University bp2601@columbia.edu

Wei Chen Microsoft Research weic@microsoft.com

We study the adaptive inﬂuence maximization problem with myopic feedback under the independent cascade model: one sequentially selects k nodes as seeds one by one from a social network, and each selected seed returns the immediate neighbors it activates as the feedback available for later selections, and the goal is to maximize the expected number of total activated nodes, referred as the inﬂuence spread. We show that the adaptivity gap, the ratio between the optimal adaptive inﬂuence spread and the optimal non-adaptive inﬂuence spread, is at most 4 and at least e/(e 1), and the approximation ratios with respect to the optimal adaptive inﬂuence spread of both the non-adaptive greedy and adaptive greedy algorithms are at least 1

e) and at most e2+1 (e+1)2 < 1 1

e. Moreover, the approximation ratio of the non-adaptive greedy algorithm is no worse than that of the adaptive greedy algorithm, when considering all graphs. Our result conﬁrms a long-standing open conjecture of Golovin and Krause (2011) on the constant approximation ratio of adaptive greedy with myopic feedback, and it also suggests that adaptive greedy may not bring much beneﬁt under myopic feedback.

1 Introduction

Inﬂuence maximization is the task of given a social network and a stochastic diffusion model on the network, ﬁnding the k seed nodes with the largest expected inﬂuence spread in the model [11]. Inﬂuence maximization and its variants have applications in viral marketing, rumor control, etc. and have been extensively studied (cf. [6, 12]).

In this paper, we focus on the adaptive inﬂuence maximization problem, where seed nodes are sequentially selected one by one, and after each seed selection, partial or full diffusion results from the seed are returned as the feedback, which could be used for subsequent seed selections. Two main types of feedback have been proposed and studied before: (a) full-adoption feedback, where the entire diffusion process from the seed selected is returned as the feedback, and (b) myopic feedback, where only the immediate neighbors activated by the selected seed are returned as the feedback. Under the common independent cascade (IC) model where every edge in the graph has an independent probability of passing inﬂuence, Golovin and Krause [7] show that the full-adoption feedback model satisﬁes the key adaptive submodularity property, which enables a simple adaptive greedy algorithm to achieve a (1 1/e) approximation to the adaptive optimal solution. However, the IC model with myopic feedback is not adaptive submodular, and Golovin and Krause [7] only conjecture that in this case the adaptive greedy algorithm still guarantees a constant approximation. To the best of our knowledge, this conjecture is still open before our result in this paper, which conﬁrms that indeed adaptive greedy is a constant approximation of the adaptive optimal solution.

Work is mostly done while Binghui was at Tsinghua University and visiting Microsoft Research Asia as an intern.

33rd Conference on Neural Information Processing Systems (Neur IPS 2019), Vancouver, Canada.

In particular, our paper presents two sets of related results on adaptive inﬂuence maximization with myopic feedback under the IC model. We ﬁrst study the adaptivity gap of the problem (Section 3), which is deﬁned as the ratio between the adaptive optimal solution and the non-adaptive optimal solution, and is an indicator on how useful the adaptivity could be to the problem. We show that the adaptivity gap for our problem is at most 4 (Theorem 1) and at least e/(e 1) (Theorem 2). The proof of the upper bound 4 is the most involved, because the problem is not adaptive submodular, and we have to create a hybrid policy that involves three independent runs of the diffusion process in order to connect between an adaptive policy and a non-adaptive policy. Next we study the approximation ratio with respect to the adaptive optimal solution for both non-adaptive greedy and adaptive greedy algorithms (Section 4). We show that the approximation ratios of both algorithms are at least 1

e) (Theorem 3), which combines the adaptivity upper bound of 4 with the results that both algorithms achieve (1 1/e) approximation of the non-adaptive optimal solution (the (1 1/e) approximation ratio for the adaptive greedy algorithm requires a new proof). We further show that the approximation ratios for both algorithms are at most e2+1 (e+1)2 0.606, which is strictly less than 1 1/e 0.632, and the approximation ratio of non-adaptive greedy is the same as the worst approximation ratio of the adaptive greedy over a family of graphs (Theorem 4).

In summary, our contribution is the systematic study on adaptive inﬂuence maximization with myopic feedback under the IC model. We prove both constant upper and lower bounds on the adaptivity gap in this case, and constant upper and lower bounds on the approximation ratios (with respect to the optimal adaptive solution) achieved by non-adaptive greedy and adaptive greedy algorithms. The constant approximation ratio of the adaptive greedy algorithm answers a long-standing open conjecture afﬁrmatively. Our result on the adaptivity gap is the ﬁrst one on a problem not satisfying adaptive submodularity. Our results also suggest that adaptive greedy may not bring much beneﬁt under the myopic feedback model.

Due to the space constraint, full proof details are included in the supplementary material.

Related Work. Inﬂuence maximization as a discrete optimization task is ﬁrst proposed by Kempe et al. [11], who propose the independent cascade, linear threshold and other models, study their submodularity and the greedy approximation algorithm for the inﬂuence maximization task. Since then, inﬂuence maximization and its variants have been extensively studied. We refer to recent surveys [6, 12] for the general coverage of this area.

Adaptive submodularity is formulated by Golovin and Krause [7] for general stochastic adaptive optimization problems, and they show that the adaptive greedy algorithm achieves 1 1/e approximation if the problem is adaptive monotone and adaptive submodular. They study the inﬂuence maximization problem under the IC model as an application, and prove that the full-adoption feedback under the IC model is adaptive submodular. However, in their ar Xiv version, they show that the myopic feedback version is not adaptive submodular, and they conjecture that adaptive greedy would still achieve a constant approximation in this case.

Adaptive inﬂuence maximization has been studied in [19, 20, 16, 13, 18, 10, 17, 5]. Tong et al. [19] provide both adaptive greedy and efﬁcient heuristic algorithms for adaptive inﬂuence maximization. Their theoretical analysis works for the full-adoption feedback model but has a gap when applied to myopic feedback, which is conﬁrmed by the authors. Yuan and Tang [20] introduce the partial feedback model and develop algorithms that balance the tradeoff between delay and performance, and their partial feedback model does not coincide with the myopic feedback model. Salha et al. [13] consider a different diffusion model where edges can be reactivated at each time step, and they show that myopic feedback under this model is adaptive submodular. Sun et al. [16] study the multi-round adaptive inﬂuence maximization problem, where k seeds are selected in each round and at the end of the round the full-adoption feedback is returned. Tong [18] introduces a general feedback model and develops some heuristic algorithms for this model. Han et al. [10] and Tang et al. [17] propose efﬁcient adaptive algorithms for inﬂuence maximization and seed set minimization respectively based on the reverse inﬂuence sampling approach, both for IC models with full-adoption feedback. In a separate paper [5], we study the adaptivity gap in the IC model with full-adoption feedback for several classes of graphs such as trees and bipartite graphs. A different two stage seeding process has also been studied [14, 3, 15], but the model is quite different, since their ﬁrst stage of selecting a node set X is only to introduce the neighbors of X as seeding candidates for the second stage.

Adaptivity gap has been studied by two lines of research. The ﬁrst line of work utilizes multilinear extension and adaptive submodularity to study adaptivity gaps for the class of stochastic submodular maximization problems and give an e/(e 1) upper bound for matroid constraints [2, 1]. The second line of work [8, 9, 4] studies the stochastic probing problem and proposes the idea of random-walk non-adaptive policy on the decision tree, which partially inspires our analysis. However, their analysis also implicitly depends on adaptive submodularity. In contrast, our result on the adaptivity gap is the ﬁrst on a problem that does not satisfy adaptive submodularity (see Section 3.1 for more discussions).

2 Model and Problem Deﬁnition

Diffusion Model. In this paper, we focus on the well known Independent Cascade (IC) model as the diffusion model. In the IC model, the social network is described by a directed inﬂuence graph G = (V, E, p), where V is the set of nodes (|V | = n), E V V is the set of directed edges, and each directed edge (u, v) E is associated with a probability puv [0, 1]. The live edge graph L = (V, L(E)) is a random subgraph of G, for any edge (u, v) E, (u, v) L(E) with independent probability puv. If (u, v) L(E), we say edge (u, v) is live, otherwise we say it is blocked. The dynamic diffusion in the IC model is as follows: at time t = 0 a live-edge graph L is sampled and nodes in a seed set S V are activated. At every discrete time t = 1, 2, . . ., if a node u was activated at time t 1, then all of u s out-going neighbors in L are activated at time t. The propagation continues until there are no more activated nodes at a time step. The dynamic model can be viewed equivalently as every activated node u has one chance to activate each of its out-going neighbor v with independent success probability puv. Given a seed set S, the inﬂuence spread of S, denoted σ(S), is the expected number of nodes activated in the diffusion process from S, i.e. σ(S) = EL[|Γ(S, L)|], where Γ(S, L) is the set of nodes reachable from S in graph L.

Inﬂuence Maximization Problem. Under the IC model, we formalize the inﬂuence maximization (IM) problem in both non-adaptive and adaptive settings. Inﬂuence maximization in the non-adaptive setting follows the classical work of [11], and is deﬁned below. Deﬁnition 1 (Non-adaptive Inﬂuence Maximization). Non-adaptive inﬂuence maximization is the problem of given a directed inﬂuence graph G = (V, E, p) with IC model parameters {puv}(u,v) E and a budget k, ﬁnding a seed set S of at most k nodes such that the inﬂuence spread of S , σ(S ), is maximized, i.e. ﬁnding S argmax S V,|S| kσ(S).

We formulate inﬂuence maximization in the adaptive setting following the framework of [7]. Let O denote the set of states, which informally correspond to the feedback information in the adaptive setting. A realization φ is a function φ : V O, such that for u V , φ(u) represents the feedback obtained when selecting u as a seed node. In this paper, we focus on the myopic feedback model [7], which means the feedback of a node u only contains the status of the out-going edges of u being live or blocked. Informally it means that after selecting a seed we can only see its one step propagation effect as the feedback. The realization φ then determines the status of every edge in G, and thus corresponds to a live-edge graph. As a comparison, the full-adoption feedback model [7] is such that for each seed node u, the feedback contains the status of every out-going edge of every node v that is reachable from u in a live-edge graph L. This means that after selecting a seed u, we can see the full cascade from u as the feedback. In the full-adoption feedback case, each realization φ also corresponds to a unique live-edge graph. Henceforth, we refer to φ as both a realization and a liveedge graph interchangeably. In the remainder of this section, the terminologies we introduce apply to both feedback models, unless we explicitly point out which feedback model we are discussing.

Let R denote the set of all realizations. We use Φ to denote a random realization, following the distribution P over random live-edge graphs (i.e. each edge (u, v) E has an independent probability of puv to be live in Φ). Given a subset S and a realization φ, we deﬁne inﬂuence utility function f : 2V R R+ as f(S, φ) = |Γ(S, φ)|, where R+ is the set of non-negative real numbers. That is, f(S, φ) is the number of nodes reachable from S in realization (live-edge graph) φ. Then it is clear that inﬂuence spread σ(S) = EΦ P[f(S, Φ)].

In the adaptive inﬂuence maximization problem, we could sequentially select nodes as seeds, and after selecting one seed node, we could obtain its feedback, and use the feedback to guide further seed selections. A partial realization ψ maps a subset of nodes in V , denoted dom(ψ) for domain of ψ, to their states. Partial realization ψ represents the feedback we could obtain after nodes in dom(ψ) are selected as seeds. For convenience, we also represent ψ as a relation, i.e., ψ = {(u, o) V O :

u dom(ψ), o = ψ(u)}. We say that a full realization φ is consistent with a partial realization ψ, denoted as φ ψ, if φ(u) = ψ(u) for every u dom(ψ).

An adaptive policy π is a mapping from partial realizations to nodes. Given a partial realization ψ, π(ψ) represents the next seed node that policy π would select when it sees the feedback represented by ψ. Under a full realization φ consistent with ψ, after selecting π(ψ), the policy would obtain feedback φ(π(ψ)), and the partial realization would grow to ψ = ψ {(π(ψ), φ(π(ψ)))}, and policy π could pick the next seed node π(ψ ) based on partial realization ψ . For convenience, we only consider deterministic policies in this paper, and the results we derive can be easily extend to randomized policies. Let V (π, φ) denote the set of nodes selected by policy π under realization φ. For the adaptive inﬂuence maximization problem, we consider the simple cardinality constraint such that |V (π, φ)| k, i.e. the policy only selects at most k nodes. Let Π(k) denote the set of such policies.

The objective of an adaptive policy π is its adaptive inﬂuence spread, which is the expected number of nodes that are activated under policy π. Formally, we deﬁne the adaptive inﬂuence spread of π as σ(π) = EΦ P[f(V (π, Φ), Φ)]. The adaptive inﬂuence maximization problem is deﬁned as follows. Deﬁnition 2 (Adaptive Inﬂuence Maximization). Adaptive inﬂuence maximization is the problem of given a directed inﬂuence graph G = (V, E, p) with IC model parameters {puv}(u,v) E and a budget k, ﬁnding an adaptive policy π that selects at most k seed nodes such that the adaptive inﬂuence spread of π , σ(π ), is maximized, i.e. ﬁnding π argmaxπ Π(k)σ(π).

Note that for any ﬁxed seed set S, we can create a policy πS that always selects set S regardless of the feedback, which means any non-adaptive solution is a feasible solution for adaptive inﬂuence maximization. Therefore, the optimal adaptive inﬂuence spread should be at least as good as the optimal non-adaptive inﬂuence spread, under the same budget constraint.

Adaptivity Gap. Since the adaptive policy is usually hard to design and analyze and the adaptive interaction process may also be slow in practice, a fundamental question for adaptive stochastic optimization problems is whether adaptive algorithms are really superior to non-adaptive algorithms. The adaptivity gap measures the gap between the optimal adaptive solution and the optimal nonadaptive solution. More concretely, if we use OPTN(G, k) (resp. OPTA(G, k)) to denote the inﬂuence spread of the optimal non-adaptive (resp. adaptive) solution for the IM problem in an inﬂuence graph G under the IC model with seed budget k, then we have the following deﬁnition. Deﬁnition 3 (Adaptivity Gap for IM). The adaptivity gap in the IC model is deﬁned as the supremum of the ratios of the inﬂuence spread between the optimal adaptive policy and the optimal non-adaptive policy, over all possible inﬂuence graphs G and seed budget k, i.e.,

OPTA(G, k) OPTN(G, k). (1)

Submodularity and Adaptive Submodularity. Non-adaptive inﬂuence maximization is often solved via submodular function maximization technique. A set function f : 2V R is submodular if for all S T V and all u V \ T, f(S {u}) f(S) f(T {u}) f(T). Set function f is monotone if for all S T V , f(S) f(T). Kempe et al. [11] show that the inﬂuence spread function σ(S) under the IC model is monotone and submodular, and thus a simple non-adaptive greedy algorithm achieves a (1 1

e) approximation of the optimal non-adaptive solution, assuming function evaluation σ(S) is given by an oracle.

Golovin and Krause [7] deﬁne adaptive submodularity for the adaptive stochastic optimization framework. In the context of adaptive inﬂuence maximization, adaptive submodularity can be deﬁned as follows. Given a utility function f, for any partial realization ψ and a node u dom(ψ), we deﬁne the marginal gain of u given ψ as f(u | ψ) = EΦ P[f(dom(ψ) {u}, Φ) f(dom(ψ), Φ)|Φ ψ], i.e. the expected marginal gain on inﬂuence spread when adding u to the partial realization ψ. A partial realization ψ is a sub-realization of another partial realization ψ if ψ ψ when treating both as relations. We say that the utility function f is adaptive submodular with respect to P if for any two ﬁxed partial realizations ψ and ψ such that ψ ψ , for any u dom(ψ ), we have f(u | ψ) f(u | ψ ), that is, the marginal inﬂuence spread of a node given more feedback is at most its marginal inﬂuence spread given less feedback. We say that f is adaptive monotone with respect to P if for any partial realization ψ with PrΦ P(Φ ψ) > 0, f(u | ψ) 0.

Golovin and Krause [7] show that the inﬂuence utility function under the IC model with full-adoption feedback is adaptive monotone and adaptive submodular, and thus the adaptive greedy algorithm achieves (1 1

e) approximation of the adaptive optimal solution. However, they show that the inﬂuence utility function under the IC model with myopic feedback is not adaptive submodular. They conjecture that the adaptive greedy policy still provides a constant approximation. In this paper, we show that the adaptive greedy policy provides a 1

e) approximation, and thus ﬁnally address this conjecture afﬁrmatively.

3 Adaptivity Gap in Myopic Feedback Model

In this section, we analyze the adaptivity gap for inﬂuence maximization problems under the myopic feedback model and derive both upper and lower bounds.

3.1 Upper Bound on the Adaptivity Gap

Our main result is an upper bound on the adaptivity gap for the myopic feedback model, which is formally stated below.

Theorem 1. Under the IC model with myopic feedback, the adaptivity gap for the inﬂuence maximization problem is at most 4.

Proof outline. We now outline the main ideas and the structure of the proof of Theorem 1. The main idea is to show that for each adaptive policy π, we could construct a non-adaptive randomized policy W(π), such that the adaptive inﬂuence spread σ(π) is at most four times the non-adaptive inﬂuence spread of W(π), denoted σ(W(π)). This would immediately imply Theorem 1. The non-adaptive policy W(π) is constructed by viewing adaptive policy π as a decision tree with leaves representing the ﬁnal seed set selected (Deﬁnition 4), and W(π) simply samples such a seed set based on the distribution of the leaves (Deﬁnition 5). The key to connect σ(π) with σ(W(π)) is by introducing a ﬁctitious hybrid policy π, such that σ(π) σ( π) 4σ(W(π)), where σ( π) is the aggregate adaptive inﬂuence spread (deﬁned in Eqs. (2) and (3)). Intuitively, π works on three independent realizations Φ1, Φ2, Φ3 and it adaptively selects seeds as π working on Φ1. The difference is that each selected seed has three independent chances to activate its out-neighbors according to the union of Φ1, Φ2, Φ3. The inequality σ(π) σ( π) is immediate and the main effort is on proving σ( π) 4σ(W(π)).

To do so, we ﬁrst introduce general notations σt(S) and σt(π) with t = 1, 2, 3, where σt(S) is the t-th aggregate inﬂuence spread for a seed set S and σt(π) is the t-th aggregate adaptive inﬂuence spread for an adaptive policy π, and they mean that all seed nodes have t independent chances to activate their out-neighbors. Obviously, σ( π) = σ3(π) and σ(W(π)) = σ1(W(π)). We then represent σt(W(π)) and σt(π) as a summation of k non-adaptive marginal gains f t(u | dom(ψs)) s and adaptive marginal gains f t(u | ψs) s, respectively (Deﬁnition 6 and Lemma 1), with respect to node s in different levels of the decision tree. Next, we establish the key connection between the adaptive marginal gain and the nonadaptive marginal gain (Lemma 3): f 3(u | ψ1) 2 f 2(u | dom(ψ1)). This immediately implies that σ3(π) 2σ2(W(π)). Finally, we prove that the t-th aggregate nonadaptive inﬂuence spread σt(S) is bounded by t σ(S), which implies that σ2(W(π)) 2σ(W(π)). This concludes the proof.

We remark that our introduction of the hybrid policy π is inspired by the analysis in [4], which shows that the adaptivity gap for the stochastic multi-value probing (SMP) problem is at most 2. However, our analysis is more complicated than theirs and thus is novel in several aspects. First, the SMP problem is simpler than our problem, with the key difference being that SMP is adaptive submodular but our problem is not. Therefore, we cannot apply their way of inductive reasoning that implicitly relies on adaptive submodularity. Instead, we have to use our marginal gain representation and redo the bounding analysis carefully based on the (non-adaptive) submodularity of the inﬂuence utility function on live-edge graphs. Moreover, our inﬂuence utility function is also sophisticated and we have to use three independent realizations in order to apply the submodularity on live-edge graphs, which results in an adaptivity bound of 4, while their analysis only needs two independent realizations to achieve a bound of 2. We now provide the technical proof of Theorem 1. We ﬁrst formally deﬁne the decision tree representation.

Deﬁnition 4 (Decision tree representation for adaptive policy). An adaptive policy π can be seen as a decision tree T (π), where each node s of T (π) corresponds to a partial realization ψs, with the root being the empty partial realization, and node s is a child of s if ψs = ψs {(π(ψs), φ(π(ψs)))} for some realization φ ψs. Each node s is associated with a probability ps, which is the probability that the policy π generates partial realization ψs, i.e. the probability that the policy would walk on the tree from the root to node s.

Next we deﬁne the non-adaptive randomized policy W(π), which randomly selects a leaf of T (π). Deﬁnition 5 (Random-walk non-adaptive policy [9]). For any adaptive policy π, let L(π) denote the set of leaves of T (π). Then we construct a randomized non-adaptive policy W(π) as follows: for any leaf ℓ L(π), W(π) picks leaf ℓwith probability pℓand selects dom(ψℓ) as the seed set.

Before proceeding further with our analysis, we introduce some notations for the myopic feedback model. In the myopic feedback model, we notice that the state spaces for all nodes are mutually independent and disjoint. Thus we could decompose the realization space R into independent subspace, R = u V Ou, where Ou is the set of all possible states for node u. For any full realization φ (resp. partial realization ψ), we would use φS (resp. ψS) to denote the feedback for the node set S V . Note that φS and ψS are partial realizations with domain S. Similarly, we would also use PS to denote the probability space u SPu, where Pu is the probability distribution over Ou (i.e. each out-going edge (u, v) of u is live with independent probability puv). With a slight abuse of notation, we further use φS (resp. ψS) to denote the set of live edges leaving from S under φ (resp. ψ). Then we could use notation φ1 S φ2 S to represent the union of live-edges from φ1 and φ2 leaving from S, and similarly ψ φ2 S with dom(ψ) = S.

Construction of the hybrid policy π. For any adaptive policy π, we deﬁne a ﬁctitious hybrid policy π that works on three independent random realizations Φ1, Φ2 and Φ3 simultaneously, thinking about them as from three copies of the graphs G1, G2 and G3. Note that π is not a real adaptive policy it is only used for our analytical purpose to build connections between the adaptive policy π and the non-adaptive policy W(π). In terms of adaptive seed selection, π acts exactly the same as π on G1, responding to partial realizations ψ1 obtained so far from the full realization Φ1 of G1, and disregarding the realizations Φ2 and Φ3. However, the difference is when we deﬁne adaptive inﬂuence spread for π, we aggregate the three partial realizations on the seed set together. More precisely, for any t = 1, 2, 3, we deﬁne the t-th aggregate inﬂuence utility function as f t : 2V Rt R+

f t S, φ1, , φt := f S, ( i [t]φi S, φ1 V \S) , (2)

where ( i [t]φi S, φ1 V \S) means a new realization φ where on set S its set of out-going live-edges is the same as the union of φ1, φt, and on set V \ S its set of out-going live-edges is the same as φ1, and f is the original inﬂuence utility function deﬁned in Section 2. The objective of the hybrid policy π is then deﬁned as the adaptive inﬂuence spread under policy π, i.e.,

σ( π) := E Φ1,Φ2,Φ3 P

f 3(V (π, Φ1), Φ1, Φ2, Φ3)

= E Φ1,Φ2,Φ3 P

h f V (π, Φ1), (Φ1 V (π,Φ1) Φ2 V (π,Φ1) Φ3 V (π,Φ1), Φ1 V \V (π,Φ1)) i . (3)

In other words, the adaptive inﬂuence spread of the hybrid policy π is the inﬂuence spread of seed nodes V (π, Φ1) selected in graph G1 by policy π, where the live-edge graph on the seed set part V (π, Φ1) is the union of live-edge graphs of G1, G2 and G3, and the live-edge graph on the non-seed set part is only that of G1. It can also be viewed as each seed node has three independent chances to activate its out-neighbors. Since the hybrid policy π acts the same as policy π on inﬂuence graph G1, we can easily conclude: Claim 1. σ( π) σ(π).

We also deﬁne t-th aggregate inﬂuence spread for a seed set S, σt(S), as σt(S) = EΦ1, ,Φt P f t(S, Φ1, , Φt) . Then, for the random-walk non-adaptive policy W(π), we deﬁne σt(W(π)) = P

ℓ L(π) pℓ σt(dom(ψℓ)), that is, the t-th aggregate inﬂuence spread of W(π) is the average t-th aggregate inﬂuence spread of seed nodes selected by W(π) according to distribution of the leaves in the decision tree T (π). Similarly, we deﬁne the t-th aggregate adaptive inﬂuence

spread for an adaptive policy π as σt(π) = EΦ1, ,Φt P f t(V (π, Φ1), Φ1, , Φt) . Note that σ( π) = σ3(π).

Now, we could give a deﬁnition for the conditional expected marginal gain for the aggregate inﬂuence utility function f t over live-edge graph distributions. Deﬁnition 6. The expected non-adaptive marginal gain of u given set S under f t is deﬁned as:

f t(u | S) = E Φ1, ,Φt P

f t S {u}, Φ1, , Φt f t S, Φ1, , Φt . (4)

The expected adaptive marginal gain of u given partial realization ψ1 under f t is deﬁned as:

f t(u | ψ1) = E Φ1, ,Φt P

f t dom(ψ1) {u}, Φ1, , Φt f t dom(ψ1), Φ1, , Φt | Φ1 ψ1 .

The following lemma connects σt(π) (and thus σ( π)) with adaptive marginal gain f t(u | ψ), and connects σt(W(π)) with non-adaptive marginal gain f t(u | S). Let Pπ i denote the probability distribution over nodes at depth i of the decision T (π). The proof is by applying telescoping series to convert inﬂuence spread into the sum of marginal gains. Lemma 1. For any adaptive policy π, and t 1, we have

i=0 E s Pπ i [ f t (π(ψs) | ψs)] , and σt(W(π)) =

i=0 E s Pπ i [ f t (π(ψs) | dom(ψs))] .

The next lemma bounds two intermediate adaptive marginal gains to be used for Lemma 3. The proof crucially depend on (a) the independence of realizations Φ1, Φ2, Φ3, (b) the independence of feedback of different selected seed nodes, and (c) the submodularity of the inﬂuence utility function on live-edge graphs. Lemma 2. Let S = dom(ψ1) and S+ = S {u} for any partial realization ψ1 and any u dom(ψ1). Then we have

E Φ1,Φ2,Φ3 P

h f S+, (Φ1 S Φ2 S Φ3 S, Φ1 u Φ2 u, Φ1 V \S+)

f S, (Φ1 S Φ2 S Φ3 S, Φ1 V \S) | Φ1 ψ1i f 2(u | S). (6)

E Φ1,Φ2,Φ3 P

h f S+, (Φ1 S Φ2 S Φ3 S, Φ1 u Φ2 u Φ3 u, Φ1 V \S+)

f S+, (Φ1 S Φ2 S Φ3 S, Φ1 u Φ2 u, Φ1 V \S+) | Φ1 ψ1i f 2(u | S). (7)

Combining the two inequalities above, we obtain the following key lemma, which bounds the adaptive marginal gain f 3(u | ψ1) with the non-adaptive marginal gain f 2(u | dom(ψ1)).

Lemma 3. For any partial realization ψ1 and node u / dom(ψ1), we have

f 3(u | ψ1) 2 f 2(u | dom(ψ1)). (8)

The next lemma gives an upper bound on the t-th aggregate (non-adaptive) inﬂuence spread σt(S) using the original inﬂuence spread σ(S). The idea of the proof is that each seed node in S has t independent chances to active its out-neighbors, but afterwards the diffusion is among nodes not in S as in the original diffusion. Lemma 4. For any t 1 and any subset S V , σt(S) t σ(S).

Proof of Theorem 1. It is enough to show that for every adaptive policy π, σ(π) 4σ(W(π)). This is done by the following derivation sequence: σ(π) σ( π) = σ3(π) = Pk 1 i=0 Es Pπ i f 3 (π(ψs) | ψs) Pk 1 i=0 Es Pπ i 2 f 2 (π(ψs) | dom(ψs)) = 2σ2(W(π)) 4σ(W(π)), where the ﬁrst inequality is by Claim 1, the second and the third equalities are by Lemma 1, the second inequality is by Lemma 3 and the last inequality is by Lemma 4.

3.2 Lower bound

Next, we proceed to give a lower bound on the adaptivity gap for the inﬂuence maximization problem in the myopic feedback model. Our result is stated as follow:

Theorem 2. Under the IC model with myopic feedback, the adaptivity gap for the inﬂuence maximization problem is at least e/(e 1).

Proof Sketch. We construct a bipartite graph G = (L, R, E, p) with |L| = m3

m2 and |R| = m3. For each subset X R with |X| = m2, there is exactly one node u L that connects to all nodes in X. We show that for any ϵ > 0, there is a large enough m such that in the above graph with parameter m the adaptivity gap is at least e/(e 1) ϵ.

4 Adaptive and Non-Adaptive Greedy Algorithms

In this section, we consider two prevalent algorithms the greedy algorithm and the adaptive greedy algorithm for the inﬂuence maximization problem. To the best of our knowledge, we provide the ﬁrst approximation ratio of these algorithms with respect to the adaptive optimal solution in the IC model with myopic feedback. We formally describe the algorithms in Figure 1.

Greedy Algorithm: S = while |S| < k do

u = argmaxu V \S f(u|S) S = S {u} end while return S

Adaptive Greedy Algorithm: S = , Ψ = while |S| < k do

u = argmaxu V \S f(u|Ψ) Select u as seed and observe Φ(u). S = S {u}, Ψ = Ψ {(u, Φ(u))} end while

Figure 1: Description for greedy and adaptive greedy.

Our main result is summarized below.

Theorem 3. Both greedy and adaptive greedy are 1

e) approximate to the optimal adaptive policy under the IC model with myopic feedback.

Proof Sketch. The proof for the non-adaptive greedy algorithm is straightforward since the nonadaptive greedy algorithm provides a (1 1

e) approximation to the non-adaptive optimal solution, which by Theorem 1 is at least 1

4 of the adaptive optimal solution. For the adaptive greedy algorithm, we need to separately prove that it also provides a (1 1

e) approximation to the non-adaptive optimal solution, and then the result is immediate similar to the non-adaptive greedy algorithm.

Theorem 3 shows that greedy and adaptive greedy can achieve at least an approximation ratio of 1 4(1 1

e) with respect to the adaptive optimal solution. We further show that their approximation ratio is at most e2+1 (e+1)2 0.606, which is strictly less than 1 1/e 0.632. To do so, we ﬁrst

present an example for non-adaptive greedy with approximation ratio at most e2+1 (e+1)2 . Next, we show that myopic feedback does not help much to adaptive greedy, in that the approximation ratio for the non-adaptive greedy algorithm is no worse than that of adaptive greedy over a family of graphs.

Theorem 4. The approximation ratio for greedy and adaptive greedy is no better than e2+1 (e+1)2 0.606, which is strictly less than 1 1/e 0.632. Moreover, the approximation ratio of non-adaptive greedy given any inﬂuence graph G and budget k is the same as the inﬁmum of the approximation ratios of adaptive greedy on a family of graphs with the same budget k.

5 Conclusion and Future Work

In this paper, we systematically study the adaptive inﬂuence maximization problem with myopic feedback under the independent cascade model, and provide constant upper and lower bounds on the adaptivity gap and the approximation ratios of the non-adaptive greedy and adaptive greedy algorithms. There are a number of future directions to continue this line of research. First, there is still a gap between the upper and lower bound results in this paper, and thus how to close this gap is the next challenge. Second, our result suggests that adaptive greedy may not bring much beneﬁt under the myopic feedback model, so are there other adaptive algorithms that could do much better? Third, for the IC model with full-adoption feedback, because the feedback on different seed nodes may be correlated, existing adaptivity gap results in [1, 4] cannot be applied even though it is adaptive submodular. For this, our recent study in [5] provides partial answers on several special classes of graphs such as trees and bipartite graphs, but the adaptivity gap on general graphs is still open. One may also explore beyond the IC model, and study adaptive solutions for other models such as the linear threshold model and the general threshold model [11].

Acknowledgment

Wei Chen is partially supported by the National Natural Science Foundation of China (Grant No. 61433014).

[1] Arash Asadpour and Hamid Nazerzadeh. Maximizing stochastic monotone submodular functions. Management Science, 62(8):2374 2391, 2016.

[2] Arash Asadpour, Hamid Nazerzadeh, and Amin Saberi. Stochastic submodular maximization. In International Workshop on Internet and Network Economics, pages 477 489. Springer, 2008.

[3] Ashwinkumar Badanidiyuru, Christos Papadimitriou, Aviad Rubinstein, Lior Seeman, and Yaron Singer. Locally adaptive optimization: Adaptive seeding for monotone submodular functions. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 414 429. SIAM, 2016.

[4] Domagoj Bradac, Sahil Singla, and Goran Zuzic. (Near) optimal adaptivity gaps for stochastic multi-value probing. In Proceedings of the 23rd International Conference Randomization and Computation (RANDOM), 2019.

[5] Wei Chen and Binghui Peng. On adaptivity gaps of inﬂuence maximization under the independent cascade model with full adoption feedback. In Proceedings of the 30th International Symposium on Algorithms and Computation (ISAAC), 2018.

[6] Wei Chen, Laks VS Lakshmanan, and Carlos Castillo. Information and Inﬂuence Propagation in Social Networks. Morgan & Claypool Publishers, 2013.

[7] Daniel Golovin and Andreas Krause. Adaptive submodularity:theory and applications in active learning and stochastic optimization. Journal of Artiﬁcial Intelligence Research, 42:427 486, 2011. ar Xiv version (arxiv.org/abs/1003.3967) includes discussions on the myopic feedback model.

[8] Anupam Gupta, Viswanath Nagarajan, and Sahil Singla. Algorithms and adaptivity gaps for stochastic probing. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 1731 1747. SIAM, 2016.

[9] Anupam Gupta, Viswanath Nagarajan, and Sahil Singla. Adaptivity gaps for stochastic probing: Submodular and XOS functions. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1688 1702. SIAM, 2017.

[10] Kai Han, Keke Huang, Xiaokui Xiao, Jing Tang, Aixin Sun, and Xueyan Tang. Efﬁcient algorithms for adaptive inﬂuence maximization. PVLDB, 11(9):1029 1040, 2018.

[11] David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of inﬂuence through a social network. In Proceedings of the ninth ACM SIGKDD, pages 137 146. ACM, 2003.

[12] Yuchen Li, Ju Fan, Yanhao Wang, and Kian-Lee Tan. Inﬂuence maximization on social graphs: A survey. IEEE Trans. Knowl. Data Eng., 30(10):1852 1872, 2018.

[13] Guillaume Salha, Nikolaos Tziortziotis, and Michalis Vazirgiannis. Adaptive submodular inﬂuence maximization with myopic feedback. In 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pages 455 462. IEEE, 2018.

[14] Lior Seeman and Yaron Singer. Adaptive seeding in social networks. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 459 468. IEEE, 2013.

[15] Yaron Singer. Inﬂuence maximization through adaptive seeding. ACM SIGecom Exchanges, 15 (1):32 59, 2016.

[16] Lichao Sun, Weiran Huang, Philip S Yu, and Wei Chen. Multi-round inﬂuence maximization. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2249 2258. ACM, 2018.

[17] Jing Tang, Keke Huang, Xiaokui Xiao, Laks V. S. Lakshmanan, Xueyan Tang, Aixin Sun, and Andrew Lim. Efﬁcient approximation algorithms for adaptive seed minimization. In Proceedings of the 2019 International Conference on Management of Data, SIGMOD Conference 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019., pages 1096 1113, 2019.

[18] Guangmo Tong. Adaptive inﬂuence maximization under general feedback models. ar Xiv preprint ar Xiv:1902.00192, 2019.

[19] Guangmo Tong, Weili Wu, Shaojie Tang, and Ding-Zhu Du. Adaptive inﬂuence maximization in dynamic social networks. IEEE/ACM Transactions on Networking (TON), 25(1):112 125, 2017.

[20] Jing Yuan and Shao-Jie Tang. No time to observe: Adaptive inﬂuence maximization with partial feedback. In Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI), 2017.