Aligning Users across Social Networks Using Network Embedding

1 Introduction

Mapping users across online social networks has recently been attracting attention in both academia and industry. The established user correspondence can benefit applications like social link prediction [Dong et al., 2012; Zhang et al., 2014] and cross-domain recommendation [Hu et al., 2013]. In general, carefully aligning heterogeneous social networks can alleviate the sparsity issue and transfer useful information for social network analysis.

One intuitive way to establish the user correspondence is to make use of user demographic attributes like username, gender, and etc. Among them, username is most commonly used with the argument that users tend to use their favorite usernames or related variants for multiple networks. The effectiveness of this simple approach has been demonstrated under some given experiment settings [Liu et al., 2013; Zhang et al., 2015]. Yet, there exist users who deliberately use different usernames. In addition, demographic information in different networks is highly likely to be unbalanced, and the presence of rich and correct profiles sometimes cannot be always assumed. Other than user attributes, some also proposed to map users using their long-term topical interest, language style of personalized wordings and emoticon adoption [Liu et al., 2014; Zafarani and Liu, 2013].

⇤Corresponding Author: Xin Li (xinli@bit.edu.cn).

Alternatively, the structural information of the social networks can be used directly for user alignment. Intra-links, inter-links and common users across the networks (also called anchor users) can be exploited to derive a probabilistic graph classifier [Zhang and Yu, 2015a; Wu et al., 2014] or to render a common subspace of multiple networks for relevance computation [Tan et al., 2014]. Most of these related work considers the links to be undirected. However, followerfollowee relations are often maintained in a number of social media like Twitter. The conformation of the follower-ship of a user somehow reflects the objective recognition from the community, whereas the conformation of the followee-ship reflects one's personal social interest. It is intuitive that the follower-ship and followee-ship collaboratively define one's unique social figure in virtual networks. Also, most of the existing work computes the structural alignment of networks using matrix factorization where matrix inverse is typically involved, making them hard to scale up for large-scale problems.

In this paper, we propose to align social networks using the network representation learning (NRL) approach [Perozzi et al., 2014; Tang et al., 2015b; 2015a]. We extend it to social network alignment using a unified optimization framework where the embeddings of multiple networks are learned simultaneously subject to hard and soft constraints on common users of the networks. To contrast with the existing NRL methods, the proposed network embedding model explicitly represents the follower-ship and followee-ship of each user as the input and output context vectors. We name it as the InputOutput Network Embedding (IONE). The IONE can preserve the proximity of users with "similar" sets of followers and followees in the embedded space. Also, both known and potential anchor users across the networks can be introduced in a unified manner to play the roles as hard and soft constraints for facilitate the transfer of the contextual information. All the considering factors are formulated into a single objective function so that minimizing it can allow network embedding learning and user alignment to be achieved at the same time. Also, we adopt the negative sampling which can substantially reduce the computation cost and make the IONE scale well to networks of large size. We conduct detailed empirical evaluation using real datasets and show that the IONE outperforms other competitive approaches.

2 RelatedWork

Structural alignment methods proposed for social network alignment can roughly be categorized into supervised and unsupervised. The unsupervised methods assume absence of anchor links, making the problem essentially a generic graph alignment problem [Koutra et al., 2013; Zhang and Yu, 2015b; 2016]. The supervised methods predict anchor links using the classification approach based on features like username, profile information, and social connectivity measures [Malhotra et al., 2012; Kong et al., 2013]. Recently, fusing anchor link prediction and social link prediction was also found effective [Zhang and Yu, 2015a].

Learning to align the network manifolds is another promising direction. In [Tan et al., 2014], hyper-edges among the users are defined and the manifolds of two social networks are projected onto a common embedded space so that the nodes in each hyper-edge will be close in the projected space. Eigenvalue decomposition on a matrix defined based on the hyperedges is required, which however is inevitably timeconsuming. Our work is along the direction of projecting multiple social networks onto a common embedded space. To contrast, the proposed IONE allows more social structural properties to be exploited for the network representation learning, with the ultimate goal to result in a more accurate social network alignment. The IONE does not require explicit definition of relations as hyperedges but can achieve a similar goal implicitly via the interactions of the input and output context representations of the nodes in the network.

