Deep Active Learning for Anchor User Prediction

1 Introduction

Social network users often join multiple social networks to obtain versatile services. For example, a user can be simultaneously active in both Foursquare and Twitter. These users are often termed as anchor users who often generate rich data for cross-network analysis. Advanced services for anchor users include cross-network recommendation [Li and Lin, 2014], link prediction [Zhang et al., 2013] and information diffusion analysis [Peng et al., 2013]. However, crossnetwork data generated from the anchor users are difficult to collect, because these users rarely use the same identities in different social networks, which poses difficulties for advancing cross network applications. Therefore, identifying anchor users across multiple social networks has attracted increasing research interests in recent years [Man et al., 2016].

∗Contact Author

To identify anchor users, previous work [Liu et al., 2013; Riederer et al., 2016] try to collect and combine users' demographic data and daily-generated content data for estimation. For example, they often combine users' registration profile data such as names, genders and locations, and their dailygenerated tweets, posts, blogs, reviews and ratings for analysis. However, it is difficult to obtain sufficient and correct demographic data and daily generated content data for prediction. As a result, the prediction accuracy of anchor users is often unstable and unsatisfactory.

Recently, researchers turn to social link data to predict anchor users [Liu et al., 2016; Man et al., 2016], because social link data, compared to demographic data and daily-generated content data, are much more reliable in terms of correctness and completeness. Existing works that use network structures for anchor user prediction can be divided into three categories, the unsupervised, supervised and semi-supervised models [Shu et al., 2017], according to whether or to what extent the anchor user data can be observed and collected before model training.

The unsupervised models are proposed to solve unlabeled social structure data. These methods are proved to be equivalent to the network alignment problem [Singh et al., 2007; Klau, 2009; Kollias et al., 2012], which falls into the NPhard combinatorial optimization. As a consequent, these approaches are either limited to small networks or only applicable to large but sparse networks [Man et al., 2016]. The supervised models are used for predicting anchor users with training labels, which often generate accurate results when the number of labeled anchor users are adequate [Kong et al., 2013; Man et al., 2016]. Last but not least, the semisupervised models can leverage both labeled and unlabeled training data for model training. Note that in semi-supervised models the unlabeled anchor users can be predicted during the learning process [Tan et al., 2014; Liu et al., 2016].

Obviously, the number of labeled anchor users plays a critical role in building an accurate anchor user prediction model. In order to reduce the number of training examples, Active Learning (AL) has been widely used to label training examples by iteratively selecting the most informative data for labeling at each round [Settles, 2009]. In this paper, we wish to design an economic anchor user prediction model based on the active learning method. To reduce the cost of labeling user pairs in social networks, we need to address the following challenges:

• Challenge 1. In this paper, active learning algorithm builds on non-independently and identically distributed data. Our anchor user prediction problem needs to consider social structure data obtained from multiple networks where both anchor and non-anchor user pairs exist.
• Challenge 2. The anchor user pairs and the non-anchor user pairs are interlocked (or correlated). The interlock means that if (viA, vm B ) is a pair of anchor users, (viA, vm′ B ) and (vi′A, vm B ) are unlikely to be a pair of anchor users when i ̸= i′ and m ̸= m′ . Hence, the query strategy of active learning should consider the interlock property among all the unlabeled user pairs.
• Challenge 3. There are two components in the anchor user prediction framework, i.e., the active sampling component and the anchor user prediction component. How to iteratively reinforce the two components and minimize the labeling cost is non-trivial.

