Motif-oriented influence maximization for viral marketing in large-scale social networks
Authors: Mingyang Zhou
Weiji Cao
Hao Liao
Rui Mao
Venue: NeurIPS 2024 poster (2024)
Keywords: influence maximization
influential node
viral marketing
Primary area: optimization

Abstract: The influence maximization (IM) problem aims to identify a budgeted set of nodes with the highest potential to influence the largest number of users in a cascade model, a key challenge in viral marketing. Traditional \emph{IM} approaches consider each user/node independently as a potential target customer. However, in many scenarios, the target customers comprise motifs, where activating only one or a few users within a motif is insufficient for effective viral marketing, which, nevertheless, receives little attention. For instance, if a motif of three friends planning to dine together, targeting all three simultaneously is crucial for a restaurant advertisement to succeed.
In this paper, we address the motif-oriented influence maximization problem under the linear threshold model. We prove that the motif-oriented IM problem is NP-hard and that the influence function is neither supermodular nor submodular, in contrast to the classical \emph{IM} setting.
To simplify the problem, we establish the submodular upper and lower bounds for the influence function. By leveraging the submodular property, we propose a natural greedy strategy that simultaneously maximizes both bounds. Our algorithm has an approximation ratio of  $\tau\cdot (1-1/e-\varepsilon)$ and a near-linear time complexity of $O((k+l)(m+\eta)\log \eta/\varepsilon^2)$.
Experimental results on diverse datasets confirm the effectiveness of our approach in motif maximization.

Motif-oriented influence maximization for viral marketing in large-scale social networks
Mingyang Zhou
Weiji Cao
Guangdong Province Key Laboratory of Popular High Performance Computers
College of Computer Science and Software Engineering Shenzhen University Shenzhen, China 51 8060 20201510628email] szu, edu cn
College of Computer Science and Software Engineering
Shenzhen University Shenzhen, China 518060 zmy@szu. edu. cn
Hao Liao*
Rui Mao
Guangdong Province Key Laboratory of Popular High Performance Computers College of Computer Science and Software Engineering Shenzhen University Shenzhen, China 518060 haoliao@szu. edu. cn
Guangdong Province Key Laboratory Popular High Performance Computers College of Computer Science and Software Engineering Shenzhen University Shenzhen, China 518060 mao8szu. edu. cn
Abstract
The influence maximization (IM) problem aims to identify budgeted set of nodes with the highest potential to influence the largest number of users in a cascade model, key challenge in viral marketing. Traditional IM approaches consider each user/node independently as potential target customer. However, many scenarios, the target customers comprise motifs, where activating only one or few users within a motif insufficient for effective viral marketing, which, nevertheless, receives little attention. For instance, if a motif of three friends planning to dine together, targeting all three simultaneously is crucial for a restaurant advertisement succeed. In this paper, address the motif-oriented influence maximization problem under the linear threshold model. We prove that the motif-oriented IM problem is NP-hard and that the influence function neither supermodular nor submodular, in contrast to the classical IM setting. To simplify the problem, we establish the submodular upper and lower bounds for the influence function. By leveraging the submodular property, we propose natural greedy strategy that simultaneously maximizes both bounds. Our algorithm has an approximation ratio of -1-11/e and near-linear time complexity of O(k +m log n)=²)) Experimental results on diverse datasets confirm the effectiveness of our approach in motif maximization.
Introduction
The utilization of "worrd-ofmouuth and "viral marketing" techniques has become prevalent in the promotion of new products. In social networks, "viral marketing" is implemented by selecting highly
"Corresponding author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

