## Online Detection of Anomalies in Temporal Knowledge Graphs with Interpretability

JIASHENG ZHANG, School of Computer Science and Engineering, University of Electronic Science and Technology of China, China

REX YING,

Department of Computer Science, Yale University, USA

JIE SHAO ∗ , Shenzhen Institute for Advanced Study, University of Electronic Science and Technology of

China, China

Temporal knowledge graphs (TKGs) are valuable resources for capturing evolving relationships among entities, yet they are often plagued by noise, necessitating robust anomaly detection mechanisms. Existing dynamic graph anomaly detection approaches struggle to capture the rich semantics introduced by node and edge categories within TKGs, while TKG embedding methods lack interpretability, undermining the credibility of anomaly detection. Moreover, these methods falter in adapting to pattern changes and semantic drifts resulting from knowledge updates. To tackle these challenges, we introduce AnoT, an efficient TKG summarization method tailored for interpretable online anomaly detection in TKGs. AnoT begins by summarizing a TKG into a novel rule graph, enabling flexible inference of complex patterns in TKGs. When new knowledge emerges, AnoT maps it onto a node in the rule graph and traverses the rule graph recursively to derive the anomaly score of the knowledge. The traversal yields reachable nodes that furnish interpretable evidence for the validity or the anomalous of the new knowledge. Overall, AnoT embodies a detector-updater-monitor architecture, encompassing a detector for offline TKG summarization and online scoring, an updater for real-time rule graph updates based on emerging knowledge, and a monitor for estimating the approximation error of the rule graph. Experimental results on four real-world datasets demonstrate that AnoT surpasses existing methods significantly in terms of accuracy and interoperability. All of the raw datasets and the implementation of AnoT are provided in https://github.com/zjs123/ANoT.

CCS Concepts: · Computing methodologies → Anomaly detection Temporal reasoning ; .

Additional Key Words and Phrases: Temporal knowledge graph, Anomaly detection, Graph summarization

## ACMReference Format:

Jiasheng Zhang, Rex Ying, and Jie Shao. 2024. Online Detection of Anomalies in Temporal Knowledge Graphs with Interpretability. Proc. ACM Manag. Data 0, 0, Article 0 ( 2024), 26 pages. https://doi.org/XXXXXXX. XXXXXXX

## 1 Introduction

Many human activities, such as political interactions [14] and e-commerce [30], can be effectively represented as time-evolving graphs with semantics, which are referred to as temporal knowledge graphs (TKGs). These TKGs are dynamic directed graphs characterized by node and edge categories.

∗ Corresponding author.

Authors' Contact Information: Jiasheng Zhang, School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, China, zjss12358@std.uestc.edu.cn; Rex Ying, Department of Computer Science, Yale University, New Haven, Connecticut, USA, rex.ying@yale.edu; Jie Shao, Shenzhen Institute for Advanced Study, University of Electronic Science and Technology of China, Shenzhen, China, shaojie@uestc.edu.cn.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org.

© 2024 Copyright held by the owner/author(s). Publication rights licensed to ACM.

ACM 2836-6573/2024/0-ART0

https://doi.org/XXXXXXX.XXXXXXX

Fig. 1. An illustration of different types of anomalies in TKGs and how anomalies relate to preserved knowledge.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00872v2-figure-d9df32cc-bc29-4c9d-90ee-763f6b6e669b.jpg)

In this context, nodes represent entities in the real world (e.g., United States ), while labeled edges signify the relations between these entities (e.g., Born In ). Each edge in conjunction with its connected nodes can constitute a tuple ( 𝑠, 𝑟, 𝑜, 𝑡 ) that encapsulates a piece of real-world knowledge, where 𝑠 and 𝑜 denote the subject and object entities, 𝑟 denotes the relation, and 𝑡 represents the occurrence timestamp of the knowledge.

While TKGs have demonstrated their value across various applications [22, 63], they often contain numerous anomalies that can significantly impede their reliability. As illustrated in Figure 1, TKG construction relies on automatic extraction from unstructured text [64]. However, existing extraction techniques often encounter conceptual confusion [36] and inaccurate relation matching [46], potentially introducing noisy tuples with erroneous entities or relations, termed as conceptual errors . Furthermore, ongoing interactions in the real world lead to the formation of new knowledge or render existing knowledge obsolete. However, knowledge-updating processes are often insufficient and delayed [48], resulting in either the omission of new knowledge or the retention of invalid knowledge, termed missing errors and time errors . Specifically, these errors are indicated by their conflicts with preserved knowledge. Conceptual errors conflict with the interaction preference of entities, while time errors conflict with other timely updated knowledge in their time order. The missing errors are valid knowledge not included in TKGs and should have few conflicts. TKG anomaly detection refers to detecting conceptual, time, and missing errors by measuring conflicts. Unfortunately, this field receives little attention.

One closely related research field is dynamic graph anomaly detection [44], aimed at identifying abnormal connections in time-evolving graphs. However, existing methods primarily rely on simple structural properties, such as connectivity [1] or clusters [34], thus failing to capture the intricate patterns present in TKGs such as relational closures [61] and temporal paths [14]. Furthermore, these methods do not consider the semantic attributes of nodes and are thus ineffective in handling the rich semantics introduced by node and edge categories. Another related field is TKG embedding [50], which aims to represent entities and relations as low-dimensional vectors for downstream tasks such as link prediction [42]. While these vectors can also be utilized for anomaly scoring [26], they face limitations due to the requirement of substantial training data [18] and the absence of

interpretability [27], making their anomaly detection less convincing. Moreover, the semantics of entities and graph patterns change as TKGs continue to update. Since these methods learn fixed vectors, they struggle to adapt to online changes. In summary, TKG anomaly detection encounters three primary challenges: CH1. Be interpretable to provide evidence for the detection results; CH2. Capturing complex patterns arising from entity and relation semantics and temporal relevance; CH3. Handling semantic and pattern changes caused by knowledge updates.

In this paper, we propose AnoT, a novel TKG summarization method for online detection of anomalies. It distills TKG into an interpretable rule graph and walks on it to gather evidence of knowledge validity. For CH1, AnoT conceptualizes observed knowledge as atomic rules, distilling interaction patterns within TKGs into concept triples that are both concise and human-readable. By mapping new knowledge as atomic rules, they can interpret how new knowledge complies or conflicts with existing patterns, and thus give evidence of the decision. Moreover, by identifying these discrepancies, AnoT can offer guidelines on correcting anomalous knowledge. For CH2, AnoT advances the utility of atomic rules by associating them through two common occurring relationships: chain and triadic occurrence. We formulate this association results as a rule graph, with nodes representing interaction patterns and directed edges indicating their sequential relationships. This novel structure enables the flexible inference of complex patterns by walking on it. For CH3, given the rule graph, the semantic and pattern changes can be easily reformed as editions on its nodes and edges, which provides a precise and scalable method for uniformly managing online changes. Additionally, we propose an error approximation strategy to determine the refresh time of the rule graph. Conceptually, AnoT is composed of three elements: a detector that constructs the rule graph and evaluates new knowledge, an updater that revises the rule graph based on new knowledge, and a monitor that estimates the rule graph's availability. Based on the rule graph, we propose static scores (measuring interaction preference conflicts) to detect conceptual errors and temporal scores (measuring occurrence order conflicts) to detect time errors. Consequently, the missing errors can be filtered as knowledge with low static and time scores during walking on the rule graph. Our contributions are as follows:

- · To the best of our knowledge, we are the first to study anomaly detection for TKGs. We propose an accurate and interpretable solution AnoT for this problem.
- · We are the first to study the method and application of TKG summarization. We propose the rule graph to effectively summarize TKGs, and verify its usage in anomaly detection.
- · Extensive experiments on four real-world TKGs justify that ANoT can accurately detect anomalies with efficiency while being interpretable. It outperforms existing methods by an average of 11.5% in AUC and 13.6% in precision.

## 2 Related Work

Dynamic graph anomaly detection. Existing methods fall into two categories. One is statistical methods, which leverage the shallow mechanisms to extract the structural information [12, 13, 34, 39]. For example, CAD [47] detects abnormal edges by tracking changes in structure and weight. DynAnom [21] uses the dynamic forward push algorithm to calculate the personalized PageRank vector for each node. AnoGraph [5] extends the count-min sketch data structure to detect anomalous edges through dense subgraph searches. F-FADE [8] models the time-evolving distributions of node interactions using frequency factorization. However, they cannot capture complex patterns brought by entity and relation semantics in TKGs. The other is deep learning-based methods, which detect anomalies by learning vector representations for nodes [2, 15, 32, 62]. AEGIS [11] proposes a graph differentiation network to learn node representations. Netwalk [59] combines random walk and a dynamic clustering-based model to score anomalies. AER [16] uses an anonymous representation strategy to identify edges by their local structures. TADDY [32] uses a dynamic graph transformer

model to aggregate spatial and temporal information. However, they lack enough high-quality labels [18] and the learned representations are not interpretable, making their detection less convincing.

TKG embedding. Factorization-based methods [50, 57, 60] regard TKGs as 4-order tensors and use tensor factorization for embeddings. TNT [28] builds on the complex vector model ComplEx [49] with temporal regularization. Timeplex [25] extends TNT by capturing the recurrent nature of relations. TELM [54] learns multi-vector representations with canonical decomposition. However, they learn tensors with fixed shapes, limiting their ability to handle new entities and timestamps. Diachronic embedding-based methods [10, 56] model entity representations as time-related functions. DE-simple [20] uses nonlinear operations to model various evolution trends of entity semantics. ATiSE [55] uses multi-dimensional Gaussian distributions to model the uncertainty of entity semantics. TA-DistMult [19] uses a sequence model for time-specific relation representations. However, they over-simplify the evolution of TKG and ignore the graph structure. GNN-based methods [31, 37, 40] employ the message-passing mechanism to simulate the entity interactions. TeMP [52] uses self-attention to model the spatial and temporal locality. RE-GCN [29] auto-regressively models historical sequence and imposes attribute constraints on entity representations. However, they lack interpretability and cannot handle online changes.

Graph summarization. Graph summarization is closely related to anomaly detection since it aims to find general patterns in data, and thus in turn can reveal anomalies [4, 7]. Many studies on knowledge graph summarization have focused on query-related summaries [53] and personalized summaries [43], while KGist [4] learns inductive summaries by introducing root graphs. However, they ignore the temporality of knowledge. Recent efforts have focused on dynamic graph summarization [23]. TimeCrunch [45] uses temporal phrases to describe the temporal connectivity. PENminer [3] mines activity snippets' persistence in evolving networks. However, they only focus on evolving connectivity and fail to handle rich semantics in TKGs. In this paper, we propose AnoT, a scalable and information-theoretic method for inductive TKG summarization.

## 3 Preliminaries

## 3.1 Temporal Knowledge Graph

