# Initialization for Network Embedding: A Graph Partition Approach

Wenqing Lin<EMAIL_ADDRESS>Tencent Inc.Shenzhen, China ,  Feng He
<EMAIL_ADDRESS>Tencent Inc.Shenzhen, China ,  Faqiang Zhang
<EMAIL_ADDRESS>Tencent Inc.Shenzhen, China ,  Xu Cheng
<EMAIL_ADDRESS>Tencent Inc.Shenzhen, China and  Hongyun Cai
<EMAIL_ADDRESS>Tencent Inc.Shenzhen, China

(2020)

###### Abstract.

Network embedding has been intensively studied in the literature and widely
used in various applications, such as link prediction and node classification.
While previous work focus on the design of new algorithms or are tailored for
various problem settings, the discussion of initialization strategies in the
learning process is often missed. In this work, we address this important
issue of initialization for network embedding that could dramatically improve
the performance of the algorithms on both effectiveness and efficiency.
Specifically, we first exploit the graph partition technique that divides the
graph into several disjoint subsets, and then construct an abstract graph
based on the partitions. We obtain the initialization of the embedding for
each node in the graph by computing the network embedding on the abstract
graph, which is much smaller than the input graph, and then propagating the
embedding among the nodes in the input graph. With extensive experiments on
various datasets, we demonstrate that our initialization technique
significantly improves the performance of the state-of-the-art algorithms on
the evaluations of link prediction and node classification by up to 7.76% and
8.74% respectively. Besides, we show that the technique of initialization
reduces the running time of the state-of-the-arts by at least 20%.

network embedding, initialization, graph partition, hyperparameter learning

††journalyear: 2020††copyright: acmcopyright††conference: The Thirteenth ACM
International Conference on Web Search and Data Mining; February 3–7, 2020;
Houston, TX, USA††booktitle: The Thirteenth ACM International Conference on
Web Search and Data Mining (WSDM ’20), February 3–7, 2020, Houston, TX,
USA††price: 15.00††doi: 10.1145/3336191.3371781††isbn:
978-1-4503-6822-3/20/02††ccs: Computing methodologies Machine learning††ccs:
Computing methodologies Learning latent representations††ccs: Information
systems Social networks

##  1\. Introduction

Graphs are so ubiquitous that most of data can be naturally modeled as graphs,
not to mention the social networks. Network embedding (Cai et al., 2017; Cui
et al., 2017; Hamilton et al., 2017a; Zhang et al., 2018; Goyal and Ferrara,
2018; Chen et al., 2018a) is an intensively studied and widely used technique,
which assigns each node in the graph a fixed-length vector that preserves the
structure of graph and is helpful in various tasks, such as link prediction
and node classification. As such, network embedding alleviates the difficult
issue of feature engineering on the graph. The solutions to network embedding
can be roughly classified into two categories, namely random walk based
approaches (Perozzi et al., 2014; Grover and Leskovec, 2016) and matrix based
approaches (Cao et al., 2015; Wang et al., 2016).

However, the problem of network embedding is non-convex (Chen et al., 2018b)
rendering the previous approaches rely on the stochastic gradient descent
(SGD) technique for optimization, which would incur the issue of stuckness in
the local minima. Therefore, the initialization strategies in the learning of
network embedding, that takes into account the structure of the input graph,
would dramatically affect the performance of the network embedding algorithms.

|
---|---
(a) $G$. |  (b) $G_{a}$.
Figure 1. A graph $G$ with $4$ partitions, each of which is colored
differently, and the abstract graph $G_{a}$ of $G$.

The previous approaches (Chen et al., 2018b) for the initialization in the
computation of network embedding take two steps: First, they coarsen the edges
or the star structures of the input graph $G$ which produces a smaller graph
$g$; Then, they exploit the existing algorithms (Perozzi et al., 2014; Grover
and Leskovec, 2016; Cao et al., 2015; Wang et al., 2016) to compute $g$’s
network embedding, which are directly used as the initialization in the
learning of $G$’s network embedding. However, there exist some issues that
would make these approaches deficient. Firstly, the coarsening method
considers only the local structure, which might not reflect the overall
structure of the input graph. For example, an edge playing the role of bridge
(Tarjan, 1974) in the graph could be coarsened, rendering the communities
incident to the bridge even difficult to be separated from each other.
Secondly, since a node $v$ in $G$ might be pertinent to multiple nodes in $g$,
the direct inheritance of the embedding from one node in $g$ would result in
the missing of $v$’s important structural features in $G$. Thirdly, there
exist several hyperparameters in the existing algorithms (Perozzi et al.,
2014; Grover and Leskovec, 2016; Cao et al., 2015; Wang et al., 2016), which
would highly degrade their performance without careful configuration. However,
the previous approaches do not provide any effective solution about the tuning
of hyperparameters.

To address the aforementioned issues in the previous approaches, we propose a
graph partition based algorithm, dubbed as GPA, which first divides the input
graph $G$ into several disjoint subsets by the graph partition algorithm
(Karypis and Kumar, 1998) that minimizes the edge cut between subsets. Based
on that, we collapse the subgraph induced on each partition as an abstract
node and the cutting edges as the weighted edges to construct an abstract
graph $G_{a}$, which is of size much smaller than $G$ and represents the
sketch of $G$. Afterwards, we compute the network embedding of $G_{a}$ by a
modified version of the existing network embedding algorithm (Perozzi et al.,
2014). Note that, it is highly costly to tune the hyperparameters of the
network embedding algorithm on the fly, due to the huge search space and
expensive evaluation cost. To alleviate this issue, we devise an approach that
learns a regression model for the hyperparameter configurations in a
preprocessing step and computes a suitable configuration in linear time.
Finally, the initial embedding of each node in $G$ is computed by propagating
$G_{a}$’s embedding among the nodes in $G$. In the experiments, we demonstrate
that the performance of GPA outperforms the state-of-the-arts on various
tasks, i.e., link prediction and node classification. Besides, we show that
the initialization strategies of GPA lead to the speedup of the running time
of the baseline algorithms.

