# MANELA: A Multi-Agent Algorithm for Learning Network Embeddings

Han Zhang and Hong Xu(✉)
<EMAIL_ADDRESS><EMAIL_ADDRESS>University of Southern California, Los Angeles,
California, USA

###### Abstract

Playing an essential role in data mining, machine learning has a long history
of being applied to networks on multifarious tasks and has played an essential
role in data mining. However, the discrete and sparse natures of networks
often render it difficult to apply machine learning directly to networks. To
circumvent this difficulty, one major school of thought to approach networks
using machine learning is via network embeddings. On the one hand, this
network embeddings have achieved huge success on aggregated network data in
recent years. On the other hand, learning network embeddings on distributively
stored networks still remained understudied: To the best of our knowledge, all
existing algorithms for learning network embeddings have hitherto been
exclusively centralized and thus cannot be applied to these networks. To
accommodate distributively stored networks, in this paper, we proposed a
multi-agent model. Under this model, we developed the multi-agent network
embedding learning algorithm (MANELA) for learning network embeddings. We
demonstrate MANELA’s advantages over other existing centralized network
embedding learning algorithms both theoretically and experimentally. Finally,
we further our understanding in MANELA via visualization and exploration of
its relationship to DeepWalk.

##  I Introduction

Playing an essential role in data mining, machine learning has a long history
of being applied to networks on multifarious tasks, such as network
classification [1], prediction of protein binding [2], etc. Thanks to the
advancement of technologies such as the Internet and database management
systems, the amount of data that are available for machine learning algorithms
have been growing tremendously over the past decade. Among these datasets, a
huge fraction can be modeled as networks, such as web networks, brain
networks, citation networks, street networks, etc. [3]. Therefore, improving
machine learning algorithms on networks has become even more important.

However, the discrete and sparse natures of networks often render it difficult
to apply machine learning directly to networks. To circumvent this difficulty,
one major school of thought to approach networks using machine learning is via
network embeddings [4]. A network embedding consists of a set of Euclidean
vectors, each of which represents a node in the network and encapsulates
information about it. These vectors can then be fed into machine learning
algorithms as input for various classification and regression tasks.

Inspired by SkipGram [5] in the area of natural language processing, [6]
proposed DeepWalk, a network embedding learning algorithm based on random
walks and neural networks. Theoretically, DeepWalk remains poorly understood.
Nevertheless, thanks to its practical effectiveness, DeepWalk has become the
core of most recently developed algorithms for learning network embeddings,
such as LINE [7], node2vec [8], DNGR [9], metapath2vec [10], GraphSAGE [11],
M-NMF [12], LANE [13], PRUNE [14], RSDNE [15], and SIDE [16]. These works are
almost exclusively built upon random walks and neural networks.

Interestingly, to the best of our knowledge, all these works have been
exclusively focusing on developing centralized algorithms, a type of algorithm
that critically relies on the computational resource of a single designated
computer111This is commonly called a “node” in many other contexts. Here, we
use the “computer” instead to avoid confusion with “nodes” as in a network.,
referred to as the central computer. This, unfortunately, comes with at least
two significant drawbacks.

##### It is often impossible to apply centralized algorithms to many networks
that are distributively stored

Many common networks are inherently distributively stored. For example,
consider a network of real-world email services. In such a network, nodes
represent email accounts and edges represent correspondence between them.
Nodes and edges are stored on different email servers and no single email
server has access to the topology of the whole network. For another example,
social networks have been perhaps the most commonly studied kind of networks
in recent network embedding learning literature. In such a network, each node
represents a social network account and each edge typically represents a
friendship or follower/followee relationship between two accounts. In recent
years, the growing concern over cyber privacy has led to the rise of federated
social networks, such as Diaspora*, GNU Social, and pump.io [17]. In a
federated social network, each edge between two accounts are stored on the
servers that host these two accounts and is normally inaccessible to other
servers. Additional examples include business transaction/contracting
networks, web of trust networks, etc.

Many of these networks share one common characteristic: Various
considerations, such as legal concerns, privacy concerns, technical
difficulties, etc. often erect an insurmountable barrier against scraping and
aggregating them. This barrier, unfortunately, conflicts with the very
foundation of centralized algorithms—That is, the ability to efficiently
access all data from a single computer. Perhaps for this reason, these
networks, despite their ubiquity, have been rarely studied in the data mining
research community.

To resolve this issue, it can be tempting to apply federated learning [18].
While federated learning might be effective in many other contexts for
learning distributively stored data, it fails to apply in the peculiar context
of network embedding learning. In federated learning, a central computer
coordinates other computers (e.g., users’ mobile devices) with limited or no
sharing of data between them. However, at least one computer inevitably has
access to all learning results, i.e., the whole learned network embedding.
Since each vector in the network embedding encapsulates information about a
node, federated learning effectively aggregates information about the network
and therefore still leaves the issue unresolved.

One possible direction to address this issue is to develop multi-agent
algorithms. In the context of network embeddings, an agent can be seen as an
autonomous unit that is circumscribed to have access to only a local subset of
the network, such as an email server or a federated social network server in
the aforementioned examples. An algorithm is multi-agent if agents are able to
cooperatively carry it out with communications that do not disclose excessive
information to other agents. This locality nature makes a multi-agent
algorithm well-suited for learning embeddings on these networks.

##### Even for networks that are aggregated, centralized algorithms still bear
scalability issues

As the amount of the input data and the complexity of the model increase, such
algorithms would inevitably require vertical scaling, i.e., adding resources
(such as RAM, CPUs, GPUs, etc.) to the central computer. Vertical scaling,
however, usually comes with serious pecuniary limitations: It becomes
extremely expensive once the required amount of resources has increased beyond
a certain point [19]. Unfortunately, this is undesirable and can be even
devastating: It prohibits against fully utilizing and building models with
complexities commensurate with the massive amount of available data in the era
of “big data,” where networks with over billions of nodes are commonplace.

Facing the scalability issue of centralized algorithms, many researchers have
turned to distributed algorithms. Unlike centralized algorithms, which always
critically rely on a central computer, distributed algorithms are capable of
taking advantages of distributed computational resources. They can be also
seen as generalizations of multi-agent algorithms where the circumscription on
information accessibility is lifted. Instead of relying on vertical scaling, a
distributed algorithm connotes horizontal scaling: More computational
resources can be added with only a linearly increasing cost by simply
incorporating more computers. In fact, in many areas of machine learning and
data mining, researchers have started paying more attention to distributed
algorithms. For instance, in the area of deep learning, a huge portion of the
TensorFlow project has been focusing on developing algorithms that train deep
neural networks under various distributed computational environments [20].
Since a multi-agent algorithm is always distributed, an efficient multi-agent
algorithm may also potentially ameliorate the scalability issue.

Because of the importance of network embedding learning and its aforementioned
contemporary challenges, i.e., inherently distributively stored networks and
the scalability issue, it has become imperative to develop multi-agent
algorithms for learning network embeddings. Surprisingly, to the best of our
knowledge, until today, there do not yet exist any multi-agent algorithms for
learning network embeddings.

Our contributions: In this paper, we develop the first multi-agent algorithm
for learning network embeddings. We present our new multi-agent model (Section
III) and our new multi-agent algorithm (Section IV), the multi-agent network
embedding learning algorithm (MANELA), for learning network embeddings under
our multi-agent model. We also compare MANELA with other baseline algorithms
both theoretically (Section V) and experimentally (Section VI). Finally, we
further our understanding of MANELA via visualization (Section VII) and
exploration of its relationship to DeepWalk (Section VIII).