Atemporal knowledge graph is denoted as G = (E R T F) E , , , . and R are entity set and relation set, respectively. T is the set of observed timestamps and F is the set of facts. In real-world scenarios, E T , , and F will be continuously enriched. Each tuple ( 𝑠, 𝑟, 𝑜, 𝑡 ) ∈ F connects the subject and object entities 𝑠, 𝑜 ∈ E via a relation 𝑟 ∈ R in timestamp 𝑡 ∈ T , which means a unit knowledge (i.e., a fact). We represent the connectivity of G in each timestamp 𝑡 with a |E| × |E| × |R| adjacency tensor 𝐴 𝑡 , where 1 represents that the entities are connected by the relation in timestamp 𝑡 . There are two common occurring relationships exist in TKGs. One is chain occurring defined as {( 𝑠, 𝑟 𝑖 , 𝑜, 𝑡 𝑖 ) → ( 𝑠, 𝑟 𝑗 , 𝑜, 𝑡 𝑗 )| 𝑡 𝑗 ≥ 𝑡 𝑖 } , e.g., ( 𝑂𝑏𝑎𝑚𝑎,𝑊𝑖𝑛𝑡ℎ𝑒𝑆𝑒𝑙𝑒𝑐𝑡𝑖𝑜𝑛,𝑈𝑛𝑖𝑡𝑒𝑑𝑆𝑡𝑎𝑡𝑒𝑠, 2008 11 04 / / ) → ( 𝑂𝑏𝑎𝑚𝑎,𝑃𝑟𝑒𝑠𝑖𝑑𝑒𝑛𝑡𝑜𝑓 ,𝑈𝑛𝑖𝑡𝑒𝑑𝑆𝑡𝑎𝑡𝑒𝑠, 2009 / 01 / 20 . The other is ) triadic occurring defined as {(( 𝑠, 𝑟 𝑖 , 𝑜, 𝑡 𝑖 ) , ( 𝑠, 𝑟 𝑗 , 𝑝, 𝑡 𝑗 )) → ( 𝑜, 𝑟 𝑘 , 𝑝, 𝑡 𝑘 )| 𝑡 𝑘 ≥ 𝑚𝑎𝑥 𝑡 ,𝑡 ( 𝑖 𝑗 )} , e.g., (( 𝐶ℎ𝑖𝑛𝑎, 𝐻𝑜𝑠𝑡𝑉𝑖𝑠𝑖𝑡, 𝑆𝑎𝑢𝑑𝑖𝐴𝑟𝑎𝑏𝑖𝑎, 2023 03 / / 06 ) , ( 𝐶ℎ𝑖𝑛𝑎, 𝐻𝑜𝑠𝑡𝑉𝑖𝑠𝑖𝑡, 𝐼𝑟𝑎𝑛, 2023 / 03 / 06 ) → ( 𝑆𝑎𝑢𝑑𝑖𝐴𝑟𝑎𝑏𝑖𝑎,𝑆𝑖𝑔𝑛𝐴𝑔𝑟𝑒𝑒𝑚𝑒𝑛𝑡, 𝐼𝑟𝑎𝑛, 2023 / 03 / 10 . The ) facts on the left of the arrow are called head facts, and those on the right are called tail facts.

## 3.2 Anomalies in TKGs

Here, we formally define three kinds of typical anomalies in TKGs. Given a TKG G , we first define its corresponding ideal TKG as ˆ G = (E R T F) , , , ˆ which removes all the incorrect facts from F and complete all the missing facts into F (i.e., ( 𝑠, 𝑟, 𝑜, 𝑡 ) ∈ F ˆ if and only if it holds in reality). We further

define the ideal triple set ˆ L = {( 𝑠, 𝑟, 𝑜 )|( 𝑠, 𝑟, 𝑜, 𝑡 ) ∈ F } ˆ . Note that, ˆ G and ˆ L are only conceptual aids that do not exist. We then use it to define anomalies.

- 3.2.1 Conceptual Errors. Extraction methods may introduce noised facts with error entities or relations in TKGs. Formally, we define the conceptual errors as F 𝑐 = {( 𝑠 𝑐 , 𝑟 𝑐 , 𝑜 𝑐 , 𝑡 𝑐 )|( 𝑠 𝑐 , 𝑟 𝑐 , 𝑜 𝑐 , 𝑡 𝑐 ) ∈ F ( , 𝑠 𝑐 , 𝑟 𝑐 , 𝑜 𝑐 ) ∉ ˆ L} , e.g., ( 𝐽𝑜𝑒𝐵𝑖𝑑𝑒𝑛, 𝐵𝑜𝑟𝑛𝐼𝑛, 𝐼𝑟𝑒𝑙𝑎𝑛𝑑, 1942 11 20 . / / )
- 3.2.2 Time Errors. Knowledge updating may make existing facts invalid, but update delays will let these invalid facts not be removed from TKGs. Formally, we define the time errors as F 𝑡 = {( 𝑠 𝑡 , 𝑟 𝑡 , 𝑜 𝑡 , 𝑡 𝑡 )|( 𝑠 𝑡 , 𝑟 𝑡 , 𝑜 𝑡 , 𝑡 𝑡 ) ∈ F , ( 𝑠 𝑡 , 𝑟 𝑡 , 𝑜 𝑡 ) ∈ L ( ˆ , 𝑠 𝑡 , 𝑟 𝑡 , 𝑜 𝑡 , 𝑡 𝑡 ) ∉ ˆ F} . For example, ( 𝑂𝑏𝑎𝑚𝑎,𝑃𝑟𝑒𝑠𝑖𝑑𝑒𝑛𝑡 𝑜𝑓 , 𝑈 𝑛𝑖𝑡𝑒𝑑𝑆𝑡𝑎𝑡𝑒𝑠, 2023 10 21 . / / )
- 3.2.3 Missing Errors. Insufficient updates also prevent some correct facts not being added to TKGs. Formally, we define the missing errors as F 𝑚 = {( 𝑠 𝑚 , 𝑟 𝑚 , 𝑜 𝑚 , 𝑡 𝑚 )|( 𝑠 𝑚 , 𝑟 𝑚 , 𝑜 𝑚 , 𝑡 𝑚 ) ∉ F ( , 𝑠 𝑚 , 𝑟 𝑚 , 𝑜 𝑚 , 𝑡 𝑚 ) ∈ F } ˆ . For instance, a TKG might include the knowledge Barack Obama left office but lack his inauguration. Unlike TKG completion that predicts missing entities or relations for given tuples, we aim to find which tuple is missing in TKG. Note that these anomalies will persist as TKGs keep growing in real-world situations.

## 3.3 Minimum Description Length Principle

In the two-part minimum description length (MDL) principle [41], given a set of models M , the best model 𝑀 ∈ M on data 𝐷 minimizes 𝐿 𝑀 ( ) + 𝐿 𝐷 𝑀 ( | ) , where 𝐿 𝑀 ( ) is the length (in bits) of the description of 𝑀 , and 𝐿 𝐷 𝑀 ( | ) is the length of the description of the data when encoded using 𝑀 . In this work, we leverage MDL to find the optimal summarization model of a given TKG. Each MDL-based approach must devise its definitions for the description lengths, and here we follow the most commonly used primitives [17].

## 3.4 Summarization of A TKG

The summarization of a graph is a more refined and compact representation of the graph [6], including super-graphs [9], sparsified graphs [33], and independent rules [45]. However, they fail to handle rich semantics and temporal relevance in TKGs, inspiring us to propose a novel rule graph as the summarization of a TKG.

- 3.4.1 Atomic Rules. Given a TKG G , we first construct a function C(·) , which takes each entity as input and outputs its category. Based on this, each knowledge ( 𝑠, 𝑟, 𝑜, 𝑡 ) ∈ G can be mapped as an atomic rule (C( ) 𝑠 , 𝑟 , C( )) 𝑜 , which summarizes the interaction pattern of the knowledge (e.g., ( 𝑂𝑏𝑎𝑚𝑎,𝑊𝑖𝑛, 𝑁𝑜𝑏𝑒𝑙𝑃𝑒𝑎𝑐𝑒𝑃𝑟𝑖𝑧𝑒, 2019 10 09 / / ) can be mapped as ( 𝑃𝐸𝑅𝑆𝑂𝑁,𝑊𝑖𝑛,𝑃𝑅𝐼𝑍𝐸 ) ).
- 3.4.2 Rule Graph. A rule graph is a directed graph G = { V E , where each , } 𝑣 ∈ V is a node indicating an atomic rule, and each 𝑒 ∈ E is a rule edge preserving the sequential relevance between atomic rules. There are two kinds of rule edges in E. One is derived from the chain occurring (e.g., ( 𝑃𝐸𝑅𝑆𝑂𝑁,𝑁𝑜𝑚𝑖𝑛𝑎𝑡𝑒𝑑,𝑃𝑅𝐼𝑍𝐸 ) → ( 𝑃𝐸𝑅𝑆𝑂𝑁,𝑊𝑖𝑛,𝑃𝑅𝐼𝑍𝐸 ) ), termed as ( 𝑣 ℎ → 𝑣 𝑡 ) where 𝑣 ℎ is the head atomic rule and 𝑣 𝑡 is the tail atomic rule. The other is derived from the triadic occurring (e.g., ( 𝑃𝐸𝑅𝑆𝑂𝑁,𝑊𝑟𝑖𝑡𝑒,𝐵𝑂𝑂𝐾 , ) ( 𝐵𝑂𝑂𝐾 𝑁𝑜𝑚𝑖𝑛𝑎𝑡𝑒𝑑,𝑃𝑅𝐼𝑍𝐸 , ) → ( 𝑃𝐸𝑅𝑆𝑂𝑁,𝑊𝑖𝑛,𝑃𝑅𝐼𝑍𝐸 ) ), termed as (( 𝑣 ℎ , 𝑣 𝑚 ) → 𝑣 𝑡 ) , where 𝑣 𝑚 is the middle atomic rule. By associating atomic rules with rule edges, paths between atomic rules can describe the occurrence relevance between two kinds of interactions.

## 3.5 Problem Definition

Detecting anomalies for TKGs that have been offline preserved in the database is meaningful. However, it is a more valuable but difficult problem to detect anomalies for TKGs that are online updating, requiring the model to be efficient, adaptive to online changes, and easy to rebuild. We term it inductive anomaly detection in TKGs.

Definition 3.1 (Inductive anomaly detection in TKGs). Given an online updating TKG G where the most recently updated timestamp is 𝑡 𝑒 , inductive anomaly detection aims to construct a model 𝑀 based on G to find anomalies in the future timestamps 𝑡 &gt; 𝑡 𝑒 . It contains classifying whether each newly arrived knowledge ( 𝑠, 𝑟, 𝑜, 𝑡 ) is an anomaly (i.e., conceptual or time errors), and determining whether some knowledge is missing in 𝑡 (i.e., missing error).

We leverage the widely used compression principle MDL to construct 𝑀 , which follows the idea of compression in information theory to find general patterns to describe the valid data, and thus in turn reveal anomalies. The sub-problem is hence defined as:

Definition 3.2 (Inductive TKG summarization with MDL). Given an online updating TKG G , we seek to find the model 𝑀 ∗ (i.e., the optimal rule graph) that minimizes the description length of G ,

$$M ^ { * } = \underset { M \in \mathcal { M } } { \arg \min } \{ L ( M ) + L ( \mathcal { G } | M ) \}.$$

With the constant enrichment of G , 𝑀 ∗ varies across timestamps. However, it is time-consuming to construct 𝑀 ∗ from scratch in every timestamp, requiring a strategy to update 𝑀 ∗ incrementally.

## 4 Method

## 4.1 Overview

Motivation. Reflecting on the challenges in TKG anomaly detection, we recognize that a rulebased summarization approach could effectively tackle these issues. First, rules encapsulate the most common patterns within a graph in a human-readable form. If we can map new knowledge as a set of rules, then they can provide interpretable evidence for its validity. Second, the complex patterns observed in TKGs stem from the composition of simpler, independent patterns. If we can appropriately link these simple rules, then the complex patterns can be flexibly deduced based on the individual rules. Last, rules describe the properties of a TKG in a more compact and refined way. Thus ideally, any semantic and pattern shifts can be described as modifications of the rules.

Solution. In this paper, we propose AnoT, a novel summarization method for TKG anomaly detection. As depicted in Figure 2, AnoT takes an online updating TKG as input, identifies anomalies, and then filters valid knowledge. The process initiates with the detector module, which constructs a rule graph based on the offline preserved part of TKG. Upon the arrival of new knowledge, this module evaluates it against the rule graph to compute an anomaly score. Subsequently, the updater module receives valid knowledge identified by the detector module, and then reforms them as edit operations on the rule graph to handle online semantic and pattern changes. The monitor module estimates the approximate error of the rule graph in representing the TKG. When the approximate error exceeds the threshold, the monitor will inform the detector to refresh the rule graph based on the current TKG. In this way, the reachable nodes during walking will give readable evidence for detection, while the complex patterns can be flexibly described by the walking paths, and the online changes are uniformly handled.

In the following, we first define the description length of G used to find the optimal rule graph, and then detail each part of AnoT.

Fig. 2. Conceptual illustration of the proposed AnoT framework.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00872v2-figure-0ce579fe-8aaa-40a6-af30-724fb6ea4a2c.jpg)

## 4.2 Description Length of The Rule Graph

We employ the minimum description length principle to guide the construction of the optimal rule graph. In other words, we consider it as a classic information-theoretic transmitter/receiver setting [51], where the goal is to describe the graph to the receiver using as few bits as possible. As a result, we should first define the number of bits required to describe the TKG (i.e., 𝐿 𝑀 ( ) and 𝐿 (G| 𝑀 ) ).

4.2.1 𝐿 𝑀 ( ) . Based on the primitives of MDL principle [17] and the definition of the rule graph, the encoding cost of a rule graph G = { V E , } consists of the number of atomic rules V, the number of rule edges E (both upper bounded by the number of possible candidates), and the encoding cost of 𝑉 and 𝐸 , which is defined as

$$L ( M ) = l o g ( 2 * | C _ { \mathcal { E } } | ^ { 2 } * | \mathcal { R } | ) + l o g \binom { 2 * | C _ { \mathcal { E } } | ^ { 2 } * | \mathcal { R } | } { 3 } + \sum _ { v \in V } L ( v ) + \sum _ { e \in E } L ( e ),$$

where the first term is the upper bound of the number of candidate atomic rules. |CE | is the total number of entity categories derived from function C(·) (see Section 4.3.1). |R| is the number of relations. Each atomic rule has the form of (CATEGORY, relation, CATEGORY), and thus results in |CE | 2 ∗ |R| . Twice because each relation has two directions. The second term is the upper bound of the number of candidate rule edges, where 𝑙𝑜𝑔 GLYPH&lt;0&gt; 𝐴 𝐵 GLYPH&lt;1&gt; means the description length of uniformly choosing 𝐵 elements from 𝐴 elements. Each rule edge associates two or three atomic rules (i.e., chain or triadic occurring), and thus results in 𝐵 =3 as the upper bound. 𝐿 𝑣 ( ) and 𝐿 𝑒 ( ) are respectively the encoding costs of each atomic rule and each rule edge, defined as

$$L ( v ) = l o g | \mathcal { C } _ { \mathcal { E } } | + ( - l o g \frac { n ^ { c _ { s } } } { | \mathcal { E } | } ) + ( - l o g \frac { n ^ { c _ { o } } } { | \mathcal { E } | } ) + ( - l o g \frac { n ^ { r } } { | \mathcal { F } | } + 1 ),$$

where the first term is the number of the categories of entities. The second to fourth terms are the number of bits used to encode subject categories, object categories, and relations respectively. Note that we use optimal prefix code [24] to encode actual categories, so 𝑛 𝑐 𝑠 is the number of times category 𝑐 𝑠 ∈ CE occurs in G ( 𝑛 𝑐 𝑜 is similar), while 𝑛 𝑟 is the number of times relation 𝑟 ∈ R occurs in G and 1 represents the direction of the relation. Since the number of relations is constant across different models, we ignore it during model selection. We define the encoding cost of each rule edge as

$$L ( e ) = l o g | E | + ( - l o g \frac { n ^ { v _ { h } } } { | E | } ) + ( - l o g \frac { n ^ { v _ { m } } } { | E | } ) + ( - l o g \frac { n ^ { v _ { t } } } { | E | } ) + 1,$$

where | E is the number of the rule edges and | 𝑛 𝑣 ℎ is the number of head atomic rule 𝑣 ℎ occurs in rule graph G. 1 represents the direction of the edge. Note that for brevity, we only give 𝐿 𝑒 ( ) of the triadic occurring and the chain occurring can be easily extended by removing the auxiliary atomic rule part (i.e., the third term).

4.2.2 𝐿 (G| 𝑀 ) . Each atomic rule can describe a set of facts in TKG (e.g., atomic rule ( 𝑃𝐸𝑅𝑆𝑂𝑁,𝑊𝑖𝑛𝑠, 𝑃𝑅𝐼𝑍𝐸 ) can describe fact ( 𝑂𝑏𝑎𝑚𝑎,𝑊𝑖𝑛, 𝑁𝑜𝑏𝑒𝑙𝑃𝑒𝑎𝑐𝑒𝑃𝑟𝑖𝑧𝑒, 2019 / 10 / 09 ), and each rule edge can de-) scribe a set of occurring relationships among facts. For example, rule edge ( 𝑃𝐸𝑅𝑆𝑂𝑁,𝑊𝑖𝑛𝑡ℎ𝑒𝑆𝑒𝑙𝑒𝑐𝑡𝑖𝑜𝑛, 𝐶𝑂𝑈𝑁𝑇𝑅𝑌 ) → ( 𝑃𝐸𝑅𝑆𝑂𝑁,𝑃𝑟𝑒𝑠𝑖𝑑𝑒𝑛𝑡𝑜𝑓 ,𝐶𝑂𝑈 𝑁𝑇𝑅𝑌 ) can describe the relationship that fact ( 𝑂𝑏𝑎𝑚𝑎, 𝑃𝑟𝑒𝑠𝑖𝑑𝑒𝑛𝑡𝑜𝑓 ,𝑈𝑛𝑖𝑡𝑒𝑑𝑆𝑡𝑎𝑡𝑒𝑠, 2009 / 01 / 20 ) occurs subsequently after the fact ( 𝑂𝑏𝑎𝑚𝑎,𝑊𝑖𝑛𝑡ℎ𝑒𝑆𝑒𝑙𝑒𝑐𝑡𝑖𝑜𝑛, 𝑈𝑛𝑖𝑡𝑒𝑑𝑆𝑡𝑎𝑡𝑒𝑠, 2008 11 04 . These described facts are called / / ) correct assertions . They can be encoded by the given rule graph. Moreover, TKGs inevitably contain noise and uncommon facts and thus there may be facts that cannot be encoded by the rule graph, called negative errors . Therefore, the encoding cost of G by the rule graph 𝑀 is 𝐿 (G| 𝑀 ) = 𝐿 (A G ) + 𝐿 (N G ) . 𝐿 (A G ) is the encoding cost of the correct assertions and 𝐿 (N G ) is the encoding cost of the negative errors. The encoding cost of the correct assertions is defined as

$$L ( \mathcal { A } ^ { \mathcal { G } } ) = \sum _ { v \in V } \sum _ { a _ { v } \in \mathcal { A } _ { v } ^ { \mathcal { G } } } L ( a _ { v } ) + \sum _ { e \in E } \sum _ { a _ { e } \in \mathcal { A } _ { e } ^ { \mathcal { G } } } L ( a _ { e } ),$$

where A G 𝑣 and A G 𝑒 are the sets of correct assertions of each atomic rule 𝑣 and each rule edge 𝑒 respectively. 𝐿 𝑎 ( 𝑣 ) and 𝐿 𝑎 ( 𝑒 ) are respectively the encoding costs of fact 𝑎 𝑣 (i.e., a correct assertion of 𝑣 ) and relationship 𝑎 𝑒 (i.e., a correct assertion of 𝑒 ), defined as

$$L ( a _ { v } ) = ( - l o g \frac { n ^ { s _ { v } } } { | \mathcal { A } _ { v } ^ { \mathcal { G } } | } ) + ( - l o g \frac { n ^ { o _ { v } } } { | \mathcal { A } _ { v } ^ { \mathcal { G } } | } ),$$