influential users as initial adopters 12.
The ultimate goal of this strategy is to trigger widespread adoption of products along social connections, i... "inffuence maximization (IM)" problem [3] IM serves as a key research problem in network analysis and has received significant attention due to its commercial applications 4
5 [ While most studies perceive each user as a potential target consumer, our paper aims to explore more general IM problem where the target consumers are represented as motif', each motif consisting of multiple users 7 g In this scenario, activating only one (or a few) users within motif may prove ineffective for viral marketing.
Consider the following scenario: A restaurant seeks to attract customers through viral marketing on social networks. In this scenario, a motif of k friends plans to dine together, and they have three different underlying mechanisms for choosing a restaurant: (a) One user already knows a restaurant and recommends it to others in the motif. Therefore, targeting only one user is sufficient for advertising the restaurant. (b) All users in the group must agree on the restaurant choice, requiring the advertisement to activate every member in the motif. (c) The decision is made through voting, with the restaurant chosen if more than half users the motif agree. To maximize restaurant profits, advertisements should target entire motif's rather than individual users in social networks. Similar situations arise in other group decision-making scenarios, such as anonymous voting, family parties, When it comes to viral marketing aimed at motif consumers, maximizing
and group tours [9 Jo the number of ultimate activated motifs is the explicit purpose for the IM, called motif-oriented IM.
The motif-oriented IM model differs from the classical IM in two key aspects: (a) A user can belong to multiple motifs and consume a product multiple times. (b) Activating the most users in the classical IM may only trigger few motifs, while activating most motifs might require fewer users than that of the classical IM. These factors present challenges in designing an effective strategy to determine the seed nodes. Note that some works investigate the group -orienrreeted IM (9. which is different from our motif-based IM. Motifs are the function units of a graph 7 S and users are mutually connected within a motif. Whereas users may be not connected (or partially reachable) in groups. In the paper, we provide an efficient solution for motif-based IM with a guaranteed approximation ratio.
This paper introduces an algorithm by optimizing the lower and upper bound of the oorif-orieened influence maximization (LBMOIM) to determine a budget set of seed nodes, aiming to maximize the number of activated motifs in social networks under the linear threshold model. In our model, each motif is associated with a threshold number r;, and if the number of activated nodes in the motif exceeds ri, the motif is called activated; otherwise, it remains inactive. Particularly, r; = (1, k. k/2} represents the three different restaurant determination scenarios introduced above. We define the target motif influence the count of activated motifs. We find that the influence function is monotone, but is neither submodular nor supermodular, making direct optimization challenging. To address this, we establish the lower and upper bounds for the influence function for different r;. The two bounds represent the weighted node-level influence function and both are monotone and submodular. We use greedy algorithm to optimize the two bounds simultancously to select the best seed nodes. Experiments in various datasets demonstrate the effecttivnness and efficiency of our algorithm. In addition, our study demonstrates that LBMOIM can be expanded to accommodate various diffusion models [. We introduce a modified version of LBMOIM for the independent cascade model. We provide evidence confirm the applicability of LBMOIM in different cascade models.
2 Related work
Node-level influence maximization. Kempe et al. 33 first introduced an algorithmic study on the IM problem, demonstrating its NP-hardness in general cases. They proposed greedy algorithm that can approximate an approximation ratio of 1/e with time complexity of (kmmmr). The major time-consuming step is the generation of Monte Carlo samples. To address this, various methods have been proposed to utilize reverse reachable (RR) sets rather than Monte Carlo simulation to reduce the time complexity without sacrificing the performance accuracy. These include the IMM [12] SSA [33. TIM [14) and OPTIM-C [15] techniques. More recently, Guo et al. [66] devised an efficient RR set generation approach that decreases the sampling time for each RR set. Hao et al. [17] propose a novel and effective framework for popularity maximization, designed to address the challenges of advertising competition. In the last few years, deep learning-based methods have emerged as alternative solutions. Fan et al. [18 introduced deep reinforcement learning framework that learns the graph representation and sequentially selects key nodes one at each step. Ling et al. 4 developed a novel framework to generate latent representations of node sets and determine the

---

best node set only in single step, in which the complex interactions among key nodes are encoded in the latent representations. Besides, there exist some other IM variants, such as time-critical IM
19, robustness IM 20 21], online IM [22] and so on 23 24
Group-level influence maximization. Group-level influence maximization is emerging field within social network analysis 22] II]. Groups refer to communities, cliques, and motifs, other kinds of subgraphs. The group-level influence maximization to pinpoint influential nodes capable of triggering the most groups. Zhu et al.
9 26 27 have introduced the problem aimed at selecting key nodes to maximize the number of activated groups. They have also proven the NP-hardness of this problem and provided upper and lower bounds for the objective function. However, it is important to note that the lower bounds are dependent on the graph structure. Nguyen al. [28] have proposed a method for identifying key nodes that exert influence over the largest number of communities. Zhong et al. [29 30) have developed a heuristic approach to maximize the number of activated groups and have empirically demonstrated its effectiveness. Phuong et al. [3] (2) have minimized the cost of group influence maximization in social networks. However, we still lack an effective method to guarantee the approximation ratio of motif influence maximization.
Our study draws parallels with the group influence optimization in references and 31 However, our work stands out from prior studies through the following innovative contributions: (a) We first propose the motif-oriented influence maximization under the linear threshold model and explore the unique properties of this problem, which differ from traditional groups in graph. (b) We propose both upper and lower bounds for the motif-orienter objective function. The two bounds share the same formalisms and can be optimized simultaneously. unlike previous solutions of group-oriented IM where the two bounds are different and cannot achieve the optimal solution simultaneously. (c) In contrast to previous heuristic approaches that cannot guarantee performance, we present a rapid algorithm that guarantees an approximation ratio. Therefore, our paper provides a viable approach to maximize motif-oriented influence in large graphs.
3 Problem definition
Let G (V, E) be a directed graph with n nodes and m edges, where node v E V represents a user and edge (u, v) E E represents the connection between users. (u, v) E means that there is a directed edge from node u to v. Each edge (u, v) E E is associated with a weight p(u, v). Given a subset of nodes S E V. denoted as initial activated seeds, we consider the following cascade process that allows for both the Linear Threshold (LT) and Independent Cascade (IC) models:
Initially, all nodes in set S are activated and the other nodes are inactive.
At each time step. when a node is activated, it has the opportunity to activate its out-neighbors in the following time step: Each node can activate its neightess only once; Once node is activated, it will remain active in the subsequent time steps.
The cascade process terminates when there are no further nodes that can be activated.
Let lc(S) be the number of activated nodes for an instance C' of the above cascade process C on condition that S is the initial seed node set. We denote (S) = (S)) as the expected influence of S under C. The traditional IM aims to find the best S to maximize (S). Here, we use motifs as the targeted customers for advertisements. We define a motif as a strongly connected subgraph:
Definition 1(Motif definition). Given a subset of nodes y in a graph, if there exist mutual paths between any pair of nodes in g, such that the paths only traverse the nodes within g, we denote y as motif(strongly connected group).
Roughly speaking, motif refers small, strongly connected set of nodes, distinct from the strongly connected giant component of a graph. Motifs are commonly regarded as the fundamental functional units within graphs, a concept widely studied in the field of network science [? g]. In order to facilitate group prcision-makingg it is essential that nodes within a motif have mutual accessibilityy ie., strongly connected. This requirement aligns well with various real-life scenarios. Establishing an acquaintance chain becomes indispensable to coordinate the activity occurring within the group.
Let g {91, .o...,..... 9h} be the targeted motifs set. Let (u()) = 1()) denote whether node is activated or not and ((gh,r;) = 1()) denote whether motif g; activated or not. Specifically, u(g.,T)) r.) = 1 indicates that there are more than r; activated nodes within motif gi (i.e., the motif
3

---

is activated), while p(g.. = O indicates that the number of activated nodes in motif 9i is less than rg- Now, let's define 1g (S) as the number of activated motifs resulting from an instance C, given that S represents the initial seed nodes, 1 (S) >i= p(g..:)). In viral marketing, motifss of different sizes bring about different profits, hence a general motif-oriented influence function is the weighted number of activated motifs, (S) = Ei=1 Wi r:), where wy 2 is the weight of motif i. Additionally, we denote (S) = ( as the expected weighted influence of seed nodes S under the cascade process C. Hence the problem in the paper is formalized as:
Problem Definition I(Motif-oriented influence maximization). Given a graph G, a cascade model C, and an integer k, the Ooiin-Oriented Influence Maximization (MOIM) asks for a size-k seed set with the largest expected activated motifs, i.e.,
S = sigg
Cascade Models: Our paper primarily focuses on the analysis of the LT model. The LT model requires that En p(u, v) S 1. In the LTT model, each node is associated with a uniformly random threshold A E 00, 1]. When node is inactive at time 1, it will become active at time / + 1 on condition that LnEA. p(u, w) u(()) 2 A.. where A. represents the activated in- nn-neigh node v. Notably, findings are not limited to the LT model and can be extended to the IC model and the triggering model, which will be discussed in Section 5,
Complexity analysis of MOIM
Theorem 1.
The MOIM problem is NP-hard for the linear threshold model.
Given that the classical IM problem can be treated as a particular case of MOIM where each motif consists of single node, since the classical IM problem is NP-hard [3] MOIM is also an NP-hard problem. Strict proof details are shown in the appendix C. O
Proof.
Theorem 2. The MOIM problem is neither submodular nor supermodular.
Proof. We present two illustrative examples demonstrate the non-submodular and non-supermodular properties. The submodular property states that the marginal gain of adding a node to a set of more seed nodes should decrease. More formally, for any two sets of nodes S, TSS C TT), and node v(v & 7), the inequality Lo(SU (v)) - Lc(S) 2 U {u}) - Lc(T") should hold.
Case I: We consider a graph with four nodes and target motif shown in Fig. Ta). When the seed nodes are S = {1} (or {2})) the expected activated motif is Ic() = p(1 - p). On the other hand, when the seed nodes are T {1, 2}. the expected activated motif is Ic
(T) (T) = 2p(1 p) + (1 p
As + O, we observe that ( U {1}) - (o) = Ic(Si)= < [c((1,2)) - Ic(())). Consequently, the MOIM model fails satisfy the submodular property.
Case 2:
We examine the MOIM problem under the specific scenario where a node represents a motif. In this case, the MOIM problem is degenerated into the classical IM problem. Notably, the marginal gain of seed nodes in the IM problem satisfies the submodular property. However, as a result this reduction, the general MOIM model no longer adheres to the supermodular property. Combining the two cases, arrive the theorem.
The proposed solution
5.1 The upper and lower bounds of the objective function
Given that the objective function of (S)) does not exhibit submodular or supermodular properties, feasible approach is to optimize the upper and lower bounds of (S), i.e., the sandwich strategy. The central issue of the sandwich strategy is to obtain the upper and lower bounds. Thus, in the subsequent sections, consider two cases and derive the upper and lower bounds of (SS)
Case (r; = 1): We first consider the IM example in Fig. a and the scenario where = 1, 1,2, h. this case, a motif will be activated if at least one node within the motif is activated. To account for this, we introduce a super node for each motif, as shown in Fig, [b). Every node within

---

