Abstract User identity linkage is a task of recognizing the identities of the same user across different social networks (SN). Previous works tackle this problem via estimating the pairwise similarity between identities from differ-ent SN, predicting the label of identity pairs or selecting the most relevant identity pair based on the similarity scores. However, most of these methods ignore the results of previously matched identities, which could contribute to the linkage in following matching steps. To address this problem, we convert user identity linkage into a sequence decision problem and propose a reinforcement learning model to optimize the linkage strategy from the global perspective. Our method makes full use of both the social network structure and the history matched identities, and explores the long-term influence of current matching on subsequent decisions. We conduct experiments on dif-

Xiaoxue Li College of Cyberspace Security, University of Chinese Academy of Sciences, Beijing, China Institute of Information EngineeringChinese Academy of Sciences, Beijing, China E-mail: lixiaoxue@iie.ac.cn

Yanan Cao Institute of Information EngineeringChinese Academy of Sciences, Beijing, China E-mail: caoyanan@iie.ac.cn

Yanmin Shang Institute of Information EngineeringChinese Academy of Sciences, Beijing, China E-mail: shangyanmin@iie.ac.cn

Yangxi Li National Computer network Emergency Response technical Team, Beijing, China E-mail: liyangxi@outlook.com

Yanbing Liu Institute of Information EngineeringChinese Academy of Sciences, Beijing, China E-mail: liuyanbing@iie.ac.cn

Jianlong Tan Institute of Information EngineeringChinese Academy of Sciences, Beijing, China E-mail: tanjianlong@iie.ac.cn

ferent types of datasets, the results show that our method achieves better performance than other state-of-the-art methods.

Keywords Social network, Reinforcement Learning, User Identity Linkage, Markov Decision Process

User Identity Linkage (UIL), which aims to recognize the identities (accounts) of the same user across different social platforms, is a challenging task in social network analysis. Nowadays, many users participate in multiple on-line social networks to enjoy more services. For example, a user may use Twitter and Facebook at the same time. However, on different social network platforms, the same user may register different accounts, have different social links and deliver different comments. If different social networks could be integrated together, we could create an integrated profile for each user and achieve better performance in many practical applications, such as link prediction and crossdomain recommendation. So, UIL has recently received increasing attention both in academia and industry.

Most of previous works consider UIL as a one-to-one alignment problem [6,12,34,37], i.e., each user has at most one identity in each social network. Matching models [26,25], label propagation algorithms [5,9,15,20,24,40] and ranking algorithms [12,32,34,39] are commonly used to address this task. These methods generally calculate pairwise similarity between identities and select the most relevant identity pairs according to the similarity score. In more recent works, identity similarity is computed based on user embedding [34], which encodes the main structure of social networks or other features into a low-dimensional and density vector. In most of these methods, each identity pair is matched independently, i.e., one predicted linkage of the identity pair would not be effected by any other.

However, we have an intuition that, the predicted linkages are inter-dependent and the previously matching would have a long-term influence on the subsequent one. This influence is two-fold: (i) if the preceding decisions are right, they would bring in positive auxiliary information to guide the following linkage. For example, if two user from two different social networks share the same friends (their friends have been matched), they are more likely to be matched in the subsequent linkage, as shown in Figure 1; (ii) the previously matched user identity could not be chosen in the subsequent matching process according to the one-to-one constraint [6], Although some previous label propagation based works have made primary attempts on using this influence, they just gave the fixed greedy strategy to iteratively select the candidate identity pair [15,20,24,40]. Neither of them re-calculate the pairwise similarity or dynamically adjust the linkage strategy after each matching step due to the high complexity.

In order to model this long-term influence effectively, we novelly consider UIL as a Markov Decision Process and propose a deep reinforcement learning

Fig. 1 An example of User Identity Linkage. The blue link represents friend relation in social network, and orange line represents matched identity pair. User identity sley (in Foursquare) has two candidate identities in Twitter: sley and sley 1. If considering previously matched information, sley in Foursquare is similar to sley 1 in Twitter because they share more similarity friends.

(RL) framework RLink to automatically match identities in two different social networks. Figure 2 illustrates the overall RLink process. In each time stamp, the state consists of two social network structures and previously matched identity pairs. According to the current state, the agent perform an action, i.e., generating an identity pair from the candidates. After performing the action, the state would be changed at the next time and a reward would be fed back to the agent to adjust its policy. Because the action space is large and dynamic in the UIL process, we adapt an Actor-Critic framework, in which the Actor network generates a deterministic action based on current state and the Critic network evaluates the quality of this action-state pair. Concretely, for each state, the Actor firstly encodes the network structure and history decisions to a latent vector representation, and then decodes this vector into an action in the identity embedding space. Based on this, our model could generate the matching sequence automatically. Deep RL model, which learns to directly optimize the overall evaluation metrics, works much better than models which learn with loss functions that just evaluate a particular single decision [10,37]. However, there has been spots of attempts on applying RL in the social network analysis field [8,29,23]. To the best of our knowledge, we are the first to design a deep RL model for user identity linkage. And in this paper, our RL model is able to produce more accurate results by exploring the long-term influence of independent decisions. The contributions of this paper can be summarized as follows:

– We are the first to consider UIL as a sequence decision problem and innovatively propose a deep reinforcement learning based model in this task, which generates the matching sequence automatically.

– The proposed model makes full use of the previous matched identity pairs which may impact on the subsequent linkage, and makes decisions from a global perspective.

Fig. 2 A Procedure of Reinforcement Learning based User Identity Linkage. The blue link represents friend relation in social network, and orange line at represents matched identity pair. At time i, agent generates a pair of matching identities as action according to current state. After environment performs this action, the state would be changed at time i + 1 and next action can be generated based on

– We conduct extensive experiments on three pairs of real-word datasets to show that our method achieves better performance than other state-of-the-art solutions to the problem.

2.1 Preliminary

Let G = (V, E) represents an online social network, where is the set of user identities and is the set of links in the network. Given two online social network (original network) and (target network), the task of user identity linkage is to identify hidden user identities pairs across and . Here, we have a set of node pair between and to represent given alignment information (ground-truth), denoted as B

In this work, we consider UIL task as a markov decision process in which the linkage agent interacts with environment over a sequence of steps. We use to denote the current state, which consists of the network structure and matched identity pairs. Action, which is denoted as , is a pair of identities. The action space of UIL is comprised of all potential identity pairs, the size of which is . At each step, the agent generates an action a based on s, and would receive a reward r(s, a) according to the given alignment information. The goal of RL is to find a linkage policy , which can maximize the cumulative reward for linkage.

Due to the large and dynamic action space, the policy-based RL [4,7] which compute probability distribution of every action and the Q-learning [17,31] which evaluate the value of each potential action-state pair are time-consuming. To reduce the computational cost, we adapt the Actor-Critic framework, where the actor inputs the current state s and aims to output a deterministic action, while the critic inputs only this state-action pair rather than all potential state-action pairs. The architecture of the Actor-Critic network is shown in Figure 3.

Fig. 3 The framework of Actor-Critic network, where the actor is comprised of an Encoder- Decoder architecture and the critic is DQN. The inputs of Actor are history identity pairs and network structure, where history identity pairs were generated by our Actor-Critic network before current epoch (See Eq.(4)). Remarkably, is a zero vector. Then this action and current state are input onto the Critic to evaluate the quality of this action.

2.2 Architecture of Actor Network

The goal of our Actor network is to generate an action (one matching identity pair) according to the current state. We propose an Encoder-Decoder architecture to achieve this goal.

2.2.1 Encoder for Current State

Encoder aims to generate the representation of current state, which contains two types of information: network structure and previous matched identity pairs. In order to integrate these information, we apply two encoding mechanisms to respectively encode the network structure and the matched pairs, as shown in Figure 3.

sional and dense vector, which is denoted as and (d is the dimension of the identity embedding). These identity embeddings are pre-trained by Node2vec [1]. To represent the social network structure, we weighted sum all identity embedding to generate the network embedding e, which is inspired by [13].

where denotes the weight of the identity . Here, we define as (similar to [13]), where is a constant and ) represents the degree of identity . We denote the representation of original network and target network as and , then we concatenate them to get and . That is:

At time t, we need to encode all previously matched identity pairs from time 1 to 1, i.e., an action sequence , ..., . In each action ([11]), the identity from are respectively denoted as and , and their embedding representation are denoted as and . Besides, we take the feedback of , which is denoted as , into account. is a one-hot vector, in which the value of each dimension is equal to the immediate reward at the corresponding time stamp. Through a neural network layer, we get the encoding vector of as :

where and , and is equal to the number of steps in each episode and depends on the dimension of .

Then, we get the representation of one history matched pair at time i by concatenating and :

where the dimensional of is |G| + 2d.

In order to capture the long-term influence of the previously matched pairs, we use a Long Short-Term Memory (LSTM) network to encode the history linkage sequence into a fixed-size vector:

Furthermore, to distinguish different contribution of the previous actions, we employ attention mechanism [2], which allows model to adaptively focus on different parts of the input: -0.5em

where the dimension of is equal to , and we leverage a location-based attention mechanism[16] to compute from the hidden state