$$L ( a _ { e } ) = ( - l o g \frac { n ^ { a _ { e } ^ { h } } } { | \mathcal { A } _ { e } ^ { G } | } ) + ( - l o g \frac { n ^ { a _ { e } ^ { m } } } { | \mathcal { A } _ { e } ^ { G } | } ) + ( - l o g \frac { n ^ { a _ { e } ^ { t } } } { | \mathcal { A } _ { e } ^ { G } | } ),$$

where 𝑛 𝑠 𝑣 and 𝑛 𝑜 𝑣 are respectively the numbers of times entity 𝑠 and 𝑜 occur in all the correct assertions of atomic rule 𝑣 (i.e., A G 𝑣 ). Note that the encoding cost of the relation is ignored since it has been included in 𝐿 𝑣 ( ) . 𝑎 ℎ 𝑒 , 𝑎 𝑚 𝑒 , and 𝑎 𝑡 𝑒 are respectively the head fact, middle fact, and the tail fact of 𝑎 𝑒 , and thus 𝑛 𝑎 ℎ 𝑒 is the number of times fact 𝑎 ℎ 𝑒 occurs in all the correct assertions of rule edge 𝑒 (i.e., A G 𝑒 ). 𝑎 𝑚 𝑒 and 𝑎 𝑡 𝑒 are defined similarly.

The negative errors contain two parts: the facts that cannot be mapped into any atomic rules, and the facts that can be mapped but cannot be associated with any other facts. Given the adjacency tensor 𝐴 𝑡 of each timestamp, the unmodeled facts can be defined as 𝐴 -𝑡 = 𝐴 𝑡 -𝐴 𝑚 𝑡 . 𝐴 𝑚 𝑡 is a subset of 𝐴 𝑡 where each element is set as 1 if 1) it is 1 in 𝐴 𝑡 ; 2) the corresponding fact can be mapped into atomic rules; and 3) the corresponding fact can be associated with a previous fact in 𝑡 ′ &lt; 𝑡 via the rule edges. Since the number of missing facts can be inferred given the total number of facts and the number of facts that are already explained by the model, we only consider the cost of encoding the positions of 1 in 𝐴 -𝑡 . The encoding cost of the negative errors can be then defined as

$$L ( \mathcal { N } ^ { \mathcal { G } } ) = \sum _ { t \in \mathcal { T } } l o g \binom { | \mathcal { E } | ^ { 2 } * | \mathcal { R } | - | A _ { t } ^ { m } | } { | A _ { t } ^ { - } | },$$

where | · | is set cardinality and the number of 1s in a tensor. As the above definitions give us a reliable way to measure the quality of summarizing a TKG, we then aim to find the best TKG summarization model by minimizing such description length.

Fig. 3. Rule graph construction, which contains: 1. Category function construction, 2. Generating candidate atomic rules, 3. Generating candidate rule edges, 4. Ranking and selecting.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00872v2-figure-c1da8cd8-776c-4fa7-8008-8fc19a26617c.jpg)

## Algorithm 1 Construct the rule graph

| 1:                                                                                                             | Input: Offline preserved part of TKG G                                                                         |                     |
|----------------------------------------------------------------------------------------------------------------|----------------------------------------------------------------------------------------------------------------|---------------------|
| 2: Output: A model 𝑀 ∗ consisting of atomic rules and rule edges                                               | 2: Output: A model 𝑀 ∗ consisting of atomic rules and rule edges                                               |                     |
| 3: Read G and construct the category function                                                                  | 3: Read G and construct the category function                                                                  | ⊲ 4.3.1             |
| 4: Generate candidate atomic rules P( 𝑣 ) and candidate rule edges P( 𝑒 ) based on G and the category function | 4: Generate candidate atomic rules P( 𝑣 ) and candidate rule edges P( 𝑒 ) based on G and the category function | ⊲ 4.3.2             |
| 5: Rank all 𝑣 ∈ P( 𝑣 ) first by Δ 𝐿 ( G| 𝑀 ∪ { 𝑣 }) ↓ then by | A G 𝑣 | ↓ and finally by 𝐼 𝐷 ↓                 | 5: Rank all 𝑣 ∈ P( 𝑣 ) first by Δ 𝐿 ( G| 𝑀 ∪ { 𝑣 }) ↓ then by | A G 𝑣 | ↓ and finally by 𝐼 𝐷 ↓                 | ⊲ 4.3.3             |
| 6: Rank all 𝑒 ∈ P( 𝑒 ) first by Δ 𝐿 ( G| 𝑀 ∪ { 𝑒 }) ↓ then by | A G 𝑒 | ↓ and finally by 𝐼 𝐷 ↓                 | 6: Rank all 𝑒 ∈ P( 𝑒 ) first by Δ 𝐿 ( G| 𝑀 ∪ { 𝑒 }) ↓ then by | A G 𝑒 | ↓ and finally by 𝐼 𝐷 ↓                 | ⊲ 4.3.3             |
| 7: 𝑀 ∗ ←∅                                                                                                      | 7: 𝑀 ∗ ←∅                                                                                                      |                     |
| 8: while not converged do                                                                                      | 8: while not converged do                                                                                      | ⊲ 4.3.3             |
| 9:                                                                                                             | for 𝑣 ∈ P( 𝑣 ) do                                                                                              |                     |
| 10:                                                                                                            | if 𝐿 ( G| 𝑀 ∗ ∪ 𝑣 ) < 𝐿 ( G| 𝑀 ∗ ) then                                                                        |                     |
| 11:                                                                                                            | 𝑀 ∗ ← 𝑀 ∗ ∪ 𝑣                                                                                                  | ⊲ add more 𝑣 to 𝑀 ∗ |
| 12:                                                                                                            | for 𝑒 ∈ P( 𝑒 ) do                                                                                              |                     |
| 13:                                                                                                            | if 𝐿 ( G| 𝑀 ∗ ∪ 𝑒 ) < 𝐿 ( G| 𝑀 ∗ ) then                                                                        |                     |
| 14:                                                                                                            | 𝑀 ∗ ← 𝑀 ∗ ∪ 𝑒                                                                                                  | ⊲ add more 𝑒 to 𝑀 ∗ |

## 4.3 Detector

The detector module has two functions: 1) Construct the optimal rule graph. As shown in Figure 3, a category function is first constructed based on existing knowledge (Section 4.3.1), and then it will be used to map knowledge as candidate atomic rules and candidate rule edges (Section 4.3.2). Finally, the most expressive candidates will be iteratively selected to construct the rule graph (Section 4.3.3). More details can be found in Algorithm 1. 2) Generate anomaly scores. As shown in the upper part of Figure 4, new knowledge will be first mapped as a set of atomic rules. Atomic rules that exist in the rule graph can give evidence of their conceptual validity, which will derive the static scores (Section 4.3.4). Then, the evidence of time validity is gathered by recursively walking on the rule graph and instantiating the processor nodes, which will derive the temporal scores. More details can be found in Algorithm 2.

4.3.1 Construct Category Function. Entity categories are often missing in real-world TKGs [58]. Fortunately, we find that the category of an entity is largely related to the relations it interacts with. For example, an entity that interacts with relations 𝐵𝑜𝑟𝑛𝐼𝑛 and 𝑃𝑙𝑎𝑦𝑠𝐹𝑜𝑟 should have a

Fig. 4. Conceptual illustrations of the scoring process and the updater module.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00872v2-figure-81f7257a-8024-4fa8-8f2f-ab37528951f9.jpg)

category of 𝐴𝑇𝐻𝐿𝐸𝑇𝐸 , and an entity that interacts with relations 𝐵𝑜𝑟𝑛𝐼𝑛 and 𝐶𝑟𝑒𝑎𝑡𝑒 can be an 𝐴𝑅𝑇𝐼𝑆𝑇 . Intuitively, the more relations are considered, the more fine-grained information a category can imply. This inspires us to generate categories for entities by extracting the frequent relation combinations. A relation combination occurs more frequently across entities means it can describe a more general property shared by entities, which is more likely to imply a category.

Formally, we define the interaction relation set of an entity 𝑒 ∈ E as 𝑅 𝑒 ( ) = { 𝑟 | ( 𝑒, 𝑟, 𝑜, 𝑡 ) ∈ F } . With each entity providing a relation set, we then use the PrefixSpan algorithm [38] to find the most frequent subset within 𝑅 𝑒 ( ) across all entities. Each identified subset is a frequent relation combination that suggests a potential category. Subsets encompassing more relations imply more granular categories. However, finding frequent subsets with large sizes is very time-consuming. To counterbalance efficiency with categories' quality, we propose to only find small relation combinations (i.e., up to 3 relations) and then iteratively aggregate selected subsets. Let the output of PrefixSpan be R = {( 𝑅 , 𝐸 1 1 ) , ( 𝑅 , 𝐸 2 2 ) , ... } , where 𝑅 𝑖 is the ith most frequent relation combination ( 𝑟 1 𝑖 , 𝑟 2 𝑖 , 𝑟 3 𝑖 ) and 𝐸 𝑖 = { 𝑒 𝑒 | ∈ E , 𝑅 𝑖 ⊆ 𝑅 𝑒 ( )} is the entities encompassed by 𝑅 𝑖 . We commence with entity-based aggregation : if a significant overlap exists between entities in 𝐸 𝑖 and 𝐸 𝑗 (exceeding 90%), it indicates shared properties that necessitate simultaneous description via both relation combinations. Consequently, we introduce ( 𝑅 = 𝑅 𝑖 ∪ 𝑅 , 𝐸 𝑗 = 𝐸 𝑖 ∩ 𝐸 𝑗 ) into R as a more fine-grained category. We then perform relation-based aggregation : if a significant overlap exists between relations in 𝑅 𝑚 and 𝑅 𝑛 (exceeding 90%), it means the categories implied by 𝑅 𝑚 and 𝑅 𝑛 are very similar. Therefore, we add ( 𝑅 = 𝑅 𝑚 ∩ 𝑅 , 𝐸 𝑛 = 𝐸 𝑚 ∪ 𝐸 𝑛 ) into R as a more generalizable category. These aggregation steps are circularly executed until no further combinations can be aggregated. Following this phase, each relation combination 𝑅 𝑖 is conceptualized as an implicit category 𝑐 𝑖 , with the respective entities in 𝐸 𝑖 being categorized accordingly. To reduce category redundancy, we sort the relation combinations in descending order of the number of their covered entities and select one by one until each entity has at least 𝑘 categories.

4.3.2 Candidate Generation. To construct the rule graph, we should first generate all possible rules and rule edges as candidates based on the input TKG. For each fact ( 𝑠, 𝑟, 𝑜, 𝑡 ) , we generate the corresponding candidate atomic rules as {( 𝑐 , 𝑟, 𝑐 𝑖 𝑗 )| 𝑐 𝑖 ∈ 𝐶 𝑠 ,𝑐 ( ) 𝑗 ∈ 𝐶 𝑜 ( )} , where 𝐶 𝑠 ( ) is the category set of 𝑠 . We gather the rules derived from all facts ( 𝑠, 𝑟, 𝑜, 𝑡 ) ∈ F as the candidate set of atomic rules.

To generate all possible chain-occurring-based rule edges, we first construct the interaction sequence 𝑆 ( 𝑠, 𝑜 ) = { 𝑟 1 , 𝑟 2 , ... } for each entity pair appeared in G . The interaction sequence preserves all the relations that occurred between 𝑠 and 𝑜 and is sorted by the ascending order of their occurrence timestamps. Thus, any adjacent relations in the sequence represent two interactions between 𝑠 and 𝑜 that occur successively, which may imply a chain-occurring pattern. Formally, given each entity pair ( 𝑠, 𝑜 ) and its corresponding interaction sequence, we generate the candidate rule edges as {( 𝑐 𝑠 , 𝑟 𝑚 , 𝑐 𝑜 ) → ( 𝑐 𝑠 , 𝑟 𝑛 , 𝑐 𝑜 )| 𝑐 𝑠 ∈ 𝐶 𝑠 ,𝑐 ( ) 𝑜 ∈ 𝐶 𝑜 ,𝑟 ( ) 𝑚 , 𝑟 𝑛 ∈ 𝑆 ( 𝑠, 𝑜 ) , 𝑚 &lt; 𝑛 } . We gather the rule edges derived from all entity pairs that appear in G as the candidate set of chain-occurring-based rule edges. Since the occurrence timespan between different relations may vary, e.g., 𝑀𝑎𝑘𝑒𝑆𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡 may occur a few days after 𝑊𝑖𝑛𝑡ℎ𝑒𝐸𝑙𝑒𝑐𝑡𝑖𝑜𝑛 , but 𝑅𝑒𝑡𝑖𝑟𝑒𝑚𝑒𝑛𝑡 may occur several years later, considering the timespan of occurrence between two relations assists in determining the occurrence of a fact at a particular timestamp. Therefore, we also preserve the occurrence timespans of facts for each rule edge 𝑒 (e.g., 𝑡 𝑛 -𝑡 𝑚 for chain-occurring facts ( 𝑠, 𝑟 𝑚 , 𝑜, 𝑡 𝑚 ) and ( 𝑠, 𝑟 𝑛 , 𝑜, 𝑡 𝑛 ) ) and results in a timespan set 𝑇 𝑒 ( ) .

For triadic-occurring-based rule edges, in each timestamp 𝑡 ∈ T , we find facts that occur at 𝑡 and share one same entity (e.g., ( 𝑠, 𝑟 𝑚 , 𝑜, 𝑡 ) and ( ℎ, 𝑟 𝑛 , 𝑜, 𝑡 ) ). Then, we find the most closely occurred fact in 𝑡 𝑝 ≥ 𝑡 that contains 𝑠 and ℎ (e.g., ( 𝑠, 𝑟 𝑝 , ℎ, 𝑡 + 3 ). These three facts describe the formation ) process of a triadic closure, which may imply a triadic-occurring pattern. Since there is local randomness in the occurrence time of facts [35], we relax the same time restriction of the former two facts as co-occurring within a short period. Formally, for each timestamp 𝑡 , the triadic-occurringbased candidate rule edges are generated as {(( 𝑐 𝑠 , 𝑟 𝑚 , 𝑐 𝑜 ) , ( 𝑐 ℎ , 𝑟 𝑛 , 𝑐 𝑜 )) → ( 𝑐 𝑠 , 𝑟 𝑝 , 𝑐 ℎ )| 𝑐 𝑠 ∈ 𝐶 𝑠 ,𝑐 ( ) 𝑜 ∈ 𝐶 𝑜 ,𝑐 ( ) ℎ ∈ 𝐶 ℎ , ( ) |T ( 𝑒 , 𝑟 𝑠 𝑚 , 𝑒 𝑜 ) -𝑡 | ≤ 𝐿, |T ( 𝑒 ℎ , 𝑟 𝑛 , 𝑒 𝑜 ) -𝑡 | ≤ 𝐿, T( 𝑒 , 𝑟 𝑠 𝑝 , 𝑒 ℎ ) ≥ 𝑡 + 𝐿 } , where T(·) is the occurrence timestamp of fact and 𝐿 is a hyperparameter. We also preserve the occurrence timespans for these facts.

4.3.3 Ranking and Selection. We propose a greedy approach to select the most representative candidate into the rule graph iteratively. Our objective is to select the candidate that leads to the largest encoding cost reduction in each iteration. Recognizing that varying orders of selection may yield inconsistent models, thus affecting reproducibility, we implement a structured ranking mechanism that ensures a consistent selection order of candidates. Since the more a candidate can reduce negative errors, the more valuable it might be, we first rank candidates based on the descending order of their error reduction Δ 𝐿 (G| 𝑀 ∪ { 𝑥 }) = 𝐿 (G| 𝑀 ) -𝐿 (G| 𝑀 ∪ { 𝑥 }) , where 𝑥 represents candidate atomic rule 𝑣 or rule edge 𝑒 . The ties in the ranking are broken by selecting candidates with more correct assertions. The final tie-breaker is the ID of each candidate. We separately rank atomic rules and rule edges since they have different magnitudes in the cost reduction. The ranked candidate rules and rule edges are respectively termed as P( ) 𝑣 and P( ) 𝑒 .

