Motif-Preserving Temporal Network Embedding

1 Introduction

Recently academic and industry have both witnessed rapid development of network embedding, which maps the nodes into a low-dimensional space while preserving certain proximities among nodes, features, or structures. Due to its powerful performance, network representation learning, namely network embedding, has been widely applied to various network-related tasks, such as link prediction, node clustering, and node classification.

Inspired by word embedding [Mikolov et al., 2013] in language processing, Deepwalk [Perozzi et al., 2014] is proposed to embed nodes in the networks. Furthermore, LINE [Tang et al., 2015] preserves first- and secondproximities, GraRep [Cao et al., 2015] preserves k-order proximities, Node2vec [Grover and Leskovec, 2016] preserves neighborhood proximity, and MNMF [Wang et al.,

∗Contact Author

2017] preserves communities. All these methods achieve good performance in various network-related tasks.

However, the methods mentioned above are all proposed to deal with static networks, while most networks exhibit complex temporal properties, which means nodes and edges always evolve over the time. For example, in an information diffusion network, information interactions between users shape the typology of temporal network and influence the network evolution. As shown in Figure 1, there are a group of three users in an information diffusion network. At time t1, when B receives A's information, an edge from A to B establishes. An edge forms once there is an action associated with information diffusion happens. If we consider a static network at time t4, we only know that there is a closed triad in which A and B send messages mutually, and C receives from B and A, respectively. However, if we capture its temporal properties, more information will be preserved that B first receives from A, which indicates that A has a higher social power according to the social status theory [Waters, 2015]. Therefore, evolution dynamics and properties need to be well examined and preserved for temporal networks.

In literature, there are only a few works focus on temporal network embedding. For instance, HTNE [Zuo et al., 2018] considers the temporal network embedding via neighborhood formation process. M2DNE [Lu et al., 2019] studies micro- and macro-dynamics by taking edge dynamics and network evolution patterns into account. The former method only considers the influence of one node's neighbor formation sequence on the current neighbor. Nevertheless the establishment of a relationship between two nodes is an interacted process, and the neighbor formation sequence cannot reflect the law of network evolution very well. Besides from edge level, the latter takes the whole network's evolution into account. However, except the consideration of micro- and macro-dynamics, the influence from a mesoscopic view for temporal networks has been ignored.

Meso-dynamics has been widely used in mining complex networks, as well as social networks. It is crucial to understand the network structure and function of social systems [Huang et al., 2018]. Unlike micro-dynamics focusing on node and edge level, meso-dynamics considers the coupling effects of a small group of nodes and edges. Besides, it exhibits group properties with only a few nodes and edges, thus preserving group-aware high-order proximity. Usually, meso-dynamics is in the form of subgraph evolution, where subgraph patterns are also called network motifs. Since network motifs have been well studied, meso-dynamics can make full use of their correlations.

In this paper, we propose a novel temporal network embedding method with the consideration of meso-dynamics, named MTNE. In view of meso-dynamics, we focus on the simplest and fundamental motif - triad - in the networks. Specially, we first incorporate the triad dynamics into the Hawkes process. So that, our model can well capture the effects of past events of users inside a triad. Moreover, we adopt attention mechanism to specify the importance of different types of triads. Note that our method can be easily applied to model other motifs due to the generality of the Hawkes process. We test our model on several real-world datasets. The experimental results show that our proposed MTNE outperforms state-of-the-art baselines in both static and dynamic tasks.

The major contributions of our work are as follows:

• To our knowledge, we are the first to concentrate on temporal network embedding with meso-dynamics that preserves motif-aware high-order proximity.
• We propose a novel model (MTNE), which leverages Hawkes process to model motif evolution and design an attention mechanism to model the importance of motif structures.
• Experiment results on five real-world datasets show that our MTNE has better performance than several state-ofthe-art baselines in both static and dynamic tasks.

2 Preliminaries

In a temporal network, each edge indicates an event that happens between two nodes at a time point. Formally, given a temporal network G = (V, E, T ), where V and E indicate nodes and edges of the temporal network and T is the set of timestamps. A temporal edge etij ∈ E represents an event that is initiated by node vi together with node vj at time t.

Note that since node vi and node vj may arise multiple events at different time t, temporal edge etij represents distinct events while edge eij is only a static edge between node vi and node vj, and can be either directed or undirected. For example, in one mobile communication network, we can construct a static network based on the relationship among users. On the other hand, we can also build a temporal network to describe the interactions among users. In the temporal network, each temporal edge means a phone call between two users at a certain time. Once user vi calls user vj at time t, then a temporal edge etij establishes.

In this paper, we start with the simplest and fundamental motif - triad, and introduce the definition of temporal triad.

