Unsupervised Anomaly Detection in Dynamic Graphs via Compatibility Modeling and Boundary Learning

1 Introduction

Anomaly detection in graphs is a fundamental task that aims to identify instances that deviate substantially from expected patterns, with critical applications in fraud detection [Zhang et al., 2021], cybersecurity [Zhang et al., 2022], and infrastructure monitoring [Berger-Wolf and Saia, 2006; Greene et al., 2010]. While extensive prior work has focused on static graphs [Peng et al., 2018; Ding et al., 2019;

∗Corresponding author: Aiwen Jiang.

Fan et al., 2020; Yuan et al., 2021; Xu et al., 2022; Tang et al., 2023], the continuous evolution of real-world networks has spurred growing interest in dynamic settings. Existing studies on dynamic graph anomaly detection [Yu et al., 2018; Liu et al., 2023; Zheng et al., 2019; Li et al., 2023; Cai et al., 2021] predominantly adopt the discrete-time dynamic graph (DTDG) formulation, modeling graph evolution as a sequence of snapshots sampled at fixed intervals. However, many practical systems generate continuous interaction events, where timely detection is crucial to mitigate downstream impact. The snapshot-based paradigm inevitably introduces temporal discretization error and detection latency, and it may obscure fine-grained temporal dependencies within each interval. These limitations motivate edge-stream modeling with incremental computation, enabling constant-time anomaly evaluation per event.

Although many studies [Eswaran and Faloutsos, 2018; Bhatia et al., 2020; Chang et al., 2021; Bhatia et al., 2023] have proposed edge-stream anomaly detectors, these methods are typically rule-based and tailored to specific anomaly types (e.g., burstiness), which limits their ability to capture more complex anomalies. More recently, learning-based continuous-time dynamic graph models have been introduced for dynamic graph anomaly detection, but they still face several challenges: (1) Feature scarcity: Real-world edge streams often contain little information beyond timestamps, as node and edge attributes are frequently missing or extremely sparse. This is particularly detrimental in anomaly detection, where anomalies are rare and supervision is limited: models must distinguish a small number of abnormal nodes from a large normal population using only subtle interaction patterns. Under such feature-scarce conditions, timestamp-only signals tend to produce weakly discriminative representations, making abnormal and normal nodes difficult to separate. (2) Inadequate interaction modeling: Many anomalies are inherently context-dependent: an interaction may be anomalous not because it is temporally infrequent, but because the destination node is incompatible with the source node's recent context. However, most existing methods encode source and destination nodes independently and then estimate edge likelihood via an MLP, which only implicitly captures source-destination compatibility and is therefore less effective at identifying such mismatched interactions. (3) Ambiguous decision boundary: In practice, anomalous events are orders of magnitude rarer than normal interactions, leading to severe class imbalance. Since reliable anomaly labels are difficult to acquire, most existing methods [Yu et al., 2018; Cai et al., 2021; Liu et al., 2023; Postuvan et al., 2024; Yang et al., 2024] adopt an unsupervised setting, learning normal patterns from normal or unlabeled data and flagging deviations as anomalies. Yet in the absence of explicit supervision, the notion of a meaningful deviation is often ambiguous, resulting in unstable decision boundaries and limited discriminability.

To address these challenges, we propose BAD, an unsupervised dynamic graph anomaly detection framework guided by boundary learning. BAD is designed to address feature scarcity and context-dependent anomalies with a minimalistic continuous-time architecture that relies on learnable node identity embeddings and pairwise compatibility modeling, without requiring node/edge attributes or heavy memorybased components. Specifically, BAD assigns each node a learnable embedding and applies cross-attention between the destination node and the source node's recent neighbors to explicitly capture source-destination compatibility, enabling the detector to identify interactions that deviate from the source's historical context. To further resolve the ambiguous decision boundary induced by the lack of anomaly labels, BAD leverages normalizing flows to learn the feature distribution of normal interactions and derive an explicit separating boundary near its support, allowing anomalies to be identified as samples falling outside the learned normal region. This combination yields a fully unsupervised detector with strong discriminability and robust generalization under realistic feature-scarce and label-scarce settings. Overall, our contributions are threefold:

1. We introduce BAD, an unsupervised anomaly detection framework for continuous-time dynamic graphs that combines temporal modeling with cross-attention to capture context-dependent spatial-temporal deviations.
2. We incorporate normalizing flows to model the distribution of normal interactions and derive an explicit separating boundary, enabling robust detection.
3. Experiments on four real-world datasets against 12 strong baselines show that BAD consistently delivers stateof-the-art performance, demonstrating strong robustness under feature-scarce and label-scarce conditions.

2 RelatedWork

2.1 Anomaly Detection in Graphs

Anomaly detection in graphs has made substantial progress, especially in static settings, where methods such as node2vec [Grover and Leskovec, 2016], DeepWalk [Perozzi et al., 2014], and contrastive learning [Xu et al., 2022] have been used to identify anomalous nodes, edges, or subgraphs. Benchmark studies [Tang et al., 2023] have further evaluated these approaches, highlighting both their strengths and limitations. However, these methods are tailored to static graphs and do not account for the temporal dynamics inherent to real-world networks.

In dynamic settings, many approaches model graphs as sequences of static snapshots and apply static detectors to each snapshot independently [Yu et al., 2018; Zheng et al., 2019; Li et al., 2023]. While this strategy captures coarse temporal variation, it introduces information loss due to fixed sampling intervals and cannot faithfully represent continuous evolution. Some works such as StrGNN [Cai et al., 2021] and TADDY [Liu et al., 2023] incorporate both spatial and temporal signals by coupling separate modules. However, this loosely coupled design often struggles to capture the tightly intertwined spatial-temporal dependencies required for accurate anomaly detection. A major challenge in dynamic graph anomaly detection is the scarcity of labeled anomalous data [Ma et al., 2023; Qiao et al., 2025; Tian et al., 2026], leading to the widespread use of unsupervised learning. Many studies rely on synthetic anomalies, such as randomly connecting unlinked nodes [Liu et al., 2023], to evaluate models. While practical, these methods generate simplistic patterns that fail to reflect real-world complexities, such as coordinated behaviors, sudden structural changes, or temporally correlated events. This highlights the need for more sophisticated anomaly generation techniques and evaluation frameworks that better mimic the dynamic nature of real-world graphs [Hua et al., 2026].

2.2 Continuous-Time Dynamic Graph Representation Learning

Given the importance of dynamic graphs, representation learning on such graphs has attracted significant attention in recent years. One common approach treats dynamic graphs as sequences of snapshots and applies static graph learning methods to each snapshot independently, leading to discretetime methods. These methods sample graph snapshots at fixed time intervals and are easy to combine with existing static graph models. However, they require manually setting the time interval, and different choices of interval may lead to different graph structures. Moreover, because they rely on static techniques within each snapshot, they often ignore the temporal order of interactions among nodes inside the same snapshot. As a result, they may struggle to capture interactions across different time granularities, which can reduce prediction accuracy. To address these limitations, there has been increasing interest in continuous-time methods, which treat dynamic graphs as continuous streams of timestamped links. These methods extend Graph Neural Networks (GNNs) to encode temporal networks and often incorporate memory mechanisms [Rossi et al., 2020b; Ma et al., 2020; Trivedi et al., 2019; Chang et al., 2020; Kumar et al., 2019]. In these approaches, each node is associated with a vector representation that is updated when new interactions occur. Some methods update representations using the node currently being interacted with [Kumar et al., 2019; Trivedi et al., 2019], while others use historical interactions or temporal neighborhoods [Xu et al., 2020; Tian et al., 2024b; Wang et al., 2021a; Tian et al., 2024a]. However, these methods primarily focus on temporal patterns and often pay less attention to the structural patterns inherent in graph data. Inspired by static networks, some studies have incorporated random walks [Wang et al., 2021b;

Jin et al., 2022] to extract structural features, thereby enhancing representation learning on dynamic graphs.

3 Preliminaries

