Influence Maximization Based on Dynamic Personal Perception in Knowledge Graph

Viral marketing on social networks, also known as Influence Maximization (IM), aims to select k users for the promotion of a target item by maximizing the total spread of their influence. However, most previous works on IM do not explore the dynamic user perception of promoted items in the process. In this paper, by exploiting the knowledge graph (KG) to capture dynamic user perception, we formulate the problem of Influence Maximization with Dynamic Personal Perception (IMDPP) that considers user preferences and social influence reflecting the impact of relevant item adoptions. We prove the hardness of IMDPP and design an approximation algorithm, named Dynamic perception for seeding in target markets (Dysim), by exploring the concepts of dynamic reachability, target markets, and substantial influence to select and promote a sequence of relevant items. We evaluate the performance of Dysim in comparison with the state-of-the-art approaches using real social networks with real KGs. The experimental results show that Dysim effectively achieves up to 6.7 times of influence spread in large datasets over the state-of-the-art approaches.


I. INTRODUCTION
Social influence [1], [2], [3] refers to the impact of a social environment on people's behavior. By exploiting the social influence of users, a wide spectrum of applications (e.g., item promotion and viral marketing) have been formulated as various research problems, such as influence maximization (IM) [1], revenue maximization (RM) [2], and profit maximization (PM) [3]. Among them, IM selects k users as the seeds to promote one target item to maximize the number of influenced users. Nevertheless, in real life, companies often promote relevant items in multiple events, e.g., Apple Inc. usually promotes iPhones, AirPods, and iPads in September, followed by a series of subsequent promotions. 1 In this work, we address a new IM problem formulated for a sequence of promotions on relevant items. 2 For multiple promotions, exploring the dynamic changes in personal perceptions on promoted items is important, since users' perceptions of item relationships may vary according to the changes in users' demand indicated by research in the marketing field [4]. First, the complementary and substitutable relationships between items affect users' preferences on items [4], [5], [6]. In economics, cross elasticity of demand [7] indicates that adopting complementary items of an item increases the preference for it, while adopting its substitutable items has the opposite effect. For example, users who own iPhones with no headphone jack may be interested in AirPods (due to its complementary relationship with iPhones), 3 while users who have iPhones may have less interest in iPads (due to their substitutable relationship). Second, the association between items may trigger extra adoptions without promotions [8], [9]. For example, AirPods may be directly adopted together with iPhones due to their complementary relationship.
Third, the perceptions of these relationships between items are usually personal and dynamic [4], [10], [11], as the items got newly adopted usually bring fresh experiences to users. For example, users who care more about large screens than mobility may treat iPhones as substitutable items of iPads; when these iPad users start to care about the mobility, they may tend to regard iPhones as complementary items of iPads. In turn, the changes in personal perceptions of item relationships lead to changes in users' preferences. Fourth, the dynamic personal perceptions of item relationships also affect users' social influence strength over friends, since friends adopting similar items and sharing similar perceptions tend to become closer [12], [13], [14], [15]. To address IM in a sequence of promotions on relevant items, it is essential to carefully examine dynamic personal perceptions of item relationships, together with their ripple effect on personal preferences for items, social influence strength, and item associations.
Knowledge graph (KG) (along with weighted meta-graphs) to capture the relationships (e.g., the complementary and substitutable relationships) has been well-explored in recommendation systems [16], [10], [11], [17], [18]. As illustrated in Fig. 1, KG represents facts (e.g., ITEM iPhone and ITEM AirPods SUPPORT the FEATURE Bluetooth in Fig. 1(a)), while meta-graphs capture relationships in the KG (e.g., m 1 in  . Note that these meta-graphs can be used to reflect the perception of item relationships, in forms of personal item network, for each individual. The personal weighting on each meta-graph describes the significance of this meta-graph to an individual (e.g., the values next to m 1 , . . . , m 3 in Fig. 1(c)), while the relevance scores between items describe the strength of their relationships in the mind of this individual [10], [11] (e.g., the values on dotted edges in Fig. 1(c)). By adjusting the weightings on meta-graphs according to previous adoptions [10], [11], dynamic personal perceptions of item relationships in individual users can be updated (in Fig. 1(d)). In this paper, we aim to leverage dynamic personal item networks for a sequence of IM promotions.
Following up the example in Fig. 1, Fig. 2 illustrates the IM process considering dynamic personal perceptions of item relationships, personal preferences for items, social influence strength, and item associations. As shown, the number of hearts indicates Bob's preference for a not-yet-adopted item, and a solid arrow represents the social influence between users (thickness implies strength). After Bob is promoted iPhone by Alice, Bob's purchase decision depends not only on the influence strength from Alice but also on his own preference for iPhone (in Fig. 2(a)). Meanwhile, item associations usually trigger extra adoptions of relevant items, such as AirPods, according to Bob's item network (in Fig. 1(c)). After Bob purchases iPhone and AirPods, his perception of the complementary relationship changes (i.e., he becomes to regard items supporting common features or belonging to the same brand as complementary), which increases the relevance between iPhone, AirPods, and the wireless charger (in Fig. 1(d)). After that, as Bob has adopted iPhone and AirPods, and their relevance to the wireless charger increases, Bob's preference for the wireless charger grows accordingly. 4 Moreover, if Cindy acts as a seed to promote the wireless charger, as Bob and Cindy have similar adopted items (in Fig. 2(b)) (indicating Bob shares a similar perception of item relationships with Cindy and tends to behave similarly with Cindy), the influence strength from Cindy to Bob thus becomes stronger. It is easier for Cindy to promote the wireless charger to Bob now, since both Cindy's influence strength to Bob and Bob's preference for the wireless charger increase.
To incorporate factors depicted in the example above, several new challenges arise. (i) Propagation of item impact (i.e., impact due to item adoption): Item adoptions change users' personal perceptions of item relationships, their preferences for other items, their strength of social influence among friends, and the item associations. In other words, the promotion of an item may affect the adoptions of subsequent items and thereby the planning for the next promotions. The order of items being promoted matters. (ii) Antagonism of the substitutable relationship: Promoting an item after adopting a substitutable item is not beneficial when the first item has met the users' needs. It is thus vital to avoid promoting substitutable items to the same users in consecutive promotions. (iii) Determination of promotional timing: As the promotions are dependent on previous ones, a seed in early promotions should facilitate subsequent promotions, while a seed in later promotions should focus on potential adoptions benefited from previous promotions. Therefore, determining the proper promotional timing for each seed is essential.
In this work, we formulate a new problem, named Influence Maximization based on Dynamic Personal Perception (referred to as IMDPP). In contrast to most previous works [19], [20], [21] focusing on one item, given the social network, KG, and meta-graphs for different item relationships, IMDPP targets on multiple promotions to maximize the overall spread of influence by choosing items and selecting seed users for promotion at proper timings under a total budget, where users have different costs as seeds [3], and each promotion allows multiple items to be promoted. We exploit personal item networks to capture dynamic personal perceptions of complementary and substitutable relationships between items. The adoptions of items dynamically adjust users' weightings on meta-graphs, reflecting dynamic personal perceptions and updating personal item networks. Also, users' preferences for other items, their social influence strength over friends, and the item associations change accordingly, in turn affecting other users' adoptions, their personal weightings on meta-graphs, their preferences for other items, their social influence strength, and the item associations in a ripple effect.
We prove that IMDPP is NP-hard and inapproximable within O( 1 |V | 1− ), where |V | is the number of users and is an arbitrarily small constant. We design an approximation algorithm, named Dynamic perception for seeding in target markets (Dysim), to tackle the above challenges of IMDPP. For the first challenge in the propagation of item impacts, Dysim introduces dynamic reachability to evaluate the impacts from previously promoted items on the currently chosen item, as well as the potential impact from the current item on any candidate item in subsequent promotions. For the second challenge in the antagonism of the substitutable relationship, Dysim identifies target markets to promote complementary items to socially close users in consecutive promotions. For the third challenge in determining the promotional timing, Dysim introduces substantial influence to evaluate both immediate and subsequent adoptions under the impact of a candidate seed (assigned at some promotional timing). We evaluate the performance of Dysim on real social networks with KGs, i.e., Amazon, Yelp, Douban, and Gowalla. The contributions of this work include: • To the best of our knowledge, IMDPP is the first attempt to study the IM problem under a sequence of promotions on relevant items, where the personal perceptions of item relationships are dynamically captured from users' previously adopted items by KG and meta-graphs, and the changes in preferences for items, social influence strength, and item associations are considered as a ripple effect in the diffusion process. • We prove that IMDPP is inapproximable within O( 1 |V | 1− ) even for a simple case with only the complementary relationship and only one promotion. • We design an approximation algorithm Dysim, which plans a distinct effective promotional strategy for each target market to avoid antagonism between substitutable items. Dysim carefully examines the dynamic reachability of items to prioritize the promotion of relevant items, and evaluates the substantial influence of candidate seeds to properly determine the promotional timing. • Via real social networks and real KGs, experimental results demonstrate that Dysim effectively achieve up to 6.7 times of the influence spread over the state-of-the-arts.

II. RELATED WORK
Influence maximization (IM) aims at maximizing the number of influenced users by selecting seed users. It was first formulated as a discrete optimization problem and proved as NP-hard by Kempe et al. [1]. In the work [1], they prove the influence maximization is NP-hard under the triggering models, i.e., the Linear Threshold (LT) and Independent Cascade (IC) diffusion models. The LT model considers a user's threshold and the weighted fraction of her all influenced friends as the criterion to be influenced while the IC model treats every influence independently with a probability. An influenced user can then propagate influence to her friends, and the influence thus diffuses until no user is newly influenced. Since then, various issues in IM have been actively studied. To address the inefficiency in computing influence spread, some exploit the submodular property and certain heuristics [22], [23]. Recent works further introduce the reverse influence sampling to approximate the influence with guarantees [24], [25]. In addition, extensive research efforts study the maximization of influence on target users [3], [26], at specified locations [27], [28], for specific contents [29], [30], or at specific time [31], [32]. IM for target users [3], [26] focuses on a subset of users and even allows users to contribute different benefits to the company. The location-based IM [27], [28] takes locations of users and the promoted event into account. As the geographical distance is an important constraint for users, the probability to influence a user is affected by her distance to the promoted event's location. Different from [28] focusing on the IC model, a variant of the IC model is employed in [27], which considers the login event so that the influence can be propagated to a friend only after she is online with a login probability. In [33], [34], the reachabilitybased diffusion process is regarded as generating a branching tree from the seed to be the egocentric influence rings of the root node (i.e., the seed). The influence is assumed to decay along the path, and it is less likely to reach the nodes that are farther away from the root. Recently, Huang et al. [19] point out that users' adopting probabilities of the promoted item should depend on users' previously adopted complementary and substitutable items (which is modeled as dynamic preferences for items in IMDPP). However, [19] targets only on a specified item in only one promotion with fixed item relationships, whereas IMDPP explores multiple promotions on relevant items and carefully examines the dynamic user perceptions of item relationships. Although various issues, e.g., target audience, scalability, and complementary/substitutable items, are studied, previous works [1], [3], [19], [23], [24] promote only one target item in only a single promotion, instead of multiple target items in multiple promotions, and the phenomenon of dynamic personal perceptions of item relationships together with its ripple effect are not considered. By contrast, IMDPP aims at a sequence of promotions on relevant items modeled by Knowledge Graph, where the item relationships and promotional timings are able to alter users adoption decisions.
Some studies investigate IM on promoting multiple target items, e.g., making exclusive adoption among items [35], avoiding spamming seeds by overwhelming promotions [36], learning diffusion probabilities of different items [37], and maximizing utility-based adoption among desired items [38]. However, they focus on a single promotion and do not consider multiple promotions to promote a sequence of relevant items modeled by KG and meta-graphs. Moreover, they study the problems under simpler scenarios without capturing the dynamic changes in personal perceptions of item relationships, personal preferences for items, social influence strength, and item associations. By contrast, in IMDPP, the adoption of items dynamically changes the personal perceptions of complementary and substitutable relationships between items. The changed perceptions of item relationships affect users' preferences for items and users' social influence strength over time, in turn affecting other users' adoptions, their preferences for other items, and their social influence strength as a ripple effect. Therefore, the above works have limitations to IMDPP, since the promotional timing is critical as users' perceptions of item relationships, preferences for items, and influence strength on friends are dynamic.
Research on adaptive IM [39], [40], [41] aims to select the seeds adaptively based on the adoptions in the previous influence diffusion. However, although multiple promotional timings are considered, they consider only one item in the IM problem and ignore multiple target items, item relationships, and dynamic preference for items. Moreover, adaptive IM requires a predefined budget allocation to different promotions, and it does not have the adaptive monotonicity and the adaptive submodularity (or even the adaptive bounded weak-submodularity). 5 By contrast, IMDPP does not require a predefined budget allocation to promotions and can be solved by Dysim with an approximation guarantee (detailed in Sec. IV-C).
Knowledge graph (KG) is employed to describe facts in a wide spectrum of applications, e.g., relevance measures and search [11], [17], and recommendation [10], [18]. Shi et al. [10] present a new similarity measure through personal weighted meta-paths to include different semantics of similarity. Users' own preferences can thus be derived from these meta-paths. Gu et al. [11] point out that a user may have different perceptions of similarity due to the change in her interests. They propose to automatically pick up meta-paths to best characterize the similarity by user-provided examples. Huang et al. [17] further extend meta-paths to meta-graphs to measure similarity with more complex connections. Note that these works focus on predicting the ratings of unknown items for users, which is essentially different from the IM problem. Inspired by the above research, we first attempt to incorporate the above relevance measurements and adopt the above meta-graphs with dynamic personal weightings in influence diffusion of multiple relevant items.

III. PROBLEM FORMULATION
To study various issues in multiple promotions of relevant items, we first introduce four important factors, which can be easily incorporated into existing diffusion models 6 by extending the diffusion process, to consider dynamic changes in personal perceptions of item relationships [4], [10], [11] and the ripple effect on personal preference for items [4], [5], [6], [7], social influence strength [12], [13], [42], and item associations [8], [9]. (1) Relevance measurement [10], [11], 5 The adaptive monotonicity is a property that conditional expected marginal adoptions of any item are non-negative. The adaptive submodularity (or the adaptive bounded weak-submodularity) is the property that conditional expected marginal adoptions of any fixed item do not increase (or boundedly increase) as more items are selected and their states are observed. 6 For example, triggering models [1], [39] and reachability-based influencediffusion models [34].  [17], [18]: KG is leveraged to measure the relevance between two items and find personal item networks, by learning the personal weightings on meta-graphs from users' previously adopted items. 7 (2) Preference estimation [16], [38], [47]: Users' preferences for not-yet-adopted items are derived and updated based on previously adopted items and personal item networks. (3) Influence learning [48], [49], [50]: The strength of social influence between two users is inferred and updated according to their similarity in adopted items and personal item networks, since friends with similar backgrounds and intentions usually become closer and more easily influence each other [14], [15]. (4) Item associations [16], [37], [18], [47]: When users are promoted and preferring the promoted item, extra adoptions of relevant items are usually triggered due to item associations based on users' personal item networks and the probability of being promoted and preferring the promoted item. The dependency of these factors is illustrated in Fig. 3, while the discussion of deriving and updating them is detailed in Sec. V-A. For ease of discussion, we summarize the notations in Table I.
Accordingly, we elaborate on the diffusion process as follows. A campaign includes T promotions. The t-th promotion contains multiple steps ζ t = 0, 1, . . ., where each step represents an influence propagation from users adopting items to their friends that haven't adopted those items yet. 8 As a promotion depends on previous promotions, the initial state of a user in the t-th promotion (i.e., adopted item, perceptions, preference, and influence strength at ζ t = 0) is the same as the state at the end of the (t − 1)-th promotion, while the seeded users in the t-th promotion newly adopt the promoted items at ζ t = 0. When the diffusion starts at step ζ t ≥ 1, a user u may be promoted x by any friend u who newly adopted x at ζ t − 1 only if u has not adopted x yet. The probability that u will adopt x is derived according to the social influence strength from u (denoted as p u ,u ) and u's preference for x (denoted as P pref (u, x, ζ t − 1)), i.e., p u ,u × P pref (u, x, ζ t − 1) [51]. In addition, being promoted x, u may further adopt x's relevant item y (not previously adopted by u) due to (4) item associations, according to the probability of u being promoted and preferring x and the relationships between x and y. 9 Then, at the end of this step, u's personal perceptions of item relationships (i.e., personal item network) are updated by (1) relevance measurement (detailed in Sec. V-A) if u newly adopts any item, while her preferences for not-yet-adopted items and the influence strength also change accordingly by (2) preference estimation and (3) influence learning (detailed in Sec. V-A), respectively. If there is any new adoption at ζ t , the next step ζ t + 1 starts with users having new adoptions at ζ t to promote their newly adopted items to their friends (who have not yet adopted those items). In other words, the diffusion of t-th promotion stops when no new adoptions happen since users cannot be promoted the adopted items again. Thus, the diffusion of the (t + 1)-th promotion follows.
Based on the above diffusion process for relevant items in multiple promotions, we aim to choose a number of items, seed suitable users, and decide the proper timing, such that the influence spread (defined below) is maximized. Formally, S = {(u, x, t)} is a seed group, where a seed (u, x, t) indicates that an item x is chosen for promotion starting at a seeded user u in the decided t-th promotion. 10 Let S t ⊆ S denote a subgroup of seeds chosen for the t-th promotion. We first define the influence spread and then formulate the problem as follows.
Definition 1 (Importance-aware influence function). Let w x be the importance of an item x and T denote the number of promotions. 11 For a seed group S, the influence spread in the social network G SN = (V, E), denoted as σ GSN (S), is the expected adoptions (weighted by item importance) in all T promotions, i.e., σ GSN where n x (S t | S 1 , S 2 , . . . , S t−1 ) is the expected new adoptions of x for S t in the t-th promotion conditioned on S 1 , . . . , S t−1 in previous promotions. 12 (When G SN is clear from context, we write σ(S) for short.) Definition 2 (Influence Maximization based on Dynamic Personal Perception (IMDPP)). Let m C and m S denote the meta-graphs for describing the complementary and substitutable relationships between items, respectively. Based on the diffusion process described earlier, given a social network , two sets of metagraphs {m C } and {m S }, a target item set I = {x} together with its importance set W = {w x }, the cost c u,x of hiring a user u ∈ V to promote an item x ∈ I, the budget b, and 9 Note that the extra adoptions of x's relevant items can be independent of the adoption of x since item associations are inspired by the promotion of x rather than the purchase decision of x. 10 An item x can be assigned to multiple seeded users at multiple promotions; each promotion can promote multiple chosen items by multiple seeded users. 11 Importance reflects how much items are valued in this campaign, e.g., higher-quality items in product lines usually have a greater importance [52]. 12 Following [1], [23], σ is estimated by the Monte Carlo method, which simulates the influence diffusion of seeds according to the probabilities.

Notation
Description Sec. III ζt Step ζ of the t-th promotion Ppref(u, y, ζt) u's preference for y updated at ζt Pact (u, v, ζt) u's influence strength on v updated at ζt Pext(u, u , x, y, ζt) u's extra adoption probability of y (when being promoted x by u ) at ζt (u, x, t); (u, x) Seed; nominee S = {(u, x, t)}; St Seed group; subgroup of seeds in the t-th promotion wx; W Importance of x; set of item importance σ G SN (S); T Importance-aware influence; number of promotions {m C } / {m S } Sets of meta-graphs for describing complementary/substitutable relationships Sec. IV τ ; G Target market; set of target markets with common users r C x,y /r S

x,y
Average complementary/substitutable relevance between x and y per user (the timing is specified from context) DR W,τ (S G , x) x's dynamic reachability of τ 's users given S G and W SI τ (S G , (u, x, t), T ) Substantial influence of (u, x, t) in τ given S G and T t Latest promotional timing in S G Sec. V Wmeta(u, m, ζt) u's weighting of meta-graph m at ζt s(x, y | m) Relevance between x and y defined by meta-graph m r C (u, x, y, ζt) / r S (u, x, y, ζt) The complementary/substitutable relevance between x and y in u's perception updated at ζt GPIN(u, ζt) u's personal item network updated at ζt A(u, ζt) u's adoption set of items updated at ζt P I W,τ (S G , x, d); RI wx,τ (S G , x, d); d τ x's proactive impact of τ 's users propagated within d hops given S G and W; x's reactive impact of τ 's users propagated within d hops given S G ; diameter of τ L C,τ (x, y, S G ) / L S,τ (x, y, S G ) Likelihood of regarding x and y as complementary/substitutable for each user in τ given S G M A τ (S G , (u, x, t)); M L τ (S G , (u, x, t)) Marginal adoption of (u, x, t) in τ given S G ; marginal likelihood of (u, x, t) in τ given S G π τ (S G ) Likelihood of not-yet-adopted items being adopted in τ in future promotions given S G the total number of promotions T , the IMDPP problem is to find the seed group S = T t=1 S t such that the influence spread σ(S) is maximized within the budget constraint b, i.e.,  Proof. We prove the theorem with the gap-introducing reduction from the decision problem of Set Cover. Given a set cover instance, by constructing a corresponding special case of IMDPP, we can prove that if there is a set cover solution with at most k sets, there is a feasible solution of IMDPP with the total influence at least |U | c +2|U |+2, where |U | is the size of the ground set of set cover instance, and c is a large constant. Otherwise, if there does not exist a set cover solution with at most k sets, the optimal value of IMDPP is at most 2|U |+k+2. Then, we assign c suitably to satisfy |V | 1− ≤ |U | c +2|U |+2 2|U |+k+2 , where |V | and are related to |U | and c. Consequently, if there is a |V | 1− approximation algorithm of IMDPP, we can solve the decision problem of set cover in polynomial time, which implies P = N P , which is a contradiction.
Specifically, given a ground set U consisting of elements and a sub-collection S on 2 U consisting of sets, an element is covered by a set if the set contains the element. The decision problem of Set Cover asks whether there are at most k sets to cover all the elements. Given a Set Cover instance (U, S), we construct an instance of IMDPP as follows. First, we construct the topology structure of the special case. Let each element and each set correspond to a user node in the social network. We number each element node by 1, 2, . . . , |U |. Denote the sets of element nodes and set nodes by V e = {v e1 , v e2 , . . . , v e |U | } and V S = {v S1 , v S2 , . . . , v S |S| }, respectively. For each pair of set node v Sj and element node v ei , we construct a directed edge from v Sj to v ei if set S j covers element e i . We add a new node v b to connect each element node v ei ∈ V e by |U | new disjoint directed paths with length 2 from v b to each v ei (1 ≤ i ≤ |U |). We also add a new directed path P C with length |U | − 1 and number each node of the path from one end node to another by 1, 2, . . . , |U |. Denote the node set of path P C by V P C = {v p1 , v p2 , . . . , v p |U | }. Then, we copy P C by |U | c times, where c is a large constant. Moreover, we sort the |U | c copied paths by an arbitrary ordering and label them by 1, 2, . . . , |U | c . We add a new node v a to connect the same end node v p1 of all the |U | c paths. Afterwards, we connect each element node v ei (1 ≤ i ≤ |U | − 1) to the corresponding node v pi of all the |U | c paths, by |U | c new disjoint directed paths from v ei to v pi with corresponding length 2i − 1. In particular, when i = |U |, we connect the element node v e |U | to the corresponding end node v p |U | of the first path by a directed path from v e |U | to v p |U | with length 2 |U | − 1. Last, we connect each end node v p |U | of the |U | c paths by exact one directed path P T from the end node v p |U | of the first path to the corresponding end node of the last path. Note that P T has |U | c nodes since it consists of |U | c end nodes v p |U | of |U | c copies of path P C . The illustration of the constructed special case is shown in Figure 4.
Second, we set the parameter of each edge and node in both the social network and KG. Assume the influence strength of each edge in social network is equal to 1, i.e., P act ≡ 1, and the budget b = k. We construct |U | + 1 items numbered by 1, 2, . . . , |U | + 1. Denote the item set by I = {x 1 , x 2 , . . . , x |U |+1 }. For each user, except users corresponding to nodes v a , v b , and set nodes in V S , we set their costs for promoting any item as a large constant M 0 > k. Moreover, we set both v a 's and v b 's cost for promoting all the items as 0 and each set node v Sj 's (v Sj ∈ V S ) cost for promoting all the items as 1. In other words, nodes v a and v b can be chosen as seeds with all the items for free. We set w xi = 0 for i = 1, . . . , |U | and w x |U |+1 = 1. That is, only promoting item x |U |+1 directly or promoting users to adopt item x |U |+1 can bring influence. Assume that there is only the complementary relationship between items. For each element node v ei , we set P pref (v ei , x 1 ) = 1; 13 otherwise, P pref (v ei , x j ) = 0 where j = 1. That is, each element node v ei can only initially adopt item x 1 . Assume after v ei adopts item x 1 , its preference for item x i+1 increases from 0 to 1.
and the preferences for other items as 0.
For each mid-node v j of the corresponding directed path with length 2i − 1 from element node v ei (i = 1, 2, . . . , |U |) to the corresponding node v pi of P C , we set P pref (v j , x i+1 ) = 1 and the preferences for other items as 0.
Next, we show the relation between any feasible solution of Set Cover and that of the constructed special case of IMDPP. For any feasible solution of Set Cover, we construct a feasible solution of IMDPP by 1) letting the chosen set nodes promote items arbitrarily and 2) seeding users corresponding to nodes v a and v b to promote all the items without violating the budget constraint k. On the other hand, for any feasible solution of IMDPP, we construct a corresponding feasible solution of Set Cover by 1) discarding those seeding nodes that are not set nodes in the solution of IMDPP and 2) regarding the seeding set nodes in the solution of IMDPP as the corresponding chosen sets. Note that the constructed solution is still a feasible solution of Set Cover, i.e., the number of chosen set is not larger than k.
Finally, we derive the gap. If there is a Set Cover solution with at most k sets, in order to maximize the influence of adopting item x |U |+1 , we let each set node in V S choose item x 1 as seeds, and let nodes v a , v b choose all the items as seeds satisfying the budget constraint k. As a consequence, all the nodes in path P T adopt item x |U |+1 , implying that at least |U | c + 2 |U | + 2 users adopt item x |U |+1 with total influence at least |U | c + 2 |U | + 2. To see this, assume that the initial seeding step is 0 and each step is one-hop influence propagation. After initial seeding, at step 1, each set node v Si (i = 1, 2, . . . , |U |) adopts item x 1 , and their preferences for item x i+1 are increased from 0 to 1. At step 2, v b propagates influence to make v Si adopt item x i+1 at step 2. On the other hand, v p1 first adopts item x 1 and its preference for item x 2 is increased from 0 to 1 at step 1. Afterwards, v S1 continues to propagate influence to make v p1 adopt item x 2 at step 3 because P pref (v p1 , x 2 ) = 1 at step 2. Similarly, each v Si (i = 2, 3, . . . , |U |) continues to propagate influence to 13 For simplicity, in this paper, when ζ and t are clear or have little impact on the proof, we ignore them in the presentation of Pext, P pref and Pact.  make v pi of directed path P C adopt item x i+1 at step 2i + 1 after each v pi adopts item x i at step 2i. Moreover, all the end nodes v p |U | of P C (i.e. all the nodes of P T ) will adopt item x |U | at step 2 |U |. Notice that, at step 2 |U | + 1, the preferences for item x |U |+1 of all the end nodes v p |U | in P C (i.e. all the nodes of P T ) have been increased from 0 to 1. Consequently, the first end node of P T adopts item x |U |+1 at step 2 |U | + 1 after its in-neighbor adopts item x |U |+1 at step 2 |U |. Then, all the left nodes of P T adopt item x |U |+1 at step Otherwise, if there does not exist a Set Cover solution with at most k sets to maximize the influence of adopting item x |U |+1 , then at most 2 |U | + k + 2 users (consisting of v a , two paths P v b v |U | v e |U | and P v e |U | , . . . , v p |U | , and any k set nodes in v S ) adopt item x |U |+1 with total influence at most 2 |U | + k + 2. By setting c sufficiently large, we construct the special case of IMDPP with user node size |V | such that |U | c +2 |U |+ 2 ≥ |V | 1− 2 and 2 |U | + k + 2 ≤ |V | 2 , respectively, where is an arbitrarily small constant. Notice that the total nodes of the newly constructed graph can be partitioned into two parts: one is the nodes in the |U | c paths; the other is the left nodes. It can be seen that the number of the left nodes is polynomial on |U |. Thus, assume that the total left nodes is |U | c1 , where c 1 is a constant. Since each path has |U | nodes, the total number of nodes of |U | c paths is |U | c+1 . Then, |V | = |U | 1+c + |U | c1 = |U | · |U | c + |U | c1 . Thus, given an arbitrarily small constant , 2|U |+k+2 approximation algorithm, then we can solve the decision problem of Set Cover in polynomial time, which implies P = N P , leading to a contradiction.
In addition, when P pref ≡ 1 and P ext ≡ 0, assume there is only one item, which implies a single user can be regarded as a seed directly. A user's adoption decision of an item is thus equivalent to checking whether the user is influenced, which simply depends on the influence strength P act . Therefore, IMDPP is reduced to the conventional influence maximization problem that is to find k users as seeds to maximize the influence spread. Since the influence maximization problem cannot be approximated within 1 − 1 e + , the special case of IMDPP cannot, either.