##  II Background

In this section, we introduce background on network embeddings, random walk-
based algorithms, and multi-agent algorithms.

###  II-A Definitions and Notations

Table I shows a list of basic notations and their meanings.

TABLE I: Notations used in this paper. Notation | Definition
---|---
$G$ | a network
$V$ | the node set of $G$
$E$ | the edge set of $G$
$|\cdot|$ | the number of elements in $\cdot$
$v,u$ | nodes in $V$
$\mathcal{N}(v)$ | the set of all neighbors of $v$
$a(v)$ | the agent that maintains $v$
$d(v)$ | the degree of $v$
$\operatorname{dist}(v,v^{\prime})$ | the distance between $v$ and $v^{\prime}$ on $G$
$\Phi(v)$ | an Euclidean vector that represents $v$
$f(v)$ | the frequency at which $a(v)$ performs updates

Given a network $G=\langle V,E\rangle$, its embedding is a set $\\{\Phi(v)\mid
v\in V\\}$ of $m$-D Euclidean vectors, in which each vector $\Phi(v)$
represents a node $v\in V$. These vectors encode some semantics of these
nodes, such as their adjacency and structural information in $G$.

###  II-B Random Walk-Based Algorithms

Random walk-based algorithms are a family of algorithms that learn network
embeddings from paths sampled using random walks in the input network. We
refer to such paths as walk paths. Generally speaking, these algorithms learn
the embedding of each node in the network by minimizing distances (under a
certain kind of metric) between the vectors that represent nodes co-occurring
in walk paths. They usually perform these minimizations via neural networks of
simple architectures. We introduce two representative algorithms in detail:

####  II-B1 DeepWalk

DeepWalk [6] undoubtedly plays an essential role in the network embedding
learning algorithm development in the past few years. Most, if not all, random
walk-based algorithms after the proposal of DeepWalk were more or less
variants of it. Inspired by SkipGram [5] in the area of natural language
processing, DeepWalk applies a simple neural network on walk paths. It first
generates multiple walk paths of length $\ell$ starting at each node for
$\gamma$ times, where $\ell$ and $\gamma$ are hyperparameters. Then it treats
nodes in each walk path $(v_{1},\ldots,v_{\ell})$ as if they were words in
each sentence (as in SkipGram)—that is, it maximizes the probability of the
presences of the nodes within distance $k$ to any node $v_{i}$ given the
presence of $v_{i}$ in a walk path, i.e., maximizing
$\sum_{i=1}^{\ell}\log\Pr(v_{\max\\{1,i-w\\}},\allowbreak\ldots,v_{i-1},\allowbreak
v_{i+1},\allowbreak\ldots,\allowbreak v_{\min\\{\ell,i+w\\}}\mid v_{i})$,
where $w$ is a hyperparameter, referred to as the window size. Either
hierarchical softmax or negative sampling can be used to approach this
optimization problem.

####  II-B2 node2vec

Node2vec [8] is a variant of DeepWalk that replaces its simple random walk
strategy with a more sophisticated alternative. Node2vec provides
hyperparameters $p,q$ to adjust how fast its biased random walks would move
further away from their predecessing nodes in a walk path. $p$ and $q$ are
competitor hyperparameters such that larger $p$ results in further walks from
the predecessing nodes, whereas larger $q$ renders closer walks. This biased
random walk strategy is a middle ground between breadth-first search (BFS) and
depth-first search (DFS) to strike a balance between encapsulating different
causes of similarities between nodes.

###  II-C Multi-Agent Algorithms

A multi-agent algorithm is an algorithm that is carried out by agents via
local computation and circumscribed communication. Agents are autonomous units
that have access to local information, e.g., information about itself and its
locally accessible neighbors. A multi-agent algorithm usually permits
communication between agents locally and without disclosing excessive
information, such as those acquired from another agent that is neither of the
two communicating parties.

We note that, another distinct concept, a distributed algorithm, is often
confused with a multi-agent algorithm. In contradistinction to a centralized
algorithm, a distributed algorithm is simply a kind of algorithm that is
capable of relatively more efficiently taking advantage of multiple computers.
While, by nature, a multi-agent algorithm is always a distributed algorithm,
the demarcation between a multi-agent algorithm and a general distributed
algorithm lies in the agents’ autonomy: For example, a distributed algorithm
would enjoy the benefits brought by a centralized computer and full
communication between computers, which are, however, unacceptable for a multi-
agent algorithm.

##  III Our Multi-Agent Model

The exact formulation of “multi-agent” varies from application to application.
In the context of network embedding learning, we formalize the multi-agent
model $\langle G=\langle V,E\rangle,s\rangle$ as follows:

  1. 1.

Maintenance: On the given network $G$, each node $v\in V$ is maintained by an
agent $a(v)$.

  2. 2.

Communication: Every agent knows the existence of all other agents and is
permitted to communicate with any of them.

  3. 3.

Possession of $G$: Each agent $a(v)$ by itself only directly possesses
knowledge on all edges incident to $v$.

  4. 4.

Accessibility of $G$: The accessibility of $G$ to $a(v)$ is circumscribed:
Each agent $a(v)$ is permitted and is only permitted to know the subnetwork
induced by all nodes within a small distance $s$ to $v$—In other words, each
agent is permitted to know a defined portion of $G$; it can acquire knowledge
on $G$ via communication with other agents if it does not possess this
knowledge but is permitted to know; but it is prohibited from acquiring
knowledge on $G$ beyond its permission by any means including communication
with (chains of) other agents.

We refer to these restrictions as the accessibility circumscription (AC). The
task is to learn a vector representation for each node under the AC.

Our multi-agent model is applicable to a variety of real-world scenarios. For
example, let us consider a Facebook-style federated social network such as
Diaspora*. Each user can be seen as a node $v$ in $G$ and two nodes are
connected iff their corresponding users are friends. (1): $a(v)$ is the server
that hosts $v$. (2): There is a global user directory so that each user knows
the existence of all other users and is permitted to communicate with any of
them. (3) and (4): $a(v)$ possesses $v$’s friend list (adjacent nodes) is
permitted to inquire $v^{\prime}$’s host $a(v^{\prime})$ about $v^{\prime}$’s
friend list if $v$ and $v^{\prime}$ are adjacent to each other (and hence
$s=2$), but is prohibited (or undesirable due to technical reasons) from
storing them. For privacy concerns, $a(v)$ is also prohibited from inquiring
$v^{\prime\prime}$’s friend list if $v$ and $v^{\prime\prime}$ are not
adjacent to each other.

##  IV Our Algorithm: MANELA

In this section, we first discuss the inadaptability of random walk-based
algorithms to be multi-agent. Then we outline the framework of our multi-agent
algorithm for learning network embeddings. Thenceforth, we delineate this
framework with discussions.

###  IV-A Inadaptability of Random Walk-Based Algorithms

