Dynamic Network Embedding : An Extended Approach for Skip-gram based Network Embedding

1 Introduction

Network embedding, as an approach to learn lowdimensional representations of vertices, has been proved extremely useful in many applications [Hamilton et al., 2017]. As the input of machine learning models, the lowdimensional features help to complete specific tasks efficiently, such as vertex classification, clustering, graph visualization, link prediction and social influence analysis [He et al., 2012; Song et al., 2015].

Network embedding can be categorized into the structurepreserving methods and property-preserving methods [Cui et al., 2017]. Our paper belongs to the former. In terms of the static network embedding, some of them are based on matrix factorization [Belkin and Niyogi, 2001]. Some are based on a deep autoencoder [Wang et al., 2016; Cao et al., 2016]. Other important methods [Perozzi et al., 2014; Grover and Leskovec, 2016; Tang et al., 2015; Cao et al., 2015] are inspired by skip-gram in word2vec [Mikolov et al., 2013]. They are more efficient than the former ones, and also have good performance.

∗These authors contributed equally to the work.

†Corresponding Author

However, there is nothing permanent except change. Many real-world networks are not static but are continuously evolving, especially social networks, such as a new user joins the network as an unseen vertex, or two users make friends as a new link in the network. With the evolvement of networks, the representations of vertices become stale and need to be updated to keep freshness. Naive dynamic network embedding methods apply static embedding algorithms to each snapshot of the dynamic networks, which may lead to the following unsatisfactory situations: one is the retrained embedding spaces will drift and it is hard to align. The other is the time complexity of training increases linearly with the number of vertices in networks. Actually, a network may not change much during a short time in dynamic situations, thus the embedding spaces should not change too much, and retraining is not necessary as well.

There are few researches on dynamic network embedding currently [Zhu et al., 2018; Zhang et al., 2017; Ma et al., 2018], which can be categorized into structure preserving and property preserving. Among the former ones, [Tang et al., 2015; Perozzi et al., 2014] are skip-gram based methods designed for static networks, which introduce a way to obtain the vector representations of new vertices briefly. But they can't handle the complicated situations in dynamic settings, e.g. the removal of vertices, the addition and removal of edges, and the update of edge weights. Another type of dynamic network embedding methods is preserving attributes [Li et al., 2017; Hamilton et al., 2017]. For example, SAGE can generalize the vertex representations efficiently with the neighbor feature information based on a general inductive framework. Meanwhile, it can also handle the network only with structural information. Actually, the performance of SAGE is inferior to models based on skip-gram framework in plain network only with structural information.

Considering the outstanding performance of Skip-gram based network embedding (SGNE) methods, we hope to extend the SGNE methods to dynamic setting and keep the optimality of the objective in theory. The dynamic changes of networks are complex, including the addition and removal of vertices and edges, and the update of edge weights. It's challenging to design a framework for all these changes. Secondly, in order to improve efficiency, only the most affected vertices should be updated. Sometimes, the nearest vertices from the new vertex are not always the most affected vertices. So how to measure the influence on the representations of vertices is also a challenge. Thirdly, when the network has great changes, it's challenging to keep the accuracy of network embedding from decreasing obviously.

In this paper, we propose an efficient and stable embedding framework for dynamic networks. It is an extension of the network embedding methods based on skip-gram in a dynamic setting. All SGNE methods are applicable to our framework and achieve the optimal solution of retraining theoretically. In this paper, we apply our framework to extend LINE into dynamic settings as an example. Besides, our model can also be applied to multiple dynamic changes and keep the learning effect when the dynamic network changes a lot.

In details, we divide the dynamic network embedding into two tasks: calculating the representations of new vertices and adjusting the representations of original vertices that are affected greatly. Due to the changes of dynamic network at each time step is small comparing with the network size, we hope to learn new vertices and only update the representations of a part of vertices to improve the efficiency. Therefore, we firstly propose a decomposable objective equivalent to the Skip-gram objective, which can learn the representation of each vertex separately. Secondly, we analyze the influence of dynamic network changes on the original vertex representations quantificationally. A selection mechanism is proposed to choose the original vertices affected greatly and update the representations of them. In addition, through smooth regularization, our model ensures the stability of the embedding results.

To summarize, we make the following contributions:

