ProNE: Fast and Scalable Network Representation Learning

1 Introduction

Over the past years, representation learning has offered a new paradigm for network mining and analysis [Hamilton et al., 2017b]. Its goal is to project a network's structures into a continuous space-embeddings-while preserving its certain properties. Extensive studies have shown that the learned embeddings can benefit a wide range of network mining tasks [Perozzi et al., 2014; Hamilton et al., 2017b].

The recent advances in network embedding can roughly fall into three categories: matrix factorization based methods such as SocDim [Tang and Liu, 2009], GraRep [Cao et al., 2015], HOPE [Ou et al., 2016], and NetMF [Qiu et al., 2018]; skip-gram based models, such as DeepWalk [Perozzi et al., 2014], LINE [Tang et al., 2015], and node2vec [Grover and Leskovec, 2016]; and graph neural networks (GNNs), such as Graph Convolution [Kipf and Welling, 2017], GraphSage [Hamilton et al., 2017a], and Graph Attention [Veliˇckovi´c et al., 2018]. Commonly, the embeddings pre-trained by the first two types of methods are fed into downstream tasks' learning models, such as GNNs.

1 Code is available at https://github.com/THUDM/ProNE

Therefore, it is critical to generate effective network embeddings efficiently in order to serve large-scale real network applications. However, most of existing models focus on improving the effectiveness of embeddings, leaving their efficiency and scalability limited. For example, in factorization based models, the time complexity of GraRep is O(n3 ) with n being the number of nodes in a network, making it prohibitively expensive to compute for large networks; In skipgram based models, with the default parameter settings, it would cost LINE weeks and DeepWalk/node2vec months to learn embeddings for a network of 100,000,000 nodes and 500,000,000 edges by using 20 threads on a modern server.

To address the efficiency and scalability limitations of current work, we present a fast and scalable network embedding algorithm-ProNE. The general idea of ProNE is to first initialize network embeddings in an efficient manner and then to enhance the representation power of these embeddings. Inspired by the long-tailed distribution of most real networks and its resultant network sparsity, the first step is achieved by formulating network embedding as sparse matrix factorization; The second step is to leverage the higher-order Cheeger's inequality to spectrally propagate the initial embeddings with the goal of capturing the network's localized smoothing and global clustering information.

This design makes ProNE an extremely fast embedding model with the effectiveness superiority. We conduct experiments in five real networks and a set of random graphs. Extensive demonstrations show that the one-thread ProNE model is about 10-400× faster than popular network embedding benchmarks with 20 threads, including DeepWalk, LINE, node2vec (See Figure 1). Our scalability analysis suggests that the time cost of ProNE is linearly correlated with network volume and density, making it scalable for billionscale networks. In fact, by using one thread, ProNE requires only 29 hours to learn embeddings for the aforementioned network of 100,000,000 nodes.

In addition to its efficiency and scalability advantage, ProNE also consistently outperforms all baselines across all datasets for the multi-label node classification task. More importantly, the second step-spectral propagation-in ProNE is a general framework for enhancing network embeddings. By taking the embeddings generated by DeepWalk, LINE, node2vec, GraRep, and HOPE as the input, our spectral propagation strategy offers on average +10% relative improvements for all of them.

2 The Network Embedding Problem

We use G = (V, E) to denote an undirected network with V as the node set of n nodes and E as the edge set. In addition, we denote G's adjacency matrix (binary or weighted) as A and its diagonal degree matrix as D with Dii = ∑j Aij .

Given a network G = (V, E), the problem of network embedding aims to learn a mapping function f : V ↦→ Rd that projects each node to a d-dimensional space (d ≪ |V |) to capture the structural properties of the network.

Extensive studies have shown that the learned node representations can benefit various graph mining tasks. , such as node classification and link prediction. However, one major challenge is that it is computationally infeasible for most network embedding models to handle large-scale networks. For example, it takes the popular DeepWalk model months to learn embeddings for a sparse random graph of 100,000,000 nodes by using 20 threads [Mikolov et al., 2013a].