After ranking the candidates, 𝑀 is initialized as ∅ and each 𝑣 ∈ P( ) 𝑣 is first selected in ranked order. For each 𝑣 , we compute the description length when 𝑣 is added into 𝑀 (i.e., 𝐿 (G , 𝑀 ∪ { 𝑣 }) ). If it is less than 𝐿 (G , 𝑀 ) , 𝑣 can enhance the expressive capability of 𝑀 . Thus, we add 𝑣 into 𝑀 . We perform the selection passes over P( ) 𝑣 until no new atomic rules can be added. We then perform the same selection process on P( ) 𝑒 to add rule edges into 𝑀 . Note that some selected rule edges may contain atomic rules that are not selected in the former process. We restrict the usage of these atomic rules only to verify the time errors. The obtained approximately optimized rule graph is termed as 𝑀 ∗ = { V ∗ , E ∗ } .

4.3.4 Deriving Anomaly Scores. Intuitively, nodes and edges in the rule graph explain the common patterns of knowledge occurring in TKG. Thus, new knowledge that cannot be mapped as nodes or cannot be associated with other knowledge via edges is unexplained and likely to be anomalous. We make this intuition more principled by defining static scores and temporal scores for tuples.

## Algorithm 2 Derive the anomaly scores

- 1: Input: New knowledge ( 𝑠, 𝑟, 𝑜, 𝑡 ) and rule graph 𝑀 ∗ 2: Output: Static score S ( 𝑠, 𝑟, 𝑜, 𝑡 ) and temporal score T ( 𝑠, 𝑟, 𝑜, 𝑡 ) 3: Generate mapped atomic rule set V ( 𝑠, 𝑟, 𝑜, 𝑡 ) 4: 𝑡𝑒𝑚𝑝 𝑠 ← 0 5: for 𝑣 ∈ V ( 𝑠, 𝑟, 𝑜, 𝑡 ) do ⊲ Eq. 9 6: 𝑡𝑚𝑝 𝑠 ← 𝑡𝑚𝑝 𝑠 + | A G | 𝑣 7: S ( 𝑠, 𝑟, 𝑜, 𝑡 ) = 1 𝑡𝑚𝑝𝑠 8: if 𝑡𝑚𝑝 𝑠 &lt; 𝜆 then ⊲ 𝜆 is a threshold 9: return S ( 𝑠, 𝑟, 𝑜, 𝑡 ) 10: 𝑉 ′ ← ( V 𝑠, 𝑟, 𝑜, 𝑡 ) , 𝑡𝑚𝑝 𝑡 ← 0 , 𝑀𝐴𝑋 \_ 𝑆𝑇𝐸𝑃 ← 0 11: 𝑡𝑚𝑝𝐿𝑖𝑠𝑡 ←∅ 12: for 𝑣 ∈ 𝑉 ′ do ⊲ Eq. 10 13: for 𝑣 𝑖 ∈ N 𝑖𝑛 ( 𝑣 ) do 14: if 𝑣 𝑖 is instantiable then 15: 𝑡𝑚𝑝 𝑡 ← 𝑡𝑚𝑝 𝑡 + |A G 𝑣 | 𝜃 + 1 16: else 17: 𝑡𝑚𝑝𝐿𝑖𝑠𝑡 ← 𝑡𝑚𝑝𝐿𝑖𝑠𝑡 ∪ 𝑣 𝑖 18: if 𝑀𝐴𝑋 𝑆𝑇𝐸𝑃 \_ &lt; 𝐾 then ⊲ 𝐾 is a hyper-parameter 19: 𝑀𝐴𝑋 𝑆𝑇𝐸𝑃 \_ ← 𝑀𝐴𝑋 𝑆𝑇𝐸𝑃 \_ + 1 20: 𝑉 ′ ← 𝑡𝑚𝑝𝐿𝑖𝑠𝑡 21: Go to 11 1

22: T ( 𝑠, 𝑟, 𝑜, 𝑡 ) = 𝑡𝑚𝑝𝑡

Static scores. Nodes in 𝑀 ∗ represent valid interaction patterns found in the TKG. When new knowledge is mapped to a node in 𝑀 ∗ , it means that the knowledge can be explained by an observed pattern, supporting its conceptual validity. The validity of new knowledge is proportionate to the number of nodes it mapped to. Furthermore, some atomic rules can explain more knowledge and thus give stronger evidence. We define the static scores as

$$\mathbb { S } ( s, r, o, t ) = \frac { 1 } { \sum _ { v \in V ^ { * } ( s, r, o, t ) } \left | \mathcal { A } _ { v } ^ { \mathcal { G } } \right | },$$

where V ∗ ( 𝑠, 𝑟, 𝑜, 𝑡 ) is the set of nodes that new knowledge ( 𝑠, 𝑟, 𝑜, 𝑡 ) can be mapped to. |A G 𝑣 | is the number of correct assertions of 𝑣 . The higher S means it is more likely to be a conceptual error.

Temporal scores. Each in-coming edge of a node 𝑣 in the rule graph provides an inducement for the interaction represented by 𝑣 to occur, while the timespans preserved in the edge provide the prompt of when it should occur. Therefore, we propose to walk on the rule graph starting from the mapped nodes of new knowledge to find evidence for it to occur. Specifically, given the new knowledge ( 𝑠, 𝑟, 𝑜, 𝑡 ) , we first map it to nodes in the rule graph by conceptualizing it as a set of atomic rules V ∗ ( 𝑠, 𝑟, 𝑜, 𝑡 ) . Then, for each 𝑣 ∈ V ∗ ( 𝑠, 𝑟, 𝑜, 𝑡 ) , we find all of its in-coming edges (i.e., ( 𝑣 𝑖 → ) 𝑣 or (( 𝑣 , 𝑣 𝑖 𝑘 ) → 𝑣 ) ) and gather all precursor nodes (i.e., { 𝑣 𝑖 | ( 𝑣 𝑖 → ) ∈ 𝑣 E ∗ 𝑜𝑟 (( 𝑣 , 𝑣 𝑖 𝑘 ) → 𝑣 ) ∈ E ∗ } ). We then perform the instantiate on these precursor nodes. For each 𝑣 𝑖 , it is instantiable if there is a fact in 𝑣 𝑖 's correct assertions that can form an occurring relationship (i.e., chain or triadic occurring) with new knowledge ( 𝑠, 𝑟, 𝑜, 𝑡 ) . The instantiable precursor nodes give evidence for the occurrence of new knowledge. Note that TKG inevitably contains noise such as knowledge missing, which can cause node instantiation to fail. We propose a recursive strategy to enhance the robustness of our scoring. If precursor node 𝑣 𝑖 fails to be instantiated, we find all the precursor nodes of 𝑣 𝑖 and use the instantiation of them as alternative evidence from 𝑣 𝑖 . Our algorithm will traverse the rule graph depth-first to gather evidence until the maximum number of hops is reached. The temporal

score is formally defined as

$$\mathbb { T } ( s, r, o, t ) = \frac { 1 } { \sum _ { v \in V ^ { * } ( s, r, o, t ) } \sum _ { v _ { i } \in \mathcal { N } _ { i n } ( v ) } x },$$

where 𝑥 = | A G 𝑣 | 𝜃 + 1 if 𝑣 𝑖 is instantiable, else 𝑥 = ˝ 𝑣 𝑗 ∈N 𝑖𝑛 ( 𝑣 𝑖 ) 𝑥 where N ( ) 𝑖𝑛 𝑣 is the set of in-coming neighbors of 𝑣 . 𝜃 = |{ 𝜏 𝑗 | 𝜏 𝑗 ∈ 𝑇 (( 𝑣 𝑖 → )) | 𝑣 , 𝜏 𝑗 - | 𝑡 -𝑡 𝑖 | | ≤ 𝐿 }| which indicates the gap between the timespan of the instantiations and the preserved timespans. 𝑡 𝑖 is the occurrence timestamp of the instantiated previous knowledge. Temporal scores can be further extended by adding the number of instantiable out-coming edges to the numerator of Eq. 10. Specifically, each out-coming edge of node 𝑣 describes an interaction that should occur after 𝑣 . Therefore, if it can be instantiated by previous knowledge, it means the occurrence of new knowledge violates a common occurrence order. The higher T means it is the more likely to be a time error. Meanwhile, if knowledge gets both low S and T but is not preserved in TKG, it is likely to be a missing error.

Correcting prompts. For conceptual errors, we use the atomic rules that can partially describe the anomaly knowledge ( 𝑠, 𝑟, 𝑜, 𝑡 ) as its correcting prompts, e.g., {( 𝑐 𝑠 , 𝑟 , 𝑐 𝑒 )| 𝑐 𝑒 ∈ C( ) 𝑒 , 𝑒 ∈ E ( , 𝑐 𝑠 , 𝑟 , 𝑐 𝑒 ) ∈ 𝑉 ∗ } and {( 𝑐 𝑠 , 𝑟 𝑖 , 𝑐 𝑜 )| 𝑐 𝑠 ∈ C( ) 𝑠 , 𝑐 𝑜 ∈ C( ) ( 𝑜 , 𝑐 𝑠 , 𝑟 𝑖 , 𝑐 𝑜 ) ∈ 𝑉 ∗ } , which tell us how to revise the entity or relation in anomaly knowledge to make it valid. For time errors, the instantiable in-coming edges (evidence of correctness) and instantiable out-coming edges (evidence of anomaly) give prompts of when the new knowledge occurs is appropriate (i.e., maximize the instantiable in-coming edges and minimize the instantiable out-coming edges). During walking, precursor nodes that fail to instantiate may indicate a missing knowledge, and thus give us prompts to extract new knowledge.

Case demonstration. Here we demonstrate how our strategies detect anomalies in Figure 1. ( 𝐾𝑖𝑚𝐽𝑜𝑛𝑔𝑈𝑁,𝐻𝑒𝑙𝑑𝑀𝑖𝑙𝑖𝑡𝑎𝑟𝑦𝐸𝑥𝑒𝑟𝑐𝑖𝑠𝑒𝑠,𝑆𝑜𝑢𝑡ℎ𝐾𝑜𝑟𝑒𝑎, 2020 / 08 / 23 ) will be assigned with a high S due to the interaction preference conflict of category 𝑃𝑅𝐸𝑆𝐼𝐷𝐸𝑁𝑇 , and thus be detected a conceptual error. ( 𝑇𝑟𝑢𝑚𝑝,𝑃𝑟𝑒𝑠𝑖𝑑𝑒𝑛𝑡𝑜𝑓 ,𝑈𝑛𝑖𝑡𝑒𝑑𝑆𝑡𝑎𝑡𝑒𝑠, 2023 01 20 / / ) will be assigned with a high T since it has occurrence order conflict with ( 𝑇𝑟𝑢𝑚𝑝,𝑂𝑢𝑡𝑔𝑜𝑖𝑛𝑔𝑃𝑟𝑒𝑠𝑖𝑑𝑒𝑛𝑡,𝑈𝑛𝑖𝑡𝑒𝑑𝑆𝑡𝑎𝑡𝑒𝑠, 2021 / 01 / 19 , and thus be ) a time error. During temporal scoring, ANoT needs to traverse the rule graph to find instantiateable nodes, and ( 𝑃𝐸𝑅𝑆𝑂𝑁,𝑊𝑖𝑛𝑡ℎ𝑒𝐸𝑙𝑒𝑐𝑡𝑖𝑜𝑛,𝑈𝑛𝑖𝑡𝑒𝑑𝑆𝑡𝑎𝑡𝑒𝑠 ) will be found uninstantiateable. By verifying the low S and T of instantiating it using 𝐽𝑜𝑒𝐵𝑖𝑑𝑒𝑛 , this knowledge will be detected as a missing error.

## 4.4 Updater

The continuous enrichment of TKG will alter the graph structure, entity semantics, and graph patterns, and introduce new entities, requiring ANoT to adapt online. As shown in the bottom part of Figure 4, we propose an updater module to flexibly handle these changes. Based on Algorithm 3, we detail the updater as follows.

Graph structure changes. ( 𝑠, 𝑟, 𝑜, 𝑡 ) will first be added into G . Thus, the next time the detector module needs to instantiate rules and rule edges, it can access the latest version of G , and thus adapts the scoring to graph structure changes brought by new knowledge.

Entity semantic changes. New knowledge can change an entity's semantics if it includes a relation the entity has not interacted with before (e.g., relation 𝑃𝑟𝑒𝑠𝑖𝑑𝑒𝑛𝑡𝑜𝑓 will add a new category 𝑃𝑅𝐸𝑆𝐼𝐷𝐸𝑁𝑇 for a person). This inspires us to handle entity semantic changes via category editing. When new relation 𝑟 is introduced for entity 𝑠 , relation combinations { 𝑅 𝑖 | 𝑟 ∈ 𝑅 , 𝑅 𝑖 ( 𝑠 ) ∩ 𝑅 𝑖 ≠ ∅} , which may describe the new categories of 𝑠 , will be identified first. Then, the relation combination with the most covered entities will be added to the category function as a new anonymous category for 𝑠 .

## Algorithm 3 Update the rule graph

| 1: Input: New valid knowledge ( 𝑠, 𝑟, 𝑜, 𝑡 ) and rule graph 𝑀 ∗ 2: Output: The updated rule graph 𝑀 ∗   | 1: Input: New valid knowledge ( 𝑠, 𝑟, 𝑜, 𝑡 ) and rule graph 𝑀 ∗ 2: Output: The updated rule graph 𝑀 ∗   | 1: Input: New valid knowledge ( 𝑠, 𝑟, 𝑜, 𝑡 ) and rule graph 𝑀 ∗ 2: Output: The updated rule graph 𝑀 ∗   |
|---------------------------------------------------------------------------------------------------------|---------------------------------------------------------------------------------------------------------|---------------------------------------------------------------------------------------------------------|
| 3:                                                                                                      | ← G ∪ { ( 𝑠, 𝑟, 𝑜, 𝑡 ) }                                                                                | ⊲ handle graph structure changes                                                                        |
| 4: for 𝑒 ∈ ( 𝑠, 𝑜 ) do                                                                                  | 4: for 𝑒 ∈ ( 𝑠, 𝑜 ) do                                                                                  |                                                                                                         |
| 5:                                                                                                      | if 𝑟 ∉ 𝑅 ( 𝑒 ) then                                                                                     | ⊲ handle entity semantic changes                                                                        |
| 6:                                                                                                      | 𝑅 ( 𝑒 ) ← 𝑅 ( 𝑒 ) ∪ { 𝑟 }                                                                               |                                                                                                         |
| 7:                                                                                                      | Generate candidate category set 𝑅 𝑐 ( 𝑒 ) = { 𝑅 𝑖 | 𝑟 ∈ 𝑅 𝑖 , 𝑅 ( 𝑒 ) ∩ 𝑅 𝑖 ≠ ∅}                        |                                                                                                         |
| 8:                                                                                                      | Find 𝑐 𝑖 ∈ 𝑅 𝑐 ( 𝑒 ) with the maximum 𝐸 𝑖                                                               |                                                                                                         |
| 9:                                                                                                      | C( 𝑒 ) ← C( 𝑒 ) ∪ { 𝑐 𝑖 }                                                                               |                                                                                                         |
| 10: for 𝑣 ∈ { ( 𝑐 𝑠 , 𝑟, 𝑐 𝑜 ) | 𝑐 𝑠 ∈ C( 𝑠 ) , 𝑐 𝑜 ∈ C( 𝑜 ) , ( 𝑐 𝑠 , 𝑟, 𝑐 𝑜 ) ∉ 𝑉 ∗ } do              | 10: for 𝑣 ∈ { ( 𝑐 𝑠 , 𝑟, 𝑐 𝑜 ) | 𝑐 𝑠 ∈ C( 𝑠 ) , 𝑐 𝑜 ∈ C( 𝑜 ) , ( 𝑐 𝑠 , 𝑟, 𝑐 𝑜 ) ∉ 𝑉 ∗ } do              | ⊲ handle new interaction patterns                                                                       |
| 11:                                                                                                     | if 𝐿 ( G| 𝑀 ∗ ∪ 𝑣 ) < 𝐿 ( G| 𝑀 ∗ ) then                                                                 |                                                                                                         |
| 12:                                                                                                     | 𝑀 ∗ ← 𝑀 ∗ ∪ { 𝑣 }                                                                                       |                                                                                                         |
| 13:                                                                                                     | for 𝑓 ′ ∈ { ( 𝑠, 𝑟 ′ , 𝑜, 𝑡 ′ ) | ( 𝑠, 𝑟 ′ , 𝑜, 𝑡 ′ ) ∈ G , | 𝑡 - 𝑡 ′ | ≤ 𝐿 } do                        |                                                                                                         |
| 14:                                                                                                     | 𝑀 ∗ ← 𝑀 ∗ ∪ { 𝑣 → 𝑣 ′ }                                                                                 | ⊲ 𝑣 ′ is the atomic rule that can describe 𝑓 ′                                                          |
| 15:                                                                                                     | 𝑇 ( 𝑒 ) ← 𝑇 ( 𝑒 ) ∪ { 𝑡 - 𝑡 ′ }                                                                         | ⊲ handle timespan distribution changes                                                                  |