motif is then connected to its corresponding super node with an activation probability of 1 in Fig. [b). The activation the super node follows the independent cascade model, meaning that the super node is activated if at least one node within the motif is activated. Let ' represent the set
1-p
p
1-p
(a)
(b) r=1
(c) r-6
Figure 1: (a) An example of graph containing only one motif. Nodes and 2 are the candidate seed nodes. (b) A super node example(labcled for motif, which connects to two nodes labeled and 4.
(c) 5-spanning tree example (see blue edges).
of super nodes, [T] = and define f(S) Ec|E.er wap(a)] as the expected number of activated super nodes weighted by the respective weights w!; given the initially activated seeds S (S T). The expectation of activated motifs can then be represented as (c) = f(S).
1, the MOIM problem can be reformulated as the modified IM problem, which seeks to determine the optimal seed set for maximizing the activation of the designated super node set T. Besides, one node may connect equal or more than two supper nodes.
Remark 1. When
Case 2 (r: > 1): We divide the cascade process into two stages for the convenience of analysis: Given a motif gs, the cascade first occurs along the edges outside the motif gi, and then the cascade occurs between nodes within the motif Jt Let Pout (S, .i. A) be the joint distribution of the activated node subset (A S Ge, A * 0) the cascade stage. In the first stage, when the number of activated nodes |A| is less than r., in order to ensure the activation of motif g., there must be at least r; |A] active edges connecting the activated nodes A and the inactive nodes in gi A.
We define a "semi d- d-spanning tree starting from node set A" as subset of edges within the motif Ii that connect nodes in A and other nodes in 9i without forming any cycles, denoted as (A))). Fig. [ee) illustrates an example of a semi 5-spanning tree starting from the node set A {7}. Let (A)) = [f,,,) (A)) p(u, v), and P (A)) represents the realization probability that the edges in set (A) are concurrently activated in the cascade. If (x(A) empty, we then set P( P(Fa((A) 1. Let P( (()()) min represent the minimal value of ((Fa(A)) for semi d-spanning tree in the motif g:- The activation probability of motif gi is given by:
Pr[u(g,, r²) 1|]
Σ
Pour (S, 9,, A) P(Ea(A))
AØ0 2.0dd12r--1
2 Σ Σ
Pout (S,gi, A). P(F)()) mmin-
1& d,d2r:
Since A 9 and d < r; - 1, we have P(E Omin 2 P(E))- Additionally, it is worth noting that Pr[u(g;,1) 1) = EayD (S, Di, A) represents the probability that at least one node in motif gi is activated by the outside nodes of gi. Thus, we have:
Prlu(gr.)) = 112 Σ Σ
Po gi, A) P(E
A d,d2n-1Al
2 P(E( ( man Pr(a(g,, =
Recalling that J(S) = Er (a)(aa) represents the expected number of activated super nodes weighted by the weights w. i = 1,,,
...,.., h. let w/ w; w.-P(( ) = min{P(Ef (P(E mmn.
1, h,,, h). (S) EclEner w()( and (S) f(S). we have the following theorem:
5

---

Theorem 3(Upper and lower bounds). f(S) is the upper bound of [S); (S) and f, (S) are
f((S)
Iwo lower bounds of (S)) (S) - [ (S) S Le (S) f(S). Besides, [ = T f(S).
Proof: Since Pr(u(gr.re)) I Prlu(g,, 1)] and wy E [0. 1], Ic)(S) Ec wiHlgs r:)] 1
Ec Di wiplgs, 1)] f(S). Hence, f(S) the upper bound of (S).
Based on Eq. 3 Ic (S) = Ec wa r:)] 2 E. wi (P(P m-mi Pr|u(g;, = 11) 2
(5) 2 Σ, ( - Pr Prijug 1) = 11) = (S)
5.2 The proposed algorithm LBMOIM
is noticed that f( (8)), and (S) share the similar formalism. In the section, we focus on optimizing ((S) to calculate the best seeds, which is also capable for (S) and (
Node selection based on RR set: In Algorithm 1, we determine the optimal seeds by optimizing the upper and lower bounds. Initially, certain number 0 of RR sets are generated (lines 2-6), followed by the standard greedy algorithm to generate a set S of size-k nodes that covers the maximum number of RR sets in R (lines 7-10). The method is similar to the node-level IM solution (see Appendix A). The only difference is the probability of choosing root nodes in the generation of RR set. The key problem of Algorithm is determining the number 8. Let R denote the set of all RR sets generated by randomly selecting a super node v with a probability of Me,, where 17 = E, wy. Let (R(S) be the fraction of RR sets in R covered by S. We have the following lemma:
Lemma 1. Assume that 0 follows
2 (8 + 22)n log 17 + log (2) + log2
(4)
OPT g²
Then, for any size-k set of seeds, the following inequality holds with at least probability n/ (2)
In PR(S) [(S) 2 OPT,
(5)
2
where OPT means the best-activated motif expectation of size-k seeds.
Proof: Comparing to Eq. 7 the only difference is replacing n by 17 Eq. because we have n weighted target motifs in our task. Since the modification doesn't 't influence the proof derivation in reference [14), please see reference [14] for the details.
Theorem 4 [14]. Given 0 that satisfies Eq. Algorithm returns a (1 1/e e) approxxmmaee solution with at least probability 1 1-7
Proof: Please see reference
for the details. D
Parameter estimation: The major problem lies in the prior evaluation OPT. To differentiate it from classical IM, we denote the optimal value as OPT; = maz (fS), we evaluate the parameters 0 and OPTy. We generalize the estimation of OPT in TIM [4] to weighted influence function to estimate lower bound of OPT;. denoted as PT (see Algorithm 3 in appendix B). We could estimate KPT in Algorithm 3 KPT [KP4/4, OPTj) with probability of at least 1 n and expected time complexity of ( + nogg)) (see the proof in appendix B).
k]. In this part,
We present Algorithm 2, which optimizes the Lower Bound of MOIM objective function (LBMOIM) to calculate the best nodes. In Algorithm 2, we initially assess the value of 0 (lines 1-2) and subsequently compute the best nodes (line 3). Optimizing the lower bound (S) also is equivalent to the optimization of the upper bound f(S), and hence we do not differentiate them and omit them.
Lemma 2(time complexity). The time complexity of Algorithm 2 is O((k + (m + v) log n/e?).
Proof: Please see the appendix C for the proof details. D
Lemma 3( Approximatiinn confidence). In Algorithm the St (etpeeee))--pppiiiiii solution with probability of at least 1 - 17
Proof: Given that the objective function f(S) is weighted version the IM problem that satisfies the submodular property, the greedy algorithm is capable of producing (1 - 1/e -)-approximate

---

Algorithm 1: NodeSelection (G)
Initialize node set St 0:
for i 1: 0 do
Randomly choose a super node e with probability ";;
Generate RR set R2 starting from node !:; Insert R2 to R.
eend
for i 1: do
Identify the node e that maximizes the marginal coverage of R, FR(S; (b}) - FR((S)) Insert into 5
10 end return St
solution for the submodular function. Additionally, by combining Eq. with Theorem 4, can deduce the probability of at least 1 - 1) 2
Lemma AApprooiiattinn ratio). Let S be the optimal solution that maximizes ( and S be the solution returned by Algorithm 2 that maximizes f(S). Algorithm achieves an approximation
f(8") (5*) N (1 1/e- =).
ratio 7
Proof: Based on Theorem 3, we have T f(S*) (S) < f(S*). Furthermore, based on Lemma
3, S* can achieve a (1 1/e =) approximation ratio. Therefore, can deduce that IL. (S*) s
f(3') f(S*) $ f(5*)/(1 - 1/e e). The approximation ratio y = [31 2 F(5-)/
r-f(S")
T. -1-- 0
Algorithm 2: (LaMMOM))ummarrzzttoon (G, k).
KPT KplEEstimaaion k)
Hog (2) +o)g
0 = (8 + 2)))n KPT-
S = SedeeSelection(..66
return S"
Improved MOIM solution: In the optimization, we only optimize F(S) (f,(S), For the optimiza-
tion of (S), we could use Algorithms 1-3 calculate the best node set that maximizes f (8) with minor modification: replacing w; and 17 E; w, with w/ and r/' = Σ, w in Algorithms 1-3. Suppose that Si and St are the returns of Algorithm 3 and correspond to the best S, (S) and (5).. Let S* argmax (f(S)S [ E ( We bear the conception that S performs better(at least equal to) S Besides, calculating S has the same time complexity and approximation ratio, which omitted due to space limitation.
Remark 2: Our algorithm could also be generalized to the independent cascade (IC) model and triggering model
3 Please see Appendix D for the generalization.
Experiments
6.1 Experimental setup
Datasets. We use five real social networks in Table our experiments. All datasets are available in KonectCollection!] H
Baseline methods.
We perform a comparative analysis of our proposed method against five existing
algorithms: STGM00201 [4]. OPIM (15), DeepIM/CML202 [4]. GIMTCSS200 CSS2019 9.. and GIA CC2023
TIM, OPIM, and IMM are among the most advanced techniques in the
hatp://koneet..c/eewwwks/

---

Table 1: Dataset characteristics.
Name
1
m
Type directed
Average degree
Flickr
2M
33.1M
28.8
Amazon
334K
925.8K
undirected
5.5
Catster
623
14.0M
undirected
44.9
Youtube
1M
3.0M
undirected
5.3
Douban
154K
327.2K
undirected
4.2
node-level IM problem, with high approximation ratio (1 1/c c). On the other hand, GIM and GIA are specifically designed to address the MOIM problem under the IC model. While GIM and EGI achieve similar approximation ratio (1 fe- 5) in terms of the objective functions, the objective functions are slightly different from the targeted influence function.
Parameter Settings. For our method, we set the default parameters as follows: E = 0.3, / - 1. w, by default. We randomly choose 2000 strongly connected subgraphs as target motifs with motif size being 3 unless otherwise stated. As for the other methods, we have employed the recommended parameters from their original references. Two cascade models, namely the LTT and IC models, have been considered. To ensure reliability, each method has been executed 10 times, and the average results have been reported. Furthermore, we have estimated the expected influence of any given seed set S by averaging the results from 100 independent cascade simulations. Our experiments run on computer with one i7 CPU, 32GB memory and C++ development environment. The code is available at https::/anonymous44orse
Evaluation metrics. The primary criterion for evaluation is the motif influence function Ic and larger Ilc (S) is better. The second metric is the time cost. The secondary criterion pertains to the time incurred during the process. In the case where different methods exhibit identical Ic(S) values, the preference is given to the method with smaller time cost.
6.2 Experiment results
we present the performance of the motif influence function under the LTT model. The figure shows that our method LBMOIM surpasses existing methods across various graphs. Additionally, comparing node-level methods (TIM+, OPIM, DeepIM) with motif- targeted methods (GIM, GIA, LBMOIM), we find that the latter outperforms the former due to a slight difference in the target objective function. Notably, for our method LBMOIM, we use simplified objective function that ensures both the approximation ratio and submodular property, resulting the consider the scenario of triangle subgraphs motifs and setting 7; = 1. Fig. shows the number of activated triangle motifs with a motif size of 3 and r, 1. Once again, the results reaffirm the superiority of our method, aligning with the findings from Fig. 2 Additionally, we compare the number of activated motifs performance at r; = 2 in Fig. 3 in Fig. (b). In Fig. 4c), we activate half of the motifs r; 2 and the other half at r; = 3. In this scenario, we optimize the lower bound and upper bound of the motif influence function. Considering only motif size 3, f, (S) degenerates into (S). and therefore, we do not differentiate between the two lower bounds. Fig. 4 further confirms that method outperforms existing methods.
Results under the ITT model: In Fig. 2
best performance (Fig. 2). Furthermore,
a and
In Figs. 2 and 3 we have investigated the performance under different motif size. We have also performed the case with a larger motif size. The results show that the performances of all methods deteriorate with the increase of the motif size. However, method still achieves the best performance. Since the results are similar to Figs. and 3 we omit them due to space limitation.
Results under the IC model: Our proposed method can be extended to the IC model and triggering model. Fig. [5] illustrates the motif coverage performance under the IC model. Specifically, we consider threesome motifs and set values equal to 1, 2, and 3 using the Douban dataset. Fig. 5 clearly demonstrates that our method consistently outperforms existing methods. to note that the GIA method exhibits similar performance to our method in Fig. (b)). However, worth mentioning that GIA lacks an approximation ratio guarantee, resulting in fluctuating performance shown in Figs. 5 a) and ((c). Furthermore, it is important to highlight that node-level
important
8

---

[a]
(b)
08.
0.4
0..
0.6
0.6
0.2
044
100
200
50
100
50
100
Figure 2: Expected motif influence k under LT model, and motif size being 2. (a) Flickr. (b) Amazon. (c) Catster. (d) Youtube. Larger is better.
(a
[b)
0.6 [c)
06 (d)
0.4.
0.2-
100
200
150
200
30
100
150
200
50
k
Figure 3: Expected motif influence It under LT model, 1 and motif size being 3. (a) Flickr.
(b) Amazon. (c) Catster. (d) Youtube. Larger is better.
DeepiM
GIA
LBMOIM(OUrS)
(a)
(c)
0.06
0.06
(,55)
0.04
0.04
0.00
0.00
0.00
0
50
100
150
200
50
100
150
200
50
100
150
200
k
Figure 4: Expected motif influence vs. k under model. (a) Flickr. Motif size is and r; = (b) Amazon. Motif size is and r, 3. (c) Catster. Half motifs have size 2 and other half motifs have size 3 and r; = 3. Larger is better.
2, whereas the
DeepiM
GIM
LBMOIM(ourS)
0.3
(a)
(b)
(c)
0.04
(i)))
0.4
0.2.
0.02
0.0
0.0
0.00
50
100
150
200
50
300
150
200
50
100
150
200
k
k
Figure 5: Expected motif influence vs. under IC model in Douban dataset,
1 and motif size
being (a) r; (b) 2. (c) r
Larger is better.
GIM
GIA
LBMOMMMOUS)
a8]
bb)
10'
50
100
150
200
50
100
150
200
50
100
150
200
50
100
150
200
under LT model, r; and motif size being (a) Flickr. (b) Amazon. (c) Catster. (d) Youtube. Smaller is better.
Figure 6: (a) Expected time consumption

---

methods such as TIM+, OPIM, and DeepIM, which have different target objective functions, also cannot achieve the best performance under the IC model.
Results of time consumption: The time consumption of different approaches is compared in Fig. [ Specifically, the comparison focuses GIM, GIA, and LBMOIM, these methods exclusively optimize motif' coverage. GIM exhibits the highest time consumption due to the need to optimize two node-level objective functions, in contrast the other two methods which only optimizes a single objective function. Importantly it should be noted that the time consumption of our proposed method exhibits a minor increase with respect to demonstrating its scalability when applied to large graphs. This observation aligns with the time complexity analysis in Lemma 2.
7 Conclusion
In this paper, we have addressed the motif-oriented influence maximization (MOIM) problem. To tackle the non-supermodular and non -ubmmuuoo MOIM objective function, we have derived simplified submodular upper and lower bounds that make the problem more tractable. We further propose an efficient algorithm capable of optimizing these bounds. The algorithm runs in expected time of O(k (m + 77) log logn/ n/==) and achieves an approximation ratio of T (1 1/e E). We experimentally evaluate our method against the state-of-the-art methods on large real-world social networks using the LT and IC models. Our results consistently demonstrate that our method outperforms ofhe-of-the-art methods in terms of both motif influence and computational efficiency. These findings highlight the potential value of motif-oriented approaches in viral marketing and social influence scenarios.
In future work, we plan delve deeper into the intricate structural properties of the motif influence function, aiming to uncover new insights into its mathematical behavior and relationships. This includes exploring more refined and tighter bounds that can guide the development of algorithms with improved performance guarantees. Additionally, we intend to extend our investigation to handle more complex motifs across diverse and heterogeneous network structures, where interactions are dynamic or context-dependent.
8
Acknowledgments
The authors thank Dr. Wei Chen for his invaluable guidance and insightful discussions, and the anony- mous reviewers for their constructive feedback and insightful comments. The authors acknowledge the financial support from the National Natural Science Foundation of China (Grant Nos. 62476173, 62276171, 62002233, 61972145), the Shenzhen Fundamental Serearcch-Gnners Project (Grant Nos. JCYJ202408 42261001, JCYJ202408 110440811141100000 311500005, JCYJ202208 155803001), Guangdong Ba- sic and Applied Basic Research Foundation (Grant Nos. 2024A151500 1938 and 2020B 15001511 1A00B1111110000
Guangdong Peral River Recruitment Program Talents (Grant Nos. 20192T08X603), Hao Liao
the corresponding author.
References
[1] Yuchen Li, Ju Fan, Yanhao Wang, and Kian-Lee Tan. Influence maximization on social graphs: A survey.
IEEE Transactions on Knowledge and Data Engineering, 1852)) 2018.
[2] Wei Chen, Chi Wang, and Yajun Wang- Scalable influence maximization for prevalent viral marketing in large-scale social networks. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1029- 1038, 2010.
[3] David Kempe, Jon Kleinberg, and Êva Tardos. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137-146, 2003.
[4] Chen Ling, Junji Jiang. Junxiang Wang, My T Thai, Renhao Xue, James Song, Meikang Qiu, and Liang Zhao. Deep graph representation leaming and optimization for influence maximization. In International Conference on Machine Learning, pages 31350-21361. PMLR, 2023.
[5] Yushun Dong, Jing Ma. Song Wang, Chen Chen, and Jundong Li. Fairness in graph mining: A survey. IEEE Transactions Knowledge and Data Engineering, 2023.
10

---

[6] Rakesh R Mallipeddi. Subodha Kumar, Chelliah Sriskandarajah, and Yunxia Zhu. A framework for analyzing influencer marketing in social networks: selection and scheduling of influencers. Management Science, 68(1):75-104, 2022.
[7] Pedro Ribeiro, Pedro Paredes, Miguel EP Silva, David Aparicio, and Fernando Silva. A survey on subgraph counting: concepts, algorithms, and applications to network motifs and graphlets. ACM Computing Surveys (CSUR), 54(2):1-36, 2021.
[8] Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. Network motifs: simple building blocks of complex networks. Science, 298(5594):824-82 2002.
[9] Jianming Zhu, Smita Ghosh, Weili Wu. Group influence maximization problem in social networks. IEEE Transactions on Computational Social Systems, 6(6): 155-1 164, 2019.
[10] Diego García-Zamora, Álvaro Labella, Weiping Ding, Rosa M Rodríguez. and Luis Martínez. Large-scale group decision making: a systematic review and a critical analysis. IEEF/CAA Journal of Automatica Sinica, 9(6):99--966 2022.
[11] Mchdi Azaouzi, Wassim Mnasri, and Lotfi Ben Romdhane. New trends in influence maximization models. Computer Science Review, 40:100393, 2021.
[12] Youze Tang, Yanchen Shi, Xiaokui Xiao. Influence maximization in near-linear time: A martingale approach. In Proceedings of the 2015 ACM SIGMOD international conference on management of data, pages 1539-1554, 2015.
[13] Hung T Nguyen, My T Thai, and Thang N Dinh. Stop-and-stare: Optimal sampling algorithms for viral marketing billion-scale networks. In Proceedings of the 2016 international conference management of data, pages 695-710 710, 2016.
[14] Youze Tang, Xiaokui Xiao, and Yanchen Shi. Influence maximization: Near-optimal time complexity meets practical efficiency. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data, pages 75- 16-86.22 2014.
[15] Jing Tang, Xueyan Tang, Xiaokui Xiao, and Junsong Yuan. Online processing algorithms for influence maximization. In Proceedings of the 2018 International Conference on Management of Data, pages 991-1005, 2018
[16] Qintian Guo, Sibo Wang, Zhewei Wei, and Ming Chen. Influence maximization revisited: Efficient reverse reachable set generation with bound tightened. In Proceedings of the 2020 ACM SIGMOD international conference management of data, pages 2167-2181, 2020.
[17] Hao Liao, Sheng Bi, Jiao Wu, Wei Zhang. Mingyang Zhou, Rui Mao, and Wei Chen. Popularity ratio maximization: Surpassing competitors through influence propagation. Proc. ACM Manag. Data, 1(2), June 2023.
[18] Changjun Fan, Li Zeng, Yizhou Sun, and Yang- Liu. Finding key players in complex networks through deep reinforcement learning. Nature machine intelligence, 216):317-324, 2020.
[19] Wei Chen, Wei Lu, and Ning Zhang. aine-critical influence maximization in social networks with time- delayed diffusion process. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 26, pages 598. 2012.
[20] Meghna Lowalekar, Pradeep Varakantham, and Akshat Kumar. Robust influence maximization. 2016.
[21] Wei Chen, Tian Lin, Zihan Tan, Mingfei Zhao, and Xuren Zhou. Robust influence maximization. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 795-804, 2016.
[22] Shuai Li, Fang Kong, Kejie Tang, Qizhi Li, and Wei Chen. Online influence maximization under linear threshold model. Advances in Neural Information Processing Systems, 33:1 192-1204, 2020.
[23] Suman Banerjee, Mamata Jenamani, and Dilip Kumar Pratihar. A survey on influence maximization in social network. Knowledge and Information Systems, 62:3417-3455, 2020.
[24] Yandi Li, Haobo Gao, Yunxuan Gao, Jianxiong Guo, and Weili Wu. A survey on influence maximization: From an based combinatorial optimization. ACM Transactions on Knowledge Discovery from Data, 17(9):1550 2023.

---

[25] Alessia Antelmi, Gennaro Cordasco. Carmine Spagnuolo, and Przemyslaw Szufel. Social influence maximization in hypergraphs. Entropy, 23(7):796, 2021.
[26] Jianming Zhu, Junlei Zhu, Smita Ghosh, Weili Wu, and Jing Yuan. Social influence maximization in hypergraph in social networks. IEEE Transactions Nenwork Science and Engineering. 6(4):801-811, 811, 2018.
[27] Jianming Zhu, Smita Ghosh, Weili Wu, and Chuangen Gao. Non-submodular model for group profit maximization problem in social networks. Computational Social Networks, 8(1):118, 2021.
[28] Lan Nguyen, Kunxiao Zhou, and My T Thai. Influence maximization community level: A new challenge with non-submodularity. 2019 JEEE 39th International Conference on Distributed Computing Systems (ICDCS), pages 327-337. IEEE, 2019.
[29] Yuting Zhong, Longkun Guo, Peihuang Huang. Maximizing group coverage in social networks. In 21st International Conference on Parallel and Distributed Computing, Applications and Technologies, pages 274-284. Springer, 2021.
[30] Yuting Zhong and Longkun Guo. Group influence maximization in social networks. In International Conference on Computational Data and Social Networks, pages 152-163 Springer, 2020.
[31] Phuong NH Pham, Canh V Pham, Hieu V Duong. Václav Snášel, and Nguyen Trung Thanh. Minimizing cost for influencing target groups in social network: A model and algorithmic approach. Computer Communications, 212:182 11:2:22-111) 2023.
[32] Phuong NH Pham, Canh V Pham, Hieu V Duong, Trung Thanh Nguyen, and My T Thai. Groups influence with minimum cost in social networks. In Computational Data and Social Networks: 10th International Conference, CSoNet 2021, Virtual Event, November 15-17, 2021, Proceedings 10, pages 231-22 231-242. Springer. 2021.
[33] Christian Borgs, Michael Brautbar, Jennifer Chayes, and Brendan Lucier. Maximizing social influence in nearly optimal time. In Proceedings of the twenty-fifth annual ACM-SIAM sympositm on Discrete algorithms, pages 946-957. SIAM, 2014.
12

---

A Existing node-level IM
Most existing scalable IM solutions consist of two phases:
Sampling. This phase iteratively generates certain number of random reverse reachable(RR) sets R,, denoted as R {R R2, ..., Ra)
Node selection. This phase utilizes the standard greedy algorithm to derive size-k node set St that covers the most number of RR sets in R. The St is the output of the best node seeds.
In the sampling phase, an RR set is constructed through two steps: Firstly, the direction of each edge in E' is reversed. Secondly, a node v is randomly selected from V, and an instance the cascade is obtained by setting as the initial activated node using the cascade model C. The resulting set of activated nodes is denoted as an RR set. The RR set exhibits the following desirable properties:
Lemma 5 33 Consider a seed set S and a randomly generated RR set R2 under the diffusion model C. The expected influence (c)) can be expressed as:
(c(S)
Pr(S R, 0).
(6)
Borgs et al. two phases. Tang al. (14) introduce improved algorithm called TIM, which has time complexity of ((k + (n + m) log n/²2). TIM estimates A as follows:
3
initially examine the efficiency of the greedy algorithm based on the aforementioned
log + log (*) + log2
0 z (8 + 22)n
OPT
where and OPT represent factor coefficient and the best influence of size-k node set, respectively, Let (5) denote the fraction of RR sets in R covered by S. Eq. 7 guaranttess probability of at least 1 - n//(") that the inequality holds:
& OPT. 2
nn (R( - Ic(S)
(8)
The lower bound of OPT is estimated based on the expected influence of size-k random node seeds. In addition, Tang et al. [2] further minimize the number of RR sets. Nguyen et al. [33] propose SSA and D-SSA to select seeds in the node selection phase, followed by the usage of a validation method to verify the performance of the selected seeds.
B Parameter estimation of OPT;
In this part, we evaluate the parameters and OPTy. Evaluating OPT; directly is computationally expensive when only limited number of RR sets are generated. Instead, calculate lower bound. Initially, we randomly sample i nodes as initially activated seeds, ensuring that any duplicates are removed. The probability of choosing node v is proportional to its in-degree within graph G. By generating a sample of l nodes, we can estimate the expected spread, denoted as KT,, which serves the lower bound for OPT;, PT OPT₁. Let R denote the set of all RR sets generated by randomly selecting a super node v with a probability of Wi. 7) Let EN be the expected number of coin flips required to generate a random RR set. We have the following lemma:
Lemma 6. IL EN [E]((")]. where the expectation of f(u*) is taken over the randomness of vt and the cascade process.
Proof: Let R be a RR set by randomly selecting a super node with probability of Pn be the probability that randomly selected edge from G points to node in R. Then EN Eppn m]. where the expectation is taken over the random choices of R.
Let v² be random node that is sampled with probability proportional to its in-degree within graph G. and 6(x*, Rt) be a boolean function that returns if v* E R, and 0 otherwise. Then, for a fixed R. we have
PR = Σ (Pr[u*] b(ux, R)).
(9)
13

---

The probability that seed node v* activates a randomly selected super node is
Pu Σ
[(Pr[R) b(e", R)).
(10)
Hence, we have Esp--] [[ J)1/n and
EN/m
Elpal
Σ
[Pr(R) PR)
R
[(Pr(R] E(Pr(o") b(v", R)))
R
[PProo'] E(rr(R] b(,",R) R))
(1I)
E(Proo' Pe.)
Epp Elf((r))\/n
which completes the proof.
0
Lemma represents the generation complexity RR sets, which is degenerated into the TIM solution
14 when wi = 1, Vjj = 1, 2, h in the classical IM problem.
We then define the width of an RR set RG denoted as ((R,). be the number of directed edges in graph G that point to the nodes within Rg. Mathematically, this is expressed as:
(B)) = Σ (the indegree of v).
(12)
=E
Lemma 7. Let Ry be a random RR set starting from a random super node v. The selection of the super node u is based the probability Kis We define x(R) as follows:
"
w R
K R =1 - 1
(13)
Then, KPT 17. Es E4 []] where the expectation is taken over the random choices of R.
Proof: Let S be random of nodes sampled based their in-degree in G. excluding duplicates. Let R2 be a random RR set starting from super node v, and an, be the probability of overlap between S and Rg. The K PT can be expressed
KPT = Es E We Pr(u(v) = 1]] E.
ES My [aRR.] 4
(14)
Consider that we sample l times uniformly from the edges in G. Let E be the set of sampled edges without duplicates. Let a'R, represent the probability that one of the edges in E* points node in R. can be observed that a'R, an. Given that there are (RR) edges pointing to nodes in R. we have a'R. (1 5 (R)/m) = x(R.). Hence, the KPT can be further simplified as:
KPT = 11 Es [E [R'R,.] 1) Es E wy [n(Rn)]]
(15)
which completes the proof.
Based on Lemma 7, we present an efficient approach for evaluating KPT in Algorithm 2: We first generate e; RR sets (lines 5-6) and accumulate the corresponding ((..)) (lines 7-8), and then evaluate the quality of the estimated K KPT* (lines 10-12). If the estimated PTT is less than threshold, we repeat the process (lines 1-13). Algorithm runs in most log, 7 iterations. Next, we analyze the time complexity of Algorithm 2.
Theorem 5. For 1) 2 2 and 2 1/2, Algorithm 2 returns result KPT* E |KPT/4, with probability of at least -l. Furthermore, the algorithm runs the expected time complexity of OlI(m + 1))log))
14

---

Algorithm 3: KptEstimation (G,
for i 1: log2 1) do
Let c; = (6l log 1 + 6 log(log2 11) 2"; 2
Let swn = 0:
for -= do
Randomly choose super node with probability ";; Generate random RR set Rg-
x(R)) 1 (1 =(m) )+;
sum = sum + n² R(Ro): end
10
if sum/c; C > 1/22 then
11
return KPT -sum/ (2c;;
12
end
13 end
return KPT*
Proof: Reference 14] has proved that for v) 2 2 and > 1/2, Algorithm 2 returns a result KPT E [KPT/4 OPTy with a probability of at least 1 1- The remaining problem is the time complexity, because the generation of RR sets slightly different from the TIM method (14).
2- the expected total number RR sets generated by Algorithm 2 is less than 2cz+2 ((2illog 7) [4] We have
Suppose that KPT/n n [2 1-,,2-5+11
O(2e)+2 EN) = 0 log EN)
0222 log 1 (1 + m) KPT)
(16)
0222l n (1 + m). 2-))
O((( m) log
which completes the proof. D
C Other Proofs
Proof of Theorem Consider an instance of the NP-complete problem of Vertex Cover in an undirected graph G (V, E). Given an integer k, the goal is to determine whether there exists set of size l in V such that every edge in has at least one endpoint S. We then show that the Vertex Cover problem is a specific instance of the MOIM problem.
To establish this connection, we define motif consisting of pair of adjacent nodes, and hence two adjacent nodes form a motif. We treat a motif is activated if all nodes in the motif are activated. If there exists vertex cover of size k; it guarantees that every edge has at least endpoint in S, enabling the activation of all nodes in V using the linear threshold cascade model. This is the only way that corresponds to get set S with (e(S)) = m. where m denotes the number of activated motifs(i.e., the number of edges). Consequently, an instance of NP-complete Vertex Cover problem can be viewed as a specific case of the MOIM problem, which arrives at Theorem O
Proof of Lemma 5: In Theorem 5, the function EstEmmatttion costs expected time O + 7))ogr). The time complexity of function Node in Algorithm is 0 EN). Based on Theorem 5, we have
O EN) = O((8 + 2s)) llog 17 + log
( + log2 EN
2
OPT
O((8 25)n llog + log (2)
+ log2
m)
(17)
2²
O((k () + 1)) log n/E2),
which completes the proof. D
15

