Fast Network Embedding Enhancement via High Order Proximity Approximation

1 Introduction

A network is an essential data type widely used in our daily lives and academic researches, such as friendship networks in Facebook and citation networks in DBLP [Ley, 2002]. Researchers have made great effort on developing machine learning algorithms for various network applications, e.g. vertex classification [Sen et al., 2008], tag recommendation [Tu et al., 2014], anomaly detection [Akoglu et al., 2015] and link prediction [Liben-Nowell and Kleinberg, 2007]. Most supervised machine learning algorithms applied on these applications require a set of informative features as input [Grover and Leskovec, 2016]. Hand-crafted features may suit the need but require much human effort and expert knowledge. Therefore, representation learning [Bengio et al., 2013] which learns feature embeddings via optimization learning was proposed to avoid feature engineering and improve the flexibility of features. In terms of network analysis, Network Representation Learning (NRL) which aims to learn distributed real-valued embeddings for vertices of a network has attracted much attention in recent years [Perozzi et al., 2014; Tang et al., 2015b; Cao et al., 2015; Grover and Leskovec, 2016].

∗Corresponding author: sms@tsinghua.edu.cn

In this paper, we summarize most existing NRL methods into a unified two-step framework, including proximity matrix construction and dimension reduction. The first step builds a proximity matrix M where each entry Mij encodes the proximity information between vertex i and j. The second step reduces the dimension of the proximity matrix to obtain network embeddings. Different NRL methods employ various dimension reduction algorithms such as eigenvector computation and SVD decomposition. Our analysis of the first step, i.e. proximity matrix construction, shows that the quality of network embeddings can be improved when higher order proximities are encoded into the proximity matrix.

However, an accurate computation of high-order proximities is time-consuming and thus not scalable for large-scale networks. Thus we can only approximate higher order proximity matrix for learning better network embeddings. In order to be more efficient, we also seek to use the network representations which encode the information of lower order proximities as our basis to avoid repeated computations. Therefore, we propose Network Embedding Update (NEU) algorithm which could be applied to any NRL methods to enhance their performances. The intuition behind is that the embeddings processed by NEU algorithm can implicitly approximate higher order proximities with a theoretical approximation bound and thus achieve better performances.

We conduct experiments on multi-label classification and link prediction tasks over three publicly available datasets to evaluate the quality of network embeddings. Experimental results show that the network embeddings learned by existing NRL methods can be improved consistently and significantly on both evaluation tasks after enhanced by NEU. Moreover, the running time of NEU takes less than 1% training time of popular NRL methods such as DeepWalk and LINE, which could be negligible.

Our main contributions are two-fold:

1) We summarize a number of existing NRL methods into a unified framework, i.e. proximity matrix construction and dimension reduction, and conclude that the quality of network embeddings can be enhanced if higher order proximities are encoded into the proximity matrix.

2) We propose NEU algorithm to improve the performances of any network embeddings learned by existing NRL algorithms. The embeddings processed by NEU can implicitly approximate higher order proximities with theoretical bound. Experimental results on multi-label classification and link prediction demonstrate the efficiency and effectiveness of our algorithm.

Related Works Here we give a brief introduction to existing NRL methods and some of which will be thoroughly analyzed in next section. Spectral Clustering [Tang and Liu, 2011] computes top-d eigenvectors of normalized Laplacian matrix as d-dimensional network embeddings. DeepWalk [Perozzi et al., 2014] employs Skip-gram [Mikolov et al., 2013] model, which is originally used in word representation learning, on random walks for NRL. LINE [Tang et al., 2015b] models first-order and second-order proximities between vertices for learning large-scale network embeddings. GraRep [Cao et al., 2015] factorizes different k-order proximity matrices and concatenates the embeddings learned from each proximity matrix. Though GraRep achieves better performance than DeepWalk and LINE, GraRep suffers heavily from inefficiency problem. Besides the above NRL methods that focus on network topology, researchers also explore algorithms to incorporate meta information, e.g. text and label information, into NRL. TADW [Yang et al., 2015] takes text information into consideration under matrix factorization framework and MMDW [Tu et al., 2016] learns semi-supervised network embeddings with maxmargin constraints between vertices from different labels. As another semi-supervised NRL method, node2vec [Grover and Leskovec, 2016] further generalizes DeepWalk with BreadthFirst Search (BFS) and Depth-First Search (DFS) on random walks. GCN [Kipf and Welling, 2017], DDRW [Li et al., 2016] and Planetoid [Yang et al., 2016] are also proposed for semi-supervised graph embeddings. SDNE [Wang et al., 2016] employs deep neural model for NRL. Other extensions include asymmetric transitivity [Ou et al., 2016], community preserving [Wang et al., 2017] and heterogenous [Tang et al., 2015a; Chang et al., 2015; Huang and Mamoulis, 2017; Xu et al., 2017; Huang et al., 2017] network embeddings. We focus on the most general case where NRL methods use only network topology in this paper.

