# MultiSAGE: a multiplex embedding algorithm
for inter-layer link prediction

Luca Gallo, Vito Latora, and Alfredo Pulvirenti L. Gallo and V. Latora are
with the Department of Physics and Astronomy, University of Catania, 95125
Catania, Italy, and INFN Sezione di Catania, Via S. Sofia, 64, 95125 Catania,
Italy
E-mail<EMAIL_ADDRESS>L. Gallo is with naXys, Namur Institute for
Complex Systems, University of Namur, 5000 Namur, Belgium. V. Latora is with
School of Mathematical Sciences, Queen Mary University of London, London E1
4NS, UK. A. Pulvirenti is with Department of Clinical and Experimental
Medicine, University of Catania, 95125 Catania, Italy.Manuscript received ;
revised .

###### Abstract

Research on graph representation learning has received great attention in
recent years. However, most of the studies so far have focused on the
embedding of single-layer graphs. The few studies dealing with the problem of
representation learning of multilayer structures rely on the strong hypothesis
that the inter-layer links are known, and this limits the range of possible
applications. Here we propose MultiSAGE, a generalization of the GraphSAGE
algorithm that allows to embed multiplex networks. We show that MultiSAGE is
capable to reconstruct both the intra-layer and the inter-layer connectivity,
outperforming GraphSAGE, which has been designed for simple graphs. Next,
through a comprehensive experimental analysis, we shed light also on the
performance of the embedding, both in simple and in multiplex networks,
showing that either the density of the graph or the randomness of the links
strongly influences the quality of the embedding.

###### Index Terms:

graph embedding, multiplex networks, link prediction, graph representation
learning.

##  1 Introduction

Graphs (or networks) are mathematical data structure to represent real-world
complex systems. In the most general view, a graph consists of a entities or
objects (i.e., nodes), together with a set of relations (i.e., edges) between
pairs of such entities. Examples of graphs include: social networks [1] in
which entities are people and links represent friendship; co-authorship and
citation networks [2]; biological networks [3] where nodes are for example
proteins and relations between nodes may represent functional or physical
interactions; knowledge graphs [4] (also known as semantic networks) in which
nodes are real-world entities, such as objects, events, situations and edges
are relationship between them. In many contexts, simple graphs, where there is
at most one edge between each pair of nodes are enough to model the
application. However, graphs having different types of relations allow to
model, in a more comprehensive way, the complex system under study. Such kind
of graphs are called multi-relational which are commonly divided in two
important sub-groups known as heterogeneous and multiplex graphs. In
heterogeneous graphs, nodes have types, and therefore, we can partition the
set of nodes into disjoint sets. Whereas, multiplex graphs can be decomposed
in a set of $k$ layers. Every node belongs to every layer (each layer allows
to represents a specific kind of relation), along with intra-layer edges type
for each layer. Furthermore, inter-layer edges types can exist, and these
connect the same node across different layers.

Due the ubiquity of networks in the real world, graph analysis has become
mandatory in several domains [5]. In particular, the field of graph
representation has received an impressive research interest the past few years
[6, 7, 8]. Network representation learning or low dimensional network
embedding, consist of algorithmic methodologies, which allow to project the
nodes of a network into a multidimensional space preserving the structure of
the network and its intrinsic properties. The usage of dimensionality
reduction techniques to encode, into vectors, the high-dimensional information
of nodes’ graph neighborhood allows then to apply traditional Machine Learning
methodologies to networks. Indeed, such node embeddings can then be used into
downstream learning tasks and analysis such as: node classification [9], link
prediction [10], and community detection [11].

The performance of machine learning methods crucially depend on the quality of
the vector representations. Therefore, there is a wealth of research proposing
a wide range of vector-embedding methods for various applications. Seminal
works in this area include LINE [12], DeepWalk [13] and node2vec [14] which
are based on taking short random walks in a graph and interpreting the
sequence of nodes seen on such random walks as if they were words appearing
together in a sentence. However, from a deep learning perspective, such
embedding methods are all shallow, indeed they directly optimise the output
vectors without hidden layers. Although, shallow approach can be generalized
to multi-relational graphs it presents several limitations. Shallow embedding
methods are transductive. Indeed, these methods are only able to generate
embeddings for nodes that were present during the training phase.

To go beyond such limitations, shallow encoders can be replaced with more
sophisticated encoders that take into account the structure and attributes of
the graph. Among the most popular encoders we have graph neural networks
(GNNs). The key feature of a GNN is that it uses a kind of neural message
passing, which essentially is a generalization of the Weisferler-Leman test
[15, 16]. At each iteration, every node aggregates information from its local
neighborhood. As these iterations go on, each node embedding contains more
information obtained from remote nodes of the graph. In the last few years,
research in this area has been proposed in this context [8, 7, 17, 18, 19].
One of the most prominent example of an inductive node-embedding tool based on
GNNs is GraphSage [20].

More recently, research models for multi-layer networks embedding have raised.
In [21] authors propose an embedding approach for multigraphs, in [22] a
generalization of deep-walk and node2vec for multiplex graphs were introduced.
[22]. Other relevant approaches include [23, 24, 25, 26]. However, in all of
these approach no distinction between inter- and intra-layer connections is
taken into account.

In this paper, we introduce MultiSAGE, a generalization of the GraphSAGE
algorithm for embedding multiplex networks. Our embedding approach focuses
only on unlabeled graphs but can be easily generalized to labeled graphs.
Through a comprehensive experimental analysis based on three benchmark
datasets, we shed light also on the limit of the vector embedding in producing
reliable vector embedding, both for simple graphs and multiplex. Indeed, our
analysis shows that either density of the graphs or the randomness of the
links actually limit the quality of the embedding.

##  2 The MultiSAGE algorithm

###  2.1 Multiplex networks

A multiplex network is a generalization of a network that allows to naturally
represent systems of connected units when multiple types of interactions among
them exist [27, 28]. Multiplex networks can be see as a particular type of a
multilayer networks [29, 30]. We will first define them describing their graph
and matrix representation, and presenting the crucial concept of _intra-layer_
and _inter-layer_ links, as well as the one of _supra-adjacency matrix_ [31].

