Large Scale Evolving Graphs with Burst Detection

1 Introduction

Dynamic networks, where edges and vertices arrive over time, are ubiquitous in various scenarios, (e.g., social media, security, public health, computational biology and user-item purchase behaviors in the E-Commerce platform [Akoglu and Faloutsos, 2013; Akoglu et al., 2015]), and have attracted significant research interests in recent years. An important problem over dynamic networks is burst detection - finding objects and relationships that are unlike the normal. There are many practical applications spanning numerous domains of burst detection, such as bursty interests of users in E-Commerce [Parikh and Sundaresan, 2008], cross-community relationships in social networks. Recently, the research community has focused on network embedding learning. One class of the network embedding methods represent nodes as single points in a low-dimensional latent space, which aims to preserve structural and content information of the network [Perozzi et al., 2014; Grover and Leskovec, 2016]. Other classes include edge embedding and subgraph embedding [Dong et al., 2017]. However, most existing network embedding methods mainly focus on the network structure, ignoring the bursty links appearing in the dynamic networks [Perozzi et al., 2014; Dai et al., 2016; Qiu et al., 2018].

In social network dynamics, users may generate consistent temporal patterns by buying consumable goods, such as food and papers, to satisfy their recurrent needs; or purchasing durable products, such as cell phones and cars, to satisfy their longtime needs. However, in the real world, bursty links are very common in network evolution. For instance, in a social network, people will meet new friends or discover new interests if they are in a new environment; in an E-Commerce network, customers often do window shopping when they are exploring recommendation sections. Figure 1 illustrates the interest evolution of the young lady during shopping. However, existing works on modeling dynamic networks mostly focus on repeated and consistent patterns [Trivedi et al., 2017; Li et al., 2017; Zhou et al., 2018], and cannot well capture bursty links due to their sparsity. Such important bursty information is commonly viewed as noisy data in the general machine learning algorithms and ignored in modeling [Chandola et al., 2009]. Furthermore, these bursty dynamics are hidden in other complex network dynamics, including the addition/removal of edges and the update of edge weights. It is challenging to design a framework to account for all these changes.

To tackle the aforementioned challenges, we propose a novel framework with contributions summarized as follows:

• Problem Formulation: we formally define the problem of evolving graphs with bursty links. The key idea is to detect bursty links in dynamic graphs during their onset.

• Algorithms: we propose a novel framework for modeling evolving graphs with bursty links, namely BurstGraph. BurstGraph divides graph evolution into two parts: vanilla evolution and bursty links' occurrences. For the sparsity of bursty links, a spike-and-slab distribution [Mitchell and Beauchamp, 1988] is introduced as an approximation posterior distribution in the variational autoencoder (VAE)[Kingma andWelling, 2013] framework, while vanilla evolution accepts the original framework of VAE. To fully exploit the dynamic information in graph evolution, we propose an RNN-based dynamic neural network by capturing graph structures at each time step. The cell of RNN maintains information of both vanilla and bursty evolution, which is updated over time.

The rest of this paper is organized as follows: Section 2 briefly reviews related work. Section 3 introduces the problem statement of evolving graphs with bursty links and presents the proposed framework. Experiments on both simulated dataset and real datasets are presented in Section 4 with discussions. Finally, Section 5 concludes the paper and visions the future work.

2 RelatedWork

Static Network Embedding. Recently, learning representations for networks has attracted considerable research efforts. Inspired by Word2Vec [Mikolov et al., 2013], [Perozzi et al., 2014; Grover and Leskovec, 2016] learn a node representation with its neighborhood contexts. As an adjacency matrix is used to represent the topology of a network, representative works, such as [Qiu et al., 2018], use matrix factorization to learn low-rank space for the adjacency matrix. Deep learning methods [Wang et al., 2016] are proposed to introduce effective non-linear function learning in network embedding.

Dynamic Network Embedding. Actually, inductive static methods [Perozzi et al., 2014; Hamilton et al., 2017a] can also handle dynamic networks by making inference of the new vertices. [Du et al., 2018] extends the skip-grammethods to update the original vertices' embedding. [Zhou et al., 2018] focuses on capturing the triadic structure properties for learning network embedding. Considering both the network structure and node attributes, [Li et al., 2017] focuses on updating the top eigenvectors and eigenvalues for the streaming network.

