Scalable Multiplex Network Embedding

1 Introduction

Network or graph embedding, which uses dense vectors to represent nodes, has been well studied for many years [Archdeacon, 1996; Chung, 1997; Goyal and Ferrara, 2017]. Recently, inspired by recurrent neural networks [Goodfellow et al., 2016], network embedding has been re-investigated and developed based on random walks over graphs and stochastic gradient descent optimization, which can be applied to very large graphs, such as real social networks [Perozzi et al., 2014; Tang et al., 2015; Grover and Leskovec, 2016]. The embedding vector of nodes can be used to encode some of the topological structure of the network, and then can be used as features for downstream models. Network embedding has been proven to be helpful for network analysis tasks including link prediction, node classification, and community detection.

Multiplexity property is a common feature of networks, especially for social networks. In the social network analysis, multiplexity refers to multifaceted relationships between two people [Verbrugge, 1979]. If we generalize this idea to all kinds of network, by "multiplex network," we mean a group of networks which contains multiple kinds of relations, and each kind of the relations can create a layer of the network. Take the social network as an example. In a social network such as Facebook, users often have different kinds of interactions with each other like friendship relation, forwarding articles to each other, conversation, money transferring, etc. Each of them will create a layer of the network among all users. If we consider them as a united one, we will get a huge multiplex network. While each layer of the network can only represent one kind of interactions among users, to better understand the whole multiplex network, it is better to integrate different types of information from these networks together without sacrificing their distinctive properties.

Considering the fact that a network could be huge, in this paper, we present a scalable multiplex network embedding model to efficiently store and learn information of multi-type relations into a unified embedding space. For each node, we propose one high-dimensional common embedding vector, which is shared across all layers of the multiplex network, and we use that to build a bridge among different layers of the network. For each node, to learn its distinct property on different layers with small memory occupation, we also propose a low-dimensional additional vector for each type of relation. To align these embeddings with different dimensions together, we introduce a global transformation matrix for each layer of the network. Following DeepWalk [Perozzi et al., 2014], we use stochastic gradient descent to optimize our model. Since the global transformation matrix will be updated much more times than node vectors will be, we add an additional regularization to constrain the size of the matrix.

Our contributions can be summarized as follows.

• We formally define the problem of multiplex network embedding to handle the multiplexity property of networks.
• We propose a scalable multiplex network embedding model to represent information from multi-type relations into a unified embedding space.
• We evaluate our embedding algorithm on two network analysis tasks: link prediction and node classification. On both tasks, our model achieved better or comparable performance compared to current state-of-the-art models with less memory use.

The source code of our model is available at: https://github.com/HKUST-KnowComp/MNE.

2 RelatedWork

2.1 Multiplex Network Analysis

Traditionally in social science, multiplexity has been used to characterize the multiple facets of social exchange relationships among users [Verbrugge, 1979]. The idea of multiplexity can be generalized to all kinds of network. In data mining community, people sometimes also use the term "multi-relational network" to represent the multi-type relations in social networks and verified that considering such relations in the social network can help data mining tasks such as community mining or link prediction [Cai et al., 2005; Chen et al., 2016]. In addition, in bioinformatics community, it has been shown that by integrating multiple networks, the node representation can be improved for genes functional analysis [Cho et al., 2016].

Nowadays, graph mining methods on the multiplex network are mainly targeting on specific tasks. For link prediction, traditional methods [Newman, 2001; Adamic and Adar, 2003] can be applied to multiplex network without considering the information of the typed edges. For community detection, cross-layer centrality measurement [Br´odka et al., 2012] is proposed to capture the centrality of nodes in a multiplex network. Besides that, multilayered local clustering coefficient (MLCC) and cross-layer clustering coefficient (CLCC) [Kazienko et al., 2010; Lytras et al., 2010] are also proposed to describe cluster coefficient of a node in a multiplex network.

In this paper, we propose a general solution for multiplex network analysis from the perspective of network embedding.

2.2 Network Embedding