Graph pattern changes. New categories may derive atomic rules that do not exist in the current rule graph, indicating an emerging interaction pattern. We model such pattern changes as the enrichment on the node set of 𝑀 ∗ . For each 𝑣 ∈ {( 𝑐 𝑠 , 𝑟 , 𝑐 𝑜 )| 𝑐 𝑠 ∈ C( ) 𝑠 , 𝑐 𝑜 ∈ C( 𝑜 , ) ( 𝑐 𝑠 , 𝑟 , 𝑐 𝑜 ) ∉ 𝑉 ∗ } derived from new knowledge, we calculate the encoding cost 𝐿 (G , 𝑀 ∗ ∪ { 𝑣 }) for it and if 𝐿 (G , 𝑀 ∗ ∪{ }) 𝑣 is less than 𝐿 (G , 𝑀 ∗ ) , 𝑣 will be added into V . We then build new edges for the new ∗ node by finding previous knowledge in the form of ( 𝑠, 𝑟 𝑖 , 𝑜, 𝑡 𝑗 ) where 𝑡 𝑗 ≤ 𝑡 . Considering the time consumption, we only perform chain-based associations. The other graph pattern change appears in the occurrence timespan distribution. For example, a regular consultation mechanism established between two countries will change the timespans of relation 𝐶𝑜𝑛𝑠𝑢𝑙𝑡 that appears between these two entities. Therefore, for each rule edge 𝑒 that can describe the new knowledge, we also add the timespans of its newly described facts into 𝑇 𝑒 ( ) , and thus the calculation of the temporal score can adapt to the changes of occurring timespans.

Newentities. For new entities brought by new emerging knowledge, we follow the same process as entity semantic changes to generate new categories for them, and thus knowledge that contains new entities can also be mapped into our rule graph and be handled uniformly. With the continuous emergence of new knowledge deriving the update of the rule graph, ANoT can keep on learning new patterns and thus adapt to new emerging knowledge.

Although new knowledge may have conflicts with some existing rules or do not fit them, it can still be considered valid since our counting-based scoring does not require all rules to be met. These conflicts and mismatches may indicate patterns not observed before. Our updater module aims to filter and keep these patterns in the rule graph, so they can help explain future knowledge.

## 4.5 Monitor

The error of the rule graph may accumulate with the updating. Thus, it is necessary to refresh the model at an appropriate time. There could be some heuristic strategies, such as restarting after a certain time or restarting after a certain number of new knowledge. However, they do not always work since the error accumulation does not change uniformly with time, and there are no shared trends of error accumulation across different TKGs [55]. An untimely restart will lead to excessive error and reduce the detection accuracy and too frequent restart will lead to low efficiency. Fortunately, the encoding cost of negative errors defined in Eq. 11 gives us an information-theoretic metric to measure the availability of the rule graph. It has three advantages: 1) It is easy to calculate and thus will not affect the detection efficiency. 2) It is discretely calculated based on each new

knowledge, avoiding the negative impacts caused by uneven knowledge distribution. 3) It is a data-driven metric and thus can adapt to different domains. We define the metric as

$$L ( \mathcal { N } ^ { \mathcal { G } ^ { o } } ) = \sum _ { t _ { i } > t _ { e } } \log \binom { | \mathcal { E } | ^ { 2 } * | \mathcal { R } | - | A _ { t _ { i } } ^ { m } | } { | A _ { t _ { i } } ^ { - } | },$$

where 𝑡 𝑒 is the latest timestamp of the offline preserved part of G . Our monitor module calculates 𝐿 (N G 𝑜 ) at each new timestamp. If 𝐿 (N G 𝑜 ) &gt; 𝐿 (N G ) , it means that the current model has performed worse on unseen data than seen data. Thus, the monitor will call the detector to reconstruct the rule graph based on the current TKG.

## 4.6 Complexity Analysis

Generating candidate atomic rules involves iterating each knowledge and its entities' categories. The number of candidate atomic rules generated by each edge ( 𝑠, 𝑟, 𝑜, 𝑡 ) is |C( )|∗|C( 𝑠 𝑜 )| . Letting C 𝑚𝑎𝑥 be the max number of categories over all entities, the complexity of generating candidate atomic rules is 𝑂 (C 2 𝑚𝑎𝑥 ∗ |F |) . Generating candidate rule edges needs to iterate knowledge within a timespan. Letting 𝑓 𝑚𝑎𝑥 be the max number of previous knowledge that can be associated, the complexity of generating candidate rule edges is 𝑂 𝑓 ( 2 𝑚𝑎𝑥 ∗ |F |) , where 𝑓 2 𝑚𝑎𝑥 is brought by the triadic closure searching. Since the complexity of computing the error cost 𝐿 (G| 𝑀 ) is constant, the complexities of ranking and selecting rules and edges are 𝑂 (|P( 𝑣 )| 𝑙𝑜𝑔 |P( 𝑣 )|) and 𝑂 (|P( 𝑒 )| 𝑙𝑜𝑔 |P( 𝑒 )|) , where |P( 𝑣 )| and |P( 𝑒 )| are the numbers of candidate atomic rules and rule edges. The scoring process and the updater module need to traverse the category of an entity and find the associated knowledge, leading to complexities as 𝑂 (| 𝐶 𝑠 ( )| + | 𝐶 𝑜 ( )| + 𝑓 𝑚𝑎𝑥 ) . The monitor only requires computing 𝐿 (N G 𝑜 ) , which is a small constant.

## 4.7 Generalize to Time-duration-based TKGs

Different from timestamp-based facts discussed before, each fact ( 𝑠, 𝑟, 𝑜, 𝑡 𝑠𝑡𝑎𝑟𝑡 , 𝑡 𝑒𝑛𝑑 ) in time-durationbased TKGs [10] is associated with start and end timestamps to indicate its valid duration, e.g., ( 𝐵𝑖𝑙𝑙𝐺𝑎𝑡𝑒𝑠, 𝑀𝑎𝑟𝑟𝑖𝑒𝑑𝑤𝑖𝑡ℎ, 𝑀𝑒𝑙𝑖𝑛𝑑𝑎, 1994 1 1 2021 5 3 . Similarly, conceptual, time and missing / / , / / ) errors can also exist in such TKGs.

Conceptual errors. Time-duration-based and timestamp-based facts only differ in their time annotations. Since the detection of conceptual errors only relies on finding the conflicts of interaction preference for entities and not related to time information, the proposed static score can be seamlessly used in time-duration-based TKGs.

Time errors. Time-duration-based facts can be invalid due to delays or errors in extracting start and end timestamps, causing conflicts with the timestamps of other valid facts, e.g., the relation 𝐶ℎ𝑎𝑖𝑟𝑚𝑎𝑛𝑜𝑓 should not start after the 𝑊𝑜𝑟𝑘𝑠𝑎𝑡 relation ends between a person and a company. Therefore, time errors can be detected by finding such conflicts. Since rule edges indicate that the tail atomic rule should follow the head atomic rule, we can create four types of rule graphs for each time-duration-based TKG by generating rule edges using different time annotation combinations:

- · ST.-ST. This rule graph is generated by only considering 𝑡 𝑠𝑡𝑎𝑟𝑡 of facts. Each edge describes that an atomic rule should start after the other one has started. Facts are first transferred to timestamp-based by only preserving 𝑡 𝑠𝑡𝑎𝑟𝑡 and then Algorithm 1 is used for construction.
- · ED.-ED. This rule graph is generated by only considering 𝑡 𝑒𝑛𝑑 during construction. Each edge describes that an atomic rule should end after the other one has ended.
- · ST.-ED. Each edge in this rule graph indicates that one atomic rule should end after another has started. During associating atomic rules (Section 4.3.2), 𝑡 𝑒𝑛𝑑 is used for tail fact and 𝑡 𝑠𝑡𝑎𝑟𝑡 is used for head fact.

Table 1. Statistics of datasets.

| Dataset     | |E|    |   |R| | |T |   | |F |      | 𝑁 𝑐    | 𝑁 𝑡    | 𝑁 𝑚    |
|-------------|--------|-------|--------|-----------|--------|--------|--------|
| ICEWS 14    | 7,128  |   230 | 365    | 90,730    | 2,198  | 2,198  | 2,198  |
| ICEWS 05-15 | 10,488 |   251 | 4,017  | 461,329   | 13,682 | 13,682 | 13,682 |
| YAGO 11k    | 9,736  |    10 | 2,801  | 161,540   | 6,004  | 6,004  | 6,004  |
| GDELT       | 7,691  |   240 | 2,975  | 3,419,607 | 91,418 | 91,418 | 91,418 |
| Wikidata    | 12,554 |    24 | 2,270  | 669,934   | 9,096  | 9,096  | 9,096  |

- · ED.-ST. Each edge in this rule graph describes that an atomic rule should start after the other one has ended. Similarly, 𝑡 𝑠𝑡𝑎𝑟𝑡 of a fact will be used if it serves as a tail fact, and 𝑡 𝑒𝑛𝑑 will be used if it is a head fact.

Given these rule graphs, the scoring process (Section 4.3.4) is separately performed on each rule graph, and then we use the average of four derived scores as the final score of a fact.

Missing errors. As the interaction preference and time conflicts are measured, missing errors can be detected by finding uninstantiateable nodes with few conflicts in all four rule graphs. In Section 5.7, we experimentally analyze the effectiveness of this strategy.

## 5 Experiments

We conduct extensive experiments on five real-world TKGs and our experiments aim to answer the following research questions:

- · RQ1. How well is AnoT able to detect anomalies?
- · RQ2. How does each component of AnoT contribute to its performance and is AnoT robust to the hyper-parameters?
- · RQ3. Is AnoT efficient in detecting anomalies?
- · RQ4. Is the detection of AnoT interpretable?
- · RQ5. Can AnoT generalize to the time-duration-based TKGs?

## 5.1 Datasets

Real-world TKGs used in our experiments are shown in Table 1. 𝑁 𝑐 , 𝑁 𝑡 , and 𝑁 𝑚 are the number of conceptual, time, and missing errors in each dataset. For each TKG, we use knowledge in the former 60% timestamps to construct the model and the latter 40% for evaluation (10% for validation and 30% for testing). We follow previous work [16] to inject synthetic anomalies by randomly perturbing valid knowledge. For each kind of anomaly (i.e., conceptual, time, and missing errors), we randomly perturb 15% valid knowledge as the anomalies. For conceptual errors, each sampled valid knowledge ( 𝑠, 𝑟, 𝑜, 𝑡 ) is randomly perturbed as ( 𝑠, 𝑟, 𝑜 ′ , 𝑡 ) ∉ F or ( 𝑠, 𝑟 ′ , 𝑜, 𝑡 ) ∉ F , where 𝑜 ′ ∈ E and 𝑟 ′ ∈ R . For time errors, each sampled valid knowledge ( 𝑠, 𝑟, 𝑜, 𝑡 ) is randomly perturbed as ( 𝑠, 𝑟, 𝑜, 𝑡 ′ ) where 𝑡 ∈ T and 𝑡 ′ ∉ T . We keep a large span between 𝑡 and 𝑡 ′ to avoid false anomalies. For missing errors, we directly delete the sampled valid knowledge from TKG to simulate the knowledge missing. More detailed descriptions of these TKGs are in [29]. Note that for the time-duration-based dataset Wikidata, the conceptual errors and missing errors are generated similarly. The time errors are generated by randomly perturbing 𝑡 𝑠𝑡𝑎𝑟𝑡 or 𝑡 𝑒𝑛𝑑 . We ensure each invalid knowledge has 𝑡 ′ 𝑠𝑡𝑎𝑟𝑡 ≤ 𝑡 ′ 𝑒𝑛𝑑 to avoid being meaningless.

## 5.2 Experimental Setting

Implementation details. Weimplement AnoT with Python and all the experiments are performed with Intel Xeon E5-2650 v3 CPU @ 2.30G Hz processor and 128 GB RAM. We use the officially released code of baseline models to perform the experiments and for each baseline model and

Fig. 5. Performance of ANoT and RE-GCN when different proportions of offline preserved knowledge are used to construct the optimal rule graph. Concept, time, and missing respectively refer to conceptual errors, time errors, and missing errors.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00872v2-figure-b93cf0e3-5451-418e-b0dc-603868fd9c7f.jpg)

AnoT, we tune its hyper-parameters using a grid search. During the candidate generation, we set the maximum number of categories of entities 𝑘 ∈ { 1 3 5 10 , , , } . We also set the maximum number of candidate rule edges as 50000 to avoid redundant generation. During the temporal score generation, we set the maximum step 𝐾 ∈ { 1 2 3 4 , , , } , and we set the timespan restriction 𝐿 ∈ { 10 100 1000 2000 , , , } . For a fair comparison, we do not allow AnoT to refresh the rule graph during evaluation.

Evaluation protocols. We evaluate the model performance by precision ( 𝑃 ), 𝐹 𝛽 score, and area under PR-curve ( 𝐴𝑈𝐶 ). For each method, we select the best hyper-parameter settings with the best 𝐹 𝛽 score on the validation set and use 𝐹 𝛽 score to select the best threshold. We set 𝛽 as 0.5 to emphasize the detection precision.

Baselines. We compare AnoT with both temporal knowledge graph representation learning models and dynamic graph anomaly detection models. For TKG representation learning models, typical models in each category are selected, including TNT [28], TELM [54], DE [20], TA [19], Timeplex [25], and RE-GCN [29]. For dynamic graph anomaly detection models, since they are inherently unable to handle rich semantics in TKGs, we only select three typical models: DynAnom [21], F-FADE [8], and TADDY [32].

## 5.3 RQ1: Overall Evaluation

We report the performance of anomaly detection in Table 2. Across all anomaly types and datasets, ANoT achieves the best performance in almost all the metrics, demonstrating its generality. In particular, ANoT largely outperforms baseline methods in detecting time errors (12.2% on AUC) and missing errors (12.3% on F-score) because the baselines neglect the temporal patterns among facts, whereas ANoT can flexibly infer complex patterns based on rule edges. RE-GCN can outperform other baselines in detecting conceptual errors since it integrates the graph structure of TKG. However, since its performance relies on the richness of the graph structure and it fails to extract the patterns of interactions, RE-GCN has a poor performance on sparse dataset (i.e., ICEWS 05-15).