Notions. A Dynamic Graph G can be represented as a Continuous-Time Dynamic Graph (CTDG), which captures the evolution of interactions over time as a chronological sequence of node pairs: G = {(v0 i , v0 j , t0), . . . , (vn i , vn j , tn)}. Here, tn denotes the timestamp and the timestamps are ordered as (0 ≤ t0 ≤ t1 ≤ ... ≤ tn). vn i , vn j ∈ V denote the node id of the n - th interaction at timestamp tn, V is the entire node set. Each node v ∈ V is associated with node feature Fv ∈ Rdv , and each edge (vi, vj, t) represents an interaction from node vi to node vj at time t accompanied by an edge feature eti,j ∈ Rde . The dimension dv and de correspond to the feature sizes of the nodes and edges, respectively. This representation allows for a fine-grained modeling of temporal dynamics and structural changes in the graph, making it particularly suitable for tasks such as anomaly detection in dynamic networks.

Problem Definition. In this work, our objective is to detect anomalous edges in dynamic graphs. Specifically, given an interaction (vi, vj , t) and historical events before t, we aim to develop a model that learns the edge representation for (vi, vj, t) and assigns it a continuous anomaly score in [0, 1], thereby quantifying its degree of abnormality and determining whether the event is anomalous. Following the common practice in dynamic graph anomaly detection, we adopt an unsupervised learning scheme. During training, all edges are treated as normal samples, and no anomaly labels are used.

4 Methodology

4.1 Encoding Layer

To illustrate the computation process of our model, we use the example of computing the representation for an edge. Given the edge (vi, vj , t), we begin by sampling L first-hop historical neighbors for node vi, vj constructing the neighbor node sequence S∗ = [s1∗ , . . . , sl∗ , . . . , sL∗ ], where ∗ represents either i or j. And the set of neighbor {sl∗ }l=1,...,L are ordered based on temporal proximity, with l denoting the l-th neighbor in the sequence. If a node has fewer than L historical neighbors, zero-padding is applied to ensure consistent sequence lengths. Next, we will introduce the encoding layer, which captures both the structural and temporal characteristics of the interactions.

Node/Edge Raw Feature Embedding Encoding. To derive embeddings for interactions, we extract the intrinsic node and edge features of the neighbors in the sequence St∗ . Following prior work, we construct the node and edge embedding sequences S∗ as follows:

where Enode ∗ ∈ RL×dv and Eedge ∗ ∈ RL×dv is the concatenation of the corresponding embeddings of nodes and edges in S∗, respectively.

Learnable Node Embedding (Position encoding): Notably, for non-attributed dynamic graphs, setting node and edge raw feature to zero vectors makes the model rely entirely on structural and temporal signals. To represent nodes with unique identifiers in this feature-scarce setting, we introduce learnable node embeddings that are trained jointly with the model. These embeddings serve as latent identifiers and allow the model to incorporate contextual information from each node's interaction history. Specifically, we learn a positional embedding for the neighbors in

where Epos ∗ ∈ RL×dp is the concatenation of the corresponding depth embeddings of nodes in St∗ .This positional encoding enables the model to capture both short-term and longterm interaction tendencies of the source node, which are critical for characterizing future behaviors. Here, the position of each node reflects its temporal order in the observed interaction sequence. Nevertheless, positional information alone is insufficient, since different nodes may share the same position in the history and thus cannot be uniquely identified by depth alone.

Time Embedding: To enhance nodes' positional information, we also encoding time intervals that usually convey important behaviour information. Specifically, we utilize the widely adopted time encoding function cos(tnω), where ω = {α-(i-1)/β }dt i=1 is employed to encode timestamps. α and β are hyperparameters to make tmax × α-(i-1)/β close to 0 when i close to dt. A cosine function is then applied to project these values into the range of [-1,+1]. Notably, we use relative timestamps instead of absolute timestamps for encoding. In other words, if the timestamp of the sampled interaction is t0, and the specific timestamp for link prediction is t, we utilize cos((tn - t)ω) as the effective relative time encoding function. So the time embedding can be represent as follow:

where Etime ∗ ∈ RL×dt is the concatenation of the corresponding time-interval embeddings of nodes in S∗.

Finally, we get the input node embedding ˆE∗ ∈ RL×(dv+de+dp+dt) for next cross-attention transformer module :

4.2 Pairwise CompatibilityModeling

