Applied Research Paper Track CIKM ’21, November 1–5, 2021, Virtual Event, Australia

Influence Maximization in Multi-Relational Social Networks

Wei Wang, Haili Yang, Yuanfu Lu∗ , Yuanhang Zou, Xu Zhang, Shuting Guo, Leyu Lin
WeChat Search Application Department, Tencent Inc. China
{unoywang,hailiyang,lucasyflu,yuanhangzou,xuonezhang,tinkleguo,goshawklin}@[Link]

ABSTRACT
Chatting
G
Influence maximization (IM) is a classic problem, which aims to find Honey 08:35
G
Morning
a set of 𝑘 users (called seed set) in a social network such that the
G
Work Group 08:05
expected number of users influenced by the seed users is maximized. [2 messages] Tom: Meeting at

Existing IM algorithms mainly focus on one-by-one influence diffu- (b-1) Four influenced users in
Lily Yesterday
a multi-relational social network
See tomorrow~
sion among users with friendships. However, in addition to 1-to-1
Shopping Yesterday G
friendships, 1-to-N group relations usually exist in real social plat-
forms, which are seldom fully exploited by conventional methods. Sisiter Saturday
G
G
In this paper, with the real-world datasets in WeChat, the largest
G
online social platform in China, we first study the IM problem
in multi-relational social networks consisting of friendships and G Group Relation
(b-2) Two influenced users in
Friendship a traditional social network
group relations, and propose a novel Generate&Extend framework
(a) (b) (c)
to find influential seed users for product promotion . Specifically, to
achieve a trade-off between effectiveness and efficiency, we present
a truncated meta-seed generator to select a small number of users, Figure 1: (a) An illustration of the chatting scenario on a
which are influential with consideration of both friendships and social platform (e.g., WeChat), where users can chat with
group relations. More importantly, a structural seed extender is friends and other users in the same group (maybe non-
put forward to extend the meta-seed set, so as to encode the dif- friends). (b) Comparison of influence spread on a multi-
ferentiated propagation structures between friendships and group relational social network and a conventional social network.
relations. Extensive online/offline experiments on three real-world (b-1) shows that the shaded user can influence 4 users via
datasets demonstrate that Generate&Extend significantly outper- friendships and group relations, while there are only 2
forms the state of the arts. Our Generate&Extend has been deployed reachable users in the conventional social network in (b-
at WeChat for mini-program promoting, and severing more than 2). (c) Influence diffusion analysis of a product in WeChat
200 million users. within one month. The numbers of friendships and group
relations indicate the number of edges involved in the shar-
ing process of the product, and the activated users represent
CCS CONCEPTS
users who use the shared product.
• Information systems → Mobile information processing sys-
tems; Data mining; • Social and professional topics → User
characteristics.

KEYWORDS 1 INTRODUCTION
social network analysis, influence maximization, social influence Online social networks (OSNs), such as Facebook with 1.5 billion
and WeChat with 1.2 billion monthly active users, have come to
ACM Reference Format:
Wei Wang, Haili Yang, Yuanfu Lu∗ , Yuanhang Zou, Xu Zhang, Shuting Guo,
play a vital role in numerous economical, social and political events
Leyu Lin. 2021. Influence Maximization in Multi-Relational Social Networks. [1, 43]. In online social networks, hundreds of millions of peo-
In Proceedings of the 30th ACM International Conference on Information ple actively interact with each other and share their opinions,
and Knowledge Management (CIKM ’21), November 1–5, 2021, Virtual Event, which makes a piece of information could quickly become perva-
QLD, Australia. ACM, New York, NY, USA, 10 pages. [Link] sive through the word-of-mouth propagation among social friends
3459637.3481928 [16, 24]. Thus, seeking the most influential users in an online social
network is practical and valuable for various applications, like prod-
∗ The corresponding author.
uct promotion and viral marketing [10, 25], which is well known
as influence maximization (IM) problem [11, 22].
Permission to make digital or hard copies of all or part of this work for personal or
classroom use is granted without fee provided that copies are not made or distributed Formally, given an online social network G, influence maximiza-
for profit or commercial advantage and that copies bear this notice and the full citation tion asks for 𝑘 users (a.k.a. seed set) in G that can influence the
on the first page. Copyrights for components of this work owned by others than ACM largest expected number of remaining users. The first seminal work
must be honored. Abstracting with credit is permitted. To copy otherwise, or republish,
to post on servers or to redistribute to lists, requires prior specific permission and/or a presented by Kempe et al. [18] formulates the influence maximiza-
fee. Request permissions from permissions@[Link]. tion as an optimization problem and shows that it is NP-hard in
CIKM ’21, November 1–5, 2021, Virtual Event, QLD, Australia general. Along this line of research, a large body of work on in-
© 2021 Association for Computing Machinery.
ACM ISBN 978-1-4503-8446-9/21/11. . . $15.00 fluence maximization has been done in the past decade, detailed
[Link] introductions can refer to [3, 6, 9–11, 18, 22, 22, 25, 27, 28, 34, 37, 38].

4193
Applied Research Paper Track CIKM ’21, November 1–5, 2021, Virtual Event, Australia

