Joint Link Prediction and Network Alignment via Cross-graph Embedding

1 Introduction

Network alignment refers to finding vertex correspondences between two networks, based on both the (optional) nodewise features and edge (i.e. link) structures around vertices. In particular, node embedding models have recently received intensive attention for scalable treatment on large-scale networks with applications for node classification, etc..

Another related and widely studied problem is link prediction [Backstrom and Leskovec, 2011; Zhang and Philip, 2015], as proposed in [Liben-Nowell and Kleinberg, 2003], which aims to infer missing links in the network based on the observed links. It has a range of applications such as recommendation, knowledge management, relation mining, etc..

We argue in the paper that link prediction refers to the problem of network structure discovery and inherently relates to network alignment. Despite such a potential connection, to one's surprise, little work [Zhang and Philip, 2015] has explored the possibility for jointly solving these two tasks in a unified model. We make an initial effort in this direction and develop a cross-graph embedding model, whereby the two tasks are alternatively performed. As the structure information becomes richer by newly added links, new possible node correspondences can be identified and vice versa. As such, more links within each graph, together with the node correspondences between graphs, can be identified, leading to an improvement on recall for both tasks.

∗ Junchi Yan is corresponding author. The work was supported by the Open Research Fund of Key Lab of Advanced Theory and Application in Statistics and Data Science (East China Normal University), Ministry of Education, and NSFC 61602176 & 61672231.

In a nutshell, the main contributions of this work are:

1. We present a joint link prediction and network alignment framework, in contrast to the majority of literature focusing on either link prediction or network alignment alone.
2. We develop a cross-graph embedding method based on random walks, whereby a new random walk formula is devised to facilitate network alignment. Also, a new crossgraph embedding based link prediction method is devised.
3. We perform extensive experiments on public benchmarks to show that alternatively performing the two tasks can benefit each other. Especially the recall can be improved for both link prediction and node correspondence establishment. Furthermore, we show how the distribution of the network's degrees relates to the effectiveness of our model.

2 The ProposedMethod

We present our joint link prediction and network alignment approach, based on node embedding across networks. The two tasks can alternatively benefit to each other, as such the recall can be improved over the bootstrapping procedure.

2.1 Notations and Preliminaries

In this paper, we only consider unweighted and undirected networks and the directed version is left for future work. Also, we focus on the setting involving two networks for notational simplicity in line with the majority of literature.

Link pattern in two networks for alignment may differ in many aspects, including density, distributions, etc.. While a basic assumption is that they share corresponding vertices and some links in each network are missing due to different reasons. If we re-link all these lost edges, the aligned networks will be the same or highly similar, thus the aligning process will be easier. On the other hand, after aligning the networks, several pairs of aligned vertices will be found and will improve the link prediction in turn, as depicted in Fig. 1. Hence, we propose a cross-graph embedding-based method that alternately performs link prediction and network alignment to improve the performance of both, in a bootstrapping way.

We first give basic notations to facilitate the later discussion.

Network alignment. Given two networks for alignment (G, G′ , π) where G = (V, E, A) is network with V, E, A as its vertices, edges and attributes respectively. π : V → V ′ denotes correspondence between G and G′ : u = π(v),v = π-1 (u) and vertices u ∈ V, v ∈ V ′ correspond to each other.

Seed vertices and seed set. For network alignment, we denote the set of vertices whose correspondences have been established, via certain means or prior given beforehand by S. In this paper, we address the unsupervised setting and assume no seed vertices are available in the beginning.

Link prediction within a network. Given networks G,G′ and their alignment π, link prediction is to predict the probability of each unobserved link, which is defined as PG(u1, u2), for u1, u2 being the two unlinked vertices in G.

The k-hop neighbors. Vertex u is called v's k-hop neighbor if the distance from u to v is exactly k. Denote NG,k(u) as the set of all k-hop neighbors of vertex u in network G.

Topological and structural similarity. In this paper, we define the inverse of the shortest path distance between two vertices as their topological similarity. While their structural similarity is defined by Eq. 1 and they may not be connected via a series of links. It is useful for cross-graph modeling.

2.2 Node Embedding

