DynWalks: Global Topology and Recent Changes Awareness Dynamic Network Embedding
Chengbin Hou Han Zhang Ke Tang Shan He
cs.SI cs.LG physics.soc-ph


SVD-Aided Multi-Beam Directional Modulation Scheme Based on Frequency Diverse Array
    Qian Cheng, Student Member, IEEE,
        Vincent Fusco, Fellow, IEEE,
        Jiang Zhu, Member, IEEE,
        Shilian Wang, Member, IEEE,
        and Chao Gu
This work was supported by a scholarship (No. 201803170247) from China Scholarship Council (CSC). (Corresponding author: Shilian Wang.)
Q. Cheng is with the College of Electronic Science, National University of Defense Technology, Changsha 410073, China, and also with the ECIT Institute, Queen's University Belfast, Belfast BT3 9DT, UK. (e-mail: chengqian14a@nudt.edu.cn)
J. Zhu and S. Wang are with the College of Electronic Science, National University of Defense Technology, Changsha 410073, China (e-mail: {jiangzhu, wangsl}@nudt.edu.cn).
V. Fusco and C. Gu are with the ECIT Institute, Queen's University Belfast, Belfast BT3 9DT, UK (e-mail: v.fusco@ecit.qub.ac.uk; chao.gu@qub.ac.uk).

    December 30, 2023
=========================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================




Learning topological representation of a network in dynamic environments has recently attracted considerable attention due to the time-evolving nature of many real-world networks i.e. nodes/links might be added/removed as time goes on. Dynamic network embedding aims to learn low dimensional embeddings for unseen and seen nodes by using any currently available snapshots of a dynamic network. For seen nodes, the existing methods either treat them equally important or focus on the k most affected nodes at each time step. However, the former solution is time-consuming, and the later solution that relies on incoming changes may lose the global topology—an important feature for downstream tasks. To address these challenges, we propose a dynamic network embedding method called DynWalks, which includes two key components: 1) An online network embedding framework that can dynamically and efficiently learn embeddings based on the selected nodes; 2) A novel online node selecting scheme that offers the flexible choices to balance global topology and recent changes, as well as to fulfill the real-time constraint if needed. The empirical studies on six real-world dynamic networks under three different slicing ways show that DynWalks significantly outperforms the state-of-the-art methods in graph reconstruction tasks, and obtains comparable results in link prediction tasks. Furthermore, the wall-clock time and complexity analysis demonstrate its excellent time and space efficiency. The source code of DynWalks is available at <https://github.com/houchengbin/DynWalks>.






§ INTRODUCTION

The interactions or connectivities between entities of a real-world complex system can be naturally represented as a network (or graph) e.g. social networks, biological networks, and sensor networks. Learning topological representation of a network, especially low dimensional node embeddings that encode network topology therein so as to facilitate downstream tasks, has received a great success in the past few years <cit.>. 
For example, DeepWalk <cit.> conducts truncated random walks on each node to generate node sequences which are then fed into the Skip-Gram neural network model <cit.> for training node embeddings; Node2Vec <cit.> extends DeepWalk by using more flexible truncated random walks to explore network topology; LINE <cit.> explicitly includes both the first-order and second-order proximity of each nodes in the KL-divergence objective function; HOPE <cit.> considers the high-order proximity and obtains node embeddings by seeking the largest k singular values of the generalized SVD problem; and etc. 
Note that these methods are designed for static networks.


However, many real-world networks are dynamic by nature i.e. nodes/links might be added/removed as time goes on. For example, in a wireless sensor network, devices will regularly or accidentally connect to or disconnect from the routers; in a social network, new users and new friendships between existing users will occur as time goes on. The aforementioned static network embedding methods cannot properly deal with dynamic networks, since they cannot update embeddings for the seen nodes based on incoming changes, and may require retraining embeddings for all nodes from scratch. 

Dynamic network embedding, which aims to learn low dimensional embeddings for unseen and seen nodes at each time step by using any currently available snapshots of a dynamic network, is now attracting much attention. Nevertheless, the existing methods still face two main challenges.