Considering that edge anomaly detection fundamentally requires judging whether a destination node is compatible with the source node's recent interaction context, we introduce pairwise compatibility modeling to explicitly capture this source-destination relationship. Unlike common designs that first compress each node's history into an independent representation and then apply an MLP to score an interaction, our goal is to let the destination directly query the source's historical neighborhood, so that incompatibility can be detected as a contextual mismatch rather than a purely temporal rarity.

To this end, we implement compatibility modeling via cross-attention between each candidate destination and the source's recent neighbors. Intuitively, the source's neighbor sequence summarizes its evolving interaction preference, and cross-attention allows each destination to selectively attend to the most relevant neighbors when forming its interactionaware representation. This mechanism enables direct assessment of whether the destination aligns with the source's temporal context, which is crucial for identifying contextdependent anomalies. Concretely, the module aims to produce dynamic representations for the interacting nodes vi (source) and vj (destination) at timestamp t by leveraging the constructed embedding sequences. We adopt a two-stream encoder with a cross-attention architecture. In the first stage, a graph Transformer block independently encodes the sourceside neighborhood sequence and the destination-side candidate sequence, producing intermediate embeddings ˜Hi and ˜Hj. In the second stage, a cross-attentional Transformer block explicitly models their dependency by exchanging information between the two streams, yielding the final embedding matrices Hi and Hj . We then extract the dynamic embeddings hi(t) and hj(t) for the interacting nodes vi and vj at time t. The core of the cross-attentional block is a multihead cross-attention operation, where the destination stream queries the source stream and aggregates key-value information to form compatibility-aware representations. Formally, the operations are defined as follows:

where LN denotes the layer normalization and FFN represents a two-layer fully-connected feed-forward network mod-

where σ is an activation function. We sequentially apply these operations to get H∗, which is the output of our graph Transformer block. The cross-attention mechanism enables the model to focus on shared semantic information between the two sequences while filtering out irrelevant details. By exchanging key-value pairs, the encoder emphasizes meaningful patterns and suppresses noise. Additionally, the attentive information from one sequence is integrated into the final representation of the other, ensuring that both representations are enriched with relevant contextual insights. This results in semantically meaningful and highly informative embeddings. Finally, the dynamic node embeddings for the interacting nodes are retrieved from the enriched embedding matrices, allowing the model to effectively capture the temporal and structural nuances of the interactions.

4.3 Boundary-based anomaly detector

In this scetion, we first briefly review normalizing flows and then describe how we integrate them into our framework.

Normalizing Flow. We follow the common definition and denote φθ : X ∈ Rd → Z ∈ Rd as the normalizing flow. It is built as a composition of coupling layers such that φθ = φL ◦· · ·◦φ2 ◦φ1, where θ is the trainable parameters and L is the total number of layers. Defining d-dimensional input and output features of normalizing flow as y0 = x ∈ X and yL = z ∈ Z, the latents can be computed as yl = φl(yl-1), where {yl}L-1 l=1 are the intermediate outputs. The input distribution estimated by model pθ(x) can be calculated according to the change of variables formula as follows:

transformation φl at yl-1, and det means determinant. Normalizing flow can approximate the feature distribution pX with pθ(x). The set of parameters θ is obtained by optimizing the log-likelihoods across the training distribution pX :

We then use normalizing flow to learn the embedding distribution through maximum likelihood optimization. The latent variable distribution pZ(z), z ∈ Rd , is typically assumed to follow a multivariate Gaussian distribution:

where µ is the mean and Σ is the covariance. For simplicity, when training on normal features, the latent variables are assumed to follow N(0, I). Substituting pZ(z) = (2π)- d2 e- 12 zT z in formula (10), the optimization objective becomes::

The maximum likelihood loss function for learning the normal distribution is defined as:

Identify Boundary. With the learned normal feature distribution, we derive an explicit and compact separating boundary. Since the feature space is high-dimensional, we construct decision boundary directly in the log-likelihood space. Specifically, using Eq. (15), we compute the log-likelihoods of all normal features and obtain Pn = {logp(xi)Ni=1 }, which approximates the normal log-likelihood distribution. We then introduce a percentile hyperparameter β to control how far the boundary lies from the distribution center, and set the normal boundary bn as the β-th percentile of the sorted values in Pn (e.g., β = 1). This choice ensures that the expected false positive rate on normal samples is upper bounded by β%. To further improve robustness, we add a margin τ (e.g., τ = 0.1) and define an abnormal boundary as ba = bn-τ . This margin creates a buffer region that facilitates more reliable separation between normal and anomalous features.