Definition 1: Temporal Triad. Given three nodes ∆ = (vi, vj, vk), if there are at least two temporal edges that involve the three nodes, -e.g., ∃et1 ij , et2 jk ∈ E - then we call ∆ a temporal triad. Specially, if there exists at least one temporal edge for any two nodes in a temporal triad, we call ∆ a temporal closed triad. If there exist two nodes in a temporal triad without any temporal edges, then we call ∆ a temporal open triad.

Network evolution is, in some sense, driven by the triadic closure process [Huang et al., 2015]. From a microscopic view, the triadic closure process describes how an open triad forms a closed triad. Given an open triad (vi, vj, vk) at time t1, where vi and vj do not know each other but they have a common friend vk. Now, if vk decides to introduce vi and vj and lets them know each other, there will be a connection between vi and vj and the open triad (vi, vj , vk) will become closed at time t2. Nevertheless, there is a problem that if there are multiple open triads which consist of vi and vj before time t1, we cannot accurately infer from the dataset which open triad determines the connection between vi and vj. We call all these temporal open triads as candidate temporal triads.

In this paper, we aim to represent the nodes in the temporal networks incorporating the influence of all candidate temporal triads. We formally define our problem as below.

Problem. Motif-Preserving Temporal Network Embedding. Given a temporal network G = (V, E, T ), during network evolution, we generate all candidate temporal triads for every node pair in V. Then, motif-preserving temporal network embedding aims to learn a mapping function f : V ↦→ Rd , where d is a positive integer indicating the number of embedding dimensions and d ≪ |V |. The objective of the function f is to not only preserve the feature of the network structure but also capture the influence of motif-based network evolution.

3 The ProposedModel

3.1 Model Overview

In this section, we propose MTNE, a novel model that is capable of learning desirable representations for nodes in temporal networks and simultaneously preserve the characteristics of motifs in the network. As illustrated in Figure 2, node pairs (i, j) and (p, q) belong to different open triads, respectively. Considered their different past temporal information, even if they have the same property, the generated embeddings for them in the new dimension would be different. Our proposed MTNE would capture such precise and diverse structural information - triad motif evolution property. Specifically, MTNE leverages Hawkes process to model motif evolution process. Then we can learn it using optimization techniques like stochastic gradient descent (SGD).

3.2 TriadMotif EvolutionModeling

As we know, the triad motif evolution process is influenced by the historical triad evolution events. Therefore, the Hawkes process [Hawkes, 1971] can be used to model triad motif evolution. We define the conditional intensity function as

where ˜λx,y(t) is the intensity of the new emerged temporal edge exy at time t, which also means the formation of certain triad that contains vx and vy at time t; µx,y denotes the base rate of establishing a connection between vx and vy, while ∆h is the candidate open triads that contains node vx and vy prior to time t. σ∆h (t) is the kernel function that represents the influence of history, which will decay over time. According to Eq. (1), we model the triad evolution process by modeling the base rate and past influence, respectively.

Base rate. Suppose the base rate between nodes will be high if they are similar to each other. So we can model the base rate as a function that measures the similarity between nodes. For brevity, we calculate the similarity using negative squared Euclidean distance. Specifically, suppose the node embeddings of node vx and vy are ux and uy respectively, then the base rate can be defined as

Influence of open triads. Likely, similarity function can also help us to model the influence of historical open triad motifs, say ∑ th<t σ∆h (t).

Specifically, we define the influence of one open triad (vx, vm, vy) as

where vm is the middle node of the open triad, ηx,m and ηy,m represent the strength of the internal relationship of the two connected node pairs in the open triad respectively. Note that the relationship between nodes can be established repeatedly in some temporary networks (e.g., mobile communication network, co-author network, etc.), ηx,m is calculated as the sum of a series of connection effects between vx and vm, i.e.,

where f(ux, um) is the similarity function between node vx and vm, i.e., f(ux, um) = -||ux-um||2 . κ(·) is the memory kernel function, which denotes the time decay effect. Here we have κ(t - tx,m) = e(-δx(t-tx,m)) , where δ is a discount rate that controls time decay effects. Note that δ is a node dependent parameter, which means that for each node, the history open triad can influence the current closure with different intensity. It can be learned during training.

Then we can get the influence of one open triad as

The value of the influence obtained in the above calculations are all negative values since the similarity is measured by negative Euclidean distance. However, the conditional intensity function should return a positive value. So we transfer ˜λx,y(t) to a positive real number by an exponential function, i.e, λx,y(t) = exp(˜λx,y(t)), and its value range is between 0 and 1, which accords with the range of the motif formation probability.

Influence of triad motifs. The influence of historical events is defined as the sum of historical open triad motifs' effects. Intuitively, different types of open triad would have different closing probabilities. Then, as shown in Figure 3, there exist nine types of open triad motifs considered its edge direction. According to [Huang et al., 2015], among all types of open triads, the open triad motif No.9 has the highest probability to become closed, of which both edges are bi-directional. Besides, the closure probability of No.2 is the lowest due to the phenomenon of assembled fans in social networks. Therefore, it is necessary to consider the motif evolution dynamics, especially the closure process of the open triad motifs when modeling σ∆h , which makes up conditional intensity function.