A. Algorithm Overview
To efficiently solve IMDPP, we design an approximation algorithm, namely Dynamic perception for seeding in target markets (Dysim), which embodies a number of ideas. (i) To tackle the challenge in the propagation of item impacts, Dysim introduces Dynamic Reachability (DR) to measure the impact made by an item promotion and the impacts resulted from the promotions of other items based on users' dynamic perceptions of item relationships (detailed later in Eq. (1)). Specifically, DR evaluates both proactive and reactive impacts for each item. For an item, the proactive impact is the probability for this item to result in an increase of users' preferences on other items. The reactive impact is the probability to increase users' preferences on this item resulted from other items promoted previously. The item with the highest DR is prioritized for promotion. Previous works [35], [37], [38] select users only and do not consider the items in IM.
(ii) To avoid antagonism between substitutable items, Dysim identifies target markets, each of which consists of socially close users to promote complementary items in consecutive promotions. Specifically, it identifies some nominees (where a nominee is a user-item pair (u, x)) as candidate seeds, denoted by (u, x, t), for an incoming promotion at time t (decided later). Note that a target market targets on a cluster of nominees in order to promote complementary items to socially close users. Since different target markets may share some common users, it is important to avoid promoting substitutable items to them. Accordingly, Dysim prioritizes the target market promoting items with the least substitutable relevance to items in the overlapping target markets (i.e., the target markets sharing many common users). By contrast, prior works [35], [37], [38] consider only one relationship and thereby may promote substitutable items to the same users.
(iii) To find the promotional timing, Dysim introduces Substantial Influence (SI) for each candidate seed (u, x, t) to evaluate immediate and subsequent adoptions if nominee (u, x) is assigned as the seed in the t-th promotion. Specifically, SI derives the marginal adoption and marginal likelihood of (u, x, t), where the former is the difference of the total adoptions with and without (u, x, t), and the latter is the difference of the likelihood with and without (u, x, t) for not-yet-adopted items to be adopted after the t-th promotion. (u, x, t) with the highest SI is selected as a new seed at each iteration. In contrast, previous works [35], [37], [38] are designed for only one promotion and do not leverage item impacts at different timings.
Equipped with the above strategies, Dysim includes three phases: Target Market Identification (TMI) and Dynamic Reachability Evaluation (DRE). 14 Since users in social net- 14 Our proposed algorithm can deal with adaptive IM (even without a predefined budget allocation to different promotions), detailed in Sec. V-D.