Then, the embedding of current state can be represented as follows:

where and represent the embedding of history matching information and network structure respectively.

It is noteworthy that, at time 1, the current state just contains two social network structures because there is not matched identity pair. That is to say, = 0, is equal to zero vector and is equal to .

Note that, the decoded and maybe not in the identity embedding space. Thus we need to map them into the real embedding space via the transformation [38]. As mentioned above, the action space is very large. In order to correctly map into the validate identity, we select the most similar as the valid identity-embedding. In this work, we compute the cosine similarity to get the valid identity in given networks:

where represents the valid identity pair . We pre-compute the value of and to decrease the computational cost. Since the right align- ment identities could be chosen in the following steps, we ignore those identities if they are correctly matched in the previous steps.

2.2.2 Reward

The agent generates the new identity pair and receives the immediate reward from networks, which is also the feedback of this identity pair,

where Groundtruth is a set of known aligned identity pairs. Since current action result has a long-term impact on subsequent decisions, we introduce a discount factor to metric the weight of reward:

where represents how much influence the action will generate on the following steps. Simply, is defined as , where t represents the current time stamp.

2.3 Architecture of Critic Network

Critic Network aims to judge whether the action generated by Actor suits the current state . Generally, the Critic is designed to learn an action-value function Q(s, a), while the actor updates its’ parameters in a direction of improving performance to generate next action according to Q(s, a) in the following steps. However, in real UIL, the state and action space is enormous and many state-action pairs may not appear in the real traces, which makes it hard to update their Q-values. Thus, we choose Deep Neural Network as an approximator to estimate the action-value function. In this work, we refer to a neural network as Deep Q-value function (DQN)[35].

Firstly, we need to feed user’s current state s and action a into the DQN. To generate user’s current state s, the agent follows the same strategy from Eq.(1) to Eq.(6). As for action a, we utilize the same strategy in decoder to compute a low-dimensional dense action vector a. Then, this action is evaluate by the DQN, which returns the Q-value of this state-action pair Q(s, a).

2.4 Training and Test

Generally, we utilize DDPG[14] algorithm to train the proposed Actor-Critic framework, which has four neural network: critic, actor, critic-target and actortarget, where target networks are the copy of critic and actor respectively. The critic is trained by minimizing the mean squared error loss with the corresponding target given by:

where is the discount factor in RL, R is the accumulative reward and is the previous state, ) = . Besides, and represent all parameters in Critic and Actor respectively, and represents the policy. The Critic is trained from samples stored in a replay buffer[18]. Similarity, actions also stored in the replay buffer generated by the strategy in Actor decoder section. This allows the learning algorithm to dynamic leverage the information of which action was actually executed to train the critic.

The first term )) in Eq.(9) is the output of target, namely y, for current iteration. And parameters from the previous iteration are fixed when optimizing the loss function ). Computing the full expectations’ gradient are not efficient. Thus, we optimize the loss function by Stochastic Gradient Descent (SGD). The derivatives of loss function ) with respective to parameters are presented as follows:

The Actor is updated by using the policy gradient:

The training algorithm for the proposed framework RLink is presented in Algorithm 1. In each iteration, there are two stages, i.e., 1) generating an action (lines 8-11), and 2) parameter updating (lines 13-17). For generating an action, given the current state , the agent firstly encode current state as a vector (line 8) and then generate a pair of nodes according to this vector (line 9); then the agent observes the reward and update state to (line 10); finally the agent stores transitions (+1)) into replay buffer D. For the parameter updating stage: the agent samples mini-batch of transitions () from D (line 13), and then updates parameters of Actor and Critic following a standard DDPG procedure (lines 14-16). Finally, the parameters of target network and is updated via the soft update way (line 17).

To evaluate the performance of our model, the test procedure is designed as an online test method, which is similar to the action generation stage in the training procedure. After the training procedure, proposed framework RLink learns parameters and . In each iteration, the agent generates a pair of identity following the trained policy . And then the agent receives the reward from networks and updates the state to .

In this section, we compare our RLink with the state-of-the-art methods on types of cross-network datasets.

3.1 Experiment Setup

3.1.1 Datasets

In order to verify our method in different types of networks, we conduct experiments on the following network collections: Foursquare-Twitter, Last.fmMyspace and Aminer-Linkedin, which are commonly used in the UIL task. The first dataset is provided by [36] and others are are collected by[37]. These datasets are introduced as follows and the statistic information is shown in Table 1 which only contain social links as user identities’ feature.

– Foursquare-Twitter is a pair of social networks, where users share their current location and other information with others.