The well known centralized network embedding learning algorithm, DeepWalk,
along with its variants, has achieved far better effectiveness than their
traditional non-embedding-based counterparts on many tasks [6, 8]. To design a
multi-agent algorithm, the most obvious means is perhaps to derive one from
these algorithms. Unfortunately, the centralized nature of random walks and
the agents’ autonomy in a multi-agent model can hardly reconcile: Walk paths
inherently bury excessive information about the network. For example, the
frequency at which a node $v$ is present in walk paths is accessible to
$a_{v}$ but also embodies the information about the distribution of degrees of
nodes in the whole network. This irreconciliation, referred to as the AC
hazard, undermines the very foundation of multi-agent algorithms, i.e., the
circumscription on information accessibility to agents.

###  IV-B Outline of Our Multi-Agent Algorithm

Facing the AC hazard, it is imperative to develop a new algorithmic framework
that accommodates multi-agent network embedding learning algorithms. Observing
that random walk, in essence, is a method for sampling pairs of nodes as
training data in random walk-based algorithms, we only need to substitute it
with a sampling method that comports with the requirement of our multi-agent
model.

Similar to Equation (4) in [5], for a given network $G=\langle V,E\rangle$, we
model our maximization objective as

$\begin{split}&\sum_{\begin{subarray}{c}v\in
V\end{subarray}}\bigg{\\{}\sum_{i=1}^{2w}\mathbb{E}_{v^{\prime}_{i}\sim
M\left(v,s,\vec{r}\right)}\log\sigma\left(\Phi(v)^{\top}\Phi(v^{\prime}_{i})\right)+\\\
&\sum_{i=1}^{2w}\sum_{j=1}^{k}\mathbb{E}_{v^{\prime}_{ij}\sim
P_{G}}\left[\log\sigma\left(-\Phi(v)^{\top}\Phi(v^{\prime}_{ij})\right)\right]\bigg{\\}}.\end{split}$
(1)

Here, $v^{\prime}_{i}$ is subject to the distribution
$M\left(v,s,\vec{r}\right)$, which we will discuss in detail later in Section
IV-D. $w$, called the half sample size, is a scalar hyperparameter that is
analogous to DeepWalk’s window size. $\vec{r}$, called the ratio vector, is a
normalized $s$-dimension vector hyperparameter in which the sum of all
components is one. $v^{\prime}_{ij}$ is subject to distribution $P_{G}$ in a
negative sampling procedure, which we choose as uniform distribution in our
algorithm.

Our algorithm is a multi-agent algorithm in which the vector $\Phi(v)$
representing each node $v\in V$ is maintained by agent $a(v)$ and is only
directly accessible to it. We refer to our algorithm as MANELA. To explain
MANELA, we first define two subprocedures: agent $a(v)$’s single
positive/negative update on $v$ from node $v^{\prime}$. During $a(v)$’s single
positive update on $v$ from $v^{\prime}$, $a(v)$ requests for
$\Phi(v^{\prime})$ from $a(v^{\prime})$. Then, $a(v)$ updates $\Phi(v)$ using

$\begin{split}\Phi(v)\leftarrow&\Phi(v)+\alpha\cdot\frac{\partial\log\sigma\left(\Phi(v)^{\top}\Phi(v^{\prime})\right)}{\partial\Phi(v)}\\\
=&\Phi(v)+\alpha\cdot\left(1-\sigma\left(\Phi(v)^{\top}\Phi(v^{\prime})\right)\right)\cdot\Phi(v^{\prime}),\end{split}$
(2)

where $\alpha$ is the learning rate. $a(v)$’s single negative update on $v$
from $a(v^{\prime})$ is similar to its positive counterpart except that
$\Phi(v^{\prime})$ is replaced with $-\Phi(v^{\prime})$.

Input: $v$: the node that the agent maintains

Input: $m$: the dimension of the vector that represents $v$

Input: $w$: the half sample size

Input: $\vec{r}$: the ratio vector

Input: $\kappa$: number of negative samples

Input: $T$: maximum running time

Output: the vector that represents $v$

1 Initialize $\Phi(v)$ to a $m$-D vector of random numbers

2 repeat

3 at frequency  _$f(v)$_ do

4 foreach  _$v_{+}\in\textnormal{{Sample}}(v,w,\vec{r})$_ do

5 $\Phi(v)\leftarrow$ Single positive update on $v$ from $v_{+}$

6 Uniformly randomly sample $\kappa$ nodes from $V$ into a newly created set
$V_{-}$

7 foreach  _$v_{-}\in V_{-}$_ do

8 $\Phi(v)\leftarrow$ Single negative update on $v$ from $v_{-}$

9

10

11

12

13until  _current running time exceeds $T$_

14return $\Phi(v)$

Algorithm 1 Update algorithm of agent $a(v)$

Algorithm 1 outlines MANELA and it works as follows. Each agent $v$
initializes $\Phi(v)$ to a random $m$-D vector (Algorithm 1). For each node
$v\in V$, at a certain frequency $f(v)$ (Algorithm 1), agent $a(v)$ samples
$v_{+}$ from distribution $M\left(v,s,\vec{r}\right)$ (Algorithm 1) and
performs its single positive update on $v$ from $a(v_{+})$ once (Algorithm 1).
In between $a(v)$’s every two consecutive single positive updates, $a(v)$
randomly samples $\kappa$ nodes $v_{-,1},\ldots v_{-,\kappa}$ (Algorithm 1)
and performs its single negative updates on $v$ from each of them (Algorithms
1 to 1), which corresponds to a $P_{G}$ that is uniform over $V$. MANELA
terminates upon reaching a running time limit (Algorithm 1).

###  IV-C Discussion: Iteration Frequency

What is the best frequency for a specific agent to perform updates? For
terminological convenience, we first make the following definitions.

######  Definition 1.

An update pair $\langle v_{\text{src}},v_{\text{tgt}}\rangle$, refers to the
updates that consist of $a(v_{\text{src}})$’s single positive update on node
$v_{\text{src}}$ from node $v_{\text{tgt}}$ and its subsequent $\kappa$ single
negative updates from randomly sampled nodes on node $v_{\text{src}}$
(Algorithms 1 to 1 in Algorithm 1). Here, $v_{\text{src}}$ is referred to as
the source node and $v_{\text{tgt}}$ is referred to as the target node.

The concept of update pair can be generalized to DeepWalk and node2vec if
negative sampling is used, where we refer to an update pair as a positive
update between $v_{\text{src}}$ and $v_{\text{tgt}}$ and the subsequent
$\kappa$ negative updates between $v_{\text{src}}$ and other nodes.

######  Definition 2.

An iteration $\operatorname{iter}(v_{\text{src}})$ is a set of source node
related streaming update pairs performing in a short time:

$\operatorname{iter}(v_{\text{src}})\coloneqq\\{<v_{\text{src}},v_{\text{tgt}}^{i}>\mid
i=1,\ldots,2w,v_{\text{tgt}}^{i}\sim M(v_{\text{src}},s,\vec{r})\\}.$ (3)

We define the frequency hyperparameter, denoted by $f(v)$, as the number of
iterations for which agent $a(v)$ performs in unit time. A policy that naively
specifies a uniform frequency hyperparameter for all agents would be unviable.
As an illustration, let us suppose node $v$ has thousands of adjacent nodes,
while node $v^{\prime}$ has only a few. Intuitively, $a(v)$ is supposed to
perform more updates than $a(v^{\prime})$ because $v$’s local information in
the network is far richer than $v^{\prime}$ and deserves more computing
resources. Therefore, in our algorithm, we set the frequency at which an agent
$a(v)$ performs updates to be proportional to $v$’s degree $d(v)$, i.e.,
$f(v)\propto d(v)$.