Algorithm 1: DPSP
works usually have different needs and diverse purchase intentions, a promotional strategy is planned more sophisticatedly if the target users are identified first. Intuitively, intensively promoting a few items within a short period can better draw users' attention. Hence, Dysim first exploits TMI to identify target markets and then leverages DRE and TDSI to plan the distinct effective promotional strategy for each target market. Specifically, TMI selects and clusters nominees to promote complementary items to each target market and prioritizes target markets with fewer substitutable items to the nominees in the overlapping target markets. For each target market, DRE finds the item with the highest DR to exploit item impacts and suggests the corresponding nominees as candidate seeds. TDSI decides the promotion timing t for the candidate seed (u, x, t) with the highest SI and adds it to the seed group. Algorithm 1 presents the pseudo-code of Dysim.
B. Algorithm Description 1. Target Market Identification (TMI): TMI selects the nominees that exert large influence spread, clusters select nominees to identify each target market for promoting complementary items to socially close users, and prioritizes the target market with fewer substitutable items to the nominees in the overlapping target markets.
For nominee selection, TMI carefully examines the marginal gain of influence for each nominee. It's crucial to select a costeffective nominee due to different costs of nominees and a limited budget. Therefore, we propose marginal cost-performance ratio (MCP) to jointly consider the above factors and ensure the approximation ratio of Dysim in Theorem 5. Specifically, given a set N of selected nominees, MCP of a nominee , where f is the importance-aware influence spread σ with the nominees placed in the first promotion as the seeds and P pref , P act , and P ext assigned at the beginning of this promotion. For the nominees with the costs satisfying c u,x < b − (u ,x )∈N c u ,x , TMI iteratively extracts the one with the highest MCP into N .
Afterward, TMI identifies the target markets by clustering the nominees. To promote complementary items to the users in a target market, TMI first clusters the nominees in N (e.g., by clustering methods POT [53] and FGCC [54]) 15 according to the social distances between the nominees and the relevance between their promoting items, i.e.,r C x,y −r S x,y , wherer C x,y andr S x,y are the average complementary and substitutable relevance between x and y over all users, respectively. 16 Larger complementary and smaller substitutable relevance are encouraged. For each cluster, a target market τ is identified by exploring the influenced users from the nominees N τ (e.g., by MIOA [23]). 17 Note that with TMI, the budget allocation of Dysim is realistic since a larger target market is inclined to have a larger budget to promote items. In TMI, the target markets are identified by the influence of nominees, where more nominees and influential nominees lead to a larger target market. As more nominees and influential nominees usually incur a larger cost [3], Dysim allocates larger budgets to those target markets accordingly.
Afterward, TMI prioritizes the target market with fewer substitutable items to the nominees in the overlapping target markets. Let G denote a set of target markets with common 15 POT discovers social communities according to users' opinions. TMI employs POT by treating the opinions of a community as items of a target market. Accordingly, TMI regards the detected item-based user communities as the clusters of nominees, where the users in the same detected community are socially close to each other, and their promoting items have larger complementary relevance than substitutable relevance. On the other hand, FGCC identifies the clusters for two types of related objects simultaneously. TMI employs FGCC by constructing the incidence matrix of users and items to identify their clusters. TMI clusters the nominees together if their users and items belong to the same user and item clusters, respectively. 16 The derivation of relevance is described in Sec. V-A. 17 MIOA identifies an influence region from a source node, and other nodes in the region can be reached from the source with sufficient influence probabilities on the maximum influence paths. TMI employs MIOA to identify all users that can be effectively influenced by the users of the nominees as the users in the target market.
with the common user number above a threshold θ. 18 TMI arranges the promoting order for the target markets in each G by deriving Antagonistic Extent (AE) of each target market τ i according to the substitutable relationship between every promoting item x and the items of other target market τ j , i.e., AE(τ i ) = x∈τi,y∈τjr S x,y , where τ i , τ j ∈ G, i = j. The target market (and the items in the corresponding nominees) with a smaller AE is promoted earlier in G. 19 Example 1. Figs. 5(a) and 5(b) present an example of TMI with a social network and the average relevance over all users in the whole social network, where the dotted and dashed edges are the complementary and substitutable relationships, respectively. The number beside each edge is the relevance.