– Last.fm-Myspace is a pair of online social networks, where users could search music and share their interested music with others.

Table 1 Statistics of experimental datasets

– Aminer-Linkedin is a pair of citation networks where contains users’ academic achievements and users could search interested community.

3.1.2 Comparative Methods

In this section, to evaluate the performance of RLink for user identity linkage, we choose the following state-of-the-art methods as competitions, including:

– IONE [12] IONE predicts anchor links by learning the followership embedding and followeeship embedding of a user simultaneously.

– DeepLink [39] DeepLink employs unbiased random walk to generate embeddings, and then use MLP to map users.

– MAG [32] MAG uses manifold alignment on graph to map users across networks.

– PAAE [43] PAAE employs an adversarial regularization to capture the robust embedding vectors and maps anchor users with an alignment autoencoders.

– SiGMa [10] SiGMa was designed to align two given network by propagating the confidence score in the matching network. We use the name matching method to generate the seed set and utilize the output scores of SVM as the pairwise similarity. Note that SiGMa is an unsupervised method.

– SDM: This method is a simpler deep model, which is similar to typical sequence prediction methods [3,11] and utilizes LSTM to process sequence matching. The matching sequence is generated via ranking the similarity of embedding. At each step i, LSTM predicts an user identity in Target SN based on current user identity embedding and previous hidden information (). Finally, the L2 loss would guide the training and testing process of this model.

3.1.3 Evaluation Metrics

To perform the user identity linkage, we utilize two standard metrics [27] to evaluate the performance, including Precision@k (P@k), recall and MAP. Note that higher the value of each these measures, the better the performance.

Precision@k is the metric for evaluating the linking accuracy, defined as:

where measures whether the positive matching identity exists in ) list, and n is the number of testing anchor nodes.

The recall is the fraction of the number of real corresponding user pairs that have been found over the total amount of real matched user pairs (Groundtruth B).

MAP is used for evaluating the ranking performance of the algorithms, defined as:

where ra is the rank of the positive matching identity and n is the number of testing anchor nodes.

3.1.4 Hyper-parameter setting

For each pair of networks, we first resort the ground truth data set by identity number and then use the first r as the training data and the later 1 as the testing data, where r means the training ratio. The dimension of the identity embedding is set to 128, whether the input of the encoder or the output of the decoder, i.e., |U| = |G| = 128. And the weighting parameter is fixed to 10. For parameters in Actor, the number of LSTM cell units is set to 256 and batch size is 64. In Critic, the number of hidden layer is 4. The batch size in replay buffer is 64 and we set 200 sessions in each episode. Besides, in training procedure, we set learning rate = 0.001, discount factor = 0.9, and the rate of target networks soft update = 0.001.

3.2 Comparisons and Analysis

We compare our proposed model RLink with the following recent user identity linkage methods. Note that SiGMa, SDM and RLink are prediction methods which determine whether two user identities from original and target are matching or not. Therefore, the evaluation of those methods becomes P@k = P@1 = MAP. From Table 2, we can see that:

– RLink is significantly better than previous user identity linkage methods. This result demonstrates that our method which considers UIL as a sequence decision problem and makes decisions from a global perspective is useful. Besides, reinforcement learning based methods, which learns to directly optimize the overall evaluation metrics, works better than other deep learning methods, such as DeepLink and PAAE.

Table 2 Performance comparison on user identity linkage

– SDM and SiGMa achieve higher precision than other baselines, which demonstrates that considering the influence of previous matched information is beneficial for UIL task. Although SigMa achieves the highest precision on Last.fm-Myspace, it suffers from a lowrecall due to its fixed greedy matching strategy. By contrast, SDM and RLink promotes about 30% and 40% recall over SigMa on respectively, which proves previous matched result has a long-time impact on the following matching process.

– IONE, PAAE and DeepLink perform better than MAH and MAG, which means that considering more structural information, such as followership/ followee-ship and global network structure, could achieve higher precision. Besides, the precision of PAAE and DeepLink are higher than IONE, which demonstrates that considering global network structure and utilizing deep learning model could improve the performance of UIL.

– Besides, we note that all methods perform better on Aminer-Linkedin than they do on Last.fm-Myspace, maybe because the scale of the training data in Aminer-Linkedin is larger.

3.3 Discussion

3.3.1 Parameter Sensitivity

In this section, we analyze the sensitivity of three parameters which are differ-ent K in P@K, training ratio r and embedding dimension d. The performance of those parameters on all three testing datasets is similar. We present the performance on Twitter-Foursquare due to the limited spaces.