Most of recent node embedding techniques on one graph, including DeepWalk [Perozzi et al., 2014], node2vec [Grover and Leskovec, 2016], LINE [Tang et al., 2015], etc., are not tailored to and cannot measure the similarity across separate networks (at least on the surface). For network alignment, even if the two networks are connected through seed vertices, the corresponding vertices in different networks may still be dissimilar to each other regarding with their embedding vectors (as will be seen in Fig. 7). Though some node embedding techniques like struc2vec [Figueiredo et al., 2017], to some extent, can obtain the structural similarities and alleviate the above problems, the topological similarity is little considered. Therefore, we propose a novel cross-graph node embedding technique that can obtain both the structural and topological similarities for nodes across networks.

Given G, G′ and their alignment π, we construct a weighted, undirected compound network. Given vertices u ∈ V, v ∈ V ′ , the structural distance between u and v is defined as f(u, v) when considering their k-hop neighbors (k = 0, 1, . . . ,K), where the 0-hop neighbor is defined as the vertex itself and K is a hyperparameter that controls the depth of structural similarities. Specifically, we define the difference between the two vertices from two networks by

where sk(u) is the rectified degree sequence of vertices of u's k-hop neighbors, i.e. sk(u) = [ ˜ d1, ˜ d2, . . . ], in which the rectified degree is specified by ˜ d = d√ |E ′ |/|V ′ | |E|/|V| for each degree d in order to maintain consistency of degree distributions in two networks. The | · | here is number of elements in a set. The dist(sk(u), sk(v)) in Eq. 1 is specified as:

Note u, v are vertices in different networks, thus f(u, v) focuses on cross-graph structural similarity. Moreover, note that only minimum and maximum degrees are concerned due to computational complexity, while we argue these two features can approximately obtain the vertices' distance 1 . We use Eq. 2 to measure the distance between u and v, however, any other technique to evaluate distance can be applied in this framework. The weight of each pair is defined as

where α is a hyperparameter that controls the distribution of weights. Then we get a weighted, undirected compound network, which we denote as ˜G, as depicted in Fig. 2. We consider a biased random walk around ˜G, as specified by:

1. Given a probability q > 0 to decide whether to walk on the current network or switch to another network (with probability q walking on the current network and probability 1 - q for network switching).
2. If the walk is on the current network, the probability of walking from vertex u ∈ V to v ∈ NG,1(u) is

1 Outside this paper, we verified this form in comparison with other forms which incorporate more fine-grained information while we find the used one in the paper is more cost-effective.

1. Given that the walk will switch networks, if the current vertex u ∈ V is a seed vertex, namely u ∈ S, the probability of walking from vertex u ∈ V to v = π(u) is:

1. If the walk will switch networks and the current vertex u ∈ V is not a seed vertex, then the probability of walking from vertex u ∈ V to v ∈ V ′ is:

where Z(u) is the normalization factor for vertex u:

Finally we use random walks to train a Skip-gram model to obtain the embedding. In particular, given a vertex, the objective of Skip-gram model is to maximize the average log probability of its context in a sequence, where the vertex's context is given by the nearby vertices in a sequence.

Since basic Skip-gram model suffers from the computational complexity, we use Negative Sampling [Mikolov et al., 2013b], whose objective is defined as follows:

where xv and x′v are the input and output vector representations of v respectively. σ(x) = 1/(1 + e-x ) is the sigmoid function and Kneg is the number of negative edges. Then we set Pn(v) ∝ d3/4 v , where dv is the degree of vertex v. By Eq. 8, the vertices' vector representations can be learned.

2.3 Network Alignment

Varieties of alignment methods e.g. [Singh et al., 2008] try to find the best overall alignments, in which each vertex in a network will be matched one or more vertices in another aligned network simultaneously. In contrast, techniques also exist [Koyut¨urk et al., 2005] that they aim to find similar motifs between aligned networks. Our method will combine the benefits of the above methods and focus on finding the most confident vertex correspondences between networks periodically. Here we further define Nk(S) as all k-hop neighbors of the vertices in G. Given vertices u ∈ V, v ∈ V ′ , we also

Algorithm 1: Network Alignment (NA)