Figure 1: A multiplex network with two layers (left) and its supra-adjacency
matrix $\tilde{\rm A}$ (right). Intra-layer links are colored in white, and
correspond respectively to the purple and blue diagonal blocks of $\tilde{\rm
A}$. Inter-layer links are displayed as black dashed lines, and correspond to
white off-diagonal blocks of $\tilde{\rm A}$.

Let us consider a set $\mathcal{V}$ of $N$ nodes interacting through $L$
different types of relations, represented as $L$ different layers. Let us
assume that $N_{\alpha}$ nodes lie on each layer $\alpha$, with
$\alpha=1,\dots,L$ so that $N_{1}+N_{2}+\dots+N_{L}=N$. Each layer of the
multiplex consists in a network
$G_{\alpha}=(\mathcal{V}_{\alpha},\mathcal{E}_{\alpha})$, where
$\mathcal{V}_{\alpha}\subseteq\mathcal{V}$ is the set of $N_{\alpha}$ nodes in
the layer, while $\mathcal{E}_{\alpha}$ is a set of edges representing the
relations of type $\alpha$. Hereby, we will refer to the edges in
$\mathcal{E}_{\mathrm{intra}}=\bigcup_{\alpha=1}^{L}\mathcal{E}_{\alpha}$ as
_intra-layer links_. The connectivity of each layer $G_{\alpha}$ can be
encoded as an adjacency matrix $A^{\alpha}\in\mathbb{R}^{N_{\alpha}\times
N_{\alpha}}$, whose element $a_{ij}^{\alpha}$ is equal to one, if
$(i,j)\in\mathcal{E}_{\alpha}$, i.e., nodes $i$ and $j$ interacts through the
relation $\alpha$, while it is equal to zero otherwise.

In addition to the intra-layer connectivity, we assume to connect some of the
nodes lying on different layers, so that given $\alpha,\beta$, with
$\alpha\neq\beta$, a node lying on layer $\alpha$ can be linked with at most
one node on layer $\beta$. This constraint makes the multiplex a suitable
representation for those systems where the same set of individuals are
connected through different relations [30]. In what follows, we will call
these connections _inter-layer links_. As a further hypothesis, we assume that
if a node $i$ on layer $\alpha$ is connected to a node $j$ on layer $\beta$,
and if $j$ is connected to a node $k$ on layer $\gamma$, then nodes $i$ and
$k$ are also connected. Therefore, the graph
$G_{\mathrm{inter}}=(\mathcal{V},\mathcal{E}_{\mathrm{inter}})$, where
$\mathcal{E}_{\mathrm{inter}}$ is the set of inter-layer links, will be formed
by disconnected components that are either cliques or isolated nodes [31].
Such a graph can be as well characterized by an adjacency matrix
$C\in\mathbb{R}^{N\times N}$, whose element $c_{ij}$ is equal to one, if
$(i,j)\in\mathcal{E}_{\mathrm{inter}}$, whereas it is equal to zero otherwise.

Finally, we can define the _supra-adjacency matrix_ $\tilde{A}$, which encodes
both intra-layer and inter-layer connections. By labeling the nodes according
to the labels of the layer, i.e., indices from $1$ to $N_{1}$ denotes the
nodes in the first layer, from $N_{1}+1$ to $N_{1}+N_{2}$ the nodes in the
second layer, and so on, we can write the supra-adjacency matrix as

$\tilde{\rm A}=\bigoplus\limits_{\alpha}A^{\alpha}+C,$ (1)

where $\bigoplus$ denotes the direct sum. An example of a multiplex network
and its supra-adjacency matrix is shown in Fig. 1. Note that the diagonal
blocks correspond to the adjacency matrices of the graphs at each layer, thus
encoding the intra-layer connectivity, while the off diagonal blocks contain
the information on the inter-layer connections. It is worth mentioning that we
can interpret $\tilde{\rm A}$ as the adjacency matrix of a single-layer
multigraph $\mathcal{M}=(\mathcal{V},\mathcal{E})$, where
$\mathcal{E}=\mathcal{E}_{\rm intra}\cup\mathcal{E}_{\rm inter}$, composed of
$N$ nodes where there are two kinds of links, namely the intra-layer and the
inter-layer. We will call such a graph the _flattened multiplex network_. This
will come up particularly useful when comparing our algorithm to GraphSAGE.

Let us remark that our definition is more flexible compared to the one usually
given for multiplex networks. Indeed, it is common to assume that each layer
of the multiplex is composed by the same number of nodes, i.e.,
$N_{\alpha}=m,\,\forall\alpha$, and that for any $\alpha,\beta$, a node on
layer $\alpha$ is connected to _exactly_ one node on layer $\beta$ [30, 28].
Here, to extend the range of possible applications of our algorithm, we do not
consider such extra constraints. As an example, let us consider the case of
different online social networks (OSNs), which can be represented by a single
entity, namely a multiplex network where each layer encodes the connections in
one of the OSNs. If a user can have only one account for each OSN, we
constraint ourselves to the case of a multiplex. In such an example, assuming
that each layer is composed by the same number of nodes and that all the
possible inter-layer links exist is too restrictive. First, the users might
not have an account on every OSN. Second, these accounts might not be
connected one another, i.e., it is not know _a priori_ that two accounts on
different OSN are owned by the same user. Hence, relaxing the constraint of
having all the possible inter-layer connections opens to relevant applications
like, for instance, the one of de-anonymization [32], which can be seen as an
inter-layer link prediction.

###  2.2 The algorithm

The embedding algorithm MultiSAGE represents the natural generalization of the
GraphSAGE algorithm [20] to multiplex networks. In order to provide a vector
representation $\mathbf{z}_{n}$ for a graph node $n$, GraphSAGE relies on the
idea of training a set of $K$ _aggregator functions_ $f_{k}$, with
$k\in\\{1,\ldots,K\\}$, that learn to aggregate information from the node
$K$-th neighborhood. In other words, given a node $n$, its embedding vector
depends, according to a first aggregator function, on the features of its
first-neighbors, which in turns are evaluated, through a second aggregator
function, from the characteristics of their first-neighborhoods, i.e. the
second-neighborhood of $n$, and so on, up to a certain depth $K$. Therefore,
the vector $\mathbf{z}_{n}$ can be determined once all the aggregator
functions are trained.