Dynamic Reachability Evaluation (DRE):
For each target market τ k ∈ G selected by TMI, DRE evaluates Dynamic Reachability (DR) of each item in τ k , and the nominees (in N τ k ) promoting the item with the highest DR serve as the candidate seeds. In other words, after TMI has identified target markets with socially close users to promote complementary items and has prioritized the target markets using AE, DRE allows each target market to prioritize its promoting items differently and lets the nominees promoting items with higher DR be the seeds earlier. 20 Specifically, let d τ k denote the diameter of the target market τ k , and S G is the seed group determined so far for all the target markets in G. Let I τ k denote the items that have not yet been promoted in τ k . DR of an item The proactive impact P I W,τ k (S G , x, d τ k ) is the probability of x to increase the preferences of users in τ k for other items.
is the probability to increase the preferences of users in τ k for x under the impact from other items in S G . 21 The derivations of the proactive impact and the reactive impact are detailed in Sec. V-B to capture the probability of increasing users' preferences for items based on their dynamic perceptions of item relationships.
Consequently, for each τ k selected by TMI, DRE extracts the nominees {(u, the highest DR as the candidate seeds iteratively, and this property (i.e., the highest DR) is important to approximate the optimal solution in Theorem 5.
Example 2. Following Example 1, this example shows how the DRE of Dysim works based on the diffusion model to solve IMDPP. Assume that the seed group becomes S G = {(u 1 , iPad, 1)} after τ 1 is promoted. To update the complementary and substitutable relevance in each user's dynamic perception, Dysim employs the Monte Carlo method to generate different cases of users' adoption decisions according to their preferences for items and the influence strength. For example, suppose that, due to the seed u 1 's promotion at t = 1, u 2 adopts iPad and promotes to u 5 by her social influence. For the case that u 5 adopts iPad, the update of her adopting item (referring Fig. 3) in turn changes her personal item network from Fig. 6(a) to Fig. 6(b). Meanwhile, u 5 's preference for AirPods increases due to the adopted item {iPad} and her changed personal item network ( Fig. 6(b)), where the complementary relevance between iPad and AirPods increases from 0.05 to 0.1. By contrast, for the case that u 5 does not adopt iPad at t = 1, her personal item network and her preference for AirPods remains unchanged. Based on the number of times these cases being observed, Dysim computes the expectation of u 5 ' personal item network, as shown in Fig. 6(c).

Timing Determination by Substantial Influence (TDSI):
After a set of nominees N p = {(u, x p )} are generated by DRE, TDSI iteratively extracts the nominee and finds a proper promotional timing t with the largest substantial influence (SI), 22 Detailed calculations are presented in Example 4. where SI is exploited to measure the impact of assigning a nominee at some timing under the impact of the seed group S G . In other words, with SI, TDSI can find some (u, x p , t) (by assigning some nominee (u, x p ) at some timing t) that has the largest impact under S G . TDSI then adds it to S G and looks for the next seed repeatedly until all nominees in N p are assigned some timings and added to S G .
Specifically, for each (u, x p , t), SI represents its impacts for immediate and subsequent adoptions according to the marginal adoption M A τ k (S G , (u, x p , t)) and marginal likelihood M L τ k (S G , (u, x p , t)), respectively. The marginal adoption is the increment of the total adoptions after (u, x p , t) is added into S G , whereas the marginal likelihood is the increment of the likelihood for not-yet-adopted items to be adopted in the future promotions if (u, x p , t) is added into S G . Let τ 1 , τ 2 , . . . , τ k−1 ∈ G denote the target markets promoted prior to τ k . Note that the seeds in τ i (i < k) have been determined since TMI has arranged the promoting order of target markets. Similar to DR, SI of (u, x p , t) is also derived under the impact of the seed group S G as follows.
where the marginal likelihood is weighted by the ratio of the remaining number promotions to the total number promotions, as more remaining promotions indicate more chances for future adoptions. To derive SI, TDSI simulates the influence diffusion with S G and S G ∪ {(u, x p , t)}, respectively, by the Monte Carlo method. MA is the difference of adoptions between whether to have (u, x p , t) as a seed. Likewise, ML is the difference of likelihood for adopting not-yet-adopted items in the future between whether to have (u, x p , t) as a seed. To estimate the likelihood, for each case simulated by the Monte Carlo method, TDSI examines the probability for every user in τ k to adopt each not-yet-adopted item in the next promotion. Accordingly, TDSI estimates the expectation of likelihood. Detailed derivations of marginal adoption and marginal likelihood are presented in Sec. V-C. They capture the changes in social influence strength and personal preferences, which is crucial to improve the lower bound in Theorem 5. TDSI iteratively extracts the nominees, finds the time leading to the largest SI, and adds it to the seed group . Instead of exploring every possible t to maximize Eq. (2) for each nominee, TDSI only needs to search t ∈ [t, min{t + 1, i≤k T τi }], wheret is the latest promotion in S G (i.e.,t = max{t | (u, x, t) ∈ S G }), T τ k is the promotional duration of τ k , proportional to the number of nominees in τ k (i.e, T τ k = |N τ k |·T τ i |N τ i | , where N τi is the set of nominees in τ i and τ i , τ k ∈ G). The limitation is satisfactory for the following reasons. On one hand, since 1) the target markets have been arranged in a promoting order (by TMI), 2) the items with higher DR have been promoted with priority (by DRE), and 3) the nominees with higher SI have become seeds (by TDSI), t is required to be no earlier than the seeds in S G , i.e., t ≥t. On the other hand, since the importance-aware influence function is non-monotonically increasing (proved in Sec. IV-C), it is not necessary to explore the later timings for nominees if the seeds of any previous promotion have not been examined entirely. Thus, evaluating only the timing right aftert is sufficient, because later promotional timings only reduce the extent of the marginal likelihood considered in SI. Moreover, since promoting items of different target markets in G are substitutable to each other (which will not be promoted simultaneously), each market τ i is allowed a promotional duration T τi , andt + 1 cannot exceed the last promotional timing of τ k , i.e., i≤k T τi . Thus, the search of t is upper bounded by min{t + 1, i≤k T τi }.
After deriving the promotional timing for a nominee (u, x p ), Dysim selects the next item with DRE and finds the timing with TDSI. After all nominees in τ k are assigned their promotional timings as the seeds, TMI moves on to the next target market τ k+1 ∈ G. It returns the seed group S = G S G as the solution after all target markets are examined. 23