Input: Networks G = (V, E, A), G′ = (V ′ , E ′ , A′ ); seed vertices S and S ′ ; alignment π; embedding {xu}u∈V , {xv}v∈V ′ ; number of vertex pairs T . 1 Compute F = {sim(u, v)}u∈V,v∈V ′ by Eq. 9 to 13; 2 while T > 0 do 3 T = T - 1; 4 Find a new vertex pair (u∗ , v∗ ) according to F; 5 Add new vertex to seed set of G: S = S ∪ {u∗ }; 6 Add new vertex to seed set of G′ : S ′ = S ′ ∪ {v∗ }; 7 Establish the new correspondence: π(u∗ ) = v∗ . Output: Updated seed vertices S, S ′ ; alignment π.

define the embedding similarity of two vertices in different networks by cosine similarity

where xu is the embedding vector of u and || · || is 2-norm of a vector. In order to align the most confident vertices, we only consider 1-hop neighbors of S and use a variant of Jaccard similarities to rectify Eq. 9, therefore, given u and v in N1(S) and N1(S ′ ) respectively, the similarity between them is

where | · | denotes the size of the set. Note Eq. 10 suggests if two vertices in different networks share similar corresponding vertices, they tend to have higher similarity.

When attribute A is given, the attribute similarity between vertex u ∈ N1(S) and v ∈ N1(S ′ ) can be written as

where yu is the attribute vector of vertex u. Thus, the similarity between u and v can be further written as

At last, we will search the most confident pairs of vertices as is shown in Alg. 1. If (u, v) is a new pair of seed vertices, then it will be added to S and S ′ respectively.

2.4 Link Prediction

In general, given a network G, link prediction refers to predicting the probability of each unobserved link, which can be written by PG(u1, u2), with u1, u2 being two unlinked vertices in G. In our task, a natural idea is that new links can be identified between u1 and u2 in one graph if the corresponding v1 = π(u1), v2 = π(u2) were already connected in G′ .

Therefore, we propose a link prediction method within a network for alignment that takes into account cross-graph information, as shown in Alg. 2.

Algorithm 2: Cross-graph Link Prediction (LP)

• Input: Networks G = (V, E, A), G′ = (V ′ , E ′ , A′ ); seed vertices S, S ′ ; alignment π; threshold thr. 1 Randomly sample a group of existent links Eext, E ′ext and nonexistent links Emis, E ′mis in G and G′ respectively and their labels o, o′ ; Randomly initialize link prediction classifier's parameters W = (w, b) and W ′ = (w′ , b′ ); 2 while W andW ′ not converged do 3 Compute loss function with training links Eext, Emis and E ′ext , E ′mis by Eq. 14; 4 Update W andW ′ by Eq. 15; 5 Construct edge lists Etest = S × S and E ′ test = S ′ × S ′ ; 6 for (u1, u2) in Etest and (π(u1), π(u2)) in E ′ test do 7 Compute objective l2(u1, u2) and l′2 (π(u1), π(u2)) with parameters W ′ and W respectively by Eq. 14. 8 //Note that W and W ′ are reversed. 9 if l2(u1, u2) > thr and l′2 (π(u1), π(u2)) > thr then 10 E = E ∪ {e = (u1, u2)}; 11 E ′ = E ′ ∪ {e′ = (π(u1), π(u2))};

Output: Updated networks G and G′ .

Given a group of existent and missing edges in graph G, we construct a training set for link prediction learning. As illustrated in Fig. 3, for edge e = (u1, u2) ∈ E and the node embedding of u1 and u2, we adopt a product layer [Qu et al., 2016] to extract the latent interaction between these two vertices, which is followed by a Logistic regression layer for binary classification. Formally, for input edge e = (u1, u2) ∈ E and its label oe ∈ {0, 1}, we have

where ◦ is Hadamard product, formally xu1 ◦ xu2 multiplies each corresponding elements in xu1 and xu2 with (xu1 ◦xu2 )i = (xu1 )i · (xu2 )i. The objective for link prediction classifier can be defined as:

We denote the above classifier as C. To approximate the links in G and G′ , C is utilized to perform cross prediction. Specifically, given u1, u2 ∈ S, e = (u1, u2) ∈ E, if C predicts that e′ = (π(u1), π(u2)) links in G′ , then e′ ∈ E ′ .

Note that classifiers C and C ′ only predict the links in their respective graphs that are connected to the seed vertices with established correspondences. This strategy avoids error accumulation by noise. The overall procedure is shown in Alg. 3.