In the original version of the GraphSAGE algorithm, which deals with the
embedding of (single-layer) graphs, when considering a specific node $n$, each
aggregator $f_{k}$ is a function of the features of the node itself and of the
ones of its first-neighborhood. Conversely, since for multiplex networks we
can distinguish, for each node, both an intra-layer and an inter-layer
neighborhood, in the MultiSAGE embedding algorithm the aggregator functions
will depend on the features of node $n$, and of its intra-neighbors, but also
on the features of its inter-neighbors. The MultiSAGE embedding generation is
formally described by Algorithm 1.

Input : Flattened multiplex network $\mathcal{M}=(\mathcal{V},\mathcal{E})$;
input feature vector $\mathbf{x}_{n}$, $\forall
n\in\\{1,\dots,|\mathcal{V}|\\}$; depth $K$; differentiable aggregator
functions $f_{k}$, $\forall k\in\\{1,\ldots,K\\}$; intra-layer and inter-layer
neighborhood functions
${N}_{H},{N}_{V}:\mathcal{V}\rightarrow\mathcal{P}(\mathcal{V})$

Output : Vector representation $\mathbf{z}_{n}$, $\forall
n\in\\{1,\dots,|\mathcal{V}|\\}$

$\mathbf{h}_{n}^{0}\leftarrow\mathbf{x}_{n}$, $\forall
n\in\\{1,\dots,|\mathcal{V}|\\}$;

for  _$k=1,\dots,K$_ do

for  _$n=1,\dots,|\mathcal{V}|$_ do

$\mathbf{h}_{n}^{k}\leftarrow f_{k}(\\{\mathbf{h}_{m}^{k-1},\forall
m\in\mathcal{N}_{H}(n)\\},\\{\mathbf{h}_{m}^{k-1},\forall
m\in\mathcal{N}_{V}(n)\\},\mathbf{h}_{n}^{k-1})$;

$\mathbf{z}_{n}\leftarrow\mathbf{h}^{K}_{n}$, $\forall
n\in\\{1,\dots,|\mathcal{V}|\\}$;

Algorithm 1 MultiSAGE embedding generation algorithm

Again, the core idea behind the embedding algorithm is to generate, for each
node of the multiplex network, a vector representation by aggregating the
features of the node $K$-th neighborhood, through a series of $K$ iterations.
This time, however, at each iteration $k\in\\{1,\ldots,K\\}$, each node $n$ is
represented by a feature vector $\mathbf{h}_{n}^{k}\in\mathbb{R}^{d_{k}}$,
which is evaluated by aggregating, through the function $f_{k}$ the
representation vectors of the intra-neighbors of node $n$,
$\\{\mathbf{h}_{m}^{k-1},\forall m\in\mathcal{N}_{H}(n)\\}$, of the inter-
neighbors of $n$, $\\{\mathbf{h}_{m}^{k-1},\forall m\in\mathcal{N}_{V}(n)\\}$,
and of the node $n$ itself, $\mathbf{h}_{n}^{k-1}$, at the previous step, i.e.
$k-1$. Note that the subscripts $H$ and $V$ stand for _horizontal_ and
_vertical_ respectively. The algorithm is initialized by defining the
representation vector $\mathbf{h}_{n}^{0}$ at step $k=0$ as the input node
features $\mathbf{x}_{n}$. Finally, the embedding vector $\mathbf{z}_{n}$ of
node $n$ is given by the representation vector at step $K$, i.e.
$\mathbf{h}_{n}^{K}$. Note that, in general, the dimension $d_{k}$ of the
representation vectors can be different from one step to another. Lastly, we
remark that, differently from GraphSAGE, in Algorithm 1 we do not consider a
concatenation step, so that the vector $\mathbf{h}_{n}^{k-1}$ contributes to
the aggregation step through the function $f_{k}$.

The aggregation of the representation vectors can be performed employing a
variety of aggregator functions $f_{k}$. In this paper, we focus on the
simplest version of GraphSAGE, namely the one using a weighted mean to define
the aggregator functions. In this case, we can substitute the line of pseudo-
code relative to $f_{k}$ in Algorithm 1 with

$\displaystyle\mathbf{h}_{n}^{k}\leftarrow\theta\Bigg{(}$
$\displaystyle\mathcal{W}_{H}^{k}\sum\limits_{m\in\mathcal{N}_{H}(n)}\frac{\mathbf{h}_{m}^{k-1}}{|\mathcal{N}_{H}(n)|}$
(2)
$\displaystyle+\mathcal{W}_{V}^{k}\sum\limits_{m\in\mathcal{N}_{V}(n)}\frac{\mathbf{h}_{m}^{k-1}}{|\mathcal{N}_{V}(n)|}+\mathcal{S}^{k}\mathbf{h}_{n}^{k-1}\Bigg{)},$

where
$\mathcal{W}_{H}^{k},\mathcal{W}_{V}^{k},\mathcal{S}^{k}\in\mathbb{R}^{d_{k},d_{k-1}}$
are matrices weighting the contribution of the intra-neighborhood, of the
inter-neighborhood, and of the focal node, respectively, while $\theta$ is a
nonlinear activation function. The representation vector $\mathbf{h}_{n}^{k}$
of node $n$ at step $k$ is determined by three factors, namely the mean of the
representation vectors at step $k-1$ of its intra-neighbors, the mean of the
representation vectors at step $k-1$ of its inter-neighbors, and the
representation vector at step $k-1$ of the node itself, all of which are
multiplied by the respective weight matrices. Given this choice for the
aggregator functions, once the algorithm is provided with the activation
function $\sigma$, the only unknown variables that have to be determined
through the training process are the weight matrices $\mathcal{W}_{H}^{k}$,
$\mathcal{W}_{V}^{k}$ and $\mathcal{S}^{k}$.

