Learning Multiple Network Embeddings for Social Influence Prediction

How to effectively predict social influence is an essential issue in social network analysis. Almost all reported methods for social influence prediction are mainly concerned with estimating influence probabilities for each linking edge. However, all of this past work cannot accurately predict influence probabilities for all edges due to the problem of data sparsity. Unlike conventional approaches, this work focuses on exploring a cross problem for multiple network embeddings and social influence prediction. This study developed a new end-to-end approach, Multi-Influor, that learns multiple influence vectors for each user in social networks, instead of estimating influence probabilities for each edge. The multiple network embeddings consider multi-dimensional influence factors that incorporate pairwise node interactions, network structures, and global similarity comparisons. Moreover, this study solves the problem of influence evaluation caused by sparse observations. Extensive comparisons based on large-scale datasets indicate that the Multi-Influor approach outperforms several state-ofthe-art baselines, and the experimental results demonstrate that the Multi-Influor approach is more practical on real-world social networks.


INTRODUCTION
The rapid development of online social networks (OSNs) lays a foundation for spreading users' ideas and messages. The related work of social network analysis has found that users' friends or neighbors greatly affect these users' behaviors or opinions from a perspective of psychology [Aslay, et al. (2018)]. Thus, this study defines social influence as a user's ability that users' actions (behaviors or opinions) affect their neighbors in OSNs. The extensive researches in social influence analysis pave the way for various applications, such as resource recommendation [Zhang, et al. (2018)], community detection [Al-Garadi, et al. (2018)], and viral marketing [Yang, et al. (2017)].
One essential problem in social influence analysis is to estimate influence probabilities based on action logs, and extensive works have been done on this problem [Pal, et al. (2014); Aslay, et al. (2018); Sun, et al. (2018)]. Almost all previously related work aims at calculating influence parameters for each edge in OSNs. However, since the problem of sparse observations for influence spreads, the previous works cannot accurately learn edge parameters to predict influence probabilities, especially for edges without sufficient diffusion data. Moreover, these conventional edge-based approaches cannot consider other influence factors (such as network structure and preference similarity) or detect hidden influence relationships between users (high-order influence spreads). Thus they perform poorly on the predictions of influence probabilities.
This work focuses on exploring a cross problem for multiple network embeddings and social influence prediction. Inspired by the research of network representation learning [Bai, et al. (2019);Grover, et al. (2018)], this study directly learns multiple latent vectors for each user to capture social influences, instead of estimating influence probabilities for each edge. Moreover, this work alleviates the challenge of sparse observation data via latent vectors.
To our knowledge, this may be the first study of social influence prediction that jointly captures influence spreads and multiple network embeddings.
To address the above challenges, this study developed a new end-to-end approach, Multiple Influence-to-vector (Multi-Influor), that learns multiple influence vectors for each user in social networks. The first key step to predicting social influence is how to generate multiple influence learning contexts. This work devised a new method of generating multiple influence contexts, which includes nodelevel, subnetwork-level, and global graph-level influence contexts. Then, the Multi-Influor method learns nodelevel and graph-level latent vectors based on the generated contexts (details in Section 3). Therefore, the multiple network embeddings incorporate multi-dimensional influence factors for pairwise node interactions, network structures, and global similarity comparisons.
In this study, we conducted extensive comparisons based on four large-scale datasets. The comparison results illustrate that the Multi-Influor approach outperforms several state-of-the-art baselines. Moreover, the experimental results demonstrate that the Multi-Influor approach is more practical on real-world social networks.

Preliminaries
In this study, we model each social network as a graph G = (V, E), where V denotes a user set and E denotes a set of linking edges between users. The linking edge (u, v) denotes that user u is a neighbor of user v. In addition, this study obtains diffusion episodes from action logs. The action logs contain sets of tuples in the form of (u, i, t i u ) that denotes user u performed an action related to item i at time t i u . Each item i (such as information, idea and opinion) corresponds to one diffusion episode D i = {(u, t i u ), · · · , (v, t i v )}, which denotes users in D i adopt to perform action i in a chronological order. Definition 2.1. (User Social Action). A binary action state for user u, s i u ∈ {0, 1}, is calculated based on action logs A, where s i u = 0 denotes user u has not performed the action i at time t i u , and s i u = 1 denotes user u has performed the action i before or at time t i u . Definition 2.2. (Social Influence Spread). Based on a social network G = (V, E) and diffusion episodes D i , a social influence spreads from user u to user v if it satisfies:

Problem Definition
This study aims to transfer each user's representation into a low-dimensional latent vector for social influence prediction. In general, this study attempts to learn multiple representations for |V | users based on a given social network and action logs, which are used to evaluate the influence probabilities for |E| edges.
Multiple Network Embeddings Problem. Based on a social network G = (V, E) and action logs, this work aims to learn multiple social influence representations for each user: node-level vector V ec u and graph-level vectors I u , S u , b u ,b u .

THE DEVELOPED METHOD: MULTI-INFLUOR
In this section, we proceed to detail the newly developed Multiple Influence-to-vector (Multi-Influor) method, which is an end-to-end neural network-based method that aims at addressing the challenges mentioned in Section 1. The framework of Multi-Influor ( Fig. 1) contains three parts. First, this work provides how to generate multiple influence contexts in stage 1. Second, based on the generated influence contexts, this paper presents a learning approach for multiple influence representations in stage 2. Finally, this study feeds the combined multiple vectors into a fully connected neural network to predict influence probabilities in stage 3.

Stage 1: Multiple Influence Contexts Generating
In this study, we introduce a method of generating multiple influence contexts, which includes node-level, subnetworklevel, and graph-level influence contexts. These influence contexts focus on multi-dimensional influence factors for pairwise node interactions, network structures, and global similarity comparisons. Definition 3.1. (Influence Context). Based on a social network G = (V, E) and action logs, this study defines an influence context for user u as a set of users who are probably affected by user u.
Node-level influence context Based on a social network and a given user u, the straightforward way to generate a node-level influence context for user u is to adopt the breadth-first search (BFS) method that starts from user u. Then, r-neighbours N r u = {v : d(u, v) ≤ r} can be acquired, where d(u, v) is the shortest path between user u and v. This work applies a sub-network induced by N r u to establishing a network of r-ego user u. To facilitate the neural network learning in network embeddings, we suppose to sample a fixed-size sub-network. In addition, this is easy to solve the problem of different sampling sizes.
According to network structures and edge weights estimated by diffusion episodes D i , this study performs random walks on the network of r-ego user u. A random walk iteratively traverses to neighbors with different probabilities and stops running until it collects a fixed-size of users (L N ). Then, this work regards the sampled network as a node-level influence context for user u, C ni u , that can embed pairwise nodes' interaction information into user u's latent influence vector.
Subnetwork-level influence context This work builds an influence spread network to incorporate subnetwork-level influence (high-order influence diffusion) information into latent influence vectors, which illustrates influence diffusions for each item in social networks (as shown on the left part of Fig. 1). Definition 3.2. (Influence Spread Network). Based on a social network G = (V, E) and action logs, we define an influence spread network as (2) each edge (u, v) denotes a social influence spreads from user u to v.
The Multi-Influor method captures high-order diffusion information via random walk processes on influence spread networks, which incorporates structure information into subnetwork-level embeddings. Moreover, this approach can solve the problem of influence estimating caused by sparse propagation data.
This study generates user u's subnetwork-level influence context, C si u , based on the influence spread network G i . We apply random walks with restarts to simulating users' influence diffusions. The random walk process starts from user u and randomly selects one neighbor of user u to traverse. Next, based on the currently activated users, we randomly select one neighbor of these users to traverse in the next sampling step. In addition, the process is probable to back to user u at each step. This work uses a length threshold (L S ) to limit the size of C si u and stops sampling when the threshold L S is reached.
Global graph-level influence context This study further incorporates users' preference similarities in latent influence vectors by using graph-level influence contexts. Given an influence spread network G i = (V i , E i ), users perform the same actions indicates that these users share the same interest.
To capture the similarity of users' interests, the Multi-Influor method uniformly samples a set of users (L G ) by a given user u in the influence spread network G i . Note that the samples of similar users denote the global graph-level influence context C gi u .
Multiple influence contexts generating algorithm Based on a social network G and a given user u, this work aims to generate multiple influence contexts C i u = C ni u +C si u +C gi u . To balance the contributions of these multi-level contexts, we suppose the component weights (α, β, γ) are all in the range of 0 to 1, and α + β + γ = 1.
First, this work generates the node-level influence context (L N = α · L) via random walks in the social network G. Then, the subnetwork-level influence context (L S = β · L) can be generated based on the influence spread network G i . Finally, this study uniformly samples the users in V i , and the length of the graph-level influence context L G = γ ·L. These multiple influence contexts contain three types of sampled data. The time complexity of multiple influence contexts generating algorithm is O(L), where L denotes the total length threshold for influence contexts (L = L N + L S + L G ).