###  IV-D Discussion: $M(v,s,\vec{r})$

We now discuss the distribution $M(v,s,\vec{r})$, from which the target nodes
in update pairs are sampled. In a network, there are two widely accepted
causes that lead to the similarity between nodes (CSNs): homophily and
structural equivalence. Homophily refers to that, the smaller the distance
between two nodes, the more similar they are. For example, in a social
network, there are coteries of directly connected people (i.e., nodes) who
share common interests and they are likely to be similar to each other.
Structural equivalence refers to that the similarity of two nodes are
commensurate with that of their structural roles in their respective
vicinities [4]. For example, once again in a social network, there are fans
(i.e., nodes) who are connected to the same celebrities (i.e., nodes) and
these fans are likely to be similar to each other.

[8] observed that random walks guided by BFS result in embeddings that
encapsulate more structural equivalence than homophily, while random walks
guided by DFS result in embeddings that encapsulate more homophily than
structural equivalence. In light of this observation, we choose a middle
ground between the two sampling strategies to trade off the encapsulation of
homophily and structural equivalence in our algorithm. To achieve this, we
embody the trade-off into the distribution $M$, such that altering its
hyperparameters leads to different trade-offs between homophily and structural
equivalence. Formally, we define $M(v,s,\vec{r})$ as satisfying

$\displaystyle P\left(\operatorname{dist}(v^{\prime},v)=k;\vec{r},s\right)$
$\displaystyle=\begin{cases}r_{k},\quad&1\leq k\leq s\\\
0,\quad&\text{otherwise}\end{cases}$ (4) $\displaystyle
P\left(v^{\prime}\mid\operatorname{dist}(v^{\prime},v)=k;v\right)$
$\displaystyle\propto 1,$ (5)

where $r_{k}$ is the the $k^{\text{th}}$ component of hyperparameter
$\mathbf{r}$. In Eq. 4, $M(v,s,\vec{r})$ distinguishes nodes in the network
based on their distances to the source node $v$: The probability that the
distance from the target node $v^{\prime}$ to $v$ is $k$ is specified by
$r_{k}$. In Eq. 5, the conditional distribution when the distance is $k$ is a
uniform distribution. $\vec{r}$ is a vector hyperparameter that can be used to
adjust the sampling weights of nodes at different distances from $v$. At one
extreme, if $r_{1}=1$ and all other components are set to 0, then obviously
all sampled target nodes are adjacent to $v$. As a result, the sampled nodes
are similar to those sampled by random walks guided by BFS, and thus the
learned network embeddings would encapsulate more structural equivalence than
homophily. At the other extreme, if we set $r_{1}=r_{2}=\ldots=r_{s}$, then
the sampled nodes are similar to those sampled by random walks guided by DFS,
and thus the learned network embeddings would encapsulate more homophily than
structural equivalence.

In practice, such distributions are difficult to sample: Even if $s$ is as
small as 2, it may demand an exorbitant amount of computational resources for
an agent $a(v)$ to store $v$’s distances from all nodes within distance $s$.
Therefore, we introduce an approximation sampling strategy based on the
following definition:

######  Definition 3.

A node $v^{\prime}$ is a $k$-hop neighbor to $v$ on $G$ if there exists a path
of length $k$ on $G$ that starts at $v$ and ends at $v^{\prime}$.

Our sampling strategy is that, in each iteration, for each $k\in[1,s]$, agent
$a(v)$ uniformly samples $\lfloor 2wr_{k}\rceil$ from all $v$’s $k$-hop
neighbors as target nodes. The size of the samples is approximately $2w$.
Algorithm 2 shows the details of our sampling strategy.

Input: $v_{\text{src}}$: the source node

Input: $w$: the half sample size

Input: $\vec{r}$: the ratio vector

Output: a list of sampled nodes

1 Initialize $S$ to an empty list

2 for  _$k\leftarrow 1$ to $|\vec{r}|$_ do

3 repeat  _$\lfloor 2w\times r_{k}\rceil$_ times

4 $v\leftarrow v_{\text{src}}$

5 repeat  _k_ times

6 Uniformly randomly sample a node $v^{\prime}$ from $\mathcal{N}(v)$

7 $v\leftarrow v^{\prime}$

8

9 Add $v$ to $S$

10

11

12return $S$

Algorithm 2 Function: Sample($v_{\text{src}},w,\vec{r}$)

##  V Theoretical Analysis

TABLE II: Theoretical comparison between different algorithms. Subscripts
“sa,” “up,” and “pre” mean the sampling, update, and preprocessing
subprocedures, respectively. In the third column, “both” indicates that both
homophily and structural equivalence can be encapsulated; and
“tunable/untunable” indicates whether the encapsulation of different CSNs can
be tuned.

Algorithm |  | Amortized Time Complexity | Capability of Encapsulating Different CSNs | Multi-Agent?
---|---|---|---|---
MANELA |  | $\Theta_{\text{sa}}(N_{\text{u}}(G)){\textsuperscript{${\ddagger}$}}~{}+\Theta_{\text{up}}\left(N_{\text{u}}(G)\right)$ | Both, Tunable | Yes
DeepWalk |  | $\Theta_{\text{sa}}\left(N_{\text{u}}(G)\right){\textsuperscript{*}}~{}+\Theta_{\text{up}}\left(N_{\text{u}}(G)\right)$ | Both, Untunable | No
node2vec |  | $O_{\text{pre}}\left(|E|\cdot|V|\right)+\Theta_{\text{sa}}\left(N_{\text{u}}(G)\right){\textsuperscript{*}}~{}+\Theta_{\text{up}}\left(N_{\text{u}}(G)\right)$ | Both, Tunable | No

  * ${\ddagger}$

$\Theta_{\text{sa}}(s\cdot N_{\text{u}}(G))$ if $s$ is not treated as a
constant.

  * *

$\Theta_{\text{sa}}\left(\frac{\ell}{w(2\ell-w-1)}\cdot
N_{\text{u}}(G)\right)$ if $\ell$ and $w$ are not treated as constants.

In this section, we theoretically compare MANELA, DeepWalk, and node2vec in
terms of time complexity and capability of encapsulating different CSNs.
Throughout this section, for the sake of simplicity in our theoretical
analysis, we assume that the input network is always connected. To the best of
our knowledge, this is also the first theoretical analysis of the time
complexity and the capability of encapsulating different CSNs on DeepWalk and
node2vec.

###  V-A Time Complexity

In this subsection, we analyze the time complexities of the network embedding
learning algorithms. We analyze MANELA, DeepWalk, and Node2vec in three parts:
the sampling subprocedure, and the update subprocedure, and any preprocessing
subprocedure (node2vec only). For the sake of fair comparison, we assume that
DeepWalk and node2vec use negative sampling in lieu of hierarchical softmax
(which is generally more costly). We assume that all algorithms are required
to perform no less than the same number $N_{\text{u}}(G)$ of times of update
pairs for each node in the network as the source node and share a same
constant $\kappa$, where $N_{\text{u}}(G)$ is a monotonically non-decreasing
function with respect to $|V|$ and $|E|$. Practically speaking, we would
desire $N_{\text{u}}=\Omega(|V|)$ for a reasonable effectiveness and
$N_{\text{u}}(G)=O(|E|)$ for a reasonable scalability.