3 Model Framework

Let G = (V↪E↪w) be a social network where V := ¶vi♦ is the set of user nodes rand E := ¶(vi↪ vj)♦ is the set of directed edges representing the user relations. Each edge is associated with a weight wij > 0 indicating the tie strength.

3.1 Input-Output Network Embedding

We propose a novel network embedding for representing social networks. Similar to most of the existing representation learning methods, we represent each node vi 2 V as a ddimensional vector in an embedded space via a projection function f : V ! <d . By leveraging the follower-followee relations of the users, we allow the context of each user in a social network to be characterized by its own set of followers and followees. To phrase that in a general network setting, we consider i) the parents of a node as its input context, and at the same time ii) its children as its output context. Accordingly, we represent each node vi with three vector representations: a node vector -!ui 2 <d , an input context vector -!ui 0 2 <d , and an output context vector -!ui 002 <d . As illustrated in Fig.1, vi is the parent node of vj and thus -!ui contributes to -!uj 0 which represents the input context of vj. Meanwhile, as vj is at the same time the child of vi, -!uj contributes to -!ui 00 which represents the output context of vi. As both input and output contexts are explicitly modelled for each node, we call the proposed model Input-Output Network Embedding (IONE).

In order to learn the network embedding from a social network G, for each edge (vi↪ vj) 2 E, we define the probability that vi contributes specifically to (or "generates" as termed in [Tang et al., 2015b]) vj as its input context when compared with how vi contributes to other nodes, given as

where ♣V ♣ is the number of users in one network. Similarly, we can define the probability that vj contributes specially to vi as its output context when compared with how vj contributes to other nodes, given as

We further define the empirical counterparts of p1(vj♣vi) and p2(vi♣vj) as b p1(i↪ j) = wij◁dout i and b p2(i↪ j) = wij◁din j respectively, where dout i = Pk2Nout(vi) wik and din j = Pk2Nin(vj) wkj. By minimizing the KL divergence of p1 and p2 and their empirical counterparts b p1 and b p2, the corresponding IONE model can be inferred (See Sec.3.2).

3.2 Aligning Network Embeddings of Multiple Networks

Given two social networks X and Y , we propose to compute their IONE models and at the same time align them. To do that, we first define an anchor node in one network (say X) as a node which has a unique correspondence to another node in the other network (say Y). The correspondence indicates that the two nodes are referring to the same person. We call the correspondence as an anchor link in the sequel. Assuming that a set of anchor links bridging the two networks are available, we learn an aligned network embedding so that

Objective 1: The structural proximity of the nodes within the two individual networks are preserved in their corresponding embeddings as far as possible, and

Objective 2: The representations of the anchor nodes coincide in the embedded space and those who are close in the embedded space can be considered as good candidates for user alignment.

To formulate the first objective, we minimize the KLdivergence of p1 and p2 and their empirical counterparts b p1 and b p2 over all the nodes in the two networks. By further defining the importance weighting of vi contributing to its child as input context in network X as λout i and that of vj contributing to its parent as output context in network X as λin j , the corresponding objective function can be given as:

By setting λout i as the output-degree dout i of vi and λin j as the input-degree din j of vj, the objective function can be rewritten as:

To formulate the second objective, we set the node vector representations of the corresponding anchor nodes in the two networks to be identical as hard constraints. In other words, we make the IONE embeddings of the X and Y aligned at the anchor nodes. On top of that, to enhance the alignment accuracy for nodes other than the anchor ones, we train a classifier for anchor link prediction and use the anchor link prediction results as "soft" constraints. To implement both, we adopt a second objective function.