Consistently with the GraphSAGE algorithm, to learn the weight matrices
defining the MultiSAGE aggregator functions in a unsupervised setting, we
introduce a loss function based on the supra-adjacency matrix of the multiplex
network. In particular, the loss function $J_{\mathcal{M}}$ is defined so to
force neighboring nodes (both intra- and inter-layer) to have similar
embedding vectors, while constraining nodes that are not connected, i.e. the
negative links, to have dissimilar representations. However, since the number
of negative links can be high, the computation of the loss function for large
networks can be computationally expensive. To reduce the computational cost of
the learning process, it is common to rely on _negative sampling_ [33, 34],
namely to evaluate the loss function only on a random subset of all the
possible negative links. Formally, given the embedding vectors
$\mathbf{z}_{n}$, $\forall n\in V$, we define

$\displaystyle J_{\mathcal{M}}=-\sum\limits_{(n,m)\in\mathcal{E}}\Big{\\{}$
$\displaystyle\mathrm{log}(\sigma(\mathbf{z}_{n}^{\top}\mathbf{z}_{m}))$ (3)
$\displaystyle+\sum\limits_{\overline{m}\sim
P(n)}\mathrm{log}(\sigma(-\mathbf{z}_{n}^{\top}\mathbf{z}_{\overline{m}}))\Big{\\}},$

where $P(n)$ is the negative sampling probability distribution, and
$\sigma(x)$ is the sigmoid function $\sigma(x)=1/(1+e^{-x})$. Note that the
sum in the curl brackets has $Q$ terms, corresponding to the number of
negative samples.

##  3 Data and evaluation

###  3.1 Multiplex network data

Network | Nodes | Layers | Intra-layer links | Inter-layer links
---|---|---|---|---
arXiv | 19310 | 13 | 48657 | 20738
Drosophila | 11867 | 7 | 40228 | 5173
ff-tw-yt | 11827 | 3 | 74815 | 6028
TABLE I: Basic features of the multiplex networks emplyed to test the performance of the MultiSAGE algorithm. Algorithm | ff-tw-yt | Drosophila | arXiv
---|---|---|---
| intra | inter | intra | inter | intra | inter
GraphSAGE | $0.47\pm 0.02$ | $0.56\pm 0.02$ | $0.54\pm 0.01$ | $0.63\pm 0.02$ | $0.72\pm 0.01$ | $0.70\pm 0.01$
MultiSAGE | $0.48\pm 0.02$ | $0.62\pm 0.02$ | $0.51\pm 0.02$ | $0.77\pm 0.02$ | $0.70\pm 0.02$ | $0.83\pm 0.01$
TABLE II: Intra-layer and inter-layer link prediction results for both
MultiSAGE and GraphSAGE on the three datasets. The table reports the average
AUC, along with the standard deviation.

To test the performance of the MultiSAGE algorithm in predicting both intra-
layer and inter-layer connections, we have analyzed different types of real-
world multiplex networks, such as collaboration, biological, and online social
networks, as well as synthetic datasets. For each empirical dataset, we
consider only the largest connected component, and we ignore, if these are
given, the directions and the weights of the links, i.e., we assume all the
networks to be undirected and unweighted.

arXiv [35]. The arXiv multiplex network is a collaboration network where each
layer represents a different category, i.e. research topic, of the pre-print
archive. To generate the network, only the papers including the word
“networks” in the title or in the abstract published before May 2014 were
selected. The network largest connected component consists in this case of
$19310$ nodes over $13$ layers, connected through $48657$ intra-layer
connections, and $20738$ inter-layer ones.

Drosophila [36, 37]. This is the protein-genetic interaction multiplex network
of the common fruit fly _Drosophila melanogaster_ , where layers correspond to
interactions of different nature. The dataset is gathered from the Biological
General Repository for Interaction Datasets (BioGRID), updated to January
2014. The largest connected component consists of $118670$ nodes over $7$
layers, with $40228$ intra-layer links, and $5173$ inter-layer ones.

ff-tw-yt [38]. This is a multiplex network obtained from Friendfeed (ff), a
social media aggregator, which allows the users to register their accounts on
other online social networks (OSNs). The retrieved multiplex network consists
of users who registered a single Twitter (tw) account and a single YouTube
(yt) account on Friendfeed, and whose Twitter and YouTube accounts are
associated to one Friendfeed account. The largest connected component consists
of $11827$ nodes over $3$ layers, with $74815$ intra-layer connections, and
$6028$ inter-layer ones.

The main characteristics of the datasets considered in this study are reported
in Table I. It is worth remarking that, for all the multiplex networks
described above, no external feature vectors is provided for the nodes.
Therefore, for each node $n$ we will consider as the input feature vector
$\mathbf{x}_{n}$ a one-hot encoder vector [39], i.e., $x_{n,i}=\delta_{ni}$,
where $\delta$ is the Kronecker delta.

###  3.2 Experimental setup and evaluation

The main task we want to test MultiSAGE on is that of predicting both the
intra-layer and the inter-layer links of a multiplex network. To assess the
performance of our algorithm, we consider the following experimental setup. We
first select a random sample of $20\%$ of the network nodes, which we refer to
as _marked nodes_. We then define the _test_ and the _training_ sets. Each one
of these sets consists of positive examples, i.e., the links of the network,
and negative examples, i.e., couples of unconnected nodes. As positive
examples in the test set, we consider a subset of $20\%$ of the intra-layer
links and all the inter-layer links of the marked nodes. Positive examples of
the training set consist of all the remaining intra- and inter-layer links of
the entire network. As concerns the negative examples, we include in the test
set $20\%$ of all the possible negative intra-layer links among the marked
nodes, and all the possible inter-layer links among them. The remaining
uncoupled pair of nodes in the entire network form the negative examples of
the training set.