####  V-A1 The Sampling Subprocedure

For random walk-based algorithms, a walk path samples $\ell$ target nodes that
are used for multiple source nodes. In such a walk path, $2w$ nodes are used
as target nodes for each of the middle $(\ell-2w)$ nodes, whereas all the rest
$2w$ nodes near either end of the path use a total of
$2(w+(w+1)+\ldots+(2w-1))=w(3w-1)$ nodes as target nodes. The number of
performed update pairs with the source node being in the walk path is thus
$2w(\ell-2w)+w(3w-1)=w(2\ell-w-1)$. The resulted amortized time complexity of
the sampling subprocedure is $\ell/w(2\ell-w-1)$ for each update pair.
Therefore, the sampling subprocedures in DeepWalk and node2vec have a time
complexity of $\Theta((\ell/w(2\ell-w-1))\cdot N_{\text{u}}(G))$. Practically,
$\ell$ and $w$ are usually fixed as constants. In this case, the time
complexity is simplified to $\Theta(N_{\text{u}}(G))$.

In MANELA, the amortized time complexity of the sampling subprocedure for each
update pair is $O(s)$. Therefore, MANELA’s sampling subprocedure has a time
complexity of $\Theta(s\cdot N_{\text{u}}(G))$. Practically, $s$ is usually a
very small constant and does not change with respect to $G$. In this case,
this time complexity is simplified to $\Theta(N_{\text{u}}(G))$.

####  V-A2 The Update Subprocedure

All three embedding learning algorithms share the same time complexity of
$O(1)$ per update pair. The total time complexity for the update subprocedure
is thus $\Theta(N_{\text{u}}(G))$.

####  V-A3 The Preprocessing Subprocedure

Node2vec is the only algorithm in our analysis that consists of a
preprocessing subprocedure for preparing a probability matrix that guides its
random walks. For each $v\in V$ and all pairs of its adjacent nodes $v_{i}$
and $v_{j}$, it computes the matrix $\\{p_{ij}=P\left(suc=v_{j}\mid
pre=v_{i}\right)\\}$. $p_{ij}$ indicates the probability that $v_{j}$ is the
successor of $v$ under the condition that $v_{i}$ is the predecessor of $v$ in
a walk path. Therefore, the time complexity of this preprocessing subprocedure
is $\Theta\left(\sum_{v\in V}d(v)^{2}\right)$, and we have

$\displaystyle\sum_{v\in V}d(v)^{2}$ $\displaystyle\geq\frac{(\sum
d(v))^{2}}{|V|}=\frac{4|E|^{2}}{|V|}$ (6) $\displaystyle\sum_{v\in V}d(v)^{2}$
$\displaystyle=O\left({|V|}^{2}\cdot\frac{|E|}{|V|}+\left(|V|-\frac{|E|}{|V|}\right)\right)=O\left(|E|\cdot|V|\right).$
(7)

Here, Eq. 6 applies the Cauchy-Schwarz inequality and hence proves that this
preprocessing step has a time complexity of $\Omega(|E|^{2}/|V|)$. Eq. 7
considers the worst scenario where edges are allocated in a way so as to
maximize the number of nodes that are connected to all other nodes. There can
be no more than $O(|E|/|V|)$ nodes that are connected to all other nodes and
their degrees are $O(|V|)$. With all other nodes having a degree of $O(1)$, we
have the term to the right of the first equal sign. Therefore, Eq. 7 proves
that this preprocessing step also has a time complexity of $O(|E|\cdot|V|)$.
In addition, this upper bound is tight: Let us consider a complete network.
Then we have $\sum_{v\in
V}d(v)^{2}=|V|\cdot{\left(|V|-1\right)}^{2}=O(|E|\cdot|V|)$, which reaches the
upper bound.

On the one hand, the worst-case running time increases at least quadratic with
respect to the number of nodes. On the other hand, the best-case running time
also increases superlinearly insofar as the network is not sparse.222Our
theoretical analysis on node2vec’s scalability here seemingly contradicts [8,
Figure 6], which empirically demonstrates that node2vec’s running time
increased linearly with respect to the number of nodes on a series of Erdős-
Rényi networks. We can reconcile these two results as follows. With a fixed
average degree of nodes, we expect $|E|=\Theta(|V|)$ for Erdős-Rényi networks
and therefore they are sparse. Then they might have just happened to fall in
node2vec’s best-case scenarios and hence demonstrated an empirically linear
scalability. We do not think this is unscalable and, therefore, it is unlikely
that node2vec can survive today’s networks that commonly have more than
millions of nodes.

###  V-B Capability of Encapuslating CSNs

We now turn to their capability of encapsulating the two kinds of CSNs:
homophily and structurual equivalence. All three algorithms are capable of
encapsulating both of them with some trade-off. DeepWalk provides no
hyperparameter for tuning this trade-off. Unlike DeepWalk, node2vec enables
such tuning, by providing hyperparameters for adjusting how fast its biased
random walks would move further away from their predecessing nodes in walk
paths. MANELA enables such tuning via $\vec{r}$.

###  V-C Summary

We have summarized our results in Table II. From all three perspectives listed
in the table, MANELA always has the best results. Practically speaking,
MANELA’s time complexity is the same as that of DeepWalk and is much smaller
than that of nod2vec, which we have proven to have a serious scalability
issue. The encapsulation of different CSNs is tunable in MANELA and node2vec,
but not in DeepWalk. Most importantly, neither DeepWalk nor node2vec can be
made multi-agent, but MANELA is multi-agent and is thus more widely
applicable.

##  VI Experimental Evaluation

In this section, we experimentally evaluate MANELA on two tasks: node
classification and link prediction. We ran our experiments in Windows Server
R2 on an Amazon Elastic Compute Cloud (Amazon EC2) instance with 32GB RAM. For
DeepWalk and node2vec, we used the implementations provided by their
respective authors. We implemented all other algorithms in Python 3.

###  VI-A Implementation of MANELA

We followed the algorithmic details in Section IV and implemented MANELA under
centralized settings (for evaluational
purposes)333https://github.com/hanzh015/MANELA. To eliminate undesirable
uncertainties and thus to promote fairness in experimental comparisons,
instead of setting a maximum running time $T$, we set a maximum number of
update pairs. The underlying rationale is that, once $\kappa$ and $w$ are
fixed, each update pair would take approximately equal amount of time. We also
fix $s=2$ throughout Sections VI and VII due to its broad real-world
applicability. As a result, $\vec{r}$ is 2-D and hence $r_{2}$ can be
determined using $r_{2}=1-r_{1}$ once $r_{1}$ is known. For this reason, we
use $r_{1}$ in lieu of $\vec{r}$ when describing experimental settings
throughout Sections VI and VII. Our implementation of Algorithm 2 also removes
$v_{\text{src}}$ from $S$ before the return statement.

###  VI-B Datasets

We used real-world networks in our experiments. To ensure fairness in our
experimental evaluation, we only selected networks that have already been used
before for evaluating network embedding learning algorithms in the literature.

  * •

BlogCatalog [21]: A network that depicts blogers’ relationship. It has 10,312
nodes, 333,983 undirected edges444This exact number of edges is different from
that in [8]. We recounted this number and believe that [8] might have made a
mistake. and 39 labels. The labels of the nodes represent the topic categories
provided by authors.

  * •

