Predict Anchor Links across Social Networks via an Embedding Approach

1 Introduction

With the prosperity of online social networks, people often join multiple social networks [Zafarani and Liu, 2009; Sun et al., 2012]. For example, one person could be an active user in both Facebook and Twitter. These shared users naturally form anchor links bridging different social networks [Kong et al., 2013]. Anchor links are crucial to crossnetwork information diffusion [Peng et al., 2013], link prediction [Ahmad et al., 2010; Dong et al., 2012], and crossdomain recommendation [Man et al., 2015]. However, information about anchor links is often not available in practical scenarios, because most users have no motivation or are unwilling to explicitly correlate their identities in different online social networks [Backstrom et al., 2007]. This poses the problem of anchor link prediction, i.e., identifying hidden anchor links across different social networks [Liu et al., 2014; Tan et al., 2014; Zhang et al., 2015; Zhang and Yu, 2015]. Early studies address this problem either by leveraging selfreported user profiles (e.g., user name, profile picture, location, gender) and other demographical features [Iofciu et al., 2011; Malhotra et al., 2012] or by exploiting user generated contents, such as, tweets, posts, blogs, reviews, and ratings [Novak et al., 2004; Liu et al., 2013]. However, an important open problem is: whether and to what extent we can address the anchor link prediction problem, if only structural information of networks is available.

Existing approaches that leverage network structure for anchor link prediction fall into two main categories. The first category of approaches works in an unsupervised manner, where no information about explicit correspondence across networks is leveraged. These approaches cope with the anchor link prediction problem as a problem of network alignment, which is generally an NP-hard combinatorial optimization problem [Singh et al., 2007; Klau, 2009; Kollias et al., 2012], and solve it by finding certain structural similarity between nodes across networks. Consequently, these approaches either are limited to networks with moderate size, or can only be applicable to large scale networks under a sparse assumption [Bayati et al., 2009]. The second category of approaches is supervised [Kong et al., 2013; Zafarani and Liu, 2013], with which the anchor link prediction problem is solved under the supervision of observed anchor links (e.g., some users may explicitly mark their accounts in different social networks in their homepages, social media channels, or third-party websites like Aboutme.com). Most existing supervised approaches directly work on structural features of social network, such as, degree, clustering coefficient, the number of involved triangles, common neighbors, to name a few [Cui et al., 2013; Kong et al., 2013]. Without capturing intrinsic structural regularities of social networks, these approaches are particularly sensitive to network structure, and thus slight changes or noises of network structure may result in remarkably different results. In sum, we still lack an effective approach that can make the best of the structural regularities of social networks and the information pertaining to observed anchor links.

To bridge this gap, in this paper we propose a novel supervised model, called PALE (Predicting Anchor Links via Embedding), to tackle the anchor link prediction problem. This model contains two anchor-link-aware stages, namely, embedding and matching. Specifically, given two networks for predicting their anchor links, we first conduct network embedding on each network to capture its major structural regularity. Unlike existing methods that directly work on human-defined structural features, we embed each network into a low-dimensional space to learn effective representation of nodes. In this way, major structural regularity of networks is well captured, while insignificant details are filtered away. Simultaneously, the network embedding preserves specific structural regularities, leveraging observed anchor links as supervised information. This method makes our model robust to slight changes of network structure. Next, in the matching stage, taking the low-dimensional representations of nodes as features, we learn a mapping function across the two learned low-dimensional spaces, supervised by observed anchor links. In order to offer the flexibility that the two latent spaces can be nonlinearly correlated, Multi-Layer Perceptron (MLP) is employed to learn the mapping function. Finally, for each node in one network, we identify the most likely counterpart in the other network according to the learned mapping function. Besides the robustness, another important merit of the proposed model is that the low-dimensional representation of network structure can be easily incorporated with contents and demographic features to further improve the accuracy of anchor link prediction.

We validate the proposed anchor link prediction model on two scenarios. The first one is to predict anchor links across two partially observed networks, which are sampled from the same social network. The second one intends to predict anchor links across two co-author networks in different research areas, namely Artificial Intelligence and Data Mining. Experimental results convincingly suggest that the proposed PALE model outperforms the compared baselines. Extensive analysis is also conducted to demonstrate the good performance of PALE under different settings of network structure.