To address the above challenges, we present a Deep Active Learning model for Anchor User Prediction (DALAUP for short). The framework of the proposed method is illustrated in Fig. 1. From this figure, we can observe the three key components of the DALAUP method, i.e., the anchor user prediction component, the query strategy component and the user pair selection component. To solve Challenge 1, DALAUP uses a couple of convolution and deconvolution networks with shared-parameter to jointly analyze multiple social networks and obtain the representation vectors for cross-network user pairs, where structure information from both singlenetwork and cross-network are jointly considered. To solve Challenge 2, in the query strategy component, DALAUP uses three different criteria for active learning query, i.e., the cross network structure aware information entropy, the cosine similarity and the expected error reduction. To solve Challenge 3, DALAUP adaptively selects user pairs by ensembling the three query methods to estimate the most informative user pairs for labeling. The main contributions of this work are summarized as follows,

• We are the first to study the problem of active learning for anchor user prediction across multiple social networks, where user data are non-i.i.d. distributed.
• We propose a new model DALAUP by integrating active sampling and anchor user prediction. Based on the rewards of the two components, they can reinforce each other via updating parameters iteratively.
• We conduct experiments on real-world data sets to verify the performance of DALAUP. The results demonstrate the effectiveness of our model compared with the stateof-the-art.

Anchor User Prediction

2 Preliminaries

Given two users in two different social networks, if they share the same identity in the real-world, we call them as an anchor user pair. The anchor user prediction aims to find out these anchor user pairs.

Formally, given two social networks represented as GA = (VA, EA) and GB = (VB, EB), where VA, VB are two sets of users, and EA = {(viA, vjA)}, EB = {(vm B , vnB )} are two sets of undirected edges. Denote the sizes NA = |VA| and NB = |VB|. Let L = {(viA, vm B )} denote a labeled set of pairs of anchor (or non-anchor) users, where viA ∈ GA and vm B ∈ GB. Let U = {VA ⊗ VB - L} denote an unlabeled set, where ⊗ is the Cartesian product. We wish to design an active anchor user prediction model which selects a small portion of pairs of users from U. Then, based on the labeled pairs of users, we can build accurate prediction models for anchor users.

In the active learning, we aim to design a set of query functions {φqs(vA, vB)} and a selection function of pairs of users which can select a small portion of pairs of users {(v∗A, v∗B )} from U for labeling. This sampling and labeling process runs continuously until a given budget of labeling limit K is reached. In the next section, we will formally define the learning function.

3 The DALAUPModel

We introduce the DALAUP model for anchor user prediction under the active learning setting.

3.1 Anchor User Prediction

Given GA, GB and L, we first extract the structural context for each user in both networks GA and GB, based on which we design a classifier for predicting the labels of pairs of users.

Structural Context

Given a social network GA, we wish to use a vector p(i,s) ∈ R1×NA to represent each user viA ∈ GA, where p(i,s) indicates the probability of visiting vjA ∈ GA after s-step transitions initiated from viA. The transitions are usually controlled by random walks with restart [Tong et al., 2006] with a parameter c ∈ (0, 1). Specifically, each transition either returns to viA with probability c, or goes forward with probability 1 - c. As a result, p(i,s) can be calculated iteratively as follows,

where DA is the normalized weighted matrix of GA with sums of the rows to be 1, and p(i,0) is the initial vector with the i-th entry to be 1 and the remaining entries 0.

To capture contextual information of network structures, we define the structural context miA of user viA to be,

where S indicates the number of steps. Following the same logic, we can obtain the structural context mmB for each user vm B ∈ VB. These structural contexts are served as the input of the following neural network architecture.

Representation of Pairs of Users Across Networks

We wish to learn stable representations of pairs of users based on the structural context defined above. To preserve the structure information of a single network, we use both convolution and deconvolution neural networks to represent social networks [Niepert et al., 2016]. The convolution neural network in our model consists of k convolution layers. Let (xiA)(0) = miA ∈ R1×NA be the input of user viA at the first convolution layer and

be the output of the l-th convolution layer, where l = 1, 2, ..., k and Conv(·) represents the convolution operation, f(·) is a non-linear activation function such as Sigmoid. W(l) is a weight parameter and b(l) is the bias. We use viA = hθA((xiA)(k) ) to denote the vector representation of user viA ∈ GA, where hθA(·) is a fully connected linear layer with a parameter set θA = {WA, bA}.