3 ProNE: Fast Network Embedding

In this section, we present ProNE-a very fast and scalable model for large-scale network embedding (NE). ProNE composes of two steps as illustrated in Figure 2. First, it formulates network embedding as sparse matrix factorization to efficiently achieve initial node representations. Second, it utilizes the higher-order Cheeger's inequality to modulate the network's spectral space and propagate the learned embeddings in the modulated network, which incorporates both the localized smoothing and global clustering information.

3.1 Fast NE as Sparse Matrix Factorization

The distributional hypothesis [Harris, 1954] has inspired the recent emergence of word and network embedding. Here we show how distributional similarity-based network embedding can be formulated as matrix factorization and more importantly, how it can enable efficient network embedding.

Network Embedding as Sparse Matrix Factorization

Node similarities are usually modeled by structural contexts. We propose to leverage the simplest structure-edge-to represent a node-context pair. The edge set then forms a nodecontext pair set D = E. Formally, we define the occurrence probability of context vj given node vi as

where σ(.) is the sigmoid function and ri, ci ∈ Rd represent the embedding and context vectors of node vi, respectively. Accordingly, the objective can be expressed as the weighted sum of log loss over all edges l = - ∑(i,j)∈D pi,j ln ˆ pi,j , where pij = Aij/Dii indicates the weight of (vi, vj) in D.

To avoid the trivial solution (ri=cj & ˆ pi,j=1), for each observed pair (vi, vj), the appearance of a context vj is also accompanied by negative samples PD,j , updating the loss as:

where τ is the negative sample ratio and PD,j-the negative samples associated with context node vj-can be defined as PD,j ∝ (∑i:(i,j)∈D pi,j)α with α = 1 or 0.75 [Mikolov et al., 2013b]. A sufficient condition for minimizing the objective in Eq. 2 is to let its partial derivative with respect to rT i cj be zero. Hence,

In observation of rT i cj representing the similarity between vi's embedding and vj's context embedding, we propose to define a proximity matrix M with each entry as rT i cj, i.e.,

Naturally, the objective of distributional similarity-based network embedding is transformed to matrix factorization. We use a spectral method-truncated Singular Value Decomposition (tSVD), i.e., M≈UdΣdV T d , where Σd is the diagonal matrix formed from the top-d singular values, and Ud and Vd are n×d orthonormal matrices corresponding to the selected singular values. Finally, Rd ← UdΣ1/2 d is the embedding matrix with each row representing one node's embedding.

Sparse Randomized tSVD for Fast Embedding

By far, we show how general distributional similarity-based network embedding can be understood as matrix factorization. However, tSVD for large-scale matrices (networks) is still time and space expensive. To achieve fast network embedding, we propose to use the randomized tSVD, which offers a significant speedup over tSVD with a strong approximation guarantee [Halko et al., 2011].

Here we show the basic idea of randomized tSVD. First, we seek to find Q with d orthonormal columns, i.e., M≈QQT M. Assuming such Q has been found, we define H=QT M, which is a small matrix (d×|V |) and can be decomposed efficiently by the standard SVD. Thus we can have H=SdΣdV T d for Sd, Vd orthogonal and Σd diagonal. Finally M can be decomposed as M ≈ QQT M = (QSd)ΣdV T d and the final output embedding matrix of this step is

The random matrix theory empowers us to find Q efficiently. The first step is to generate a |V | × d Gaussian random matrix Ω where Ωij ∼ N(0, 1d ). Given this, we can get Y =MΩ and take the QR decomposition , i.e., Y =QR, where Q is a |V | × d matrix whose columns are orthonormal.

Note that inspired by [Levy and Goldberg, 2014], a recent study shows that skip-gram based network embedding models can be viewed as implicit matrix factorization [Qiu et al., 2018]. However, the matrix to be implicitly factorized is a dense one, resulting in the O(|V |3 ) time complexity for its associated matrix factorization model, while our case involves sparse matrix factorization in O(|E|) (Cf. Eq. 4).