In summary, the contributions of the present work are the followings.

  * •

We devise the GPA algorithm as an effective technique for the initialization
of network embedding algorithms. Specifically, GPA considers the structure of
the input graph by exploiting the graph partition algorithm to construct the
sketch of a graph and minimize the size of edge cut.

  * •

We develop the algorithm to generate the abstract graph, which is a weighted
graph and is much smaller than the input graph. We also devise the algorithm
to compute the network embedding on the weighted graph, which is not discussed
in the previous approaches.

  * •

We propose an efficient algorithm that produces the initial embedding of each
node in the input graph from the embedding of the abstract graph, and smooths
the initialization via a propagation process.

  * •

We develop the hyperparameter learning algorithm that addresses the issue of
hyperparameter tuning for the network embedding on the abstract graph, which
improves the performance of the proposed algorithm.

  * •

We demonstrate in various experiments where GPA outperforms the state-of-the-
arts by up to 8.74% performance gain on effectiveness and reduces the running
time by at least 20%.

Paper organization. Section 2 explains the definitions and notations used in
the paper. Section 3 provides an overview of our solution, as well as the
details of the algorithms that address the goal in this paper. After that, we
demonstrate the superior performance of our algorithms compared with the
baseline methods over several graphs. Finally, we discuss the related work in
Section 5 and conclude the paper in Section 6.

##  2\. Preliminaries

Consider a graph $G=(V,E)$, where $V$ is the set of nodes and $E$ is the set
of edges. We say that a node $v\in V$ is a neighbor of the other node $u\in V$
if there exists an edge $(u,v)\in E$. We denote $N(v)$ as the set of neighbors
of $v$ in $V$, i.e., $N(v)\subseteq V$.

A partitioning of $G$, denoted by
$\mathcal{P}=\\{V_{1},V_{2},\cdots,V_{k}\\}$, divides $V$ into $k$ disjoint
subsets where $k$ is a user-defined number, such that we have (i) $V_{i}\cap
V_{j}=\emptyset$ where $1\leq i<j\leq k$, and (ii)
$\cup_{V^{\prime}\in\mathcal{P}}V^{\prime}=V$.

An abstract graph $G_{a}=(V_{a},E_{a})$ of $G$ is constructed on the
partitioning $\mathcal{P}$ of $G$. In particular, each subset in $\mathcal{P}$
is represented as an abstract node $u_{a}$ in $V_{a}$. In other words, there
is a bijective function $b$ that maps each partition
$V^{\prime}\in\mathcal{P}$ to an abstract node $u_{a}\in V_{a}$, i.e.,
$b(V^{\prime})=u_{a}$. Besides, there is a surjective function $p$ that maps
each node $v\in V$ to an abstract node $u_{a}\in V_{a}$, denoted by
$p(v)=u_{a}$. In addition, we construct a weighted edge
$(u_{a},u_{a}^{\prime})\in E_{a}$ for any two abstract nodes $u_{a}$ and
$u_{a}^{\prime}$ in $V_{a}$ if and only if there exist two nodes $v$ and
$v^{\prime}$ in $V$ such that we have (i) $p(v)=u_{a}$, (ii)
$p(v^{\prime})=u_{a}^{\prime}$, and (iii) $(v,v^{\prime})\in E$. The weight of
$(u_{a},u_{a}^{\prime})$, denoted by $w(u_{a},u_{a}^{\prime})$, is computed as
the number of such edges $(v,v^{\prime})$. That is, a weighted edge in $G_{a}$
represents the edges in $G$ that connect the corresponding partitions.

###### Example 0.

Figure 1(a) shows a graph $G$ with $12$ nodes and $16$ edges. Assume that we
partition $G$ into $4$ subsets, each of which is colored differently. Then,
the nodes with the same color are collapsed as an abstract node. Therefore,
there are $4$ abstract nodes in the abstract graph $G_{a}$ of $G$, as shown in
Figure 1(b). Besides, there is an edge of weight $2$ between the yellow
abstract node and the gray abstract node in $G_{a}$, since there exist $2$
edges, each of which connects a yellow node and a gray node in $G$. $\square$

---
Figure 2. The computing framework of GPA.

Given the graph $G=(V,E)$, the network embedding of $G$ maps each node $v\in
V$ to a $d$-dimensional vector $f(v)$, where $f:V\rightarrow\mathbb{R}^{d}$
and $d$ is a user-defined parameter satisfying $d\ll|V|$. In general, network
embedding should preserve the structure of $G$. In the other words, network
embedding minimizes

(1) $\sum_{v,u\in V}\big{(}\boldsymbol{A}_{v,u}-\theta(f(v),f(u))\big{)}^{2}$

where $\boldsymbol{A}\in\mathbb{R}^{|V|\times|V|}$ could be the matrix of
connections, such as the adjacency matrix of $G$, i.e., $\boldsymbol{A}_{v,u}$
is $1$ if $(v,u)\in E$ otherwise $0$, and $\theta$ is a similarity function
that maps $f(v)$ and $f(u)$ to a real value in $\mathbb{R}$.

As aforementioned, most of the algorithms for network embedding ultimately
exploit the technique of stochastic gradient descent (SGD) for optimization,
which would suffer from the issue of stucking in the local minima. Therefore,
the initialization, that takes into account the structure of the input graph,
could play an important role in the learning of network embedding that largely
enhances its performance.

Goal. Given a graph $G=(V,E)$, we are to compute for each node $v\in V$ a
coarse embedding $f(v)$, which preserves the sketching structure of $G$ and
can be used as the initialization for the network embedding algorithms.

##  3\. Methodologies

A naive approach for the initialization of network embedding is by random,
which assigns random numbers in ${\mathbb{R}}$ for the initial embedding of
each node in the graph. However, this approach disregards the structure of the
input graph, rendering it unsuitable for network embedding. Instead, we
propose the graph partition based algorithm (GPA) that depicts the sketch of
the input graph $G=(V,E)$ using the partitioning of $G$, which are then
processed as the initial embedding of each node in $V$.