C. Theoretical Results
In the following, we first present several good properties of the importance-aware influence function σ under some conditions. Definition 3 (Submodular function [56]). Given a ground set U , a set function ρ : 2 U → R is submodular if for any subset X ⊆ Y and any element e ∈ U \ Y , Lemma 1. The importance-aware influence function σ is nonmonotone increasing but submodular for P pref , P act , and P ext assigned at the beginning of all promotions.
Proof. Firstly, we first analyze the case with a single promotion. It is obvious that the importance-aware influence function 23 S G of different G can be derived in parallel due to the independency of different G.
σ is monotone increasing even if we add a seed that promotes an item with importance 0 and no longer promote any other user to adopt items. That is, σ does not decrease. For each user-item pair, the preference P pref (u, y) is regarded as the probability of the edges from user-item pair (u , y) to useritem pair (u, y), where u denotes u's in-neighbors. Likewise, the extra adoption probability P ext (u, u , x, y) is also regarded as the probability of the edge from user-item pair (u , x) to user-item pair (u, y). When P pref , P act and P ext do not change, all the events of evaluating preference P pref and influence strength P act , and extra adoption P ext happen independently. Then, the proof of the submodularity of σ can be reduced to the proof of its submodularity in every arbitrary realization (i.e. a deterministic graph) of the stochastic graph. Therefore, σ is a coverage function, which is submodular [57].
Our proof can be generalized to the triggering model easily by sampling the corresponding in-neighbor edge set of each user independently. For better understanding of the process of influence propagation, we first show the proof for the ICbased models. Following [1], the proof of the submodularity of importance-aware influence function on the IC model is reduced to that in every arbitrary realization of the stochastic graph. Specifically, the realization is determined by flipping a coin on every edge independently according to its probability. We show the submodularity of σ(S t ) in a deterministic realized graph G SN (V, E ) by flipping the edge coin P act (u , u) of G SN with the probabilities of influence strength and the edge coin P ext (u, u , x, y) with the extra adoption probabilities independently first. If the edge coin P act (u , u) of G SN is up, i.e., the event of influence happens, then we flip the edge coin P pref (u, y) with the probabilities of preference. Then, The process of adoption propagation can be regarded as the influence propagation process. Upon the deterministic graph G SN , a user u can be successfully influenced by its in-neighbor u who has adopted x, if and only if it does not adopt the item x or the relevant item y of x (i.e. the item y with P ext (u, u , x, y) > 0 has not been purchased). Notice that the two events happen independently. Thus, for any nominee (u, x), its influence propagation becomes a connected subgraph of G SN rooted by u, which is regarded as the influence of seeding u to promote item x. Note that each path of the connected subgraph may consist of different items due to the happening of the two events (e.g. P x1x2x2x4... ), and each user in the path may adopt more than one item. For each seed group S t in the t-th promotion, a realization of σ(S t ) is exactly the union of the connected subgraphs that combine the influence produced by each nominee (u, x) together.
Next, we analyze the case of multiple promotions. Even when P pref , P act and P ext are static, there are some cases showing that the monotone increasing property of the importanceaware influence function σ does not hold. This is because if a user u successfully adopts item x, it cannot adopt item x again in the later promotions, i.e., it cannot propagate influence of item x again. As a consequence, putting a seed to promote u to adopt item x early may result in the influence of u adopting x not propagating in later promotions to increase the adoption s2, y of other users. Now we show the non-monotone increasing property by the following observation.
Assume there are exactly two candidate items y and x. We let w x = 1, w y = 0, c u,x > b, c u,y > b, c v,x > b for any v = u (i.e., only (v, y) can be nominees for any v = u), P pref (v, y) ≡ 1, P ext (v, y, x) = P ext (v, x, y) ≡ 0 24 , P pref (v, x) ≡ 0 for any v = u (i.e., v can only adopt item y for any v = u), P pref (u, x) ≡ 0, and P ext (u, y, x)) ≡ 1 (i.e., u can only adopt item x after its in-neighbor adopts item y). As a consequence, the total influence focuses on computing the probability of user u adopting item x. Assume there are exactly two promotions of influence propagation. Given a seed group S, we denote the probability of user u adopting item x in the first and second promotions as P r 1 and P r 2 , respectively, according to the seed group S. Note that σ(S) = P r 1 + (1 − P r 1 )P r 2 and P r 2 is conditioned on P r 1 . If we add any nominee (v, y) to the first promotion, the probability of u adopting x in the first promotion becomes P r 1 , where P r 1 ≥ P r 1 . However, the probability of u adopting x in the second promotion becomes P r 2 , which is at most P r 2 . This is because some nodes on the existing promoting paths, which make u adopt x, in the second promotion cannot propagate influence since they have been promoted by (v, y) in the first promotion, and the new nodes promoted the adopted items by (v, y) cannot improve the probability of u adopting x in the second promotion. It implies σ(S) = P r 1 + (1 − P r 1 )P r 2 is larger than σ(S ∪ {(v, y, 1)}) = P r 1 + (1 − P r 1 )P r 2 under the condition of (1−P r 1 )P r 2 −(1−P r 1 )P r 2 > P r 1 −P r 1 . By letting P r 1 = 0 (e.g. no seed in the first promotion), the condition becomes P r 2 − (1 − P r 1 )P r 2 > P r 1 . If a sufficiently large P r 2 (e.g. almost 1) is achieved, then choosing P r 2 slightly smaller than 1 is sufficient to satisfy the condition. The illustrative example is shown in Figure 7. Note that P r 1 = 0, P r 1 = 0.74, P r 2 = 0.96 and P r 2 = 0.48 imply σ({(s 2 , y, 2)}) = P r 1 + (1 − P r 1 )P r 2 = 0.96 > σ({(s 1 , y, 1), (s 2 , y, 2)}) = P r 1 + (1 − P r 1 )P r 2 = 0.74 + (1 − 0.74) × 0.48 = 0.8648, which is not monotone increasing.
The realization of σ(S) is not the union of total adopted items in each promotion directly. However, the submodularity 24 The simplified symbol Pext(v, y, x) ≡ 0 represents that it holds for arbitrary in-neighbors of v.
can still be proved in a realized deterministic graph, which is a specific disjoint union of each graph corresponding to a different promotion, and each graph is similar to the one in single promotion. Hence, The importance-aware influence function is also a coverage function, which is submodular [57]. Specifically, in the first promotion, we first flip the edge coin P act (u , u) of G SN with the probabilities of influence strength and the edge coin P ext (u, u , x, y) with the extra adoption probabilities independently. If the edge coin P act (u , u) of G SN is up, then we flip the edge coin P pref (u, y) with the probabilities of preference independently. Afterward, we obtain the connected subgraphs of the deterministic graph rooted at each seed of S 1 . After the first promotion, the promoted nodes in this promotion cannot be promoted the adopted items again, and it propagates the corresponding the influence later. Therefore, after flipping edge coins for the second promotion again, we obtain those connected subgraphs of the deterministic graph rooted at each seed of S 2 to avoid reaching each promoted user-item pair (u, x) in the connected subgraphs rooted at each seed of S 1 . 25 In addition, if S 2 has some nominees in the first promotion, these nominees can still try to promote their neighbors in the second promotion since they are chosen as new seeds again. Similarly, we repeat the same process until all the random edges over the T promotions are realized. Notice that we flip edge coins of all the T promotions before seeding since the probability of each edge in the later promotions is independent of that in the previous promotions. After the above realization, letσ(S t | S 0 , S 1 , . . . , S t−1 ) denote the influence of seeding S t conditioned on seeding S t for t = 0, 1, . . . , t − 1, where S 0 = ∅. Letσ(S) denote the importance-aware influence of a realization of σ(S). Then, σ(S) = T ∪ t=1σ (S t | S 0 , S 1 , . . . , S t−1 ). To prove the submodularity, it is sufficient to show that the functionσ under each realization satisfies Inequality (3) based on the property that a user cannot be promoted again by another path, if it is promoted by some realized path rooted at some nominee in an early promotion. For any seed group set S X ⊆ S Y and any seed (u, x, t) ∈ U \ S Y , where U consists of all the possible seeds, it is sufficient to prove that the marginal decreased influence of seed (u, x, t) conditioned on the larger seed group is more than the smaller one. It is equivalent to show that all the users, who can be promoted by (u, x, t) but have been promoted by S X earlier than (u, x, t), can also be promoted by S Y earlier than (u, x, t) to adopt the same item. Since S Y contains S X , for each (v, y, t ) ∈ S X , it can either block (u, x, t) similar to those in S Y or be replaced by some seed (v , y , t ) ∈ S Y \S X that does not have smaller influence than (v, y, t ) in S X (i.e. (v , y , t ) may promote users earlier or promote more users). Therefore, (4) The lemma follows.
Note that the general importance-aware influence function is not submodular. The reason is that, in some case, some users' P pref or P ext in an early promotion can be increased by seeds, but these seeds cannot bring the immediate adoption in this promotion. For a later promotion, however, the seeds can bring more immediate adoptions due to the increased P pref or P ext . As a consequence, the sum of immediate adoptions under the influence of respective seeds in each promotion is smaller than the overall adoptions under the influence of all seeds in all promotions. It makes the importance-aware influence function non-submodular, i.e, violating the submodular Inequality (3).
According to Lemma 1, based on the approximation algorithm for the non-monotone increasing submodular maximization with knapsack constraint problem (SMK), we have the following theorem.
Theorem 2. For P pref , P act , and P ext assigned at the beginning of all promotions, there is an α − -approximation algorithm for IMDPP, where α is the performance ratio of the approximation algorithm for SMK and > 0 is the evaluation error.
Although there is an improved 1 e − -approximation algorithm for SMK by continuous greedy strategy [58] (implying 1 e − -approximation for IMDPP for the current user preferences, social influence, and extra adoption probabilities), it takes much more time than O(n 5 ) (roughly O(n 8 )). Due to the high complexity of the above approximation algorithm for SMK, we design a fast and simple approximation algorithm within O(n 2 ) function calls, where n is the size of the ground set. So far, for SMK, there is a 1 6 -approximation algorithm [59] taking O(n 5 ) by enumeration of at most three potential solutions with the greedy strategy, where n is the size of the ground set. Inspired by the work [59], following a similar frame, our algorithm does not involve the enumeration, and the time complexity can be reduced to O(n 2 ). More specifically, there are two steps to achieve the goal. First, instead of finding a solution satisfying the condition of Lemma 3 combining the enumeration and greedy strategy, we find the desired solution satisfying the condition by TMI. TMI iteratively adds an element with the maximum marginal cost-performance ratio (i.e., MCP) into the solution until the budget is just violated or negative marginal influence occurs. Second, to achieve the desired approximation, following a similar approach in [59] by calling the greedy process with O(n 2 ) function calls and a linear time algorithm [60] for unconstrained submodular maximization problem (USM), we can obtain a solution with a good approximation ratio. However, the achieved solution may be not feasible. We find the feasible solution by deleting the violating element to obtain a new candidate solution. Then, the algorithm finds another seed group consisting of a single element that has the maximum importance-aware influence, and chooses the better one between them. To analyze the performance ratio, we first derive the following two key lemmas. In the following, for better comparison with [59] and understanding, we still use f as the importance-aware influence function of SMK. Lemma 2 (Lemma 2.2 in [59] ). Given a submodular function, sets C, S 1 ⊂ U , let C = C \ S 1 , and S 2 ⊂ U \ S 1 . Then The following lemma shows that TMI can find a solution with a good approximation ratio. for any i = 1, 2, . . . , l and j = 1, 2, . . . , k. After summing up the numerator and the denominator separately of the lefthand-side with l terms and the right-hand-side with k terms in Inequality (6), respectively, we have 27 Based on Lemma 2 and 3, we have the following theorem.
Theorem 3 (adapted from Theorem 2.3 in [59]). There is a Proof. Let S * be the optimal solution with f (S * ) = opt. Note that S * \ S 1 and S * \ S 1 \ S 2 are both feasible solutions disjointing with S 1 and S 2 , respectively. By Lemma , respectively. If f (S 1 ∩ S * ) ≥ c · opt, then the 1 2 -approximate algorithm of USM on the ground set S 1 in linear time [60] implies the approximation ratio is at least c 2 opt. Otherwise, opt. 27 In fact, even if the negative marginal influence occurs, we can continue to run the algorithm until the budget is just violated. Although the marginal influence may be negative, Inequality (8) still holds only if the corresponding denominator (i.e. cost function) is more than zero, implying the lemma still holds.
where the last inequality comes from Lemma 2. Thus, Combining with the case f (S 1 ∩ S * ) ≥ c 2 opt, the approximation ratio becomes min{ c 2 , 1−c 4 }opt. By setting c = 1 3 , we achieve a 1 6 -approximation solution, denoted byS. However, S may be infeasible since all of S 1 , S 2 , and S 1 ∩ S * may just violate the budget constraint by the same element e 1 added into both S 1 and S 1 ∩ S * , and e 2 added into S 2 defined in Lemma 3.
In the following, we construct a feasible solution with the guaranteed performance ratio. We denote e max = argmax e f ({e}) andŜ = argmaxS \{e},{emax} {f (S \ {e}), f ({e max })} as the output of the algorithm, where e is the corresponding element ofS that violates the budget constraint. Consequently, where the third inequality is based on the submodularity. The theorem follows.
Afterwards, we apply the proposed algorithm to the special case. Note that f becomes the importance-aware influence function σ with |V | |I| T variables, for seeding some users and choosing some items to be promoted at some promotional timings. Let k max denote the maximum size of a feasible solution. Since we study the strategy between the multiple promotions and the single promotion under the same budget, we assume k max of the multiple promotions and the single promotion is the same, which is bounded by |V | |I| without the budget constraint. Notice that k max can be computed in linear time by iteratively adding the minimum cost seed until the budget constraint is violated. Proof. By Theorem 2 and 3, the approximation ratio follows. We analyze the time complexity as follows. Let M be the time to evaluate σ by Monte Carlo sample depending on the evaluation error > 0. By lemma 3, it needs at most O(n 2 ) function calls in TMI. For IMDPP, n = |V | |I| T and it needs at most k max iterations to use all the budget, i.e., stop the algorithm. Thus, the number of function calls is O(|V | |I| T k max ) in TMI. Note that TMI brings the main function calls. Thus, the total number of function calls of the designed algorithm becomes O(|V | |I| T k max ), implying the time complexity is O(M |V | |I| T k max ).
Next, let us analyze the performance ratio of Dysim in the following more general case.
where P minpref > 0, P minext > 0 and P minact > 0 are the minimum preference, extra adoption probability and influence strength, respectively. c is the maximum hop of influence propagation, M is the time to evaluate σ depending on the evaluation error > 0, and k max is the maximum size of a feasible solution.
Proof. Since the importance-aware influence function of the general problem is neither monotone increasing nor submodular, we first find the relation between the general problem and a restricted problem (defined later) whose importance-aware influence function is monotone increasing and submodular. Consequently, a solution found by the algorithm in the restricted problem can be regarded as an approximation solution to the general problem. We first prove that the output value of Dysim is at least β − (defined later) times of the value of the restricted problem . Afterwards, according to the evaluation of the range of parameters changing, we derive the importanceaware influence function gap between the restricted problem and original problem is at most γ (defined later), implying the total gap is (β − )γ.
Specifically, let γ = min{P c minpref · P c minact , P c minext }. Let S t and S * t denote the seeds in the t-th promotion of the optimal solution of the restricted problem (i.e., P pref ≡ P minpref , P ext ≡ P minext , P act ≡ P minact , and c-hop influence propagation) and the optimal solution of the general problem, respectively. First, we construct an auxiliary solutionN such that σ(N ) = max{σ(N first ), σ({e max })}, where N first consists of all nominees in N promoting items in the first promotion, i.e., N first = {(u, x, 1) | (u, x) ∈ N }, and e max is the seed bringing the maximum expected importance-aware influence. Note that σ( G S G ) ≥ σ(N ) since the solutionN has been considered by Dysim. Hence, our goal is to prove σ(N ) ≥ (β − )γσ(S * ) sufficiently by two stages, where β will be decided later. Before presenting the formal proof, we first consider the case that each seed user can adopt each item once in all the promotions. Notice that if P pref , P ext and P act do not change, it is not necessary to assign the seeds in different promotions; it may decrease the probability of adoption for the multiple promotions since the promoted users in early promotions cannot propagate the influence in later promotions, where these users may become the bridges to promote the items with larger importance to others. Thus, if P pref , P ext and P act do not change in the restricted problem, there exists an optimal solution for the restricted problem such that only the first promotion has seeds (i.e.,Ŝ t = ∅ for t > 1).
For the first stage, when P pref , P act and P ext are static, by the above observation, we can focus on the single promotion. Moreover, by the proof of Lemma 1, the importanceaware influence function is monotone increasing submodular. Consequently, if there exists a β-approximation algorithm for monotone increasing submodular maximization with knapsack constraint problem (MSMK), then σ(N ) ≥ (β − )σ(Ŝ 1 ) if P pref ≡ P minpref , P ext ≡ P minext and P act ≡ P minact do not change for the single promotion, where is the evaluation error of Monte Carlo sampling. Furthermore, when P pref , P ext and P act can change, σ(N ) is no smaller than σ(N ) with P pref ≡ P minpref , P ext ≡ P minext and P act ≡ P minact unchanged, since higher P pref , P ext and P act lead to more influence for a single promotion. Therefore, if P pref , P ext and P act can change, σ(N ) is at least (β − )σ(Ŝ 1 ) with P pref ≡ P minpref , P ext ≡ P minext and P act ≡ P minact unchanged. For the second stage, it is sufficient to prove when P pref ≡ P minpref , P ext ≡ P minext and P act ≡ P minact do not change, σ(Ŝ 1 ) is at least γσ(S * ) with varying P pref , P ext and P act . Note that, if P pref ≡ P minpref , P ext ≡ P minext and P act ≡ P minact do not change, σ(Ŝ 1 ) ≥ σ(S * first ), where S * first consists of all nominees of S * and assigns them in the first promotion, i.e., S * first = {(u, x, 1) | (u, x, t) ∈ S * }, and it is a feasible solution of the restricted problem. Moreover, σ(S * first ) with P pref ≡ 1, P ext ≡ 1 and P act ≡ 1 is no smaller than σ(S * ) with varying P pref , P ext and P act , since P pref , P ext and P act can be increased to at most 1 for the multiple promotions. Therefore, we only need to prove that, σ(S * first ) is no smaller than γσ(S * first ) with P pref ≡ 1, P ext ≡ 1, and P act ≡ 1, if P pref ≡ P minpref , P ext ≡ P minext and P act ≡ P minact do not change. To prove it, for each promoted user-item pair, it can be promoted by the promoting paths from different influence propagation hop j (j ∈ {1, 2, . . . , c}). Then, we denote X j as the probability that all the promoting paths succeed to promote the useritem pair in the j-th hop with varying P pref , P ext and P act . For each influence propagation hop j, when P pref ≡ P minpref , P ext ≡ P minext and P act ≡ P minact do not change, the total adoption probability of paths in hop j is at least min{P j minpref · P j minact , P j minext }X j . Thus, the total adoption probability of paths with P pref ≡ P minpref , P ext ≡ P minext and P act ≡ P minact unchanged is at least min{P c minpreft · P c minact , P c minext } of that with P pref ≡ 1, P ext ≡ 1 and P act ≡ 1. Thus, σ(S * first ) is no smaller than γσ(S * first ) with P pref ≡ 1, P ext ≡ 1 and P act ≡ 1, if P pref ≡ P minpref , P ext ≡ P minext and P act ≡ P minact do not change. As mentioned above, the approximation ratio of the case depends on the approximation β of MSMK. In particular, Dysim can guarantee the performance ratio for MSMK by Nominee Selection and checking all possible single candidate seed in a subroutine of Dysim, i.e., the algorithm in [61] which has 1−e −1 2 approximation [62] for MSMK. In fact, this approximation can be further improved to 1 − 1 √ e by an analysis similar to that in [63] for MSMK. Furthermore, since the improvement of other subroutines in Dysim does not worsen the result, the approximation holds, implying β = 1 − 1 √ e . Last, we analyze the time complexity. Recall that M is the time to evaluate σ by Monte Carlo sample depending on the evaluation error > 0. It is sufficient to show the total number of σ function calls. Note that Nominee Selection and TDSI take the main function calls. In Nominee Selection, it involves at most |V | |I| k max function calls. In TDSI, the primary cost is finding the promotional timing for each nominee. If there are at most Ī items chosen in Nominee Selection, Ī items are distributed to at most k max nominees chosen in Nominee Selection. We assume the i-th item is associated with k i users, where i k i ≤ k max . For the i-th item, it takes at most k 2 i function calls since TDSI searches at most two promotional timings for each nominee associated with the item. Therefore, TDSI involves at most (k 2 Thus, the total number function calls of Dysim is O(|V | |I| k max ), implying the time complexity is O(M |V | |I| k max ). The theorem follows.

A. Update Mechanism of Main Factors in IMDPP
The details of deriving and updating each factor are elaborated as follows.
(1) Relevance measurement. KG and meta-graphs with personal weightings are exploited to find the personal relevance between two items [10], [11], [17], [18]. KG [11], [18] is a heterogeneous information network G KG = (V, E, Φ, Ψ) with node and edge sets (V and E) and two type-mapping functions (Φ and Ψ), e.g., Φ(iPhone) = ITEM and Ψ((iPhone, Bluetooth)) = SUPPORT. A meta-graph is a schema represented as a graph of node types with certain connections (e.g., Fig. 1(b)) specified by users [17] or learned from historical data of users [11]. For a meta-graph m, its instances are the subgraphs of KG that exactly match the schema of m. The relevance between item x and item y as defined by meta-graph m, i.e., s(x, y | m) ∈ [0, 1], is correlated to the number of m's instances with end items x and y (e.g., SCSE [17]). For example, in Fig. 1(b), s(x, y | m 1 ) is correlated to the number of common FEATUREs supported by x and y in KG.
As each relationship can be captured by various meta-graphs with different connections between ITEMs, we realize the personal item networks using the meta-graphs with personal weightings [10]. Formally, let W meta (u, m, ζ t ) denote a user u's weighting on a meta-graph m at the end of step ζ t , i.e., the significance of m to u for describing an item relationship. According to [44], [16], [10], [11], adopted items usually change users' perceptions of item relationships. Therefore, we update u's weightings on meta-graphs (e.g., by SemRec and RelSUE [10], [11]) after all adoption decisions at step ζ t are made. Then, the complementary and substitutable relevance between x and y in u's perception, denoted as r C (u, x, y, ζ t ) and r S (u, x, y, ζ t ) respectively, are immediately derived (e.g., by SemRec [10]) according to s(x, y | m C ) and s(x, y | m S ) of every meta-graph m C and m S , respectively. 28 Consequently, u's personal item network is deduced as G PIN (u, ζ t ) = (V ITEM , E C , E S ), where V ITEM is the item set, and an edge (x, y) ∈ E C (or E S ) exists and carries the complementary (or substitutable) relevance between x and y if r C (u, x, y, ζ t ) > 0 (or r S (u, x, y, ζ t ) > 0). When u and ζ t are clear from context, we write r C x,y and r S x,y for short. (2) Preference estimation. Following [16], [38], [47], u's preference for x depends on her adopted items and personal item network. Thus, after all adoption decisions are made and the personal item network is changed, the preferences for not-yet-adopted items are updated to reflect users' interests in those items. Previous works derive users' preferences for not-yet-adopted items by learning the embedding of users and items (e.g., RSC and RCF [16], [47]) or by statistics inference [38]. Thus, let A(u, ζ t ) be the set of items that u has adopted so far after all adoption decisions are made at step ζ t . Equipped with A(u, ζ t ) and G PIN (u, ζ t ), we follow the above research to derive u's rating on each not-yet-adopted item y as u's updated preference for y at ζ t , i.e., P pref (u, y, ζ t ).
(3) Influence learning. The influence strength is correlated to the similarity of users, i.e., their personal item networks and their adopted items, since similar users are inclined to become closer and easier to influence each other. Therefore, after users' personal item networks and adopted items update, the influence strength changes according to statistic models [48] and user embedding (e.g., DeepInf and DANSER [49], [50]). Following the above works, after the sets of adopted items A(u, ζ t ) and A(v, ζ t ) are obtained and personal item networks G PIN (u, ζ t ) and G PIN (v, ζ t ) are updated, we update the influence strength from u to v at step ζ t as P act (u, v, ζ t ).
(4) Item associations. When users are promoted an item x by social influence, an extra adoption of a relevant item y is triggered due to item associations according to the probability of u being promoted and preferring x as well as the relationships and relevance between x and y, by learning and comparing the embedding of u, x, and y (e.g., CKE, RSC, and RCF [16], [18], [47]). As a result, when u is promoted an item x by u , at step ζ t , u's extra adoption probability for x's relevant item y is P ext (u, u , x, y, ζ t ), derived according to P act (u , u, ζ t − 1), P pref (u, x, ζ t − 1), and u's personal item network G PIN (u, ζ t − 1).

B. Derivation of DR in DRE of Dysim
As formulated in Eq. (1), for an item x to be promoted in τ k ∈ S G , its DR consists of x's proactive impact (PI) and reactive impact (RI). The former is the probability of increasing users' preferences for other items by x, while the latter is the probability of increasing users' preferences for x by other items. The adoption of x increases (decreases) the preferences for the items complementary (substitutable) to x [7]. Given S G , the likelihood of regarding x and y as complementary (substitutable) for each user is proportional to the complementary (substitutable) relevance between x and y, i.e., L C,τ k (x, y, S G ) =r C x,ȳ r C x,y +r S x,y and L S,τ k (x, y, S G ) = r S x,ȳ r C x,y +r S x,y , wherer C x,y andr S x,y are the average complementary and substitutable relevance between x and y over all users in τ k after the promotion of S G , respectively. 29 Therefore, PI is recursively formulated as follows.
where y represents each item relevant to x, and W is the set of item importance. The first two terms are the likelihood to increase and decrease the preferences of the users in τ k for y (weighted by the corresponding relevance between x and y and y's item importance). The last term P I W,τ k (S G , y, d − 1) recursively captures the likelihood to increase or decrease the preferences (of users in τ k ) for other items via item impact propagation from y, where P I W,τ k (S G , y, 0) = 0. 30 Similarly, RI evaluates the item impact propagation from any other item z to x according tor C z,x andr S z,x as follows.
where z is each item relevant to x and RI wx,τ k (S G , y, 0) = 0. Note that RI is derived from w x (rather than W in PI), since RI only focuses on the preferences for x.
Example 4. For Example 2, we show the detailed calculation of the DR of iPhone as follows.
= 0.7 + 1 = 1.7. 29 The update of relevance is described in Sec. V-A. 30 Here it is d − 1 because item impact has propagated 1-hop from x to y.

C. Derivation of SI in TDSI of Dysim
As formulated in Eq. (2), SI of a candidate seed (u, x p , t) is measured by the marginal adoption (MA) and the marginal likelihood (ML). The marginal adoption of (u, x p , t) after the promotion of S G is where σ τ k (S G ) is the importance-aware influence in τ k under S G . The marginal likelihood of (u, x p , t) after the promotion of S G is where π τ k (S G ) is the likelihood of all users in τ k to adopt the rest of not-yet-adopted items in the future under S G . As the probability for a user to adopt an item depends on the social influence strength she receives and her preference for the item, π τ k (S G ) is derived from the sum of probabilities of all u ∈ τ k to adopt their not-yet-adopted items y.
where ζ last t is the last step of the latest promotiont in S G (i.e., is the set of items adopted by v so far after the promotions of S G . AIS(v, y, ζ last t ) is the aggregated influence probability for y to be promoted to v in the next promotion after the promotions of S G . 31 P pref (v, y, ζ last t ) is v's preference for y after the promotions of S G . 32

D. Dysim for Adaptive IM
For the adaptive IM without a predefined budget allocation, Dysim carefully determines the current promotion budget by avoiding the antagonism of the substitutable relationship. Specifically, to find S t after the propagation of the (t − 1)th promotion is observed, for t < T , TMI is modified by selecting only one nominee with the largest MCP at a time. Accordingly, Dysim exploits TMI multiple times to gradually find nominees and target markets until the identified overlapping target markets promote substitutable items. Then, Dysim rejects the latest identified nominee that causes the antagonism of the substitutable relationship. Next, Dysim exploits DRE and TDSI alternatively to determine whether the identified nominees for each G are suitable for the t-th promotion. Note that the search for possible promotional timings in TDSI is limited to t and t+1. Once the candidate seed with the largest SI is assigned to t + 1, Dysim ends the searching of S G t since 31 For example, under the IC, AIS(v, y, ζ last 32 The updates are described in Sec. V-A. the remaining nominees in S are suitable for later promotions as well. After all G are examined, S t = G S G t is found as the seeds for the t-th promotion. On the other hand, for t = T , Dysim exploits TMI to select the best nominees under the remaining budget and assigns them to T as S T .

A. Experiment Setup
The experiment includes four datasets, where each one consists of a KG and a social network: 33 i) Douban [37], ii) Gowalla [64], iii) Yelp [65], and iv) Amazon [65]. Since there are no social relationships in Amazon, we supplement it with Pokec 34 according to the user profiles [66]. To capture the complementary and substitutable relationships between items, the meta-graphs are generated according to [44], and the relevance of a certain relationship regarding a meta-graph is derived according to [17]. For the diffusion models, the four factors, relevance measurement (including the learning of personal weightings on meta-graphs and the constructions of personal item networks), preference estimation, influence learning and item associations are learned and updated based on [10], [16], [48], and [16], respectively. To set up the IMDPP problem, the item importance of Douban, Yelp, and Amazon is distributed following the prices on their websites, while that of Gowalla is randomly assigned (since its website is no longer online). The statistics of the datasets are listed in Table II. Following [3], [67], the costs of hiring users to promote items are set proportional to users' out-degree and their preferences for items, since users who are more influential and who prefer the item less may need more incentive to be seeds. In the implementation of Dysim, we exploit the submodularity (similar to CELF++ [22]) to speed up the nominee selection, and follow [53] and [23] to cluster nominees and explore influenced users, respectively, in TMI.
We compare Dysim with OPT (derived from a brute-force approach) and four state-of-the-art approaches: BGRD [38], HAG [37], PS [35], and DRHGA [19] as the baselines. 35 We extend [19], [35], [37], [38] to consider different costs of selecting a user to promote an item by selecting from 33 The KGs are heterogeneous information networks (HINs) in the datasets, where the HINs contain diverse node types like items, categories, brands, etc. Please refer to [37], [64], [65] for more details. 34 https://snap.stanford.edu/data/soc-Pokec.html. 35 Codes and datasets are available on https://tinyurl.com/y26fx2mp. the user-item pairs or the users that satisfy the remaining budget. Furthermore, since they cannot be directly applied to our problem, we augment [19], [35], [37], [38] with CR-Greedy [39] to support multiple promotions and determine the promotion timings of the user-item pairs as the seeds in each baseline. The performance metrics include the 1) influence spread σ (Def. 1) 36 and 2) execution time. We perform a series of sensitivity tests in terms of the budget b and the number of promotions T . To verify our algorithm, we further conduct an empirical study on course promotion in viral marketing for the course selection system. We conduct all experiments on an HP DL580 server with an Intel 2.10GHz CPU and 1TB RAM. Each simulation result is averaged over 100 samples (i.e., M = 100).