---

D Generalization to other cascade models
We mainly discuss the generalization to the independent cascade (IC) model and triggering model 3], since the two models are widely used in the IM problem.
In the IC model, when node is first activated at time t, for each directed edge (u, v) from node to v, u has a probability p(u, v) to activate at time t + 1. After time I + 1, cannot activate any node. In the triggering model, for each node u, we take sample from its in-neighbors based some prior distribution and define the sample as the triggering set of u. In the cascade process, when a node is activated time I, if appears in the triggering of v, v will be activated at time / 1. Note that the IC model and LT model are two particular cases of triggering model.
In our algorithms and the analysis, we do not rely anything specific to the LT model. The only difference is the generation of random RR sets. Reference [14] analyzed the complexity of generating RR sets of the three models. Though the three models(LT, IC, and triggering models) have slightly different processes to generate the RR sets, the time complexity of generating RR set is almost the same. Hence, our method could be generalized to the IC model and triggering model. A similar generalization in the classical IM has been shown in ref. [14], and our method follows almost the same procedure to be extended IC and triggering models.
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction of the paper have stated the claims made, highlighted the contributions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Our method has two tunable parameters. We have discussion the limitation in the part of Parameter determination the end of section 4.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
17

---

Answer:
[Yes]
Justification:
We have provided detailed proofs for all theorems and lemmas.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We have provided the pscudocode and the detailed analysis of our algorithm in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
18

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We use open data (Konect Data Collection, http:///oneet..c//etwwkkk// and have released the code on the anonymous website:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
public/guides/ Soaalees//CooSSuuubsisiiiiiii
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ https/cccccuclccuuueeeeeeeeeeeee Coaee///ddeSebmmmcma ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We have provided all the settings in section 4.3 and section 5.1.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Our algorithm generates deterministic results. Hence, we don't 't require to evaluate the error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
19

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We have discussed the computer resources at the beginning of section 5.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Our research agrees with the ethics requirements.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We have discussed the societal impacts in the introduction.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
20

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We have properly cited the assets used in the paper.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
21

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
22


Reviews:
[{"review_id": "rATQDedSHT", "reviewer": "Reviewer_zfSx", "summary": "This paper proposes the motif-oriented influence maximization problem based on the traditional influence maximization problem. This paper proves that the problem is NP-hard and proposes a new method, LBMOIM, based on upper and lower bounds to solve it. The experimental results demonstrate that LBMOIM can achieve effective expected motif influence across multiple datasets.", "questions": "* Considering the dynamism of real-world networks, can you provide more justifications that motifs are defined reasonably in actual scenarios?\n* Can the authors explain why, in Figure 6, even though there is a significant difference in the size of the Flickr and Amazon datasets, the runtime appears to be on the same order of magnitude?", "limitations": "The authors' discussion of the limitations is not particularly clear. It seems that the authors should consider more how to ensure the expected motifs actually exist in real-world social networks.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper investigates motif-oriented influence maximization, a new perspective in the field of influence maximization, which typically focuses on individual nodes rather than motifs.\n\n2. This paper provides a rigorous analysis of the motif-oriented IM problem.\n\n3. According to the experiments, the proposed LBMOIM method is both effective and computationally efficient in solving the motif influence maximization problem compared to existing methods.", "weaknesses": "1. The paper is filled with numerous symbols and proofs. Adding intuitive explanations for the proofs can help readers better understand the content.\n2. One major concern is the motivation of this paper. In the Section of Introduction, the example of restaurant is not convincing, as the group decision may influenced by many factors.The assumptions made for motif activation may not always align with real-world dynamics. \n3. There are no data observations or analyses to illustrate the motivation of this work. The rationality of the motif-oritented IM is not justified. It seems that this paper highly relies on some assumptions. \n4. The investigated problem still seems limited to a few fixed propagation models, the results and the effectiveness of the method are tightly coupled with the assumptions of these models. However, real-world propagation patterns are much more complex than these fixed models. \n5. How to set the hyperparameter is not introduced. There is also no ablation study.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1**: The paper is filled with numerous symbols… Adding intuitive explanations …\n\n**Reply**: Thank you for your feedback. To improve the readability and flow of the main text, we will move the detailed proofs of the upper and lower bounds (currently on Page 4) to the supplementary material in the final version. Additionally, we will provide more detailed explanatory examples for Figure 1 to help readers clarify the concepts. Furthermore, we will introduce a case study related to Figure 1 before the method section to better understand the problem.\n\n**Q2**: One major concern is the motivation of this paper...\n\n**Reply**: We agree that group decisions can be significantly influenced by various factors. We note that most previous works about influence maximization also had no real data. To further illustrate the motivation, we provide two additional examples: \n\n(a) The advertisement of the ‘KFC Family Bucket’ in the online social network: When determining whether to purchase a KFC Family Bucket, every family member must consent to consume KFC. \n\n(b) Farmigo platform (https://www.farmigo.com/): It offers subscription services for group customers when a specific number of members in the group purchase the foods, which can reduce the average delivery cost. \n\nWe recognize that the assumptions made for motif activation may not always align perfectly with real-world dynamics, and obtaining real-world data is challenging due to privacy concerns and commercial interests. We acknowledge this as a limitation of our research. However, our work represents one of the first systematic explorations of this problem. We will explicitly clarify this limitation in the final version.\n\n**Q3**: There are no data observations or analyses to illustrate the motivation of this work. The rationality of the motif-oriented IM is not justified…\n\n**Reply**: The motif-oriented influence maximization is prevalent in real-world scenarios, such as the advertisement for \"KFC Family Bucket\" and group tours. However, due to commercial interests and privacy security concerns, we cannot obtain the real data associated with group decision-making processes. We note that most previous works about influence maximization problem also have no real data (e.g., refs. [1-3]). We plan to clarify the limitation as suggested.\n\n[1] C. Ling, J. Jiang, J. Wang, M. et al., Deep graph representation learning and optimization for influence maximization, ICML, 2023.\n\n[2] H. Liao, S. Bi, J. Wu, et al., Popularity Ratio Maximization: Surpassing Competitors through Influence Propagation, SIGMOD, 2023.\n\n[3] Q. Guo, S. Wang, Z. Wei, et al., Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened, SIGMOD, 2020.\n\n**Q4**: The investigated problem still seems limited to a few fixed propagation models…\n\n**Reply**: Our propagation models are extensively utilized in the simulation of cascade dynamics and viral marketing within social networks. For more complex scenarios, we could modify eqs. 2-3 to handle more complex propagation models. We have already generalized our model to accommodate more intricate triggering mechanisms (see Appendix D). In the final version, we will also include a discussion on the generalization and limitations of applying more complex spreading models.\n\n**Q5**:  How to set the hyperparameter is not introduced. There is also no ablation study.\n\n**Reply**: Our method has parameter $r_i$ that has been investigated in Fig. 5. There are no other hyperparameters that need to be trained. Hence, we omit the ablation study.\n\n**Q6**:  … can you provide more justifications that motifs are defined reasonably in actual scenarios?\n\n**Reply**: We introduce a novel case study of the \"KFC Family Bucket\" advertisement on online social networks. In this scenario, all members of the family (or a motif) must agree to purchase the KFC Family Bucket. See the response of Q2 for other cases.\n\nIn actual scenarios, motifs represent the function units of complex graphs, which have been well investigated in the field of network science. For example, in the paper \" Network motifs: simple building blocks of complex networks, Science, 2002”, the authors examined motifs with various shapes, including loops, chains, bi-fans, and triangles, among others. To illustrate, a chain motif $x-y-z$ signifies a path from node $x$ to its 2-length neighbor $z$. A triangle motif denotes a group of fully connected three nodes, such as three close friends. Our definition of motif agrees with previous research. Hence, we could ensure the expected motifs actually exist in real social networks.\n\nWe will discuss more justifications of motifs as suggested in the final version.\n\n**Q7**:  Can the authors explain why, in Figure 6, even though there is a significant difference in the size of the Flickr and Amazon datasets, the runtime appears to be on the same order of magnitude?\n\n**Reply**: The runtime of our algorithm is mainly influenced by the number of targeted motifs rather than the number of nodes in the network. Given that we have set the number of targeted motifs to 2000 for all graphs, the runtime remains within the same order of magnitude, regardless of the differences in dataset size, which is consistent with our theoretical analysis. We will provide further clarification on this matter in the revised version.\n\n\n**Q8**: The authors' discussion of the limitations is not particularly clear. It seems that the authors should consider more how to ensure the expected motifs actually exist in real-world social networks.\n\n**Reply**: Motifs serve as functional units within complex graphs, a concept extensively explored in the domain of network science, which exists in various real-world social networks. The time complexity of our method depends much on the number of motifs. If a small graph has a large number of motifs, the time consumption is also high. We will discuss the limitations as suggested in the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "V9E1ajK7n8", "reviewer": "Reviewer_hHht", "summary": "The paper on motif-oriented influence maximization for viral marketing in large-scale social networks introduces a novel approach that focuses on targeting motifs - strongly connected subgraphs of users - to maximize influence (i.e., targeting motifs rather than individual users for viral marketing campaigns). It formulates the motif-oriented influence maximization problem under the linear threshold model in social networks. The proposed algorithm provides a systematic approach to maximize influence within strongly connected subgraphs by simultaneously optimizing the lower and upper bounds to select the best seed nodes for maximizing motif-oriented influence. The influence function is neither submodular nor supermodular, making direct optimization challenging. The paper establishes lower and upper bounds for the influence function based on thresholds  (where the threshold signifies the activated vertices in the motif).", "questions": "1) See the Weakness section\n\n2) Can the term motif defined in the paper be interpreted as a maximal strongly connected component induced by the vertices in $g_i$ (as no other path exists between the vertices in $g_i$)?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1) It is interesting that the upper and lower bounds have similar formalism ( I haven't seen this in influence maximization approaches). \n\n2) A thorough analysis of Motif based influence maximization is provided in the paper.", "weaknesses": "1) The term \"Motif\" in Network Analysis is traditionally defined as recurrent sub-patterns in the graph. It is better to stay consistent with the literature to avoid confusion for some readers.   \n\n2) Group-level influence maximization was performed earlier for independent cascade models (Motifs can be considered as specialized groups), so the problem setting is not entirely novel.    \n Here are a few other related references apart from the ones already cited in the paper: \n       1) Zhu, J., Ghosh, S., Wu, W. and Gao, C., 2019, November. Profit maximization under group influence model in social networks. In International conference on computational data and social networks (pp. 108-119). \n\nMinor comments: It is better to have the abstract and parts of the text self-contained where the relevant terms in approximation ratio and time complexity are well defined.\n\nThis paper can be strengthened by adapting it to dynamic networks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1**: The term \"Motif\" in Network Analysis is traditionally defined as recurrent sub-patterns in the graph. It is better to stay consistent with the literature to avoid confusion for some readers.\n\n**Reply**: Thank you for your valuable feedback. The term \"motif\" is commonly employed in the analysis of graph functions, for example,\n\n[1] Ribeiro P, Paredes P, Silva M E P, et al. A survey on subgraph counting: concepts, algorithms, and applications to network motifs and graphlets[J]. ACM Computing Surveys (CSUR), 2021.\n\n[2] Chia X W, Tan J K, Ang L F, et al. Emergence of cortical network motifs for short-term memory during learning. Nature Communications, 2023.\n\n[3] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, \"Network motifs: simple building blocks of complex networks,\" Science, 2002.\n\nWhile the term \"motif\" shares some similarities with recurrent sub-patterns within a graph, it possesses specific characteristics that distinguish it from traditional sub-patterns, i.e., strong connectivity. We will provide further clarification on this matter in the final version.\n\n**Q2**: Group-level influence maximization was performed earlier for independent cascade models (Motifs can be considered as specialized groups), so the problem setting is not entirely novel. Here are a few other related references apart from the ones already cited in the paper: 1) Zhu, J., Ghosh, S., Wu, W. and Gao, C., 2019, November. Profit maximization under group influence model in social networks. In International conference on computational data and social networks (pp. 108-119).\n\n**Reply**: We acknowledge that the exploration of group-level influence maximization has been a subject of previous research, and we have indeed addressed the distinctions in our discussion of related work. The referenced paper introduced a heuristic greedy approach, which, in its generalization as presented in reference [7], diverges from our methodology in several critical respects:\n\n(a) The definition of motifs as strongly connected subgraphs contrasts with the concept of groups that do not necessitate such connectivity.\n\n(b) In group-level influence maximization, the emphasis is typically on optimizing a surrogate objective function and providing an approximation ratio for the surrogate objective, rather than guaranteeing an approximation ratio for the original objective.\n\n(c) Our algorithm offers a strict approximation ratio for the original objective function, distinguishing it from the referenced approach. \n\n(d) Our method allows for the simultaneous optimization of upper and lower bounds that share a common formalism.\n\n**Q2**: Can the term motif defined in the paper be interpreted as a maximal strongly connected component induced by the vertices in $g_i$ (as no other path exists between the vertices in  $g_i$)?\n\n**Reply**: A motif refers to a small, strongly connected set of nodes, distinct from the strongly connected giant component within $g_i$. Motifs are commonly regarded as the fundamental functional units within graphs, a concept widely studied in the field of network science, as exemplified by:\n\n[1] Chia X W, Tan J K, Ang L F, et al. Emergence of cortical network motifs for short-term memory during learning. Nature Communications, 2023.\n\n[2] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, \"Network motifs: simple building blocks of complex networks,\" Science, 2002.\n\nWe will provide more background and discussion about the definition of motif as suggested in the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6UtYIi08VS", "reviewer": "Reviewer_3uSV", "summary": "The paper proposes a novel approach to influence maximization (IM) by targeting motifs—interconnected subgraphs of nodes—instead of individual nodes. The authors propose the motif-oriented influence maximization (MOIM) model under the linear threshold (LT) and independent cascade (IC) models. They demonstrate the NP-hardness and non-submodular nature of the problem and develop submodular upper and lower bounds for the influence function. The proposed greedy algorithm achieves a (1 - 1/e - ε) approximation ratio and near-linear time complexity. Extensive experiments validate the algorithm's effectiveness and efficiency across various datasets, showing superior performance compared to existing methods.", "questions": "For the 𝑟=1 case, the problem is actually submodular and can be solved using classic influence maximization algorithms by simply adding additional nodes. Why is there still a significant performance gap, given that the proposed algorithm is supposed to solve this problem exactly? Can you provide more insights or explanations for this discrepancy?", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper introduces a novel approach by shifting the focus from individual nodes to motifs in the context of influence maximization. This new perspective addresses real-world scenarios where group decisions are crucial, adding significant value to the field of viral marketing.\n2. The paper is well-written, with a clear problem definition, detailed methodology, and rigorous theoretical derivations. The logical flow and thorough explanations make the contributions easy to understand and appreciate.\n3. The method's support for multiple classical diffusion models, including the linear threshold (LT) and independent cascade (IC) models, enhances its versatility and applicability in various real-world scenarios.", "weaknesses": "1. The paper lacks an approximation hardness result, which is important for understanding the limits of the proposed algorithm's performance. Additionally, the NP-hardness of the problem is derived straightforwardly from traditional influence maximization, offering little new insight into the complexity specific to motif-oriented influence maximization.\n2. The approximation rate is not graph-independent and can deteriorate exponentially with the size of the motif. Additionally, it would be beneficial to include experiments demonstrating how performance changes with increasing motif size, providing deeper insights into the algorithm's scalability and effectiveness in varied settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1**: The paper lacks an approximation hardness result, which is important for understanding the limits of the proposed algorithm's performance. Additionally, the NP-hardness of the problem is derived straightforwardly from traditional influence maximization, offering little new insight into the complexity specific to motif-oriented influence maximization.\n\n**Reply**: Thanks for the comment. We will relocate certain less critical sections, such as the discussion on NP-hardness, to the Appendix part. Additionally, we have expanded our discussion on the approximation hardness result. Our proposed algorithm achieves an approximation ratio of $\\tau\\cdot (1-1/e-\\varepsilon)$, as detailed in Lemma 4.\n\n**Q2**: The approximation rate is not graph-independent and can deteriorate exponentially with the size of the motif. Additionally, it would be beneficial to include experiments demonstrating how performance changes with increasing motif size, providing deeper insights into the algorithm's scalability and effectiveness in varied settings.\n\n**Reply**: We appreciate the suggestion regarding the influence of motif size on our results. To address this point, we have conducted additional experiments to explore the effect of motif size on our findings (see Figure 1 in the global Author Rebuttal and Table R1). Table R1 presents the expected motifs as a function of motif size under the LT model in the Amazon graph. The result indicates that as the motif size increases, the expected number of activated motifs also increases. However, theoretical analysis reveals that the approximation rate degrades exponentially with the motif size. On one hand, given that real-world graphs are typically heterogeneous, with central nodes having a higher probability of occurrence in larger motifs. On the other hand, the central nodes have a higher likelihood of being activated in information cascades. Consequently, we observe a trend where larger motif sizes correspond to higher expected numbers of activated motifs. Therefore, our approach remains effective for analyzing large motif sizes in real-world scenarios. We will provide further clarification on this matter in the final version of our manuscript.\n\nTable R1: The expected motif influence vs. motif size $\\|g_i\\|$ under LT model in Amazon graph. We set $r_i = 3$ and the initial seeds $|S|=100$, meaning that a motif is activated if more than three nodes in the motif are activated. Larger is better.\n\n\n| $\\|g_i\\|$ |   3   |   4   |   5   |   6   |   7   |   8   |   9   |   10   |\n|:---------:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|\n|     $I_c^g(S)$      | 0.344 | 0.268 | 0.242 | 0.248 | 0.266 | 0.287 | 0.308 | 0.616 |\n\n\n**Q3**: For the 𝑟=1 case, the problem is actually submodular and can be solved using classic influence maximization algorithms by simply adding additional nodes. Why is there still a significant performance gap, given that the proposed algorithm is supposed to solve this problem exactly? Can you provide more insights or explanations for this discrepancy?\n\n**Reply**: Thank you for your insightful comment. When $𝑟=1$, the problem is degenerated into the classical influence maximization problem. However, the focus here is on activating motifs, which are not uniformly distributed in the graphs. It is possible that certain central nodes may serve as members of multiple motifs. Given that the traditional influence maximization approach primarily seeks to activate the maximum number of nodes rather than motifs, there persists a significant performance gap.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PZ8nsWxQ2K", "reviewer": "Reviewer_MwLB", "summary": "The paper introduces a motif-oriented influence maximization (MOIM) problem under the linear threshold model, where motifs, rather than individual nodes, are the primary targets for viral marketing. The authors propose an algorithm to optimize the influence function by establishing submodular upper and lower bounds. The proposed approach aims to maximize the number of activated motifs, with experiments conducted on various datasets to validate its effectiveness.", "questions": "1.Why was there no comparison of the time required for different algorithms such as TIM+, OPIM, and DeepIM?", "limitations": "Clarify Motif Definition: Provide a clearer rationale for defining motifs as strongly connected groups. This could include theoretical advantages or references to other studies that have used a similar definition.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.Novel Problem Definition: The paper addresses a less explored area in influence maximization by focusing on motifs instead of individual nodes, adding a new dimension to the problem.\n2.Algorithmic Contribution: The proposed algorithm leverages submodular properties to provide an approximation solution with a guaranteed ratio, which is a significant contribution to the field.", "weaknesses": "1.Unclear Motif Definition Rationale: The primary issue with the paper is the rationale behind defining a motif as a strongly connected group. The authors do not provide sufficient justification for this choice, and it is unclear if other works have adopted a similar definition.\n\n2. Minor Writing Issue: There is a minor writing issue on line 189 where the text appears to be out of sequence.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1**: Unclear Motif Definition Rationale: The primary issue with the paper is the rationale behind defining a motif as a strongly connected group. The authors do not provide sufficient justification for this choice, and it is unclear if other works have adopted a similar definition.\n\nLimitations: Clarify Motif Definition: Provide a clearer rationale for defining motifs as strongly connected groups. This could include theoretical advantages or references to other studies that have used a similar definition.\n\n\n**Reply**: Thank you for your comments. Motifs represent the basic functional units of graphs and have been well-investigated in the field of network science, for example, \n\n[1] Ribeiro P, Paredes P, Silva M E P, et al. A survey on subgraph counting: concepts, algorithms, and applications to network motifs and graphlets. ACM Computing Surveys (CSUR), 2021.\n\n[2] Chia X W, Tan J K, Ang L F, et al. Emergence of cortical network motifs for short-term memory during learning. Nature Communications, 2023.\n\n[3] Losapio G, Schöb C, Staniczenko P P A, et al. Network motifs involving both competition and facilitation predict biodiversity in alpine plant communities. Proceedings of the National Academy of Sciences, 2021.\n\n[4] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, \"Network motifs: simple building blocks of complex networks,\" Science, 2002.\n\nIn the field of network science, motifs are typically strongly connected. We are the first to investigate the motif-oriented influence maximization problem. In the final version, we will provide a detailed justification of the motif definition as suggested.\n\n\n**Q2**: Minor Writing Issue: There is a minor writing issue on line 189 where the text appears to be out of sequence.\n\n**Reply**: The issue is attributed to the insufficient margin space surrounding Figure 1. We plan to address this template issue in the final version.\n\n**Q3**: Why was there no comparison of the time required for different algorithms such as TIM+, OPIM, and DeepIM?\n\n**Reply**: Thank you for your feedback. It is important to note that TIM+, OPIM, and DeepIM are specifically designed for node-level influence maximization and their time complexity is not directly related to the number of targeted motifs. In contrast, the time complexity of the other methods considered is directly dependent on the number of targeted motifs, and we could tune the number of targeted motifs to tune the time consumption of these methods. Therefore, a direct comparison of our method with TIM+, OPIM, and DeepIM in terms of time complexity is not appropriate.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
The appendix file includes a figure that shows the influence of motif size on the performance.

Meta-review: The paper introduces an approach to influence maximization that targets interconnected subgraph of nodes (aka motifs) instead of individual nodes as existing algorithms. All the reviewers were positive or mildly positive about the paper and I recommend accepting the paper. I ask the authors to address the reviewers' comments in the final version of their paper.
Decision: Accept (poster)