2 Predict Anchor Links via Embedding

Denote a social network as G = ¶V↪E♦, where V is the set of nodes, and the edge set E ⇢ (V ⇥ V ) reflects social relationships among nodes (e.g., friendships in Facebook). In this paper, we consider such a scenario: some users are simultaneously involved in two different social networks, forming anchor links across the two networks. Without loss of generality, we refer to one network as source network, and the other as target network, denoted with Gs and Gt respectively. For each node in the source network, we aim to identify, if any, its counterpart in the target network. This can be formally formulated as the following anchor link prediction problem.

Anchor link prediction: Given two networks Gs = ¶V s ↪Es ♦ and Gt = ¶V t ↪Et ♦ and a set of observed anchor links T = ¶(v↪ u)♣v 2 V s ↪ u 2 V t ♦, it aims to identify hidden anchor links across Gs and Gt .

To solve the anchor link prediction problem, we propose a novel supervised model, called PALE. In this model, the source and target networks are both embedded into lowdimensional spaces, denoted as Z s and Z t respectively, and a mapping function φ : Z s ! Z t across the two spaces is learned. Formally, PALE aims to find the optimal Z s , Z t , and φ by

where Le(Gs ↪Z s ↪Gt ↪Z t ↪ T) is the loss when embedding the source network Gs and the target network Gt into the low-dimensional spaces Z s and Z t , and the matching loss Lm(φ↪ Z s ↪ Z t ↪ T ) reflects whether or not the observed anchor links in T are correctly predicted by the mapping function φ with Z s and Z t as its inputs.

Unfortunately, it is very difficult to solve this optimization problem efficiently because of the interdependence between Z s , Z t and φ. For this reason, we turn to find an approximately optimal solution, working in a two-stage embedding and matching manner, as shown in Figure 1.

2.1 Anchor-link-aware Network Embedding

In this stage, each network is embedded into a lowdimensional latent space, where each node vi is represented as a d-dimensional vector zi. A crucial problem for anchor link prediction is that some edges that exist in practice may be unobserved, as they have not been explicitly built or fail to be crawled. These missing edges can lead to unreliable representations when embedding networks into latent spaces. To combat this problem, we propose a strategy to identify hidden edges with the help of the observed anchor links and the structure of the other network. Based on the identified unobserved edges together with the observed ones, a reliable network embedding is learned.

Cross Network Extension

Before network embedding, we first leverage observed anchor links to extend both source and target network. It is usually true that given a pair of users with anchor links, if they have a connection in one network, so do their counterparts in the other network [Bayati et al., 2009]. Based on such an observation, if two nodes are not linked in one network, but their counterparts are linked in the other network, we can add an edge between them in the present network, as shown in Figure 2. Formally, given two networks Gs and Gt with anchor links T, the extended network ˜Gs of the source network Gs can be described as

Similarly, the target network Gt is extended into ˜Gt . Note that cross-network extension is not a mandatory requirement in our model.

Network Embedding

With the extended source and target networks, we embed them independently into latent spaces. For convenience, in this subsection, we use the same notations without distinguishing the source and the target network. For a pair of nodes vi and vj , given their d-dimensional representations zi and zj , the probability that an edge is observed between them is

where σ(x) = 1◁(1 + exp(-x)) is the sigmoid function.

To learn the latent representation, we maximize the loglikelihood of the extended network ˜G

Since only observed edges, including extended edges if any, are modeled, there exists a trivial solution when maximizing the objective function in Eq. (4): zik = 1. To avoid the trivial solution, for each observed edge (vi↪ vj), we maximize the objective function with negative sampling as

where the first term models the observed edge, the second expectation term samples negative edges from a null model where each node is sampled with the probability Pn(v) ⇠ d3◁4 v as proposed in [Mikolov et al., 2013b] andK is the number of sampled negative edges, dv is the degree of node v.

Note that maximizing the summation of Eq. (5) over all the edges in the extended network ˜Gs and ˜Gt independently is an effective way to approximately minimize the loss of network embedding Le in Eq. (1). Finally, we adopt stochastic gradient descent to learn the latent representations.

2.2 Supervised Latent Space Matching

Next, we turn to learn a mapping function φ, supervised by the observed anchor links (vs l ↪ utn ) 2 T with latent representations being zs l and ztn .