• We propose Dynamic Network Embedding (DNE), an extended dynamic network embedding framework for Skip-gram based network embedding methods, which can approximately achieve the performance of retraining more efficiently.
• We present a decomposable objective which can learn the representation of each vertex separately. In theory, we quantitatively analyze the degree of impact on original vertices during the network evolvement, and propose a selection mechanism to select the greatly affected vertices to update.
• We conduct extensive experiments on four real networks to validate the effectiveness of our model in vertex classification and network layout. The results demonstrate that DNE can approximately achieve the performance of LINE retraining, and it is about 4 times faster than LINE. Besides, DNE shows strong layout stability.

2 RelatedWork

Static Network Embedding Network embedding can be categorized into structure-preserving methods [Henderson et al., 2012; Ribeiro et al., 2017] and property-preserving methods [Li et al., 2015; Kipf and Welling, 2016] . Inspired by the skip-gram in word2vec [Mikolov et al., 2013], some approaches represent a node with its nearby nodes. Deepwalk [Perozzi et al., 2014] generalizes the word embedding and employs a truncated random walk to learn latent representations of a network. LINE [Tang et al., 2015] designs an optimized objective function to preserve first-order and secondorder proximities to learn network representations. Besides the structure-preserving, many property-preserving works [Li et al., 2017] specialize to design for attributes network. However, all the aforementioned methods are designed for the static network embedding specially.

Dynamic Network Embedding Similar to the static network embedding, the dynamic network embedding can also be categorized into structure-preserving methods and property-preserving methods. Actually, DeepWalk [Perozzi et al., 2014] LINE [Tang et al., 2015] can also be regarded as a structure-preserving dynamic network embedding. The two methods handle new vertices based on static embedding. But the new vertices do not update the original vertices and the relationship among the new vertices will not be preserved into the representations. [Zhou et al., 2018] focuses on mining the pattern of network evolvement to predicts whether there will be a link between two vertices at the next time step. But it can't handle the addition of vertices. In term of property-preserving dynamic network embedding, SAGE [Hamilton et al., 2017] proposes a inductive method to learn the projection between the node features and the node representations. But the parameters in the model are fixed after training, which greatly limits the scalability of the model. Besides, it is proved in the paper that the model is still structurepreserving when dealing with high-dimensional embeddings. But our experiments show that its ability of preserving structure is inferior to our skip-gram based structure-preserving framework.

3 ProblemDefinition and Analysis

3.1 ProblemDefinition

Definition 1 (Dynamic Network). A dynamic network G is a sequence of network snapshots within a time interval and evolving over time: G = (G1, ...,GT ). Each Gτ = (Vτ ,Eτ) ∈ G is a weighted and directed network snapshot recorded at time τ, where Vτ is the set of vertices and Eτ is the set of edges within the time interval τ. Each edge (i, j) ∈ Eτ is associated with a weight wij > 0. For each (i, j) /∈ Eτ , wij is set to 0.

As undirected networks and unweighted networks are special cases of the network we defined, they are included in our problem definition. In addition, ∆Gτ = (∆Vτ ,∆Eτ) denotes the change of the whole network, where ∆Vτ and ∆Eτ are the sets of the vertices and edges to be added (or removed) at time τ . According to the definition of dynamic network, we define the dynamic network embedding:

Definition 2 (Dynamic Network Embedding). Given a dynamic network G, the dynamic network embedding is a sequence of functions Φ = (Φ1, ..., ΦT ), where each function

Φτ ∈ Φ is Vτ → Rd (d ≪ minτ |Vτ |) which can preserve the structure property of Gτ .

Since we focus on the vector representations of vertices, the dynamic embedding process can be divided into two parts, the learning of the representations of the new vertices and the adjustment of the original ones. All situations of dynamic changes mentioned above will influence the representations of original vertices, while only the addition of new vertices needs to learn new vectors. In our framework, other changes are considered as a special case of adding vertices. The addition of vertices is introduced as the example of our model, and how to handle other situations will be presented briefly later.

3.2 Analysis

Our method is an extended framework for the Skip-gram network embedding (SGNE) methods in a dynamic setting. We firstly generalize about the main idea of SGNE. Since we use LINE as an example of SGNE to introduce our method, the objective of LINE [Tang et al., 2015] is introduced secondly.