Although existing methods achieve either approximation guar- the reverse influence sampling [7] and the observations on real
antees or practical efficiency, they almost focus on influence dif- data of WeChat, the truncated meta-seed generator truncates the
fusion between friends. In the real-world online social network, reachable neighborhood structures, which serves for the selection
relations between two users are usually complex and diverse [32]. of a small number of influential users, i.e., meta-seed set. On the
For instance, Fig. 1(a) illustrates a multi-relational social net- other hand, we present a structural seed extender to cope with
work in WeChat, an online social platform serving more than 1 the different influence propagation structures of friendships and
billion users in China. Different from the conventional social net- group relations in the multi-relational social network. The struc-
work, the multi-relational social network consists of friendships tural seed extender first encodes the differentiated structures into
and group relations between users, where the friendship repre- low-dimensional representations, and then takes the meta-seed
sents that two users are in a 1-to-1 relation while the group relation set and the structure-embedded representations as input to extend
means that two users are in the same group (i.e., a 1-to-N relation) the meta seeds in terms of structural similarity. Finally, the pro-
with similar interests but not necessarily friends. Intuitively, in Fig. posed Generate&Extend framework derives a seed set for influence
1(b), the shaded user can reach two more users and propagate wider maximization in a multi-relational social network.
influence with 1-to-N group relations. Furthermore, in Fig. 1(c), in- To summarize, this work makes the following major contribu-
fluence diffusion analysis of one product in WeChat shows that tions.
much more group relations are involved in the influence diffusion
• To the best of our knowledge, this is the first attempt to investi-
process and most users are activated by group sharing. Thus, multi-
gate influence maximization in a multi-relational social network,
ple social relations may significantly change the influence diffusion
which not only contains 1-to-1 friendships, but more importantly
in an online social network, recasting the influence maximization
includes 1-to-N group relations.
problem in the need of considering not only 1-to-1 friendships but
• We conduct extensive analysis on real social influence diffusion
also 1-to-N group relations.
in WeChat for the first time, which motivates us to propose a
To seek the most influential users in a multi-relational social
novel Generate&Extend framework to find the most influential
network, one straightforward solution is to take all relations as
users in industrial scenarios.
friendships and then apply the state-of-the-art methods (e.g., SSA
• Our proposed Generate&Extend leverages a truncated meta-seed
[28] or OPIM [36]). However, this simple idea suffers from two
generator to select meta-seed users and a structural seed ex-
predominant problems: (1) 1-to-N group relations lead to a high-
tender to generate the final seed set with the consideration of
degree and large-scale social network, which makes traditional IM
differentiated friendships and group relation structures.
algorithms inefficient and even infeasible. As shown in Fig. 1(b),
• We conduct extensive empirical studies (including online and
the number of group relations is more than twice that of friend-
offline) on three real-world datasets in WeChat, and demonstrate
ships in the multi-relational social network of WeChat. Moreover,
that Generate&Extend consistently and significantly outperforms
in the multi-relational social network, a group usually comprises
various state of the arts.
of hundreds of members and a user could join various groups, thus
the degrees of nodes are much higher than that of nodes in a con-
ventional social network only consisting of 1-to-1 friendships. (2)
2 RELATED WORK
Influence diffusion in a multi-relational social network could be
significantly changed. The basic assumption of traditional IM al- Influence Maximization. Influence maximization is first mod-
gorithms is that the more people a user can reach, the larger the eled as an algorithmic problem in [18], which proposes a greedy
influence of the user. However, this could not be strictly held in a framework that returns (1 − 1/𝑒 − 𝜖)-approximation for several
multi-relational social network, since the 1-to-N group relations influence diffusion models. Subsequently, a plethora of greedy-
show significant different structures from the 1-to-1 friendships, based heuristics has been developed to achieve approximate solu-
For instance, a seed user who joins many groups can reach much tions in the literature [6, 22]. Broadly, based on how to evaluate
more people, but she/he always keeps silent and never share any the influence spread, existing IM algorithms can be classified into
content, which makes her/him a fake seed. simulation-based, proxy-based, and sketch-based approaches. The
The above issues trigger us to investigate the influence maxi- simulation-based algorithms perform Monte-Carlo (MC) simulation
mization problem in multi-relational social networks. Motivated for evaluating influence spread, which can incorporate differernt
by the extensive analysis of a multi-relational social network in diffusion models (e.g., IC [13] or LT [15]) and have a good theo-
WeChat, we propose a novel Generate&Extend framework. The retical property. However, the MC simulation incurs significant
basic idea of Generate&Extend is to first find a small set of seed computational overheads [14]. Instead of performing heavy MC
users, called meta-seed set, by constructing truncated reachable simulations, the proxy-based algorithms devise proxy models to
neighborhood sets, and then extend the meta-seed set through se- approximate influence spread, which makes it more practical and
lecting the structure similar users for influence maximization in the efficient on large-scale networks at the expense of theoretical guar-
multi-relational social network. More specifically, the proposed Gen- antees [11, 23]. To overcome the drawbacks of the aforementioned
erate&Extend consists of two components: truncated meta-seed algorithms, the sketch-based approaches construct theoretically
generator and structural seed extender. Towards a trade-off be- grounded sketches based on the diffusion model and then evaluate
tween effectiveness and efficiency, a truncated meta-seed generator influence spread via the constructed sketches, which ensures that
is put forward to address the large-scale and high-degree challenges the algorithm achieves theoretical efficiency while preserving the
proposed by the 1-to-N group relations. Taking inspiration from approximation guarantee [28, 37]. Besides, there exist some works

4194
Applied Research Paper Track CIKM ’21, November 1–5, 2021, Virtual Event, Australia

107
107
105 via Friendship via Friendships via Friendships
# Users sharing the product

# Users sharing the product

# Users sharing the product

via Group Relation
106
via Group Relations 106 via Group Relations
104 105 105

103 104 104

103 103
102
102 102
101
101 101

100 100 100

100 101 102 103 104 105 100 101 102 103 100 101 102 103 104
# Reachable users # Share times # Activated users
(a) Distribution of reachable users. (b) Distribution of share times. (c) Distribution of activated users.

Figure 2: Data observations of a multi-relational social network in WeChat.

that attempt to incorporate content information, such as location group relations with Tom and May. Intuitively, influence spreads in
and time [12, 21, 42]. a group is wider and quicker than that between 1-to-1 friendships.
Unfortunately, all the above-mentioned approaches are designed
for social networks with only simple 1-to-1 friendship structures, Definition 2. Influence Maximization in MRSNs. Given a MRSN
therefore they cannot be directly applied for influence maximiza- G = (V, E), a positive integer 1 ≤ 𝑘 ≤ |V | and a diffusion model
tion in multi-relational social networks that are ubiquitous in real M, IM aims to select a seed set S ∗ ⊂ V of 𝑘 users that maximizes
applications. In this paper, we firstly investigate both 1-to-1 friend- the influence propagation under the given diffusion model M, i.e.,
ships and 1-to-N group relations in social networks for influence the expected number of influenced users via both friendships and
maximization problem. group relations.
Social Influence Analysis. In recent decades, the booming of
various social platforms has promoted the research on social influ- 4 DATA OBSERVATIONS
ence analysis [34, 35]. For instance, Bakshy et al. [5] investigate In this section, we look into the unique characteristics of multi-
the attributes and relative influence of Twitter users by tracking relational social networks with a real-world dataset of WeChat1 ,
diffusion events that took place on the Twitter. Similarly, on Twitter and draw some observations motivating our proposed framework.
network, Azaza et al. [4] propose an influence assessment approach
for Twitter users by considering three actions: retweet, mention 4.1 Background
and reply. Moreover, [2] and [40] attempt to analyze how social WeChat is the largest online social communication service in China,
influence on Facebook affects the news we read and the product with more than 1.2 billion monthly active users (MAUs), where users
we purchase. While social influence analysis is much practical and are allowed to send and receive multimedia messages, articles and
valuable in real-world applications, few efforts has been made for mini-programs2 (i.e., “mini-applications” running within WeChat)
analyzing the influence of group relations in social networks, es- in real-time via Internet. One important feature in WeChat is that
pecially for IM problem. Thus, we make a preliminary attempt to users can not only chat with their friends but also with several
maximize influence in a multi-relational social network. other users in the same chat group at the same time. For example, a
user can share a mini-program to his/her friends or groups, and the
3 PRELIMINARIES persons who use the shared mini-program at the next moment are
In this section, we first present the formal definition of the multi- regarded as activated users. Thus, in WeChat, information can be
relational social network and then formalize the problem of influ- propagated one by one through friendships, and more importantly,
ence maximization in multi-relational social networks. can also be widely diffused among numerous users in a chat group
through group relations.
Definition 1. Multi-Relational Social Network (MRSN). A multi- It is worth mentioning that there also exist other applications like
relational social network is denoted as G = (V, E), consisting of WhatsApp3 and LINE4 that provide the similar chat group feature.
a user set V and a relation set E = E𝑆 ∪ E𝐺 . Here E𝑆 and E𝐺 Here we mainly study the influence diffusion in WeChat, and it
are the sets of 1-to-1 friendships and 1-to-N group relations is flexible to apply some conclusions and our Generate&Extend
between users. In fact, group relations formalize the social relations framework to their scenarios.
between two users, and two users connected via group relations
usually share similar interests.
1 [Link]
2 [Link]
Example 1. Fig. 1(a) shows the chatting scenario of a user in
guide/
WeChat, which derives a multi-relational social network. There are 3 [Link]

friendships between the user and Honey, Lily and Sisiter, as well as 4 [Link]

4195
Applied Research Paper Track CIKM ’21, November 1–5, 2021, Virtual Event, Australia

