DECRL: A Deep Evolutionary Clustering Jointed Temporal Knowledge Graph Representation Learning Approach

GNNs and variants of recurrent neural networks (RNNs) are commonly integrated to model graph structural information and temporal dependency within TKGs, respectively bai2023 ; wu2020 ; li2021temporal ; li2022 . For example, TeMP wu2020 and RE-GCN li2021temporal both utilize relation-aware GCN schlichtkrull2018 to model the influence of neighbor entities and apply GRUs to model the temporal dependency. TiRGN li2022 employs multi-relational GNNs to model graph structural information, and utilizes GRUs to capture the temporal dependency across sequential timestamps. However, these approaches often resort to stacking multiple layers to model the influence of distant neighbors, which may lead to the over-smoothing problem.

Recent research advancements have introduced paths li2021search ; han2020 ; liu2022TLogic to enhance the modeling capability of the latent pairwise correlations between entities. For example, xERTE han2020 utilizes a time-aware graph attention mechanism to obtain and exploit local subgraphs. TLogic liu2022TLogic employs a time-based random walk strategy to acquire logical paths. Furthermore, some researchers have leveraged derived structures, e.g., communities zhang2022 , entity groups tang2023 , and hypergraphs tang2024 , to model high-order correlations among entities. For example, EvoExplore zhang2022 utilizes a temporal point process enhanced by a hierarchical attention mechanism to establish dynamic communities for modeling latent correlations among entities. DHyper tang2024 utilizes hypergraph neural networks to model high-order correlations among entities and among relations.

While the promising results of introducing derived structures, existing approaches lack the capability to capture the temporal evolution of high-order correlations in TKGs. To address this gap, we propose DECRL, which is the first work to integrate deep evolutionary clustering approaches into TKGs. DECRL jointly optimizes TKG representation learning with evolutionary clustering to capture the temporal evolution of high-order correlations.

Existing deep evolutionary clustering approaches employ different strategies for discovering stable clusters folino2013 ; ma2017 ; yang2023 ; ma2020 ; you2021 ; yao2021 . For example, DYNMOGA folino2013 employs a deep evolutionary clustering approach designed to identify evolving communities within dynamic networks, which treats the process as a multi-objective optimization problem aimed at cluster stability. sE-NMF ma2017 implements linear fusion of adjacency matrices across timestamps to enhance the temporal stability of clusters. Both DNETC yang2023 and CDNE ma2020 use constructed temporal smoothness loss functions to ensure a consistent and stable evolution of clustering results through successive timestamps. TRNNGCN yao2021 introduces a decay matrix to assess the influence of historical clustering results, thereby stabilizing the current clustering configuration.

These approaches straightforwardly incorporate prior clustering results with current timestamp results over time under the presumption that clustering results are relatively stable across different timestamps. However, the nuances between similar clusters are difficult to recognize in this way. In TKG representation learning, it is necessary to discern the subtle differences in high-order correlations. To bridge this gap, in our work, a cluster-aware unsupervised alignment mechanism is introduced, which ensures the precise one-to-one alignment of soft overlapping clusters across timestamps, thereby maintaining the temporal smoothness of clusters over successive timestamps.

The proposed DECRL approach is illustrated in Figure 1. At each timestamp, entity and relation representations updated by the cluster graph message passing module are merged with input representations from the previous timestamp using a time residual gate, serving as the input for the current timestamp. The multi-relational interactions among entities are modeled by the relation-aware GCN. The deep evolutionary clustering module captures the temporal evolution of high-order correlations among entities, maintaining the temporal smoothness of clusters over successive timestamps through an unsupervised alignment mechanism. The implicit correlation encoder captures the latent correlations between any pair of clusters, enabling message passing within the cluster graph to update entity representations. Finally, the attentive temporal encoder captures temporal dependencies among entity and relation representations across timestamps, integrating them with temporal information for future event prediction. The computational complexity of DECRL can be found in Appendix A.1.

The entity graph $G_{\text{e}}^{t}=(V_{\text{e}}^{t},E_{\text{e}}^{t})$ is constructed based on the historical events at timestamp $t$, which can be used to capture the structural dependency among concurrent events. Since the entity graph is a multi-relational graph, relation-aware GCN schlichtkrull2018 is utilized to model the structural dependency, which is formulated as:

where $\boldsymbol{h}_{\text{s}}^{t,l}$, $\boldsymbol{h}_{\text{o}}^{t,l}$, and $\boldsymbol{h}_{\text{r}}^{t,l}$ denote the $l^{th}$ layer representations of subject entity $s$, object entity $o$, and relation $r$ at timestamp $t$, respectively. $\boldsymbol{W}_{1}$ and $\boldsymbol{W}_{2}$ are learnable parameters for aggregating neighbor entity representations and self-loop, respectively. ${d_{\text{o}}}$ denotes the in-degree of object entity $o$. Initially, entities are assigned random representations based on their in-degree, such that entities with the same in-degree have the same initial representations, thereby efficiently accelerating the update process of entity representations. Relations are given with the random initial representations. For simplicity, the subscript $l$ of variables is omitted in the following sections without causing ambiguity.

The representation of the relation $r$ at timestamp $t$ is influenced by the $r$-related entity representations at timestamp $t$ and its representation at timestamp $t-1$. The updating of the relation representation is formulated as $\boldsymbol{h}_{\text{r}}^{t}=\mathrm{pooling}[\boldsymbol{e}^{t}_{\mathcal{V}^{t}_{\text{r}}};\boldsymbol{h}_{\text{r}}^{t-1}]$, where $[;]$ denotes the concatenation operation. $\mathrm{pooling}$ denotes the mean pooling operation. $\boldsymbol{e}^{t}_{\mathcal{V}^{t}_{\text{r}}}$ denotes $r$-related entity representations at timestamp $t$, where $\mathcal{V}^{t}_{\text{r}}=\{i|(i,r,o,t)\,or\,(s,r,i,t)\in\mathcal{G}^{t}\}$.

A country entity may be affiliated with different international political organizations at different timestamps within TKGs. Thus, the fuzzy c-means clustering method pu2024 is utilized to obtain the soft overlapping clusters, which outputs the membership matrix between entities and clusters by optimizing the object function as follows:

where ${N_{\text{e}}}$ and ${N_{\text{c}}}$ are the number of entities and clusters, respectively. ${u}_{i,j}^{t}$ denotes the membership degree of the entity representation $\boldsymbol{e}_{i}^{t}$ to the cluster centroid $\boldsymbol{\mu}_{j}^{t}$ at timestamp $t$. $m$ denotes the fuzzy smoothing hyper-parameter, which is typically set to a value greater than $1$. $\langle\cdot\rangle$ denotes the dot product. $\|\cdot\|$ denotes the norm of a vector. Then, the representation of clusters is formulated as:

where $\boldsymbol{c}_{j}^{t}$ denotes the representation of cluster $j$ at timestamp $t$, weighted by the membership degree of different entities to the cluster.

The maximum weight matching can be found in polynomial time using the Hungarian algorithm kuhn1955 . Herein, a cluster-aware Hungarian matching algorithm is introduced to ensure a smooth one-to-one alignment of clusters across timestamps. The cluster-aware Hungarian matching algorithm quantifies the similarity between clusters of consecutive timestamps, i.e., $t-1$ and $t$, which creates an affinity matrix $A$, where each element ${a}_{j,k}$ represents the similarity between the cluster $j$ at timestamp $t-1$ and the cluster $k$ at timestamp $t$:

With the affinity matrix established, the cluster-aware Hungarian algorithm seeks an optimal assignment that maximizes the sum of similarities across matched clusters. It is formulated as an optimization problem: $\max_{\pi}\sum_{j=1}^{N_{\text{c}}}{a}_{j,\pi(j)}$, where $\pi$ is the permutation function representing the one-to-one alignment between clusters of consecutive timestamps. Therefore, $\pi(j)$ denotes the index of the cluster at timestamp $t$ matched with the cluster $j$ at timestamp $t-1$.

Subsequently, the fused cluster representations are computed by taking a weighted combination of the cluster representations at consecutive timestamps, which is formulated as:

where $\beta$ is the fusion weight, which indicates the relative contribution of each cluster representation at consecutive timestamps to the fused cluster representation.