To analyze the stability of different methods, in Figure 5 we report detection results of ANoT and the most powerful baseline method RE-GCN when they are trained by different proportions of data. ANoT can outperform RE-GCN in different training proportions. Even though only 20% data are used to construct the model, ANoT can still achieve remarkable detection AUC, which shows its stability. This result also gives evidence for the effectiveness of our updater module in adapting the rule graph with new knowledge.

Table 2. Performance comparison of baseline models and ANoT on inductive anomaly detection. The best results are boldfaced and the second best results are underlined.

|             | Dataset           | ICEWS 14   | ICEWS 14   | ICEWS 14   | ICEWS 05-15   | ICEWS 05-15   | ICEWS 05-15   | YAGO 11k   | YAGO 11k    | YAGO 11k   | GDELT     | GDELT     | GDELT   |
|-------------|-------------------|------------|------------|------------|---------------|---------------|---------------|------------|-------------|------------|-----------|-----------|---------|
| Model       | Anomaly           | Precision  | 𝐹 𝛽 score  | AUC        | Precision     | 𝐹 𝛽 score     | AUC           | Precision  | 𝐹 𝛽 score   | AUC        | Precision | 𝐹 𝛽 score | AUC     |
| DE          | Conceptual errors | 0.554      | 0.575      | 0.867      | 0.558         | 0.593         | 0.861         | 0.536      | 0.581       | 0.877      | 0.815     | 0.827     | 0.863   |
|             | Time errors       | 0.273      | 0.317      | 0.595      | 0.309         | 0.352         | 0.612         | 0.335      | 0.372       | 0.564      | 0.283     | 0.323     | 0.604   |
|             | Missing errors    | 0.779      | 0.579      | 0.690      | 0.815         | 0.695         | 0.758         | 0.924      | 0.831       | 0.784      | 0.630     | 0.575     | 0.779   |
|             | Conceptual errors | 0.616      | 0.642      | 0.887      | 0.617         | 0.653         | 0.890         | 0.550      | 0.601       | 0.884      | 0.862     | 0.843     | 0.864   |
| TA          | Time errors       | 0.267      | 0.311      | 0.579      | 0.297         | 0.343         | 0.512         | 0.267      | 0.309       | 0.589      | 0.278     | 0.319     | 0.562   |
| TA          | Missing errors    | 0.745      | 0.537      | 0.640      | 0.856         | 0.671         | 0.709         | 0.620      | 0.596       | 0.720      | 0.638     | 0.569     | 0.764   |
| Timeplex    | Conceptual errors | 0.564      | 0.588      | 0.857      | 0.405         | 0.445         | 0.757         | 0.592      | 0.636       | 0.860      | 0.688     | 0.615     | 0.783   |
| Timeplex    | Time errors       | 0.263      | 0.305      | 0.513      | 0.332         | 0.373         | 0.547         | 0.460      | 0.514       | 0.678      | 0.330     | 0.272     | 0.533   |
| Timeplex    | Missing errors    | 0.684      | 0.549      | 0.682      | 0.435         | 0.450         | 0.608         | 0.962      | 0.905       | 0.797      | 0.433     | 0.512     | 0.660   |
| TNT         | Conceptual errors | 0.660      | 0.687      | 0.904      | 0.439         | 0.471         | 0.780         | 0.689      | 0.723       | 0.917      | 0.806     | 0.829     | 0.855   |
| TNT         | Time errors       | 0.365      | 0.409      | 0.502      | 0.372         | 0.407         | 0.556         | 0.442      | 0.490       | 0.671      | 0.402     | 0.430     | 0.526   |
| TNT         | Missing errors    | 0.610      | 0.544      | 0.711      | 0.632         | 0.586         | 0.701         | 0.955      | 0.902       | 0.828      | 0.635     | 0.587     | 0.782   |
| TELM        | Conceptual errors | 0.692      | 0.702      | 0.906      | 0.509         | 0.592         | 0.793         | 0.659      | 0.696       | 0.897      | 0.866     | 0.824     | 0.882   |
| TELM        | Time errors       | 0.372      | 0.416      | 0.522      | 0.391         | 0.421         | 0.607         | 0.439      | 0.489       | 0.662      | 0.389     | 0.417     | 0.512   |
| TELM        | Missing errors    | 0.711      | 0.562      | 0.723      | 0.693         | 0.611         | 0.749         | 0.968      | 0.899       | 0.815      | 0.638     | 0.593     | 0.785   |
| RE-GCN      | Conceptual errors | 0.733      | 0.731      | 0.901      | 0.737         | 0.712         | 0.920         | 0.817      | 0.825       | 0.934      | 0.870     | 0.802     | 0.876   |
| RE-GCN      | Time errors       | 0.357      | 0.398      | 0.617      | 0.334         | 0.370         | 0.667         | 0.410      | 0.432       | 0.687      | 0.365     | 0.395     | 0.628   |
| RE-GCN      | Missing errors    | 0.543      | 0.584      | 0.724      | 0.763         | 0.674         | 0.809         | 0.723      | 0.724       | 0.840      | 0.674     | 0.629     | 0.739   |
| DynAnom     | Conceptual errors | 0.565      | 0.597      | 0.757      | 0.516         | 0.559         | 0.732         | 0.759      | 0.798       | 0.803      | 0.621     | 0.670     | 0.773   |
| DynAnom     | Time errors       | 0.603      | 0.642      | 0.751      | 0.537         | 0.528         | 0.723         | 0.417      | 0.460       | 0.682      | 0.620     | 0.669     | 0.771   |
| DynAnom     | Missing errors    | 0.571      | 0.515      | 0.652      | 0.519         | 0.571         | 0.679         | 0.861      | 0.886       | 0.831      | 0.619     | 0.625     | 0.728   |
|             | Conceptual errors | 0.496      | 0.544      | 0.627      | 0.348         | 0.378         | 0.536         | 0.346      | 0.397       | 0.509      | 0.338     | 0.342     | 0.584   |
|             | Time errors       | 0.490      | 0.536      | 0.615      | 0.361         | 0.383         | 0.514         | 0.452      | 0.483       | 0.502      | 0.359     | 0.378     | 0.551   |
| F-FADE      | Missing errors    | 0.415      | 0.465      | 0.594      | 0.450         | 0.479         | 0.509         | 0.559      | 0.613       | 0.720      | 0.546     | 0.557     | 0.601   |
|             | Conceptual errors | 0.329      | 0.316      | 0.508      | 0.313         | 0.336         | 0.527         | 0.493      | 0.511       | 0.620      | 0.370     | 0.385     | 0.614   |
| TADDY       | Time errors       | 0.517      | 0.569      | 0.653      | 0.344         | 0.369         | 0.502         | 0.479      | 0.496       | 0.691      | 0.386     | 0.402     | 0.593   |
|             | Missing errors    | 0.534      | 0.572      | 0.609      | 0.498         | 0.514         | 0.547         | 0.657      | 0.683       | 0.769      | 0.537     | 0.543     | 0.595   |
|             | Conceptual errors | 0.789      | 0.792      | 0.921      | 0.847         | 0.815         | 0.933         | 0.829      | 0.841       | 0.952      | 0.936     | 0.835     | 0.887   |
| AnoT (ours) | Time errors       | 0.639      | 0.661      | 0.825      | 0.601         | 0.526         |               | 0.524      |             | 0.863      | 0.710     | 0.786     | 0.875   |
|             | Missing errors    | 0.822      | 0.705      | 0.730      | 0.894         | 0.797         | 0.729 0.834   | 0.988      | 0.579 0.933 | 0.867      | 0.683     | 0.696     | 0.841   |

Table 3. Performance comparison of ANoT and its variants.

| Dataset                                     |                            | ICEWS 14    | ICEWS 14    | ICEWS 14    | ICEWS 05-15   | ICEWS 05-15   | ICEWS 05-15   | YAGO 11k    | YAGO 11k    | YAGO 11k    | GDELT       | GDELT       | GDELT       |
|---------------------------------------------|----------------------------|-------------|-------------|-------------|---------------|---------------|---------------|-------------|-------------|-------------|-------------|-------------|-------------|
| Variants                                    | Anomaly                    | Precision   | 𝐹 𝛽 score   | AUC         | Precision     | 𝐹 𝛽 score     | AUC           | Precision   | 𝐹 𝛽 score   | AUC         | Precision   | 𝐹 𝛽 score   | AUC         |
| Conceptual                                  | errors                     | 0.657       | 0.680       | 0.886       | 0.714         | 0.736         | 0.875         | 0.798       | 0.807       | 0.926       | 0.873       | 0.796       | 0.842       |
| category aggregations                       | Time errors                | 0.618       | 0.602       | 0.758       | 0.577         | 0.489         | 0.676         | 0.494       | 0.541       | 0.846       | 0.688       | 0.741       | 0.833       |
|                                             | Missing errors             | 0.784       | 0.667       | 0.681       | 0.856         | 0.743         | 0.801         | 0.965       | 0.903       | 0.842       | 0.656       | 0.618       | 0.799       |
| Conceptual                                  | errors                     | 0.784       | 0.781       | 0.912       | 0.844         | 0.810         | 0.927         | 0.805       | 0.815       | 0.944       | 0.901       | 0.817       | 0.851       |
| Remove updater module                       | Time errors                | 0.551       | 0.585       | 0.796       | 0.530         | 0.519         | 0.697         | 0.438       | 0.494       | 0.807       | 0.670       | 0.712       | 0.812       |
| Missing                                     | errors                     | 0.801       | 0.667       | 0.689       | 0.875         | 0.778         | 0.807         | 0.951       | 0.891       | 0.840       | 0.644       | 0.678       | 0.809       |
| triadic occurring rule edges Time           | errors                     | 0.614       | 0.646       | 0.812       | 0.572         | 0.498         | 0.685         | 0.495       | 0.552       | 0.846       | 0.687       | 0.752       | 0.844       |
| Missing                                     | errors                     | 0.789       | 0.693       | 0.718       | 0.876         | 0.792         | 0.816         | 0.965       | 0.912       | 0.852 0.831 | 0.665 0.698 | 0.635 0.761 | 0.806 0.854 |
| recursive strategy                          | Time errors                | 0.618       | 0.634       | 0.815       | 0.581         | 0.522 0.786   | 0.703 0.814   | 0.494       | 0.550       |             |             | 0.679       | 0.851       |
| Missing                                     | errors                     | 0.792       | 0.692       | 0.714       | 0.882         |               | 0.927         | 0.962       | 0.915       | 0.850       | 0.670       | 0.817       | 0.818       |
| and rule edges only by |A G | ↓ Time errors | Conceptual errors          | 0.784       | 0.781       | 0.912       | 0.844         | 0.810         |               | 0.805       | 0.815       | 0.944       | 0.901       | 0.678       | 0.809       |
|                                             |                            | 0.551       | 0.585       | 0.796       | 0.530         | 0.519         | 0.697         | 0.438       | 0.494       | 0.807       | 0.670       | 0.712       | 0.812       |
|                                             | Missing errors             | 0.801       | 0.667       | 0.689       | 0.875         | 0.778         | 0.807         | 0.951       | 0.891       | 0.840       | 0.644       |             |             |
| as 1 when deriving scores Time              | Conceptual errors          | 0.781       | 0.769       | 0.901       | 0.838         | 0.809         | 0.931         | 0.814       | 0.832       | 0.941       | 0.915       | 0.826       | 0.877       |
|                                             | errors                     | 0.493       | 0.448       | 0.603       | 0.332         | 0.375         | 0.646         | 0.478       | 0.529       | 0.810       | 0.584       | 0.632       | 0.701       |
| Missing                                     | errors                     | 0.820       | 0.584       | 0.693       | 0.859         | 0.732         | 0.798         | 0.976       | 0.873       | 0.857       | 0.636       | 0.642       | 0.788       |
|                                             | Conceptual errors          | 0.789       | 0.792       | 0.921       | 0.847         | 0.815         | 0.933         | 0.829       | 0.841       | 0.952       | 0.936       | 0.835       | 0.887       |
| Original                                    | Time errors Missing errors | 0.639 0.822 | 0.661 0.705 | 0.825 0.730 | 0.601 0.894   | 0.526 0.797   | 0.729 0.834   | 0.524 0.988 | 0.579 0.933 | 0.863 0.867 | 0.710 0.683 | 0.786 0.696 | 0.875 0.841 |

## 5.4 RQ2: Effect of Each Component

Ablation study. As shown in Table 3, removing category aggregations will result in a degradation in performance. This is because first, small relation combinations cannot reflect fine-grained categories; furthermore, aggregation strategies can summarize redundant categories and thus help to alleviate the effect of data noises. Removing the updater module will result in the model failing to adapt to the new knowledge, thus degrading the performance, especially in detecting time errors. This is because temporal patterns change more frequently and thus require timely updating. Figure 6 shows the long-time detection performance, particularly for unseen knowledge, with and

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00872v2-figure-1e23e9d0-a8e6-4b4e-abc0-bb3d490b4956.jpg)

(a)

ICEWS 14

Fig. 6. Inductive detection performance of ANoT across different timestamps on the ICEWS 14 and GDELT datasets.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00872v2-figure-a4e5033c-8299-4e5b-ba79-86f7104b18dd.jpg)

Fig. 7. Performance and detection throughput of ANoT under the different settings of the number of recursive steps 𝐾 .

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00872v2-figure-5e5b9478-04ed-4794-ab7c-e3b43b696e9c.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00872v2-figure-7dee1578-563e-47e4-a6b2-b186999220e2.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00872v2-figure-1ec3fdd0-e763-4500-bd5e-2eb74b98469a.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00872v2-figure-b5a2faaf-29de-4886-bea4-ac549d9930bf.jpg)

without the updater module. We can see that the updater can constantly enhance performance across different timestamps, demonstrating its effectiveness in handling new emerging knowledge and patterns. Since triadic rule edges and recursive strategies only affect the temporal scoring, only results of time errors and missing errors are reported. We can see that they both contribute to the detection performance, demonstrating the effectiveness of triadic rule edges in describing knowledge-occurring patterns and recursive strategies in supporting more stable scoring.

Comparison with variants. We further analyze the effectiveness of our ranking strategy. As shown in Table 3, when we rank the atomic rules and rule edges only by the number of correct assertions |A G | , the performance of all anomaly types degrades. This is because the rules and rule edges with larger |A G | are not necessarily helpful in improving the expressiveness of the model and thus may introduce low-expressive rules and edges. When we only use the number of mapped rules and rule edges to derive scores, the performance degrades especially for the time errors. This shows the effectiveness of considering different expression powers.

Effects of the number of recursive steps 𝐾 . As shown in Figure 7, when 𝐾 increases from 1 to 2, the detection performances on all four datasets improve, which demonstrates the effectiveness of our recursive strategy in achieving more accurate scoring. However, when 𝐾 continues to increase, the performance will gradually degrade. This is because the more steps required by a reachable node, the more uncertain it can be evidence for new knowledge. Thus, a too large 𝐾 will bring much noise during scoring.

Effects of the length of timespan 𝐿 . As shown in Figure 8, different datasets require different 𝐿 to get the best performance. We notice that the best 𝐿 is largely related to the size of each dataset (e.g., 200 for ICEWS 14 and 2000 for ICEWS 05-15). This may be because a larger TKG requires a