Since the algorithm is trained so that adjacent nodes have a similar vector
representation, while nonadjacent nodes have a dissimilar one, we would expect
MultiSAGE to discriminate between positive and negative links in terms of the
similarity of their vertices. Indeed, when it performs well, the similarity
between the vertices of a positive link should be higher than the similarity
between the vertices of a negative link. Instead of setting an arbitrary
discrimination threshold on the value of the vertex similarity, so that all
links whose vertex similarity is above threshold are considered true links of
the networks and vice versa, to estimate the algorithm performance we rely on
the Receiving Operating Characteristic (ROC) curves. To construct them, for
both intra-layer and inter-layer links, we evaluate the frequency distribution
of the vertices similarity for positive and negative links respectively, and
estimate how the true positive rate, namely the fraction of positive links
correctly predicted as true links, and the false positive rate, i.e., the
fraction of negative links incorrectly predicted, vary as a function of the
discrimination threshold. Therefore, as a scalar measure of the algorithm
performance, we consider the area under the ROC curve (AUC), which corresponds
to the probability that a randomly chosen positive link have a vertex
similarity higher than one of a randomly chosen negative link. Therefore, when
the algorithm is able to distinguish between positive and negative links, the
value of the AUC tends to $1$, while in the opposite case it goes to $0.5$,
i.e., random classifier.

##  4 Results

Figure 2: Variation of the AUC for inter-layer (blue lines) and the intra-
layer (orange lines) link prediction as a function of the number of layers,
for MultiSAGE (solid lines) and GraphSAGE (dashed lines), on A) Drosophila and
B) arXiv multiplex networks.

In this section we present a series of results obtained for GraphSAGE and our
generalization to multiplex network. First, we compare the performance of the
two algorithms in predicting the intra-layer and inter-layer connectivity of
the multiplex networks described above. Then, we analyze the dependence of
both MultiSAGE and GraphSAGE on the number of layers of a network, assessing
how the performances vary as we gradually change the number of layers to
embed. Finally, we will further investigate such a dependence, showing how the
prediction accuracy of GraphSAGE is related to the link density and to the
randomness of the network.

###  4.1 Embedding multiplex networks

Our first analysis consists in evaluating the performance of MultiSAGE in
predicting intra-layer and inter-layer links when embedding a multiplex
network. To do so, for each of the three dataset illustrated, we consider the
experimental setup described in the previous section, training and testing the
algorithm on $20$ different samplings of the marked nodes and of the train and
test sets. As a measure of the algorithm performance, we consider the AUC
averaged over the different realizations of the embedding procedure. We use
the standard deviation as a measure of the error. As a benchmark, we compare
the results obtained by MultiSAGE with the one of GraphSAGE, where we have
trained the algorithm with no distinction between intra-layer and inter-layer
links.

Table II illustrates the results obtained by the two algorithms, on the three
datasets, for both intra-layer and inter-layer link prediction. First, we note
that, for both GraphSAGE and MultiSAGE, the value of the average AUC tends to
be generally higher for the inter-layer link prediction than for the intra-
layer link prediction. On all the multiplex networks considered, MultiSAGE
provides significantly better predictions of the inter-layer connectivity
compared to GraphSAGE, while the two algorithms have the same performance,
within the error bars, when reconstructing the intra-layer connections.
Furthermore, we remark that the performance of both algorithms seem to
positively depend on the number of layers of the network. Indeed, when
predicting the intra-layer links, both MultiSAGE and GraphSAGE obtain results
that are comparable to those of a random classifier, i.e., $\mathrm{AUC}=0.5$,
on the ff-tw-yt network, which has three layers, and on the Drosophila
network, composed by seven layers. Conversely, on the arXiv network, which is
formed by thirteen layers, the value of the AUC goes up to abouth $0.70$ for
both algorithms. As regards the inter-layer link prediction, the dependency on
the number of layers seems to be more pronounced, with the value of AUC
ranging from $0.62$ and $0.56$ for the online social network, to $0.83$ and
$0.70$ for the collaboration network, for MultiSAGE and GraphSAGE
respectively.

Overall, for both intra-layer and inter-layer link prediction, the number of
layers of the network seems to have a positive impact on the performance of
the algorithms, so that the more the layers the higher the value of the AUC.
In the next section, we will provide an in-depth analysis of the dependence of
the algorithm performance on the number of layers of the network, introducing
an explanatory measure for the accuracy of the link prediction.

Figure 3: Variation of the AUC for inter-layer link prediction (green line)
and of the parameter $\delta$ (orange line) as a function of the number of
layers, on A) Drosophila and B) arXiv multiplex networks.

###  4.2 Varying the number of layers

As we have shown above, the accuracy of both MultiSAGE and GraphSAGE in intra-
layer and inter-layer link prediction seems to depend on the number of layers
of the network. To further analyze this dependence, here we carry on the
following study. For the Drosophila and the arXiv datasets, we first sort the
$L$ layers according to their number of nodes, so that
$N_{1}>N_{2}>\dots>N_{L}$. Then, we construct a set of multiplex sub-networks,
the first being formed by layers $\\{1,2\\}$, i.e., the two layers with the
largest number of nodes, the second formed by layers $\\{1,2,3\\}$, and so on.
Finally, the last network of the set consists in the original multiplex
network, formed by all the $L$ layers. Therefore, for each network in the set,
we consider the experimental setup previously described, again training and
testing the algorithm over $20$ different sampling of the marked nodes. To
measure the accuracy of both MultiSAGE and GraphSAGE, we adopt once again the
AUC averaged over the different realizations of the embedding procedure.

Fig. 2 shows the results obtained for the Drosophila (panel A) and the arXiv
(panel B) multiplex networks. First, one can observe that, for both datasets,
the accuracy of MultiSAGE in the prediction of the inter-layer links is
generally higher compared to the one of GraphSAGE, for every sub-network
considered. The only exception consists of the embedding of the arXiv sub-
network formed by two layers, for which we find $\mathrm{AUC}_{\rm MS}=0.51\pm
0.03$ and $\mathrm{AUC}_{\rm GS}=0.59\pm 0.03$. As regards to the prediction
of the intra-layer connections, GraphSAGE performs better than MultiSAGE,
despite the difference between the two algorithms is not as marked as it is
for the inter-layer link prediction. According to these results, our algorithm
seems to display a sort of compensation effect, so that, to enhance its
performance in the reconstruction of inter-layer connections, it loses in
accuracy when predicting the intra-layers links. We also note that, for both
datasets and for both the algorithms, the accuracy of the intra-layer link
prediction does not vary much with the number of layers considered, whereas
the AUC for the inter-layer link prediction clearly depends on it. Indeed, one
can see that the latter increases as we add layers, up to a point where the
AUC curves seem to saturate to a certain value, as it is particularly evident
for the case of the Drosophila network.