Stage 2: Multiple Network Embeddings
The stage of multiple network embeddings provides an effective approach that simulates relationships between users and their multiple influence contexts. Inspired by the related work in the field of natural language processing, we apply a modified word2vec technique to learning multiple influence representations for each user in social networks [Grover, et al. (2018)].
Node-level influence representation learning This study develops a neural network-based approach that learns node-level influence vectors. Based on the node-level influence contexts, this work aims to estimate the probability of affecting user v conditional on his/her r-ego network G r v and action state of his/her r-neighbors S r v . We formulate the method of predicting the influence probability for user v after a given time interval ∆t as To calculate node-level influence probabilities, this work formulates the node-level influence prediction as a binary graph classification problem, which can be solved by maximizing the objective function as Based on the node-level influence contexts, all users learn an embedding matrix X ∈ R d×n , each column corresponding to the representation of a user in the network. Each user u i maps to his/her d-dimensional vector x ui ∈ R d using a pre-trained embedding layer. Then, this work adopts an instance normalization technique [Huang, et al. (2017)] to calculate the instance normalization for each embedding dimension d as where µ i is the mean of vectors, σ i is the variance of vectors, and is a small number for numerical stability.
With a node-level embedding for each user, this work also devises to incorporate various user-specific features into the input layer of the graph convolutional network (GCN), such as content features and demographic features [Qiu, et al. (2018)]. Aside from instance normalization vectors, this work also considers a binary variable to indicate users' action states.
In the neural network learning, we stack multiple GCN layers to conduct nonlinear transformations [Narayan, et al. (2018)]. The input of each GCN layer is a vertex feature matrix H, and the output H is calculated as where the notation A(G) denotes a n × n matrix that captures structural information for the network G, and W and b are model parameters.
Finally, this work supposes the output layer provides a two-dimension representation (V ec u ) for each user. We use the vector of user u to predict the ego user's state and the influence probability of user u. We compare the prediction results with ground truth data to optimize the objective function (Eq. (1)). Therefore, we learn a nodelevel influence vector for each user.
Graph-level influence representation learning To capture graph-level influence information, this work uses a skipgram method to generate the graph-level context for a given user u [Krishna, et al. (2019)]. The key step in graph-level influence embedding is to evaluate the probability of observing the graph-level influence context, P r(C si+gi u |u), including the contexts of subnetwork-level and global graph-level influence (C si+gi u = C si u +C gi u ). This work calculates the probability P r(C si+gi u |u) by using the independent probability P r(v|u) that influences propagate from user u to v, and the notation v denotes a user in the graph-level context C si+gi This work generates a list of (u, C si+gi u ) tuples for each diffusion episode, which is denoted as T Di . The whole influence context tuples, T , contains all the observed episodes D i in action logs A. This work attempts to maximize the log-probability of P r(C si+gi u |u). Thus, this study defines the loss function of the graph-level influence representation learning as Next, this work calculates the loss function by evaluating the probabilities that influences propagate from user u to v. The Multi-Influor method calculates the probability

Algorithm 1 Multi-Influor
Input: A social network G = (V, E), diffusion episodes D i , component weights α, β, γ, a learning rate η and the dimension of influence vector k. Output: Multiple influence representations for each user u ∈ V . 1: Initialize vectors I u and S v with uniform distribution Generate a node-level influence context C ni u ;

5:
Extract an influence spread network G i = (V i , E i ).

6:
for each user u ∈ V i do 7: Generate C si u and C gi u ; 8: Insert T Di into T . 10: Multiple influence representations learning: 11: for T Di ∈ T do 12: for v ∈ C i u do

15:
Graph-level influence vectors: I u , S v , b u ,b v ; 16: Update all parameters until convergence. 17: return V ec u , I u , S u , b u ,b u . P r(v|u) via the inner product of users' latent vectors I u · S v , where I u denotes the influence ability vector for user u and S v denotes the susceptibility vector for user v. Moreover, this work uses b u andb v to reflect the bias of influence vector for user u and the bias of susceptibility vector for user v, respectively. Therefore, this work formulates the probability that user u influences user v as a softmax function (Eq. 6). P r(v|u) = e (Iu·Sv+bu+bv) /sum(u) where sum(u) = w∈Vi e (Iu·Sw+bu+bw) is a normalization term.
To alleviate the issue of computation efficiency, the negative sampling can be used to compute the softmax function [Peng, et al. (2017)]. Then, this study uses the method of stochastic gradient descent to learn all parameters. During each step, this work updates parameters Θ via gradient calculations as where η denotes a learning rate and ∂ ∂Θ denotes the gradient of parameters Θ.