3.2 NE Enhancement via Spectral Propagation

Similar to DeepWalk and LINE, the embeddings learned above can only capture local structural information. To further incorporate global network properties, i.e., community structures, we propose to propagate the initial embeddings in the spectrally modulated network.

Formally, given the input/initial embeddings Rd, we conduct the following propagation rule:

where In is the identity matrix, ˜L is the Laplacian filter, and all together, D-1A(In - ˜L) is the modulated network of the input G. This is inspired by the higher-order Cheeger's inequality [Lee et al., 2014; Bandeira et al., 2013], which will be shown below. Note that the propagation strategy is general and can be also used to enhance existing embedding models, such as DeepWalk, LINE, etc. (Cf. Figure 4).

Bridge NE, Graph Spectrum, and Graph Partition

Higher-order Cheeger's inequality suggests that eigenvalues in graph spectral are closely associated with a network' spatial locality smoothing and global clustering. First, in graph spectral theory, the randomwalk normalized graph Laplacian is defined as L=In-D-1A. The normalized Laplacian can be decomposed as L=UΛU -1 , where Λ=diag([λ1, ..., λn]) with 0=λ1 ≤ · · · ≤ λn as its eigenvalues and U is the n×n square matrix whose ith column is the eigenvector ui. The graph Fourier transform of a signal x is defined as ˆx = U -1x while the inverse transform is x = U ˆx. Then a network propagation D-1Ax can be interpreted that x is first transformed into the spectral space and scaled by the eigenvalues, and then transformed back.

Second, the graph partition effect can be measured by the Cheeger constant (a.k.a., graph conductance). For a partition S ⊆ V , the constant is defined as φ(S) = |E(S)| min{vol(S),vol(V-S)} where E(S) is the set of edges with one endpoint in S and vol(S) is the sum of nodes' degree in node set S. The k-way Cheeger constant is defined as ρG(k) = min{max{φ(Si) : S1, S2, ..., Sk ⊆ V disjoint}} which reflects the effect of the graph partitioned into k parts. A smaller value means a better partitioning effect.

Higher-order Cheeger's inequality bridges the gap between graph spectrum and graph partition via controlling the bounds of k-way Cheeger constant as follows:

In spectral graph theory, the number of connected components in an undirected graph is equal to the multiplicity of the eigenvalue zero in graph Laplacian [Von Luxburg, 2007], which can be concluded from ρG(k)=0 when setting λk=0.

Eq. 7 indicates that small (large) eigenvalues control the network's global clustering (local smoothing) effect by partitioning it into a few large (many small) parts. This inspires us to incorporate the global and local network information into network embeddings by propagating the embeddings Rd in the partitioned/modulated network D-1A(In - ˜L), where the Laplacian filter ˜L = Ug(Λ)U -1 with g as the spectral modulator. To take both global and local structures into consideration, we design the spectral modulator as g(λ) = e- 1 2 [(λ-µ)2-1]θ . Therefore, we have the Laplacian filter

g(λ) can be considered as a band-pass filter kernel [Shuman et al., 2016; Hammond et al., 2011] that passes eigenvalues within a certain range and attenuates eigenvalues outside that range. Hence ρG(k) is attenuated for corresponding top largest and smallest eigenvalues, leading to the amplified local and global network information, respectively. Note that the band-pass filter is a general spectral network modulator and the other kinds of filters can also be used.

Chebyshev Expansion for Efficiency

To avoid the explicit eigendecomposition and Fourier transformation in Eq. 8, we utilize the truncated Chebyshev expansion. The Chebyshev polynomials of the first kind are defined recurrently as Ti+1(x) = 2xTi(x) - Ti-1(x) with T0(x) = 1, T1(x) = x. Then

where ¯Λ = - 12 [(Λ-µIn)2 -In], ¯L = - 12 [(L-µIn)2 -In]. ¯λ = 12 [(λ - µ)2 - 1], and the new kernel is f(¯λ) = e-¯λθ .