Fig. 8. Performance and detection throughput of ANoT under the different settings of the timespan length 𝐿 .

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00872v2-figure-21b6d983-217d-4748-8fff-caa4d4f2c73d.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00872v2-figure-ced9cb03-b2c2-4a3e-8ffc-6862ae317b26.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00872v2-figure-71658ecd-c88c-4f7e-91eb-1ae4f1ac382a.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00872v2-figure-97421d35-5a75-4bee-8fa9-604baa87ab2d.jpg)

Fig. 9. Performance of ANoT under the different settings of the number of entity categories 𝑘 .

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00872v2-figure-ec3d8fb3-59eb-4818-8679-428dabfb37eb.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00872v2-figure-c6e22088-b549-4d88-9aea-9e495e0e1eb7.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00872v2-figure-f25f2b92-4dad-4f22-824f-605da08f40b6.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00872v2-figure-f03d08f2-524a-47f8-9ba7-073f270ced8c.jpg)

larger 𝐿 to extract long-range patterns. The YAGO 11k dataset requires a small 𝐿 since its granularity is a month but other datasets are day or minute.

Effects of the number of entity categories 𝑘 . As shown in Figure 9, two ICEWS datasets get the nearly best performance when 𝑘 is 3, and keep stable when 𝑘 continues to be larger. This demonstrates that our category function can effectively extract the properties shared by different entities. The YAGO 11k dataset has a smaller number of relations which limits the expression power of each relation combination and thus requires more categories.

## 5.5 RQ3: Efficiency Analysis

Detection efficiency. As shown in Figure 7, we analyze how the recursive steps 𝐾 affect the detection efficiency. With 𝐾 increases, the throughput of ANoT gradually decreases, but we can see that the best performance of ANoT does not rely on a large 𝐾 . Therefore, a small 𝐾 can already achieve remarkable performance and acceptable efficiency. Furthermore, When 𝐾 increases, the reachable nodes increase exponentially but our throughput only decreases linearly, which also shows the effectiveness of our strategies.

In Figure 8, we analyze how the timespan 𝐿 affects the detection efficiency. We find that even though 𝐿 increases largely, the throughput only decreases linearly. This is because our ranking and selection strategies can avoid too many redundant rule edges being added to the rule graph, and thus reduce the searching time.

Time consumption of building model. As shown in Table 4, the time consumption of building the optimal rule graph increases sub-linearly when the number of entity categories 𝑘 increases, which is acceptable in practice. The consumption of the YAGO 11k dataset is extremely small since it contains only a few relation categories, therefore the option spaces of the candidate rules and rule edges are smaller than other datasets. The size of the GDELT dataset is much larger than other

Table 4. Model building time, the sizes of the obtained optimal rule graph, and the proportions of explained facts under different settings of category number 𝐾 .

|                                       | ICEWS 14   | ICEWS 14   | ICEWS 14   | ICEWS 14   | ICEWS 05-15   | ICEWS 05-15   | ICEWS 05-15   | ICEWS 05-15   | YAGO 11k   | YAGO 11k   | YAGO 11k   | YAGO 11k   | GDELT   | GDELT   | GDELT   | GDELT   |
|---------------------------------------|------------|------------|------------|------------|---------------|---------------|---------------|---------------|------------|------------|------------|------------|---------|---------|---------|---------|
| Maximum number of entity categories 𝑘 | 1          | 3          | 5          | 10         | 1             | 3             | 5             | 10            | 1          | 3          | 5          | 10         | 1       | 3       | 5       | 10      |
| Building time                         | 49s        | 584s       | 629s       | 660s       | 773s          | 1,239s        | 1,577s        | 1,814s        | 44s        | 50s        | 65s        | 84s        | 1,160s  | 1,585s  | 2,081s  | 2,314s  |
| Number of rule edges                  | 97         | 6,349      | 5,428      | 5,064      | 3,751         | 9,688         | 11,053        | 11,384        | 92         | 76         | 66         | 63         | 87      | 20,223  | 27,847  | 30,106  |
| Proportion of explained facts         | 0.132      | 0.766      | 0.767      | 0.767      | 0.165         | 0.788         | 0.853         | 0.874         | 0.716      | 0.909      | 0.908      | 0.907      | 0.170   | 0.896   | 0.894   | 0.894   |

Table 5. Examples of the obtained entity categories and the entities that are assigned as these categories.

| Entity category (relation combinations)                                                                      | Described entities                                                                                              |
|--------------------------------------------------------------------------------------------------------------|-----------------------------------------------------------------------------------------------------------------|
| host a visit | Express intent to provide military aid | Make statement | Express intent to change leadership | 1. Xi Jinping, 2. Barack Obama, 3. Kim Jong-Un                                                                  |
| Demand economic aid | Threaten with military force | Return or release person(s)                             | 1. Naxalites group, 2. Rebel Group (Abu Sayyaf), 3. Combatant (Djibouti)                                        |
| Died in | Was born in                                                                                        | 1. China, 2. Japan, 3. United States 4. France                                                                  |
| Has won prize                                                                                                | 1. Nobel Peace Prize, 2. Fields Medal 3. Lasker Award                                                           |
| Reduce or break diplomatic relations | Bring a lawsuit against                                               | 1. Rights Activist (Ukraine), 2. Shamsul Islam Khan 3. Center for Reproductive Rights 4. Democratic Labor Party |
| Was born in | Created | Graduated from                                                                       | 1. Harry Weese, 2. I. M. Pei 3. Whit Stillman 4. Robert Ardrey                                                  |

Table 6. Examples of rule edges in the obtained optimal rule graph.

| Entity category (relation combinations)                                                                                                             |
|-----------------------------------------------------------------------------------------------------------------------------------------------------|
| (PERSON, Was born in, COUNTRY) → (PERSON, Died in, COUNTRY)                                                                                         |
| (PERSON, Created, PRODUCTS) → (PERSON, Owns, PRODUCTS)                                                                                              |
| (COUNTRY, Host a visit, PERSON) → (PERSON, Make a visit, COUNTRY)                                                                                   |
| (ORGANIZATION A, Cooperate, ORGANIZATION B) → (ORGANIZATION A, Consult, ORGANIZATION B)                                                             |
| (COUNTRY A, Accuse, PEOPLE), (COUNTRY A, Provide military aid, COUNTRY B) → (COUNTRY B, Accuse, PEOPLE)                                             |
| (PERSON A, Was born in, COUNTRY), (PERSON A, Is married to, PERSON B) → (PERSON B, Was died in, COUNTRY)                                            |
| (COUNTRY A, Investigate, COUNTRY B), (COUNTRY C, Criticize or denounce, COUNTRY B) → (COUNTRY A, Express intent to cooperate, COUNTRY C)            |
| (COUNTRY A, Engage in negotiation, COUNTRY B), (COUNTRY C, Halt negotiations, COUNTRY B) → (COUNTRY A, Express intent to meet or negotiate, COUNTRY |

datasets but our ANoT can still handle it within one hour (baselines need over 100 epochs to train while each epoch needs nearly 3 minutes), showing our efficiency.

Size of the optimal rule graph. We further analyze the size of the obtained optimal rule graph in Table 4. As the number of entity categories 𝑘 continuously increases, the number of rule edges becomes stable or even slightly decreases, meaning that the construction of the optimal rule graph is robust to the entity categories. The decrease may be because a larger number of entity categories can expand the number of candidate rules and rule edges, and thus help ANoT to find more powerful patterns. We further find that as 𝑘 increases, the proportion of facts that can be explained gradually increases, which means improvements in the expression power of our rule graph. Combined with the results in Figure 9, the case with a high proportion of explained facts also has a high AUC in detection, showing the effectiveness of our selection strategies.

## 5.6 RQ4: Interpretability Analysis

Category interpretability. We select some representative entity categories and report their corresponding relation combinations and the entities that are assigned as these categories in Table 5. We can see that relations contained in one relation combination have related semantics, e.g., 'Express intent to provide military aid' and 'Make statement' are both political behaviors of leaders. Thus, relation combinations can imply entity categories. For example, 'Was born in' and 'Created' may imply artists, and 'Express intent to provide military aid' and 'Make statement' may imply presidents. The described entities of these categories also give evidence, e.g.' 'Barack Obama' and 'Kim Joung-Un' are both presidents, and 'Harry Weese' and 'I. M. Pei' are both architects. These examples show the interpretability of our framework at the atomic rule level.

Rule edge interpretability. In Table 6 we further select some representative rule edges to show the interpretability of our framework at the rule edge level. The chain-based rule edges extract some direct relevance between facts, such as 'Create' → 'Owns', while the triadic-based rule edges can extract more complex relevance, such as 'Accuse', 'Provide military aid' → 'Accuse' shows that

Table 7. 𝐹 𝛽 score of ANoT and typical TKG embedding models on the time-duration-based TKG dataset Wikidata.

| Model                  |   Conceptual errors |   Time errors |   Missing errors |
|------------------------|---------------------|---------------|------------------|
| DE                     |               0.849 |         0.56  |            0.869 |
| TA                     |               0.859 |         0.53  |            0.701 |
| Timeplex               |               0.866 |         0.668 |            0.898 |
| TNT                    |               0.806 |         0.586 |            0.879 |
| TELM                   |               0.851 |         0.641 |            0.885 |
| RE-GCN                 |               0.858 |         0.697 |            0.903 |
| ANoT (without updater) |               0.961 |         0.687 |            0.951 |
| ANoT                   |               0.967 |         0.806 |            0.956 |

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00872v2-figure-bbb68d9b-39a3-400b-bb28-e7305ee2f76d.jpg)

ST. - ST.

ST. - ED.

ED. - ST.

ED. - ED.

3

5

Maximum number of entity categories k

(b)

Fig. 10. (a) Performance of different adaption strategies. (b) Proportions of facts explained by different rule graphs.

countries with cooperation tend to have the same position. Based on these interpretable rules and rule edges, our ANoT can generate a set of human-readable prompts to describe what patterns a new knowledge comply and what patterns it violates.

## 5.7 RQ5: Generalization Analysis

Detection accuracy. Here we analyze the generalization ability of ANoT to the time-durationbased TKGs. We employ the most popular time-duration TKG benchmark Wikidata [29] for evaluation. As shown in Table 7, ANoT can still outperform existing TKG embedding models, especially for the time errors, demonstrating its generalization ability, and the updater module can help our solution to adapt to time-duration-based pattern changes.

Effectiveness of adaption strategy. As illustrated in Figure 10(a), we can see that our strategy outperforms other simple strategies that can transfer time duration to timestamps, showing the effectiveness of our proposed four types of rule graphs in capturing various patterns in timeduration-based TKGs.

Effectiveness of different rule graphs. Figure 10(b) shows how four types of rule graphs contribute to the performance. We can see that all four types of rule graphs can describe a unique part of time-duration knowledge, showing their necessities. As the number of entity categories increases, each type of rule graph can describe more knowledge.

0.19

0.18

0.17

0.16

0.15

0.14

0.13

0.12

1

10

## 6 Conclusion

In this paper, we make the first attempt at strategies to summarize a temporal knowledge graph and first explore how to inductively detect anomalies in TKG. We propose a novel rule graph to map a TKG as a set of human-readable rules and rule edges. The rule graph allows us to flexibly infer complex patterns. Based on the rule graph, we propose an ANoT framework, which can efficiently detect anomaly knowledge by traversing the rule graph, and effectively adapt the rule graph to new knowledge. Extensive experimental results demonstrate the superiority of ANoT in accuracy, robustness, efficiency, and interpretability. In our future works, integrating our rule graph with graph learning methods is an interesting direction.

## Acknowledgments

This work is supported by the National Natural Science Foundation of China (No. 62276047) and Shenzhen Science and Technology Program (No. JCYJ20210324121213037).

## References

- [1] Charu C. Aggarwal, Yuchen Zhao, and Philip S. Yu. 2011. Outlier detection in graph streams. In Proceedings of the 27th International Conference on Data Engineering, ICDE 2011, April 11-16, 2011, Hannover, Germany . 399-409.
- [2] Rafaël Van Belle, Charles Van Damme, Hendrik Tytgat, and Jochen De Weerdt. 2022. Inductive Graph Representation Learning for fraud detection. Expert Syst. Appl. 193 (2022), 116463.
- [3] Caleb Belth, Xinyi Zheng, and Danai Koutra. 2020. Mining Persistent Activity in Continually Evolving Networks. In KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23-27, 2020 . 934-944.
- [4] Caleb Belth, Xinyi Zheng, Jilles Vreeken, and Danai Koutra. 2020. What is Normal, What is Strange, and What is Missing in a Knowledge Graph: Unified Characterization via Inductive Summarization. In WWW'20: The Web Conference 2020, Taipei, Taiwan, April 20-24, 2020 . 1115-1126.
- [5] Siddharth Bhatia, Mohit Wadhwa, Kenji Kawaguchi, Neil Shah, Philip S. Yu, and Bryan Hooi. 2023. Sketch-Based Anomaly Detection in Streaming Graphs. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023, Long Beach, CA, USA, August 6-10, 2023 . 93-104.
- [6] Maximilian Blasi, Manuel Freudenreich, Johannes Horvath, David Richerby, and Ansgar Scherp. 2022. Graph Summarization with Graph Neural Networks. CoRR abs/2203.05919 (2022).
- [7] Sejla Cebiric, François Goasdoué, Haridimos Kondylakis, Dimitris Kotzinos, Ioana Manolescu, Georgia Troullinou, and Mussab Zneika. 2019. Summarizing semantic graphs: a survey. VLDB J. 28, 3 (2019), 295-327.
- [8] Yen-Yu Chang, Pan Li, Rok Sosic, M. H. Afifi, Marco Schweighauser, and Jure Leskovec. 2021. F-FADE: Frequency Factorization for Anomaly Detection in Edge Streams. In WSDM '21, The Fourteenth ACM International Conference on Web Search and Data Mining, Virtual Event, Israel, March 8-12, 2021 . 589-597.
- [9] Chen Chen, Cindy Xide Lin, Matt Fredrikson, Mihai Christodorescu, Xifeng Yan, and Jiawei Han. 2009. Mining Graph Patterns Efficiently via Randomized Summaries. Proc. VLDB Endow. 2, 1 (2009), 742-753.
- [10] Shib Sankar Dasgupta, Swayambhu Nath Ray, and Partha P. Talukdar. 2018. HyTE: Hyperplane-based Temporally aware Knowledge Graph Embedding. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, Brussels, Belgium, October 31 - November 4, 2018 . 2001-2011.
- [11] Kaize Ding, Jundong Li, Nitin Agarwal, and Huan Liu. 2020. Inductive Anomaly Detection on Attributed Networks. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020 . 1288-1294.
- [12] Dhivya Eswaran and Christos Faloutsos. 2018. SedanSpot: Detecting Anomalies in Edge Streams. In IEEE International Conference on Data Mining, ICDM 2018, Singapore, November 17-20, 2018 . 953-958.
- [13] Dhivya Eswaran, Christos Faloutsos, Sudipto Guha, and Nina Mishra. 2018. SpotLight: Detecting Anomalies in Streaming Graphs. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery &amp; Data Mining, KDD 2018, London, UK, August 19-23, 2018 . 1378-1386.
- [14] Wenfei Fan, Ruochun Jin, Ping Lu, Chao Tian, and Ruiqi Xu. 2022. Towards Event Prediction in Temporal Graphs. Proc. VLDB Endow. 15, 9 (2022), 1861-1874.
- [15] Yujie Fan, Yanfang Ye, Qian Peng, Jianfei Zhang, Yiming Zhang, Xusheng Xiao, Chuan Shi, Qi Xiong, Fudong Shao, and Liang Zhao. 2020. Metagraph Aggregated Heterogeneous Graph Neural Network for Illicit Traded Product Identification in Underground Market. In 20th IEEE International Conference on Data Mining, ICDM 2020, Sorrento, Italy, November 17-20, 2020 . 132-141.