Stage 3: Influence Probability Predicting
After obtaining multiple influence representations for each user, this work uses a multi-layer fully connected neural network to gradually reduce the vector's dimension for each user. In the end, we predict the influence probability, s uv , that influences propagate from user u to v. This study compares the prediction results with ground truth data, and optimizes the log-likelihood loss function as To sum up, the Multi-Influor method incorporates the finegrained influence relationships that are captured by the node-level embedding and the coarse influence information that is captured by the graph-level embedding, which provides a thorough view of influence probability estimating to the prediction approach.
This study randomly selected 60%, 20%, 20% instances of sampling data for training, validation, and testing, respectively. The size of a mini-batch was set to be 512 across four datasets. The Multi-Influor method performed random walks with a restart probability of 0.75 in the steps of contexts sampling. Furthermore, this work set the dimension of initial vectors to be 64 in the node-level embedding, and to be 60 in the graph-level embedding. Each initial vector in the input layers was pre-trained via the autoencoder technique.
In the step of neural network learning, this work supposed the learning rate η = 0.005 and the influence vector's dimension k = 62. According to the empirical study on tuning set [Bai, et al. (2019)], the total length threshold for influence context L was set to 160, and the component weights were set as α = 0.4, β = 0.3, and γ = 0.3.

Evaluation Metrics
Prediction performance comparison. The task of influence diffusion prediction focuses on predicting predict probabilities of whether users will be influenced by seed users. This study evaluated the predictive performance for different methods in terms of precision (Prec.), recall (Rec.), F1-measure, and area under curve (AUC).
Influence spread comparison. This work used the prediction results to detect seeds and solve the influence 1 http://open.weibo.com/ maximization problem. We compared the seeds' influence, which is demonstrated by the range of influence spread. We conducted these comparisons on different datasets and used the independent cascade (IC) model to simulate influence spread processes on OSNs [Aslay, et al. (2018)].

Prediction Performance Comparison
This subsection presents the comparisons of diffusion probability predictions based on different OSNs (Table 2). In general, the Multi-Influor approach achieves significantly better performance than the conventional methods (SVM and Emb-IC) in the datasets of Sina Weibo, Epinions, and NetHEPT. The methods of Multi-Influor and Inf2vec perform best, but the Multi-Influor method performs better than the Inf2vec method in diffusion probability predictions. These may because the Multi-Influor method considers multiple network embeddings that incorporate more influence factors. However, in the dataset of WikiVote, Node2vec and Emd-IC sometimes outperform than the Multi-Influor approach.
Since the data size of WikiVote is small, the Multi-Influor approach lacks training data to improve the performance of neural network-based learning (GCN layers and fully connected neural network). Adding more sampling data in the training processes can improve the performance of Multi-Influor. These experimental results demonstrate that the Multi-Influor approach is highly data-driven.

Influence Spread Comparison
We uniformly used a greedy algorithm to detect seeds based on the prediction results [Sun, et al. (2018)]. Then, we compared the range of activated users influenced by seeds. After adding a new user to the seeds, we set the number of influence spread simulations to be 10,000. In addition, this study conducted comparisons under the conditions of different datasets and seed sizes.
In general, the comparisons of influence spread (Fig. 2) illustrate that the Multi-Influor approach always performs best, which means that it can lay a solid foundation for solving the influence maximization problem. In the datasets of Sina Weibo, Epinions, and NetHEPT ( Fig. 2  (a), (b), (d)), the Multi-Influor method performs much better than SVM and Emb-IC, and above 30% better than Node2vec. However, with much less training data in WikiVote, the approaches all perform worse than in other datasets. In WikiVote (Fig. 2 (c)), the Multi-Influor method only performs better than SVM and Emb-IC, and it achieves near performance to Node2vec and Inf2vec.

Fig. 2. Influence Spread Comparisons
The size of training data in neural networks could strongly affect the performance of Multi-Influor. However, these experimental results indicate that using more information propagation data improves the performance of the Multi-Influor approach. The real-world social networks provide extensive user data, which guarantees the performance of Multi-Influor. In other words, the Multi-Influor approach can be more practical on large-scale datasets.

CONCLUSION
This study focused on exploring a cross problem for multiple network embeddings and social influence prediction, and we developed a new end-to-end approach, namely Multi-Influor, that learns multiple network embeddings for each user in OSNs. The basic idea is to learn a neuralnetwork-based function that considers multi-dimensional influence factors. The Multi-Influor approach takes a social network and action logs as input and outputs predictive influence probabilities. The experimental results illustrate that the Multi-Influor approach performs better than other baselines on influence predictions. Moreover, Multi-Influor is a highly data-driven method that can be more practical on real-world social networks.