We denote pa(vX i ♣vY k ) as the probability that vX i and vY k are the same user as predicted by a pre-trained classifier. If say there is an anchor link between vX i and vY k as provided in the training set, we set the value of the corresponding pa to 1. It can be proved that this is equivalent to setting the hard constraints for the representations of the corresponding anchor users to be identical (see Appendix I). For non-anchor nodes, the estimated pa(vX i ♣vY k ) acts as a "bridge" between vX i and vY k , and vY k in network Y can contribute as input context to vX i in network X with the probability pa(vX i ♣vY k ). Then, vY k in network Y can contribute to other nodes in network X as if it is vX i with a probability pa(vX i ♣vY k ). Based on this idea, we first define the empirical probabilities ˆ p1(vX◁Y j ♣vY ◁X k ) = Pvi2X◁Y pa(vX◁Y i ♣vY ◁X k ) ⇤ wij◁dout i , ˆ p2(vX◁Y i ♣vY ◁X k ) = Pvj2X◁Y pa(vX◁Y j ♣vY ◁X k ) ⇤ wij◁din j . We can again minimize the KL-divergence of p and the empirical distribution b p, and the corresponding objective function becomes:

Thus, the multiple networks can be aligned in the embedded space by minimizing the combined objective function O = O1 + O2 over the parameters ¶(-! uxX ↪ -! ux 0X ↪ -! ux 00X )♦ and ¶(-! uy Y ↪ -! uy 0 Y ↪ -! uy 00 Y )♦ where O1 helps ensure that two nodes (users) sharing more common input and output contexts (common followers and followees) will be drawn closer in the embeded space, and O2 allows the contexts of the anchor nodes to be propapated across the networks which in turn can enhance the individual learning of the two embeddings.

3.3 Model Inference

We use the stochastic gradient descent to learn the vector representations of the two networks. To update the node vector of vi in network X, i.e., -!ui X , the gradient is computed as:

Calculating the conditional probability p1 in Eq.(6) requires the summation over the entire set of nodes. To reduce the computational complexity, we adopt the negative sampling approach [Mikolov et al., 2013]. In short, it makes the problem of minimizing the above objective function equivalent to a problem of estimating the parameters of a probabilistic binary classifier that uses the same parameters to distinguish samples of the empirical distribution from samples generated by the noise distribution. The equivalent counterparts of the objective function can be derived, given as:

where σ(x) = 1◁(1 + exp (-x)) is the sigmoid function, K is the number of negative samples vn sampled from the "noisy distribution" of pn(v) = d3◁4 v as in [Mikolov et al., 2013], and dv is the output degree. Thus the partial derivative of Eq.(6) w.r.t. -!ui can be rewritten as:

Similarly, we can obtain the partial derivatives w.r.t. the other context vectors of the concerned nodes given as:

With reference to Eqs.(9-14), the updating rules for network Y can be obtained by swapping the superscripts X and Y . They are not listed due to the page limit. The overall algorithm is shown in Algorithm 1:

Algorithm 1 Learning Aligned IONE Across Networks

Require: Two networks GX and GY , a set of anchor links

Ea, learning rate ⌘, # of negative samples K Ensure: Node representations ⇥ = ¶(-! uxX ↪ -! ux 0X ↪ -! ux 00X ), (-! uy Y ↪ -! uy 0 Y ↪ -! uy 00 Y )♦ 1: procedure LEARNING(GX ,GY , Ea, ⌘, K) 2: Initialize ⇥ = ¶(-! uxX ↪ -! ux 0X ↪ -! ux 00X ), (-! uy Y ↪ -! uy 0 Y ↪ -! uy 00 Y )♦ 3: repeat 4: for N in ¶X↪ Y ♦ do 5: Sample one edge (vi,vj) fromGN 6: Update -!uj 0 ↪ -!ui↪ -!ui 00 ↪ -!uj based on Eqs.(9-12) with ⌘ 7: for i = 0; i < K; i = i + 1 do 8: Sample a negative node vn 9: Update -!ui ↪ -!uj ↪ -! un 0 ↪ -! un 00 based on Eqs.(9, 10, 13, 14) with ⌘ 10: end for 11: end for 12: until convergence 13: return ⇥ 14: end procedure

3.4 Time Complexity

Sampling an edge takes constant time O(1). Optimization using K negative samples takes O(d(K + 1)) time, where d is the dimension. Therefore, the overall complexity for each step is O(dK). In practice, the number of steps need for the optimization is usually proportional to the number of edges ♣E♣ [Tang et al., 2015b]. Therefore, the overall time complexity of our model is O(dK♣E♣) which is linear to the number of edges ♣E♣ and does not depend on the number of nodes ♣V ♣.