Specifically, GPA takes two phases in its computing framework, namely the
preprocessing phase and the initialization phase, as shown in Figure 2.

In the initialization phase, GPA first computes a partitioning $\mathcal{P}$
of $G$ by the graph partitioning algorithm, which produces $k$ disjoint
subsets of $V$, where $k$ is a user-defined number and will be discussed in
Section 3.1. Then, we construct an abstract graph $G_{a}=(V_{a},E_{a})$ based
on the partitioning of $G$, as aforementioned. Note that, the size of $G_{a}$
is $k$, which should be much smaller than the size of $G$, i.e.,
$|V_{a}|=k\ll|V|$.

After that, we compute the network embedding $f_{a}$ of the abstract graph
$G_{a}$, which is a weighted graph, by a modified version of random walk based
algorithm (Perozzi et al., 2014). Finally, each node in $G$ inherits the
embedding of its corresponding abstract node in $G_{a}$, and then performs the
embedding fusion among its neighbors via a propagation process. Once the
propagation is converged, we obtain the initial embedding of each node, which
will be taken as input by the network embedding algorithms on $G$.

On the other hand, in the preprocessing phase, we build a regression model
that learns the configuration of hyperparameters for the network embedding
algorithm on the abstract graph. As such, given an abstract graph, we are able
to identify a suitable set of hyperparameters by inspecting the regression
model with a linear time cost.

In what follows, we will elaborate the details of each step.

###  3.1. Abstract Graph Construction

To construct the abstract graph $G_{a}=(V_{a},E_{a})$ of $G=(V,E)$, we first
obtain a partitioning $\mathcal{P}$ of $G$, denoted by
$\mathcal{P}=\\{V_{1},V_{2},\cdots,V_{k}\\}$ where $k$ is a user-defined
number. The goal of graph partition is $(k,\epsilon)$-balanced where
$0<\epsilon<1$, such that it satisfies the constraint

$\max_{1\leq i\leq
k}|V_{i}|\leq(1+\epsilon)\Big{\lceil}\frac{|V|}{k}\Big{\rceil},$

and also minimizes the size of edge-cut, i.e.,

$\bigcup_{1\leq i,j\leq k}\\{(v,u)\in E\mid v\in V_{i},u\in V_{j}\\}.$

However, the $(k,\epsilon)$-balanced graph partition is NP-hard (Buluç et al.,
2016). To address this issue, we resort to the METIS algorithm (Karypis and
Kumar, 1998) for graph partitioning, which is widely adopted in practice and
incurs a running time complexity of $O(|V|+|E|+k\log k)$ (Karypis and Kumar,
1995).

Based on $\mathcal{P}$, we construct the abstract graph $G_{a}$ of $G$ by (i)
creating an abstract node $v_{a}$ for each partition
$V^{\prime}\in\mathcal{P}$, i.e., $b(V^{\prime})=v_{a}$, and (ii) connecting
two abstract nodes $v_{a}$ and $u_{a}$ with an abstract edge $(v_{a},u_{a})$
of a weight $w(v_{a},u_{a})$ if and only if there exist $w(v_{a},u_{a})>0$
edges $(v,u)\in E$ such that $v\in b^{-1}(v_{a})$ and $u\in b^{-1}(u_{a})$.
Hence, the number of abstract nodes in $G_{a}$ is $k$, i.e., the number of
partitions of $G$. Besides, the number of abstract edges of $G_{a}$ is bounded
by the size of edge cut.

One crucial issue remaining is how to decide $k$. On one hand, if $k$ is
small, then one abstract node would be pertinent to a lot of nodes in the
input graph $G$. As such, the initial embedding of each node in $G$ inherited
from the corresponding abstract node would lose the power of effectiveness. On
the other hand, if $k$ is large, then the abstract graph $G_{a}$ would be
large too. Therefore, it would be highly expensive to compute the network
embedding on $G_{a}$, which increases the overall cost of the initialization
phase. To strike a good balance, we set $k=\lceil\sqrt{|V|}\rceil$, which is a
sufficiently large number but much smaller than $|V|$, that works well in
practice.

Input: The set $S$ of elements $e$ with the transition probability $P(e)$.

Output: The alias probability $P_{a}(e)$ and the alias $A(e)$ for all $e\in
S$.

1

2Let $P_{a}(e)=|S|\cdot P(e)$ and $A(e)=e$;

3 Let $S_{l}=\\{e\in S|P_{a}(e)>1\\}$ and $S_{s}=\\{e\in S|P_{a}(e)<1\\}$;

4 while  _$S_{l}$ is not empty_ do

5 Select any elements $x\in S_{s}$ and $y\in S_{l}$;

6 Let $A(x)=y$ and remove $x$ from $S_{s}$;

7 Decrease $P_{a}(y)$ by $1-P_{a}(x)$;

8 if  _$P_{a}(y)\leq 1$_ then

9 Remove $y$ from $S_{l}$;

10 If $P_{a}(y)<1$, then add $y$ into $S_{s}$;

11

12

return $P_{a}(e)$ and $A(e)$ for all $e\in S$.

Algorithm 1 Build-Alias($S$)

###  3.2. Abstract Graph Embedding

To compute the network embedding $f_{a}$ of the abstract graph $G_{a}$, which
is a weighted graph, we cannot directly exploit the previous network embedding
techniques (Perozzi et al., 2014; Tang et al., 2015; Grover and Leskovec,
2016; Qiu et al., 2018) as they are tailored for the un-weighted graphs.

In order to remedy this issue, we adopt the random walk based algorithm, i.e.,
DeepWalk (Perozzi et al., 2014), with a slight modification to accommodate the
network embedding learning on the abstract graph $G_{a}$. Note that, there are
two phases of computation in the random walk based algorithms: First, it
generates a number of random walks from each node in $G$; Then, it computes
the embedding of each node by word2vec (Mikolov et al., 2013), which takes as
input the random walks. There are some hyperparameters in the random walk
based algorithms, namely the number of random walks and the length of a random
walk, which would be configured by the hyperparameter learning module, as
explained in the later section. While the second phase remains the same, the
modification mainly happens in the first phase where the generation of random
walks follows the distribution of weights on the abstract edges.