By using the deconvolution architecture, we can obtain the reconstruct representation ˆmiA for user viA. Similarly, we can obtain representation viB and reconstruct representation ˆmmB for user vm B ∈ GB with the parameters θB = {WB, bB} in full connected linear layer and the sharedparameters (W(l) , b(l) )kl=1 in convolution layers.

The goal of preserving the structure information of a single network is to minimize the reconstruction error as follows,

We consider anchor users to be similar in their representation spaces. Then, the loss of representing cross-network information Lcross with respect to anchor users can be formulated as follows,

where S(·) is a cosine similarity function, L+ ⊂ L is a set of pairs of anchor users, L- ⊂ L is a set of pairs of non-anchor users, and ϵ is the margin.

Anchor User Pair Classification

Based on the anchor user representation viA and vm B discussed above, we further design a classifier to estimate a pair of users (viA, vm B ), e.g., (viA, vm B ) is a pair of anchor users when c = 1, otherwise, a pair of non-anchor users. The probability of a pair of users (viA, vm B ) belongs to class c ∈ {0, 1} can be defined as follows,

where v(i,m) := concat(viA, vm B ) is an aggregated representation of a pair of users (viA, vm B ), and hθ(·) is a fully connected linear layer with a parameter set θ = {W, b}. The loss function under the cross entropy measure can be formulated as follows,

where y(viA,vm B ) ∈ {0, 1} is the true label of a pair of anchor users (viA, vm B ).

In other words, the objective function of anchor user prediction can be formulated by minimizing the function as follows,

where Lreg = 1 |L| ∑(viA,vm B )∈L(‖viA‖2 + ‖vm B ‖2 ) is an L2norm regularizer term to prevent over-fitting and λ1, λ2, λ3 are hyper-parameters to tradeoff the four parts.

3.2 Query Strategy

Based on the prediction of pairs of anchor users, we have two networks GA, GB, a labeled data set L and an unlabeled data set U. Moreover, we obtain the representations of all nodes in GA, GB, and the prediction probability p((·, ·), c) for unlabeled pair in U. Then, we wish to design query strategies to choose the most informative user pairs for labeling.

The anchor user pairs and non-anchor user pairs are interlocked. Once an anchor user pair is labeled, we can infer a large set of non-anchor user pairs. Thus, anchor user pairs are more valuable and informative for labeling than nonanchor user pairs. Here, we design two strategies cross network information entropy and cosine similarity to find user pairs which are more likely to be anchor ones. Moreover, we propose the third query strategy expected error reduction to maximize the label certainty of the unlabeled use pairs.

Cross Network Structure Aware Information Entropy

Given two networks GA, GB and a labeled set L, according to Eq. (6), we can obtain the probability p((viA, vm B ), c) of the candidate user pair (viA, vm B ) ∈ U belonging to class c. The measure function for unknown label c of each unlabeled user pair (viA, vm B ) is defined as follows,

where R((viA, vm B ), c) is the reward function to measure the labeling outcome ((viA, vm B ), c). For information entropy, reward function R((viA, vm B ), c) can be defined as follows,

Due to the interlock between anchor user pairs and nonanchor user pairs, the reward for labeling anchor user pairs is much more important than labeling non-anchor ones. Let S(viA,vm B ) denote a set of non-anchor user pairs inferred from (viA, vm B ) when it is labeled to be anchor one, we modify the reward function in Eq. (10) to be,

and

Based on the new measure functions, we enable the cross network information entropy for candidate user pairs in U, i.e., the larger φie(viA, vm B ), the more informative (viA, vm B ) we obtain.

Cosine Similarity

After predicting the anchor users, we obtain the representations of viA, vm B in the low-dimensional vector space. Since the anchor user pairs are similar between their representation vectors as in Eq. (5), we adopt the cosine similarity cs(viA, vm B ) to query each candidate user pair (viA, vm B ) ∈ U. The cosine similarity based query strategy φcs is defined as follows,