4.2 Data Observations encodes 1-to-1 and 1-to-N structures into low-dimensional repre-
The data for this study comes from anonymized logs of a mini- sentations with graph neural networks [17], and then extends the
program (i.e., the product to be promoted) sharing data in WeChat. seed users with similar structures.
We collect the sharing logs ranging from 2020/07/01 to 2020/07/31,
which derives a large scale multi-relational social network con- 5.2 Truncated Meta-seed Generator
sisting of 25.59 million nodes (i.e., user) and 1.8 billion edges (i.e., As motivated, towards handling the high-degree and large-scale
friendships and group relations). Note that we only have access MRSN caused by 1-to-N group relations, it is important to balance
to records of a share action but no detailed content due to user the effectiveness and efficiency of the seed selection. Given a MRSN
privacy. Here we conduct an analysis on the influence diffusion of G = (V, E), we take inspiration from [7] and define the truncated
the product (i.e., the mini-program) within one week, and showcase reachable set of source user 𝑣 as follows:
the results in Fig. 2. We have the following observations:
(1) More users can be reached through group relationships than T𝑣 = {𝑢 |𝑢 ∈ Nℎ (𝑣), 𝑣 ∈ V} ∪ {𝑣 }, (1)
through friendships. Fig. 2(a) presents the distribution of the number
where Nℎ (𝑣) is the ℎ-hop reachable neighbors of the user 𝑣 via
of reachable users w.r.t users sharing the product in our collected
friendships or/and group relations. For example, Fig. 3(a) shows
data. Overall, the number of users reachable via group relations
Í the 2-hop truncated reachable sets for read users. In essence, the
(i.e., for each group the user joins (#members in a group)) is larger than
truncated reachable set is a subgraph of the MRSN G, in which the
the number of users reachable via friendships (i.e., the number of
social influence is capable of spreading among each other.
friends). Only a few users can reach more users via friendships
Likewise, we can construct multiple truncated reachable sets
since they have many friends. It inspires us to incorporate not
as T = {T1, · · · , T𝑚 }. Intuitively, influential users are likely to
only 1-to-1 friendships but also 1-to-N group relations for influence
appear frequently in the truncated reachable sets. In other words, a
maximization problem.
user who cover most of the truncated reachable sets is likely to be
(2) Influence spread through group relations is much wider and
selected as a seed user and achieves the maximum influence. Thus,
more powerful than the influence spread through friendships. Ob-
we can select top-𝑘 0 seed users that cover the maximum number
serving from Fig. 2(b) and (c), we find that although users generally
of truncated reachable sets as
prefer to share the product through friendships, fewer sharing
𝑚
via group relations yields more activated users. This observation Õ
motivates us to carefully distinguish the influence diffusion of dif- S0 = Rank({𝑣 : min(|{𝑣 } ∩ T𝑖 |, 1)|𝑣 ∈ V}, 𝑘 0 ), (2)
𝑖=1
ferentiated relations in a multi-relational social network.
where S0 is the 𝑘 0 -size seed set, and Rank(𝑘𝑒𝑦 : 𝑣𝑎𝑙𝑢𝑒, 𝑘 0 ) is a
5 METHODOLOGY ranking function that outputs the top-𝑘 0 𝑘𝑒𝑦s based on the corre-
As motivated by the aforementioned data observations, we next sponding 𝑣𝑎𝑙𝑢𝑒s.
elaborate our key designs of the Generate&Extend framework, Until now, we can directly solve Eq. (2) based on the greedy
which effectively selects a small number of influential users as algorithm for max-coverage problem [20]. However, as mentioned
the meta-seed set and extends the meta-seeds with the consider- before, the 1-to-N group relations in a multi-relational social net-
ation of the differentiated diffusion structures of friendships and work make it inefficient and even impractical in the real application
group relations. scenario. Thus, we only generate a small number of users as a meta-
seed set S0 (i.e., 𝑘 0 is small), and then present a structural seed
extender to derive the final seed set that maximizes influence in a
5.1 Overview of Generate&Extend
multi-relational social network.
As illustrated in Fig. 3, the Generate&Extend framework consists
of two components: truncated meta-seed generator in Fig. 3(a) and
5.3 Structural Seed Extender
structural seed extender in Fig. 3(b).
First, existing IM algorithms mainly focus on social networks With the generated meta-seed set S0 , next we extend S0 to achieve
with only 1-to-1 friendships that are small and low-degree [19, 28]. the influence maximization in the multi-relational social network.
However, the 1-to-N group relations make the social network high- Relation-aware Structural Distance. As motivated, the ex-
degree and large-scale since a group usually contains hundreds of tended seed set is expected to be similar to the meta seeds in struc-
members. Thus, taking inspiration from reverse influence sampling tures, rather than in features, so as to avoid the influence overlap
(RIS) [7] for IM, we design a truncated meta-seed generator to problem [41]. However, there are significant differences in the prop-
select a small number of influential users as the meta-seed set, agation structures of friendships and group relations, as analysis in
which only takes ℎ-hop neighborhoods into consideration, so as to Fig. 1(b) and Section 4. Thus, it is necessary to differentiate 1-to-1
achieve a trade-off between effectiveness and efficiency for large- and 1-to-N relations in the measurement of the structural distance
scale networks. in the multi-relational social network.
Second, since the meta-seed users are generated with a limited Formally, given a multi-relational social network G = (V, E =
number for a large-scale network, it is crucial to extend the seed E𝑆 ∪ E𝐺 ), a meta-seed set S0 , we denote N𝑙𝑆 (·) and N𝑙𝐺 (·) as
users with the consideration of the significant different propagation the 𝑙-hop neighbors of nodes via friendships and group relations,
structures between 1-to-1 and 1-to-N relations. Thus, based on a respectively. In particular, based on the 𝑙-hop neighborhood struc-
relation-aware structure similarity, our structural seed extender tures (i.e., N𝑙𝑆 (·) and N𝑙𝐺 (·)), the relation-aware structural distance

4196
Applied Research Paper Track CIKM ’21, November 1–5, 2021, Virtual Event, Australia

Truncated Reachable Sets

common user source user meta-seed user

Meta-Seed Users
G

G G
G G
G …
G …
G

(a) Truncated Meta-seed Generator

G
G
G
G
G G Random
G Walk
G
G
…
G
G

…
Group Single G
Relation Relation

Meta-seed Extension
Relation-aware Structure-embedded Representation
Structure Distance
(b) Structural Seed Extender

Figure 3: Illustration of the proposed Generate&Extend framework. (a) Truncated meta-seed generator, which generates mul-
tiple truncated reachable sets given the source nodes (in grey), and selects a small set of influential users (in red) that cover
most truncated reachable sets as the meta-seed set. (b) Structural seed extender encodes different structures of friendships
and group relations into low-dimensional representations, which are fed to a cluster to gather users with structure similar to
the meta seeds as the final seed set.

between user 𝑢 and user 𝑣 is defined as follows: Intuitively, the above-defined hierarchical similarity determines
the similarity between users base on their neighborhood structures
D (𝑢, 𝑣, 𝑙) = 𝛼 ∗ 𝑑 (N𝑙𝑆 (𝑢), N𝑙𝑆 (𝑣)) (3)
on the bottom of the hierarchy, while the similarity depends on
+ (1 − 𝛼) ∗ 𝑑 (N𝑙𝐺 (𝑢), N𝑙𝐺 (𝑣)), the entire graph at the top of the hierarchy. In essence, the struc-
tural similarity allows the social influence in the network to spread
where the hyper-parameter 𝛼 is the trade-off factor between the
among users’ neighbors and the entire graph with different weights.
1-to-1 friendships and 1-to-N group relations. The function 𝑑 (·)
Thus, in the 𝑙-th layer of the multi-layer network, the edge weight
measures the distance between two node sequences, which can
between two nodes is defined as
be implemented with various distance measure methods, such as
degree-based dynamic time warping [30] adopted in our work. 𝑤 (𝑢, 𝑣, 𝑙) = 𝑒 R (𝑢,𝑣,𝑙) . (5)
As neighborhood structures (i.e., N𝑙𝑆 (·) and N𝑙𝐺 (·)) imply the Naturally, the larger the distance between two users with respect to
role of nodes in the graph and social influence propagates along neighborhood structures, the more similar the two users, as well as
neighbors, it is natural that the defined structural distance D (𝑢, 𝑣, 𝑙) the larger the edge weight between the two users. Thus, the graph
copes with distinguishing structures between friendships and group
in layer 𝑙 can be formulated as G𝑙 = (V, E𝑙 ), where |E𝑙 | = | V |

2 .
relations and captures more refined structural similarity.
In terms of the connection of two layers, inspired by [31], we
Structure-embedded Representation. By definition D (𝑢, 𝑣, 𝑙) link each node to its corresponding node in the layer above and
is based on the 𝑙-hop neighborhood structures, we can flexibly below. Thus, the edge weight between layers are defined as follows:
measure the similarity between two users in terms of different
neighborhood structures. Towards fully exploring the diffusion of 𝑤 (𝑢𝑙−1, 𝑢𝑙 ) = 1, (6)
Õ
social influence among users, we construct a multi-layer weight 𝑤 (𝑢𝑙 , 𝑢𝑙+1 ) = log( 1(𝑤 (𝑢, 𝑣, 𝑙) > 𝑤 (𝑙)) + 𝑒),
graph that hierarchically encodes the structural similarity, then 𝑣 ∈V
perform the random walk on the multi-layer weight graph to de- where 𝑤 (𝑢𝑙−1, 𝑢𝑙 ) and 𝑤 (𝑢𝑙 , 𝑢𝑙+1 ) are the edge weights of the node 𝑢
rive the user sequences, and finally learn the structure-embedded
in the above and below layers. The term 𝑤 (𝑙) = 𝑢,𝑣 ∈V 𝑤 (𝑢, 𝑣, 𝑙)/ | V |

Í
representations for users, as shown in Fig. 3(b). 2
is the average edge weight of the complete graph in layer 𝑙, and the
Formally, given the structural distance D (𝑢, 𝑣, 𝑙) based on the
log function reduces the magnitude of the potentially large number
𝑙-hop neighborhood structures, we hierarchically formulate the
of nodes that are similar to 𝑢 in a given layer.
structural similarity in the 𝑙-th layer of the multi-layer graph as:
Now, given the number of layers, denoted as 𝑙, we can formulate
𝑙
Õ the multi-layer graph H as
R (𝑢, 𝑣, 𝑙) = − D (𝑢, 𝑣, 𝑖). (4)
𝑖=1 H = G 1 ★ G 2 ★ · · · ★ G𝑙 , (7)

4197
Applied Research Paper Track CIKM ’21, November 1–5, 2021, Virtual Event, Australia

where the operation ★ represents the connection between two Table 1: Statistics of the three datasets.
layers of networks. In fact, the multi-layer graph H can cope with
the different structures between the 1-to-1 friendships and 1-to-N Dataset 7-days 15-days 31-days
group relations in the multi-relational social network G, since the
#Users 179,080,550 190,932,127 255,878,282
weights between nodes in each layer of H completely lie on the
#Friendships 117,028,138 249,286,424 508,216,853
relation-aware structural distance defined before.
#Group Relations 300,675,112 643,033,468 1,322,769,827
With the multi-layer graph H , we next learn the structure-
embedded representations for users in the MRSN G. Following [31],
we conduct a random walk on the multi-layer graph H to generate
the context sequences that are likely to include structurally similar
nodes, denoted as C. Further, inspired by recently emerging graph 6.1 Experimental Setup
convolutional networks [17], we learn the structure-embedded rep-
Datasets. As described in Section 4, we further extract three sub-
resentations for users by optimizing the co-occurrence probability:
sets of the real-world dataset in WeChat for evaluation, named 7-
days dataset (contains 17.91 million users ranging from 2020/07/01
L = − log 𝜎 (x𝑢⊤ x𝑣 ) − 𝐾 · E𝑣′ ∼𝑃 log 𝜎 (−x𝑢⊤ x𝑣′ ), (8) to 2020/07/07), 15-days dataset (contains 19.09 million users rang-
ing from 2020/07/01 to 2020/07/15), and 31-days dataset (contains
25.59 million users ranging from 2020/07/01 to 2020/07/31). Their
where x𝑢 ∈ X ∈ R |V |×𝑑 is the structure-embedded representation
statistics are summarized in Table 1.
for the user 𝑢 in the MRSN G, and 𝜎 means the sigmoid function.
Here 𝐾 is the number of negative sample and 𝑃 is the negative Baselines. We compare our proposed Generate&Extend with
sample distribution. Since 𝑣 in Eq. (8) is a node that co-occurs near several state-of-art methods in the literature, including the classic
𝑢 in the random sequence C traversing the multi-layer graph H , the Random-based and DegreeDiscountIC [11] methods, as well as
learned representations for users is capable of encoding different the recent SSA [28] and OPIM [36]. Please note that we have also
structures of friendships and group relations in the original multi- tried to compare our Generate&Extend to some classic methods
relational social network G. (e.g., IMM [37] and TIM [38], etc.), however, they either fail to obtain
results due to time or memory complexity, or perform much worse.
Meta-seed Extension. Recall that our goal is to extend the meta-
seed set considering the different propagation structures of the • Random-based method simply selects 𝑘 random nodes in the
1-to-1 and 1-to-N relations, next we cluster the seeds of similar multi-relational social network.
structure with the learned structure-embedded representations. • DegreeDiscountIC [11] is a degree discount heuristic designed
In specific, we take each seed user in the meta-seed set as a for the uniform IC model [13] with a propagation probability of
cluster center, and then input the learned structure-embedded rep- 𝑝 = 0.01, as suggested in [11].
resentations X into a cluster to gather users with structures similar • SSA [28] is also a reverse influence sampling based algorithm
to the meta seed as the extended seeds. In particular, we have that achieves the (1 − 1/𝑒 − 𝜖) theoretical guarantee.
• OPIM [36] is also based on reverse influence sampling algorithm
that achieve the (1 − 1/𝑒 − 𝜖) theoretical guarantee.
S = CLuster(S0, X), (9)
Evaluation Metrics. We evaluate the comparison performance by
where S is the final seed set for influence maximization in the predicting the next week’s influence propagation of seed users. We
multi-relational social network G. The function CLuster can be adopt a variety of metrics widely used in the industry to measure
implemented with clustering algorithms, such as K-nearest neigh- the online and offline performance of influence maximization. For
bor [29] adopted in our work. In fact, the structure-embedded user the online experiment, we mainly use the number of activated
representations ensure that the extended seeds are similar to the users by seed users S (i.e., the expected influence as in [28]) and
meta seeds in structure, which effectively tackle the challenges of the activation rate. Besides, to show the quality of the seed set, as
different structures and the large-scale network cased by the 1-to-N mentioned before, we also measure the true influential seeds and
group relations. the fake seed rate. Formally,

#Activated Users = #Users that use the product shared by S

6 EXPERIMENTS
#Activated Users
In this section, we conduct extensive online and offline experiments #Activation Per Seed =
to answer three research questions: (RQ1) In terms of the online |S|
number of activated users by the seeds, how does Generate&Extend #True Influential Seeds = #Seeds that successfully activate others
perform compared to the state of the arts? (RQ2) What is the offline #Seeds that unsuccessfully activate others
Fake Seed Rate =
consumption of the promoted product by seed users w.r.t. differ- |S|
ent methods? (RQ3) How does Generate&Extend benefit from the
structural seed extender for both online and offline performance? For the offline experiment, we adopt two widely used metrics to
Besides, a case study is provided to intuitively demonstrate the evaluate the offline product consumption of the selected seed users,
influence diffusion in a multi-relational social network. including the sharing rate and the number of sharing times per

4198
 # Activated Users
3.2E+07 6.8E+06 0.90

# True Influential Se
#Activation Per Se

Fake Seed Rate

1.35
2.4E+07 5.1E+06 0.80
0.90
1.6E+07 3.4E+06 0.70
Applied 0.45
8E+06Research Paper Track 1.7E+06 CIKM ’21, November 1–5,0.60
2021, Virtual Event, Australia
0E+00 0.00 0E+00 0.50
6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7
Day Day Day Day

Random-based DegreeDiscountIC SSA OPIM Generate&Extend Random-based DegreeDiscountIC SSA OPIM Generate&Extend
3E+07
Random-based DegreeDiscountIC 3.00
SSA OPIM Generate&Extend 6.5E+06
Random-based DegreeDiscountIC 1.00
SSA OPIM Generate&Extend

Seeds
3.5E+07 1.80 8.5E+06 1.00

Seed
Users

2.4E+07 5.2E+06

Seeds

Rate
2.25 0.83

Seed
6.8E+06
Users

ree-based 2.8E+07 SSA 1.44

Generate&Extend 0.90

Influential
PerPer

Rate
1.8E+07 Random-based
3.9E+06 DegreeDiscountIC SSA OPIM Generate&Extend Random-based
# Activated

Seed
Influential
1.50 3.5E+07 1.80 0.65 8.5E+06

#Activation
2.1E+07 1.08 5.1E+06 0.80

# True Influential Seeds

# Activated

Seed
1.2E+07 2.6E+06

#Activation Per Seed

#Activation

Fake
6.8E+06

# Activated Users
1.4E+07 0.72 2.8E+07
3.4E+06 1.44 0.70
0.75 0.48

# True
6E+06

Fake
1.3E+06
2.1E+07 1.08 0.60 5.1E+06

# True
7E+06 0.36 1.7E+06
0E+00 0.00 0E+00 0.30
6 7 0E+00 1 2 3 4 5 6 7 0.00 1 2 3 4 5 6 7 1.4E+07
0E+00 1 2 3 4 5 6 7 0.72 0.50 1 2 3 4 5 6 3.4E+06
7
6 7 1 2 3 Day
4 5 6 7 1 2 3 4 5 6 7 7E+06 1 2 3 Day4 5 6 7 1 2 3 4 5 6 7
Day 0.36 Day 1.7E+06
Day Day Day Day
(a) 7-days 0E+00
dataset 0.00 0E+00
2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3
Day Day Day
Random-based DegreeDiscountIC SSA OPIM Generate&Extend Random-based DegreeDiscountIC SSA OPIM Generate&Extend
4E+07 1.80 8.5E+06 1.00

# True Influential Seeds

#Activation Per Seed

ree-based 3.2E+07 SSA Generate&Extend

# Activated Users

6.8E+06
Random-based DegreeDiscountIC SSA 0.90 OPIM Generate&Extend Random-based

Fake Seed Rate

1.35
Random-based DegreeDiscountIC SSA OPIM Generate&Extend
4E+07 1.80 8.5E+06
2.4E+07 0.08 5.1E+06 0.80

# True Influential Seeds

2.5

#Activation Per Seed

0.90

# Activated Users
3.2E+07 1.35 0.70 6.8E+06
1.6E+07 0.07 3.4E+06
#Sharing Per User

2.0
2.4E+07 5.1E+06
Sharing Rate

0.45
8E+06 0.06 1.5 1.7E+06 0.90 0.60
1.6E+07 3.4E+06
0E+00 0.05 0.00 1.0 0E+00 0.50
6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8E+06 1 2 3 4 5 6 7 0.45 1 2 3 4 5 6 7
1.7E+06
0.04 Day Day Day 0.5 Day
0E+00 0.00 0E+00
0.03 2 3 0.14 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3
(b) 15-days dataset
Random-based7-days DegreeDiscountIC
15-days 31-days SSA OPIM7-daysGenerate&Extend
Day 15-days 31-days Random-based DayDegreeDiscountIC SSA OPIM Day Generate&Extend
3E+07 Dataset 3.00 Dataset 6.5E+06 1.00
Random-based DegreeDiscountIC SSA OPIM Generate&Extend Random-based DegreeDiscountIC SSA OPIM Generate&Extend
Seeds

(a) Sharing rate (b) #Sharing Pre User

Per Seed

Degree-based 3.5E+07 SSA OPIM

1.80 Random-based
8.5E+06 DegreeDiscountIC SSA 1.00 OPIM Generate&Extend Random-based
UsersUsers

2.4E+07 5.2E+06

RateRate
2.25 3.00 0.83
Seeds

3E+07 6.5E+06
Per Seed

Influential

# True Influential Seeds

2.8E+07
1.8E+07 1.44 6.8E+06
3.9E+06 0.90

#Activation Per Seed

# Activated

SeedSeed
# Activated Users

1.50 2.4E+07 5.2E+06

2.25 0.65
#Activation

Influential

2.1E+07
1.2E+07 Generate&Extend-M
1.08 Generate&Extend-D
5.1E+06
2.6E+06 Generate&Extend
0.80
# Activated

1.8E+07

FakeFake
3.5E+07 8.5E+06 0.071 2.4 3.9E+06
#Activation

0.75 0.48
# True Influential Seeds

1.50 0.70
# True

1.4E+07
6E+06 0.72 3.4E+06
1.3E+06
1.2E+07 2.6E+06

#Sharing Per User

# Activated Users

3.3E+07
7.5E+06 0.069 1.8
# True

7E+06 0.36 1.7E+06 0.75 0.60

Sharing Rate

0E+00 0.00 0E+00 0.30

6 7 3.1E+07
1 2 3 4 5 6 7 1 2 3 4 5 6 7 6E+06 1 2 3 4 5 6 7 1 2 3 4 5 6 1.3E+06
7
0E+00 0.00 6.5E+06 0E+00 0.066 0.50 1.2
6 7 1
2.9E+07 2 3 Day 4 5 6 7 1 2 3 Day 4 5 6 7 0E+00 1 2 3 Day 4 5 6 7 0.00 1 2 3 Day4 5 6 7 0E+00
2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3
2.7E+07 Day 5.5E+06 Day 0.064 Day 0.6 Day
Day Day Day
2.5E+07 4.5E+06 (c) 31-days dataset 0.061 0
Random-based7-daysDegreeDiscountIC
15-days 31-days SSA OPIM 7-days 15-days
Generate&Extend 31-daysRandom-based 7-days 15-days
DegreeDiscountIC31-days
SSA OPIM7-days Generate&Extend
15-days 31-days
4E+07 Dataset 1.80 Dataset 8.5E+06 Dataset 1.00 Dataset
# True Influential Seeds

Figure 4: Online experimental results on three datasets with respect to each day in the next week.
#Activation Per Seed
# Activated Users

3.2E+07 6.8E+06 0.90

Fake Seed Rate

Random-based DegreeDiscountIC 1.35 SSA OPIM Generate&Extend

2.4E+07 0.08 2.5 5.1E+06 0.80
0.90 Random-based DegreeDiscountIC SSA OPIM Generate&Extend
#Sharing Per User

SA
seed user. In specific,
OPIM 1.6E+07 0.07 Generate&Extend 2.0 3.4E+06
0.08 0.70
2.5
Sharing Rate

8E+06 0.06 product #Seeds who share0.45 the

1.5
#Sharing Per Seed

1.7E+06
0.07 0.60
2.0
Sharing Rate =
Sharing Rate

0E+00 0.05 #Seeds who use the

0.00 1.0product 0E+00
0.06 0.50
1.5
6 7 1 2 3 4 5 6 #Total
7 1 times
sharing 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7
0.04 0.5 0.05 1.0
#Sharing Per
DaySeed = Day Day Day
0.03 |S| 0.1 0.04 0.5
7-days 15-days 31-days 7-days 15-days 31-days
Random-based
Implementation Details. DegreeDiscountIC SSA OPIM
We randomly initialize our model Generate&Extend
pa- Random-based
0.03 DegreeDiscountIC SSA 0.1 OPIM Generate&Extend
3E+07 Dataset 3.00 Dataset 6.5E+06 7-days 15-days 31-days 1.00 7-days 15-days 31-days
(a) Sharing rate (b) #Sharing Pre User
# True Influential Seeds

rameters with an xavier initialization and set the

31-days optimizer as Adam.
#Activation Per Seed

Dataset Dataset
# Activated Users

2.4E+07 we set the sizes of meta-seed set to 1,000,000, 2,000,000 5.2E+06

# True Influential Seeds Fake Seed Rate

Moreover, Dataset 2.25 (a) Sharing rate 0.83 (b) #Sharing Per Seed
and1.8E+07
2,000,000, and the sizes of the final seed set is set to 10,000,000, 3.9E+06
1.50
Generate&Extend-M Generate&Extend-D 0.65
Generate&Extend
1.2E+07
20,000,000 and 20,000,000 for three datasets,
3.5E+07
respectively. The num-
8.5E+06 Figure
2.6E+06 5: Offline product consumption
0.071 2.4 of the selected seed
Generate&Extend-D ber of layers of the Generate&Extend Generate&Extend-M Generate&Extend-D
# True Influential Seeds

6E+06 multi-layer graph 0.75

is 𝑙 = 2, the trade-off factor users
1.3E+06
3.5E+07
on three datasets. 0.48
8.5E+06 0.071
#Sharing Per User
# Activated Users

3.3E+07
7.5E+06 0.069 1.8
Sharing Rate

𝛼 is set to 0.4, and the dimension of structure-embedded repre-

0E+00 0.00 0E+00 0.30
# Activated Users

3.1E+07 3.3E+07 7.5E+06 0.069

1 users
2 3 is4set5to 128.6 7 We set the
Sharing Rate

6 7 sentations for 1 number

2
6.5E+06 3 of 4 negative
5 6 7 1
0.066 2 3 4 5 6 7 11.2 2 3 4 5 6 7
2.9E+07
samples to 𝐾 = 5 andDay the learning rate to 1𝑒 − 5. The hops Day of the
3.1E+07
Day Day
6.2 Online Evaluation (RQ1)
6.5E+06 0.066
5.5E+06are set to ℎ = 6 2.9E+070.064 the online performance of methods, 0.6
truncated2.7E+07
reachable set and structure distance To evaluate we mainly measure
5.5E+06 0.064
and 𝑙 =2.5E+07
3, respectively. For the baselines, we set the same seed set
4.5E+06 2.7E+07
the number
0.061 of activated users by seeds (i.e., 0 the expected influence
7-days 15-days 31-days
size as our framework and optimize other parameters according to 7-days 15-days 31-days
as2.5E+07 7-days 15-days
in [28]) and the number of activation 31-days 4.5E+06 7-days 15-days
per seed. Besides, to demon- 31-days 0.061
literatures. Since the baselines Dataset are not15-days
designed31-days Dataset
for multi-relational 7-days
strate the quality 15-days
of Dataset
the 31-days
seed set, we further measure7-days 15-days
Dataset
the number31-days 7-da
Dataset
social networks, we take all relations as the same type. of true influential Dataset
seeds and the fake rate of seeds. Dataset
Random-based DegreeDiscountIC SSA OPIM Generate&Extend
0.08 2.5
#Sharing Per User

0.07 2.0
Sharing Rate

0.06 1.5

0.05 1.0 4199

0.04 0.5

0.03 0.1
 Sharin

#Sharing
0.05 1.0
0.04 0.5

0.03 0.1
Applied Research
7-days Paper
15-daysTrack
31-days 7-days 15-days 31-days CIKM ’21, November 1–5, 2021, Virtual Event, Australia
Dataset Dataset
(a) Sharing rate (b) #Sharing Pre User

Generate&Extend-M Generate&Extend-D Generate&Extend

3.5E+07 8.5E+06 0.071 2.4

# True Influential Seeds

#Sharing Per User

# Activated Users

3.3E+07
7.5E+06 表格 1 0.069 1.8

Sharing Rate
3.1E+07 31days 15days 7days
6.5E+06 0.066 1.2
100w 32795057.71 31582668.43 27965268.14 50 770508.8575 -770508.8575
2.9E+07
150w 32824244.57 31760448.43 28093427.29 75 875922.4519 -875922.4519
2.7E+07 5.5E+06 0.064 0.6
200w 32918395.29 31908223.57 28145529.14 100 875866.9369 -875866.9369
250w 32902765.86 31893071 28127105.71 125 865801.7849 -865801.7849
2.5E+07 4.5E+06 0.061 0
7-days 15-days 31-days 7-days 15-days 31-days 7-days 15-days 31-days 7-days 15-days 31-days
Dataset Dataset Dataset Dataset

Figure 6: Analysis of Generate&Extend using various ablated models.

40000 2.82E+07 3.30E+07

Random-based 7days
Running time (s)

# Activated Users

# Activated Users
30000 DegreeDiscountIC 2.81E+07 3.26E+07
SSA 2.81E+07 3.22E+07
20000 OPIM
Generate&Extend 2.80E+07 3.18E+07
10000
2.80E+07 3.14E+07 31days
0 15days
2.79E+07 3.10E+07
7-days 15-days 31-days 500k 750k 1000k 1250k 1000k 1500k 2000k 2500k
(a) Running time analysis. (b) Impact of the size of meta-seed set.

Figure 7: Analysis of running time and parameter.

We report the comparison results w.r.t. every day in the next sharing times per user means that the seed users are more active.
week in Fig. 4, from which we have the following findings: (1) Over- Compared to the baselines, we observe that our Generate&Extend
all, our Generate&Extend consistently yields the highest quality achieves the largest sharing rate, which implies that much more
seeds among all methods on three datasets. Specifically, seed users seed users of Generate&Extend are willing to share the product of-
selected by our Generate&Extend significantly improve the num- fline after using the product. We believe the reason is that seed uses
ber of activated users and the activation rate, which implies that selected by Generate&Extend have the similar structures encoding
our Generate&Extend is capable of modeling user influence in the 1-to-N group relations in the MRSN, which is in line with the before
MRSN and thus finding the most influential seeds. (2) In terms of analysis that more activated users are brought by group relations.
the quality of the seed set, the number of true influential seeds in On the other hand, it is obvious that the seed users selected by
the seed set selected by our Generate&Extend is obviously larger the proposed Generate&Extend have the strongest sharing and
than that of the baselines. Besides, our Generate&Extend achieves consumption power, achieving the largest sharing times per users.
the lowest fake seed rate, i.e., the proportion of users who do not As the 1-to-N group relations significantly affect a user’s sharing
share the promoted product in the seed set, which benefits from behavior, Generate&Extend effectively captures the different prop-
the extension of the meta-seed with the consideration of structures agation structures of friendship and group relations,
of multiple relations. (3) Among different baselines, random-based
method has a much worse influence spread, indicating that a careful
seed selection is indeed important to effective product promotion. 6.4 Model Analysis (RQ3)
DegreeDiscountIC and SSA improve the quality of the seed set, but Ablation Analysis. To investigate the underlying mechanism
the performance is still unsatisfactory since they lose the different of our Generate&Extend, we conduct an ablation analysis with
structures of friendships and group relations. (4) From the perspec- two variant models: Generate&Extend-M without the multi-layer
tive of online influence in a week, we obverse that the number network, as well as Generate&Extend-D without differentiating
of activated users is generally stable on different days, since the friendships and group relations. As presented in Fig. 6, our Gener-
number of daily active users of WeChat is stable. ate&Extend is consistently superior to all variant models, in terms of
the number of online activated user and the offline consumption of
6.3 Offline Evaluation (RQ2) the seed users. Among different ablated models, Generate&Extend-
We investigate the offline consumption of the promoted product M is least competitive in most cases, which makes sense as it opti-
by seed users: the product sharing rate, and the number of sharing mizes node embedding based on feature homophily (i.e., two con-
times per user. Since similar trends are observed every day in next nected node should be similar) and loses the hierarchical structure
week, here we report the average performance of the entire week. information in the multi-relational social network. Compared with
As presented in Fig. 5, the higher sharing rate indicates that Generate&Extend-M, Generate&Extend-D achieves better perfor-
more seed users share the promoted product offline, while the more mance but still underperforms Generate&Extend, illustrating that

4200
 表格 1-1

需求3

Applied Research Paper Track

所在群分段 ⼈数 好友数分段 ⼈数 CIKM ’21, November 1–5, 2021, Virtual Event, Australia
<10 17377349 <100 13935548

10~20 4321288 100~200 6292812

20~50 1418630 200~300 3657312

50~100 967668 300~500 683261

100+ 766600 500+ 282602

120
Friendship

# Activated users
需求4 成员数 群组数

<10 456377291
90 Group Relation
10~50 390527647 449483726

50~100 58956079 60
100~300 36852734

300+ 10302927 30

需求5 聊天类型 ⼈数
0
1007 17648322
1 2 3
1008 15367896 Hop
(a) Generate&Extend-M. (b) Generate&Extend. Friendship
Group Relation
(a) Influence propagation graph. (b) Statistics of activated users.
120

# Activated
Figure 8: Visualization of node embeddings The meta-seed 90

users
Figure 9: Case study 60 of the influence diffusion of a user (the
nodes are in red, while the others are in blue.
red node) through 30 friendships (red lines) and group rela-
Friendship
tions (blue lines). 0 Group Relation
1 2 3 1.4E+09
the structures-embedded representation is a crucial component of
Hop
Generate&Extend and differentiating friendships and group rela- 1.1E+09

Number
study to visualize the influence propagation graph of a seed user. In
tions is vital for IM. specific, we randomly select a seed user in the 7.0E+08
seed set generated by
Moreover, in order to intuitively demonstrate the capability 表格our1-2 Generate&Extend, and then we enumerate 3.5E+08the activated users
of structure-embedded representations, we comparatively visual-Friendship
influenced by the seed user during the {1,0.0E+00
Group Relation
2, 3}-hop propagation.
508216853 1322769827
ize the low-dimensional node embeddings learned by our Gen- As showcased in Fig. 9, the blue edges occupy almostRelation
the entire
erate&Extend and Generate&Extend-M. In specific, we map the 102774069 214087987
graph, which indicates that the spread of influence via 1-to-N group
low-dimensional node embeddings to a 2-D space using the t-SNE relations are much wider than the spread2.2E+08 of influence via 1-to-1

# Activated users
[39] package, and color the meta-seed nodes as red and the others friendships. Besides, we can observe that 1.7E+08
the number of activated
as blue in Fig. 8. It is obvious that our Generate&Extend can better users influenced through group relations1.1E+08 is much larger than the
separate the meta-seed users from other users, showing that the number of users influenced by friendships. This case study is also in
selected meta-seed users are similar in structure rather than fea- 5.5E+07
line with the data observations in Section 4, which demonstrates the
ture homophily. Besides, this observation shows that it is critical to effectiveness of Generate&Extend in capturing 0.0E+00multiple relational
extend the meta-seed users with the consideration of the structure Relation
structures in a multi-relational network.
similarly, so as to avoid the influence overlap problem [26].
Running Time Analysis. To verify the efficiency of our pro- 7 CONCLUSION
posed Generate&Extend, we compare the running time of Gener- In this paper, we conducted analysis on social influence diffusion in
ate&Extend to the baselines on three datasets. We run all methods WeChat, and first studied the problem of influence maximization in
on the same machine with 12 Intel(R) Xeon(R) CPUs. As presented multi-relational social networks. To simultaneously cope with the
in Fig. 7(a), as the scale of dataset increases, the advantages of our 1-to-1 friendships and 1-to-N group relations, we proposed a novel
Generate&Extend become more obvious, with less running time Generate&Extend framework consisting of a truncated meta-seed
than the comparison method. Among all baselines, the random- generator and a structural seed extender. Specifically, the truncated
based and DegreeDiscountIC achieve the less running time since meta-seed generator selected a small number of influential users as
they do not need to operate reverse influence sampling as in other the meta-seed set, which achieved a trade-off between effectiveness
baselines and our Generate&Extend. and efficiency. More importantly, a structural seed extender was
Parameter Analysis. Lastly, we study the impact of the size of put forward to differentiate influence propagation structures of
meta-seed set (i.e., 𝑘 0 ) on model performance, and report the num- friendships and group relations, and then derived the final seed
ber of activated users w.r.t different meta-seed sizes in Fig. 7(b). We set for influence maximization in a multi-relational social network.
observe that as the number of meta seeds increases, the number Extensive experiments on three datasets of WeChat demonstrated
of activated users also increases at the beginning, but it gradually that Generate&Extend significantly outperforms the baselines in
stabilizes, indicating that Generate&Extend is generally robust w.r.t. online and offline scenarios.
the size of meta-seed set. Since Generate&Extend selects meta seeds
without differentiating friendships and group relations in consid- 8 ETHICS STATEMENT
eration of efficiency, a larger meta-seed set will include more fake While our proposed Generate&Extend is evaluated on datasets of
seed, leading to a gradually stable influence of the entire meta seeds. WeChat, it sheds an interesting insight for influence maximization
The results imply the importance of structural seed extender to in multi-relational social networks, which is adaptable to various
distinguish different structures of friendships and group relations. scenarios in online social platforms. As we all know, machine learn-
As we select enough meta-seeds, the method achieves the largest ing in general runs the risk of violating privacy due to the collection
influence and the performance tends to be stable. of user data, especially in the filed of social network analysis [8, 33].
Thus, to avoid any leakage of personal privacy information, in our
6.5 Case Study work, we desensitize the collected data and only use meaningless ids
To intuitively demonstrate the capability of modeling influence to denote users. We state that the datasets are strictly anonymous
diffusion in a multi-relational network, here we conduct a case and have no access to the detailed user profiles.

4201
Applied Research Paper Track CIKM ’21, November 1–5, 2021, Virtual Event, Australia

REFERENCES [22] Yuchen Li, Ju Fan, Yanhao Wang, and Kian-Lee Tan. 2018. Influence maximization
[1] Eva Anduiza, Camilo Cristancho, and José M Sabucedo. 2014. Mobilization on social graphs: A survey. IEEE Transactions on Knowledge and Data Engineering
through online social networks: the political protest of the indignados in Spain. 30, 10 (2018), 1852–1872.
Information, Communication & Society 17, 6 (2014), 750–764. [23] Qi Liu, Biao Xiang, Enhong Chen, Hui Xiong, Fangshuang Tang, and Jeffrey Xu
[2] Nicolas M Anspach. 2017. The new personal influence: How our Facebook friends Yu. 2014. Influence maximization over large-scale social networks: A bounded
influence the news we read. Political Communication 34, 4 (2017), 590–606. linear approach. In Proceedings of CIKM. 171–180.
[3] Akhil Arora, Sainyam Galhotra, and Sayan Ranu. 2017. Debunking the myths [24] Yuanfu Lu, Ruobing Xie, Chuan Shi, Yuan Fang, Wei Wang, Xu Zhang, and
of influence maximization: An in-depth benchmarking study. In Proceedings of Leyu Lin. 2020. Social Influence Attentive Neural Network for Friend-Enhanced
SIGMOD. 651–666. Recommendation. In Proceedings of ECML-PKDD, Vol. 12460. 3–18.
[4] Lobna Azaza, Sergey Kirgizov, Marinette Savonnet, Eric Leclercq, and Rim Faiz. [25] Hao Ma, Haixuan Yang, Michael R Lyu, and Irwin King. 2008. Mining social
2015. Influence assessment in twitter multi-relational network. In Proceedings of networks using heat diffusion processes for marketing candidates selection. In
SITIS. 436–443. Proceedings of CIKM. 233–242.
[5] Eytan Bakshy, Jake M Hofman, Winter A Mason, and Duncan J Watts. 2011. [26] Peter V Marsden and Noah E Friedkin. 1993. Network studies of social influence.
Everyone’s an influencer: quantifying influence on twitter. In Proceedings of Sociological Methods & Research 22, 1 (1993), 127–151.
WSDM. 65–74. [27] Akash Mittal, Anuj Dhawan, Sahil Manchanda, Sourav Medya, Sayan Ranu, and
[6] Suman Banerjee, Mamata Jenamani, and Dilip Kumar Pratihar. 2020. A survey on Ambuj Singh. 2019. Learning heuristics over large graphs via deep reinforcement
influence maximization in a social network. Knowledge and Information Systems learning. arXiv preprint arXiv:1903.03332 (2019).
(2020), 1–39. [28] Hung T Nguyen, My T Thai, and Thang N Dinh. 2016. Stop-and-stare: Optimal
[7] Christian Borgs, Michael Brautbar, Jennifer Chayes, and Brendan Lucier. 2014. sampling algorithms for viral marketing in billion-scale networks. In Proceedings
of SIGMOD. 695–710.
Maximizing social influence in nearly optimal time. In Proceedings of SIAM. 946–
[29] Leif E Peterson. 2009. K-nearest neighbor. Scholarpedia 4, 2 (2009), 1883.
957.
[30] Thanawin Rakthanmanon, Bilson Campana, Abdullah Mueen, Gustavo Batista,
[8] Salvatore A Catanese, Pasquale De Meo, Emilio Ferrara, Giacomo Fiumara, and
Brandon Westover, Qiang Zhu, Jesin Zakaria, and Eamonn Keogh. 2013. Ad-
Alessandro Provetti. 2011. Crawling facebook for social network analysis pur-
dressing big data time series: Mining trillions of time series subsequences under
poses. In Proceedings of WIMS. 1–8.
dynamic time warping. ACM Transactions on Knowledge Discovery from Data 7,
[9] Wei Chen, Wei Lu, and Ning Zhang. 2012. Time-Critical Influence Maximization
3 (2013), 1–31.
in Social Networks with Time-Delayed Diffusion Process. In Proceedings of AAAI.
[31] Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel R Figueiredo. 2017. struc2vec:
[10] Wei Chen, Chi Wang, and Yajun Wang. 2010. Scalable influence maximization
Learning node representations from structural identity. In Proceedings of KDD.
for prevalent viral marketing in large-scale social networks. In Proceedings of
385–394.
KDD. 1029–1038.
[32] Marko A Rodriguez and Joshua Shinavier. 2010. Exposing multi-relational net-
[11] Wei Chen, Yajun Wang, and Siyu Yang. 2009. Efficient influence maximization in
works to single-relational network analysis algorithms. Journal of Informetrics 4,
social networks. In Proceedings of KDD. 199–208.
1 (2010), 29–41.
[12] Nan Du, Le Song, Manuel Gomez Rodriguez, and Hongyuan Zha. 2013. Scalable
[33] Michael Seufert, Tobias Hoßfeld, Anika Schwind, Valentin Burger, and Phuoc
influence estimation in continuous-time diffusion networks. In Proceedings of
Tran-Gia. 2016. Group-based communication in WhatsApp. In 2016 IFIP network-
NeurIPS. 3147–3155.
ing conference (IFIP networking) and workshops. IEEE, 536–541.
[13] Jacob Goldenberg, Barak Libai, and Eitan Muller. 2001. Talk of the network: A
[34] Jimeng Sun and Jie Tang. 2011. A survey of models and algorithms for social
complex systems look at the underlying process of word-of-mouth. Marketing
influence analysis. In Social network data analytics. Springer, 177–214.
letters 12, 3 (2001), 211–223.
[35] Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. 2009. Social influence analysis in
[14] Amit Goyal, Wei Lu, and Laks VS Lakshmanan. 2011. Celf++ optimizing the
large-scale networks. In Proceedings of KDD. 807–816.
greedy algorithm for influence maximization in social networks. In Proceedings
[36] Jing Tang, Xueyan Tang, Xiaokui Xiao, and Junsong Yuan. 2018. Online processing
of WWW. 47–48.
algorithms for influence maximization. In Proceedings of SIGMOD. 991–1005.
[15] Mark Granovetter. 1978. Threshold models of collective behavior. American
[37] Youze Tang, Yanchen Shi, and Xiaokui Xiao. 2015. Influence maximization in
journal of sociology 83, 6 (1978), 1420–1443.
near-linear time: A martingale approach. In Proceedings of SIGMOD. 1539–1554.
[16] Adrien Guille, Hakim Hacid, Cecile Favre, and Djamel A Zighed. 2013. Infor-
[38] Youze Tang, Xiaokui Xiao, and Yanchen Shi. 2014. Influence maximization: Near-
mation diffusion in online social networks: A survey. ACM Sigmod Record 42, 2
optimal time complexity meets practical efficiency. In Proceedings of SIGMOD.
(2013), 17–28.
75–86.
[17] Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation
[39] Laurens Van der Maaten and Geoffrey Hinton. 2008. Visualizing data using t-SNE.
learning on large graphs. In Proceedings of NeurIPS. 1024–1034.
Journal of machine learning research 9, 11 (2008).
[18] David Kempe, Jon Kleinberg, and Éva Tardos. 2003. Maximizing the spread of [40] Jyun-Cheng Wang and Ching-Hui Chang. 2013. How online social ties and
influence through a social network. In Proceedings of KDD. 137–146. product-related risks influence purchase intentions: A Facebook experiment.
[19] Moein Khajehnejad, Ahmad Asgharian Rezaei, Mahmoudreza Babaei, Jessica Electronic Commerce Research and Applications 12, 5 (2013), 337–346.
Hoffmann, Mahdi Jalili, and Adrian Weller. 2020. Adversarial Graph Embeddings [41] Ning Wang, Zi-Yi Wang, Jian-Guo Liu, and Jing-Ti Han. 2019. Maximizing
for Fair Influence Maximization over Social Networks. In Proceedings of IJCAI. spreading influence via measuring influence overlap for social networks. arXiv
4306–4312. preprint arXiv:1903.00248 (2019).
[20] Samir Khuller, Anna Moss, and Joseph Seffi Naor. 1999. The budgeted maximum [42] Xiaoyang Wang, Ying Zhang, Wenjie Zhang, and Xuemin Lin. 2016. Efficient
coverage problem. Information processing letters 70, 1 (1999), 39–45. distance-aware influence maximization in geo-social networks. IEEE Transactions
[21] Guoliang Li, Shuo Chen, Jianhua Feng, Kian-lee Tan, and Wen-syan Li. 2014. on Knowledge and Data Engineering 29, 3 (2016), 599–612.
Efficient location-aware influence maximization. In Proceedings of SIGMOD. 87– [43] Christine B Williams and Girish J‘Jeff’ Gulati. 2013. Social networks in political
98. campaigns: Facebook and the congressional elections of 2006 and 2008. New
Media & Society 15, 1 (2013), 52–71.

4202