B. Performance Comparison
First, we compare all approaches and OPT on small datasets sampled from Amazon with 100 users. Fig. 8(a) shows the importance-aware influence under different budgets. Dysim has the closest performance to OPT, and outperforms BGRD, HAG, PS, and DRHGA, because TMI of Dysim carefully selects influential nominees by MCP, and DRE of Dysim then prioritizes nominees based on dynamic perceptions of item relationships. In contrast, the baselines neglect the changes in item relationships and do not promote items beneficial to each other over time. Fig. 8(b) compares the importanceaware influence under various numbers of promotions. Dysim creates a larger influence spread as T increases because TMI avoids promoting substitutable items to the same users in near promotions, and TDSI finds the promotional timings by carefully evaluating the subsequent adoptions. All baselines do not incorporate the item impact propagation to achieve a larger influence spread as T grows even a sophisticated algorithm based on CR-Greedy [39] is employed to schedule promotions at different timings.
Figs. 9(a)-9(c) compare the importance-aware influence in large datasets under different budgets. 37 For all datasets, Dysim achieves the largest influence spread, followed by DRHGA, BGRD, HAG, and PS, because Dysim is able to   exploit the changes in users' preferences and social influence strength. PS fails to obtain a large influence spread because it only estimates the influence of a seed alone and cannot utilize the impact of items from other promotions to find seeds. BGRD usually achieves smaller than half of the importanceaware influence compared with Dysim, because it neglects the substitutable relationship and regards all items as a bundle to be promoted. Although DRHGA also promotes all items, it is usually better than BGRD since DRHGA is able to select appropriate users to promote each item, instead of regarding all items as a bundle in BGRD. However, as DRHGA does not choose items to be promoted, it still generate a smaller influence spread compared with Dysim. HAG outperforms BGRD in Yelp with low budgets and in Amazon when the budget is relatively low to the social network size. This is because HAG greedily selects the most influential combination of user-item pairs as the seeds, instead of the most influential user to promote a bundle of items, making the solutions of HAG more cost-effective. BGRD fails to achieve a large influence spread for a large b in Douban since items (e.g., songs and books) in Douban are usually complementary, but BGRD still allocates the budget to the same users to promote a bundle of complementary items.
Figs. 9(e)-9(f) present the importance-aware influence in large datasets under different numbers of promotions with the maximal T as 40 (following [39]). Dysim achieves the largest influence spread for all T with significant increments as T grows, because TMI of Dysim first arranges the promoting order of target markets, and Dysim then exploits SI (aware of the changes in preferences and social influence strength) to determine proper promotional timings of nominees for each target market. In contrast, the influence spreads grow slowly for the baselines, especially when T ≥ 20, because they cannot arrange the promoting order holistically and fail to utilize more promotions to properly gain more adoptions.
Figs. 9(d) and 9(g)-9(h) compare the execution time under different budgets and different numbers of promotions, respectively. As shown in Fig. 9(d), when b varies, Dysim requires the least execution time for most cases. HAG suffers from finding numerous combinations of seeds for a large budget. PS requires much time to search for maximum influence paths to evaluate the influence of a user. Although DRHGA only selects users, it takes more time than BGRD since the selection process is repeated for each item. As b becomes larger, the execution time of Dysim only slightly increases since TMI quickly selects influential nominees by MCP according to the cost and increment on important-aware influence for each candidate nominee. PS is less sensitive to b since it employs a discounting strategy to estimate a seed's influence under the impact of selected seeds. On the other hand, as shown in Fig. 9(g), Dysim requires a low overhead to find promotional timings due to an efficient search with pruning in TDSI, whereas the baselines greedily assigning the promotional timings tend to suffer from larger T . To show the scalability of Dysim, Fig. 9(h) compares the execution time of Dysim on different datasets (in the order of the number of users in the social network). The time increases not only as the number of users increases but also as that of items increases (e.g., so the time on Gowalla and Amazon are similar) due to the propagation of item impact. Fig. 10 compares Dysim, Dysim without target markets (i.e., w/o TM), and Dysim without item priority (i.e., w/o IP). We have the following three observations. First, the influence spread is smaller when target markets are not identified, since the selected nominees may promote substitutable items to the same users in consecutive promotions, which detracts from users' preferences for the posterior items to be promoted. By contrast, Dysim effectively avoids the antagonism of the substitutable relationship by identifying and prioritizing the target markets. Second, the influence spread of Dysim without item priority is also smaller than that of Dysim, because all items in a target market are promoted simultaneously, and therefore the promotion of an item is hardly facilitated by promoting its complementary items first. In contrast, Dysim determines the item priority by exploiting DR, which carefully measures the impact from previously promoted items on an item and also the potential impact from this item on other items in subsequent promotions. Third, as T increases, the gaps between Dysim and Dysim w/o TM/IP increase. This is because the number of promotions in Dysim w/o TM/IP is limited, i.e., at most the number of items/target markets, implying that more promotions are not beneficial for a larger influence spread. By contrast, Dysim effectively schedules the promotional timings of different target markets and different items to exploit the propagation of item impacts.