Protein-Protein Interaction (PPI) [8]: A network that depicts the interaction
of proteins. We obtain labels from hallmark gene set [22]. The network has
3,890 nodes, 38,292 undirected edgesFootnote 4, and 50 different labels.

  * •

Wikipedia [8]: A co-occurrence network of words present in Wikipedia. It has
4,777 nodes, 92,091 undirected edgesFootnote 4, and 40 different labels.

###  VI-C Node Classification

Node classification is a classification task that, given the labels of a
subset of nodes in $G$, predicts the labels of the rest of the nodes in $G$.
It has been widely accepted as a standard instrument for evaluating network
embedding learning algorithms [4].

To ensure fairness in our experimental evaluation, we deployed an experimental
procedure that is commonly used in the literature. (a) First, for each
network, we ran each network embedding learning algorithm once to learn a
network embedding. (b) Then, we performed node classification using a one-
versus-rest logistic regression classifier (scikit-learn [23] on top of
liblinear [24] with 100 iterations): We randomly sampled a subset of nodes and
used their representing vectors and labels as training data; and we used the
representing vectors and labels of the rest of the nodes as test data. We
repeated this step for a range of train ratios, i.e., the ratios of the amount
of training data to that of all data. For each train ratio, we repeated this
step 10 times. (c) Finally, we evaluate predicted labels in the test data
using the micro-f1 and macro-f1 scores averaged over the 10 runs of Step (b)
for each train ratio.

Due to the absence of dedicated multi-agent algorithms, we adapted Relational
Neighbors (RN) [25], a centralized algorithm, and used it as an additional
baseline multi-agent algorithm. RN is an iterative algorithm for node
classification. In each iteration, it traverses all nodes once and labels each
node $v$ with the most frequent label among its adjacent nodes
$\mathcal{N}(v)$. The algorithm terminates when all nodes have been labeled.
RN can be easily adapted to be multi-agent: Each node $v$ is maintained by an
agent $a(v)$. Then $a(v)$ iteratively labels $v$ with the most frequent label
among $\mathcal{N}(v)$. This only requires exchanging information locally
between agents maintaining adjacent nodes and no information on the network
would have been explicitly passed along via a chain of agents.

TABLE III: The optimal hyperparameters for MANELA and node2vec used in node classification. Hyperparameters | BlogCatalog | PPI | Wikipedia
---|---|---|---
MANELA: $r_{1}$ | 0.7 | 0.1 | 0.3
node2vec: $p,q$ | 0.25,0.25 | 4,1 | 4,0.5

In our experiments, we terminated each network embedding learning algorithm
upon reaching the same number of times of update pairs. Following the
recommended hyperparameters in [8], we set $w$ to 10, $\ell$ to 80, and
$\gamma$ to 10 for both DeepWalk and node2vec. For MANELA, we also set $w$ to
10 and made it perform the same number of times of update pairs as DeepWalk
and node2vec. Following [6, 8], we set the dimension of learned vectors to
128. The learning rate of MANELA, DeepWalk, and node2vec is 0.025 initially
and decreases to $0.0001\times 0.025$ linearly with respect to the number of
times that they performed update pairs. Table III lists other hyperparameters
that we used. For node2vec, we used the optimized hyperparameters mentioned in
[8]. Similarly, we ranged $r_{1}$ from 0 to 1 and chose a value of $r_{1}$
that led to the highest micro-f1 score for each network.

TABLE IV: Micro-f1 scores in node classification resulted from each algorithm on each network where train ratios were set to 0.5. Algorithm |  | BlogCatalog | PPI | Wikipedia
---|---|---|---|---
MANELA |  | $0.386$ | $\mathbf{0.229}$ | $0.492$
node2vec |  | $\mathbf{0.394}$ | $0.216$ | $\mathbf{0.517}$
DeepWalk |  | $0.380$ | $0.210$ | $0.474$
RN |  | $0.037$ | $0.039$ | $0.005$

Table IV summarizes our results. It lists the micro-f1 score resulted from
each algorithm on each network with train ratios set to be 0.5. RN always had
micro-f1 scores that are far lower than those of any other algorithms for all
three networks.

For all three networks, MANELA had higher micro-f1 scores than those of
DeepWalk. This might be caused by the fact that MANELA has a tunable
capability of encapsulating homophily and structural equivalence. Mostly
noticeably, in PPI, MANELA’s micro-f1 score was as large as 9% higher than
DeepWalk.

MANELA had an overall performance that is comparable with that of node2vec:
MANELA worked better on PPI, while node2vec worked better on BlogCatalog and
Wikipedia. However, we emphasize that the settings of this comparison were
biased against MANELA: (a) First, under our centralized experimental settings,
while node2vec enjoyed unstinting exploitation of computational resources, our
MANELA was unduly fettered by the AC. (b) Secondly, even if our experimental
settings were made purely for evaluating centralized algorithms, they were
still biased toward node2vec. According to our theoretical analysis in Section
V-A3, node2vec has a serious scalability issue that MANELA does not bear. To
perform the same number of times of update pairs on the same network, node2vec
demands much more computational resources, which can be onerous even for
moderately large networks.

Figure 1: The results of node classification. Each row shows the results of a
network. The y-axes are micro-f1 scores for the plots in the left column and
are macro-f1 scores for those in the right column. The x-axes are train
ratios, which range from 0.1 to 0.9 for all three networks.

Fig. 1 shows more detailed comparisons among MANELA, DeepWalk, and node2vec.
They further confirm our previous results: Although inured to the AC, MANELA
was still more effective than DeepWalk; and it was also comparable to node2vec
in terms of effectiveness, despite node2vec’s undue demands on computational
resources.

###  VI-D Link prediction

TABLE V: Averaged MAPs of 10 runs by all three algorithms. Similar to those in Section VI-C, we chose the values of the listed hyperparameters by searching for the ones that led to the highest averaged MAPs. We set all other hyperparameters to the same as in Section VI-C to achieve the same number of times that each algorithm performed update pairs. Algorithm | Hyperparameters | Averaged MAP
---|---|---
MANELA | $r_{1}=0.4$ | 0.1360
node2vec | $p=4,q=4$ | 0.1059
DeepWalk | None | 0.0964
Figure 2: ${\operatorname{precision@}}k$ for different $k$’s averaged over 10
runs by MANELA, node2vec, and DeepWalk. Solid lines indicate the averages over
${\operatorname{precision@}}k$ produced in the 10 runs. Due to the heavy
computational costs, the average ${\operatorname{precision@}}k$’s were carried
out on edges incident to a set $V_{\text{s}}$ of 1024 randomly sampled nodes,
i.e., we approximated $E_{\text{pred}}$ in Eq. 8 as
$E_{\text{pred}}\mid_{\bigcup_{v\in V_{\text{s}}}\partial v}$. The transparent
area around the curves indicates the standard deviations for different $k$’s.

Link prediction is a rising application of network embeddings. A link
prediction algorithm takes a network as input (i.e., training data), often in
the context of a dynamically growing network, and predicts edges that would be
added in the future. For example, in a social network, the algorithm predicts
people (i.e., nodes) who are likely to get acquainted with each other in the
future and thus helps recommend new connections to them. The predicted edges
are usually in the form of a list (referred to as the predicted edge list and
denoted by $E_{\text{pred}}$) where predicted edges are sorted descendingly by
their predicted likelihood to be added.