We now want to further investigate the trend of the AUC curves for the inter-
layer link prediction, aiming at explaining the cause of the accuracy
dependence on the number of layers. To do so, let us define the following
parameter:

$\delta(L)=1-\frac{m_{L}}{\sum\limits_{l=2}^{L}(l-1)N_{l}}\in[0,1],$ (4)

where $m_{L}$ is the number of inter-layer links when $L$ layers are
considered, and $N_{l}$ are the number of nodes at each layer $l$.
Intuitively, this parameter corresponds to the density of inter-layer links
that are not present in the network. To clarify this, let us consider $L=2$,
i.e., a two-layer network. In this case, the parameter $\delta$ is simply
given by

$\delta(2)=1-\frac{m_{2}}{N_{2}},$ (5)

where $m_{2}$ is the number of inter-layer nodes between the two layers and
$N_{2}$ is the number of nodes in the smallest layer, i.e., $N_{2}\leq N_{1}$.
When all the nodes in layer $2$ are connected to a node on layer $1$ we have
$m_{2}=N_{2}$, thus $\delta(2)=0$. However, if there are nodes on layer $2$
that do not have an inter-layer neighbor on layer $1$, one has $m_{2}<N_{2}$,
which leads to $\delta(2)>0$, up to the case where no inter-layer links exist,
for which $\delta(2)=1$. Note that the term $(l-1)$ within the summation comes
from the fact that, when we add the $l$-th layer to the network, we could
connect each of the $N_{l}$ nodes to $(l-1)$ nodes, one for each of the
$(l-1)$ layers already present.

Fig. 3 shows the comparison between the AUC curves for the inter-layer link
prediction and the parameter $\delta(L)$ defined above, for the Drosophila
(panel A) and the arXiv (panel B) multiplex networks. As one can note, for
both datasets $\delta(L)$ well correlates with the AUC curve. Such a result
suggests that MultiSAGE, at least when performing a featureless network
embedding, better predicts the inter-layer connectivity when the density of
inter-layer links is low, i.e., when $\delta$ is closer to one. To have an
intuition of the role of the link density in the algorithm accuracy, let us
imagine to perform the embedding of a (almost) complete graph using GraphSAGE.
As (almost) all the nodes in the network are adjacent, at each step of the
embedding procedure they will be characterized by the same vector
representation. As a consequence, the accuracy of the link prediction will be
low, since all the connections in the test set, both positive and negative,
will be predicted as positive. In the next section we will further investigate
such a result, showing that the GraphSAGE (and consequently the MultiSAGE)
accuracy is affected not only by the network sparsity, but also by its
randomness, so that the more the graph is random the worse the performance of
the algorithm is.

###  4.3 The impact of the network randomness

As we have discussed in the previous section, the accuracy of the inter-layer
link prediction in the MultiSAGE algorithm seems to depend on the density of
connections. To better understand such a result, here we come back to
GraphSAGE, which shares the same embedding strategy as MultiSAGE, while being
a simpler algorithm to examine. We hereby perform two different numerical
analysis. Initially, we study how the accuracy of the link prediction changes
as we randomly add links to a network, i.e., as we make the network denser.
Then, we investigate the impact on GraphSAGE performance of randomly rewiring
the network links, namely, we explore how making the network more random
affects the link prediction accuracy.

We begin by further analyzing the role of the link density in the prediction
accuracy. To carry out the study, we generate a set of networks constructed by
starting from the largest layer of the arXiv dataset and adding a fraction of
links $\rho$ between nonadjacent nodes. As the additional links are
homogeneously distributed, we can think the newly constructed graphs as the
union111The union of two graphs $G_{1}=(V_{1},E_{1})$ and
$G_{2}=(V_{2},E_{2})$ is here defined as the graph $G=(V,E)=(V_{1}\cup
V_{2},E_{1}\cup E_{2})$. Note that, as in the case here considered we have
$V_{1}=V_{2}$, it follows that $V=V_{1}=V_{2}$. between the original graph and
an Erdös-Rényi (ER) random graph [40], with $n_{1}$ nodes and connection
probability $\rho$. Considering also the starting network ($\rho=0$), we
account for a total of eleven networks, that we embed following the usual
experimental setup, training and testing the algorithm over $20$ different
sampling of the marked nodes. Again, to measure the prediction accuracy, we
consider the AUC averaged over the different runs of the embedding procedure.

Fig. 4 displays how the average AUC varies as a function of the fraction of
additional links $\rho$. In agreement with the results of the previous
section, when the network is sparse, i.e., for $\rho<10^{-4}$, GraphSAGE is
able to distinguish between positive and negative links, as shown by the high
value of the AUC, which is close to $0.75$. However, when the density of links
increases, the accuracy of the algorithm starts to decrease, down to
$\mathrm{AUC}=0.5$ ($\rho\approx 10^{-2}$), where GraphSAGE performs as a
random classifier. We can therefore conclude that, when embedding a graph with
featureless nodes, GraphSAGE is able to accurately reconstruct the network
connectivity only when the network itself is sparse, whereas it fails to do so
for graphs that are dense.

Figure 4: Variation of GraphSAGE link prediction accuracy as a function of the
fraction of links $\rho$ added to the original network, consisting in the
larger layer of the arXiv multiplex network. Note that the plot scale is
linear-log.