Inspired by attention mechanism that used in neural machine translation [Bahdanau et al., 2015], we define the weight of the n-th open triad motif using a softmax function as follows:

where sn indicates the influence of n-th type of triad motif in Figure 3. It will be also learned and updated during training. Therefore, the conditional intensity function can be re-formulated as,

where w∆h calculates the influence of the type of triad motif that ∆h belongs to.

Loss function. By modeling triad evolution with Hawkes process, we can infer the edge evolution with the consideration of candidate temporal triads. That is, given a node pair (vx, vy) before time t, considering candidate temporal triads H∆(t), the probability of forming connection between vx and

vy can be inferred by the conditional intensity as,

where y′ represents all nodes except vx in the network.

After taking a log function, the likelihood of edge formation for all node pairs in the network can be written as,

Since we have transferred the conditional intensity to a positive number by an exponential function, p(vx, vy|H∆(t)) is actually a softmax unit. Besides, in order to avoid to summarize the entire set of nodes when calculating Eq. (9), we use negative sampling techniques as in [Zuo et al., 2018]. Then the loss function of the connection between a node pair (vx, vy) at time t can be computed as follows,

where K is the number of negative nodes sampled according to the degree distribution Pn(v) ∝ d3/4 v , where dv is the degree of node v, and σ(x) = 1/(1 + e-x ) is the sigmoid function.

In experiments, the number of candidate temporal triads will affect computational cost. Thus we fix the maximum number of candidate temporal triads in this paper and discuss its influence in section 4.3.

Finally, we use Stochastic Gradient Descent (SGD) to optimize the loss function. After converging, we can get the learned node embeddings.

4 Experiments and Discussions

4.1 Experimental Setup

Datasets. We test MTNE on five different real-world datasets, say School [Fournet and Barrat, 2014], DBLP [Ley, 2009], Digg [Hogg and Lerman, 2012], Mobile [Huang et al., 2018], and Weibo [Zhang et al., 2013]. Their statistics is listed in Table 1.

Baselines. We compare the performance of MTNE against the following seven network embedding methods, including four static network embedding methods and four temporal network embedding methods, shown in Table 2.

Parameter settings. For all methods, the embedding dimension d is set as 64. For our proposed MTNE, the batch size, the learning rate of the SGD, the number of candidate temporal triads, and the number of negative samples are set to be 1000, 0.003, 5, 5, respectively, while for other baselines, we use the default parameters settings. For each experiment, we repeat 10 times and report the average value as the final results.

4.2 Experiment Performance

We validate our proposed model from two aspects: tasks for static networks and temporal networks. For the former, we first learn node embeddings and then treat them as features. We test two traditional tasks here: node classification and link prediction, and use precision, recall, and F1 as the measures. For the latter, we perform a temporal recommendation task and use precision and recall as measures.

Node classification. We train a logistic regression classifier using the learned node embeddings as features to predict node labels. We use School, Weibo, and DBLP datasets, and report the results in Table 3.

From the results, we can see that our method MTNE performs better than all baselines. Specifically, compared with methods for static network embedding (i.e., DeepWalk, LINE, GraRep, and Node2vec), the better performance of MTNE suggests that the evolutionary dynamics are of great importance for node classification. On the other hand, compared with methods for temporal network embedding (i.e., TNE, DynamicTriad, HTNE, and M2DNE), our method captures motif-aware high-order proximity by modeling motif evolution process, which increases the semantic meaning of the embeddings. Specifically, MTNE encodes motif features in the latent space and the nodes in the same motif are more likely to be in the same class, which further improves the performance of classification.

Link prediction. For the task of link prediction, we aim to predict whether there is an edge between the given node pair (vx, vy). We utilize |ux-uy| as the feature to train a Logistic Regression classifier, where ux and uy are embeddings of vx and vy respectively. In each dataset, we randomly choose 10, 000 edges as positive samples and 10, 000 unconnected node pairs as negative samples. The experiment results are shown in Table 4.

From the table, we can see that our method performs the best on all datasets, which again proves the effectiveness of our method. We believe the significant improvement is because that our method captures network structure features more accurately by modeling the motif evolution process, which is an essential feature for real network evolution, as discussed in [Huang et al., 2015].

Temporal recommendation. We study the effectiveness of MTNE for capturing temporal information in networks with the task of temporal recommendation. Specifically, given a testing timestamp t, we obtain the node embeddings in the network before time t and recommend possible new connections for the testing node after time t. We conduct experithe temporal information with network snapshots and do not consider the entire evolution process. Although HTNE and M2DNE consider the evolution process, they ignore the motif evolution process in the temporal network, which is one of the critical characteristics of network evolution.