Given zs l 2 Z s , the mapping function parameterized as φ(zs l ;⇥) projects it into the target space Z t . Here, ⇥ is the collection of all parameters in the mapping function φ. The loss is

where ♣♣ · ♣♣F is the Frobenius norm, which is a distance metric between the predicted latent factor and the training latent factor.

In this paper, we consider both linear and non-linear mapping functions. For the linear mapping function, ⇥ is a d ⇥ d matrix, as follows

Eq. (6) finds the best matrix ⇥ so that ⇥⇥zs l closely approximates ztn for all labelled pairs (vs l ↪ utn ) 2 T. Indeed, a linear mapping function has been successfully used in the previous study [Mikolov et al., 2013a].

In addition, we employ Multi-Layer Perceptron (MLP) [Ruck et al., 1990] to capture the non-linear relationship between the source and target spaces. In this way, the two spaces obtained in the network embedding stage are not required to be linearly aligned, which offers the embedding stage more flexibility to capture the structural regularities of networks.

2.3 Anchor Link Prediction

To make prediction, for any given node vs l in the source network with its representation zs l , we map it into the target latent space according to the mapping function φ(zs l ;⇥). We then predict hidden anchor links by identifying the counterpart node utn that is the closest one to φ(zs l ;⇥) by

Alternatively, for each node in the source network, we can offer a list of nodes in the target network as its potential counterparts.

2.4 Complexity Analysis

In the network embedding stage, the total time complexity for one network G is O(kd♣E♣), where k is the number of iterations, d is the dimension of the embedding vectors, ♣E♣ is the number of edges in the network. In the latent space matching stage, the two models with linear and non-linear mapping functions have different time complexity. For the case of the linear mapping function, the time complexity of solving each row of the transfer matrix as a sub-problem is O(♣T ♣d2 ), thus the total complexity is O(♣T♣d3 ), where ♣T♣ is the size of the set of observed edges; for the case with MLP as the non-linear mapping function, the time complexity is O(kd♣T ♣), where k is the iteration times, ♣T♣ is the size of the set of observed edges. For prediction, the time complexity to match nodes across networks is O(♣V ♣2 ), where ♣V ♣ is the number of nodes in the network.

3 Experiments

In this section, we compare the proposed PALE model with existing baseline methods on two datasets. One contains networks sampled from the Facebook network. The other consists of two co-author networks in different research areas, namely, Artificial Intelligence and Data Mining.

3.1 Methods andMetrics for Comparison

We choose both unsupervised and supervised methods for comparison, including

• ÷ Degree-Based Alignment: Nodes between two networks are matched in terms of their degrees, offering a trivial baseline for anchor link prediction.
• ÷ Matching Across Domains (MAD) [Li and Lin, 2014]: It matches shared nodes across homogenous networks through singular value decomposition, which is an unsupervised model for anchor link prediction.
• ÷ Multi-Network Anchoring (MNA) [Kong et al., 2013]: It extracts pairwise social features from partially aligned social networks and then solves the anchor link prediction problem as a classification problem. We use the same settings to extract cross-network social features.
• ÷ Collective RandomWalk (CRW) [Zhang and Yu, 2015]: Random walk is conducted on networks with anchor links to identify the counterpart of each node in the other network.
• ÷ PALE (LIN): PALE model with a linear mapping function in the matching stage.
• ÷ PALE (MLP): PALE model with the MLP being employed as the mapping function, where the dimension of the hidden layer is 2 ⇤ d, the learning rate and the regularizing coefficient are chosen based on a 5-fold crossvalidation.

As the anchor link prediction algorithms output a list of candidate nodes for each node in the source network, F1measure and MAP@30 are adopted as metrics for performance comparison.

3.2 Experiment on Facebook Dataset Dataset

The first dataset 1 was crawled from Facebook and published in [Viswanath et al., 2009]. In the experiment, we filter out those nodes whose degree is less than 5, resulting in 40↪ 710 users and 766↪ 519 edges. We then adopt the following process to sample two sub-networks, where nodes are all inherited from the original network. For each edge, we generate a random value p with the uniform distribution in [0↪ 1]. If p  1-2↵s+↵s↵c, the edge is discarded; If 1-2↵s+↵s↵c < p  1 - ↵s, it is preserved only in the first sub-network; If 1 - ↵s < p  1 - ↵s↵c, it is kept only in the other sub-network; Otherwise, it is preserved in both sub-networks. With such a sample strategy, both sub-networks keep the same sample ratio ↵s of edges from the original network in average, reflecting the sparsity level of networks. Besides, an expected fraction ↵c of edges are shared among the two subnetworks, reflecting the overlap level.