D. Comparison of Different Market Orders
To compare with Antagonistic Extent (AE), we leverage the following metrics to evaluate additional promotional orders of target markets: profitability (PF) [55], size of the market (SZ) [55], relative market share (RMS) [68], and random (RD). PF and SZ are two of the most common criteria to prioritize target markets in the marketing research field. PF is the expected adoptions under the promotion from the corresponding nominees minus the cost of the nominees. SZ is the number of customers in the target market. A target market with a larger PF or SZ is preferred to be promoted earlier. RMS is widely used to assess the value of a firm's item in the product management field. RMS of an item x is defined as the ratio of x's market share to the largest market share of its substitutable item, where the market share is evaluated by the number of users preferring the item most. The target market that promotes items with a higher RMS is prioritized. Fig. 11 manifests that AE and PF usually achieve the largest influence spread, followed by SZ, RMS, and RD. AE and PF outperform the others since AE prioritizes the target markets that have less substitutable relationship on the subsequent target markets, while PF prioritizes the target markets with more profits to ensure their influence spread. When there exist excessively large target markets (e.g., identified by plenty of nominees), PF is suggested as the ordering metric, since PF can accurately prioritize these large target markets to maximize the influence. In general cases, AE is usually a better metric to prioritize the target markets since the impact from the substitutable items promoted by prior target markets is minimized. By contrast, SZ, RMS, and RD, without carefully examining the relationships of items promoted in other target markets, cannot avoid the antagonism of the substitutable relationship. The results manifest that promoting target markets with a smaller AE or a larger PF earlier in TMI is beneficial to achieve a larger influence spread.