In particular, when generating the random walks on $G_{a}$, the transition
probability of an edge $(u_{a},v_{a})\in E_{a}$, denoted by $P(u_{a},v_{a})$,
is calculated as the fraction of the weight $w(u_{a},v_{a})$ among the total
weights of the edges incident to $u_{a}$, i.e.,
$P(u_{a},v_{a})=\frac{w(u_{a},v_{a})}{\sum_{v_{a}^{\prime}\in
N(u_{a})}w(u_{a},v_{a}^{\prime})}$. Therefore, for each edge $(u_{a},v_{a})\in
E_{a}$, we have (i) $0<P(u_{a},v_{a})\leq 1$, and (ii)
$\sum_{v_{a}^{\prime}\in N(u_{a})}P(u_{a},v_{a}^{\prime})=1$. In the
generation of the random walk with the ending node $u_{a}$, we extend the walk
by selecting a node $v_{a}\in N(u_{a})$ with the transition probability
$P(u_{a},v_{a})$.

To make the selection of nodes in random walk efficiently, we resort to the
alias method (Vose, 1991) with a preprocessing step, as illustrated in
Algorithm 1. Specifically, the alias method builds for each element $e\in S$
an alias probability $P_{a}(e)\in[0,1]$ and an alias $A(e)\in S$. To explain,
for each element $e\in S$, the algorithm first enlarges the transition
probability $P(e)$ by $|S|$ times, and sets the initial alias probability
$P_{a}(e)=P(e)\cdot|S|$ and the initial alias of $e$ as itself (Line 1). Then,
the algorithm works iteratively where each iteration selects two distinct
elements $x$ and $y$ where $P_{a}(x)<1$ and $P_{a}(y)>1$, and then assigns $y$
as the alias of $x$ and decreases $P_{a}(y)$ by $1-P_{a}(x)$. The algorithm
terminates when there are no elements $y$ with $P_{a}(y)>1$ (Lines 2-9). After
that, to select an element from $S$, the alias method first randomly selects
an element $e\in S$ with the probability $\frac{1}{|S|}$, and then chooses $e$
with the probability $P_{a}(e)$ or $A(e)$ with the probability $1-P_{a}(e)$.
As a result, the time complexity of the preprocessing step and selecting an
element is $O(|S|)$ and $O(1)$ respectively.

1

Input: The graph $G=(V,E)$, the embeddings $f_{a}$ of $G$’s abstract graph,
and the threshold $\delta$.

Output: The set $f_{i}$ of initial embedding of each node $v\in V$.

2

3Let $f_{i}(v)=f_{a}(p(v))$ for each node $v\in V$;

4 do

5 for  _each node $v\in V$_ do

6 Let $f_{nbr}(v)=\frac{1}{|N(v)|}\sum_{u\in N(v)}f_{i}(u)$;

7 Compute $f_{i}^{\prime}(v)=\frac{1}{2}(f_{i}(v)+f_{nbr}(v))$;

8

9 Let $\Delta=\frac{1}{|V|}\sum_{v\in V}\|f_{i}^{\prime}(v)-f_{i}(v)\|$;

10 For each node $v\in V$, let $f_{i}(v)=f_{i}^{\prime}(v)$;

11

12while  _$\Delta >\delta$_;

return $f_{i}$.

Algorithm 2 Propagate($G$, $f_{a}$, $\delta$)
---
Figure 3. The generation of training data for hyperparameter learning.

###  3.3. Embedding Propagation

To compute the initial network embedding of $G$ from the network embedding
$f_{a}$ of the abstract graph $G_{a}$, a naive approach is to let the initial
embedding of each node $v$ equal the embedding of the corresponding abstract
node $p(v)$. However, this approach would suffer from the issue where the
nodes pertinent to the same abstract node have the same initial embeddings,
rendering this approach ineffective.

In order to address this issue, we devise an iterative approach where each
node updates its own embedding based on the embeddings of its neighbors until
the convergence is met. Specifically, in each iteration, each node $v\in V$
first aggregates the embeddings of $v$’s neighbors, which results in the
average embedding $f_{nbr}(v)$. Then, we update $v$’s embedding as the
aggregation of $f_{nbr}$ and its own embedding $f_{i}(v)$. The rationale is
that the embedding of a node should be close to the ones of its neighbors in
the graph.

Algorithm 2 illustrates the procedure of embedding propagation. Consider a
graph $G=(V,E)$, the abstract graph $G_{a}$ of $G$, and the network embedding
$f_{a}$ of $G_{a}$. At the beginning, for each node $v\in V$, we let the
initial embedding $f_{i}(v)$ of $v$ be the embedding $f_{a}(p(v))$ of its
abstract node $p(v)$ in $G_{a}$ (Line 1). Then, the algorithm works in several
iterations. In each iteration, the updating of the embedding of each node
$v\in V$ can be achieved in a two-layer computing framework. In the first
layer, we compute the average embedding $f_{nbr}$ among its neighbors (Line
4), i.e.,

$f_{nbr}(v)=\frac{1}{|N(v)|}\sum_{u\in N(v)}f_{i}(u).$

Then, we employ another layer to calculate the updated embedding
$f_{i}^{\prime}(v)$ of $v$ as the average of $f_{i}(v)$ and $f_{nbr}(v)$,
i.e.,

$f_{i}^{\prime}(v)=\frac{1}{2}(f_{i}(v)+f_{nbr}(v)).$

After that, for all nodes $v\in V$, we compute the average difference between
the updated embedding $f_{i}^{\prime}(v)$ and the previous embedding
$f_{i}(v)$ on their Euclidean distance (Line 6), denoted by

$\Delta=\frac{1}{|V|}\sum_{v\in V}{\|f_{i}^{\prime}(v)-f_{i}(v)\|}.$