1 http://socialnetworks.mpi-sws.org/data-wosn2009.html

In the experiment, one of the two sub-networks is selected as source network Gs , and the other as target network Gt . Since only edges could be different in sub-networks, every corresponding pair of nodes in Gs and Gt are anchor linked as the ground truth, and a fraction ↵t of them are chosen as supervised anchor links T. Through the experiment, we demonstrate the performance of the PALE model on different settings of sparsity level ↵s and overlap level ↵c, compared with all baseline models.

Results and Comparison

To comprehensively evaluate PALE, we compare it with baseline methods in different settings. First, ↵t = 3% anchor links are sampled for training and then predict the rest ones as test data. Experimental results are presented in Table 1. In Table 1(a) different sparsity levels ↵s = [0▷5↪ 0▷6↪ · · · ↪ 0▷9] with the same overlap level ↵c = 0▷9 are tested. Meanwhile, with fixed sparsity level ↵s = 0▷6, different overlap levels ↵c = [0▷5↪ 0▷6↪ · · · ↪ 0▷9] are examined in Table 1(b).

From Table 1, we can notice that the method using only the degrees of nodes to predict anchor links achieves the poorest performance, where both F1 and MAP are less than 0▷1. Without considering observed anchor links as supervision, MAD achieves about 0▷39 and 0▷41 in F1 and MAP, respectively, in the case of ↵c = 90% overlapping edges between the two networks. It becomes worse when the overlap level decreases. For supervised methods, namely, MNA, CRW, and PALE, to evaluate their performance, we conduct 10 runs of the experiment with sampling ↵t = 3% anchor links for training. The average results of F1 and MAP, as well as their standard deviations, are given in Table 1. We can see that the performance of these supervised methods is better than the unsupervised method. Among all supervised methods, PALE (MLP) outperforms the others in terms of both F1 and MAP under all settings. PALE (LIN) achieves comparable performance with CRW, which uses global structural information via random walks. Since MNA considers only node similarity across networks through local structure information, it achieves much worse performance than CRW and PALE. This again demonstrates that structural information is important for improving the accuracy of anchor link prediction, and our network embedding method offers an effective way to capture the structural regularities of networks in a global and specific way.

In addition, we also examine the effect of different sizes of the supervised anchor link set in the PALE model by varying PALE (MLP) 0▷9100◦0▷0008* 0▷9207◦0▷0009* 0▷9224◦0▷0011* 0▷9228◦0▷0005* 0▷9237◦0▷0008*

(a) Experimental results under different sparsity levels, ↵c = 90%. Significantly outperforms CRW at the: * 0.01 level, paired t-test.

PALE (MLP) 0▷4197◦0▷0010* 0▷4845◦0▷0007* 0▷6224◦0▷0012* 0▷8118◦0▷0010* 0▷9207◦0▷0009*

(b) Experimental results under different overlap levels, ↵s = 60%. Significantly outperforms CRW at the: * 0.01 level, paired t-test.

↵t from 0▷5% to 5%. Without loss of generality, we check the performance of PALE (MLP) only in terms of MAP. In Figure 3(a), the overlap level is fixed as ↵c = 0▷9, while the sparsity level ↵s varies from 0▷5 to 0▷9. In Figure 3(b), the sparsity level is fixed as ↵s = 0▷6, while the overlap level ↵c takes different values in [0▷5↪ 0▷6↪ ▷▷▷↪ 0▷9]. From Figure 3, we can observe that as the size of the training set increases from 0▷5% to 2%, the performance of the PALE model is raised quickly under various settings of sparsity level and overlap level. The increase speed slows down when ↵t exceeds 2%. That is to say, PALE can lead to good performance with relatively less supervised information. Another interesting phenomenon is that, anchor link prediction between sparser networks can achieve similar prediction results, especially with more supervised anchor links, as Figure 3(a) shows. In Figure 3(b), two networks with less overlap edges, e.g. ↵c = 50%, cannot predict as correctly as those with more overlap edges, even when more anchor links are used for training. Thus, it suggests that as compared to sparsity level, overlap level plays a more important role in the performance of anchor link prediction.