Burst Detection. Traditionally, burst detection is to detect an unexpectedly large number of events occurring within some time duration. There are two typical types of burst detection approaches, i.e., threshold-based [Heard et al., 2010] and statebased methods [Kleinberg, 2003]. [Heard et al., 2010] studies fast algorithms using self-similarity to model bursty time series. [Kleinberg, 2003] uses infinite-state automaton to model the burstiness and extract structure from text streams. However, the link building of evolving graphs is usually sparse and slow, where unexpected links are rare to occur simultaneously. Therefore, our definition of a burst is simply an unexpected behavior within a time duration, which is a straightforward definition adopted by many applications in the real world.

3 The ProposedModel

Existing dynamic network embedding methods mainly focus on the expansion of new vertices and new edges, but usually ignore the changes of vertices' attributes through time that lead to unexpected bursty network changes [Angel et al., 2012]. To tackle this problem, we propose to learn low-dimensional representations of vertices to capture both vanilla and bursty evolution. Given a dynamic network {G1, ...,GT}, the dynamic network embedding is to learn a series of functions , where each function fφt maps vertices in network Gt to low-dimensional vectors: fφt (vi) -→ Rd and φts are corresponding network parameters. We first summarize symbols and notations in Table 1 and use bold uppercase for matrices (e.g., A), bold lowercase for vectors (e.g., a), normal lowercase for scalars (e.g., a). 1 denotes a vector whose elements are all 1 and I denotes the identity matrix. The framework of the proposed model is illustrated in Figure 2. It mainly consists of two components, namely the original VAE for vanilla evolution and the spike-and-slab model to detect bursty links.

3.1 VAE for Graph Evolution

After detecting the bursty links at each discrete time t, we split the adjacency matrix of graph At into two parts: vanilla adjacency matrix Av,t and burst adjacency matrix Ab,t. To capture information of these two parts, we extend the framework of VAE and introduce a spike-and-slab distribution to simulate the sparsity of burst adjacency matrix. The loss function of VAE at each time step t is written as:

where Gi,t denotes the graph structure of vertex vi at time step t. zt and st are random variables in the VAE-based model for vanilla and bursty evolution respectively. The evidence lower bound (ELBO) of VAE [Kingma and Welling, 2013] can be written as:

where importance weight λ is a hyperparameter. θ and φ are parameters of the encoder and decoder networks respectively. The approximate posterior distribution of random variable zt follows a Gaussian distribution: qφ(zt|Gi,t) ∼ N(µ0(Gi,t), Σ0(Gi,t)). µ0(·) and Σ0(·) are the encoder networks, which can be any highly flexible functions such as neural networks [Kingma and Welling, 2013]. We use GraphSAGE [Hamilton et al., 2017a], a representative framework of graph convolutional network, to generate representation from vertex attributes and its neighbours:

where µ0(Gi,t) and Σ0(Gi,t) share the same GraphSAGE network to learn representation from topology structure and attributes of vertex vi. In our paper, fµ0 (·) and fΣ0 (·) are both two fully-connected layers where hidden layers are activated by RELU function. Similar to the original framework of VAE [Kingma and Welling, 2013], the prior of random variable zt follows a standard Gaussian distribution. This is no longer suitable in the case of rare and discrete bursty links. In our paper, the approximate posterior distribution of random variables st for bursty links is set to follow a spike-and-slab distribution

[Mitchell and Beauchamp, 1988]:

where µ1(·) and Σ1(·) are the encoder networks, with the same neural network structure settings as µ0(·) and Σ0(·) in Equation (3), respectively. ψ(·) is also an encoder network which is two fully-connected layers activated by sigmoid function. The value for β > 0 is predefined with usual setting β = 100 for more flexbilities [Ishwaran et al., 2005]. Therefore, rt,1 follows a spike distribution while rt,2 is a slab distribution.

For easy implementation, the prior distribution p∗ (st) of st is set to: p∗ (st) ∼ (1 -α) · N(0, 1 100 I) + α · N (0, I), where α = {αi} and each αi is drawn from a Bernoulli distribution: {αi} iid ∼ Bernoulli( 12 ). The regularization loss of spike-and-slab variable st in ELBO can be written as:

By using the reparameterization trick, the random variables like zt, ct, rt,1 and rt,2 can be rewritten as:

where ϵ follows the uniform distribution ϵ ∼ U(0, 1). γ0, γ1 and γ2 all follow the standard Gaussian distribution: γ0, γ1, γ2 ∼ N(0, I). The decoder network fs(st) = σ(Ws · st) is a transition function to reconstruct the bursty links Abi,t in time t. For vanilla evolution, the framework are similar with the original VAE, where the prior of random variable zt follows a standard Gaussian distribution and the decoder network fz(zt) is a fully-connected network activated by sigmoid function to reconstruct the vanilla connection Avi,t at time t.