Precision on different K. For different K in P@K, we reports the precision of different methods on variable K between 1 and 30. RLink outperforms all the comparison methods consistently and significantly given different @K settings. IONE performs better than MAG and MAH, showing that constructing the incidence matrices of the hypergraph could fail to differentiate the follower-ship and followee-ship. Both RLink and DeepLink perform better than MAG, MAH and IONE, showing that deep learning methods could

Fig. 4 Detailed Performance Comparison on Twitter-Foursquare Dataset

extract more node feature for UIL than traditional methods. The precision of most of the testing methods grow increase significantly with the increase of K until K = 20, indicating that most of ranking methods achieve matched identity in 20.

we reports the Precision@30 of different methods on variable training ratio between 10% and 90%. RLink outperforms all the comparison methods when the ratio rose to 60%. The ratio of anchor nodes used for training greatly affects the performance of RLink. Especially for ratio settings as 60% to 70%, the performance enhancement is significant. While the result shows that with the increase of training data, the precision of UIL firstly increases significantly and then does not increase drastically as the ratio rose to 70%. And the comparative methods achieve good performance when the training ratio is setting around 90%, which demonstrates the robust adaptation of our method RLink. Besides, from Figure 4b, we found that DeepLink performs better than RLink when the training ratio is less then 40%, indicating that RLink might need more train dataset than DeepLink.

4c, both MAG and MAH achieve good performance when the dimensionality setting is around 800, while RLink, IONE and DeepLink achieve good performance when the dimensionality is around 100. The complexity of the learning algorithm is highly depending on the dimensionality of the subspace. And low dimensional representation also leads to an efficient relevance computation [12]. Therefore, we conclude that RLink, IONE and DeepLink is significantly more effective and efficient than MAH and MAG. Besides, RLink achieves the best results when the dimensionality setting is bigger than 80.

3.3.2 Evaluation of Actor-Critic Framework

In this paper, we use DDPG algorithm to train the RLink model. To evaluate the effectiveness of the Actor-Critic framework, we compare the performance of DDPG with DQN. From Figure 5, we can see that DQN performs similar to DDPG, but the training speed of DQN is much slower. As shown in Figure5 (a), DQN needs 1200 episodes to converge, which is almost four times of the episodes DDPG needs. In Linked-Aminer, as shown in Figure5(b), both DDPG and DQN need more training episodes, i.e., 750 and 2000 episodes respectively, when the size of action space rose to 41534153. Besides, DQN performs worse than it does in Last.fm-Myspace, which demonstrates that DQN is not suitable for the large action space. In summary, DDPG achieves better performance and faster training speed than DQN, which indicates that Actor-Framework is suitable for UIL with enormous action space.

Fig. 5 Comparison between DDPG and DQN: The x-axis shows the training episodes. The y-axis shows the total reward of each episode. Red line represents DDPG and green Line is DQN.

3.3.3 Effect of Long-term Reward

To evaluate the effectiveness of long-term reward, we compare it with an immediate reward via Q-value performance. Q-value performance is a judgment of whether a suits s. From Figure 6, we can find that both long-term and immediate reward would converge to a similar value, but the Q-value of immediate reward is increased first and then decreased. The higher Q-value in the training procedure indicates that the immediate reward may get trapped in a local optimum. By contrast, the long-term reward makes our model make decisions from a global perspective and the Q-value smoothly converge.

3.3.4 Effectiveness of RLink Components

This experiment is designed to validate the effectiveness of main components in the Actor network, including the input features, attention layer, LSTM layer, action transformer and decoder. We systematically eliminate the corresponding component and define the following variants of RLink.

– (RLink with LINE as pre-trained embedding method): In this variant, we replace the pre-trained embedding method Node2vec by LINE[33] to evaluate the diversity of different pre-trained identity embeddings.

Fig. 6 Q-value performance with different reward on Last.fm-Myspace and Linkedin- Arminer. The x-axis shows the training episodes. The y-axis shows the normalize Q-value of each session. The value of immediate reward is equal to 11, while long-term reward is

– RLink-FEED (RLink without feedback information): This variant is to evaluate the feedback fed into the Encoder. So, we just use the representation of matched identity pair as the history matching information.

– RLink-LSTM (RLink without LSTM layer): This variant is to evaluate the contribution of LSTM layer. We replace the LSTM layer by simple fully-connected layer.

– RLink-ATT (RLink without attention machine): This variant is to evaluate the contribution of the attention layer. So, we remove the attention machine after the LSTM layer.

– RLink-TRANS (RLink without transformer layer): In this variant, we replace the action transformer component by fully-connected layer to evaluate its effectiveness.

– (RLink utilizes MLP as decoder): In this variant, we replace the single neural network (NN) layer in the decoder by MLP to evaluate the effective of NN layer.