What’s more, it is essential to ensure the temporal smoothness of these cluster representations across consecutive timestamps. To this end, a temporal smoothness loss is introduced to penalize significant deviations of cluster representations across consecutive timestamps, which is formulated as:

Due to the intricate relationships and alliances formed among international political organizations, it is crucial to capture the latent correlations between clusters for event prediction. Herein, an implicit correlation encoder is proposed to capture the latent correlations between any pair of clusters. The cluster graph is designed to be a fully connected graph to avoid missing any relevant information between clusters. The representations of the latent correlations are formulated as:

where $\boldsymbol{c}_{i}^{t}$ and $\boldsymbol{c}_{j}^{t}$ are representations of the cluster $i$ and $j$ at timestamp $t$, respectively. $\varphi$ is the transformation function, which is implemented by the multi-layer perceptron.

It is worth noting that clusters exhibit varying degrees of interaction, characterized by different intensities of latent correlations. Thus, we quantify the intensity of latent correlations between clusters, which is formulated as:

where $\sigma$ is the sigmoid function, which ensures the resulting correlation intensity bounded between $0$ and $1$. $\mathrm{Conv}(\cdot)$ represents the convolution operation.

The intensity of the latent correlations between clusters varies in the short term and intensifies over time; a higher frequency of interactions indicates a stronger latent correlation. To this end, we construct a global graph, which is a static graph composed of all events from the training set. The spectral clustering approach is then applied to this global graph to obtain global clusters $\boldsymbol{c}_{i}^{\mathrm{global}}$. The similarity between global clusters is used to enhance the intensity of latent correlations between cluster pairs, which is formulated as:

where $\boldsymbol{c}_{\pi^{t}(i)}^{\mathrm{global}}$ and $\boldsymbol{c}_{\pi^{t}(j)}^{\mathrm{global}}$ are global clusters matched with the cluster $i$ and $j$ at timestamp $t$, respectively. ${m}_{i,j}^{t}$ is the similarity between the global cluster $i$ and $j$ at timestamp $t$. $\widehat{q}_{i,j}^{t}$ is the enhanced intensity of latent correlations, which also integrates structural information from the global graph.

In the message passing process of the cluster graph, the stronger the intensity of the latent correlation, the more critical the latent correlation is, and vice versa. The aggregation operation is formulated as:

where $\widehat{q}_{i,j}^{t}$ and $\boldsymbol{s}_{i,j}^{t}$ denote the enhanced intensity and the representation of latent correlation calculated by Equation 9 and Equation 7, respectively. Then, the representation of clusters is updated through:

To implement information transfer from clusters to individual entities, we use the membership matrix from Section 4.2. Entity representations are updated based on their associated cluster representations, which are formulated as $\boldsymbol{e}_{i}^{\prime t}=\sum_{j=1}^{N_{\text{c}}}\boldsymbol{u}_{i,j}^{t}\boldsymbol{\widehat{c}}_{j}^{t}$, where ${N_{\text{c}}}$ denotes the number of clusters.

The time residual gate is introduced to combine updated entity and relation representations with input representations of the current timestamp through a weighted mechanism. This approach preserves inherent characteristics while capturing the temporal evolution of entities and relations. For simplicity, the subscripts $i$ and $j$ of variables are omitted in the following sections without causing ambiguity. The final updated representations at timestamp $t$ are formulated as:

where $\boldsymbol{H}_{\theta}^{t}$ denotes the entity or relation representations updated by the cluster graph message passing module at timestamp $t$. $\boldsymbol{H}^{t-1}$ denotes the output of entity or relation representations at timestamp $t-1$, and also is the input of timestamp $t$. The time residual gate, i.e., $\boldsymbol{X}^{t}$, determines the inherent characteristics to be preserved, where $\sigma$ is the sigmoid function. $\boldsymbol{W}_{3}$ and $\boldsymbol{b}$ are learnable parameters.

In the context of sequence modeling, the attentive temporal encoder is introduced to capture the temporal dependency among the final updated representations across timestamps. The position-enhanced representations of entity and relation are formulated as:

where $\boldsymbol{H}^{t}$ is the final updated representation of entity or relation at timestamp $t$. $[;]$ denotes the concatenation operation. $\Phi(t)$ is the time position encoder. $d$ denotes the value of the representation dimension. $\omega_{1}$ to $\omega_{d}$ are learnable parameters. $\tau^{t}$ is the timestamp. Then, the temporal dependency is captured by a position-enhanced self-attention mechanism based on representation sequence $\boldsymbol{z}^{1:T-1}=\{\boldsymbol{z}^{1},\boldsymbol{z}^{2},...,\boldsymbol{z}^{T-1}\}$. For simplicity, the subscript $t$ of variables is omitted in the following sections. The integrated entity or relation representation is formulated as:

where $\boldsymbol{W}_{q}$ and $\boldsymbol{W}_{k}$ are learnable parameters. $\alpha_{m,n}$ is the attention weight. $\overline{\boldsymbol{h}}_{m}$ is the integrated representation of entity or relation, which integrates the temporal information.

ConvTransE shang2019 is employed as the decoder of DECRL, which predicts the probability of each relation between an entity pair, which is formulated as:

where $\hat{\boldsymbol{r}}$ is the probability vector of relations. $\sigma$ is the sigmoid function. $\boldsymbol{H}_{\text{r}}$ is the relation representation matrix, each row of which corresponds to an integrated relation representation $\overline{\boldsymbol{r}}$. $\mathrm{ConvTransE}(\cdot)$ contains a one-dimensional convolution layer and a fully connected layer.

The event prediction training objective is minimizing the cross-entropy loss, which is formulated as:

where $S$ and $N_{\text{r}}$ denote the numbers of samples in the training set and relations, respectively. $y_{i,j}$ denotes the label of relation $j$ for sample $i$, of which the element is $1$ if the event occurs, otherwise $0$. $p_{i,j}$ is the predicted probability of relation $j$ for sample $i$, calculated by Equation 15.

Finally, the total loss for DECRL is formulated as:

where $\lambda$ is a hyper-parameter that controls the trade-off between event prediction and temporal smoothness, which is bounded between $0$ and $1$.

We evaluate DECRL on seven real-world datasets: ICEWS14 trivedi2017 , ICEWS18 jin2020 , ICEWS14C tang2024 , ICEWS18C tang2024 , GDELT leetaru2013gdelt , WIKI leblay2018deriving , and YAGO jin2020 . The ICEWS14 and ICEWS18 datasets span January 1, 2014, to December 31, 2014, and January 1, 2018, to October 31, 2018, respectively. We derive ICEWS14C and ICEWS18C datasets by filtering the original datasets to focus exclusively on events involving countries. The GDELT dataset spans January 1, 2018, to January 31, 2018. The WIKI and YAGO datasets are subsets of the Wikipedia history and YAGO3 mahdisoltani2013yago3 , respectively. Dataset statistics and experimental settings are detailed in Appendices A.2 and A.3.

DECRL is compared against 12 SOTA TKG representation learning approaches, categorized into shallow encoder-based approaches, i.e., TTransE leblay2018deriving and HyTE dasgupta2018hyte , DNN-based approaches, i.e., RE-NET jin2020 , Glean deng2020dynamic , TeMP wu2020 , RE-GCN li2021temporal , DACHA chen2021dacha , and TiRGN li2022 , and derived structure-based approaches, i.e., TITer sun2021timetraveler , EvoExplore zhang2022 , GTRL tang2023 , and DHyper tang2024 . All baselines are evaluated following consistent experimental settings with well-tuned hyper-parameters. The detailed descriptions of compared baselines can be found in Appendix A.4.

Tables 1, 2, and 3 display the MRR and Hits@1/3/10 results of event prediction on ICEWS14, ICEWS18, ICEWS14C, ICEWS18C, and GDELT datasets. “*” denotes the statistical superiority of DECRL over compared approaches based on pairwise t-tests at a 95% confidence level. The best results are highlighted in bold, while the second-best results are underlined. Notably, DECRL consistently exhibits superior performance, yielding average improvements of 13.24%, 12.98%, 10.42%, and 14.68% in MRR and Hits@1/3/10 metrics, respectively. These findings affirm the efficacy of integrating deep evolutionary clustering for capturing the temporal evolution of high-order correlations among entities. Furthermore, it is evident that approaches leveraging derived structures generally outshine those relying on DNNs, which in turn surpass approaches employing shallow encoders.

