  Anomaly detection in continuous-time dynamic graphs is an emerging field yet
under-explored in the context of learning-based approaches. In this paper, we
pioneer structured analyses of link-level anomalies and graph representation
learning for identifying anomalous links in these graphs. First, we introduce a
fine-grain taxonomy for edge-level anomalies leveraging structural, temporal,
and contextual graph properties. We present a method for generating and
injecting such typed anomalies into graphs. Next, we introduce a novel method
to generate continuous-time dynamic graphs with consistent patterns across
time, structure, and context. To allow temporal graph methods to learn the link
anomaly detection task, we extend the generic link prediction setting by: (1)
conditioning link existence on contextual edge attributes; and (2) refining the
training regime to accommodate diverse perturbations in the negative edge
sampler. Building on this, we benchmark methods for anomaly detection.
Comprehensive experiments on synthetic and real-world datasets -- featuring
synthetic and labeled organic anomalies and employing six state-of-the-art
learning methods -- validate our taxonomy and generation processes for
anomalies and benign graphs, as well as our approach to adapting link
prediction methods for anomaly detection. Our results further reveal that
different learning methods excel in capturing different aspects of graph
normality and detecting different types of anomalies. We conclude with a
comprehensive list of findings highlighting opportunities for future research.