Now, we can update the embedding $f_{i}(v)$ of $v$ as $f_{i}^{\prime}(v)$,
i.e., $f_{i}(v)=f_{i}^{\prime}(v)$, which completes this iteration. If the
average difference $\Delta$ is not more than a user-defined threshold
$\delta$, we terminate this procedure and return $f_{i}$ as the result.
Otherwise, we continue updating the embedding of each node $v\in V$ until
convergence is met, i.e., $\Delta\leq\delta$. Note that, $\delta$ is usually
set as a value proportional to $\frac{1}{|V|}$. Consequently, the time
complexity of one iteration is $O(\sum_{v\in V}|N(v)|)=O(|E|)$, as each node
needs to inspect the embeddings of its neighbors once.

Table 1. Hybrid features for hyperparameter learning. Category | Feature
---|---
hyperparameters | the number of random walks
the length of a random walk
graph statistics | the number of nodes of $G_{a}$
the number of edges of $G_{a}$
the density of $G_{a}$
the diameter of $G_{a}$
the average degree of $G_{a}$
the maximum degree of $G_{a}$
the average edge weight of $G_{a}$
the maximum edge weight of $G_{a}$

###  3.4. Hyperparameter Learning

There is one crucial issue remaining in the network embedding learning on the
abstract graph $G_{a}$ which is the configuration of hyperparameters in the
random walk based algorithm, i.e., the number of random walks and the length
of a random walk. A naive approach is to configure the hyperparameters with
random values. However, this approach would severely degrade the performance
of the network embedding algorithm. Alternatively, one might propose the
solution that exploits the existing optimization techniques (Bergstra et al.,
2011), such as grid search, to tune the hyperparameters on the fly.
Nevertheless, this approach would greatly increase the running time of the
network embedding algorithm, as the optimization could be costly.

To cope with this issue, we utilize a preprocessing phase which trains a
regression model that takes into account both the hyperparameters and the
statistics of the abstracts graphs. As such, given an abstract graph $G_{a}$,
we are able to infer from the model the suitable hyperparameters for $G_{a}$
with a slight cost, as explained shortly.

Table 1 shows the hybrid features for hyperparameter learning, which consists
of two features from the category of hyperparameters and eight features from
the category of graph statistics.

As illustrated in Figure 3, to generate the training data with the hybrid
features, we first construct a set $\mathcal{H}$ of hyperparameter
combinations and a set $\mathcal{S}$ of graph statistics for each abstract
graph $G_{a}$. Specifically, we enumerate the possible values for each
hyperparameter by heuristic to produce the set $\mathcal{H}$. Besides, to
generate $\mathcal{S}$, we first exploit the random graph generation technique
(Leskovec et al., 2005) to generate a set $\mathcal{G}$ of random abstract
graphs. And then, we utilize the graph mining tool, SNAP (Leskovec and Sosič,
2016), to calculate the statistics of each graph in $\mathcal{G}$, which
results in the set $\mathcal{S}$. After that, for each hyperparameter
combination $H\in\mathcal{H}$ and each graph statistics $S\in\mathcal{S}$, we
concatenate $H$ and $S$ to generate one data point with the hybrid features.
That is, the total number of data points will be
$|\mathcal{H}|\cdot|\mathcal{G}|$. All data points with the hybrid features
together form the hybrid matrix, denoted by $\boldsymbol{X}$.

For each row in the hybrid matrix $\boldsymbol{X}$, which is generated from a
hyperparameter combination $H$ and the statistics $S$ of an abstract graph
$G_{a}$, we compute the network embedding $f_{a}$ on $G_{a}$ with
hyperparameters in $H$. Then, we evaluate $f_{a}$ on Equation 1 with a slight
modification where $\theta$ is an Euclidean distance function and
$\boldsymbol{A}_{v,u}$ is $w(v,u)$ if $(v,u)\in E_{a}$ otherwise $0$. As such,
for all the data points in $\boldsymbol{X}$, we obtain a vector of the
evaluation scores, denoted by $\boldsymbol{Y}$.

Hence, our goal is to find a vector $\boldsymbol{w}$, such that we have

$\boldsymbol{X}\cdot\boldsymbol{w}^{T}=\boldsymbol{Y}.$

As a result, the objective is

$\min_{w_{1},w_{2},\dots,w_{\alpha}}\sum_{1\leq i\leq\beta}{(\sum_{1\leq
j\leq\alpha}{x_{ij}\cdot w_{j}}-y_{i})^{2}}$

where $\alpha$ is the number of dimensions of $\boldsymbol{X}$ and $\beta$ is
the number of data points in $\boldsymbol{X}$. Solving the above formula by
stochastic gradient descent, we are able to identify the vector
$\boldsymbol{w}$ that largely approximates to the optimal solution.

Once obtained the regression model, i.e., $\boldsymbol{w}$, we can compute a
suitable configuration of hyperparameters for a given abstract graph $G_{a}$
efficiently. To explain, we first produce the graph statistics $S$ of $G_{a}$
by utilizing SNAP. Then, we inspect each hyperparameter combination
$H\in\mathcal{H}$, and generate a data point $\boldsymbol{x}$ with the hybrid
features by concatenating $H$ and $S$. Hence, we can calculate the score of
the data point $\boldsymbol{x}$ as $y=\boldsymbol{x}\cdot\boldsymbol{w}^{T}$.
In the end, we choose the hyperparameter combination $H\in\mathcal{H}$ with
the highest score. Note that, the time complexity of identifying the suitable
hyperparameters is $O(|\mathcal{H}|)$.

Table 2. Datasets. Dataset | Category | #Nodes | #Edges | #Labels
---|---|---|---|---
Enron111http://www.cs.cmu.edu/$\sim$enron | email | 36,692 | 183,831 | 0
GRQC222http://snap.stanford.edu/data/ca-GrQc.html | collaboration | 5,242 | 14,496 | 0
Blog333http://socialcomputing.asu.edu/datasets/BlogCatalog | social | 10,312 | 333,983 | 39
Wiki444www.mattmahoney.net/dc/textdata | word | 4,777 | 184,812 | 40

##  4\. Experimental Evaluations