The larger φcs(viA, vm B ) is, the more valuable (viA, vm B ) is.

Expected Error Reduction

For (viA, vm B ) ∈ U, we introduce the expected error reduction query strategy, based on the prediction performance on the remaining unlabeled instances U\(viA, vm B ) [Aggarwal et al., 2014]. The expected error reduction aims to choose (viA, vm B ) ∈ U to maximize the label certainty of use pairs in U\(viA, vm B ). Intuitively, the estimated label of (ˆ viA, ˆ vm B ) ∈ U\(viA, vm B ) relates the probability ˆ p((ˆ viA, ˆ vm B ), c). Thus, the error reduction based query for (viA, vm B ) can be defined as follows,

where ˆ p((ˆ viA, ˆ vm B ), c) is the probability that user pair (ˆ viA, ˆ vm B ) belongs to class c, which can be calculated by Eq. (6) with ((viA, vm B ), c) being added to L. The bigger φeer(viA, vm B ) is, the more helpful is (viA, vm B ) for maximizing the label certainty of pairs in U\(viA, vm B ).

3.3 Active User Pair SelectionMechanism

Based on the above query strategies, a natural question is how to choose one candidate at each iteration e for labeling. As the prediction performance tends to get better when the labeled data set L becomes larger after adding the labeled user pairs at each iteration, it is intuitive that the rewards are not independent random variables at different iterations. In this paper the reward Re(φ) is defined as the average rise of Precision@30 and MAP@30, which can be estimated on the validate data. The recommended user pairs of the strategy are influenced by the recommendation results at previous iterations.

To simulate the adversarial setting, we use the multi-armed bandit method as the solution [Auer et al., 2002]. To adaptively select the most informative user pairs, we adjust the ϵ-greedy algorithm to make a trade-off between exploitation and exploration, where the exploration probability ϵ is time-sensitive, e.g. ϵ ∼ Beta(0.1, e) for different iteration e ∈ {1, 2, . . . , K/bs}. At the e-th iteration, we first sample an ϵ according to Beta(0.1, e). The selection randomly selects a query strategy with probability ϵ (Exploration); Otherwise, it selects the one with the highest historical mean reward (Exploitation).

Specifically, let Qe-1(φ) denote the historical mean reward of the query strategy φ at the first e - 1 active learning iterations, then the query strategy φe at the e-th iteration can be chosen as below,

where ϵ is a sample from Beta(0.1, e). With the iteration time e increasing, ϵ is expected to decrease, which will reduce the attention onto the exploitation.

Let ne-1(φ) be the time of query strategy φ employed at the first e - 1 iteration. Assume the query strategy φsaie is employed in the e-th iteration, then the historical mean reward and employ times of φsaie can be updated through,

and ne(φ) := ne-1(φ) + 1 with φ = φsaie. Meanwhile, Qe(φcs) := Qe-1(φcs), Qe(φeer) := Qe-1(φeer), ne(φcs) := ne-1(φcs) and ne(φeer) := ne-1(φeer). The update is similar, when φcs or φeer is employed at the e-th iteration.

3.4 Algorithms

The algorithm for solving DALAUP is summarized in Algorithm 1, where Θe denotes a set of the learnable parameters in the anchor user prediction component at the e-th iteration, where e ∈ {0, 1, . . . , K/bs}.

Algorithm 1 The DALAUP algorithm

Input:

Network GA and GB, labeled and unlabeled set {L, U}, maximum size K, size of small batch set bs, and query strategy set Φ := {φsaie, φcs, φeer}.

Output:

Parameter set ΘK/bs and ultimate prediction results.

