Technical Summary: Learning Discriminative and Generalizable Anomaly Detector for Dynamic Graph with Limited Supervision (SDGAD)

1. Problem Definition

Dynamic Graph Anomaly Detection (DGAD) is critical for applications such as financial fraud detection, abnormal social interactions, and cyberattack identification. However, existing methods face two primary challenges in real-world scenarios:

1. Scarcity of Labeled Anomalies: Anomalies are extremely rare compared to normal instances, making supervised learning difficult.
2. Limitations of Current Paradigms:
   • Unsupervised Methods: While avoiding the need for labels, they often produce ambiguous decision boundaries where anomaly scores collapse into a narrow, low-valued range with significant overlap between normal and anomalous samples. This makes threshold selection unstable and unreliable.
   • Semi-supervised Methods: These leverage limited labeled anomalies but often overfit to the specific patterns of the few available labels. Consequently, they generalize poorly to unseen anomaly types in open-set scenarios.

The paper addresses the gap of learning a discriminative and generalizable decision boundary from normal/unlabeled data while effectively utilizing limited labeled anomalies without sacrificing generalization to unseen anomalies.

2. Methodology: SDGAD Framework

The authors propose SDGAD, a model-agnostic framework designed to integrate with existing Continuous-Time Dynamic Graph (CTDG) encoders. The framework consists of three core components:

A. Residual Representation Encoding

Standard CTDG encoders aggregate historical interactions with the current event, often resulting in embeddings dominated by long-term context. This weakens the distinction between the current interaction and its recent history, which is crucial for detecting rare anomalies.

• Mechanism: SDGAD computes the residual representation ($\Delta E$) by subtracting the node embedding without the current event from the embedding with the current event.
• Goal: This explicitly preserves the incremental change introduced by the current interaction. Normal behaviors exhibit local continuity (small residuals), while anomalies break this continuity (large residuals), providing a more discriminative signal.

B. Representation Restriction Loss

Different anomaly patterns induce residuals at vastly different scales, hindering the learning of a unified boundary. The authors introduce a restriction loss to constrain normal representations within a specific geometric region.

• Geometry: Instead of a single origin-centered hypersphere (which can suffer from the "soap-bubble phenomenon" where mass concentrates on the boundary), the method constrains normal residuals within an interval bounded by two co-centered hyperspheres (inner radius $r_{min}$ and outer radius $r_{max}$).
• Loss Function:
  • Normal Samples: Penalized if they fall outside the interval $[r_{min}, r_{max}]$, pulling them into a compact region with consistent scales.
  • Anomalous Samples: Penalized if they fall inside the outer hypersphere (specifically, within a margin $\Delta r$ beyond $r_{max}$), pushing them outside the normal region.
• Adaptation: Unlike previous bi-hypersphere methods that assume i.i.d. data, this approach is designed for the non-i.i.d. nature of dynamic graphs and is optimized in an end-to-end manner.

C. Bi-Boundary Optimization

To construct an explicit and robust decision boundary, the framework employs a Normalizing Flow as a density estimator to model the log-likelihood distribution of normal samples.

• Challenge: In high-dimensional spaces, normalizing flows can assign high likelihoods to out-of-distribution inputs, leading to ambiguous boundaries.
• Strategy: The authors propose a bi-boundary optimization strategy. Instead of a single threshold, they define a normal boundary ($B_n$) and an anomalous boundary ($B_a = B_n - \tau$), creating a buffer region (margin $\tau$).
• Objective: The loss function ($L_{BO}$) uses a softplus function to enforce that normal samples lie above $B_n$ and anomalous samples lie below $B_a$. This creates a clear margin, reducing boundary ambiguity and improving robustness against threshold selection.

Overall Training Objective: The total loss combines the maximum-likelihood loss of the normalizing flow ($L_{ML}$), the representation restriction loss ($L_{RR}$), and the bi-boundary optimization loss ($L_{BO}$).

3. Key Contributions

1. SDGAD Framework: A generalizable, model-agnostic framework that performs effectively under both unsupervised and limited-supervision settings.
2. Novel Components:
   • A residual representation encoding mechanism to capture anomaly-relevant deviations.
   • A representation restriction loss using co-centered hyperspheres to normalize scales and improve separability.
   • A bi-boundary optimization strategy using normalizing flows to learn explicit, robust decision boundaries.
3. Comprehensive Evaluation: Extensive experiments on six datasets (including real-world and synthetic anomalies) across three settings: unsupervised, limited supervision, and few-shot.

4. Experimental Results

The framework was evaluated against 15 baselines, including discrete-time (DTDG) and continuous-time (CTDG) methods.

• Performance: SDGAD consistently outperformed all baselines across diverse datasets (Wikipedia, Reddit, MOOC, Enron, UCI, LastFM) and evaluation metrics (AUROC, AP, F1).
• Robustness:
  • In the fully unsupervised setting (S3), SDGAD achieved performance comparable to the limited-supervision setting (S1), demonstrating its ability to learn discriminative boundaries without labels.
  • In few-shot settings (S2), the framework remained effective even with only 1–3 labeled anomalies, whereas semi-supervised baselines showed unstable training and high variance.
• Ablation Studies: Removing any of the three core components (residual encoding, restriction loss, or bi-boundary optimization) led to performance degradation, particularly in F1 scores and score separability.
• Visualization: Score distributions from SDGAD showed clear separation between normal and anomalous samples, whereas baselines often produced collapsed scores near zero, making threshold selection difficult.

5. Significance and Claims

The paper claims that SDGAD addresses a fundamental limitation in DGAD: the trade-off between utilizing limited supervision and maintaining generalization to unseen anomalies. By explicitly learning a discriminative boundary through residual encoding and bi-boundary optimization, the method provides:

• Stable Decision Rules: Unlike unsupervised methods with ambiguous boundaries, SDGAD offers well-calibrated scores suitable for high-stakes applications requiring fixed or tiered cutoffs.
• Generalization: It avoids overfitting to the specific patterns of scarce labeled anomalies, performing robustly in open-set scenarios.
• Model Agnosticism: The framework can be seamlessly integrated with various existing CTDG encoders (e.g., TCL, CAWN, DyGFormer), enhancing their anomaly detection capabilities without requiring a complete redesign of the underlying architecture.

The authors note that while synthetic anomalies in some datasets (like LastFM) may be easily detectable due to simple structural cues, the framework's robustness across diverse settings and its ability to handle real-world anomalies highlight its practical utility. Future work is suggested to refine synthetic anomaly protocols and extend the problem to anomaly typing.