2 Framework of Existing NRL Algorithms

In this section, we present a unified framework which can cover several representative NRL algorithms include Spectral Clustering [Tang and Liu, 2011], DeepWalk [Perozzi et al., 2014], TADW [Yang et al., 2015], LINE [Tang et al., 2015b] and GraRep [Cao et al., 2015]. First, we clarify the notations and formalize the problem of NRL. Then we introduce the concept of k-order proximity. Finally, we summarize an NRL framework based on proximity matrix factorization and show that the aforementioned NRL methods fall into the category.

Let G = (V,E) be a given network where V is vertex set and E is edge set. The task of NRL is to learn a realvalued representation rv ∈ Rd for each vertex v ∈ V where d is the embedding dimension. We assume that networks are unweighted and undirected in this paper without loss of generality and define adjacency matrix ˜ A ∈ R|V |×|V | as ˜ Aij = 1 if (vi, vj) ∈ E and ˜ Aij = 0 otherwise. Diagonal matrix D ∈ R|V |×|V | denotes the degree matrix where Dii = di represents the degree of vertex vi. A = D-1 ˜ A is normalized adjacency matrix where the summation of each row equals to 1. Similarly, we also have Laplacian matrix ˜L = D - ˜ A and normalized Laplacian matrix L = D- 1 2 ˜LD- 1 2 .

2.1 K-order Proximity

The (normalized) adjacency matrix and Laplacian matrix characterize the first-order proximity which models the local pairwise proximity between vertices. Note that each offdiagonal nonzero entry of the first-order proximity matrix corresponds to an edge in the network. However, real-world networks are always sparse which indicates that O(E) = O(V ). Therefore the first-order proximity matrix is usually very sparse and insufficient to fully model the pairwise proximity between vertices. As a result, people also explore higher order proximity to model the strength between vertices [Perozzi et al., 2014; Tang et al., 2015b; Cao et al., 2015]. For example, the second-order proximity can be characterized by the number of common neighbors between vertices. As an alternative view, the second-order proximity between vi and vj can also be modeled by the probability that a 2-step random walk from vi reaches vj. Intuitively, the probability will be large if vi and vj share many common neighbors. In the probabilistic setting based on random walk, we can easily generalize it to k-order proximity [Cao et al., 2015]: the probability that a random walk starts from vi and walks to vj with exactly k steps. Note that the normalized adjacency matrix A is the transition probability matrix of a single step random walk. Then we can compute k-step transition probability matrix as the k-order proximity matrix

where the entry Akij is the k-order proximity between vertex vi and vj.

2.2 NRL Framework

Now we have introduced the concept of k-order proximity matrix. In this subsection, we first summarize the NRL framework based on dimension reduction of a proximity matrix and then conduct a theoretical analysis to show that most existing NRL algorithms can be formalized into this framework.

We summarize NRL methods as a two-step framework:

Step 1: Proximity Matrix Construction. Compute a proximity matrix M ∈ R|V |×|V | which encodes the information of k-order proximity matrix where k = 1, 2 . . . ,K. For example, M = 1K A+ 1K A2 · · ·+ 1K AK stands for an average combination of k-order proximity matrix for k = 1, 2 . . . , K. The proximity matrix M is usually represented by a polynomial of normalized adjacency matrix A of degree K and we denote the polynomial as f(A) ∈ R|V |×|V | . Here the degree K of polynomial f(A) corresponds to the maximum order of proximities encoded in proximity matrix. Note that the storage and computation of proximity matrix M does not necessarily take O(|V |2 ) time because we only need to save and compute the nonzero entries.