We now want to analyze how the network randomness influences the accuracy of
the algorithm predictions. To do so, we construct a collection of networks
using the Watts and Strogatz (WS) model [41]. In particular, starting from a
ring lattice of $N=10^{4}$ nodes, where each nodes is connected to $K=4$
neighbors, two on each side, we generate the networks by rewiring the links of
the lattice with a certain probability $\phi$. One crucial feature of the WS
model is that we can tune the network from a regular structure ($\phi=0$) to a
disordered one ($\phi=1$), while keeping the link density constant, i.e.,
$D=K/(N-1)$. Therefore, the WS model allows to study how the randomness of the
network connectivity affects the accuracy of the link prediction, leaving out
the contribution of edge density. Including also the regular lattice
($\phi=0$), we consider eleven networks in total. Again, we embed each network
following the experimental setup described above, with $20$ different train-
test splits. As an accuracy measure, we once again evaluate the AUC averaged
over the different realizations of the embedding procedure.

Fig. 5 shows the variation of the average AUC as a function of the rewiring
probability $\phi$. In particular, we observe that the accuracy of GraphSAGE
in the link prediction is negatively affected by the randomness of the
network. Indeed, for smaller rewiring probabilities, i.e., $\phi<10^{-2}$, the
AUC is over $0.85$, meaning that the algorithm is performing well in the
positive and negative links discrimination. However, for higher values of
$\phi$, the accuracy of the models starts to decrease. In particular, for
$\phi=1$ GraphSAGE almost behaves as a random classifier, as
$\mathrm{AUC}=0.55$. Summing up, this analysis shows that randomness can
negatively affect the performance of the algorithm. In particular, the more a
network is similar to a homogeneous random graph the worse will be the
prediction accuracy. On the other hand, the results obtained suggest that
networks with a regular structure or with an high clustering coefficient, such
as the one generated by the WS model for small value of the rewiring
probability, allows for better performances in the link prediction task.
Finally, it is worth mentioning once again that such an analysis is performed
in a condition where no node is provided with an external feature vector. We
leave such a study for future work.

Figure 5: Variation of GraphSAGE link prediction accuracy as a function of the
rewiring probability $\phi$ in the Watts and Strogatz model. Note that the
plot scale is linear-log.

##  5 Conclusion

In this paper we have introduced an algorithm for the embedding of multiplex
network, which distinguishes between intra- and inter-layer edges and produces
reliable results, especially for the prediction of inter-layer link. We have
tested the algorithm performance on different types of empirical multiplex
networks. The results of our analysis clearly show that taking into account
the multi-layer nature of the network positively influences the quality of the
embedding. On the other hand, we also found that, either increasing the
density of links, or shuffling the network edges, negatively influences the
quality of the embedding.

## Acknowledgments

L.G. would like to thank C. Monti for the useful discussion and for his
precious suggestions on how to perform the numerical analysis.

