Towards Robust Dynamic Network Embedding

1 Introduction

A network or graph has been widely used to represent a complex system in sociology, biology, the Internet, etc. Network Embedding that embeds a static network into a low dimensional vector space [Cui et al., 2019], as a kind of topological feature extraction, has become a well-studied technique.

Recently, the research interest has moved to dynamic networks, as real-world networks are often dynamic by nature [Barros et al., 2021; Cui et al., 2019]. As a result, Dynamic Network Embedding (DNE) has drawn much attention. It aims to embed a dynamic network into a low dimensional vector space promptly at each timestep and meanwhile preserve some network topologies. A dynamic network G can be represented as a sequence of snapshots {G0 ,G1 , ...,Gt , ...} taken at each timestep. We could define the degree of changes as the average number of the changed edges between consecutive snapshots spanning a dynamic network.

There are two straightforward ways to generate a dynamic network as shown in Figure 1. First, the dynamic network G1 is generated by slicing with a fixed number of edges [Du et al., 2018; Zhang et al., 2018]. Second, the dynamic network G2 is generated by slicing with a fixed time interval [Hou et al., 2020; Singer et al., 2019]. For the both cases, the degree of changes could be quite different even for the dynamic networks generated from the same dataset. According to these two cases, we discuss the following two scenarios.

• The choice of a fixed number of edges for slicing might be difficult to justify, because of lacking obvious realworld significance. One may thus adopt different slicing settings. Are existing DNE methods effective and robust w.r.t. the different slicing settings that are used to generate different dynamic networks with different degree of changes from the same dataset?
• It might be easier to choose a fixed time interval for slicing, e.g., one day, owing to the obvious connection to real-world time. However, the number of changed edges might vary a lot over timesteps, due to different rate of streaming edges over time. Are existing DNE methods effective and robust w.r.t. different degree of changes while slicing through different slicing settings? More importantly, are they effective and robust w.r.t. different number of changed edges over timesteps?

We found that existing DNE methods are not robust in the former scenario. A robust DNE method via ensembles was therefore proposed to address this issue [Hou et al., 2021]. For the latter scenario, it is still an open problem.

2 Our Research

The degree of changes is a unique character of dynamic networks compared to static networks. It could be affected by various factors such as the slicing setting and the rate of streaming edges. It is natural to ask if existing DNE methods are effective and robust w.r.t. the degree of changes, which motivates us to conduct the following research works.

For the finished work, we started with the simpler scenario where the number of changed edges is identical over timesteps. A dynamic network is generated by slicing with a fixed number of edges as G1 illustrated in Figure 1. In this scenario, each dataset generates several different dynamic networks using different choices of a fixed number of edges. We then investigated whether existing DNE methods can robustly obtain a good performance over these different dynamic networks with different degree of changes.

We compared six existing DNE methods on five realworld datasets, and evaluated the resulting embeddings by three types of downstream tasks. Comprehensive experiments demonstrated that the existing DNE methods are not robust in this scenario. To address this issue, we proposed a robust DNE method which has been shown to be effective and robust. Concretely, the proposed method employs an incremental Skip-Gram embedding model as the base learner. Multiple base learners with a novel diversity enhancement strategy then form the ensembles to capture different levels of local-global topology, so as to learn node embeddings at each timestep [Hou et al., 2021]. The source code is available at https://github.com/houchengbin/SG-EDNE

For the future work, we would generate a dynamic network by slicing with a fixed time interval. This scenario is more challenging, because the number of changed edges may vary a lot over timesteps, e.g., much more friendships than usual would be built in a social network during a social event. This scenario tries to study the performance of a DNE method at each timestep, while the previous one focuses more on the average performance over all timesteps. Ideally, a desirable DNE method should be effective and robust w.r.t. not only different degree of changes by different slicing settings, but also different number of changed edges over timesteps.

We would benchmark existing DNE methods under this new scenario. After that, a more robust DNE method for this scenario would be proposed. Specifically, we would again exploit the notion of ensembles, while other details such as the choice of base learners and how base learners cooperate with each other are not decided yet.

It is promising to employ ensembles to improve the model robustness, since ensembles could provide a redundant design to alleviate the uncertainties in generating dynamic networks or in dynamic networks themselves. Furthermore, ensembles have been successfully applied in traditional streaming data [Sun et al., 2018] and graph streaming data [Hou et al., 2021] to improve the model robustness. If the aforementioned desirable DNE method is achieved, we would not only improve the average performance over all timesteps, but also apply it in industrial applications such as anomaly detection [Zheng et al., 2019] to avoid occasionally seriously degraded performance at some snapshots or timesteps.

3 Contributions

The contributions are as follows. First, we investigate the robustness of DNE w.r.t. the degree of changes, which is the first time to be formally studied. This is important to DNE

community, as robustness itself is a critical topic in dynamic environment. Second, we suggest two important scenarios. One is to investigate the robustness w.r.t. different slicing settings that are used to generate different dynamic networks with different degree of changes, while another would focus more on the robustness w.r.t. different number of changed edges over timesteps. Third, we have proposed a robust DNE method based on ensembles (for the first time) for the former scenario, and would propose another robust DNE method also based on ensembles for the latter scenario.

4 Conclusion

Though we have suggested the two important scenarios, there could be other complicated scenarios by other preprocessing approaches on the original dataset. It is impossible to list all. In the future, we should rethink of how to represent a dynamic network in a more proper way to reduce the uncertainties in generating dynamic networks, so that we can then propose a robust DNE method for broader applications.