Step 2: Dimension Reduction. Find network embedding matrix R ∈ R|V |×d and context embedding C ∈ R|V |×d so that the product R · C T approximates proximity matrix M. Here different algorithms may employ different distance functions to minimize the distance between M and R · C T . For example, we can naturally use the norm of matrix M - R · C T to measure the distance and minimize it.

Spectral Clustering [Tang and Liu, 2011] computes the first d eigenvectors of normalized Laplacian matrix L as ddimensional network representations. The information embedded in the eigenvectors comes from the first-order proximity matrix L. Note that the real-valued symmetric matrix L can be factorized as L = QΛQ-1 via Eigendecomposition where Λ ∈ R|V |×|V | is a diagonal matrix, Λ11 ≥ Λ22 ≥ . . .Λ|V ||V | are eigenvalues and Q ∈ R|V |×|V | is the eigenvector matrix.

We can equivalently reduce Spectral Clustering to our NRL framework by setting proximity matrix M as the firstorder proximity matrix L, network embedding R as the first d columns of eigenvector matrix Q and context embedding C T as the first d rows of ΛQ-1 .

DeepWalk [Perozzi et al., 2014] generates random walks and employs Skip-gram model for representation learning. DeepWalk learns two representations for each vertex and we denote the network embedding and context embedding as matrix R ∈ R|V |×d and C ∈ R|V |×d . As proved by [Yang et al., 2015], DeepWalk implicitly factorizes a matrix M ∈ R|V |×|V | into the product of R · C T , where

and w is the window size used in Skip-gram model. Matrix M characterizes the average of the first-order, second-order, . . . , w-order proximities. DeepWalk algorithm approximates high-order proximity by Monte Carlo sampling based on random walk generation without calculating the k-order proximity matrix directly.

To adopt DeepWalk algorithm to our two-step framework, we can simply set proximity matrix M = f(A) = A+A2+···+Aw w . Note that we omit the log operation in Eq. (2) because they yield competitive performance as reported by [Yang et al., 2015].

GraRep [Cao et al., 2015] accurately calculates k-order proximity matrix Ak for k = 1, 2 . . . ,K, computes a specific representation for each k, and concatenates these embeddings. Specifically, GraRep reduces the dimension of k-order proximity matrix Ak for k-order representation via SVD decomposition. In detail, we assume that k-order proximity matrix Ak is factorized into the product of UΣS where Σ ∈ R|V |×|V | is a diagonal matrix, Σ11 ≥ Σ22 ≥ . . . Σ|V ||V | ≥ 0 are singular values and U, S ∈ R|V |×|V | are unitary matrices. GraRep defines k-order network embedding and context embedding R{k}, C{k} ∈ R|V |×d as the first d columns of UΣ 12

and ST Σ 12 , respectively. The computation of k-order representation R{k} naturally follows our framework. However, GraRep cannot efficiently scale to large networks [Grover and Leskovec, 2016]: though the first-order proximity matrix A is sparse, a direct computation of Ak (k ≥ 2) takes O(|V |2 ) time which is unacceptable for large-scale networks.

It is straightforward that TADW [Yang et al., 2015] and LINE [Tang et al., 2015b] can also be formalized into our framework and the proofs are omitted due to space limitation.

3 Observation and ProblemFormalization

By far, we have shown five representative NRL algorithms can be formulated into our two-step framework, i.e. proximity matrix construction and dimension reduction. In this section, we focus on the first step and study how to define a good proximity matrix for NRL. The study of different dimension reduction methods, e.g. SVD decomposition, will be left as future work.

We summarize the comparisons among Spectral Clustering (SC), DeepWalk and GraRep in Table 1 and conclude the following observations.

Observation 1 Modeling higher order and accurate proximity matrix can improve the quality of network representation. In other words, NRL could benefit if we explore a polynomial proximity matrix f(A) of a higher degree.

From the development of NRL methods, we can see that DeepWalk outperforms Spectral Clustering because DeepWalk considers higher order proximity matrices and the higher order proximity matrices can provide complementary information for lower order proximity matrices. GraRep outperforms DeepWalk because GraRep accurately calculates the k-order proximity matrix rather than approximating it by Monte Carlo simulation as DeepWalk did.