Main Idea of SGNE The SGNE methods are to learn useful vertex representations for predicting the neighbor vertices. Thus, they have the same essential objective that is to maximize the log probability:

where NS(vi) is the neighbor set of vi and p(vj|vi) is modeled using Softmax. Different methods have different definitions of neighbour set NS. Among several SGNE methods, the neighborhood definition of LINE is the most direct. So we use LINE as an example to introduce our model, and we will also present how other methods are applied to our model later.

Objective of LINE In LINE, the neighborhood definition of the vertex vi is direct, namely, NS(vi) = {vj|(i, j) ∈ E}. LINE introduces two definitions of objectives. One of them, LINE with Second-order Proximity (LINE-SP), is based on Skip-gram which we mainly talk about.

LINE-SP learns the vertex representations to preserve the similarity between the neighborhood network structures of vertex pairs. The objective is defined as:

where, σ(·) = 1/(1+e-x ) is the sigmoid function, wij is the weight of the edge (i, j), ⃗ui is the representation of vi when it is treated as a central vertex and ⃗ci is the representation of vi when it is treated as a specific "context" (i.e a specific successor vertex). Pn(v) ∝ dαv is the noise distribution for negative sampling, where dv is the out-degree of the vertex v and α is a hyper parameter which is set to 3/4 in LINE.

In our model, we have two adjustments regarding the dαv . To facilitate the theoretical proof, we set α = 1, the same as the setting of [Levy and Goldberg, 2014]. In fact, sampling according to P 3/4 produces somewhat superior results on some of the semantic evaluation tasks [Levy and Goldberg, 2014] and it has not been proved to have a better effect in the network representation. The other one is that we set dv to the in-degree of v instead of the out-degree. As the meaning of Pn(v) is the probability of a vertex to be sampled as a negative sample when v is a specific successor node, we believe the in-degree is a better choice.

4 Dynamic Network EmbeddingModel

In this section, we firstly propose a decomposable objective equivalent to the objective of LINE (Eq.(2)), which can be optimized for ⃗ui, ⃗ci on the basis that the representations of most vertices don't need to be adjusted. Based on the objective, we secondly introduce a method to learn the representations of new vertices. Thirdly, we present an embedding adjustment mechanism for original vertices, analyzing the influence of the dynamic changes on original vertices quantitatively. Finally, we discuss the applicability of the framework on other SGNE methods, and to deal with other dynamic changes of the network.

4.1 Decomposable Objective Equivalent to LINE

The objective of LINE-SP Eq.(2) can not decompose into local objective for ⃗ui and ⃗ci simultaneously. We give the decomposable objective:

where, µ is an arbitrary real number between 0 and 1. Pin(v) ∝ d(in) v and Pout(v) ∝ d(out) v are the noise distributions for negative sampling, where d(in) i is the in-degree of vertex vi and d(out) i is the out-degree of vertex vi, i.e. d(in) i = ∑j wji and d(out) i = ∑j wij.

Lemma 1. For any real number µ ∈ [0, 1], the objective Eq.(3) is equivalent to Eq.(2), i.e.the objective of LINE-SP.

Proof. According to the wij = 0 for any (i, j) /∈ E, Eq.(2) can be rewritten:

where the expectation term can be explicitly expressed:

where D = ∑(i,j)∈E wij .

We focus on the latter term of Eq.(4):

Combine Eq.(4) and Eq.(5):

Thus, the lemma has been proved.

The objective can decompose on ⃗w when µ is set to 1:

and the objective can decompose on ⃗c, when µ is set to 0:

[Levy and Goldberg, 2014] derives the theoretical optimal solution of Skip-gram with negative sampling. Based on the work, we give the theoretical optimal solution of LINE-SP:

It shows that the optimal solution is for the inner product ⃗cj ·⃗ui of the vertex pairs rather than every specific ⃗ui and ⃗cj. Thus, with a fixed ⃗ui (or ⃗cj ), we can optimize the objective only for ⃗cj (or ⃗ui), which makes ⃗cj · ⃗ui tend to xij.

4.2 NewVertex Representation