3.5 Mapping Users Across Social Networks

To map users across networks, we compute cosine similarity between the vector representations of one node in network X and another in Y to determine their correspondence.

So, for each user vX i in network X, we can find the most relevant user vY j in network Y to be an anchor candidate.

4 Experiments

For performance evaluation, we employ two real-world social network datasets collected from Foursquare and Twitter [Zhang and Yu, 2015a]. Table 1 lists their statistics. The ground truth of anchors are provided in Foursquare profiles.

4.1 Comparative Methods

We compare the proposed IONE with several state-of-the-art methods, which are summarized as follows:

• ÷ MAG: A graph-based manifold alignment [Tan et al., 2014] where the similarity of a linked user pair is defined as 1.
• ÷ MAH: A hypergraph-based manifold alignment [Tan et al., 2014] where the hyperedges model the high-order relations in a social network.
• ÷ CLF: A method proposed in [Zhang and Yu, 2015a] which includes two phases: 1) collective multi-network link prediction and 2) collective link fusion across partially aligned probabilistic networks.
• ÷ CRW: A method called collective random walk with restart that is essentially the second step of CLF, which is used here as a baseline.

Also, we abbreviate the proposed model with only the hard constraints on anchor nodes as IONE and that with also the soft constraints as illustrated in Sec.3.2 as IONE-S. And, we abbreviate the proposed model with only input context as INE and with only output context as ONE.

4.2 EvaluationMetrics

In our experiments, Precision@N is the evaluation metric, given as:

where ♣CorrUser@N♣ is the number of unmapped anchor users with their corresponding users found among the top-N neighbors in the embedded space. ♣UnMappedAnchors♣ is the total number of all unmapped anchor users.

Also, since the network alignment performance in general depends on the degree of overlapping of the two networks, we measure the degree as in [Tan et al., 2014], given as

where RelationsX◁Y is the set of direct edges in network X◁Y and Correlations is their intersection.

4.3 Experimental Results

The experimental results are presented in Figure 2. IONE is found to outperform all the baselines consistently and significantly given different @N settings as well as different training-to-test ratios. MAH and MAG perform better than CRW, showing that the random walk approach is not as accurate as the manifold alignment approach. However, both MAG and MAH fail to differentiate the follower-ship and followee-ship when constructing the incidence matrices of the hypergraph. We found that even INE and ONE can give better results, while IONE performs the best. Table2 tabulates our detailed quantitative improvement over the comparative baselines for P@30. Note that, different from our proposed method, the methods based on random walks (e.g.,CLF and CRW) are "asymmetric" in which taking a different network as the source network for a particular network pair will lead to different prediction results. For such methods, the alignment has to be computed in both directions and thus the computation complexity doubles. For different training-to-test ratios, as observed from Fig.2(b), IONE outperforms all the baselines. Even for ratio settings as low as 10% to 20%, the performance enhancement is still significant.

Among the subspace learning based methods, we also compare their performance under the settings using representations of different dimensions. According to Fig.2(c), both MAG and MAH achieve good performance when the dimensionality setting is around 950, while IONE reaches good performance when the dimensionality is under 50. It is well known that the complexity of the learning algorithm is highly depending on the dimensionality of the subspace. Besides, low-dimensional representation also leads to an efficient relevance computation. We conclude that the proposed network embedding approach is significantly more effective and efficient than the matrix factorization-based approach.

Fig.2(d) shows how different methods perform at different values of Interop 1 . Intuitively, it will be easier to align the networks if they share more common edges. We observe that the performance of all the methods consistently achieve better results as the Interop value increases. Again, IONE consistently outperforms all the baseline methods, even when the resemblance of the networks is rather low.

1 In our experiments, we vary the Interop value by removing non-