Table 3. Precisions in the task of link prediction evaluated by Cosine similarity and Euclidean similarity. Algorithm | Initialization | Cosine Similarity | Euclidean Similarity
---|---|---|---
Enron | GRQC | Blog | Wiki | Enron | GRQC | Blog | Wiki
node2vec | GPA | 0.9579 | 0.9933 | 0.9816 | 0.9325 | 0.9665 | 0.9947 | 0.9887 | 0.9438
HARP | 0.9209 | 0.9621 | 0.9708 | 0.9210 | 0.9418 | 0.9846 | 0.9618 | 0.9258
Random | 0.9136 | 0.9533 | 0.9631 | 0.9117 | 0.9309 | 0.9817 | 0.9587 | 0.9217
DeepWalk | GPA | 0.9702 | 0.9937 | 0.9820 | 0.9315 | 0.9691 | 0.9958 | 0.9879 | 0.9411
HARP | 0.9352 | 0.9625 | 0.9717 | 0.9178 | 0.9449 | 0.9842 | 0.9658 | 0.9354
Random | 0.9218 | 0.9430 | 0.9535 | 0.9024 | 0.9355 | 0.9764 | 0.9517 | 0.9276
LINE | GPA | 0.7849 | 0.9852 | 0.9436 | 0.8175 | 0.5790 | 0.9665 | 0.9274 | 0.8356
HARP | 0.7484 | 0.9526 | 0.9298 | 0.7849 | 0.5372 | 0.9471 | 0.9016 | 0.8126
Random | 0.7414 | 0.9411 | 0.9127 | 0.7658 | 0.5237 | 0.9392 | 0.8836 | 0.8028

In this section, we demonstrate that the proposed graph partition based
algorithm, dubbed as GPA, outperforms the state-of-the-art, i.e., HARP (Chen
et al., 2018b), as well as the randomized method, denoted by Random, on
various datasets and over different tasks, such as link prediction and node
classification. In particular, we apply the initialization techniques of GPA,
HARP and Random to the widely-used network embedding algorithms, i.e.,
node2vec (Grover and Leskovec, 2016), DeepWalk (Perozzi et al., 2014), and
LINE (Tang et al., 2015). Note that, (i) the original versions of network
embedding algorithms adopt Random as its initialization method, and (ii) for
each algorithm, we set the embedding vector size $d=128$ and their other
hyperparameters as the recommended ones in all experiments.

Our algorithms are implemented in Scala and C++, and all experiments are
conducted on a machine with 8 GB memory and an Intel Core i5 CPU (2.3 GHz),
which is installed with the macOS. For each set of experiments, we perform
each algorithm 10 times and report the average reading.

Following the previous work (Grover and Leskovec, 2016; Leskovec and Sosič,
2016), we evaluate the performance of the proposed algorithms against $4$
datasets from various categories in our experiments, as shown in Table 2.

###  4.1. Evaluations on Link Prediction

In the first set of experiments, we evaluate the performance of network
embedding with the initialization, provided by GPA, on the task of link
prediction. Specifically, we compare GPA against HARP and Random on the
graphs: Enron, GRQC, Blog, and Wiki.

To generate the testing and training sets for the task of link prediction on
each graph $G=(V,E)$, we first randomly select $\lceil\alpha|E|\rceil$ number
of edges from $E$, denoted by $E_{s}$, where $0<\alpha<1$. Then, we remove
$E_{s}$ from $E$, resulting in the residual set $E_{r}$ of edges, i.e.,
$E_{r}=E\setminus E_{s}$. After that, we compute the largest connected
component $C$ of the graph induced on the edges in $E_{r}$. Finally, we
produce the training set consisting of the edges in $E_{r}$ whose nodes are in
$C$, and generate the testing set that contains two parts: (i) The positive
samples, i.e., the set of the edges of $E_{s}$ whose nodes are both in $C$,
and (ii) the negative samples, i.e., the set of random pairs of nodes $u$ and
$v$ in $C$ where $(u,v)$ is not an edge in $E$. Note that, in the experiments,
we set $\alpha=10\%$ and the size of testing set as $2|E_{s}|$, i.e., the
number of positive samples equals the number of negative samples.
Additionally, due to practical considerations, for each node $v$ appearing in
$E_{s}$, the number of positive samples incident to $v$ should be equal to the
number of negative samples incident to $v$.

For each graph $G=(V,E)$, we compute the embedding of each node in $V$ by
running the network embedding with the initialization techniques on the
training set, and then calculate the similarity of all pairs of nodes in the
testing set. For each node $v$, we predict the top $t$ nodes that are the most
similar to $v$, where $t$ is the number of positive samples incident to $v$ in
$E_{s}$. We adopt two kinds of similarity measures: Cosine similarity and
Euclidean similarity. Given two vectors $\boldsymbol{x}$ and $\boldsymbol{y}$
of the same length, the Cosine similarity of $\boldsymbol{x}$ and
$\boldsymbol{y}$ is
$\frac{\boldsymbol{x}\cdot\boldsymbol{y}}{\|\boldsymbol{x}\|\|\boldsymbol{y}\|}$,
and the Euclidean similarity of them is $\|\boldsymbol{x}-\boldsymbol{y}\|$.
In the end, we calculate the accuracy as the fraction of positive samples in
the most similar $|E_{s}|$ pairs of nodes in the testing set.

Table 3 shows the accuracy of node2vec, DeepWalk, and LINE with the
initialization techniques, i.e., GPA, HARP, and Random, for link prediction by
Cosine similarity and Euclidean similarity on the datasets Enron, GRQC, Blog,
and Wiki respectively. As we can see, GPA outperforms HARP on all datasets and
in terms of both similarity measures, and the results of HARP is slightly
better than the ones of Random. In particular, on the Enron dataset using the
Euclidean similarity, GPA is better than HARP on LINE by $7.8\%$, on node2vec
by $2.6\%$, and on DeepWalk by $2.5\%$. This is due to that GPA exploits
several effective strategies that overcome the shortage of HARP and lead to a
better initialization for the network embedding algorithms.

