RWNE: A Scalable Random-Walk based Network Embedding Framework with Personalized Higher-order Proximity Preserved

Higher-order proximity preserved network embedding has attracted increasing attention recently. In particular, due to the superior scalability, random-walk based network embedding has also been well developed, which could efficiently explore higher-order neighborhood via multi-hop random walks. However, despite the success of current random-walk based methods, most of them are usually not expressive enough to preserve the personalized higher-order proximity and lack a straightforward objective to theoretically articulate what and how network proximity is preserved. In this paper, to address the above issues, we present a general scalable random-walk based network embedding framework, in which random walk is explicitly incorporated into a sound objective designed theoretically to preserve arbitrary higher-order proximity. Further, we introduce the random walk with restart process into the framework to naturally and effectively achieve personalized-weighted preservation of proximities of different orders. We conduct extensive experiments on several real-world networks and demonstrate that our proposed method consistently and substantially outperforms the state-of-the-art network embedding methods.


Introduction
Network embedding, which has recently attracted increasing attention in both academia and industry, is a general and fundamental technique for representing nodes of a network as vectors in a low-dimensional space Goyal and Ferrara 2018;Cai, Zheng, and Chang 2018). Such embedding vectors can then be used for a variety of network mining tasks, such as node profiling (classification and clustering) (Sen et al. 2008;, link prediction (Shi et al. 2015;Wei et al. 2017), similarity search (Sun et al. 2011;Sun et al. 2012;Zhou et al. 2017), etc.
One basic requirement of network embedding is that the learned vectors of nodes should preserve the network structures. Along with this direction, many network embedding methods are proposed to preserve the first-order proximity which expresses the local pairwise structure indicated by the observed edges between nodes (e.g., (Roweis and Saul 2000;Belkin and Niyogi 2002;Tang and Liu 2011;Ahmed et al. 2013)), or further to preserve the second-order proximity between a pair of nodes which implies the similarity be-tween their neighborhood structures (e.g., (Tang et al. 2015;. Despite their success, in recent years, more and more works (Cao, Lu, and Xu 2015;Ou et al. 2016;) have demonstrated that, besides the first-and second-order proximity directly indicated by pairwise edges, the higher-order proximity is also of tremendous importance in capturing the underlying structures of the network. First, differentorder proximities describe the network structures from different levels of scope, which give us much valuable information with different granularities. Thus, embeddings with the lower-order proximity alone do not necessarily perform best on all networks and target applications (Perozzi et al. 2017;. For example, in classification tasks with coarser-grained classes, the higher-order proximity is likely to be more helpful than lower-order proximity. Second, real-world networks are usually very sparse, with only a small number of edges observed. That is, the observed first-order proximity and even second-order proximity may not be sufficient to reflect the underlying relations between nodes (Tang et al. 2015). Therefore, to address the network sparsity issue, it is also very important to incorporate higherorder proximity to capture more available information.
Although many works have been recently proposed to preserve the higher-order proximity in network embedding, most of them are developed to explicitly exploit the higherorder proximity matrix by the technique of matrix factorization (e.g., (Cao, Lu, and Xu 2015;Ou et al. 2016;) or deep learning (e.g., Cao, Lu, and Xu 2016)), which are known to have scalability issues when dealing with large-scale networks . In order to be more efficient, inspired by the Skipgram algorithm (Mikolov et al. 2013), random walk based network embedding algorithms have also been well developed (Perozzi, Al-Rfou, and Skiena 2014;Tang et al. 2015;Grover and Leskovec 2016;Perozzi et al. 2017). In general, these algorithms use a two-step approach to generate nodes embeddings. First, they perform random walks on a network to generate nodes sequences. Then they run the Skipgram algorithm over these sequences to generate nodes embeddings. Although these random walk based algorithms are known for having superior scalability for large-scale net-works and having ability for exploring higher-order neighborhood via multi-hop random walks, there are still some issues. First, they either treat different-order neighborhood equivalently (Perozzi, Al-Rfou, and Skiena 2014) which may not be expressive enough to incorporate a personalized combination of proximities of different orders, or use a complex second-order biased random walk (Grover and Leskovec 2016) which can be costly when pre-computing its third-order transition probability hypermatrix . Second, in essence, these algorithms convert the network embedding problem as the word embedding problem by treating a node as a word and pre-generating the node "corpus" via random walks. As a consequence, they have no specific objective to articulate what and how network proximity is preserved and have no sound theory to estimate the essential role of random walk playing in network embedding, which also limits their superiority.
In this paper, to address the above issues, we present a general scalable Random Walk based Network Embedding framework (called RWNE), in which arbitrary higher-order proximity of the network can be explicitly preserved with a sound objective carefully designed to simultaneously capture both the local pairwise similarity and the global listwise equivalence between nodes. More than that, to make the framework efficient and practical for large-scale networks, we theoretically show that the above objective can be equivalently optimized by sampling the nodes via the random walk process with the probability proportional to the proximity, which clarifies why and how we can use random walks to preserve arbitrary user-specified network proximity and reversely explains what and how network proximity is preserved for an arbitrary user-specified random walk. Further, we introduce the random walk with restart process to naturally and effectively achieve personalized-weighted preservation of different-order proximities with an elegant attenuation function controlled by a personalized teleport probability. Finally, we conduct extensive experiments on six realworld networks over three classical network mining tasks: multi-label node classification, node clustering, and link reconstruction. The experimental results demonstrate that our proposed method consistently and substantially outperforms the state-of-the-art network embedding methods. To summarize, the main contributions of our work are as follows: 1. We systematically present a general scalable randomwalk based network embedding framework in which random walk is efficiently and explicitly incorporated into a sound objective designed theoretically to preserve arbitrary higher-order proximity.
2. We further introduce the random walk with restart process to practically preserve the personalized higher-order proximity which naturally weights different-order proximities with an elegant attenuation function controlled by a personalized teleport probability.
3. We conduct extensive experiments on several real-world networks and demonstrate that our proposed model consistently and considerably outperforms the state-of-the-art network embedding methods.

Related Work
Network embedding has aroused lots of research interest. The earlier network embedding algorithms, also called graph embedding, are studied as a dimension reduction problem, such as LLE (Roweis and Saul 2000), Laplacian eigenmaps (Belkin and Niyogi 2003), etc. These methods focus on the first-order proximity which models the local structure of the network. Recently, to sufficiently explore the network structure from different levels of scope, a bunch of methods have been proposed to preserve the higher-order proximity in network embedding. Most of these methods are proposed to explicitly factorize a higher-order proximity matrix, such as GraRep (Cao, Lu, and Xu 2015), HOPE (Ou et al. 2016), M-NMF , NetMF (Qiu et al. 2018), AROPE , etc. However, in principle, as the computation and storage of higher-order proximity matrices are generally at least O(|V| 2 ) complexity, these matrix-factorization methods often have efficiency issues when dealing with large-scale networks. Besides, deep learning is also studied in preserving higher-order proximity. For example, SDNE  first applies a deep auto-encoder to preserve both 1stand 2ndorder proximity. DNGR (Cao, Lu, and Xu 2016) further uses a stacked denoising auto-encoder to preserve higherorder proximity. Unfortunately, same as matrix-factorization methods, these methods also confront efficiency issues. Specially, deep convolution networks are popularly applied on graphs in very recent years (e.g. GCN (Kipf and Welling 2017) and GAT (Velickovic et al. 2018)), which are studied as supervised/semi-supervised feature learning models with node attributes/features incorporated. We also compare with these methods, but it is noteworthy that in this paper we focus on the most fundamental case that only the network structure information is available.
On the other hand, due to the superior scalability, randomwalk based network embedding algorithms have also been well developed. In general, these algorithms use a twostep framework to generate node embeddings: first perform random walks on a network to generate nodes sequences and then run the Skipgram algorithm (Mikolov et al. 2013) over these sequences to generate nodes embeddings. For example, DeepWalk (Perozzi, Al-Rfou, and Skiena 2014) uses uniform random walks to generate node sequences and then runs the Skip-gram algorithm. Node2vec (Grover and Leskovec 2016) further generalizes a second-order biased random walk to seek a trade-off between breadth-first and depth-first graph searches. Despite their success, as introduced in Section 1, there are still some issues. In this paper, instead of the above two-step framework, we focus on a straightforward framework by explicitly incorporating random walk into a sound objective designed theoretically to preserve personalized higher-order proximity.

Problem Formulation
We formulate the normalized adjacency matrix (denoted as A) as the first-order proximity matrix, which captures the direct neighbor relations between nodes (Tang et al. 2015;. Specially, such first-order proximity can be alternatively viewed as the transition probability of a single step of random walk over the network. Then, in the probabilistic setting based on random walk, we can easily generalize it to kth-order proximity A k (Cao, Lu, and Xu 2015): the transition probability of a random walk with exactly k steps, which represents the k-hop relations between nodes. As proximities of different orders explore the relations from different levels of scope, which all can provide valuable information to guide the embedding, a desirable embedding model for real-world networks must be capable of preserving a delicate integrated higher-order proximity which combining the proximities of different orders as follows: where β k is the weight to control the prestige of kth-order proximity A k , and the sum of all weights In the rest of this section, we will systematically present a general scalable random-walk based network embedding framework, called RWNE, which is able to effectively and efficiently preserve the above integrated higher-order proximity. Without loss of generality, we first describe the RWNE model to directly preserve a general form of higher-order proximity D with arbitrary weights. Then, we show a superior optimization with random-walk simulation, which makes the model computationally efficient and scalable for large-scale networks. We further introduce the random walk with restart process to naturally adjust the prestiges of different-order proximities by a personalized teleport probability. Finally, we briefly analyze the time complexity of RWNE.

Preserving Higher-order Proximity
Local Pairwise Similarity. Given a higher-order proximity matrix D integrating all orders from the 1-st to the k-th (as defined in Eq. (1)), it is straightforward that each entry D ij implies the local pairwise similarity between each pair of nodes (v i , v j ) in view of the integrated relation from different levels of scope (from 1-hop to k-hop). If D ij > 0, there is a similarity between v i and v j , and the larger D ij is, the more similar v i and v j are; If D ij = 0, they have no similarity. Therefore, we can directly use each entry D ij to constrain the similarity of the embedding vectors of each pair of nodes (v i , v j ). Before that, we first define a normalized cosine distance as follows, which is used to measure the similarity of the embedding vectors: where v i is the embedding vector of node v i . Then, instead of a naive treatment which rigidly sets D ij as the target similarity and minimizes the error loss between D ij and sim(i, j), we propose a new loss to measure the similarity cost of each pair of nodes (v i , v j ) in the embedding space: There are two subtleties in our careful design of Eq. (3). First, though under normalization, one proximity may have different weight from one similarity score, which means rather than treating proximity as the exact target similarity, it can only be concluded that the larger proximity is, the more similarity is. And that is why we abandon the aforementioned naive treatment. In our design, we impose a penalty to push v i and v j embedded similarly and set D ij as the penalty coefficient to guarantee that larger proximity will incur more penalty and thus generate a stronger push to be similar. Second, there is an exception that zero proximity expresses the dissimilarity, which is essentially different from positive proximity. Thus we separate out the zero proximity and set an opposite penalty for it, i.e., impose a penalty to push v i and v j embedded dissimilarly.
Then, by using the loss of Eq.
(3) for all pairs of nodes, the objective function to preserve the local similarity is defined as follows: Minimizing Eq. (4) pushes the similarity of the embedding vectors of v i and v j towards 1 if proximity D ij is large (The larger the proximity, the stronger the push) and pushes it towards 0 if D ij = 0. As a result, we preserve the local pairwise similarity between nodes.
Global Listwise Equivalence. In addition to the local similarity, we can extract more information by considering the relative equivalence. For instance, for three nodes v i , v j , v k with D ij = D ik = D jk = 0.1, the local similarity between v i and v j may be very weak in view of the strength of D ij . However, in a relative view, we can conclude that v i and v j is equivalent in v k 's viewpoint, because they distribute the equal proximity with v k . Further, if for the listwise proximity distribution D i =(D i,1 , D i,2 , · · ·, D i,|V| ) and D j =(D j,1 , D j,2 , · · ·, D j,|V| ), v i and v j always have the above equivalence (i.e., D ik ≡D jk for ∀k=1, · · ·, |V|), we can conclude that v i and v j play an equivalent global structure role in the whole network. We refer to the above information as the global listwise equivalence. Note that some works (Tang et al. 2015) extract the similar information from first-order proximity. We differentiate them in the aspects where we provide a more definite meaning and generalize it as a basic attribute of arbitrary higher-order proximity.
To preserve the global listwise equivalence, we propose a self-supervised component: the proximity predictor Φ(·), which is a deep architecture composed of multiple nonlinear functions to predict the proximity distribution of an input node. As shown in Figure 1, for each node v i , the predictor Φ(·) uses the embedding vector v i as the input and output a |V|-dimentional distribution Φ(i) ∈ R 1×|V| , which is the predicted approximation of proximity distribution D i . Then, supervised by D i , the predictor Φ(·) is trained to make the output Φ(i) be close to D i , which means that if we pick two nodes v i and v j with similar proximity distributions (i.e. D i = D j ), the predictor Φ(·) will be trained to learn similar outputs (i.e. Φ(i) = Φ(j)) and thus to push the input embedding vector v i and v j to be similar. Therefore, by modeling the proximity in this way, we can learn similar embeddings for nodes with similar proximity distributions. That is, we capture the global listwise equivalence between nodes.  To train the predictor Φ(·), we follow the inspiration of the design in Eq. (3) which sets the target proximity as a penalty coefficient and separates zero proximity from positive proximity, and design the loss to measure the prediction cost for each node v i as follows: Note that in principle, Φ(·) can be an arbitrarily deep neural network, but as we focus on the effort of random walk in this paper, we only use a simple single-layer architecture and leave a superior trying as future work. In this setting, the proximity predictor Φ(·) is defined as: where W∈R |V|×d , V is the nodes set, d is the embedding dimensionality; σ(·) is the logistic function.
Finally, by using the loss of Eq. (5) for all nodes, the objective function to preserve the global equivalence is defined as follows: The Joint Objective. To simultaneously preserve both the local pairwise similarity and the global listwise equivalence provided by the higher-order proximity D, we jointly minimize the following objective function, which combines Eq. (4) and Eq. (7): where (i, j) =−(γ log sim(i, j) +λ log Φ(i) j ) is the loss for positive proximity, ζ(i, j)=−(γ log(1−sim(i, j))+λ log(1− Φ(i) j ) is the loss for zero proximity; γ and λ are hyperparameters to reflect user's emphasis.

Optimization with Random Walk Simulation
In practice, an accurate computation of Eq. (1) to get the higher-order proximity matrix D with k ≥ 2 is both time and space consuming. Thus it is undesirable to directly solving the objective of Eq. (8) due to the efficiency issue, especially for large-scale networks.
To address the above issue, we highlight that D is essentially an integrated probability matrix combining the transition probabilities of a random walk in 1-st, 2-nd, · · · , k-th step with corresponding weights β 1 , β 2 , · · · , β k , where each entry D ij = β 1 A ij + β 2 A 2 ij + · · · + β k A k ij represents the weighted average hitting probability from v i to v j within a k-steps random walk. Then, Without calculating Eq. (1), we can invent a k-steps "drop-out" random walk to simulate the probability matrix D: in l-th step (for ∀l = 1, 2, · · ·, k), the walker first randomly moves from the current node to an adjacent node as a normal random walk, and then randomly drops out the current-step hitting node with the dropping probability 1−β l . By this means, the expected hitting probability from v i to v j in k steps is exactly D ij . That is to say, for each node v i , the above k-steps "drop-out" random walker starting from v i hits/samples a paired node v j with the probability D ij .
In our carefully designed objective of Eq. (8), the probability D ij is delicately and theoretically arranged as a weight coefficient. Then, in the probabilistic setting, we can equivalently treat the probabilistic real weight as a binary weight by node-sampling treatment, with the sampling probability proportional to the original real weight. That is, we can eliminate the D ij in the first term of Eq. (8) by sampling nodes with the probability D ij , which can be simulated by the aforementioned k-steps "drop-out" random walks starting from v i . Furthermore, for the second term j∈{Dij=0} ζ(i, j) in Eq. (8), as the matrix D is usually very sparse with many zero entries, we also leverage an uniform-sampling treatment to optimize it. Overall, with the node-sampling treatment, the objective function of Eq. (8) is optimized as: where T is the sampling-frequency/walk-times which can be set as the iteration epochs when solving the objective by an iterative algorithm (e.g. SGD); p 1→k i is the hitting nodes set in a k-steps "drop-out" random walk starting from v i ; E j ∼I/{p 1→k i } means an uniform-sampling with nodes {p 1→k i } excluded. Note that in each walk, as the random walker samples |p 1→k i | nodes, we also operate uniform-sampling for the equal times to ensure the fairness.
The optimized objective of Eq. (10) replaces the expensive computation of higher-order proximity with random walk simulation, and thus has superior efficiency and scalability, and can be easily mini-batch-minimized by applying an iterative algorithm. So far, we have theoretically described a general scalable random walk based embedding framework. For arbitrary user-specified weights {β 1 , β 2 , · · · , β k , · · · }, the framework is able to effectively and efficiently preserve the weighted combination of different-order proximities by deploying the aforementioned "drop-out" random walk. Reversely, for arbitrary user-specified random walk, the framework can also be used by directly minimizing the Eq. (10), However, superior to other random-walk models, the framework explicitly clarifies what and how network proximity is preserved in random-walk structure, that is the average hitting/sampling probability in k steps of the user-specified random walk is just the integrated higher-order proximity which is theoretically preserved by the objective of Eq. (8).
Random Walk with Restart. Although we have theoretically described the RWNE framework, it is still limited because there is no principled way to determine desirable weights {β 1 , β 2 , · · · , β k , · · · } or random walks. In general, it is intuitive that the relation/influence over a very long distance can be very weak, i.e., the prestige of different-order proximity is likely to decay with the distance. Therefore, instead of a normal random walk widely used in the existing models, we introduce the random walk with restart (referred to as RWR) process: in each step of a random walk, the walker can return back to the root with a personalized teleport probability α. The transition probability of RWR is recurrently formalized as: where P k is the k-th step transition probability matrix of RWR, and P 0 = I is an identity matrix; A is the single-step transition probability matrix of normal random walk, i.e., the first-order proximity matrix. Equivalently, we have: Thus, by deploying the RWR process, the integrated higherorder proximity matrix to be preserved (i.e. the average hitting/sampling probability matrix) in k steps is derived as: in which the proximities of different-orders are weighted with a function β(t)= (1+α(k−t))(1−α) t k . As Figure 2 shows, β(t) is approximately an exponentially decreasing function, and the decay rate can be freely adjusted by the personalized teleport probability α.
Finally, by deploying the RWR process, RWNE is able to effectively and efficiently preserve a personalized higherorder proximity (as shown in Eq. (13)) in which the proximities of different orders are naturally weighted with an elegant attenuation function controlled by a personalized teleport probability. The final objective of RWNE by applying the RWR process is as follows: (14) where rwr 1→k i is the hitting nodes set in a k-steps random walk with restart process starting from v i .

Complexity Analysis
In this section, we discuss the time complexity of RWNE. We use iterative algorithms (e.g. mini-batch SGD) to minimize the objective function (as shown in Eq. (14)). In each iteration, we only consider a single root node and deploy a k-steps random walk (with restart) starting from it to sample  Figure 2: The decline curves of β(t) = (1+α(k−t))(1−α) t k in different α. The k is set as 100 and each curve is normalized by β(1). k paired nodes. As random walk takes only constant time in each step (even in a weighted network, we can use Alias sampling (Walker 1977) to perform a random walk in O(1) time) and the computation of the loss for each pair of nodes also takes constant time, we can see that the complexity of each iteration (i.e., the complexity of the inner-body in Eq. (14)) is O(k). Then, given the network size |V| and the iteration epochs T , we can extract that the overall time complexity of RWNE is O(kT |V|), which is linear to the number of nodes in the network. Therefore, the proposed RWNE model is computationally efficient and scalable for large-scale networks.

Experiments
In this section, we report the experimental results. Code and data will be released in the camera-ready version.

DataSets
Here we use the following six publicly available networks.
• Cora (McCallum et al. 2000): This is a citation network with 2,708 papers, 5,429 citation links, and 7 categories.
• PubMed (Kipf and Welling 2017): This is also a citation network with 19,717 nodes, 44,338 links, and 3 categories.
• Blogcatalog (Tang and Liu 2009a): This is a social network with 10,312 nodes, 333,983 links, and 39 categories.
• Flickr (Tang and Liu 2009a): This is a social network with 80,513 nodes, 5,899,882 links, and 195 categories.
• Youtube (Tang and Liu 2009b): This is a very large network with 1,138,499 nodes, 2,990,443 links and 47 labels.

Baseline Methods and Experimental Settings
We compare our RWNE model with the following random walk based (DeepWalk, LINE, Node2vec), matrix factorization based (GraRep, HOPE), and deep learning based (SDNE, GCN, GAT) network embedding methods.
• LINE (Tang et al. 2015) defines loss functions to preserve 1st-and 2nd-order proximity separately. After optimizing the loss functions, it concatenates these embeddings.
• Node2vec (Grover and Leskovec 2016) is generalized from Deepwalk by introducing a biased random walk.
• GCN (Kipf and Welling 2017) is a semi-supervised feature learning model which defines a convolution operator to directly operate graph-structured data.
• GAT (Velickovic et al. 2018) is a novel neural network architecture that operates graph-structured data by leveraging masked self-attentional layers.
We evaluate the quality of the embedding vectors learned by different methods on three classical network mining tasks: multi-label node classification, node clustering, and link reconstruction. To ensure the significance of the results, we repeat each experiment ten times and report their mean value and standard deviation value. For the common hyperparameters, we set learning-rate lr = 0.025, embeddingdimension d = 128, negative-samples m = 5, and iterationepochs T = 20000 for all methods. Specially, for Deep-Walk and Node2vec, we set walk-times wt=10, walk-length wl = 80, window-size k = 10, and set the bias parameters of Node2vec as p = q = 0.25, as recommended in their papers. For SDNE, we tune its parameters of α, β, ν by using a grid-search strategy, and get α = 10 3 , β = 10, ν = 10 −4 . For GCN and GAT, we consistently use the structural features (i.e. adjacent matrix) as the input features. For other parameters and other baselines, we use the default settings as shown in their original papers. For our RWNE model, we set the loss-weight γ = 10 and λ = 1 (see in Eq. (8)), the personalized-teleport-probability α = 0.3 (see in Eq. (11)), the walk-steps (walk-length) k =10 (see in Eq. (14)). Note that the walk-steps k in our model actually delimits an upper bound of the order to be preserved which shares the similar meaning with the window-size in DeepWalk and Node2vec.

Multi-label Node Classification
For the node classification task, we first learn the node embedding vectors from the full nodes on each dataset, and then use the embedding vectors as input features for a one-vs-rest logistic regression classifier, and use both Macro-F1 score and Micro-F1 score as the metrics for evaluation. We repeat each classification experiment ten times and randomly split 50% of the nodes for training and the other 50% for testing, and report both the mean value and the standard deviation value. Due to the lack of space, we report the mean Macro/Micro-F1 scores in Table 1 and Table 2, and report the standard deviations in the supplementary material. Note that we exclude the results of some models on the Youtube dataset because they either fail to terminate in one week (SDNE) or run out of memory (GraRep, HOPE, GCN, GAT). We can observe that our proposed RWNE model consistently and significantly outperforms all the state-of-theart baselines in both metrics on all datasets. For example, on the Cora dataset, RWNE outperforms all baseline models by 0.03-0.22 (relatively 4%-35%) in terms of Macro-F1 score and by 0.03-0.08 (relatively 4%-11%) in terms of Micro-F1 score; On the BlogCatalog dataset with larger size, RWNE also achieves the gains of 0.03-0.16 (relatively 12%-109%) in Macro-F1 score and 0.02-0.19 (relatively 7%-78%) in Micro-F1 score. Specially, by only taking random-walk based methods (DeepWalk, LINE, Node2vec) into account, we can find that RWNE also consistently improves the classification performance by around 0.02-0.08 in both metric scores on all datasets.
More generally, we can find that, by deploying sufficient long-distance random walks, random walk based algorithms (DeepWalk, Node2vec, and our RWNE) can achieve considerable improvements than matrix factorization based and  deep learning based algorithms, especially on the large-scale datasets. Besides, it is worth mentioning that by using the adjacent matrix as the input features, the semi-supervised feature learning models (GCN, GAT) show worse performance than expected, which implies that these models may not be suitable to exploit a graph with poor attribute features.

Node Clustering
For the node clustering task, we use the embedding vectors as the input to a k-means cluster and evaluate the performance in terms of NMI (Normalized Mutual Information) score. And also, all the experiments are conducted ten times, and the mean NMI scores are shown in Table 3, and the standard deviations are shown in the supplementary material.
Overall, the results of node clustering are consistent with the results of node classification, and we can reach a similar conclusion as analyzed in Section 4.3. We can see that the proposed RWNE model consistently and clearly outperforms all the comparative baselines on all datasets. For example, on the Cora dataset, RWNE improves the NMI score by 0.02-0.12 (relatively 5%-33%) over random walk based models, and by 0.05-0.17 (relatively 12%-57%) over other baseline models. On the BlogCatalog dataset, RWNE improves the NMI score by around 0.02-0.03 (relatively 9%-17%) over random walk based models, and by around 0.03-0.08 (relatively 15%-72%) over other baseline models.

Link Reconstruction
For the link reconstruction task , we rank pairs of nodes according to their similarities, i.e. the inner product of two embedding vectors, and then reconstruct/predict the links for the highest ranking pairs of nodes. We use the MAP (Mean Average Precision) metric (Goyal and Ferrara 2018) to estimate the reconstruct precision. Also, all the experiments are conducted ten times, and the mean MAP scores are shown in Table 4, and the standard deviations are shown in the supplementary material.
We can observe that the results of link reconstruction are also consistent with the results of node classification and node clustering, and we can draw similar conclusions. Overall, in terms of the MAP scores on all the six datasets, the proposed RWNE consistently and substantially achieves around 0.02-0.07 improvements over DeepWalk and Node2vec, and around 0.05-0.27 gains over other baselines.

Parameter Sensitivity
In our model, there exist four important parameters: walksteps k, personalized teleport probability α, and loss weight γ and λ. In this section, we illustrate these parameters sensitivity by the Macro-F1 scores of node classification experiments on the Blogcatalog dataset. For each experiment, we vary one parameter and fix the others as the default values (as shown in Section 4.2). The results are shown in Figure 3. From Figure 3(a), we can see that the performance is soaring when k<10 while it shows a slight decline trend when k>10, which reveals that it is beneficial to capture the proximity within an appropriate level of scope. From Figure 3(b), we can observe that the model achieves the best performance when α reaches around 0.3, which clearly proves the necessity and effectiveness of random walk with restart process. In addition, Figure 3(c) and Figure 3(d) show the effects of varying the weight γ and λ. We can observe that it is worthwhile to jointly preserve the local similarity and global equivalence with suitable weights (e.g., γ = 10 and λ = 1).

Case Study: Scalability
As analyzed in Section 3.4, the proposed RWNE model has superior scalability with a linear complexity. In this section, we further experimentally verify the scalability of RWNE. We first generate a series of random graphs with different sizes of [1k; 10k; 100k; 1000k; 10000k], and then apply our method to these synthetic networks to learn node embeddings. The time consumption is shown in Figure 4. We can see that the running time grows linearly with the number of nodes, which demonstrates that our method is efficient and scalable for large-scale networks.
In this paper, we present a general scalable random walk based network embedding framework. Distinguishing from existing random-walk based methods, we systematically design a sound objective to explicitly preserve arbitrary higherorder proximity and then equivalently optimize it by random walk simulation. As a result, the random walk is theoretically incorporated into the objective function, which explicitly clarifies the essential role of random walk playing in higher-order proximity preserved network embedding. Further, we also introduce the random walk with restart process to naturally and effectively weight the proximities of different orders by a personalized teleport probability. We conduct extensive experiments on several datasets and the results demonstrate the superiority of our model.