3.2 Learning Representations For Dynamic Network

In the evolving network settings, the goal is to learn the evolving changes from a set of sequential graphs G = {G1,G2, ...,GT}. To take the temporal structure of the sequential graphs into account, we introduce an RNN structure into our framework as shown in Figure 3. The prior of the latent random variables is not set to follow a standard distribution, but depends on the last hidden variable ht-1:

In the similar way, the approximate posterior distribution of these random variables will depend on both the current network snapshot Gi,t and the last hidden variable ht-1:

In the same way of RNN, the hidden variable ht is updated based on the previous hidden variable ht-1, the random variables zt and st:ht = fh(ht-1, zt, st),

where fh(·) is also a fully-connected network to transform the hidden variables.

Training. We adopt Adam optimizer [Kingma and Ba, 2014] to optimize the objective and also introduce dropout with weight penalties into our proposed model. As expected, we penalize L1-norm of weight Ws to induce the sparsity of the output. It is worth to note that all the parameters of our proposed model are shared along dynamic graphs over time interval (1, T). GraphSAGE in encoder network also shares a random features input for each vertice over time interval (1, T ). The edge evolution is always sparse and unbalanced, which brings trouble to identify the positive instances to achieve better performance. Instead of traditional sigmoid cross entropy loss function, we use inter-and-intra class balanced loss in our model:

where Lpos and Lneg are the cross entropy losses for positive and negative samples, respectively. Similarly, Lnod and Lcls are the cross entropy losses for labels in each node and class. Similar to the setting of loss, npos and nneg define the number of positive and negative samples, while nnod and ncls define the number of labels in each node and class, respectively.

4 Experiment

In this section, we evaluate our model in the dynamic setting from the performance on the multi-class link prediction.

Dataset. We first use the simulated data to verify the effectiveness of the model, then we apply BurstGraph to a real challenging dataset from a world-leading E-Commerce company.

1

• Simulated Dataset: We generate a sequence of synthetic bipartite graph snapshots of 21K vertices and 527K edges that share similar characteristics as real data. We assume that each vertex has two types (vanilla/burst) of representations. More specifically, we divide the generation process into two parts: the first part is to generate hyperparameters for each vertex to ensure the independence; the second part is to generate links by sampling two representations of vertices from Gaussian distributions with fixed hyperparameters. First, for each vertex, we sample the hyperparameters µ0, σ2 0 from the uniform distributions µ0 ∼ U(0, 2.5) and σ2 0 ∼ U(0, 0.01) for the vanilla evolution, and µ1, σ2 1 from µ1 ∼ U(-2.5, 0) and σ2 1 ∼ U(0, 1) for the bursty evolution respectively. To make sure that bursty links are sparse, the variance σ2 is set to be bigger than σ2 0 . We then generate the links in each snapshot as follows: we first determine the link types of each vertex pair with probability drawn from Bernoulli(0.1) for bursty links and vanilla links other-

wise. We then generate the links for each vertex pair. According to their link types, we resample the representations of these two vertices from corresponding Gaussian distributions: N(µ0, σ2 0 ) or N(µ1, σ2 1 ). A fixed weight W is employed to transform these two representations into a single value. In all simulated graph snapshots, we set a threshold to truncate around 4% of vertex pairs as links. Results are illustrated in Figure 4.

• Alibaba Dataset: We collect this dataset from a worldleading E-Commerce company Alibaba with two types of nodes, user and item. The bursty link between user and item is defined as if the user has no interaction with the item or similar items in the same category during the last 15 days according to business needs. The other links are viewed as vanilla links. With dynamic graph setting, we split the whole graph into a sequence of graph snapshots with the same time interval (e.g., 1 day). The dataset with sampled items is denoted as Alibaba-S dataset.

The statistics of the above datasets are shown in Table 2. In each dataset, graph snapshot Gt consists of all the nodes and interactions that appear at time step t. In our experimental setting, we hide a set of edges from the original graph and train on the remaining graph. The test dataset contains 10% randomly selected vertices, while the negative links are also randomly selected with the same number of positive links for each link type (vanilla/burst).

Baseline Methods We compare our model against the following network embedding algorithms.