Network embedding (or sometimes called graph embedding, historically also graph drawing) has been well studied for many years [Archdeacon, 1996; Chung, 1997; Goyal and Ferrara, 2017]. It is also related to manifold learning [Huo et al., 2007] while manifold learning was usually applied to dimensionality reduction for high-dimensional data. Network embedding focuses on generating the vector representation of nodes for real networks or graphs to facilitate further analysis of networks. Traditional approaches to network embedding usually involve time-consuming computational components, such as eigenvalue decomposition to analyze the spectral property of graphs [Spielman, 2011]. However, given modern very large-scale online social networks, such approaches may be less efficient and sometimes infeasible to generate the node representations.

Recently, inspired by the development of recurrent neural networks [Goodfellow et al., 2016], particularly the efficient word embedding method, word2vec [Mikolov et al., 2013b; Mikolov et al., 2013a], many network embedding approaches have been proposed to handle large-scale social networks. For example, DeepWalk [Perozzi et al., 2014] proposes to perform random walk on the network to generate sequences of nodes and then perform skip-gram algorithm (a technique used in word2vec) on those sequences to achieve the embedding. On top of DeepWalk, Node2Vec [Grover and Leskovec, 2016] adds two parameters to control the random walk process and make it biased random walk. Some other embedding models focus on specific kinds of structures in the network. For example, LINE [Tang et al., 2015] tries to use the embedding to approximate the first-order and second-order proximities of the network.

All the models above have been proven useful on single network analysis, but they did not consider multiplexity. Recently, an embedding approach is proposed to target the multiplexity property [Liu et al., 2017]. They proposed three methods to learn one overall embedding from the multiplex network. Unlike their approach, we propose one high-dimensional common embedding and several lowerdimensional additional embeddings for each type of relations. A recent work [Li et al., 2018] called itself multi-layer network embedding. Essentially, it is a heterogeneous information network since in the definition in their paper, different layers have different type of nodes.

3 Multiplex Network Embedding

3.1 ProblemDefinition

We first introduce our problem and notations. Given a multiplex network, our goal is to learn a representation for each node. Suppose N is the set of nodes and there are M different relation types, represented as G1, ..., GM. For each relation based network Gi = (Ni, Ei), we have Ei ⊆ Ni ×Ni and Ni ⊆ N.

For each node n ∈ N , it has one common embedding vector, which is shared across all the relation types and denoted as bn ∈ Rd . We use that common embedding as a bridge to transfer information across different relation types. To capture the distinct property of each sub-network, for each node, we also propose a series of low-dimensional vectors uin ∈ Rs for each relation type i. Here, d is the dimension of common embedding and s is the dimension of typed relation vector. To avoid our model becoming too large, we set s ≪ d ≪ |N|, where |N| is the number of all nodes. To align bn and uin , we introduce a transformation matrix Xi ∈ Rs×d . Then we use a new vector vin to represent the embedding vector of n for relation type i:vin = bn +wi · XiT uin , (1)

where we use a weight wi to denote the overall importance of relation type i.

3.2 Optimization

For each relation type i of the multiplex network, we conduct random walk to generate a sequence of nodes and then perform Skip-gram algorithm used in word2vec [Mikolov et al., 2013a] over the sequences to learn the embeddings. As shown in Eq. (1), a node's final embedding is composed of three parts: common embedding bn, relation-based embedding uin , and transformation matrix Xi . We need to learn these parameters at the same time.

For any node n in a random walk path relation type i, assuming it appears in position j, we will take nj-c, ..., nj+c as its neighbors, where c is half of the window size. Thus, given a sequence of nodes, our objective is to minimize the following negative log-likelihood:

which can be further factorized as - ∏j-1 k=j-c logPθi(nk|nj)·

∏j+c k=j+1 logP(nk|nj) given the conditional independence assumption. Here we use Pθi to denote the parameterization for relation type i. For each Pθi(nk|nj), a softmax function is used to define the probability:

where vinj represents the input word embedding of user nj, and v′nk , and v′n represent the parameters of context vectors shared by all relation types, which are only used during the training process. To speed up the training process, following word2vec [Mikolov et al., 2013a], we use negative sampling to approximate the objective function as:

where σ(x) = 1/(1 + exp(-x)) is the logistic function and N inj is the randomly sampled negative context node set for nj .

Assuming the sequence is generated in relation type i, according to Eq. (1), in the new objective function, we can replace vin with bn +XiT uin . After that we employ stochastic gradient descent (SGD) to minimize the objective function. We update the context parameter vectors, node embedding vectors, and transformation matrix as follows:

where e(nj , nk) = σ(v′nk T · vinj ) - tk and tk=1 if nk is the neighbor of nj and tk=0 if nk is in the negative sampling set.

We initialize all the vi with zero vector and Xi with zero matrix. For context parameter vector v′n for all the users, we randomly initialize them. Since Xi 's can be updated many times when optimizing the objective function, to avoid its norm becoming too huge, we add the following constraints:

where r is a controlling parameter for the Frobenius norm of matrix ||Xi ||. In our experiment, we also involve an extra combination layer and since this layer has no actual meaning, we will only update common embedding during the training on that layer.

We summarize our algorithm in Algorithm 1. As our model is a random walk based solution, assuming that we have M relation types of sub-networks and |N| nodes, the time complexity of our model is O(M|N|). The memory complexity of our model is O((d + s ∗ M)|N |).

Algorithm 1 Multiplex Network Embedding

INPUT: Multiplex network which is composed of sub networks G1, . . . , GM, common embedding dimension d, additional embedding dimension s, learning rate η, size of context window c, number of negative sampling k, transformation matrix size regularization parameter r.

• 1: Initialize bn, vin and Xi for different nodes n's and relations i's.
• 2: for Each relation network Gi do
• 3: for Each path P generated by random walk do
• 4: for nj ∈ P do 5: for nc ∈ P [j - c, j + c] do 6: Nnj = NegativeSampling(N,m) 7: vinj = bnj +XiT uinj 8: Nsample =Nnj ∪ nc 9: for nk ∈ Nsample do 10: e(nj , nk) = σ(v′nk T · vinj ) - tk 11: Update bnj , v′nk , uinj , and Xi based on Eqs. (5), 6), (7), and (8) respectively. 12: end for 13: if ∥∥Xi∥∥ > r then 14: Xi := r ‖Xi ‖ · Xi 15: end if 16: end for 17: end for 18: end for
• 19: end for

OUTPUT: Common embedding bn, additional embeddings uin , and transformation matrix Xi for different nodes n's and relations i's.

4 Experiments

4.1 Datasets

We use open multiplex networks from Manlio De Domenico project 1 as our experimental datasets. We select four multiplex networks from different network types. The selection criteria are that they cannot be too small and they cannot be too sparse, which means that they should have at least one edge per node per relation type. The details of these datasets are as follows:

Vickers [Vickers and Chan, 1981]: Data collected by asking 29 seventh grade students in a school in Victoria, Australia, for whom they asked three questions and each of them creates a relation type of the network.

• CKM [Coleman et al., 1957]: Data collected by asking physicians in four towns in Illinois, Bloomington, Quincy, and Galesburg. They asked three questions and each of them creates a relation type of the network.

LAZEGA [Lazega, 2001]: This multiplex social network consists of three kinds of relationships (Co-work, Friendship, and Advice) between partners and associates of a corporate partnership.

C.ELEGANS [Chen et al., 2006]: This multiplex network consists of layers corresponding to synaptic junctions:

1 http://deim.urv.cat/~manlio.dedomenico/data.php

electric ("ElectrJ"), chemical monadic ("MonoSyn"), and polyadic ("PolySyn") among a group of neurons.

Since the sizes of the above multiplex networks are relatively small, to test the scalability and performance of our model, we also conduct experiments on two real large-scale online social media networks: Twitter and Private. The detailed information of these large scale social networks are as follows:

Twitter: The Twitter data used in our experiments is the higgs-twitter dataset 2 . This dataset was used to analyze the spreading of news [De Domenico et al., 2013]. It crawled all tweets about a scientific term "Higgs boson discovery" in one week. We select the largest two sub-networks (following and retweet) to build the multiplex network.

Private: Our Private data is based on an online social network, where users can have friendship relations with each other and can send articles to their friends. From all of our users, we randomly chose 40,000 users who have annotated themselves affiliated with a university and we recorded all the article forward activities within that group in one month. After applying topic modeling on the content of the articles, we grouped all the articles by topics. Thus, we got 16 topics and each one of them creates a relation type of the multiplex network. If we add the base friendship relation, we have in total 17 relation types.