Anomaly Scoring. The key advantage of normalizing flows is that they enable exact evaluation of the log-likelihood logp(x) for each input sample x:

Given logp(x), the corresponding likelihood is exp(logp(x)). Because the exponential function is monotonic, logp(x) and exp(logp(x)) induce the same ordering over samples. Moreover, since we maximize the log-likelihood of normal samples in Eq. (14), this likelihood provides a direct measure of normality. We therefore define the anomaly score of a sample x as:

5 Experiments

5.1 Datasets

We evaluate our method on four real-world dynamic graph datasets: Wikipedia, Reddit, Bitcoin-Alpha, and BitcoinOTC. The Wikipedia dataset records user edits on Wikipedia pages, where a user is labeled as anomalous if they are banned after a specific edit. The Reddit dataset consists of user posts on subreddits, and the label indicates whether the user is banned after the corresponding post. BitcoinAlpha and Bitcoin-OTC are who-trusts-whom networks of bitcoin traders from [www.btc-alpha.com] and [www.bitcoinotc.com], where users assign ratings from -10 (total distrust) to +10 (complete trust). We use these time-stamped ratings to identify anomalous nodes and assign dynamic labels. For all datasets, we use the final 15% of interactions in chronological order as the test set for both our method and all baselines. Dataset statistics are provided in Table 1.

5.2 Baselines

We extensively compare BAD against 12 baselines, which can be classified into four categories: rule-based methods, learning-based discrete-time and continuous-time dynamic graph methods.

• Rule-based Stream Methods: SedanSpot [Eswaran and Faloutsos, 2018], MIDAS [Bhatia et al., 2020], FFADE [Chang et al., 2021], Anoedge [Bhatia et al., 2023]
• Learning-based DTDGMethods: StrGNN [Cai et al., 2021], TADDY [Liu et al., 2023]
• Learning-based CTDG Methods: JODIE [Kumar et al., 2019], DyRep [Trivedi et al., 2019], TGAT [Xu et al., 2020], TGN [Rossi et al., 2020a], SAD [Tian et al., 2023], SLADE [Lee et al., 2024]

For the four rule-based methods, which do not involve representation learning, we directly evaluate their performance on the test set without training. For the six learning-based methods, we train each model on the training set and use the checkpoint with the best validation performance for testing. Except for SAD, these learning-based baselines follow the standard two-stage pipeline in [Lee et al., 2024]: first training the encoder via link prediction-based self-supervised learning, and then training a classifier with labels in a supervised manner.

5.3 Experimental setting

Most prior work only use the Area Under the Receiver Operating Characteristic Curve (AUC) as the evaluation metric. However, AUROC can be optimistic under highly skewed label distributions. We therefore also report the Area Under the Precision-Recall Curve (AP) for a more comprehensive assessment. All models are trained for up to 100 epochs, and the checkpoint with the best validation performance is used for testing. We fix the batch size to 100 across all methods and datasets. To mitigate randomness, we report the mean and standard deviation over five independent runs. We optimize model parameters using Adam [Kingma and Ba, 2015] and perform grid search over its main hyperparameters.

5.4 Experimental Results

We compare our proposed method, BAD, with 12 strong baselines across four datasets. As shown in Table 2, BAD achieves the best overall performance across all four datasets, consistently outperforming strong rule-based and learningbased baselines. The results also reveal clear differences among baseline categories. Rule-based methods generally perform poorly, especially on Wikipedia and Reddit, where AP is close to zero. This is expected because these methods are designed for specific anomaly patterns such as burstiness and rely on hand-crafted statistics, which limits their ability to detect more diverse and complex anomalies. Learningbased DTDG methods improve slightly over rule-based approaches but remain substantially worse than CTDG methods. This gap highlights the limitations of the snapshotbased paradigm, where temporal discretization and information loss prevent accurate modeling of fine-grained dynamics in edge streams. Learning-based CTDG methods achieve markedly stronger results, confirming the importance of continuous-time modeling for edge-stream anomaly detection. Among them, SLADE is the strongest baseline across datasets, while SAD occasionally yields competitive AP (e.g., onWikipedia), indicating that explicitly leveraging anomalyoriented training objectives can benefit precision-recall performance. Nevertheless, BAD consistently surpasses these methods on all datasets in AUC and achieves the best AP on three out of four datasets, demonstrating that our minimalistic identity-based representation and explicit sourcedestination compatibility modeling provide additional discriminative power beyond existing CTDG encoders.

