Network embedding has become a very promising technique in analysis of complex networks. It is a method to project nodes of a network into a low-dimensional vector space while retaining the structure of the network based on vector similarity. There are many methods of network embedding developed for traditional single layer networks. On the other hand, multilayer networks can provide more information about relationships between nodes. In this paper, we present our random walk based multilayer network embedding and compare it with single layer and multilayer network embeddings. For this purpose, we used several classic datasets usually used in network embedding experiments and also collected our own dataset of papers and authors indexed in Scopus.
1.1
Many complex and large systems can be represeneted as networks. Examples include social networks, transportation networks, information networks, biological networks, etc. It is a known fact that these networks are often very complicated and because of this they are challenging to analyze. Thus, to deal with them e ectively one needs to nd an appropriate and e ective network representation. This means concise and precise enough representation that will suit well for di erent kinds of tasks such as analysis and prediction and that will make algorithms performing these tasks time and space e cient. ? Copyright c 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). ?? Sections 1{3 on network embeddings and data collection were prepared with support by the Russian Science Foundation under grant 19-11-00281. Section 4{6 were prepared with support by the Russian Science Foundation under grant 17-11-01294.
Due to the growing size of modern networks, the traditional ways of network representation such as adjacency matrices, nodes and edges lists has become computationally ine cient. This leads to development of network embedding methods. These methods produce low-dimensional vector representations of the network nodes. The relationship between nodes, which in traditional models was presented as edges between those nodes, in case of network embedding takes form of a distance between corresponding vectors of the nodes in an embedding space. The smaller the distance { the more "close" nodes are considered to each other. Moreover, the nature of embeddings appeared to be able to preserve the structure of input network.
Network embedding is a very promising technique widely used today for many network analysis tasks, such as node classi cation, node clustering, network alignment and link prediction. It is used in many areas such as social networks analysis, transportation networks analysis, neuroscience, etc. In current work, we focus mainly on a link prediction task. 1.2
Standard multilayer or multiplex network can be considered a set of networks (often called layers or subnetworks), which share the set of nodes but di er in set of edges. More formally, a multilayer network is a tuple:
M N = (V; E; L); where V is the set of nodes, E is the set of layers and L is the set of multilalyer edges such that:
E
f(x; y; l)jx; y 2 V; l 2 Lg Multilayer networks re ect di erent kind of relationships between nodes. Each layer depicts its own type of relationship. Analyzing multilayer network can produce more promising results in di erent network analysis tasks because models based on multilayer networks capture information from several types of relationships. A trivial example of such analysis is the following. Consider some user's networks of contacts in di erent social networks such as Vkontakte, Facebook and Instagram. If we see that this user has a friend in Vkontakte but they are not friends in Facebook we can recommend him to add a friend from VKontakte as a friend in Facebook also, if we have direct node-to-node correspondence between di erent layers nodes.
Another type of multilayer network, which is not widely used, is a set of networks where layers do not share the set of nodes, but we can associate particular node from one layer with its counterpart from another layer. We consider a multilayer network with two layers: (1) (2) { Co-authorship of scienti c papers; { Citations between scienti c papers. Obviously, given an author from the rst layer we can get all his articles (which are basically its adjacent edges) and thus associate them with a set of nodes from citation networks. 1.3
In this work, we focus mainly on a link prediction problem. It is a task of learning a model based on original network, which, given two nodes, produces a probability of an edge between them. Formally, given a multilayer network M N = (V; E; L) we aim to learn a function f : V ! Rd that embeds nodes from V into a low-dimensional vector space. After learning two nodes u and v representations we compute probability between them based on softmax approximation of their dot product of corresponding embedding vectors f (u) f (v). Then, standard binary classi cation framework is trained for link prediction using negative sampling for balancing classes of existing edges and non-connected pairs of nodes.
Link prediction is a very crucial task for social networks. For example, it is used in Vkontakte, Facebook, Instagram to recommend friends to users or in LinkedIn to recommend companies hiring new employees. 2 2.1
There are many methods of embedding single layer networks, the most widely
known are LINE[
The commonly used models include traditional centrality measures extensions,
matrix factorization, random walk, deep neural networks and their variations.
Traditional centrality measures extensions As an extension of traditional
centrality measures there are works that incorporate cross-layer degree
centrality [
Another method based in matrix factorization is MANE[
Methods based on matrix factorization can do well in some cases (usually when analyzed networks are small) but they have one big drawback. When large networks are analyzed (which is usually the case because modern networks are extremely large) these methods can lead to computational errors and are very slow.
One of the way to use random-walks based methods on a multilayer networks is to merge all layers into a single network and then use random-walks based methods for single-layer networks. But during the process of merging layers su cient part of information about nodes relationship in di erent layers is lost.
Besides that there are already invented random-walks based methods for
multilayer networks. One of them is PMNE(c)[
Another random-walk based method is OhmNet[
There are many other network embedding methods using random walks, each
of them generates these walks in its own way. Examples are Scalable Multiplex
Network Embedding [
For conducting experiments in this work, a new dataset was collected. With the
use of Elsevier API[
Layers
co-authorship 14749 62060
citations
In order to obtain two networks described in previous sections, we needed to nd
a way to interact with Scopus site and with Elsevier's API to Scopus database.
There were several options on how to make this interaction:
{ Interacting with Elsevier's API to Scopus database. This API provides
several functions to retrieve data from Scopus. The most universal function is
"Scopus search". With use of this function one can send http requests to an
url \https://API.elsevier.com/content/search/Scopus" and retrieve needed
information about published articles. Bene ts of this method is its exibility.
There are many con gurable parameters that ease the process of acquiring
data. Main drawback of this method is restrictions that exist for a user,
which does not have su cient privileges. Any user who registers at Elseveir
will have those insu cient privileges. But a user with a subscription to
Scopus is able to download needed data. Another drawback is the restriction
on the number of requests to Elsevier's API. Each user can have up to 10
API keys but each key allows one to send 20000 requests. After sending this
number of requests one has to wait for a week to be able to use this API key
again.
{ There is a library called elsapy[
After research the decision was made to use rst method. 4
We propose a model of embedding a Scopus multilayer network using randomwalk approach. The algorithm consists of three steps. In step one, random walk is generated from a co-authorship network. Then, in step two, starting node of this random walk is considered. All its adjacent edges are taken and then their `artId' attribute is considered. Set of these attributes is now a new starting node on a citations layer. Short random walks (of size 1-2) are generated on citations layer. After that, terminating nodes of these walks are considered. Edges from co-authorship layer having `artId' in set of terminating nodes are taken. Ends of these edges are added to the end of random walk generated on step one. Steps one and two are repeated until desired number of random walks is reached. At step three, skipgram model is trained on obtained random walks.
This model allows us to use the topology of the second layer of multilayer network and thus consider relationship between nodes in it. An algorithm of our method is presented below.
Data: M ultilayernetworkM N withtwolayers : co authorsiplayerandcitationslayer, numW alks, walkLength, shortW alkLength Result: N etworkembeddingf f orM N Initialize walkList to empty; walkList := generateRandomW alks(M N (Layer1); walkLength); for i from 1 to numW alks do startingN ode = getStartingN ode(walkList(i)); secondLayerStartingN odes = getAttributes(adjacentEdges(startingN ode); artId) walkListSecondLayer = generateRandomW alks(M N (Layer2);; secondLayerStartingN odes; shortW alkLength) terminatingN odes = getT erminatingN odes(secondLayerStartingN odes); walkList(i)+ = terminatingN odes end f node2vecSGD(walkList)
Algorithm 1: Algorithm for proposed model
To demonstrate e ectiveness of multilayer network embedding algorithms rstly we apply baseline methods on classic multilayer networks datasets. We choose PMNE method (all three of its variations) to demonstrat superiority of multilayer embedding over single layer embedding. Then we apply baseline methods including PMNE and our method to Scopus dataset. 5.1
For our experiments we use datasets of multilayer networks from site of Manlio
De Domenico [
This network is based on the survey of 29 seventh grade students from Victoria, Australia. They have been asked three questions. Each question is a di erent type of relationship in the network.
CKM :
This network is based on the survey of physicians from Illinois, Bloomington, Quincy, and Galesburg. They have been asked three questions. Each question is a di erent type of relationship in the network.
This is a social multiplex network. There are three types of relationships (Co-work, Friendship, and Advice) between partners and associates of a corporate partnership.
Description of datasets statistics is available at Table 5.1.
Dataset #layers #nodes #edges Vickers 3 29 740 CKN 3 246 1551
LAZEGA 3 71 2223 5.2
Our model will be compared to the following baseline methods:
As it was stated before, this method generates several random walks on the network and then uses skipgram model to learn embeddings.
This model also generates random walks as the DeepWalk but adds its own term to cost function. Also is considers second order neighbors along with rst order neighbors to incorporate higher order relations.
Node2Vec uses two additional parameters to control generation of random walks. It performs better than DeepWalk in some of the cases.
In their work, authors of PMNE suggested three models of merging multilayer network in order to produce embeddings for each node. They're usually denoted as PMNE (n) (network aggregation), PMNE (r) (results aggregation), and PMNE (layer co-analysis) Apart from baseline embedding methods our model will also be compared to well-known network structure methods used for link prediction.
Given two nodes u and v JC is computed as follows: where N (:) is the neighborhood of a node.
AA acts almost like JC but it weights nodes with fewer neighbors more than JC. It is computed as follows: (3) (4) 5.3
As we were considering link prediction task, we used ROC-AUC as the criteria. It is very common practice to use this metric. Higher value of ROC-AUC means that model has great performance in link prediction. Value one means that the model perfectly predicts all the links. 5.4
For all baseline methods, we set dimension of embedding space to 200. For random walk methods, window parameter is chosen to be 10, negative sampling size is 5. For LINE model, the dimension of embedding space is 100 as it creates two embeddings and merges them into one. For Node2Vec, as stated in their work, best parameters are p = 2 and q = 0:5. For PMNE model, methods the parameters are chosen according to the original paper.
jN (u) \ N (v)j jN (u) [ N (v)j
X z2N(u)\N(v)
1 log(jN (z)j)
In our experiment, we use ve-fold cross-validation. Also we chose negative samples of non-existing edges in the network. Size of negative sample is 20% of testing sample size.
The results are stated in Table 5.5.
From the results, we can see that in case of large enough multilayer networks, methods of embedding single layer networks perform worse when compared to multilayer network embedding methods, such as PMNE (all variants) and our method. Also we can state that our method performs equally or even slightly better than PMNE on several of selected datasets.
Still PMNE performs better than our method. One of the interpretations of this result can be the fact that PMNE uses information from \merged" network, i.e., it uses larger neighborhoods from all of the layers whereas our method use full random walk on the rst layer producing large neighborhoods but it does not use all nodes from the second layer, retaining only terminal nodes.
We also made an attempt to interpret why does our method outperforms single layer network models. We took node2vec method, which was run on co-authorship layer of Scopus network. As it was stated earlier, some edges were removed from network to obtain test set. We have searched for an edge in this set, which was not predicted by node2vec but was predicted by our method. It is the edge (`57189500027', `8592870000'), numbers here are Scopus ids of authors. Then we looked at articles published by these authors in the citations layer. There was edge (`85029806407', `85028755866'), so article `85029806407' was published by `57189500027', and article `85028755866' was published by `8592870000'. Because our method considers short paths in citations layer, edge (`85029806407', `85028755866') was predicted by it and terminal node `85028755866' was explored. Then all authors of `85028755866' were added to random walk, including `8592870000'. This is a good example of how our method incorporates network relations from second layer to make predictions in the rst layer.
In this work, we presented new model of embedding multilayer networks. It was shown that it performs equally and in some cases better than PMNE, a well known method for embedding multiplex networks. Also it was shown that single layer networks embedding methods perform worse than multilayer network embedding methods when multilayer network is given and is a part of highly correlated relations between corresponding nodes across the layers.