The statistics of these datasets are listed in Table 1.

4.2 Baseline Methods

We will first compare our model with following state-of-theart embedding-based baseline methods.

• DeepWalk: DeepWalk [Perozzi et al., 2014] first applies random walk on the network, treats the path as a sentence, and then uses Skip-gram algorithm to train the embeddings.
• LINE: LINE [Tang et al., 2015] adds direct link fitting term to the DeepWalk cost function, and adds second hop friends into one hop friends to incorporate higherorder relations.
• Node2Vec: Node2Vec [Grover and Leskovec, 2016] adds a pair of parameters to control the random walk process and makes it better for certain types of nodes, such as hubs or tail users.
• Principled Multilayer Network Embedding: PMNE [Liu et al., 2017] proposed three different models to merge multiplex network together to generate one overall embedding for each of the node, we will

2 https://snap.stanford.edu/data/higgs-twitter.html

compare our model with all of their three models. We denote their network aggregation, results aggregation, and Co-analysis model as PMNE (n), PMNE (r), and PMNE (c) respectively.

Besides the above embedding methods, we will also compare our embedding model with the state-of-the-art network structure-based methods for the link prediction task.

• Common neighbor (CN): The CN metric is one of the most widespread measurements used in link prediction tasks due to its simplicity [Newman, 2001]. For each pair of nodes, the more common neighbors it has, the more likely it will have one edge.
• Jaccard Coefficient (JC): For a pair of nodes, JC normalized the number of common neighbors with the number of their total neighbors.
• Adamic/Adar (AA): AA [Adamic and Adar, 2003] is similar to JC, but unlike JC, AA gives more weight to the nodes with fewer neighbors and compared with other structure-based methods, it achieved state-of-theart performance on a series of networks [Liben-Nowell and Kleinberg, 2007].

4.3 Experimental Settings

Evaluation Metrics

For link prediction, following the commonly used evaluation criteria in similar tasks, we use ROC-AUC [Hanley and McNeil, 1982] as the evaluation criteria in our experiment. A higher value represents better performance and an ideal model that ranks all the positive samples above negative samples will achieve AUC value of 1. For Node Classification, we employ the ℓ2-regularized logistic regression on learned embedding to train classifiers and we evaluate all the embedding models based on the prediction accuracy.

Model Parameters

To be fair, following their original papers, for all the embedding based methods, we set their embedding dimensions and the dimension of common embedding in our model to be 200. For all the random walk based methods, we set the width of the window to be ten and select five negative samples. As LINE has two kinds of embedding (the so-called first-order proximity and second-order proximity), we set the embedding dimension for both embeddings to be 100 and concatenate them together. For Node2Vec, we empirically use the best hyper-parameter for training, which is p = 2 and q = 0.5. For the three PMNE models, we will use the hyperparameters given by their original paper. For our algorithm multiplex network embedding (MNE), we simply set the dimension of additional vectors to be 10.

4.4 Link Prediction

As shown in Table 2, we evaluate AUC values of different models on all of the datasets with five-fold cross-validation setting. Following other embedding methods, for each pair of nodes, we calculate the cosine similarity of their embedding. The larger the similarity the more likely there exists a link between them. As the multiplex network has more than one relation types, we will compute AUC for each relation type first and take the average of all the relation types as the final result. For the models designed for single layer network, we will train a separate embedding for each relation type of the network and use that to predict links on the corresponding relation type, which means that they do not have information from other relation types of the network. One thing worth mentioning is that, in the two large online social network, the following/friendship network is the base network for other relation types. For example, in our Private data, one can only send articles to their friends. To make the evaluation more similar to our real task, for the AUC evaluation of these two datasets, we will randomly select the same amount of edges from the base network, which do not appear in that relation type to be the negative examples and we will not evaluate the base network. Based on the experiment results, we have the following interesting observations:

(1) For nearly all the networks, jointly considering different relation types of the network is helpful. The models that take the whole network into consideration outperform all the models designed for the single network (Deepwalk, LINE, Node2Vec). This is consistent with our assumption that the information from any single network is not enough and information in different relation types can be the complement to each other.