Observation 2 Accurate computation of high order proximity matrix is not feasible for large-scale networks.

The major drawback of GraRep is the computation complexity of calculating the accurate k-order proximity matrix. In fact, the computation of high order proximity matrix takes O(|V |2 ) time and the time complexity of SVD decomposition also increases as k-order proximity matrix gets dense when k grows. In summary, a time complexity of O(|V |2 ) is too expensive to handle large-scale networks.

The first observation motivates us to explore higher order proximity matrix in NRL algorithm but the second observation prevents us from an accurate inference of higher order proximity matrices. Therefore we turn out to study the problem that how to learn network embeddings from approximate higher order proximity matrices efficiently. In order to be more efficient, we aim to use the network representations which encode the information of lower order proximity matrices as our basis to avoid repeated computations. We formalize our problem below.

Problem Formalization Assume that we have normalized adjacency matrix A as the first-order proximity matrix, network embedding R and context embedding C where R, C ∈ R|V |×d . Suppose that the embeddings R and C are learned by the above NRL framework which indicates that the product R · C T approximates a polynomial proximity matrix f(A) of degree K. Our goal is to learn a better representation R′ and C ′ which approximates a polynomial proximity matrix g(A) with higher degree than f(A). Also, the algorithm should be efficient in the linear time of |V |. Note that the lower bound of time complexity is O(|V |d) which is the size of embedding matrix R.

4 Approximation Algorithm

In this section, we present a simple, efficient and effective iterative updating algorithm to solve the above problem.

Method Given hyperparameter λ ∈ (0, 12 ], normalized adjacency matrix A, we update network embedding R and context embedding C as follows:

The time complexity of computing A · R and AT · C is O(|V |d) because matrix A is sparse and has O(|V |) nonzero entries. Thus the overall time complexity of one iteration of operation (3) is O(|V |d).

Recall that product of previous embedding R and C approximates polynomial proximity matrix f(A) of degree K. Now we prove that the algorithm can learn better embeddings R′ and C ′ where the product R′ · C ′T approximates a polynomial proximity matrix g(A) of degree K + 2 bounded by matrix infinite norm.

Theorem Given network and context embedding R and C, we suppose that the approximation between R·C T and proximity matrix M = f(A) is bounded by r = ||f(A) - R · C T ||∞ and f(·) is a polynomial of degree K. Then the product of updated embeddings R′ and C ′ from Eq. (3) approximates a polynomial g(A) = f (A) + 2λAf (A) + λ2A2 f (A) of degree K + 2 with approximation bound r′ = (1 + 2λ + λ2 )r ≤ 94 r.

(4)

where the second last equality replaces g(A) and f(A) - RC T by the definitions of g(A) and S and the last equality uses the fact that ||A||∞ = maxi ∑j |Aij| = 1 because the summation of each row of A equals to 1.

In our experimental settings, we assume that the weight of lower order proximities should be larger than higher order proximities because they are more directly related to the original network. Therefore, given g(A) = f(A) + 2λAf(A) + λ2A2 f(A), we have 1 ≥ 2λ ≥ λ2 > 0 which indicates that λ ∈ (0, 1 2 ]. The proof indicates that the updated embedding can implicitly approximate a polynomial g(A) of 2 more degrees within 94 times matrix infinite norm of previous embeddings. QED.

Algorithm The update Eq. (3) can be further generalized in two directions. First we can update embeddings R and C according to Eq. (5):

The time complexity is still O(|V |d) but Eq. (5) can obtain higher proximity matrix approximation than Eq. (3) in one iteration. More complex update formulas which explores further higher proximities than Eq. (5) can also be applied but we use Eq. (5) in our experiments as a cost-effective choice.

Another direction is that the update equation can be processed for T rounds to obtain higher proximity approximation. However, the approximation bound would grow exponentially as the number of rounds T grows and thus the update cannot be done infinitely. Note that the update operation of R and C are completely independent. Therefore we only need to update network embedding R for NRL. We name our algorithm as Network Embedding Update (NEU). NEU avoids an accurate computation of high-order proximity matrix but can yield network embeddings that actually approximate high-order proximities. Hence our algorithm can improve the quality of network embeddings efficiently. Intuitively, Eq. (3) and (5) allow the learned embeddings to further propagate to their neighbors. Thus proximities of longer distance between vertices will be embedded.