## References

  * [1] J. Scott, “Social network analysis,” _Sociology_ , vol. 22, no. 1, pp. 109–127, 1988.
  * [2] X. Liu, J. Bollen, M. L. Nelson, and H. Van de Sompel, “Co-authorship networks in the digital library research community,” _Information processing & management_, vol. 41, no. 6, pp. 1462–1480, 2005.
  * [3] A.-L. Barabási, N. Gulbahce, and J. Loscalzo, “Network medicine: a network-based approach to human disease,” _Nature reviews genetics_ , vol. 12, no. 1, pp. 56–68, 2011.
  * [4] S. Ji, S. Pan, E. Cambria, P. Marttinen, and S. Y. Philip, “A survey on knowledge graphs: Representation, acquisition, and applications,” _IEEE Transactions on Neural Networks and Learning Systems_ , 2021.
  * [5] J. Zhou, G. Cui, S. Hu, Z. Zhang, C. Yang, Z. Liu, L. Wang, C. Li, and M. Sun, “Graph neural networks: A review of methods and applications,” _AI Open_ , vol. 1, pp. 57–81, 2020.
  * [6] D. Bacciu, F. Errica, A. Micheli, and M. Podda, “A gentle introduction to deep learning for graphs,” _Neural Networks_ , vol. 129, pp. 203–221, 2020.
  * [7] F. Chen, Y.-C. Wang, B. Wang, and C.-C. J. Kuo, “Graph representation learning: a survey,” _APSIPA Transactions on Signal and Information Processing_ , vol. 9, 2020.
  * [8] M. Grohe, “word2vec, node2vec, graph2vec, x2vec: Towards a theory of vector embeddings of structured data,” in _Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems_ , 2020, pp. 1–16.
  * [9] Y. Rong, W. Huang, T. Xu, and J. Huang, “Dropedge: Towards deep graph convolutional networks on node classification,” _arXiv preprint arXiv:1907.10903_ , 2019.
  * [10] L. Lü and T. Zhou, “Link prediction in complex networks: A survey,” _Physica A: statistical mechanics and its applications_ , vol. 390, no. 6, pp. 1150–1170, 2011.
  * [11] S. Fortunato, “Community detection in graphs,” _Physics reports_ , vol. 486, no. 3-5, pp. 75–174, 2010.
  * [12] J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei, “Line: Large-scale information network embedding,” in _Proceedings of the 24th international conference on world wide web_ , 2015, pp. 1067–1077.
  * [13] B. Perozzi, R. Al-Rfou, and S. Skiena, “Deepwalk: Online learning of social representations,” in _Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining_ , 2014, pp. 701–710.
  * [14] A. Grover and J. Leskovec, “node2vec: Scalable feature learning for networks,” in _Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining_ , 2016, pp. 855–864.
  * [15] N. Shervashidze, P. Schweitzer, E. J. Van Leeuwen, K. Mehlhorn, and K. M. Borgwardt, “Weisfeiler-lehman graph kernels.” _Journal of Machine Learning Research_ , vol. 12, no. 9, 2011.
  * [16] A. Leman and B. Weisfeiler, “A reduction of a graph to a canonical form and an algebra arising during this reduction,” _Nauchno-Technicheskaya Informatsiya_ , vol. 2, no. 9, pp. 12–16, 1968.
  * [17] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio, “Graph attention networks,” _arXiv preprint arXiv:1710.10903_ , 2017.
  * [18] M. Liu, H. Gao, and S. Ji, “Towards deeper graph neural networks,” in _Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining_, 2020, pp. 338–348.
  * [19] H. Gao and S. Ji, “Graph u-nets,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , pp. 1–1, 2021.
  * [20] W. L. Hamilton, R. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” _arXiv preprint arXiv:1706.02216_ , 2017.
  * [21] Y. Cen, X. Zou, J. Zhang, H. Yang, J. Zhou, and J. Tang, “Representation learning for attributed multiplex heterogeneous network,” in _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2019, pp. 1358–1368.
  * [22] M. Gong, W. Liu, Y. Xie, Z. Tang, and M. Xu, “Heuristic 3d interactive walk for multilayer network embedding,” _IEEE Transactions on Knowledge and Data Engineering_ , 2020.
  * [23] W. Liu, P.-Y. Chen, S. Yeung, T. Suzumura, and L. Chen, “Principled multilayer network embedding,” in _2017 IEEE International Conference on Data Mining Workshops (ICDMW)_. IEEE, 2017, pp. 134–141.
  * [24] M. Qu, J. Tang, J. Shang, X. Ren, M. Zhang, and J. Han, “An attention-based collaboration framework for multi-view network representation learning,” in _Proceedings of the 2017 ACM on Conference on Information and Knowledge Management_ , 2017, pp. 1767–1776.
  * [25] H. Zhang, L. Qiu, L. Yi, and Y. Song, “Scalable multiplex network embedding.” in _IJCAI_ , vol. 18, 2018, pp. 3082–3088.
  * [26] Y. Shi, F. Han, X. He, X. He, C. Yang, J. Luo, and J. Han, “mvn2vec: Preservation and collaboration in multi-view network embedding,” _arXiv preprint arXiv:1801.06597_ , 2018.
  * [27] M. De Domenico, A. Solé-Ribalta, E. Cozzo, M. Kivelä, Y. Moreno, M. A. Porter, S. Gómez, and A. Arenas, “Mathematical formulation of multilayer networks,” _Physical Review X_ , vol. 3, no. 4, p. 041022, 2013.
  * [28] F. Battiston, V. Nicosia, and V. Latora, “Structural measures for multiplex networks,” _Physical Review E_ , vol. 89, no. 3, p. 032804, 2014.
  * [29] M. Kivelä, A. Arenas, M. Barthelemy, J. P. Gleeson, Y. Moreno, and M. A. Porter, “Multilayer networks,” _Journal of complex networks_ , vol. 2, no. 3, pp. 203–271, 2014.
  * [30] S. Boccaletti, G. Bianconi, R. Criado, C. I. Del Genio, J. Gómez-Gardenes, M. Romance, I. Sendina-Nadal, Z. Wang, and M. Zanin, “The structure and dynamics of multilayer networks,” _Physics reports_ , vol. 544, no. 1, pp. 1–122, 2014.
  * [31] E. Cozzo, G. F. De Arruda, F. A. Rodrigues, and Y. Moreno, _Multiplex networks: basic formalism and structural properties_. Springer, 2018.
  * [32] S. Ji, P. Mittal, and R. Beyah, “Graph data anonymization, de-anonymization attacks, and de-anonymizability quantification: A survey,” _IEEE Communications Surveys & Tutorials_, vol. 19, no. 2, pp. 1305–1326, 2016.
  * [33] T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean, “Distributed representations of words and phrases and their compositionality,” in _Advances in neural information processing systems_ , 2013, pp. 3111–3119.
  * [34] Z. Yang, M. Ding, C. Zhou, H. Yang, J. Zhou, and J. Tang, “Understanding negative sampling in graph representation learning,” in _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2020, pp. 1666–1676.
  * [35] M. De Domenico, A. Lancichinetti, A. Arenas, and M. Rosvall, “Identifying modular flows on multilayer networks reveals highly overlapping organization in interconnected systems,” _Physical Review X_ , vol. 5, no. 1, p. 011027, 2015.
  * [36] M. De Domenico, V. Nicosia, A. Arenas, and V. Latora, “Structural reducibility of multilayer networks,” _Nature communications_ , vol. 6, no. 1, pp. 1–9, 2015.
  * [37] C. Stark, B.-J. Breitkreutz, T. Reguly, L. Boucher, A. Breitkreutz, and M. Tyers, “Biogrid: a general repository for interaction datasets,” _Nucleic acids research_ , vol. 34, no. suppl_1, pp. D535–D539, 2006.
  * [38] M. E. Dickison, M. Magnani, and L. Rossi, _Multilayer Social Networks_. Cambridge University Press, 2016.
  * [39] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” _arXiv preprint arXiv:1609.02907_ , 2016.
  * [40] P. Erdős and A. Rényi, “On random graphs I,” _Publicationes Mathematicae (Debrecen)_ , vol. 6, pp. 290–297, 1959.
  * [41] D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’networks,” _nature_ , vol. 393, no. 6684, pp. 440–442, 1998\.

|  Luca Gallo received the bachelor’s degree in physics in 2016, and the
master’s degree in physics of complex systems in 2019, both from the
University of Turin. Currently, he is a Ph.D. student in complex Systems for
physical, socio-economic and life sciences at the University of Catania. His
research interests include dynamical systems, complex networks, and higher-
order networks.
---|---
|  Vito Latora received the Ph.D. in Theoretical Physics in 1996 from the
University of Catania, Italy. Currently, he is Professor of Applied
Mathematics, Chair of Complex Systems, and Head of the Complex Systems and
Networks Research Group in the School of Mathematical Sciences at Queen Mary
University of London. He is also Professor of Physics at the University of
Catania. His research interests include the structure and dynamics of
multiplex networks, temporal networks and higher-order networks. He is
interested in applications of network science to study innovation ecosystems
and to understand the social and neural aspects of human creativity. He is
coauthor of more than 200 scientific publications, and editor of the Journal
of Complex Networks.
---|---
|  Alfredo Pulvirenti received the Ph.D. in Computer Science in 2003 from the
University of Catania. Currently, he is Associate Professor of Computer
Science at the University of Catania. His research interests mainly focuses on
bioinformatics and data analysis with applications in biomedicine. In
particular, he studies methods for pathway and biological network analysis,
drug repositioning, ncRNAs, design of pipelines for RNA-seq and DNA-Seq data,
subgraph matching, and motif finding. He his coauthor of more than 140
scientific publications.
---|---