We discuss the situation of adding several vertices at time τ. For the new vertices, their edges can be categorized into three types. For any edges (i, j) ∈ ∆Eτ : ∆E(1) τ = {(i, j)|vi ∈ ∆Vτ ∧ vj ∈ ∆Vτ},∆E(2) τ = {(i, j)|vi ∈ ∆Vτ ∧ vj /∈ ∆Vτ }, ∆E(3) τ = {(i, j)|vi /∈ ∆Vτ ∧ vj ∈ ∆Vτ}. They correspond to different values of µ in the objective: 12 , 1 or 0. Thus, the objective for new vertices is defined as:

where,

where ⃗u (τ ) i ,⃗c (τ) i is the vector representations of vi at time τ. τn equals to τ when vn ∈ ∆Vτ , otherwise τn equals to τ -1. It shows that the objective only learns the vector representations of the new vertices, but doesn't adjust the original ones.

4.3 Adjustment of Original Vertex Representation

Generally, for a dynamic change in the network, a few vertices will be influenced. Therefore, in order to improve the efficiency, we don't have to adjust the representations of all vertices. We only adjust the vertices influenced greatly. We analyze theoretically the changes of the optimal solution for the original vertex representations when the network changes dynamically.

Based on the Eq.(6), we can calculate the delta of the theoretical optimal solution ∆xij between two snapshots. When a new vertex v∗ is added at time τ , the delta is

In reality, we are unable to obtain the optimal solution. Therefore, we give the standard to justify whether vi should be adjusted combing the edge weights:

where x(τ) ij is calculated according to Eq.(6) and Z (τ-1) i is a normalization factor, i.e. Z (τ-1) i = ∑j∈N (τ-1) out (vi) wij + ∑j∈N (τ-1) in (vi) wji.

We adjust the top m original vertices with the largest ϵi. For the original vertices needed to be adjusted, we add them into ∆Gτ with their edges, and adopt the objective Eq.(7) to learn them.To guarantee the stability of original vertex representations, we introduce a smooth regularization term.

The overall objective is defined as:

where,

We adopt Adam optimizer [Rushing et al., 2005] to optimize the objective. The computational complexity of our model is the same as LINE in each batch, if the sizes of mini-batch are the same. But the number of parameters in our model is O(|∆V |), while in LINE it's O(|V |). So the convergence speed of our model is faster than LINE.

4.4 Applicability Analysis

Various Dynamic Changes For any type of dynamic change within the interval τ , we have two networks Gτ-1 and Gτ . According to the two networks, we first calculate two theoretical optimal solutions xτ-1 ij and xτij by Eq.(6). Next, the impact degree ϵi of each vertices vi is obtained by Eq.(8). Finally, we optimize the objective Eq.(9) to adjust the top m original vertices with the largest ϵi. These steps above is suitable for all dynamic changes.

Various SGNE Methods Other Skip-gram based network embedding methods can be extended to dynamic setting with the framework of DNE. The main difference among these methods is the definition of the vertex neighborhood NS(v). Based on NS(v), we define ES = {(i, j)|vj ∈ NS(vi)}. In order to extend these method with the help of our approach, we replace E in the aforementioned equations (in section 4) with ES. When new vertices arrive, we first obtain the neighborhoods of the new vertices and the affected ones, and then we optimize the objective Eq.(9) to learn the representations of these vertices.

5 Experiments

In this section, we evaluate our model in the dynamic setting from three aspects: the performance on the multi-class vertices classification, the time cost and the embedding stability. Experimental analyses are presented as follows.

5.1 Experiment Setup

Data Sets We employed the following three real datasets in Facebook social networks [Traud et al., 2012] for vertex classification, which comprises 100 colleges and universities in US. We choose the social networks in Amherst College (2235nodes, 90954edges), Duke University (9895nodes, 506443edges) and Auburn University (18448nodes, 973918edges). Besides, in order to validate the embedding stability of our model, Karate [Zachary, 1977] are applied to visualize the network.

Next, we introduce how to generate a sequence of network snapshots (G1, ..., GT ) from the original network. The initial network G1 is a sub-network sampling from the original network. Each time step τ , Gτ can be obtained by adding a fixed size of new vertices and edges to Gτ-1

Compared Methods We compared the DNE against the following three network embedding algorithms:

• LINE [Tang et al., 2015]. A static network embedding method which optimizes a carefully designed objective function to preserve the local and global network structures. In dynamic scenarios, as the representative of the static embedding method, LINE can be retrained for new vertices. In this paper, LINE with second-order proximity is employed in experiment.
• LINE for New Vertices (LINE-NV) [Tang et al., 2015]. A simply extended method on LINE for new vertices through updating the embedding of the new vertex and keeping the embeddings of existing vertices.
• GraphSAGE [Hamilton et al., 2017]. A general inductive framework of the dynamic network embedding that leverages vertex feature information (e.g. text attributes) to efficiently generate vertex embeddings for previously unseen data. Besides, GraphSAGE is capable of maintaining modest performance by leveraging graph structure, even with completely random feature inputs.

Parameters Settings For fair comparison, the parameters settings of all models in experiments are consistent. The dimensionality of embeddings is set to 20 for classification and 2 for visualization. The mini-batch size of the stochastic gradient descent is set as 300. The learning rate is set as 0.003. There are some special parameters in DNE: the number of original vertices that need to be updated at each time step is set as 10. Other special parameters settings for SAGE follows the recommended settings in the relevant code package 1 .

5.2 Vertex Classification

In order to verify the effectiveness of DNE, we employ three real social networks to validate the accuracy of vertex classification and time cost. The learned representations are used to classify the vertices into a set of labels. The classifier we used is Logistic Regression with sklearn package, and the evaluation metric is Accuracy. For all models, the size of network at the first snapshot (i.e. the initial network G1) is set to 200 nodes for Duke and Auburn, 500 nodes for Amherst. The number of new arriving nodes at each snapshot is set to 200. The dimensionality of embeddings is set to 20. The results are averaged over 10 different runs.

Fig.1 illustrates the effect of number of snapshots on the vertex classification and the average time cost on every snapshot. In terms of accuracy, it can be seen from the Fig.1 that the performance of our model DNE almost keeps up with LINE. Obviously, since LINE-NV does not update the original vertices during the network evolvement, the performance of the model is unstable and inferior to DNE and LINE. Besides, the experiment results illustrate that SAGE is weak in structure preservation. In terms of time cost, since the LINENV does not refresh the original vertex embeddings during the evolvement of the network, LINE-NV is the fastest. Compared with LINE, fewer parameters and faster convergence make DNE several times faster than LINE. Compared with DNE LINE LINE-NV SAGE

1 https://github.com/williamleif/GraphSAGE

(c) The comparison of vertex classification accuracy and time cost of different models on the Auburn dataset

Figure 1: The performance comparison of vertex classification on three real networks. For each sub-graph, the left is the effect of number of snapshots on the vertex classification, and the right is the average time cost on each snapshot.

SAGE, it can be found that the time cost of DNE will be more stable, especially when the network becomes larger and larger. This is because the sampling strategy of SAGE will lead more and more original vertices need to be updated while the network is becoming larger and larger. However, DNE presents an embedding adjustment mechanism for original vertices to adjust the top m original vertices. In general, our model performs better, especially in the large-scale network.

5.3 Network Layouts

Network layout is an important application of network embedding which projects a network into two-dimensional space. Especially, in dynamic scenarios, layout stability is an important and challenging problem. The embedding of networks at consecutive time steps should not differ too much when the networks do not change much.

In this experiment, the Karate data set with 34 nodes is generated into a sequence of three network snapshots G = (G1,G2,G3), where G1 is initialized as a network with 10

nodes, and 12 nodes are added into G at each snapshot. In order to evaluate the layout stability of models, G are embedded into 2-dimensional space. Besides, we track four point (0, 2, 6, 9), which can be seen in Fig.2, to observe their positions at different snapshots. From the visualization, LINE, as the representative of the static embedding method, appears obvious embedding space drift. Our model DNE is superior to other two models, because just the most affected m nodes will be updated at each snapshot.

6 Conclusion

We propose an efficient and stable embedding framework for dynamic networks, which is an extension of SGNE methods in a dynamic setting. On three real social networks, we validate the effect of our model in vertex classification. We can achieve the approximate performance as retraining and DNE are obviously more efficient. Besides, DNE shows strong layout stability. The idea that we propose to extend the static method in dynamic setting is a general method. A particularly interesting direction for future work is to extend other static network embedding methods in dynamic setting based on our idea.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (Grant No. 61572041).