The first main challenge is the time and space complexity. It has been discussed a lot in the static network embedding methods <cit.> for handling a large-scale static network. And it becomes more severe for a dynamic network. For example, assuming some small changes occur at each time step, after evolving over k steps, the nodes and links over k snapshots would be about k times the number of them in the initial snapshot. Besides, if a real-world application requires to run downstream tasks e.g. daily, dynamic network embedding methods will therefore have the real-time constraint.

The earlier work <cit.> proposes BCGD-global that uses all available snapshots and BCGD-local that uses current snapshot and one previous snapshot. Although BCGD-local reduces the space complexity, both of them are still time-consuming, since they iteratively optimize embeddings for all nodes over each employed snapshot until convergence.
DynGEM <cit.> proposes a heuristic strategy to modify the structure of a deep auto-encoder based on the size of the current snapshot. It continuously trains the adaptive auto-encoder using all links in current snapshot, which is also time-consuming.
NetWalk <cit.> adopts random walks to produce network walks for training the auto-encoder that minimizes the pairwise distance among all nodes in each walk. Unfortunately, it needs to retrain almost all network walks if there are a few links removed.
DynTriad <cit.> models the triadic closure process, social homophily, and temporal smoothness in its objective function. However, optimizing the objective function requires all the links over all available snapshots.
In summary, these methods are not scalable to a large-scale dynamic network, and are intractable to fulfill real-time constraint if needed. 

To overcome the first main challenge, one natural idea is to put the limited computational resources on some most important parts. Recently, some methods <cit.> propose different strategies to select the k most affected nodes, and then update embeddings for these nodes at each time step. The k most affected nodes highly depend on incoming changes, and any changes can affect all nodes in a connected network via high-order proximity. Hence, the global topology of the network will be significantly altered by accumulated changes or small special changes as illustrated in Figure <ref>, which is the second main challenge i.e. the ability of global topology preserving. Moreover, DHEP <cit.> extends HOPE <cit.> by modifying the k most affected eigenvectors based on matrix perturbation theory, so as to efficiently cope with dynamic changes. But there will be non-ignorable accumulated errors after multiple time steps <cit.>, which might also be related to the second challenge.



To tackle the above two main challenges, we propose a dynamic network embedding method called DynWalks, which has the following desired properties: 1) the excellent time and space efficiency, 2) the flexibility to balance global topology and recent changes, 3) fulfilling the real-time constraint if needed, and 4) handling unseen nodes without placeholders or knowing them in advance.

The main contributions of this work are three-folds: 1) Two important challenges of dynamic network embedding are identified especially the global topology one; 2) DynWalks has some desired properties as listed above. In particular, a novel online node selecting scheme is proposal to balance global topology and recent changes; and 3) The more realistic slicing approach based on the calendar day(s) is used to slice each dynamic network. The empirical studies on six real-world dynamic networks under three different slicing ways confirm the effectiveness and efficiency of DynWalks.



§ NOTATION AND PROBLEM DEFINITION


Definition 1. Static Network Embedding: Let G=(𝒱,ℰ) be a given network/graph, where 𝒱 denotes a set of |𝒱| nodes/vertices and ℰ denotes a set of |ℰ| links/edges. 
The static network embedding aims to find a mapping function Z=f(G) where Z∈ℝ^|𝒱|× d, d ≪ |𝒱| and each row vector Z_i∈ℝ^d is the node embedding vector corresponding to node v_i. The pairwise similarity of node embeddings in Z should reflect the pairwise topological similarity of the nodes in G. 

Definition 2. The snapshots of a dynamic network: A dynamic network in this paper refers to a time-evolving network i.e. nodes or edges might be added or removed as time goes on. The snapshots of a dynamic network are the copy of the network at each time step. A dynamic network 𝒢 contains a set of snapshots 𝒢=(G^0,G^1,...,G^t,G^t+1,...) where t denotes the current time step.

Definition 3. Dynamic Network Embedding: The dynamic network embedding problem can be generally defined as using any currently available snapshots to obtain embedding vector Z^t_i for each node v_i in the current snapshot G^t i.e. Z^t=f(G^t,G^t-1,...,G^0).





§ THE PROPOSED METHOD

The proposed method DynWalks includes two key components. Firstly, an online network embedding framework aims to efficiently learn embeddings based on the selected nodes. Secondly, an online node selecting scheme selects the nodes by considering both recent changes and global topology.



 §.§ Online Network Embedding Framework