In addition, we evaluate the considered methods under different training-test splits. Specifically, we use the first T% of edges as the train set and evaluate each model on the remaining edges. We refer to T as a test start ratio. As shown in Figure 2, BAD outperforms all baseline methods in most settings across different test start ratios. Moreover, on the Wikipedia dataset, BAD shows only a marginal performance drop when the test start ratio changes from 80% to 40%, indicating that using only about half of the dataset for training is sufficient to retain strong detection performance.

We also provide a qualitative analysis of the anomaly scores produced by BAD on the Wikipedia and Reddit datasets in Figure 3. In the top row (Figures 3(a) and 3(b)), the estimated score distributions exhibit a clear separation between normal and anomalous samples. Normal interactions concentrate sharply near low anomaly scores, forming a dominant peak close to zero, whereas anomalies shift toward substantially higher scores with a broader spread. This consistent rightward shift indicates that BAD assigns systematically higher abnormality to truly anomalous events, rather than relying on a few extreme outliers. Although a small overlap remains in the intermediate score range, the two distributions are largely distinguishable, suggesting that BAD learns a discriminative boundary in the score space. The bottom row (Figures 3(c) and 3(d)) further visualizes anomaly scores across the full test stream. Normal samples remain stably clustered at low scores throughout the timeline, demonstrating that BAD produces consistent confidence estimates under continuous temporal evolution. In contrast, anomalous samples appear as sparse points with noticeably higher scores, and this pattern persists across the entire stream rather than being confined to specific periods. This behavior is important for edge-stream anomaly detection, where anomalies are rare and may occur at arbitrary times. Overall, these observations confirm that BAD yields well-separated score distributions and maintains reliable detection signals over long temporal ranges, supporting its strong performance in Table 2.

5.5 Ablation Study

We conduct an ablation study to assess the contribution of each component in BAD by systematically removing key modules. We consider the following variants: w/o pos, which removes the learnable node identity embeddings; w/o time, which excludes time encoding and thus discards temporal information; w/o CA, which replaces cross-attention with selfattention; and w/o NF, which replaces the normalizing flow with a simple MLP classifier. We compare BAD against these variants under the same hyperparameter settings as the full model. As summarized in Table 3, BAD consistently achieves the best performance across all datasets, indicating that each component contributes to the overall effectiveness, albeit to different extents. Among the variants, removing time encoding (w/o time) causes the largest degradation across all datasets. Replacing cross-attention with self-attention (w/o CA) also leads to a clear performance drop, indicating that explicit source-destination compatibility modeling is critical for identifying context-dependent anomalies. In contrast, removing node identity embeddings (w/o pos) results in a smaller yet consistent decline, suggesting that learnable identifiers provide complementary discriminative information under feature-scarce settings. Finally, replacing the normalizing flow with an MLP classifier (w/o NF) yields the most competitive variant but still underperforms the full model, demonstrating that explicit boundary learning further improves separability in the unsupervised detection setting.

6 Conclusion

In this paper, we proposed BAD, an unsupervised framework for anomaly detection in continuous-time dynamic graphs. BAD addresses realistic challenges under extreme class imbalance. It adopts a minimalistic design with learnable node identity embeddings and cross-attention to explicitly model source-destination compatibility, and further leverages normalizing flows to learn the normal interaction distribution and derive a robust separating boundary without anomaly labels. Experiments on four real-world datasets against 12 strong baselines show that BAD consistently achieves superior AUROC and AUPRC, demonstrating its effectiveness in featurescarce and label-scarce settings.

Acknowledgements

This work is supported by National Natural Science Foundation of China ( No. 62366021).