3.3 Experiment on Co-author Networks Dataset

The second dataset used in this paper is a co-author network formed by conference papers from the fields of Artificial Intelligence (AI) and Data Mining (DM), thus denoted as AI-DM, which were extracted from the Microsoft Academic Graph (MAG) [Sinha et al., 2015] 2 . MAG is a heterogeneous

2 http://research.microsoft.com/en-us/projects/mag/

Table 2: Statistics of the AI-DM dataset.

♣E♣

graph containing bibliographic information of publications, citation relationships between publications, and information of authors and institutions. We choose 10 representative conferences on AI and DM 3 , respectively. Two co-author networks are then built on the two groups of papers, and the authors with less than 3 co-author relationships are filtered out. The statistics of the dataset is listed in Table 2. There are 1↪ 154 common authors between the two networks, forming the ground truth of anchor links.

Results and Comparison

We consider training sets with ↵t ranging from 5% to 50%, and the rest of anchor links are used for testing. For each sample ratio ↵t, we also carry out 10 runs of the experiment and report the average results as shown in Figure 4. It is shown that PALE exhibits the best performance on predicting anchor links between the two co-author networks on AI and DM. PALE (LIN) performs better than CRW in the cases where the training set is less than 30% of existing anchor links. For example, when 5% of existing anchor links are taken as the training set, PALE (LIN) outperforms CRW by 37% (from

3 The conferences selected from the AI field are IJCAI, AAAI, CVPR, ICCV, ICML, NIPS, UAI, ACL, EMNLP, and ECAI, while the conferences selected from the DM field include KDD, SIGMOD, SIGIR, ICDM, ICDE, VLDB, WWW, SDM, CIKM, and WSDM.

• (b) Different overlap level with sparsity level = 0.6

Figure 3: Performance results with different networks sampled from the Facebook dataset.

0▷1200 to 0▷1651). However, when the training fraction ↵t is greater than 30%, CRW becomes comparable to or even slightly superior to PALE (LIN), while PALE (MLP) still keeps superior. This suggests that a non-linear function can better capture the mapping relationship across latent spaces. It also justifies the validity of the PALE model.

3.4 Discussion on Network Embedding

In the PALE model, network embedding plays an important role. There are several well-known methods for network embedding, including Spectral Clustering (SC) [Tang and Liu, 2011], Graph Factorization (GF) [Ahmed et al., 2013], Deepwalk [Perozzi et al., 2014]. In this subsection we investigate the performance of the network embedding method proposed in this paper by comparing it with those existing ones. For this purpose, we replace the network embedding method proposed in this paper with those existing ones in the PALE model and then compare the performance of different PALE models, where MLP is taken as the mapping function. Moreover, we want to see how much the contribution of the cross-network extension step to PALE. For this purpose, we compare the performance of PALE with and without crossnetwork extension, denoted as PALE(-). The experiment is conducted on the AI-DM dataset, and the training set is sampled with ↵t = 30%. In Table 3, we present the average values and standard variances of F1 and MAP@30 for 10 runs. It PALE 0▷4271◦0▷0009 0▷4770◦0▷0011

can be seen that our network embedding method outperforms all existing ones.

4 Conclusions

In this paper, we proposed an embedding and matching based model for anchor link prediction, called PALE. Different from existing methods that either cope with anchor link prediction as an unsupervised network alignment problem or directly work on structural features defined on networks, the proposed model employs network embedding to keep major structural regularities of networks with awareness of supervised anchor links and then learns a stable cross-network mapping for anchor link prediction. The effectiveness of the proposed model was evaluated on two datasets. As future works, we will devote to designing a unified optimization method for anchor link prediction, balancing the costs at the network embedding and latent space matching stages.

Acknowledgments

This work was funded by the National High-tech R&D Program of China (863 Program) under grant number 2014AA015103, the National Basic Research Program of China (973 Program) under grant numbers 2012CB316303 and 2014CB340401, and the National Natural Science Foundation of China under grant numbers 61425016, 61472400, 61572473, 61572467. Huawei Shen is also funded by Youth Innovation Promotion Association CAS.