For IONE-S, the soft constraint pa(vX i ♣vY k ) was derived similar to what being proposed in CLF [Zhang and Yu, 2015a]. By considering the labeled anchor links as positive data and those randomly sampled from unlabeled user pairs across networks as negative data, we compute structural features including common neighbors, extended Jaccard's coefficient and extended Adamic/Adar Measure for a SVM-Platt scaling classification model to estimate pa(vX i ♣vY k ). With the estimated pa(vX i ♣vY k ) incorporated as the soft constraints, the network embedding is then obtained via IONE-S. In general, the classification model achieves better performance when the training sets are more balanced. Here we use imbalance ratio ♣-ve anchor links♣ ♣+ve anchor links♣ as a proxy to reflect the performance of the empirical classification model. Fig.3(a) shows that IONE-S outperforms CLF where a similar SVM classification method is used. The performance of CLF is slightly better than that of the classification model indicating its high dependence on the ability of the classification model. For IONE-S, we found that it is very robust even when the accuracy of the estimated value of pa(vX i ♣vY k ) is limited. As there is an edge sampling process in learning IONE (See in Algorithm 1), whether the learning algorithm can converge is an important issue. Fig. 3(b) shows that IONE-S and IONE both converge in a stable manner. Specifically, IONE-S achieves its convergence much earlier than IONE. We believe the gain comes from the empirical soft constraints.

4.4 ACase Study

Here we plot Fig.4 to illustrate the effectiveness of IONE by showing two subgraphs, which are part of the corresponding social networks, and their embeddings in the inferred subspace. We adopt t-SNE [Van der Maaten and Hinton, 2008] for visualizating the embeddings. The red, green and blue nodes in the two subgraphs denote the anchor users in the training set, the anchor users in the test set, and the users only belonging to one network respectively. Generally speaking, topologically similar nodes with the help of the clue provided by the anchor links are projected to locations close to each other in the embedded space. In particular, we observe that

1. Two nodes sharing more common edges in one network appear closer in the learned low dimensional space. In the Twitter network, Bar tw shares with jac tw two input edges from kyl an and hue an, but none with JES tw which in turn has an input edge to kyl an. Thus Bar tw appears closer to jac tw than JES tw in the embedded space (near the left side).
2. The anchor links do help the network alignment. We observe that jam fs has 3 input edges and 3 output edges from 3 anchor users (kyl an, hue an, mil an) in the Foursquare network, while jam tw also has 3 input and 2 output edges from the same set of anchor users in the Twitter network. In the plot of the embedded space (near the lower

anchor relations in the networks.

side), jam tw (green octagon) and jam fs (green cross) are located very close to each other.

3) User proximity is preserved in the embedded space based on both follower-ship and followee-ship collaboratively. Consider jes fs, rad fs and tim fs in the Foursquare network. All three have edges connecting to kyl an. Node jes fs has a bi-directed edge with kyl an. Nodes rad fs and tim fs have only input edges from kyl an. Therefore, rad fs and tim fs are closer to each other in the inferred space (near upper right corner) and farther apart from jes fs. For another example, JES tw is the only node in the Twitter network pointing to kyl an, and jes fs is one of two nodes in the Foursquare network pointing to kyl an. Thus, kyl an has significant contribution to both jes fs and JES tw, drawing them close in the inferred space (near lower left corner).

5 Conclusion

We studied the problem of mapping users across networks. A representation learning model with the objective to learn an aligned network embedding for multiple networks was proposed. The proposed approach explicitly models the follower-ship and followee-ship of each user as the input and ouput contexts. Both given and potential anchor links can be used in this model as hard and soft constraints in a unified framework for learning. Stochastic gradient descent and negative sampling are used for the efficient learning of the model. The extensive experiments conducted on two realworld datasets demonstrate that our proposed model outperforms several state-of-the-art methods. Future work includes extending it to multiple networks and exploring its applicability to other types of network data.

Appendix I

We prove that our proposed formulation is equivalent to setting hard constraints to force the representations of the mapped anchor users equivalent. Suppose (vX i ↪ vY i ) is an anchor link, and thus pa(vX i ♣vY i ) = pa(vY i ♣vX i ) = 1

The updating rule for -!ui Y can also be obtained:

which is equivalent to Eq.(18) when we set the anchors' initial values as -!ui Y = -!ui X . This completes the proof.

6 Acknowledgement

This work has been partially supported by NSFC under Grant No. 61300178, National Program on Key Basic Research Project under Grant No. 2013CB329605, and Hong Kong Baptist University Strategic Development Fund.