• 1: Extract structural context mA,mB.
• 2: Learn initial parameter Θ0 with initial L.
• 3: Initialize n0(φ) ← 0,Q0(φ) = 0 for each φ ∈ Φ.
• 4: Initialize e ← 1.
• 5: while e ≤ K/bs do
• 6: ϵ ∼ Beta(0.1, e), γ ∼ U[0, 1]
• 7: if γ < ϵ then
• 8: φe ← rand(Φ)
• 9: else
• 10: φe ← arg maxφ′∈Φ Qe-1(φ′ )
• 11: end if
• 12: Estimate Re(φe) on validate data set.
• 13: Update Qe(φe) with Eq. (15).
• 14: ne(φe) ←ne-1(φe) +1.
• 15: ne(φ∗ ) ←ne-1(φ∗ ) for each φ∗ ∈ Φ\φe.
• 16: Qe(φ∗ ) ←Qe-1(φ∗ ) for each φ∗ ∈ Φ\φe.
• 17: Choose bs candidate user pairs C ⊆ U according to query strategy φe and label them.
• 18: L←L∪ C, U ←U\C.
• 19: Learn parameter Θe with updated L.
• 20: e ← e +1.
• 21: end while
• 22: return ΘK/bs and ultimate prediction results.

4 Experiments

In this section, we compare DALAUP with existing baseline methods on real world social networks. Experimental results show the effectiveness of DALAUP compared with the stateof-the-art methods. 1 .

4.1 Data Sets

We use Foursquare and Twitter [Kong et al., 2013] as the testbed. All the anchor user pairs are known in these data sets. The statistics are listed in Table 1.

We consider the labeled anchor user pairs as positive data and the inferred or labeled non-anchor user pairs as negative data. In the training process, we adopt undersampling to balance positive and negative data [Japkowicz and Stephen, 2002]. In our experiment, we randomly sample two nonanchor user pairs corresponding to an anchor user pair.

1 https://github.com/chengaf/DALAUP

4.2 Baseline Methods and EvaluationMetrics

In order to evaluate the effectiveness of DALAUP, we choose the state-of-the-art unsupervised, supervised and semi-supervised methods for comparison,

• DW: DeepWalk [Perozzi et al., 2014]. An unsupervised method which first represents two social networks to a low-dimensional vector space and then calculates cosine similarity between vector representations of crossnetwork user pairs to predict anchor user.
• PALE: Predicting Anchor Links via Embedding [Man et al., 2016]. A supervised model that learns network embedding with extended structural information.
• IONE: Input-output Network Embedding [Liu et al., 2016]. A semi-supervised approach that gets aligned vector representations for multiple networks.

In addition, we introduce some variants of DALAUP for comparison, including

• AUP: Anchor User Prediction method proposed in this paper, which is a supervised manner.
• DALAUP-saie, DALAUP-eer, DALAUP-cs, DALAUPie, and DALAUP-Rand.: the variants of DALAUP distinguished by their different AL query strategies, i.e., DALAUP-saie ia an active anchor user prediction model with only one query strategy φsaie defined by Eq. (9) and Eq. (11). Same argument for DALAUP-eer and DALAUP-cs. Besides, DALAUP-ie is a simplified model of DALAUP-saie with a query strategy φie := φsaie in which R is defined by Eq. (10). The last method DALAUP-Rand. is to randomly select user pairs from unlabeled set to label.

For each user in Foursquare, all above anchor user prediction algorithms output a list of candidate anchor users in Twitter. The Precision@30 [Liu et al., 2016] and MAP@30 [Man et al., 2016] are used as metrics for performance comparison.

4.3 Parameter Setting

The optimal parameter settings for each method are either determined by experiments or taken from the suggestions by previous works. Following [Perozzi et al., 2014], we use the default parameter setting for DW, i.e., window size is 5 and walks per user is 80. In our method, we set the restart probability to c = 0.6 [Tong et al., 2006] and the number of convolution layers k = 2. Margin ϵ in Lcross is set to 0. The other parameters are set as: λ1 = 0.01, λ2 = 0.01, λ3 = 10-5 .