As Ti is orthogonal with the weight 1/√1-x2 on the interval [-1, 1], the coefficient of Chebyshev expansion for e-xθ can be obtained by:

where β=1 if i=0 otherwsie β=2 and Bi(θ) is the modified Bessel function of the first kind [Andrews and Andrews, 1992]. Then the series expansion of the Laplacian filter:

Truncated Chebyshev expansion provides an approximation for e-xθ with a very fast convergence rate. By combining Eqs. 11 and 6, the embeddings Rd can be enhanced by the propagation in the spectrally modulated network in a very efficient manner. In addition, to maintain the orthogonality of the original embedding space achieved by the sparse tSVD, finally we apply SVD on Rd again.

3.3 Complexity Analysis

The time complexity of SVD of H and QR decomposition of Y is O(|V |d2 ). Since |D| ≪ |V | × |V |, M is a sparse matrix and the time complexity of the multiplication involved in the process above is O(|E|). Therefore, the overall complexity for the first step is O(|V |d2 + |E|), which is very efficient.

The computation of Eqs. 6 and 11 can be efficiently executed in a recurrent manner. Denote ¯R(i) d = Ti(¯L)Rd, then ¯R(i) d = 2¯L ¯R(i-1) d - ¯R(i-2) d with ¯R(0) d = Rd and ¯R(1) d = ¯LRd. Note that ¯L = - 12 [(L-µIn)2 -In] and L is sparse. SVD on a small matrix is O(|V |d2 ). Therefore, the overall complexity for the second step is O(k|E| + |V |d2 ).

All together, the time complexity of ProNE is O(|V |d2 + k|E|). Due to space constraint, we cannot include details about its space complexity, which is O(|V |d + |E|).

3.4 Parallelizability

The computing time of ProNE is mainly spent in the sparse matrix multiplication, which is efficient enough for handling very large-scale graphs on a single thread. Nevertheless, there have been many progresses on sparse matrix multiplication parallelizability [Buluc¸ and Gilbert, 2012; Smith et al., 2015], which can offer a further speedup for our current implementation.

4 Experiments

We evaluate the efficiency and effectiveness of the ProNE method on multi-label node classification-a commonly used task for network embedding evaluation [Perozzi et al., 2014; Tang et al., 2015; Grover and Leskovec, 2016].

4.1 Experimental Setup

Datasets. We employ five widely-used datasets for demonstrating the effectiveness of ProNE. The dataset statistics are listed in Table 1. In addition, we also use a set of synthetic networks for evaluating its efficiency and scalability.

• BlogCatalog [Zafarani and Liu, 2009] is a social blogger network, in which Bloggers' interests are used as labels.
• Wiki 2 is a co-occurrence network of words in the first million bytes of the Wikipedia dump. Node labels are the Partof-Speech tags.
• PPI [Breitkreutz et al., 2008] is a subgraph of the PPI network for Homo Sapiens. Node labels are extracted from hallmark gene sets and represent biological states.
• DBLP [Tang et al., 2008] is an academic citation network where authors are treated as nodes and their dominant conferences as labels.
• Youtube [Zafarani and Liu, 2009] is a social network between Youtube users. The labels represent groups of viewers that enjoy common video genres.

Baselines. We compare ProNE with popular benchmarks, including both skip-gram (DeepWalk, LINE, and node2vec) and matrix factorization (GraRep and HOPE) based methods. For a fair comparison, we set the embedding dimension d = 128 for all methods. For the other parameters, we follow the original authors' preferred choices. For DeepWalk and node2vec, windows size m=10, #walks per node r=80, walk length t=40. p, q in node2vec are searched over {0.25, 0.50, 1, 2, 4}. For LINE, #negative-samples k = 5 and total sampling budget T=r×t×|V |. For GraRep, the dimension of the concatenated embedding is d=128 for fairness. For HOPE, β is calculated in authors' code and searched over (0, 1) for the best performance. For ProNE, the term number of the Chebyshev expansion k is set to 10, µ=0.2, and θ=0.5, which are the default settings. Note that convolution-based methods are excluded, as most of them are in (semi-)supervised learning settings and require side information features (such as embeddings) for training.