Table 4. F1 scores in the task of node classification. Algorithm | Initialization | Micro-F1 score | Macro-F1 score
---|---|---|---
Blog | Wiki | Blog | Wiki
node2vec | GPA | 0.3174 | 0.6310 | 0.2395 | 0.5830
HARP | 0.3028 | 0.6192 | 0.2281 | 0.5631
Random | 0.2916 | 0.6033 | 0.2195 | 0.5587
DeepWalk | GPA | 0.3399 | 0.6295 | 0.2563 | 0.5616
HARP | 0.3191 | 0.6029 | 0.2387 | 0.5481
Random | 0.3106 | 0.5967 | 0.2315 | 0.5380
LINE | GPA | 0.3070 | 0.4987 | 0.2082 | 0.4282
HARP | 0.2823 | 0.4798 | 0.2029 | 0.4165
Random | 0.2799 | 0.4687 | 0.1982 | 0.4091

###  4.2. Evaluations on Node Classification

In node classification, we evaluate the performance of GPA, HARP and Random on
the datasets, i.e., Blog and Wiki, whose nodes are associated with labels. We
run the embedding algorithm with the initialization techniques on each graph
to obtain the embedding of nodes, which are then input to a multi-class
logistic regression classifier utilizing one-vs-rest technique and L2
regularization. We randomly split the set of nodes equally to generate the
training and testing sets respectively. Following the previous work (Grover
and Leskovec, 2016), we measure the performance of GPA, HARP, and Random in
micro-F1 score and macro-F1 score.

Table 4 presents the micro-F1 score and macro-F1 score of all the algorithms
on the datasets Blog and Wiki. Observe that GPA consistently outperforms HARP
in all settings, and HARP is slightly better than Random. In particular,
regarding the method of LINE, the relative performance gain on Blog of GPA
compared to HARP is $8.76\%$ in micro-F1 score and $2.62\%$ in macro-F1 score.
Besides, on Wiki, DeepWalk with GPA gives us $4.41\%$ gain in micro-F1 score
and $2.46\%$ gain in macro-F1 score. This again demonstrates the superiority
of our graph partition based approach that provides effective initialization
for network embedding.

###  4.3. Evaluations on Efficiency

In this experiment, we evaluate the efficiency of GPA by comparing with HARP
on all datasets. Figure 4 reports the running time of GPA and HARP that take
as input the whole graph in each dataset. GPA is much faster than HARP on all
datasets with at least 20% performance gain. In particular, GPA reduces the
running time by 33.33% compared to HARP on the Enron dataset. This is because
HARP computes the initial embedding of each node in a hierarchical manner that
requires several iterations of computation, while GPA reduces the input graph
to the abstract graph of size $\large\lceil\sqrt{n}\large\rceil$ whose
embeddings are then propagated among the nodes in the input graph with a
linear cost, where $n$ is the number of nodes in the input graph.

---
Figure 4. The running time of the initialization techniques.

##  5\. Related Work

Network embedding or graph representation learning has been intensively
studied in the literature (see (Cai et al., 2017; Cui et al., 2017; Hamilton
et al., 2017a; Zhang et al., 2018; Goyal and Ferrara, 2018; Chen et al.,
2018a) and the references therein). Most of these approaches (Perozzi et al.,
2014; Tang et al., 2015; Grover and Leskovec, 2016; Hamilton et al., 2017b;
Qiu et al., 2018) exploit negative sampling or skip-gram models, which turn
out to be the non-convex problem (Goldberg and Levy, 2014; Chen et al., 2018b)
and usually solved by stochastic gradient descent (SGD). However, few of them
takes into account the effect of the initial embedding of each node in the
network that would dramatically impact the performance of the algorithms.

Besides HARP (Chen et al., 2018b), introduced in Section 1, MILE (Liang et
al., 2018) also adopts the hierarchical computing framework, almost the same
as HARP, but differs from HARP in that it aims to compute the final network
embedding for the input graph.

On the other hand, Mishkin et al. (Mishkin and Matas, 2015) discussed the
importance of initialization in the training of deep neural networks. However,
their approach does not consider the graph data, and can not be applied to
network embedding. The other line of research on network embedding is for
different problem setting or datasets (Yang et al., 2015; Tu et al., 2018; Ma
et al., 2018), making them unsuitable for solving the problem of this paper.

##  6\. Conclusions

In this paper, we studied the issue of initialization for network embedding
that would significantly affect the performance of network embedding
algorithms. To address this issue, we proposed the algorithm GPA that
constructs the abstract graph sketching the input graph by well partitioning
the input graph. We developed a weighted network embedding algorithm to
compute the embedding of nodes in the abstract graph. After that, the network
embedding of the abstract graph will be propagated among the nodes of the
input graph, which leads to the initial embedding of the input graph. Besides,
to make the weighted network embedding algorithm efficient, we devised a
regression model to address the issue of hyperparameter tuning in the weighted
network embedding algorithm. Finally, we demonstrated the effectiveness and
efficiency of GPA against the state-of-the-arts on various datasets. In
particular, GPA achieves the performance gains of up to 7.76% and 8.74% on
link prediction and node classification respectively, and reduces the running
time by at least 20%.