The result is shown in Table 3. We can find that adapt LINE to pre-train user identity embedding vectors, which achieves similar performance to RLink. This phenomenon indicates that the pre-trained identity embeddings could not have great influence on the performance of UIL. RLinkFEED performs the worst among all variants, which demonstrates that the feedback information significantly promotes the performance of our model. RLink-LSTM performs worse than RLink, which suggests that capturing the long-term memory of the history matched information by LSTM is very ben-eficial for the subsequent matching. RLink-ATT proves that incorporating attention mechanism can better capture the influence of each previous decision than only LSTM. RLink-TRANS proves that action transformer could map and exactly. proves that simply neural network in the decoder phase could perform better than more complicated model (MLP).

Table 3 Performance on different RLink components

RLink outperforms all its variants, which indicates the effectiveness of each component for UIL.

In this section, we briefly introduce previous researches related to our study, including user identities linkage and reinforcement learning.

4.1 User Identities Linkage

Previous UIL works consider UIL as a matching problem, or utilize classifica-tion models and label propagation algorithms to tackle this task. Matchingbased methods build a bipartite graph according to affinity score of each candidate pair of identities and achieves one-to-one matching for all user identity pairs based on this bipartite graph [25,26]. The basic principle is Stable Marriage Matching. Classification-based models classify whether each candidate matching is correct or not. Commonly used classifiers include Naive Bayes, Decision tree, Logistic regression, KNN, SVM and Probabilistic classifier[5,22, 21,34]. Label-Propagation based methods discover unknown user identity pairs in an iterative way from the seed identity pairs which have been matched[9,15, 20,24,40]. Some recent works prefer to combine above methods, for example, [37] computes local consistency based on matching model and applies label propagation for global consistency.

With the development of network embedding and deep learning, embedding based methods and deep learning models have been utilized to solve UIL problem. Embedding based methods embed each identity into the low-dimensional space which preserve the structure of network firstly, and then align them via comparing the similarity between embedding vectors across networks [34,32, 39,19]. However, those two-step methods needs two subject which is difficult to optimize. [12] proposes an unified framework to address this challenge, where the embeddings of multiple networks are learned simultaneously subject to hard and soft constraints on common users of the network. [41] introduces an active learning method to over the sparsity of labeled data, which utilizes the numerous unlabeled anchor links in model building. Finally, inspired by the recent successes of deep learning in different tasks, especially in automatic feature extraction and representation, [39] propose a deep neural network based algorithm for UIL.

4.2 Reinforcement Learning

Reinforcement Learning (RL) is one of the most important machine learning methods, which gets optimal policy through trail-and-error and interaction with dynamic environment. Generally, RL contains two categories: modelbased and model-free. And the most frequently used method is model-free reinforcement learning methods which can be divided into three categories: Policybased RL, Q-learning and Actor-Critic. The policy-based RL [4,7] learns the policy directly which compute probability distribution of every action. The Q-learning [17,31] learns the value function which evaluate the value of each potential action-state pair. And Actor-Critic [38,30] learns the policy and value function simultaneously which aims to evaluate the quality of a deterministic action at each step.

Recently, due to various advantages of RL, it has been successfully applied in many fields, such as Game [17,28], Computer Vision [42] and Natural Language Processing [4]. However, due to the complexity of online social network analysis tasks, works based on RL is less than in other fields. [29] is an early work based on reinforcement learning in social network which argues modeling network structure as dynamic increases realism without rendering the problem of analysis intractable. Existing methods utilize DQN or Q-learning framework, such as [8] applies DQN to address Graph Pattern Matching problem and [23] applies Q-Learning to search expert in social network. Inspired by the above works, we consider UIL as a markov decision problem and apply the reinforcement learning framework. However, computing Q-value of each identity pair is time-consuming. So, we adapt Actor-Critic framework to address UIL in this paper.

In this paper, we consider user identity linkage as a sequence decision problem and present a reinforcement learning based model. Our model directly generate a deterministic action based on previous matched information via Actor-Critic framework. By utilizing the information of previously matched identities and the social network structures, we can optimize the linkage strategy from the global perspective. In experiments, we evaluate our method on Foursquare-Twitter, last.fm-Mysapce and Linkedin-Aminer datasets, the results show that our system out performs state-of-the-art solutions. There are many other information in the network, such as user attribute information, and the links in the network is varied, such as AP (Author-Paper) and PC (Paper-Conference). Therefore, in the future, we would utilizes those attribute information and varied links in our model to address the UIL task.