Since link prediction has not been popularly used to the evaluation of network
embedding learning algorithms yet, we only experimented on PPI to show some
preliminary results. In our experiment, we performed multiple runs and, in
each run, we ran all three algorithms once. We generated the training and test
data as follows. In each run, we randomly removed 20% edges in PPI and used
them as test data. In case the resulting subnetwork is disconnected, we
further reduced it to the connected component with the maximum number of
nodes. Then we used this further reduced subnetwork as training data for
MANELA, DeepWalk, and node2vec to learn the network embeddings.

The score of a predicted edge $(v,v^{\prime})$ is calculate using
$\Phi(v)\cdot\Phi(v^{\prime})$. We use the precision at k, denoted by
${\operatorname{precision@}}k$, and the mean average precision (MAP) as the
metrics for evaluating the effectiveness for link prediction. The higher they
are, the more effective the algorithms are. Formally,
${\operatorname{precision@}}k$ is defined as

${\operatorname{precision@}}k\coloneqq\frac{|E_{\text{pred}}[\\{1,\ldots,k\\}]\cap
E_{\text{obs}}|}{k},$ (8)

where $E_{\text{pred}}[\\{1,\ldots,k\\}]$ denotes the set of the first $k$
edges in $E_{\text{pred}}$ and $E_{\text{obs}}$ is the test data (i.e., the
set of the removed 20% of the edges). The MAP is defined as

$\displaystyle E_{\text{obs}(v)}$ $\displaystyle\coloneqq
E_{\text{obs}}\cap\partial v$ (9) $\displaystyle E_{\text{pred}(v)}$
$\displaystyle\coloneqq E_{\text{pred}}\mid_{\partial v}$ (10)
$\displaystyle{\operatorname{precision@}}k(v)$
$\displaystyle\coloneqq\frac{\left|E_{\text{pred}(v)}[\\{1,\ldots,k\\}]\cap
E_{\text{obs}(v)}\right|}{k}$ (11) $\displaystyle AP\left(v\right)$
$\displaystyle\coloneqq\frac{\sum_{k=1}^{|E_{\text{pred}(v)}|}{\operatorname{precision@}}k\left(v\right)\cdot\mathbb{1}_{E_{\text{pred}(v)}[k]\in
E_{\text{obs}(v)}}}{\max\left\\{\left|E_{\text{pred}(v)}\mid_{E_{\text{obs}(v)}}\right|,1\right\\}}$
(12) $\displaystyle MAP$ $\displaystyle\coloneqq\frac{\sum_{v\in
V}AP\left(v\right)}{|V|},$ (13)

where $\partial v$ is the set of edges that are incident to $v$;
$E_{\text{pred}}\mid_{\partial v}$ denotes the sublist of $E_{\text{pred}}$
which only contains elements in both $E_{\text{pred}}$ and $\partial v$ and in
which their ordering in $E_{\text{pred}}$ is kept; and $E_{\text{pred}(v)}[k]$
denotes the $k^{\text{th}}$ element in $E_{\text{pred}(v)}$.

Table V summarizes our experimental results. MANELA clearly outperformed both
node2vec and DeepWalk in terms of averaged MAPs. Fig. 2 shows more detailed
results with varying $k$. These results further confirm the advantages of
MENELA over node2vec and DeepWalk, especially when $k$ was not too large.

##  VII Discussion: Visualization

(a) $r_{1}=1$

(b) $r_{1}=0.75$

(c) $r_{1}=0.5$

Figure 3: Visualization of the network embedding learned by MANELA on SYN-SBM.
Each scattered dot represents the location of a node in the 2-D space. Every
color indicates a different community.

Visualization is an important tool for understanding network embedding
learning algorithms. To understand the network embeddings learned by MANELA,
similar to [4], instead of using real-world networks, we used a random
network, SYN-SBM [26], which we deem more suitable for studying the
encapsulation of homophily.

SYN-SBM is a random network generated using the stochastic block model (SBM)
with 1024 nodes, each of which belongs to a random community out of 3
communities. This network has 1024 nodes and 29,833 edges. The edges were
added according to the following rules: For every two nodes in the same
community, a edges had the probability of 0.1 to be added. Edges between nodes
in different communities were added similarly except that the probability was
0.01. Considering homophily, nodes in the same community should tend to be
more similar to each other than nodes in different communities. Therefore,
ideally, nodes that belong to the same community were always clustered and
there were clear boundaries between clusters corresponding to different
communities.

We ran MANELA (with $r_{1}=1,0.75$, and 0.50) on SYN-SBM to learn network
embeddings consisting of 128-D vectors. We used the GEM python package [27] on
top of the t-SNE [28] visualization tool to project learned 128-D vectors onto
a 2-D vector space. The relative locations of nodes in the 2-D vector space
approximately reflect their distances in the original 128-D vector space:
Small distance between two nodes in the 2-D vector space usually implies a
small distance in the original high-dimensional space as well. Therefore, the
locations of these projected vectors provide an intuitive visualization of the
similarity between nodes embodied in the network embeddings.

Fig. 3 plots these projected 2-D vectors. When $r_{1}=1$, meaning that agents
only performed update pairs with its adjacent nodes as the target nodes, the
resulting boundaries between communities were somewhat blurred. However, when
we gradually decreased $r_{1}$ from 1 to 0.5, these boundaries were also
gradually cleared up. This is because, when $r_{1}$ decreased, the agents are
more likely to sample nodes in its community other than its adjacent nodes. As
a result, the sampled nodes, compared to those under the situation where
$r_{1}=1$, encoded a more accurate macro view of nodes’ adjacency, which is
critical in inferring homophily. Our intuitive understanding here is
consistent with that in [8]. As shown in this experiment, tuning $\vec{r}$
effectively tuned the extent of encapsulating homophily.

##  VIII Discussion: Relationship to DeepWalk

(a) DeepWalk

(b) MANELA

(c) DeepWalk

(d) MANELA

Figure 4: Similarity between Deepwalk and MANELA. The results are obtained
during the node classification experiment on the BlogCatalog dataset in
Section VI. (a) and (b) show the histograms of the number of times that each
node’s representing vector was updated. Both follow power laws. (c) and (d)
show the linear relationship between nodes’ degrees ($y$-axes) and the number
of times that their representing vectors were updated ($x$-axes). Each circle
represents a node in the network.

We further our understanding of MANELA by briefly exploring its relationship
to DeepWalk. MANELA and DeepWalk are quite similar in many aspects. For
example, both share very similar optimizing objectives and updating procedures
on single vectors. In addition, both involve procedures that sample nodes for
updating their representing vectors: DeepWalk employs random walks, while
MANELA employs a multi-agent variant of it (Algorithm 2 and Algorithm 1 in
Algorithm 1). Furthermore, as shown in Fig. 4, our experiment demonstrates the
similarity between the effects of their sampling procedures with respect to
the frequencies that nodes’ representing vectors were updated. This similarity
may partially explain why MANELA, while severely fettered by the AC, could
still consistently achieve effectiveness that is comparable to (and in fact
usually better than) that of DeepWalk.

##  IX Conclusion