Running Environment. The experiments were conducted on a Red Hat server with Intel Xeon(R) CPU E5-4650 (2.70GHz) and 1T RAM. ProNE is implemented by Python 3.6.1.

Evaluation. We follow the same experimental settings used in baseline works [Perozzi et al., 2014; Grover and Leskovec, 2016; Tang et al., 2015; Cao et al., 2015]. We randomly sample different percentages of labeled nodes for training a liblinear classifier and use the remaining for testing. We repeat the training and predicting for ten times and report the average Micro-F1 for all methods. Analogous results also hold for Macro-F1, which thus are not shown due to space constraints. We follow the common practice for efficiency evaluation by the wall-clock time and ProNE's scalability is analyzed by the time cost in multiple-scale networks [Tang et al., 2015].

2 http://www.mattmahoney.net/dc/text.html

• (a) The node degree is fixed to 10 and #nodes grows

(b) #nodes is fixed to 10, 000 and the node degree grows

Table 2: Efficiency comparison based on running time (second).

4.2 Efficiency and Scalability

We compare the efficiency of different methods. The efficiency of all baselines is accelerated by using 20 threads/processes, while ProNE uses one single thread (Note that though in one minor step the number of threads used in the SciPy package is not controlled by users, its effect on efficiency is limited and all conclusions hold).

Table 2 reports the running time (both IO and computation time) of ProNE and the three fastest baselines-DeepWalk, LINE, and node2vec. The spectral matrix factorization baselines are much slower than them. For example, the time complexity of GraRep is O(|V |3 ), making it infeasible for relatively big networks, such as Youtube of 1.1 million nodes.

The running time results suggest that for PPI and Wikismall networks (1,000+ nodes), ProNE requires less than 10 seconds to complete while the fastest baseline LINE is at least 14× slower and DeepWalk/node2vec is about 100× slower. Similar speedups can be consistently observed from BlogCatalog and DBLP-moderate-size networks (10,000+ nodes)- and YouTube-a relatively big network (1,000,000+ nodes). Remarkably, ProNE can embed the YouTube network within 11 minutes by using one thread while by using 20 threads LINE costs 100 minutes, DeepWalk requires 19 hours, and node2vec takes more than fives days. To sum up, the onethread ProNE model is about 10-400× faster than the 20thread LINE, DeepWalk, and node2vec models, and its efficiency advantage over other spectral matrix factorization methods is even more significant.

We use synthetic networks to demonstrate the scalability of ProNE and its potential for handling billion-scale networks in Figure 3. First, we generate random regular graphs with fixed node degree as 10 and the number of nodes ranging between 1,000 and 100,000,000. Figure 3(a) shows ProNE's running time for random graphs of different sizes, suggesting that the time cost of ProNE increases linearly as the network size grows. In addition, the running time for the five real datasets is also inserted into the plot, which is in line with the scalability trend on synthetic data. Therefore, we can project that it costs ProNE only ∼29 hours to embed a network of 0.1 billion nodes and 0.5 billion edges by using one thread, while it takes LINE over one week and may take DeepWalk/node2vec several months by using 20 threads.

Second, Figure 3(b) shows the running time of ProNE for random regular networks of a fixed size (10,000 nodes) and varied degree between 100 and 1,000. It can be clearly observed that the efficiency of ProNE is linearly correlated with network density. All together, we conclude that ProNE is a scalable network embedding approach for handling largescale and even dense networks.

4.3 Effectiveness

We summarize the prediction performance in Table 3. Due to space limitation, we only report the results in terms of MicroF1 and the standard deviation (σ) of the proposed model's results. Our conclusions below also hold for Macro-F1. In addition to ProNE, we also report the interim embedding results generated by the sparse matrix factorization (SMF) step in ProNE. For Youtube, we only use the two fastest and representative baselines, LINE and Deepwalk, to save time.