In general, the idea of capturing network topology and learning node embeddings is motivated by DeepWalk <cit.>. The truncated random walks with length l are conducted on each interested nodes for r times, which generates r|𝒱| node sequences. A sliding window with length w+1+w is used to slide along each sequence, and the training pairs set 𝒟 is built via (v_center, v_center+i) where i ∈ [-w,+w], i ≠ 0. Note that, the random walks with length l can capture at most l-hops away neighbors of a given starting node; and the resulting training pairs can encode 1^st∼ w^th-order proximity of a given center node. Due to them, DynWalks can capture the high-order proximity.

In order to further reduce complexity <cit.> and freely deal with unseen nodes without placeholders, the Skip-Gram Negative Sampling (SGNS) neural network model (which is different from the model used in DeepWalk) is employed to train node embeddings over each node pair (v_i,v_j) ∈𝒟 i.e.

    max  logσ (Z_i· Z_j) + m·𝐄_v_k∼ P_𝒟[logσ (-Z_i· Z_k)]

where σ is the Sigmoid function, Z_i is the node embedding vector for node v_i, m is the number of negative samples, and v_k is the negative sample from the unigram distribution P_𝒟 <cit.>. The aim of Eq. (<ref>) is to make the node embedding vectors similar if the nodes co-occur, and dissimilar if they are negative samples. The overall objective is to sum over all pairs i.e.
∑_(v_i,v_j) ∈𝒟#(v_i,v_j) Eq.(<ref>). Intuitively, the more frequently a pair of nodes co-occurs, the more similar they are.