In this paper, we proposed a multi-agent model for learning network
embeddings. To the best of our knowledge, this is the first attempt to learn
network embeddings under multi-agent settings. Under this model, we developed
MANELA, a multi-agent algorithm for learning network embeddings. We
demonstrated MANELA’s advantages over DeepWalk and node2vec both theoretically
and experimentally. Theoretically, MANELA is always the champion in terms of
amortized time complexity, the capability of encapsulating different CSNs, and
the multi-agentness. In our experimental evaluation, for node classification,
MANELA was more effective than both DeepWalk and RN. Even if it was inured to
the AC and conceded node2vec’s undue demands on computational resources,
MANELA was still able to achieve an effectiveness comparable to that of
node2vec. For link prediction, we also preliminarily showed that MANELA beat
both DeepWalk and node2vec on PPI. Finally, we furthered our understanding of
MANELA via visualization and exploration of its relationship to DeepWalk.

## References

  * [1] P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-Rad, “Collective classification in network data,” _AI Magazine_ , vol. 29, no. 3, pp. 93–106, 2008.
  * [2] B. Alipanahi, A. Delong, M. T. Weirauch, and B. J. Frey, “Predicting the sequence specificities of DNA- and RNA-binding proteins by deep learning,” _Nature Biotechnology_ , vol. 33, pp. 831–838, 2015.
  * [3] H. Xu, K. Sun, S. Koenig, and T. K. S. Kumar, “A warning propagation-based linear-time-and-space algorithm for the minimum vertex cover problem on giant graphs,” in _the International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research_ , 2018, pp. 567–584.
  * [4] P. Goyal and E. Ferrara, “Graph embedding techniques, applications, and performance: A survey,” _Knowledge-Based Systems_ , vol. 151, pp. 78–94, 2018.
  * [5] T. Mikolov, I. Sutskever, K. Chen, G. Corrado, and J. Dean, “Distributed representations of words and phrases and their compositionality,” in _the Neural Information Processing Systems Conference_ , 2013.
  * [6] B. Perozzi, R. Al-Rfou, and S. Skiena, “DeepWalk: Online learning of social representations,” in _the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , 2014, pp. 701–710.
  * [7] J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei, “LINE: Large-scale information network embedding,” in _the International Conference on World Wide Web_ , 2015, pp. 1067–1077.
  * [8] A. Grover and J. Leskovec, “node2vec: Scalable feature learning for networks,” in _the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , 2016, pp. 855–864.
  * [9] S. Cao, W. Lu, and Q. Xu, “Deep neural networks for learning graph representations,” in _the AAAI Conference on Artificial Intelligence_ , 2016, pp. 1145–1152.
  * [10] Y. Dong, N. V. Chawla, and A. Swami, “Metapath2vec: Scalable representation learning for heterogeneous networks,” in _the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , 2017, pp. 135–144.
  * [11] W. Hamilton, Z. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” in _the Neural Information Processing Systems Conference_ , 2017, pp. 1024–1034.
  * [12] X. Wang, P. Cui, J. Wang, J. Pei, W. Zhu, and S. Yang, “Community preserving network embedding,” in _the AAAI Conference on Artificial Intelligence_ , 2017, pp. 203–209.
  * [13] X. Huang, J. Li, and X. Hu, “Label informed attributed network embedding,” in _the ACM International Conference on Web Search and Data Mining_ , 2017, pp. 731–739.
  * [14] Y.-A. Lai, C.-C. Hsu, W. H. Chen, M.-Y. Yeh, and S.-D. Lin, “PRUNE: Preserving proximity and global ranking for network embedding,” in _the Neural Information Processing Systems Conference_ , 2017, pp. 5257–5266.
  * [15] Z. Wang, X. Ye, C. Wang, Y. Wu, C. Wang, and K. Liang, “RSDNE: Exploring relaxed similarity and dissimilarity from completely-imbalanced labels for network embedding,” in _the AAAI Conference on Artificial Intelligence_ , 2018, pp. 475–482.
  * [16] J. Kim, H. Park, J.-E. Lee, and U. Kang, “SIDE: Representation learning in signed directed networks,” in _the World Wide Web Conference_ , 2018, pp. 509–518.
  * [17] G. Silva, L. Reis, A. Terceiro, P. Meirelles, and F. Kon, “Implementing federated social networking: Report from the trenches,” in _Proceedings of the International Symposium on Open Collaboration_ , 2017, pp. 8:1–8:10.
  * [18] J. Konečný, H. B. McMahan, F. X. Yu, P. Richtarik, A. T. Suresh, and D. Bacon, “Federated learning: Strategies for improving communication efficiency,” in _NIPS Workshop on Private Multi-Party Machine Learning_ , 2016.
  * [19] M. T. Fisher and M. L. Abbott, _Scalability Rules: 50 Principles for Scaling Web Sites_. Addison-Wesley Professional, 2011, ch. 3, pp. 29–42.
  * [20] M. Abadi, A. Agarwal, P. Barham, E. Brevdo, Z. Chen, C. Citro, G. S. Corrado, A. Davis, J. Dean, M. Devin, S. Ghemawat, I. Goodfellow, A. Harp, G. Irving, M. Isard, Y. Jia, R. Jozefowicz, L. Kaiser, M. Kudlur, J. Levenberg, D. Mané, R. Monga, S. Moore, D. Murray, C. Olah, M. Schuster, J. Shlens, B. Steiner, I. Sutskever, K. Talwar, P. Tucker, V. Vanhoucke, V. Vasudevan, F. Viégas, O. Vinyals, P. Warden, M. Wattenberg, M. Wicke, Y. Yu, and X. Zheng, “TensorFlow: Large-scale machine learning on heterogeneous systems,” 2015, software available from tensorflow.org. [Online]. Available: https://www.tensorflow.org/
  * [21] L. Tang and H. Liu, “Scalable learning of collective behavior based on sparse social dimensions,” in _Proceedings of the 18th ACM Conference on Information and Knowledge Management_ , 2009, pp. 1107–1116.
  * [22] A. Liberzon, A. Subramanian, R. Pinchback, H. Thorvaldsdóttir, P. Tamayo, and J. P. Mesirov, “Molecular signatures database (msigdb) 3.0,” _Bioinformatics_ , vol. 27, no. 12, pp. 1739–1740, 2011.
  * [23] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay, “Scikit-learn: Machine learning in Python,” _Journal of Machine Learning Research_ , vol. 12, pp. 2825–2830, 2011.
  * [24] R.-E. Fan, K.-W. Chang, C.-J. Hsieh, X.-R. Wang, and C.-J. Lin, “LIBLINEAR: A library for large linear classification,” _Journal of Machine Learning Research_ , vol. 9, pp. 1871–1874, 2008.
  * [25] S. A. Macskassy and F. Provost, “A simple relational classifier,” DTIC Document, Tech. Rep., 2003.
  * [26] Y. J. Wang and G. Y. Wong, “Stochastic blockmodels for directed graphs,” _Journal of the American Statistical Association_ , vol. 82, no. 397, pp. 8–19, 1987.
  * [27] P. Goyal and E. Ferrara, “GEM: A Python package for graph embedding methods,” _Journal of Open Source Software_ , vol. 3, no. 29, p. 876, 2018\.
  * [28] L. v. d. M. Maaten and G. Hinton, “Visualizing high-dimensional data using t-sne,” _Journal of Machine Learning Research_ , vol. 9, pp. 2579–2605, 2008\.