Embedding Dynamic Attributed Networks by Modeling the Evolution Processes (2020)

Abstract: Network embedding has recently emerged as a promising technique to embed nodes of a network into low-dimensional vectors. While fairly successful, most existing works focus on the embedding techniques for static networks. But in practice, there are many networks that are evolving over time and hence are dynamic, e.g., the social networks. To address this issue, a high-order spatio-temporal embedding model is developed to track the evolutions of dynamic networks. Specifically, an activeness-aware neighborhood embedding method is first proposed to extract the high-order neighborhood information at each given timestamp. Then, an embedding prediction framework is further developed to capture the temporal correlations, in which the attention mechanism is employed instead of recurrent neural networks (RNNs) for its efficiency in computing and flexibility in modeling. Extensive experiments are conducted on four real-world datasets from three different areas. It is shown that the proposed method outperforms all the baselines by a substantial margin for the tasks of dynamic link prediction and node classification, which demonstrates the effectiveness of the proposed methods on tracking the evolutions of dynamic networks.

## introduction network embedding (ne) aims to represent each node by a low-dimensional vector, while seeking to preserve their neighborhood information as much as possible. it has been shown that working on the lowdimensional representations is much more efficient than on the original large-scale networks directly in various real-world applications, such as friend recommendation, product advertising, community detection @xcite , nodes classification etc. because of its capability in facilitating downstream applications, many methods have been developed to embed network nodes into vectors efficiently and effectively, like deepwalk in @xcite , line in @xcite , node2vec in @xcite etc. later, the attributes/texts available at nodes are further taken into account, e.g. the cane in @xcite and wane in @xcite , to obtain more comprehensive embeddings. however, these methods mostly focus on static networks, but in practice, networks are often dynamic. in social networks, for instance, new friend connections are established all the time, and user profiles are also updated from time to time. for these dynamic networks, how to learn their embeddings, and more importantly, how to leverage the embeddings to predict their evolution trends is crucial for many applications. existing methods for dynamic network embedding can be roughly divided into two categories. the first category concerns about how to obtain new embeddings from the stale ones efficiently when changes of networks are observed. in @xcite , by decomposing the learning objective into different parts, it is shown that new embeddings can be updated by only considering the newly added and most influential nodes. differently, @xcite proposed to use a graph convolutional network (gcn) or gaussian process to learn a mapping from the associated attributes to the embeddings, respectively, then the embeddings can be updated directly with the output of the mapping. the aforementioned methods avoid to re-compute the embeddings from scratch at every timestamp by tracking the network changes continuously. however, since these methods focus only on the changes at the current timestamp rather than their dynamics, the induced embeddings can only represent the networks at the current timestamp, but are poor at predicting their future evolvement. the second category methods focus more on the improvement of prediction performance. @xcite proposed to learn embeddings and an alignment matrix for the network at each timestamp by solving a sequential optimization problem, and then input the embeddings into recurrent neural networks (rnn) to predict the future links. however, sequential optimization is very expensive, hindering it from being applied to large networks. alternatively, @xcite proposed to learn embeddings with the objective to predict the future closure process of nodes that are separated by at most two hops. later, @xcite proposed to employ auto-encoders to predict nodes' direct neighbors with the neighbors from the previous timestamps via the long short-term memory (lstm). recently, @xcite introduced the concept of neighborhood formation and used it to track the evolution of nodes with their direct neighbors from the previous timestamps. in all of these methods, only the direct (first-order) neighbors in the spatial dimension are leveraged. however, to capture the dynamics of networks, it is important to consider the high-order information of nodes in both the spatial and temporal dimensions simultaneously. as illustrated in fig. 1 , the green node is isolated from the red node at t 1 and becomes its fourth-order neighbor at t 2 , and further evolves into its direct neighbor at t n . to capture this evolution process, the model should have the ability to be aware of nodes' high-order neighborhood information spatially and memorize the changes that occurred many timestamps before temporally. in this paper, a dynamic attribute network embedding model (dane) is developed to track the evolutions of dynamic networks. specifically, an activeness-aware neighborhood embedding method is proposed to extract the high-order neighborhood information at each given timestamp. the activenessaware mechanism enables the model to emphasize more on nodes that are active in social activities. then, an embedding prediction framework is developed to capture the temporal correlations of dynamic networks, in which the attention mechanism is employed instead of rnns for its efficiency in computing and flexibilities in modeling. the methods are evaluated on the tasks of dynamic link prediction and node classification over four real-world datasets. it is shown that the proposed methods outperform all comparable embedding methods, including both static and dynamic ones, on the link prediction by a substantial margin. this demonstrates that the proposed methods are able to capture the correlations from the dynamic networks. similar phenomena are observed on the task of dynamic node classification, which further confirms the effectiveness of the proposed methods on tracking the evolutions of dynamic networks. ## related work representation learning for graphs has attracted considerable attention recently, since they can potentially benefit a wide range of applications. specifically, @xcite employs random walks to obtain sequences of nodes, and then uses the word2vec technique to represent the nodes into lowdimensional vectors. to preserve both the global and local structure information, @xcite proposed to jointly optimize the first-and second-order proximity of nodes in network. later, @xcite introduced a biased random walk procedure under the bfs and dfs search strategies to further exploit the diversity of structure patterns of networks. however, in all of these methods, only the topology information of network is leveraged. but in many real-world networks, nodes are often associated with attributes or texts. to take the attributes into account, a mutual attention mechanism is designed to enhance the relationships between attributes of neighboring nodes in @xcite . to extract more semantic features from attributed data, @xcite modified the mutual attention mechanism in @xcite and employed a fine-grained word alignment mechanism. however, all these works are overwhelmingly performed in the context of plain or static networks. various techniques have been proposed to learn deep representations in dynamic patterns. @xcite first provides an offline embedding method and then leverages matrix perturbation theory to maintain the freshness of the end embedding results in an online manner. in @xcite , the model was developed to combine convolutional neural networks on graphs to identify spatial structures and rnn to find dynamic patterns. similarly, @xcite proposed a deep recurrent architecture to model historical evolution of entity embeddings in a specific relationship space. to capture both structural properties and temporal evolutionary patterns, @xcite jointly employed self-attention layers along structural neighborhood and temporal dynamics. differently, @xcite employed a temporal version of traditional random walks to capture temporally evolving neighborhood information. although significant efforts have been made to learn effective representations in evolutionary patterns, methods aiming to extract high-order spatio-temporal evolutionary information have been rarely explored. in our work, an activeness-aware neighborhood embedding method is developed to capture high-order neighbor evolutionary relationship, followed by a low-complexity attention-based mechanism, which efficiently apprehends temporal evolutionary patterns. ## experiments in this section, we evaluate the performance of the proposed methods on two tasks: dynamic link prediction and node classification. for the link prediction, we predict the new links that appear at timestamp t + 1 for the first time based on the historical observations until t @xcite . for the task of node classification, the categories of nodes at timestamp t + 1 are predicted, with only the nodes that change their categories at t + 1 considered @xcite . in the experiments, the dimension of network embeddings is set to 100 for all considered methods. the negative samples are set to 1 and the mini-batch size is set to 50 to speed up the training process. adam(kingma and ba, 2014) is employed to train the proposed model with a learning rate of 1 × 10 -4 . ## conclusion in this paper, a dynamic attribute network embedding framework is proposed to track the network evolution by modeling the high-order correlations in spatial and temporal dimensions jointly. to this end, an activeness-aware neighborhood embedding method is proposed to extract the high-order neighborhood information at each timestamp. then, an embedding prediction framework is developed to capture the temporal correlations. extensive experiments were conducted on four real-world datasets over the tasks of link prediction and node classification, confirming the ability of the model to track the evolutions of dynamic networks.