• DeepWalk: DeepWalk 1 [Perozzi et al., 2014] is a representative embedding method for static network. DeepWalk generates truncated random walks and uses Skipgram algorithm [Mikolov et al., 2013] to learn latent representations by treating walks as the equivalent of sentences.
• GraphSAGE: GraphSAGE 2 [Hamilton et al., 2017b] is a general inductive framework of network embedding, which leverages topological structure and attribute information of vertices to efficiently generate vertex embedding. Besides, GraphSAGE can still maintain a good performance even with random features input.
• CTDNE: CTDNE [Nguyen et al., 2018] is a continuoustime dynamic network embedding method. CTDNE generates temporal randomwalk as the context information of each vertex and uses Skip-gram algorithm to learn latent representations. In this method, the time of each edge is simply valued according to the number of its snapshot.

1 https://github.com/phanein/deepwalk

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

• TNE: TNE 3 [Zhu et al., 2016] is a dynamic network embedding algorithm based on matrix factorization. Besides, this method holds a temporal smoothness assumption to ensure the continuity of the embeddings in evolving graphs.

It is worthy to mention, DeepWalk and GraphSAGE are static network embedding methods. To facilitate the comparison between our method and these relevant baselines, these two methods are trained with the whole graph, which includes all graph snapshots. In the following, we compare the performance of these methods with BurstGraph 4 on three datasets in terms of Micro-F1 and Macro-F1.

Comparison Results. Table 3 shows the overall performance of different methods on three datasets. Our model BurstGraph is able to consistently outperform all sorts of baselines in various datasets. Next we compare and analyze results on vanilla evolution and burst links, respectively. For the vanilla evolution, BurstGraph has a performance gain of +1.4% in terms of Micro-F1 and +3.5% in terms of Macro-F1 on average. For the bursty evolution, BurstGraph outperforms other methods +5.5% in terms of Micro-F1 and +5.3% in terms of Macro-F1 averagely. These results show that splitting evolving graphs into vanilla and bursty evolution not only

benefits for the performance of the bursty evolution, but also benefits for that of the vanilla evolution. Moreover, compared to other baselines, the performance of BurstGraph is quite robust over the three datasets. Notice that DeepWalk, CTDNE and TNE perform poorly on the simulated dataset. One potential reason could be that the simulated generation process may be easier for message passing algorithms (e.g., GraphSAGE) compared to matrix factorization based methods (e.g., DeepWalk, CTDNE or TNE).

Parameter Analysis. We investigate the sensitivity of different hyperparameters in BurstGraph including importance weight λ and random variable dimension d. Figure 5 shows the performance of BurstGraph on Alibaba-S dataset when altering the importance weight λ and variable dimension d, respectively. From part a), we can see that the performance of vanilla link prediction is stable when changing the importance weight λ. The performance of burst link prediction rises with the increase of importance weight λ and converges slowly when importance weight is larger than 1. From part b), we can conclude that the performance of BurstGraph is relatively stable within a large range of variable dimension, and the performance decreases when the variable dimension is either too small or too large.

Visualization of vertex representations. We visualize the embedding vectors of sampled vertices in the simulated dataset and Alibaba-S dataset learned by BurstGraph. We project the embedding vectors to a 2-dimensional space with t-SNE method. As shown in Figure 6, embeddings from the vanilla evolution can be clearly separated from embeddings of the bursty evolution. More specifically, the embeddings of vertexes in the vanilla evolution evenly spread out in the space, while the embeddings of vertexes in the bursty evolution gather in a relatively small area. The reason could be that the vertex

3 https://github.com/linhongseba/Temporal-Network-Embedding

4 https://github.com/ericZhao93/BurstGraph

• embedding in the vanilla evolution is highly depended on its attributes, while the vertex embedding in the bursty evolution is another way around because of sparsity.

5 Conclusion

In this work, we propose a novel approach for evolving graphs and assume that the evolving of edges in a sequence of graph snapshots can be split into two parts: vanilla and bursty evolution. In addition, these two parts utilize variational autoencoders based on two different prior distributions to reconstruct the graph evolution, respectively. The vanilla evolution follows a Gaussian distribution, when the burst evolution follows a spike-and-slab distribution. Experiment results on real-world datasets show the benefits of our model on bursty links prediction in evolving graphs. However, there still exist limitations in our model. First, only bursty links are considered in our framework. However, there exist other bursty objects, e.g., vertices and communities, which should also be taken into account. We plan to extend our approach to support these bursty objects in the future. Second, we plan to propose a new time series model that supports continuous inputs rather than discretized graph snapshots.