1. Jure Leskovec Aditya Grover.2016. node2vec: Scalable Feature Learning for Networks.In KDD.

2. Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio.2014. Neural Machine Trans- lation by Jointly Learning to Align and Translate. CoRR abs/1409.0473(2014).

3. Georg Dorffner, Horst Bischof, and Kurt Hornik (Eds.).2001. Artificial Neural Networks- ICANN 2001, International Conference Vienna, Austria, August 21-25, 2001 Proceedings. Lecture Notes in Computer Science, Vol.2130.Springer.

4. Zheng Fang, Yanan Cao, Qian Li, Dongjie Zhang, Zhenyu Zhang, and Yanbing Liu. 2019. Joint Entity Linking with Deep Reinforcement Learning.InThe World Wide Web Conference, WWW 2019, San Francisco, CA, USA, May 13-17, 2019.438447.

5. Oana Goga, Howard Lei, Sree Hari Krishnan Parthasarathi, Gerald Fried land, Robin Sommer, and Renata Teixeira.2013. Exploiting innocuous activity for correlating users across sites. In WWW.

6. Qi He, Arun Iyengar, Wolfgang Nejdl, Jian Pei, and Rajeev Rastogi (Eds.).2013. 22nd ACM International Conference on Information and Knowledge Management, CIKM13, San Francisco, CA, USA, October 27 - November 1, 2013.ACM.

7. Minghao Hu,Yuxing Peng,Zhen Huang,Xipeng Qiu,Furu Wei,and Ming Zhou.2018. Re- inforced Mnemonic Reader for Machine Reading Comprehension. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden.40994106.

8. Hiroki Kanezashi, Toyotaro Suzumura, Dario Garcia-Gasulla, Minhwan Oh, and Satoshi Matsuoka. 2018. Adaptive Pattern Matching with Reinforcement Learning for Dynamic Graphs. In 25th IEEE International Conference on High Performance Computing, HiPC 2018,.

9. Nitish Korula and Silvio Lattanzi. 2014. An ecient reconciliation algorithm for social networks. VLDB (2014).

10. Simon Lacoste-Julien, Konstantina Palla, Alex Davies, Gjergji Kasneci, Thore Grae- pel, and Zoubin Ghahramani. 2013. SiGMa: Simple Greedy Matching for Aligning Large Knowledge Bases.In KDD.

11. Guillaume Lample, Miguel Ballesteros, Sandeep Subramanian, Kazuya Kawakami, and Chris Dyer. 2016. Neural Architectures for Named Entity Recognition.In NAACL HLT 2016, The 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, San Diego California, USA, June 12-17, 2016.260270.

12. Liu Li, William K.Cheung, Li Xin, and Lejian Liao. 2016. Aligning Users across Social Networks Using Network Embedding. In IJCAI.

13. Sanjeev AroraYingyu Liang and Tengyu Ma.2017. A SIMPLE BUT TOUGH-TO-BEAT BASELINE FOR SENTENCE EMBEDDINGS. ICLR (2017).

14. Timothy P.Lillicrap, JonathanJ.Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yu- val Tassa, David Silver, and Daan Wierstra.2015. Continuous control with deep reinforcement learning. CoRR (2015).

15. Siyuan Liu, Shuhui Wang, Feida Zhu, Jinbo Zhang, and Ramayya Krishnan.2014. HYDRA:Large-scale social identity linkage via heterogeneous behavior modeling. In SIGMOD.

16. Thang Luong, Hieu Pham, and ChristopherD.Manning. 2015. Effective Approaches to Attention-based Neural Machine Translation. In EMNLP. 14121421.

17. Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin A.Riedmiller. 2013. Playing Atari with Deep Reinforcement Learning. CoRR abs/1312.5602 (2013).

18. Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin A. Riedmiller, Andreas Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, ShaneLegg, and Demis Hassabis. 2015. Human-level control through deep reinforcement learning. Nature (2015).

19. Xin Mu, Feida Zhu, EePeng Lim, Jing Xiao, and ZhiHua Zhou. 2016. User Identity Linkage by Latent User Space Modeling. In Acm Sigkdd International Conference on Knowledge Discovery Data Mining.

20. Arvind Narayanan and Vitaly Shmatikov. 2009. De-anonymizing Social Networks. In IEEE Symposium on Security Privacy.

21. Howard Lei Renata Teixeira Oana Goga, Daniele Perito and Robin Somme.2013. Large- scale correlation of accounts across social networks. (2013).

22. Olga Peled, Michael Fire, Lior Rokach, and Yuval Elovici. 2013. Entity Matching in Online Social Networks. In International Conference on Social Computing, SocialCom,.