With the above modified DeepWalk i.e. a scalable static network embedding method, DynWalks further extends it to an online manner as shown in Figure <ref>. It can be formalized as:

    Z^t={[                     f(G^t,SGNS^t_rand)                                    t=0; f(G^t,G^t-1,SGNS^t-1)=f(Δℰ^t,SGNS^t-1)                                    t≥1 ].

where SGNS^t-1 is the trained model from last time step, Z^t is the current embedding matrix directly taken from newly trained SGNS^t via an index operator, and streaming links Δℰ^t are the differences between G^t and G^t-1 i.e. a set of triples indicating node pairs being added or removed.

As shown in Figure <ref> and Eq. (<ref>), DynWalks has two stages. For t=0, random walks are conducted on all nodes in G^0 and SGNS^0 is randomly initialized, since there is no historical information of all nodes and their embeddings. For t≥1, random walks are conducted on the selected nodes from G^t where the number of nodes |𝒱^t_sel|<|𝒱^t_all|, so as to reduce the time and space complexity. And SGNS^t-1 is used as the initialization of SGNS^t, so as to utilize the historical/temporal information and stabilize the embedding vector of a node appeared in both G^t-1 and G^t.




 §.§ Online Node Selecting Scheme


The online node selecting scheme as shown in Figure <ref> is proposed to select nodes from current snapshot G^t. There are two questions to be answered. Firstly, how many nodes should be selected? To reduce time and space complexity, one natural idea is to focus on a part of important nodes. Therefore, the hyper-parameter α is used to limit the number of selected nodes to α|𝒱^t| where α can be adapted according to the real-time constraint if needed. And secondly, which nodes should be selected? To balance recent changes and global topology, the hyper-parameter β is used to select βα|𝒱^t_all| most affected nodes and (1-β)α|𝒱^t_all| diverse nodes.

For the most affected nodes, the stream links Δℰ^t can be obtained based on the differences between G^t-1 and G^t if not given. After that, the reservoir ℛ is used to count and maintain the accumulated changes for the nodes with at least one change, e.g. (v^t_i,v^t_j,add/del) gives the accumulated changes of both nodes increased by one (note the selected nodes will be removed from ℛ to save space usage). Finally, motivated by the concept of inertia from Physics, the online scoring function is defined as


    S(v^t_k)
         = |Δℰ^t_k|+ℛ^t-1_k/Deg(v^t-1_k) 
         = | 𝒩(v_k^t) ∪𝒩(v_k^t - 1) - 𝒩(v_k^t) ∩𝒩(v_k^t - 1) | 
         + ℛ_k^t-1/Deg(v^t-1_k)


where ℛ^t-1_k denotes the accumulated changes[The accumulated changes in reservoir are used to fix the case when a node has small changes at each time step for a long time, which will affect network topology but may be ignored if the small changes are not recorded.] of node v_i at time step t-1, 𝒩(·) denotes a set of the neighbors of a node, and |·| denotes the number of elements in a set. According to the scores of the affected nodes, the top-k most affected nodes will be selected, and the time-variant k=βα|𝒱^t|. Intuitively, the larger degree of a node is, the larger accumulated changes are required to select it.

For the diverse nodes, the most affected nodes in a set 𝒱_m^t as well as unseen nodes in a set 𝒱_u^t will be stored in a set of tabu nodes 𝒱_tabu^t=𝒱_m^t ∪𝒱_u^t. The diverse nodes, (1-β)α|𝒱^t| in total, are then selected randomly from the set given by 𝒱_d^t=𝒱_all^t - 𝒱_tabu^t. Note that, other more advanced diversity-based heuristic selecting approach can be applied, which leaves as the future work.




 §.§ Algorithm and Complexity Analysis



 
The pseudocode of DynWalks is summarized in Algorithm <ref>, and the source code is also provided in the supplementary materials. For t=0 i.e. offline stage, it is a modified version of DeepWalk <cit.> which instead trains a SGNS model, such that the time complexity is further reduced to O(r|𝒱^0_all|lw). 
For t≥0 i.e. online stage, lines 13-15 are similar to lines 2-4, and the time complexity is similarly as O(r|𝒱^t_sel|lw). In lines 6-12 i.e. the online node selecting scheme, lines 6-7 require O(|Δℰ^t|) respectively, and lines 8-12 at most require O(|𝒱_all^t|) respectively. Note that, in line 9, the introselect algorithm is used to find the element in the top-k position without fully sorting other elements and then use it to select the top-k values, which gives O(|𝒱_all^t|). Therefore, the overall time complexity during online stage is O(2|Δℰ^t|+5|𝒱_all^t|+r|𝒱^t_sel|lw). 
For most real-world large dynamic networks, the streaming links |Δℰ^t|≈ c|𝒱_all^t| where c is usually a constant smaller than the average degree, and the selected nodes |𝒱^t_sel|≈α |𝒱^t_all| due to relatively less unseen nodes. The overall time complexity during online stage can be rewritten as O((2c+5+α rlw) · |𝒱^t_all|) where α∈ [0.0, 1.0]. To meet the real-time constraint if needed, one may decrease α at the risk of decreasing performance. 

Regarding the space complexity, there are four space-consuming variables kept in memory: the previous SGNS model with size 2|𝒱^t-1_all|d, the reservoir dictionary with size at most |𝒱^t_all|, the streaming edges Δℰ^t or two snapshots G^t-1 and G^t, and the training pairs |𝒟^t|= O(r|𝒱^t_sel|wl). Therefore, the space complexity is linearly proportional to the number of nodes in G.



 §.§ Global Topology and Recent Changes Awareness

 
DynWalks can aware and balance global topology and recent changes via the hyper-parameter β. As shown in Figure <ref> (except the red unseen nodes at the top-left corner obviously needed to select and train), for β=0.0 in (a) i.e. focus on global topology, the selected nodes in blue are diversely distributed; whereas for β=1.0 in (c) i.e. focus on recent changes, all the recently changed nodes by new links in red (roughly at the middle-right corner) are selected. Consequently, the grey-scale heatmap of (a) implies almost all nodes get similar attention for training; whereas the heatmap of (c) shows the training is bias to recent changes, but neglects other parts i.e. the large light parts in the heatmaps. Nevertheless, choosing a proper β in between e.g. β=0.5 in (b), a good trade-off between global topology and recent changes may be achieved. Note that the darker a node is, the more frequently it occurs in 𝒟, and hence it is trained by Eq. (<ref>) for more times.






§ EMPIRICAL STUDY

The six real-world dynamic networks come from <http://konect.uni-koblenz.de/> or <http://snap.stanford.edu/data/>. DNC is the leaked email communication network of US Democratic National Committee in 2016. AS733 contains 733 daily instances of the Autonomous System of routers exchanging traffic flows with neighbors. Chess is an online gaming network of Chess where each pair of nodes records a game between two players. Elec is the network of English Wikipedia users vote for and against each other in admin elections. FBW is a social network of Facebook Wall posts where nodes are the users and links are built based on the interactions in their wall posts. HepPh is a co-author network extracted from the papers of High Energy Phsics Phenomenology in the arXiv. All datasets except AS733 are given in the streaming links format i.e. a pair of nodes with a timestamp (streaming links may bring unseen nodes), whereas AS733 is given in the snapshots format and only AS733 has nodes/links being removed. All datasets are treated as undirected networks. Besides, the minimum possible interval in Chess is 1 month, whereas the interval for other datasets is 1 day. Moreover, three ways are employed to slice dynamic networks into snapshots as shown in Table <ref>, and only the most recent snapshots if appropriate are taken out after data slicing (the source code is provided in supplementary materials): S1–the minimum interval of each dataset for 21 snapshots, S2–the maximum possible interval for 21 snapshots, S3–the minimum interval for 100 snapshots.





In the experiments, the proposed method is compared to four state-of-the-art dynamic network embedding methods. BCGD-local <cit.>, DynGEM <cit.>, and DynWalks (Ours) are online learning method, as they only use the topological information available at current time step to learning embeddings for current time step, whereas BCGD-global <cit.>  and DynTriad <cit.> use all topological information including future time steps together to learn embeddings for each time step. The original source code in <https://github.com/linhongseba/Temporal-Network-Embedding>, <https://github.com/palash1992/DynamicGEM>, and <https://github.com/luckiezhou/DynamicTriad> for BCGD, DynGEM, and DynTriad respectively is used. And the original hyper-parameters in the source code are employed and fixed for all experiments. For fairness, the key hyper-parameters of our method are also fixed at α=0.2 and β=0.5 for all experiments, and other parameters r, l, w are fixed at 20, 80, 10 respectively <cit.>. The embedding size d is set to 128 for all methods.



 §.§ Graph Reconstruction and Link Prediction

Graph Reconstruction (GR) is used to evaluate the quality of the embeddings for recovering the network topology of the interested nodes. In this paper, GR task aims to retrieve for 1/4 randomly sampled nodes of the snapshot at t using embeddings at t, whereas Changed GR (CGR) task aims to retrieve for the nodes directly affected by changes. Both tasks are then evaluated by Average Precision@k (AP@k) score <cit.>. Link Prediction (LP) is used to evaluate the ability of predicting future links at t+1 using embeddings at t. The testing links include all changed links from t to t+1, plus other links randomly sampled from the snapshot at t+1 for balancing existent links and non-existent links. LP task is then evaluated by Area under the ROC Curve (AUC) score <cit.>.








As shown in Table <ref>, for all CGR and GR tasks, our method significantly outperforms other methods in most cases. One exception is the GR-AP@10-S2-DNC case where BCGD-local and our method both obtain bad results, which is due to that S2 makes the snapshots of DNC snapshots dramatically sparse as shown in Table <ref> (i.e. the email network at very beginning has 64 nodes and 62 links). DynTriad and BCGD-global can still obtain good results, however, they use all links over all snapshots together (hence overcome the sparsity problem but is not realistic in some scenarios) to learn embeddings for each time step, whereas BCGD-local and ours are the online learning method. For all LP tasks, all methods except DynGEM are comparable, since no method can always outperform others.

As shown in Figure <ref>, the methods that can complete the given tasks with 100 time steps within a reasonable duration are conducted. For the CGR and GR tasks, our method not only outperforms other methods, but also exhibits the stability w.r.t. time evolving, which may verify the usefulness of using embeddings at t-1 as the initialization of embeddings at t. For Chess-LP task, our method performs not that good at the beginning, but gradually catches up with others as the network grows. Furthermore, regarding all experiments, our method is better at GR/CGR tasks than LP tasks, since GR/CGR tasks ask for correctly recovering as many the neighbors of a given node as possible, which requires the good knowledge of global topology—the special advantage of our method.










 §.§ Sensitivity Analysis

The sensitivity analysis of two hyper-parameters α and β is shown in Figure <ref>. For β=0.5 and varying α i.e. to see the effect of different numbers of the selected nodes: the performance significantly increases as α grows when α is relatively small, but may saturate or decrease when α is relatively large. For α=0.2 and varying β i.e. to see the effect of different attentions between global topology and recent changes: there is no clear tendency as β grows, since different datasets and different tasks both have different bias. Note that, α=0.2 and β=0.5 are fixed for all other experiments, however, it is possible to obtain even better results via tuning them properly.









 §.§ Wall-Clock Time

To access wall-clock time, all the results as shown in Table <ref> are produced in the same computer with 128G ROM, 40-cores Intel E5-2630v4@2.2GHz CPU, and Nvidia Tesla-P100-16G GPU. The n/a values are due to the methods exceed either memory limit or 12 hours. It is obvious that our method is much faster than other methods (DynTriad uses GPU for acceleration and hence may be slightly faster on the small dynamic network within 21 time steps). Considering online stage Ours_t≥1,avg^0.2,0.5, the superiority will become more obvious if lasting for more times steps. Besides, the last three columns and Figure <ref> show the practical significance of α to balance wall-clock time and performance.






§ CONCLUSION

This paper first identifies the two main challenges about complexity and global topology preserving of the dynamic network embedding problem. DynWalks is hence proposed to tackle these challenges. To reduce the complexity, an online network embedding framework extends the modified DeepWalk so as to dynamically and efficiently learn embeddings based on the selected nodes. To preserve the global topology—an important feature for downstream tasks, a novel node selecting scheme offers the flexible choices to balance global topology and recent changes. The extensive empirical studies have verified the effectiveness and efficiency of DynWalks. The limitation might be the cold start problem at the very beginning of a dynamic network if the snapshot is extremely sparse, one future work is to employ side information e.g. node attributes to overcome it. Another future work is to improve the diverse nodes selecting approach <cit.> for better maintaining the global topology.  








unsrt


Appendices


§ IMPLEMENTATION DETAILS OF DYNWALKS AND OTHER COMPARED METHODS

The pseudocode of DynWalks is summarized in Algorithm 1, and the source code implemented in Python is also provided in the supplementary materials. However, there is a trick not explicitly mentioned in the paper, but it can help DynWalks properly deal with either very large or few changes for any choices of α and β. In order to make the wall-clock time controllable (by limiting the number of selected nodes), as well as to retain an acceptable performance (by choosing as many selected nodes as possible), DynWalks asks for selecting exactly α |𝒱^t_all| nodes in total, which includes βα|𝒱^t_all| most affected nodes and (1-β)α|𝒱^t_all| diverse nodes. However, sampling βα|𝒱^t_all| most affected nodes from the reservoir might be impossible, if the number of nodes maintained in the reservoir is less than βα|𝒱^t_all|. In this case, the small trick is to calculate the number of lacked nodes, which is then added to the number of diverse nodes, so that the total selected nodes are still α |𝒱^t_all|. As a consequence, the performance is likely to be superior (not wasting computational resources) and the wall-clock time is also controllable (not exceeding required time). Please see the function node_selecting_scheme() in source code → src → libne → DynWalks.py for details.

In this paper, DynWalks is compared with other four dynamic network embedding methods. We re-implement these methods according to the following procedures. 1) BCGD-local, BCGD-gloabl, and DynTriad need to know all unique nodes in advance. Hence, we write a Python script to obtain all unique nodes throughout all snapshots. 2) Run the their code to obtain node embeddings, and convert node embeddings in different formats into the standard format i.e. dict-of-dict {t1: Z_1, t2: Z_2, ...} where Z_1={node1: emb1, node2: emb2, ...}. 3) Since all the outputs of all methods are now in the same format, we employ eval.py and libne as provided in supplementary materials for evaluation. 4) During running the compared methods, some methods for some tasks may exceed 128G ROM or 12 hours, which leads to the n/a values as shown in the tables. In general, DynGEM consumes very large ROM, and the complexity might be related to the number of nodes; DynTriad also consumes relatively large ROM, but the complexity might be related to the number of links; BCGD-local and BCGD-global only consume small ROM, but they learn node embeddings in an iterative way over all given snapshots until convergence, which is particularly time-consuming.