| [16]   | Lanting Fang, Kaiyu Feng, Jie Gui, Shanshan Feng, and Aiqun Hu. 2023. Anonymous Edge Representation for Inductive Anomaly Detection in Dynamic Bipartite Graphs. Proc. VLDB Endow. 16, 5 (2023), 1154-1167.                                                                                                                                                               |
|--------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [17]   | Esther Galbrun. 2022. The minimum description length principle for pattern mining: a survey. Data Min. Knowl. Discov. 36, 5 (2022), 1679-1727.                                                                                                                                                                                                                            |
| [18]   | Junyang Gao, Xian Li, Yifan Ethan Xu, Bunyamin Sisman, Xin Luna Dong, and Jun Yang. 2019. Efficient Knowledge Graph Accuracy Evaluation. Proc. VLDB Endow. 12, 11 (2019), 1679-1691.                                                                                                                                                                                      |
| [19]   | Alberto García-Durán, Sebastijan Dumancic, and Mathias Niepert. 2018. Learning Sequence Encoders for Temporal Knowledge Graph Completion. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, Brussels, Belgium, October 31 - November 4, 2018 . 4816-4821.                                                                        |
| [20]   | Rishab Goel, Seyed Mehran Kazemi, Marcus A. Brubaker, and Pascal Poupart. 2020. Diachronic Embedding for Temporal Knowledge Graph Completion. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, New York, NY, USA, February 7-12, 2020 . 3988-3995. |
| [21]   | Xingzhi Guo, Baojian Zhou, and Steven Skiena. 2022. Subset Node Anomaly Tracking over Large Dynamic Graphs. In KDD '22: The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 14 - 18, 2022 . 475-485.                                                                                                                       |
| [22]   | Pankaj Gupta, Venu Satuluri, Ajeet Grewal, Siva Gurumurthy, Volodymyr Zhabiuk, Quannan Li, and Jimmy Lin. 2014. Real-Time Twitter Recommendation: Online Motif Detection in Large Dynamic Graphs. Proc. VLDB Endow. 7, 13 (2014), 1379-1380.                                                                                                                              |
| [23]   | Mahdi Hajiabadi, Venkatesh Srinivasan, and Alex Thomo. 2022. Dynamic Graph Summarization: Optimal and Scalable. In IEEE International Conference on Big Data, Big Data 2022, Osaka, Japan, December 17-20, 2022 . 545-554.                                                                                                                                                |
| [24]   | David A. Huffman. 1952. A Method for the Construction of Minimum-Redundancy Codes. Proceedings of the IRE. 40, 9 (1952), 1098-1101.                                                                                                                                                                                                                                       |
| [25]   | Prachi Jain, Sushant Rathi, Mausam, and Soumen Chakrabarti. 2020. Temporal Knowledge Base Completion: New Algorithms and Evaluation Protocols. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020 . 3733-3747.                                                                           |
| [26]   | Shengbin Jia, Yang Xiang, Xiaojun Chen, Kun Wang, and Shijia E. 2019. Triple Trustworthiness Measurement for Knowledge Graph. In The World Wide Web Conference, WWW2019,San Francisco, CA, USA, May 13-17, 2019 . 2865-2871.                                                                                                                                              |
| [27]   | Jaehun Jung, Jinhong Jung, and U Kang. 2021. Learning to Walk across Time for Interpretable Temporal Knowledge Graph Completion. In KDD '21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14-18, 2021 . 786-795.                                                                                               |
| [28]   | Timothée Lacroix, Guillaume Obozinski, and Nicolas Usunier. 2020. Tensor Decompositions for Temporal Knowledge Base Completion. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020 .                                                                                                                        |
| [29]   | Zixuan Li, Xiaolong Jin, Wei Li, Saiping Guan, Jiafeng Guo, Huawei Shen, Yuanzhuo Wang, and Xueqi Cheng. 2021. Temporal Knowledge Graph Reasoning Based on Evolutional Representation Learning. In SIGIR '21: The 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, Virtual Event, Canada, July 11-15, 2021 . 408-417.        |
| [30]   | Huafeng Liu, Mingjie Zhou, Mingyang Song, Deqiang Ouyang, Yawen Li, Liping Jing, Jian Yu, and Michael K. Ng. 2023. Learning Hierarchical Preferences for Recommendation with Mixture Intention Neural Stochastic Processes. IEEE Trans. Knowl. Data Eng. (2023). https://doi.org/10.1109/TKDE.2023.3348493                                                                |
| [31]   | Kangzheng Liu, Feng Zhao, Guandong Xu, Xianzhi Wang, and Hai Jin. 2023. RETIA: Relation-Entity Twin-Interact Aggregation for Temporal Knowledge Graph Extrapolation. In 39th IEEE International Conference on Data Engineering, ICDE 2023, Anaheim, CA, USA, April 3-7, 2023 . 1761-1774.                                                                                 |
| [32]   | Yixin Liu, Shirui Pan, Yu Guang Wang, Fei Xiong, Liang Wang, Qingfeng Chen, and Vincent Cheng-Siong Lee. 2023. Anomaly Detection in Dynamic Graphs via Transformer. IEEE Trans. Knowl. Data Eng. 35, 12 (2023), 12081-12094.                                                                                                                                              |
| [33]   | Antonio Maccioni and Daniel J. Abadi. 2016. Scalable Pattern Matching over Compressed Graphs via Dedensification. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016 . 1755-1764.                                                                                          |
| [34]   | Emaad A. Manzoor, Sadegh M. Milajerdi, and Leman Akoglu. 2016. Fast Memory-efficient Anomaly Detection in Streaming Heterogeneous Graphs. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016 . 1035-1044.                                                                  |
| [35]   | Jayanta Mondal and Amol Deshpande. 2012. Managing large dynamic graphs efficiently. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2012, Scottsdale, AZ, USA, May 20-24, 2012 . 145-156.                                                                                                                                         |

- [36] Zara Nasar, Syed Waqar Jaffry, and Muhammad Kamran Malik. 2022. Named Entity Recognition and Relation Extraction: State-of-the-Art. ACM Comput. Surv. 54, 1 (2022), 20:1-20:39.

- [37] Namyong Park, Fuchen Liu, Purvanshi Mehta, Dana Cristofor, Christos Faloutsos, and Yuxiao Dong. 2022. EvoKG: Jointly Modeling Event Time and Network Structure for Reasoning over Temporal Knowledge Graphs. In WSDM '22: The Fifteenth ACM International Conference on Web Search and Data Mining, Virtual Event / Tempe, AZ, USA, February 21 - 25, 2022 . 794-803.
- [38] Jian Pei, Jiawei Han, Behzad Mortazavi-Asl, Helen Pinto, Qiming Chen, Umeshwar Dayal, and Meichun Hsu. 2001. PrefixSpan: Mining Sequential Patterns by Prefix-Projected Growth. In Proceedings of the 17th International Conference on Data Engineering, April 2-6, 2001, Heidelberg, Germany . 215-224.
- [39] Stephen Ranshous, Steve Harenberg, Kshitij Sharma, and Nagiza F. Samatova. 2016. A Scalable Approach for Outlier Detection in Edge Streams Using Sketch-based Approximations. In Proceedings of the 2016 SIAM International Conference on Data Mining, Miami, Florida, USA, May 5-7, 2016 . 189-197.
- [40] Xin Ren, Luyi Bai, Qianwen Xiao, and Xiangxi Meng. 2023. Hierarchical Self-Attention Embedding for Temporal Knowledge Graph Completion. In Proceedings of the ACM Web Conference 2023, WWW 2023, Austin, TX, USA, 30 April 2023 - 4 May 2023 . 2539-2547.
- [41] Jorma Rissanen. 1978. Modeling by shortest data description. Autom. 14, 5 (1978), 465-471.
- [42] Andrea Rossi, Donatella Firmani, Paolo Merialdo, and Tommaso Teofili. 2022. Kelpie: an Explainability Framework for Embedding-based Link Prediction Models. Proc. VLDB Endow. 15, 12 (2022), 3566-3569.
- [43] Tara Safavi, Caleb Belth, Lukas Faber, Davide Mottin, Emmanuel Müller, and Danai Koutra. 2019. Personalized Knowledge Graph Summarization: From the Cloud to Your Pocket. In 2019 IEEE International Conference on Data Mining, ICDM 2019, Beijing, China, November 8-11, 2019 . 528-537.
- [44] Mahsa Salehi and Lida Rashidi. 2018. A Survey on Anomaly detection in Evolving Data: [with Application to Forest Fire Risk Prediction]. SIGKDD Explor. 20, 1 (2018), 13-23.
- [45] Neil Shah, Danai Koutra, Tianmin Zou, Brian Gallagher, and Christos Faloutsos. 2015. TimeCrunch: Interpretable Dynamic Graph Summarization. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, August 10-13, 2015 . 1055-1064.
- [46] Alisa Smirnova and Philippe Cudré-Mauroux. 2019. Relation Extraction Using Distant Supervision: A Survey. ACM Comput. Surv. 51, 5 (2019), 106:1-106:35.
- [47] Kumar Sricharan and Kamalika Das. 2014. Localizing anomalous changes in time-evolving graphs. In International Conference on Management of Data, SIGMOD 2014, Snowbird, UT, USA, June 22-27, 2014 . 1347-1358.
- [48] Jizhi Tang, Yansong Feng, and Dongyan Zhao. 2019. Learning to Update Knowledge Graphs by Reading News. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-IJCNLP 2019, Hong Kong, China, November 3-7, 2019 . 2632-2641.
- [49] Théo Trouillon, Christopher R. Dance, Éric Gaussier, Johannes Welbl, Sebastian Riedel, and Guillaume Bouchard. 2017. Knowledge Graph Completion via Complex Tensor Factorization. J. Mach. Learn. Res. 18 (2017), 130:1-130:38.
- [50] Jiapu Wang, Boyue Wang, Meikang Qiu, Shirui Pan, Bo Xiong, Heng Liu, Linhao Luo, Tengfei Liu, Yongli Hu, Baocai Yin, and Wen Gao. 2023. A Survey on Temporal Knowledge Graph Completion: Taxonomy, Progress, and Prospects. CoRR abs/2308.02457 (2023).
- [51] Pei Wang, Junqi Wang, Pushpi Paranamana, and Patrick Shafto. 2020. A mathematical theory of cooperative communication. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual .
- [52] Jiapeng Wu, Meng Cao, Jackie Chi Kit Cheung, and William L. Hamilton. 2020. TeMP: Temporal Message Passing for Temporal Knowledge Graph Completion. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020 . 5730-5746.
- [53] Yinghui Wu, Shengqi Yang, Mudhakar Srivatsa, Arun Iyengar, and Xifeng Yan. 2013. Summarizing Answer Graphs Induced by Keyword Queries. Proc. VLDB Endow. 6, 14 (2013), 1774-1785.
- [54] Chengjin Xu, Yung-Yu Chen, Mojtaba Nayyeri, and Jens Lehmann. 2021. Temporal Knowledge Graph Completion using a Linear Temporal Regularizer and Multivector Embeddings. In NAACL-HLT . 2569-2578.
- [55] Chenjin Xu, Mojtaba Nayyeri, Fouad Alkhoury, Hamed Shariat Yazdi, and Jens Lehmann. 2020. Temporal Knowledge Graph Completion Based on Time Series Gaussian Embedding. In The Semantic Web - ISWC 2020 - 19th International Semantic Web Conference, Athens, Greece, November 2-6, 2020, Proceedings, Part I . 654-671.
- [56] Chengjin Xu, Mojtaba Nayyeri, Fouad Alkhoury, Hamed Shariat Yazdi, and Jens Lehmann. 2020. TeRo: A Timeaware Knowledge Graph Embedding via Temporal Rotation. In Proceedings of the 28th International Conference on Computational Linguistics, COLING 2020, Barcelona, Spain (Online), December 8-13, 2020 . 1583-1593.
- [57] Jinfa Yang, Xianghua Ying, Yongjie Shi, and Bowei Xing. 2024. Tensor decompositions for temporal knowledge graph completion with time perspective. Expert Syst. Appl. 237, Part A (2024), 121267.
- [58] Jiaxuan You, Xiaobai Ma, Daisy Yi Ding, Mykel J. Kochenderfer, and Jure Leskovec. 2020. Handling Missing Data with Graph Representation Learning. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual .

- [59] Wenchao Yu, Wei Cheng, Charu C. Aggarwal, Kai Zhang, Haifeng Chen, and Wei Wang. 2018. NetWalk: A Flexible Deep Embedding Approach for Anomaly Detection in Dynamic Networks. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery &amp; Data Mining, KDD 2018, London, UK, August 19-23, 2018 . 2672-2681.
- [60] Fu Zhang, Hongzhi Chen, Yuzhe Shi, Jingwei Cheng, and Jinghao Lin. 2024. Joint framework for tensor decompositionbased temporal knowledge graph completion. Inf. Sci. 654 (2024), 119853.
- [61] Jiasheng Zhang, Shuang Liang, Yongpan Sheng, and Jie Shao. 2022. Temporal knowledge graph representation learning with local and global evolutions. Knowl. Based Syst. 251 (2022), 109234.
- [62] Li Zheng, Zhenpeng Li, Jian Li, Zhao Li, and Jun Gao. 2019. AddGraph: Anomaly Detection in Dynamic Graph Using Attention-based Temporal GCN. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019 . 4419-4425.
- [63] Weiguo Zheng, Jeffrey Xu Yu, Lei Zou, and Hong Cheng. 2018. Question Answering Over Knowledge Graphs: Question Understanding Via Template Decomposition. Proc. VLDB Endow. 11, 11 (2018), 1373-1386.
- [64] Xinyi Zhu, Liping Wang, Hao Xin, Xiaohan Wang, Zhifeng Jia, Jiyao Wang, Chunming Ma, and Yuxiang Zengt. 2023. T-FinKB: A Platform of Temporal Financial Knowledge Base Construction. In 39th IEEE International Conference on Data Engineering, ICDE 2023, Anaheim, CA, USA, April 3-7, 2023 . 3671-3674.
Jiasheng Zhang Rex Ying Jie Shao
Online Detection of Anomalies in Temporal Knowledge Graphs with Interpretability
Temporal knowledge graphs (TKGs) are valuable resources for capturing
evolving relationships among entities, yet they are often plagued by noise,
necessitating robust anomaly detection mechanisms. Existing dynamic graph
anomaly detection approaches struggle to capture the rich semantics introduced
by node and edge categories within TKGs, while TKG embedding methods lack
interpretability, undermining the credibility of anomaly detection. Moreover,
these methods falter in adapting to pattern changes and semantic drifts
resulting from knowledge updates. To tackle these challenges, we introduce
AnoT, an efficient TKG summarization method tailored for interpretable online
anomaly detection in TKGs. AnoT begins by summarizing a TKG into a novel rule
graph, enabling flexible inference of complex patterns in TKGs. When new
knowledge emerges, AnoT maps it onto a node in the rule graph and traverses the
rule graph recursively to derive the anomaly score of the knowledge. The
traversal yields reachable nodes that furnish interpretable evidence for the
validity or the anomalous of the new knowledge. Overall, AnoT embodies a
detector-updater-monitor architecture, encompassing a detector for offline TKG
summarization and online scoring, an updater for real-time rule graph updates
based on emerging knowledge, and a monitor for estimating the approximation
error of the rule graph. Experimental results on four real-world datasets
demonstrate that AnoT surpasses existing methods significantly in terms of
accuracy and interoperability. All of the raw datasets and the implementation
of AnoT are provided in https://github.com/zjs123/ANoT.