3 RelatedWork

We discuss related work in node embedding, network alignment and link prediction, as involved in our approach.

Algorithm 3: Cross-graph Node Embedding for Joint Network Alignment and Link Prediction (CENALP)

Input: Networks G = (V, E, A), G′ = (V ′ , E ′ , A′ ); seed vertices S and S ′ ; alignment π.

1 while new vertex correspondences can be found do

2 Update {xu}u∈V, {xv}v∈V ′ by Eq. 4 to 8;

• 3 Search new correspondences by Alg. 1;
• 4 Predict links within a network by Alg. 2;

Output: Updated seed vertices S, S ′ ; alignment π;node embedding {xu}u∈V , {xv}v∈V ′ .

Node Embedding. There are scalable node embedding methods e.g. DeepWalk [Perozzi et al., 2014] based on random walk and node2vec [Grover and Leskovec, 2016] inspired by Skip-gram model [Mikolov et al., 2013a]. In particular, LINE [Tang et al., 2015] explicitly defines first-order proximity and second-order proximity and builds heuristics models for the two proximities. However, the techniques above cannot obtain similarity between vertices in separate networks. Though struc2vec [Figueiredo et al., 2017] learns node representations from structural identity and allows for learning representations in separate networks, it ignores topological neighbors that are crucial to network alignment tasks. In this paper, we propose a novel node embedding technique that can learn from both structural and topological neighbors.

Network Alignment. Network alignment has recently become an active area. Different features have been used to network alignment e.g. network structures[Singh et al., 2008], node attributes [Zhang et al., 2015] and edge attributes [Si and Tong, 2016]. It is common for a user getting involved in multiple social networks e.g. Foursquare, Facebook and Twitter. Such shared users among different networks are referred to as 'anchor users' [Kong et al., 2013; Tong et al., 2016]. In particular, [Zhang and Philip, 2015] connects the users by both social links and anchor links simultaneously. However, some positive anchor links have to be used to train their models and the metrics AUC and Precision@30 (i.e. correct alignments in top-30 choices) do not find a one-to-one correspondence. In our approach, we propose a cross-graph embedding-based aligning technique which enables the model to learn in an unsupervised way.

Link Prediction. Link prediction has been a well- studied area since the seminal work [Liben-Nowell and Kleinberg, 2003]. A line of works formulates link prediction as a supervised classification task [Al Hasan et al., 2006], whereby different types of links are labeled for prediction according to their physical meaning [Backstrom and Leskovec, 2011]. Meanwhile, unsupervised methods [Xiang et al., 2010] are also developed for estimating the link strength. While in our case, we perform binary prediction to estimate whether the link shall be formed or not, regardless of their detailed types.

4 Experiments

Popular datasets are used i.e. Twitter/Facebook, Douban (online and offline communities as China's popular social network), and the DBLP benchmark. For better visualization, a simple example is given in Fig. 4 to illustrate our method.

4.1 Protocols

The statistics of the used datasets are summarized in Table 1. 1) DBLP. It is collected by [Prado et al., 2013], which can be treated as a co-authorship network. Each author can be considered as a vertex and authors' academic cooperation as the links. Each author is associated with an attribute vector representing the number of publications in computer science conferences. To generate a similar but slightly different network to align, we randomly drop 10% edges and flip 10% attribute information in line with [Si and Tong, 2016]. 2) Facebook/Twitter. A cross-graph constructed from two real-world social networks as collected and published by [Cao and Yong, 2016]. Facebook and Twitter are the most popular worldwide online social network and micro-blog website respectively. Each social account is treated as a vertex and accounts' friend relationship as edges. If a real-world user owns both Facebook and Twitter accounts, these two accounts will be treated as an alignment between two networks. In this task, no attribute information is used. 3) Douban online/offline. A real-world social network extracted from which is collected and published by [Zhong et al., 2012]. It has an online social network and an offline social network to align. Users' locations are treated as attributes.

We compare CENALP and its variant CENA to baselines by accuracy i.e. proportion of correct node correspondences of the total correspondences. We also evaluate the impact of the missing ratio of links in our experiments.

We compare our approach with the following methods:

1) DeepWalk. Random walk based network embedding model [Perozzi et al., 2014] inspired by language model; 2) Struc2vec. Node embedding method [Figueiredo et al., 2017] based on structural identity; 3) IsoRank. Global alignment method initially with application to protein interaction networks [Singh et al., 2008]; 4) FINAL. State-of-the-art graph alignment algorithm [Si and Tong, 2016] considering both node attributes, edge attributes and graph structures. FINAL needs a prior alignment as input, which is not applied in our approach. So we treat it as attribute similarity alignment. And if not, the uniform is used; 5) CENALP. Our proposed framework with joint alignment and link prediction over iterations; 6) CENA. A variant of our approach with only crossgraph alignment one time without link prediction.

The parameters commonly used in the compared methods are set the same for a fair comparison. Specifically, the dimension of node embeddings, including DeepWalk, struc2vec and our proposed method, is universally set as 64. The maximum depth of neighbors to hop is set as K = 2. The parameter in Eq. 3 is set as α = 5. The probability controlling whether to switch networks is set as q = 0.3.

4.2 Results and Discussion

Recall and precision. As shown in Fig. 5, by joint link prediction and network alignment, recall increases while precision is stable. We evaluate alignment accuracy and influence of missing links for different methods. The results are depicted in Fig. 6. The proposed CENALP achieves the highest alignment accuracy in DBLP and Facebook/Twitter networks while CENA achieves the second highest in Douban, under different values for the ratio of missing links against all links in the datasets. In contrast, DeepWalk and struc2vec tend to drop as link missing ratio grows. Also, the scatter plots of node degrees in two networks are given on the right, from which one can see that CENALP works well when the scatters are more linearly distributed (DBLP and Facebook/Twitter

(c) Douban online/offline

Figure 6: Alignment accuracy by varying: edges missing ratio levels (left) and degree scatters after log transformation (right) of networks.

in contrast to Douban). This helps users to decide if our method is applicable for their practical tasks. In general, the alignment accuracy of DeepWalk is low and sometimes approaches random guess. In our analysis, this is because DeepWalk cannot obtain similarities in separate networks. For struc2vec, it can only learn structural neighbors and ignores topological neighbors, thus not suitable for aligning tasks, though it performs better than FINAL and IsoRank in Facebook/Twitter. FINAL and IsoRank are two aligning methods that depend on both structure and prior alignment, therefore in our expectation, they perform badly in Facebook/Twitter due to the lack of attribute information and prior alignment. In summary, though our proposed methods do not always perform best, it is suitable for aligning networks whose degree scatter plots are narrowed, or in case when the attribute information is absent. Our approach learns not only information from topological neighbors (within graph), but also the one from structural ones (cross-graph), since the biased random walk is both within and cross-graph, and based on Eq. 4, 5 and 6. We compare the distribution of embedded vertices with different embedding techniques as depicted in Fig. 7, and tend to conclude that our methods perform better in obtaining both topological and structural information.

Time overhead. Though our method covers embedding, alignment and link prediction, the time cost mainly depends on sampling time for random walks. Specifically, the task for DBLP and its disturbed copy with 2,151 nodes and 22 iterations can be finished in average 94 seconds per iteration. Douban online/offline with 1,118 nodes and 18 iterations spend in average 116 seconds per iteration and Facebook/Twitter with 1,043 nodes and 12 iterations spend in average 53 seconds per iteration on our desktop with 2.1GHz CPU and 16G memory. By comparison, for the task DBLP and its disturbed copy, IsoRank and FINAL spend around 7 seconds and 16 seconds respectively while the embeddingbased methods DeepWalk and struc2vec spend 86 seconds and 183 seconds respectively. Recall that our method CENA can be regarded as the running of the first iteration, which is still competitive against baselines as shown in Fig. 6. By our design, CENA focuses more on accuracy to ensure the subsequent iteration will not be influenced by wrong vertex correspondences. In fact, our method in each iteration has the same time complexity with Deepwalk.

5 Conclusion

We have presented a joint link prediction and network alignment framework for improving the recall for both of the two tasks. We also develop a cross-graph embedding technique based on structural and topological neighbors to effectively enable the node to embed from separate graphs.

We also empirically show the condition under which our bootstrapping method can perform in expectation and suggest the possible failure case. We believe this is important as inherently our method may encounter error accumulation which is common to many self-learning like methods.