§ HYPER-PARAMETERS TUNING OF DYNWALKS

There are two types of hyper-parameters: the key hyper-parameters i.e. α=0.2 for the upper limit of selected nodes and β=0.5 for balancing global topology and recent changes; and the other hyper-parameters related to random walks and Skip-Gram model i.e. walks per node r=20, walk length l=80, window size w=10, embedding dimensionality d=128, and negative samples of SGNS model in Eq <ref> m=5. For fairness, we fix the above hyper-parameters for all experiments except sensitivity analysis. The experimental results in Table <ref>, Figure <ref>, and Table <ref> show that the fixed hyper-parameters have already obtain the superior results in terms of both downstream tasks and walk-clock time. Nevertheless, according to the sensitivity analysis, it is possible to obtain even better results if we tune α and β properly. 

The practical guidance of tuning α and β according to our experience is as follows. First of all, we should choose a proper α to fulfill the real-time constraint based on the size of the dynamic network and the computational resources. Because the real-world approximation of time complexity is O((2c+5+α rlw) · |𝒱^t_all|), we can use a toy dynamic network to obtain the wall-clock time in the machine, and then deduce the estimated wall-clock time of the large dynamic network in the same machine via t_large/t_toy≈|𝒱_large|/|𝒱_toy|. 
After that, we could choose a proper β via gird search in [0.0, 1.0], since different datasets and different tasks both have different bias to global topology.