5 Experiments

We evaluate the qualities of network embeddings on two tasks: multi-label classification and link prediction. We perform our Network Embedding Update algorithm (NEU) over the embeddings learned by baseline methods and report both evaluation performance and running time.

5.1 Datasets

We conduct experiments on three publicly available datasets: Cora 1 [Sen et al., 2008], BlogCatalog and Flickr 2 [Tang and Liu, 2011]. We assume that all three datasets are undirected and unweighted networks.

Cora contains 2, 708 machine learning papers drawn from 7 classes and 5, 429 citation links between them. Each paper has exactly one class label. Each paper in Cora dataset also has text information denoted by a 1, 433 dimensional binary vector indicating the presence of the corresponding words.

1 http://linqs.cs.umd.edu/projects/ /projects/lbc/index.html.

2 http://socialcomputing.asu.edu/pages/ datasets.

BlogCatalog contains 10, 312 bloggers and 333, 983 social relationships between them. The labels represent the topic interests provided by the bloggers. The network has 39 labels and a blogger may have multiple labels.

Flickr contains 80, 513 users from a photo sharing website and 5, 899, 882 friendships between them. The labels represent the group membership of users. The network has 195 labels and a user may have multiple labels.

5.2 Baselines and Experimental Settings

We consider a number of baselines to demonstrate the effectiveness and robustness of NEU algorithm. For all methods and datasets, we set the embedding dimension d = 128.

Graph Factorization (GF) simply factorizes the normalized adjacency matrix A via SVD decomposition to reduce dimensions for network embeddings.

Spectral Clustering (SC) [Tang and Liu, 2011] computes the first d eigenvectors of normalized Laplacian matrix as ddimensional embeddings.

DeepWalk [Perozzi et al., 2014] has three hyperparameters besides embedding dimension d: window size w, random walk length t and walks per vertex γ. As these hyperparameters increase, the number of training samples and running time will increase. We evaluate three groups of hyperparameters of DeepWalk, i.e. a default setting of the authors' implementation DeepWalklow where w = 5, t = 40, γ = 10, the setting used in node2vec [Grover and Leskovec, 2016] DeepWalkmid where w = 10, t = 80, γ = 10 and the setting used in the original paper [Perozzi et al., 2014] DeepWalkhigh where w = 10, t = 40, γ = 80.

LINE [Tang et al., 2015b] learns two separate network representations LINE1st and LINE2nd respectively. We use default settings for all hyperparameters except the number of total training samples s = 104 |V | so that LINE has comparable running time against DeepWalkmid.

TADW [Yang et al., 2015] incorporates text information into DeepWalk and we add this baseline for Cora dataset.

node2vec [Grover and Leskovec, 2016] is a semisupervised NRL method and we use the same hyperparameter setting used in their paper: w = 10, t = 80, γ = 10. We employ a grid search over return parameter and in-out parameter p, q ∈ {0.25, 0.5, 1, 2, 4} for semi-supervised training.

GraRep [Cao et al., 2015] is only used for the smallest dataset Cora due to its inefficiency [Grover and Leskovec, 2016]. We set K = 5 and thus GraRep has 128 × 5 = 640 dimensions.

Experimental Settings For Spectral Clustering, DeepWalk, LINE, node2vec, we directly use the implementations provided by their authors. We set the hyperparameters of NEU as follows: λ1 = 0.5, λ2 = 0.25 for all three datasets, T = 3 for Cora and BlogCatalog and T = 1 for Flickr. Here λ1, λ2 are set empirically following the intuition that lower proximity matrix should have a higher weight and T is set as the maximum iteration before the performance on 10% random validation set begins to drop. In fact, we can simply set T = 1 if we have no prior knowledge of downstream tasks. The experiments are executed on a single CPU for the ease of running time comparison and the CPU type is Intel Xeon E5-2620 @ 2.0GHz.

5.3 Multi-label Classification