4.4 Results and Analysis

To evaluate the effectiveness of DALAUP, we conduct two parts of experiments: effectiveness of AUP and effectiveness of DALAUP. For all experiments, we repeat the process 10 times and report the average results to test the statistical significance of the comparison results.

Effectiveness of AUP

In this experiment, different ratios of anchor user pairs are sampled randomly as positive data and the corresponding inferred non-anchor user as negative data for training. The remaining ones are viewed as test data. We set ratio η ∈

{0.1, 0.15, 0.2, ..., 0.9} respectively and fix the representation dimension d = 56 [Liu et al., 2016]. Experiment results are shown in Fig. 2.

From Fig. 2, we can observe that the performance of our supervised method AUP is significantly better than the other comparing methods. Specially, when the ratio γ comes to 0.5, IONE can achieve about 48% and 19% in Precision@30 and MAP@30, while AUP can obtain 97% and 95% in these two measures.

Effectiveness of DALAUP

In this part, we investigate the effectiveness of the AL query strategies and the select mechanism proposed in section 3.2 and 3.3. To ensure that the performance difference in the experiments is solely caused by different AL query strategies and their select mechanism, we first randomly split the whole anchor user data into four parts: an initial training set to build an initial model, a validate set to get the rewards of different query strategies, a test set to evaluate the performance of the model, and an unlabeled set to select user pairs [Shen et al., 2004].

The size of anchor user pairs in each part is 100, 300, 600 and 2,141 respectively. According to the interlock property, the non-anchor user pairs can be inferred from the anchor user pair set. At each iteration, we select a small batch of user pairs by following our AL query strategies, add the real label on them, and put them into the training set. The batch size bs = 100 and the maximum size K = 1, 500. The performance comparisons of different query strategies with the different number of queried user pairs are shown in Fig. 3, in which the dotted line is the performance of the AUP model without any newly labeled information being added.

From Fig. 3, we can observe that:

• DALAUP significantly outperforms all the other methods in terms of both Precision@30 and MAP@30, which demonstrates that the proposed active user pair selection methods is effective in improving the prediction performance.
• The poor results of DALAUP-Rand. further validate the effectiveness of the proposed AL query strategies.
• Compared to information entropy DALAUP-ie, the modified DALAUP-saie method largely improves Precision@30 and MAP@30, which proves that cross network structure information can be used to ameliorate information entropy.

In addition, we investigate the performance of different anchor link prediction methods when adding 1500 extra labeled user pairs. These labeled data are selected in two manners.

One is to select by DALAUP , while the other is to select randomly. For the convenience comparison, we also add the performance of these methods with no extra labeled data added.

The results are shown in Fig. 4, from which we can observe that:

• DALAUP outperforms all the other methods, no matter the data selected by itself or by random.
• The labeled data, selected by DALAUP, can improve performance for the baselines.
• The randomly selected 1500 data for labeling cannot help better the benchmark methods, which confirms the importance of active selection methods.

5 Conclusion

In this paper, we present a deep active learning based method DALAUP to solve the anchor user prediction problem. We design a couple of convolution and deconvolution networks with shared-parameter to estimate the vector representations of cross-network anchor users. To solve the correlation difficulty of labeling anchor user pairs and non-anchor user pairs, we design three query strategies and a time-sensitive user pair selection algorithm for precisely selecting pairs of users for labeling . Experiments on real-world social network datasets demonstrate the effectiveness and efficiency of the proposed DALAUP method.

Acknowledgments

This work was supported in part by the National Key Research and Development Program of China (No. 2016YFB0801301), the NSFC (No. 61872360), the MQNS (No. 9201701203), the MQEPS (No. 90275252 and No. 96804590), the MQRSG (No. 95109718), the Youth Innovation Promotion Association CAS (No. 2017210), and the Investigative Analytics Collaborative Research Project between Macquarie University and Data61 CSIRO.