We observe that ProNE consistently generates better results than baselines across five datasets, demonstrating its strong effectiveness. Interestingly, it turns out that the simple sparse matrix factorization (SMF) step for fast embedding initialization in ProNE is comparable to or sometimes even better than existing popular network embedding benchmarks. With the spectral propagation technique further incorporated, ProNE generates the best performance among all baselines due to its effective modeling of local structure smoothing and global clustering information.

Spectral Propagation for Embedding Enhancement

Recall that ProNE composes of two steps: 1) sparse matrix factorization for fast embedding initialization and 2) spectral propagation for enhancement. Can spectral propagation also help improve the baseline methods?

We input the embeddings learned by DeepWalk, LINE, node2vec, GraRep, and HOPE into ProNE's spectral propagation step. Figure 4 shows both the original and enhanced results (denoted as "ProBaseline') on Wiki, illustrating significant improvements achieved by the Pro versions for all five baselines. On average, our spectral propagation strategy offers +10% relative gains for all methods, such as the 25% improvements for HOPE. Moreover, all enhancement experiments are completed in one second. The results demonstrate that the spectral propagation in ProNE is effective and a general and fast strategy for improving network embeddings.

5 RelatedWork

The recent emergence of network embedding is largely triggered by representation learning natural language processing [Mikolov et al., 2013b]. Its history can date back to spectral clustering [Chung, 1997] and social dimension learning [Tang and Liu, 2009]. Over the course of its development, most network embedding methods aim to model distributional similarities of nodes either implicitly or explicitly.

Inspired by the word2vec model, a line of skip-gram based embedding models have been presented to encode network structures into continuous spaces, such as DeepWalk [Perozzi et al., 2014], LINE [Tang et al., 2015], node2vec [Grover and Leskovec, 2016], and metapath2vec [Dong et al., 2017]. Recently, learned from [Levy and Goldberg, 2014], a study shows that skip-gram based network embedding can be understood as implicit matrix factorization and it also presents the NetMF model to perform explicit matrix factorization for learning network embeddings [Qiu et al., 2018]. The difference between NetMF and our model lies in that the matrix to be factorized by NetMF is a dense one, whose construction and factorization involve computation in O(|V |3 ) time complexity, while our ProNE model formalizes network embedding as sparse matrix factorization in O(|E|).

The other recent matrix factorization based network embedding models include GraRep [Cao et al., 2015] and HOPE [Ou et al., 2016]. Spectral network embedding is related to spectral dimension reduction methods, such as Laplacian Eigenmaps [Belkin and Niyogi, 2001] and spectral clustering [Yan et al., 2009]. These matrix decomposition based methods usually require expensive computation and excessive memory consumption due to their high time and space complexity.

Another significant line of work focuses on generalizing graph spectral into (semi-)supervised graph learning, such as graph convolution networks (GCNs) [Henaff et al., 2015; Defferrard et al., 2016; Kipf and Welling, 2017]. In GCNs, the convolution operation is defined in the spectral space and parametric filters are learned via back-propagation. Different from them, our ProNE model features a band-pass filter incorporating both spatial locality smoothing and global clustering properties. Furthermore, ProNE is an unsupervised and taskindependent model that aims to pre-train general embeddings, while most GCNs are (semi-)supervised with side features as input, such as the network embeddings learned by ProNE.

6 Conclusions

In this work, we propose ProNE-a fast and scalable network embedding approach. It achieves both efficiency and effectiveness superiority over recent powerful network embedding benchmarks, such as DeepWalk, LINE, node2vec, GraRep, and HOPE. Remarkably, the single-thread ProNE model is ∼10-400× faster than the aforementioned baselines that are accelerated by using 20 threads. For future work, we would like to apply the sparse matrix multiplication parallelizability technique to speed up ProNE as discussed in Section 3.4. In addition, we are also interested in exploring the connection between graph spectral based factorization models and graph convolution and graph attention networks.