23. Farzad Peyravi, Vali Derhami, and Alimohammad Latif. 2015. Reinforcement learning based search (RLS) algorithm in social networks. In International Symposiumon Artificial Intelligence Signal Processing.

24. Lei Tang Reza Zafarani and Huan Li.2015. User identication across social media. TKDD (2015).

25. Christopher Riederer, Yunsung Kim, Augustin Chaintreau, Nitish Korula, and Silvio Lattanzi. 2016. Linking Users Across Domains with Location Data: Theory and Validation. In WWW.

26. Irina Taranu Sebastian Labitzke and Hannes Hartenstein. 2011. What your friends tell others about you: Low cost link ability of social network proles. (2011).

27. Kai Shu, Suhang Wang, Jiliang Tang, Reza Zafarani, and Huan Liu. 2016. User Identity Linkage across Online Social Networks: A Review. SIGKDD (2016).

28. David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Vedavyas Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy P. Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis.2016. Mastering the game of Go with deep neural networks and tree search. Nature 529,7587(2016),484489.

29. Brian Skyrms and Robin Pemantle. 2009. A Dynamic Model of Social Network Forma- tion.

30. RichardS. Sutton and Andrew G. Barto. 1998. Reinforcement learning an introduction. MITPress. http://www.worldcat.org/oclc/37293240

31. Nima Taghipour and Ahmad A. Kardan. 2008. A hybrid web recommender system based on Q-learning. In Proceedings of the 2008 ACM Symposium on Applied Computing (SAC), Fortaleza, Ceara, Brazil, March 16-20, 2008.11641168.

32. Shulong Tan, Ziyu Guan, Deng Cai, Xuzhen Qin, JiajunBu, and Chun Chen.2014. Mapping Users across Networks by Manifold Alignment on Hypergraph. In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, July27-31, 2014, Qubec City, Qubec, Canada. 159165.

33. Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei.2015. LINE:Large-scale Information Network Embedding. In Proceedings of the 24th International Conference on World Wide Web, WWW 2015, Florence, Italy, May 18-22, 2015.10671077.

34. Man Tong, Huawei Shen, Shenghua Liu, Xiaolong Jin, and Xueqi Cheng. 2016. Predict anchor links across social networks via an embedding approach. In IJCAI.

35. Mnih Volodymyr, Kavukcuoglu Koray, Silver David, Andrei A Rusu, Veness Joel, Marc G Bellemare, Graves Alex, Riedmiller Martin, Andreas K Fidjeland, and Ostrovski Georg. 2015. Human-level control through deep reinforcement learning. Nature (2015).

36. Jiawei Zhang and Philip S. Yu. 2016. PCT: Partial Co-Alignment of Social Networks. In International Conference on World Wide Web.

37. Yutao Zhang, Jie Tang, Zhilin Yang, Jian Pei, and Philip S. Yu. 2015. COSNET: Con- necting Heterogeneous Social Networks with Local and Global Consistency. In KDD.

38. Xiangyu Zhao, Long Xia, Liang Zhang, Zhuoye Ding, Dawei Yin, and Jiliang Tang. 2018. Deep reinforcement learning for page-wise recommendations. In Proceedings of the 12th ACM Conference on Recommender Systems, RecSys 2018, Vancouver, BC, Canada, October 2-7, 2018. 95103.

39. Fan Zhou, Lei Liu, Kunpeng Zhang, Goce Trajcevski, Jin Wu, and Ting Zhong. 2018. DeepLink: A Deep Learning Approach for User Identity Linkage.In2018 IEEE Conference on Computer Communications, INFOCOM 2018, Honolulu, HI, USA, April 16-19, 2018.13131321.

40. X.Zhou, X.Liang, H.Zhang, and Y.Ma. 2016. Cross-Platform Identification of Anony- mous Identical Users in Multiple Social Media Networks. IEEE Transactions on Knowledge and Data Engineering (2016).

41. Junxing Zhu, Jiawei Zhang, Quanyuan Wu, Yan Jia, Bin Zhou, Xiaokai Wei, and Philip S. Yu. 2017. Constrained Active Learning for Anchor Link Prediction Across Multiple Heterogeneous Social Networks. Sensors 17,8(2017),1786.

42. Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and QuocV.Le. 2017. Learning Trans- ferable Architectures for Scalable Image Recognition. (2017).

43. Shang, Y.; Kang, Z.; Cao, Y.; Zhang, D.; Li, Y.; Li, Y.; and Liu, Y. 2019. PAAE: A unied framework for predicting anchor links with adversarial embedding. In IEEE International Conference on Multimedia and Expo, ICME 2019, Shanghai, China, July 8-12, 2019, 682687.