For multi-label classification task, we randomly select a portion of vertices as training set and leave the rest as test set. We treat network embeddings as vertex features and feed them into a one-vs-rest SVM classifier implemented by LibLinear [Fan et al., 2008] as previous works did [Tang and Liu, 2009; 2011]. We repeat the process for 10 times and report the average Macro-F1 and Micro-F1 score. Since a vertex of Cora dataset has exactly one label, we only report classification accuracy for this dataset. We normalize each dimension of network embeddings so that the L2-norm of each dimension equals to 1 before we feed the embeddings into the classifier as suggested by [Ben-Hur and Weston, 2010]. We also perform the same normalization before and after NEU. The experimental results are listed in Table 2, 3 and 4. The numbers in the brackets represent the performances of corresponding methods after processing NEU. "+0.1","+0.3","+1" and "+8" in the time column indicate the additional running time of NEU on Cora, BlogCatalog and Flickr dataset, respectively. As an illustrative example on Cora dataset, NEU takes 0.1 second and improves the classification accuracy from 78.1 to 84.4 for network embeddings learned by TADW when labeled ratio is 10%. We exclude node2vec on Flickr as node2vec failed to terminate in 24 hours on this dataset. We bold the results when NEU achieves more than 10% relative improvement. We conduct 0.05 level paired t-test and mark all entries that fail to reject the null hypothesis with ∗ .

5.4 Link Prediction

For the purpose of link prediction, we need to score each pair of vertices given their embeddings. For each pair of network embedding ri and rj, we try three scoring functions, i.e. cosine similarity ri·rj ||ri||2||rj||2 , inner product ri · rj and inverse L2-distance 1/||ri - rj||2. We use AUC value [Hanley and McNeil, 1982] which indicates the probability that the score of an unobserved link is higher than that of a nonexistent link as our evaluation metric and select the scoring function with best performance for each baseline. We remove 20% edges of Cora, 50% of BlogCatalog and Flickr as test set and use the remaining links to train network embeddings. We also add three commonly used link prediction baselines for comparison: Common Neighbors (CN), Jaccard Index and Salton Index [Salton and McGill, 1986]. We only report the best performance for DeepWalk∈{DeepWalklow, DeepWalkmid, DeepWalkhigh} and LINE∈{LINE1st, LINE2nd} and omit the results of node2vec as it only yields comparable and even worse performance than the best performed DeepWalk. The experimental results are shown in Figure 1. For each dataset, the three leftmost columns represent the traditional link prediction baselines. Then each pair of columns stands for an NRL method and its performance after NEU.

5.5 Experimental Results Analysis

We have four main observations over the experimental results of two evaluation tasks:

(1) NEU consistently and significantly improves the performance of various network embeddings using almost negligible running time on both evaluation tasks. The absolute improvements on Flickr are not as significant as that on Cora and BlogCatalog because Flickr dataset has an average degree of 147 which is much denser than Cora and BlogCatalog and thus the impact of higher order proximity information is diluted by rich first-order proximity information. But for Cora dataset where the average degree is 4, NEU has very significant improvement as high-order proximity plays an important role for sparse networks.

(2) NEU facilitates NRL method to converge fast and stably. We can see that the performances of DeepWalklow+NEU and DeepWalkmid+NEU are comparable and even better than that of DeepWalkmid and DeepWalkhigh respectively and the former ones use much less time. Also, DeepWalk encounters the overfitting problem on Cora dataset as the classification accuracy drops when hyperparameters increase. However, the performances of DeepWalk+NEU are stable and robust.

(3) NEU also works for NRL algorithms which don't follow our two-step NRL framework, i.e. node2vec. This observation demonstrates the effectiveness and robustness of NEU.

6 Conclusion

In this paper, we propose a unified NRL framework which covers a number of existing NRL methods. We analyze the first step of the framework, i.e. proximity matrix construction, compare the proximity matrices used in different NRL algorithms and conclude that we can learn better network embeddings if higher order proximities are encoded into the proximity matrix. Then we present Network Embedding Update (NEU) algorithm to improve the performance of any given network embeddings by implicitly approximating higher order proximity matrix. The running time of NEU is almost negligible and the improvement over baseline methods are consistent and significant.

Acknowledgements

This work is supported by the National 973 Program (No.2014CB340501) and the Major Project of the National Social Science Foundation of China (No.13&ZD190).