In additional, DeepWalk <cit.> can be seen as a special case of DynWalks when α=1.0 and replacing the original Skip-Gram Hierarchical Softmax model with Skip-Gram Negative Sampling model. However, according to Figure <ref> and Table <ref>, too large α brings increasing wall-clock time, but it is hard to receive further increasing performance. Based on our experience, the performance significantly increases as α grows when α is relatively small e.g. below 0.5 on AS7SS dataset.




§ GRAPH RECONSTRUCTION AND LINK PREDICTION: THE STANDARD DEVIATION








Tables <ref> and <ref> show the more detailed results of the experiments in slicing ways S1 and S2 respectively. Differently form Table <ref>,  Table <ref> and Table <ref> additionally present the results of DynWalks^0.1,0.5 and the averaged standard deviation (std) i.e. the average over 10 runs of the std over 21 steps. According to tables <ref> and <ref>, we have the following observations.

For all tasks, DynWalks^0.2,0.5 achieves better results than DynWalks^0.1,0.5 in both S1 (see Table <ref>) and S2 (see Table <ref>) cases. But the performance gain is more significant in S2 case, which might be due to the changes of consecutive snapshots are larger than in S1 case. As a result, the more training samples may be required to reflect the larger changes, which leads to an interesting future work to make α adaptive based on the dynamic changes rather than choose a prefixed value. Note that, even if we compare DynWalks^0.1,0.5 (requires less computation resources than DynWalks^0.2,0.5) to other dynamic network methods, DynWalks^0.1,0.5 also receives the better results in most cases.

Regarding the stability w.r.t time-evolving, DynWalks is more stable than other methods in most cases. In particular, for CGR-AP@10 and GR-AP10 on DNC dataset, DynWalks does not receive the highest mean value, however, the std value of DynWalks is much smaller than the method that receives the highest mean value. And this observation is also according with the observation made in Figure <ref>. Therefore, it enables DynWalks to work in some special real-world applications that require such stability w.r.t time-evolving. 




§ GLOBAL TOPOLOGY AND RECENT CHANGES AWARENESS: THE REMOVING CASE

 

In addition to Figure <ref> i.e. nodes/links adding case, Figure <ref> illustrates nodes/links removing case on a similar toy dynamic network. The general observations are similar as the observations made in Figure <ref>. However, the choices of a proper β might be more crucial for the removing case due to the following two reasons. Firstly, it may bring very sparsely connected part(s). However, random walks are naturally biased to densely connected part(s), and hence, may not generate enough node training pairs around the very sparsely connected part(s). And secondly, it may even bring isolated sub-network(s), so that random walks will be trapped inside the isolated sub-network(s) if without the help of enough diverse nodes.