E. Empirical Study
In this study, we have recruited five classes for promoting courses by viral marketing to evaluate the effectiveness of Dysim in real-world settings. There were 30 elective courses for computer science college students, including artificial intelligence (AI), objective-oriented programming (OOP), and big data, to name a few. The goal of the campaigns is to encourage the students in Taiwan University to select those courses, i.e., maximizing the total number of students selecting the elective courses. The statistics of all classes are presented in Table III.
To construct KG of these courses, we crawled their syllabuses from Taiwan University, and extracted keywords of courses, related compulsory courses, and research fields of teachers. The meta-graphs were defined according to the curriculum guidelines in Taiwan. 38 Following [3], the costs of hiring users to promote courses are set as users' out-degree over their initial preferences for courses, since users who are more influential and who prefer the course less may need more incentive to be the seeds.
To evaluate the effectiveness of different approaches, we have launched campaigns based on the following approaches: 1) Dysim, 2) BGRD [38], 3) HAG [37], and 4) PS [35]. In this study, the budget and the number of promotions were set to 50 and 3, respectively. For Dysim, relevance measurement (including the learning of personal weightings on meta-graphs and the constructions of personal item networks), preference estimation, influence learning and item associations are learned and updated based on [10], [16], [48], and [16], respectively. TMI of Dysim follows [53] and [23] to cluster nominees and explore influenced users, respectively. Fig. 12 reports the total number of students selecting the elective courses for different approaches in each class. For all classes, Dysim induces the most students who selected those courses, followed by BGRD, HAG, and PS. These results validate that Dysim is able to encourage students to select those courses by carefully evaluating the dynamic changes in the relationships between courses. For instance, we observe that a student in Class A initially regarded the complementary relevance between AI and software design for cloud computing (SDCC) as 0.1. After he selected AI and big data, the complementary relevance between AI and SDCC increased to 0.6 (derived according to [10]). He then selected SDCC accordingly. In Class D, another student initially reported that the influence from one of her classmates is 0.2. During the promotions, both of them selected cloud computing and IoT, which increased the classmate's influence to this student to 0.7 (derived according to [48]). Then, this student selected big data after being informed that the classmate selected big data as well. By contrast, BGRD, HAG, and PS do not capture the dynamic changes in the relationships between courses and the ripple effect, resulting in fewer students selecting the elective courses in the end.
Besides, although BGRD is able to select influential students in each class, all courses are promoted as a bundle without considering their relationships. For example, in Class B, BGRD selects a student to promote python and C++ 38 https://cirn.moe.edu.tw/Upload/file/32077/83646.pdf.      in a bundle, but the two courses were usually regarded as substitutable for most students (i.e., the average substitutable relevance between python and C++ was 0.7). We observe that more than two-thirds of the students who selected python did not select C++ when they were promoted C++ by their classmates. Similar to BGRD, HAG does not examine the substitutable relationship when promoting courses. In Class B, HAG also promoted OOP and C++ to the same set of students. However, more than half of the students selected only one of OOP and C++, indicating the waste of simultaneous promotions for substitutable items. PS induces the fewest students to select the elective courses, since it does not facilitate students to promote multiple courses and cannot properly utilize the course promotion from other seeds. For example, in Class C, PS selected a student to promote deep learning (DL) to a set of students who were very interested in DL (i.e., their average initial preference for DL was 0.9). As DL and natural language processing (NLP) were regarded as highly complementary for this set of students (i.e., the average complementary relevance between DL and NLP was 0.75), a good strategy is to let the students selected by PS to promote NLP as well. However, PS did not promote any other course to this set of students in Class C. The above results lead to conclusions consistent with the experiments in Sec. VI-B, indicating that exploring the dynamic personal perceptions of item relationships, dynamic preference for items, dynamic social influence strength, and item associations is the cornerstone of influence maximization under a sequence of promotions on relevant items.

F. Case Study
From the experiments, we find several interesting cases in Amazon and study them in detail as follows.
1) For b = 500 and T = 20, we find that User #277 inclines to adopt items with greater importance via item associations. She is promoted and adopts a cinema camera Canon EOS C500 and two of its lenses in the 5th, 6th, and 9th promotions, respectively. Then, in the 13th promotion, if she is promoted a camera Premier DS-3081S, she adopts another camera Canon EOS M via item associations (instead of Premier DS-3081S) with a very high probability. We observe that the average substitutable relevance between Premier DS-3081S and Canon EOS M is increased from 0.7 to 0.93 if she adopts the two lenses in separate promotions after adopting Canon EOS C500, since she may regard the lenses with similar functions as substitutable. Her perception of the substitutable relationship triggers the adoption of a more expensive camera Canon EOS M, as cameras are high-end items, and users usually adopt only one among the substitutable items. The changes in perceptions facilitating item associations indeed lead to larger importanceaware influence in subsequent promotions.
2) For b = 200, User #16900 has different purchase decisions between settings T = 1 and T = 10. We observe that her preferences for Kindle and Kindle Unlimited service are 0.61 and 0.32, respectively, before any promotion. For T = 1, she usually adopts only Kindle if she is promoted both items at the same time. For T = 10, she is likely to be promoted and adopt Kindle in the 2nd promotion. We find that as Kindle and Kindle Unlimited service are complementary to each other, the adoption of Kindle increases her preference of Kindle Unlimited service to 0.58 on average. If she is then promoted Kindle Unlimited service in the 3rd promotion, she adopts it with a high probability. Exploiting the item relationships and the changes in personal preferences in multiple promotions is able to achieve more adoptions.
3) For b = 300 and T = 10, we find two different results when User #2236 promotes some item to User #186644. If User #2236 attempts to promote Kindle to User #186644 in the 2nd promotion, she probably fails. If both users adopt Garmin nuvi 50 promoted by their common friend in the 5th promotion, User #2236 is very likely to successfully promote Kindle Voyage to User #186644 in the 7th promotion. In the case that User #2236 and User #186644 both adopt Garmin nuvi 50 in the 5th promotion, they become more similar and socially closer accordingly. This makes the influence strength from User #2236 to User #186644 increased from 0.39 to 0.47 on average, which further helps User #2236 promote Kindle Voyage to User #186644 in the 7th promotion. Fig. 13 compares the importance-aware influence under different numbers of meta-graphs. With more meta-graphs, Dysim achieves larger importance-aware influence by better capturing users' perceptions, demonstrating the importance of modeling item relationships via KG and meta-graphs for a sequence of promotions. Fig. 14 shows the sensitivity to the threshold θ for identifying target markets with common users in TMI. A large θ slightly reduces the importance-aware influence since target markets may promote substitutable items to their common users. Nevertheless, a small θ also slightly deteriorates the performance because the promotional duration of a target market may be insufficient (when there are too many target markets in the same G) to foster the promotion of complementary items properly.

VII. CONCLUSION
To the best of our knowledge, this paper makes the first attempt to study the problem of influence maximization under a sequence of promotions for multiple relevant items. By exploring KG and meta-graphs to capture dynamic personal perceptions of item relationships, we formulate a new problem, named IMDPP, to choose items and select seed users for promotions at proper timings. We prove the hardness of IMDPP and design an approximation algorithm Dysim to solve IMDPP. Dysim first identifies nominees and target markets to promote complementary items to socially close users in consecutive promotions. For each target market, Dysim prioritizes the items to be promoted by dynamic reachability of items.
Then, Dysim determines proper promotional timings with the highest substantial influence for each nominee. Experiments on real social networks and KGs demonstrate that Dysim can effectively achieve up to 6.7 times of the influence spread. Furthermore, the empirical study validates that exploring the dynamic personal perceptions of item relationships, dynamic preference for items, dynamic social influence strength, and item associations is crucial for influence maximization under a sequence of promotions on relevant items.

ACKNOWLEDGEMENT
We thank to National Center for High-performance Computing (NCHC) of National Applied Research Laboratories (NARLabs) in Taiwan for providing computational and storage resources.