Since most approaches do not report event prediction results on WIKI and YAGO datasets, we compare DECRL with TiRGN and DHyper, both of which provide results on these datasets, as shown in Table 4. Furthermore, TiRGN and DHyper are the SOTA DNN-based approach and the SOTA derived structure-based approach, respectively. As a result, DECRL shows improvements of 0.29% and 0.25% over the runner-up, DHyper, on WIKI and YAGO datasets, respectively, underscoring its effectiveness. Detailed entity prediction results are presented in Appendix A.6 due to space limitation.

To dissect the contributions of each module within DECRL, we conduct the ablation study on ICEWS14. The detailed descriptions of variants are as follows:

• •

  DECRL-w/o-alignment: Removing unsupervised alignment mechanism.

• •

  DECRL-w/o-fusion: Removing fusion operation between clusters across timestamps.

• •

  DECRL-w/o-ICE: Removing implicit correlation encoder, resulting in a fully connected graph where all edges are assigned uniform weights.

• •

  DECRL-w/o-global-graph: Removing the guidance of the global graph on the assignment of different interaction intensities to different cluster pairs.

• •

  DECRL-w/o-$\mathcal{L}_{\mathrm{temporal}}$: Removing the temporal smoothness loss term.

Table 5 displays the MRR and Hits@1/3/10 results of DECRL and the variants on ICEWS14. From the ablation study, several conclusions can be drawn: Firstly, the most substantial performance degradation is observed in the DECRL-w/o-fusion variant, which indicates the effectiveness of capturing the temporal evolution of high-order correlations among entities. Moreover, the performance degradation of the DECRL-w/o-global-graph variant justifies the effectiveness of leveraging structural information from the global graph for guiding the assignment of different interaction intensities to different cluster pairs. Lastly, the performance degradation of DECRL-w/o-alignment and DECRL-w/o-$\mathcal{L}_{\mathrm{temporal}}$ variants shows the importance of preserving the temporal smoothness of clusters over successive timestamps.

To demonstrate the efficacy of DECRL, we conducted a case study with two variants: DECRL-w/o-alignment and DECRL-w/o-fusion, both of which are elaborated in Sub-section 5.3. In Figure 2, we utilize t-SNE Laurens2021tsne for the visualization of entity representations on ICEWS14C, where red dots represent individual entities in the TKGs, with their groupings indicating entity clusters. Notably, the entities marked in Figure 2, i.e., China, Thailand, Vietnam, Laos, Malaysia, Philippines, and Cambodia, are countries in East Asia participating in the Belt and Road Initiative. “Middle” and “Final” denote the entity representations obtained after training at the penultimate epoch and the final epoch, respectively, for different variants.

By comparing the visualizations in the first row of sub-figures in Figure 2, we observe that DECRL exhibits the best entity clustering phenomena during the mid-training phase. By comparing the visualizations in the second row of sub-figures in Figure 2, Figure 2(d) (Final DECRL) showcases pronounced clustering phenomena, and inter-cluster distances indicate significant differences in clusters, i.e., international political organizations. Figure 2(e) (Final DECRL-w/o-alignment) demonstrates moderate clustering phenomena among countries, but inter-cluster distances are not significant enough. This observation implies that the lack of precise one-to-one alignment may lead to proximity between different clusters. Figure 2(f) (Final DECRL-w/o-fusion, which only models high-order correlations without temporal evolution) exhibits increased inter-cluster distances, with less distinct clustering phenomena. The comparison between Figure 2(d) (Final DECRL) and Figure 2(f) (Final DECRL-w/o-fusion) shows that capturing temporal evolution leads to better entity representations, as indicated by larger inter-cluster distances and tighter intra-cluster groupings. Comparing the first and third rows of Figure 2 further highlights the training progression, where modeling temporal evolution gradually enhances cluster separation and tightens the grouping of entities within clusters. This demonstrates that the capability of DECRL to model the temporal evolution of high-order correlations significantly enhances its ability to capture more nuanced cluster representations. Additional case study details are provided in Appendix A.7.