(2) The performance of baseline methods varies a lot based on the topological structure of different networks. For example, if the network is a dense one like LAZEGA or C.ELEGANS, the performance of traditional simple methods are good enough, sometimes even better than the embedding based approach. However, when the network is relatively sparse like Vickers or CKM, embedding based methods have better performance.

(3) The main difference between our model and PMNE is that PMNE generates one overall embedding for a node and our model generates a set of embeddings to capture the distinct information about each relation type. The experimental results show that such information could be important, especially on our Private dataset, where difference among different relation types of the network is more obvious.

To summarize, on six multiplex networks, our model can stably outperform or achieve comparable performance with all the baseline methods. Our understanding is that the common embedding in our model merges information from different relation types, and the additional vectors keep the distinct property of each relation type of the network.

4.5 Parameter Sensitivity

In our algorithm, there are three parameters: the dimension of low-dimensional addition vectors s, the weight of additional vectors wi , and the transformation matrix norm limitation r. To clearly show the influence of these parameters, we repeat our link prediction experiment with different parameter settings. For the small multiplex datasets, we take the average of them to see the trend.

As shown in Figure 1(a), the performance of our model is improved when we increase the dimension of the additional vector. When the dimension reaches 10, the performance reaches the top, which proves that with the help of common embedding, we can use a very low dimension (about onetenth of the base dimension) vector to represent the property of each relation type of the multiplex network.

As shown in Figure 1(b), when we increase the weight of the additional vector, the performance of our model will arise. But after reaching to 1, the performance will start to go down slightly. This is because in our embedding training phase, we fixed the weights as one. It seems tuning this weights using cross-validation does not further improve link prediction.

As shown in Figure 1(c), if we set the regularization parameter of the transformation matrix to be too small, we may restrict the learning process of our model. When the regularization parameter is larger than 10, the performance becomes stable and the influence of our restriction is not significant.

4.6 Node Classification

In this section, we conduct the experiment on node classification task to evaluate the quality of embedding captured by our model. As the CKM social network is the only multiplex network that provides the ground truth about node labels, we use it as the experimental dataset. Considering the size of datasets being small, we conduct 2-fold cross-validation experiment on this task. The dataset labels all the researchers with their original companies. We use this feature as labels

(a) additional vector dimension s

to train the classifier and evaluate our embedding. For Deepwalk, LINE, and Node2Vec, as they are designed for single network, we first train a separate embedding for each relation type and average them as the final embedding for each node. For our model, we set the weight wi of all the types to be 1.

The result is shown in Figure 2. Our model can achieve the best performance among all the embedding models. This proves that through simple average operation, our model can produce the high-quality overall representation of nodes.

4.7 Scalability of Our Model

In this section, we investigate the scalability of our model with our large-scale online social network. As we all know, in real life, the social network could be huge. For example, there are about 1 billion active users on our private social network. Every day, more than 500 million relational edges are created. If we learn embedding for all of the sub-networks, the training and storage of these models could be a big challenge. Hence we propose the structure of small additional vector and transformation matrix, trying to reduce the overall model size without sacrificing the overall performance.

As shown in Figure 3, the memory used by our model is almost linear to the network size. Compared with Node2Vec and LINE, our model occupy one-tenth of the memory space without sacrificing performance. The reason is obvious. As we showed in section 3, the memory complexity of our model is O((d + s ∗ M)|N |) and the memory complexity of Deepwalk and LINE is O((d ∗ M)|N|), where s is designed to be much smaller than d. For the PMNE(n) and PMNE(c), as they merge the multiplex network into one single network, their model is the smallest but their model loses distinct information about relational edges, which is proved important in the previous experiment.

5 Conclusion and FutureWork

In this paper, we present a new scalable embedding model for multiplex networks. We tested our model on two tasks: link prediction and node classification. The experimental results show that our model can effectively capture the overall representation of nodes without sacrificing the distinct property of every single relation types. We also conduct scalability experiments using our social network to show that when the network is large, we only need one-tenth of the old model size to achieve better performance. In the future, we will explore the idea of multiplex network for tasks in other areas.

Acknowledgments

This paper was supported by HKUST-WeChat WHAT Lab, China 973 Fundamental R&D Program (No. 2014CB340304), and the Early Career Scheme (ECS, No. 26206717) from Research Grants Council in Hong Kong.