## References

  * (1)
  * Bergstra et al. (2011) James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. 2011.  Algorithms for Hyper-Parameter Optimization. In _Advances in Neural Information Processing Systems 24: NIPS 2011, Granada, Spain._ 2546–2554.
  * Buluç et al. (2016) Aydin Buluç, Henning Meyerhenke, Ilya Safro, Peter Sanders, and Christian Schulz. 2016.  Recent Advances in Graph Partitioning.  In _Algorithm Engineering - Selected Results and Surveys_. 117–158.
  * Cai et al. (2017) HongYun Cai, Vincent W. Zheng, and Kevin Chen-Chuan Chang. 2017\.  A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications.  _CoRR_ abs/1709.07604 (2017).  http://arxiv.org/abs/1709.07604
  * Cao et al. (2015) Shaosheng Cao, Wei Lu, and Qiongkai Xu. 2015.  GraRep: Learning Graph Representations with Global Structural Information. In _Proceedings of the 24th ACM International Conference on Information and Knowledge Management, CIKM 2015, Melbourne, VIC, Australia, October 19 - 23, 2015_. 891–900.
  * Chen et al. (2018a) Haochen Chen, Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2018a.  A Tutorial on Network Embeddings.  _CoRR_ abs/1808.02590 (2018).
  * Chen et al. (2018b) Haochen Chen, Bryan Perozzi, Yifan Hu, and Steven Skiena. 2018b.  HARP: Hierarchical Representation Learning for Networks. In _Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, New Orleans, USA, February 2-7, 2018_.
  * Cui et al. (2017) Peng Cui, Xiao Wang, Jian Pei, and Wenwu Zhu. 2017\.  A Survey on Network Embedding.  _CoRR_ abs/1711.08752 (2017).
  * Goldberg and Levy (2014) Yoav Goldberg and Omer Levy. 2014.  word2vec Explained: deriving Mikolov et al.’s negative-sampling word-embedding method.  _CoRR_ abs/1402.3722 (2014).  arXiv:1402.3722 http://arxiv.org/abs/1402.3722
  * Goyal and Ferrara (2018) Palash Goyal and Emilio Ferrara. 2018.  Graph embedding techniques, applications, and performance: A survey.  _Knowl.-Based Syst._ 151 (2018), 78–94.
  * Grover and Leskovec (2016) Aditya Grover and Jure Leskovec. 2016.  node2vec: Scalable Feature Learning for Networks. In _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016_. 855–864.
  * Hamilton et al. (2017a) William L. Hamilton, Rex Ying, and Jure Leskovec. 2017a.  Representation Learning on Graphs: Methods and Applications.  _IEEE Data Eng. Bull._ 40, 3 (2017), 52–74.
  * Hamilton et al. (2017b) William L. Hamilton, Zhitao Ying, and Jure Leskovec. 2017b.  Inductive Representation Learning on Large Graphs. In _Advances in Neural Information Processing Systems 30: NIPS 2017, Long Beach, CA, USA_. 1025–1035.
  * Karypis and Kumar (1995) George Karypis and Vipin Kumar. 1995.  Analysis of Multilevel Graph Partitioning. In _Proceedings Supercomputing, San Diego, CA, USA, December 4-8, 1995_. 29.
  * Karypis and Kumar (1998) George Karypis and Vipin Kumar. 1998.  A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs.  _SIAM J. Scientific Computing_ 20, 1 (1998), 359–392.
  * Leskovec et al. (2005) Jure Leskovec, Deepayan Chakrabarti, Jon M. Kleinberg, and Christos Faloutsos. 2005.  Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication. In _Knowledge Discovery in Databases: PKDD 2005, Porto, Portugal, October 3-7, 2005, Proceedings_. 133–145.
  * Leskovec and Sosič (2016) Jure Leskovec and Rok Sosič. 2016.  SNAP: A General-Purpose Network Analysis and Graph-Mining Library.  _ACM Transactions on Intelligent Systems and Technology (TIST)_ 8, 1 (2016), 1.
  * Liang et al. (2018) Jiongqian Liang, Saket Gurukar, and Srinivasan Parthasarathy. 2018\.  MILE: A Multi-Level Framework for Scalable Graph Embedding.  _CoRR_ abs/1802.09612 (2018).
  * Ma et al. (2018) Yao Ma, Zhaochun Ren, Ziheng Jiang, Jiliang Tang, and Dawei Yin. 2018.  Multi-Dimensional Network Embedding with Hierarchical Structure. In _Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, WSDM 2018, Marina Del Rey, CA, USA, February 5-9, 2018_. 387–395.
  * Mikolov et al. (2013) Tomas Mikolov, Ilya Sutskever, Kai Chen, Gregory S. Corrado, and Jeffrey Dean. 2013.  Distributed Representations of Words and Phrases and their Compositionality. In _Advances in Neural Information Processing Systems 26: NIPS 2013, Nevada, United States._ 3111–3119.
  * Mishkin and Matas (2015) Dmytro Mishkin and Jiri Matas. 2015.  All you need is a good init.  _CoRR_ abs/1511.06422 (2015).  arXiv:1511.06422 http://arxiv.org/abs/1511.06422
  * Perozzi et al. (2014) Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014\.  DeepWalk: online learning of social representations. In _The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’14, New York, NY, USA - August 24 - 27, 2014_. 701–710.
  * Qiu et al. (2018) Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. 2018\.  Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec. In _Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, WSDM 2018, Marina Del Rey, CA, USA, February 5-9, 2018_. 459–467.
  * Tang et al. (2015) Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. 2015\.  LINE: Large-scale Information Network Embedding. In _Proceedings of the 24th International Conference on World Wide Web, WWW 2015, Florence, Italy, May 18-22, 2015_. 1067–1077.
  * Tarjan (1974) Robert Endre Tarjan. 1974\.  A Note on Finding the Bridges of a Graph.  _Inf. Process. Lett._ 2, 6 (1974), 160–161.
  * Tu et al. (2018) Ke Tu, Peng Cui, Xiao Wang, Fei Wang, and Wenwu Zhu. 2018.  Structural Deep Embedding for Hyper-Networks. In _Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, New Orleans, USA, February 2-7, 2018_.
  * Vose (1991) Michael D. Vose. 1991\.  A Linear Algorithm For Generating Random Numbers With a Given Distribution.  _IEEE Trans. Software Eng._ 17, 9 (1991), 972–975.
  * Wang et al. (2016) Daixin Wang, Peng Cui, and Wenwu Zhu. 2016.  Structural Deep Network Embedding. In _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016_. 1225–1234.
  * Yang et al. (2015) Cheng Yang, Zhiyuan Liu, Deli Zhao, Maosong Sun, and Edward Y. Chang. 2015.  Network Representation Learning with Rich Text Information. In _Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015_. 2111–2117.
  * Zhang et al. (2018) Daokun Zhang, Jie Yin, Xingquan Zhu, and Chengqi Zhang. 2018\.  Network Representation Learning: A Survey.  _CoRR_ abs/1801.05852 (2018).