4.3 Parameter Analysis

We then study the influence of some important parameters, that is, the number of candidate temporal triads, the number of negative samples, and the number of recommended nodes.

The number of candidate temporal triads. The number of candidate temporal triads is designed to preserve the time effects of triads and reduce computational cost. From Figure 4 (a), we can see that the Macro-F1 first increases along with the number of candidate temporal triads h when h < 5. Then, the Macro-F1 begins to drop. Therefore, for a balance between effectiveness and efficiency, we set the number to 5 in our default experiment settings.

The number of negative sample. We then test how the number of negative samples influences the performance. The results are shown in Figure 4 (b). From the figure, we can see that Macro-F1 is very low when the number of negative sample is less than 5, and then increases slowly after 5.

The number of recommended nodes. We now test the influence of the number of recommended nodes in the task of temporal recommendation. Take Mobile data as an example, and we test the results with top-5, 10, 15, 20 nodes, respectively. The results are shown in Table 6.

5 RelatedWork

We discuss related work from two parts: static network embedding and temporal network embedding.

(b)

Figure 4: Impacts of candidate temporal triads and negative samples on dblp. The X-axis represents the number of of candidate temporal triads (a) and negative samples (b), and the Y-axis represents the Macro-F1 of node classification.

ments on School, Digg, and Mobile, and use data from the first 80% of the period as a training set the rest as a testing set.

For each test node vi in the network, we predict the top-10 possible new connections for vi after t. We use the negative squared Euclidean distance between node embeddings as the ranking score, and obtain the top-10 nodes with the highest score as our predicted nodes. The experimental results are reported in Table 5 with respect to recall and precision.

From the results, we can see that MTNE outperforms all the baselines. The improvement confirms that the triad motif evolution process proposed in MTNE captures the evolution patterns of the temporal network to some extent. Also, the dynamic methods (i.e., TNE, DynamicTriad, HTNE, M2DNE, and MTNE) perform better than the static methods (i.e., DeepWalk, LINE, GraRep, and Node2vec), which demonstrates the importance of temporal information in the network. In the dynamic methods, TNE and DynamicTriad perform relatively worse, which might because they only model Static network embedding. Since Deepwalk [Perozzi et al., 2014] first represents the nodes in networks, a significant amount of progress have been made in network representation learning. In order to represent static networks, researchers focus on various network information, aiming to preserve the proximity of neighbor nodes or high-order proximities among nodes. For example, Node2vec [Grover and Leskovec, 2016] preserves neighbor nodes, Line [Tang et al., 2015] preserves first- and second-order proximities, MNMF [Wang et al., 2017] preserves communities, and GraRep [Cao et al., 2015] preserves k-order proximities, RUM [Yu et al., 2019] preserves motifs. More related work can refer to [Cui et al., 2018].

Temporal network embedding. There are also several attempts towards dynamic network embedding, especially temporal network embedding. In dealing with temporal information, two solutions are usually used. The first is to divide the time into several snapshots [Du et al., 2018]. For example, [Zhu et al., 2016] proposes a matrix factorization based method for representing dynamic network snapshots. DANE [Li et al., 2017] and DHPE [Zhu et al., 2018] solve the dynamic network embedding problem with matrix perturbation theory. DynamicTriad [Zhou et al., 2018] models the dynamics via triadic closure process and obtains node embeddings at each snapshot.

On the other hand, in order to consider the full dynamics over time, the second line of works try to consider the whole evolution process [Nguyen et al., 2018]. For instance, HTNE [Zuo et al., 2018] represents temporal networks with integrating the Hawkes process with consideration of neighborhood formation. Netwalk [Yu et al., 2018] proposes a deep neural network and reservoir sampling-based network representation learning framework for real-time anomaly detection. M2DNE [Lu et al., 2019] captures both micro- and macro-dynamics of networks during evolution.

However, all the methods mentioned above either represent nodes on each snapshot or only consider limited dynamics and structures for temporal network embedding. None of them capture motif proximities in temporal network embedding from a mesoscopic view.

6 Conclusion

In this paper, we investigate the problem of representing nodes in temporal networks by incorporating the influence of meso-dynamics, in terms of the triad. In detail, we propose MTNE, a novel embedding model that leverages the Hawkes process to stimulate the triad formation process, and combines attention mechanism to distinguish the importance of different types of triads better. Experiments on different real-world networks demonstrate that MTNE achieves the best performance, compared with several state-of-the-art techniques in both static and dynamic tasks, including link prediction, node classification, and link recommendation. In the future, we will perform our model with other motifs, say four-node motif or above in real network applications.

Acknowledgments

The research was supported by National Natural Science Foundation of China (No. 61802140, U1936104, 61972442) and CCF-Tencent Open Fund.