PaperlayerView exact revision on arXiv

Source-linked AI summary

Anomaly Detection in Dynamic Graphs via Transformer

Yixin Liu, Shirui Pan, Yu Guang Wang, Fei Xiong, Liang Wang, Qingfeng Chen, Vincent CS Lee

arXiv:2106.09876v2cs.LG

TL;DR

Dynamic-graph anomaly detection lacks informative node encodings and must learn from coupled spatial-temporal patterns. TADDY combines comprehensive structural-temporal node encoding with a dynamic graph transformer, and it outperforms existing methods across six real-world datasets. Its computational cost scales as O(τkmI + T en2), and prior methods’ separate spatial-temporal processing remains a stated limitation.

  • Problem

    Dynamic-graph anomaly detection is challenged by missing raw node attributes and difficulty learning discriminative knowledge from coupled spatial-temporal information.

  • Method

    TADDY is an end-to-end transformer framework that uses comprehensive node encoding and jointly models spatial-temporal information for dynamic-graph anomaly detection.

  • Results

    TADDY consistently outperforms all baselines on six dynamic graph datasets, with an average AUC gain of 4.49% over the best baseline.

  • Takeaways & Limitations

    TADDY provides an informative encoding for evolving nodes and captures coupled spatial-temporal information with a sole transformer model.

  • Takeaways & Limitations

    The framework has overall time complexity O(τkmI + T en2), dominated by substructure sampling and processing nodes for target edges.

Abstract

from arXiv · show

Detecting anomalies for dynamic graphs has drawn increasing attention due to their wide applications in social networks, e-commerce, and cybersecurity. Recent deep learning-based approaches have shown promising results over shallow methods. However, they fail to address two core challenges of anomaly detection in dynamic graphs: the lack of informative encoding for unattributed nodes and the difficulty of learning discriminate knowledge from coupled spatial-temporal dynamic graphs. To overcome these challenges, in this paper, we present a novel Transformer-based Anomaly Detection framework for DYnamic graphs (TADDY). Our framework constructs a comprehensive node encoding strategy to better represent each node's structural and temporal roles in an evolving graphs stream. Meanwhile, TADDY captures informative representation from dynamic graphs with coupled spatial-temporal patterns via a dynamic graph transformer model. The extensive experimental results demonstrate that our proposed TADDY framework outperforms the state-of-the-art methods by a large margin on six real-world datasets.

1 INTRODUCTION

Dynamic-graph anomaly detection is important but difficult because unattributed nodes lack informative features and spatial-temporal information is coupled. TADDY addresses these challenges with comprehensive node encoding and a transformer that jointly models spatial and temporal knowledge, achieving state-of-the-art performance on six datasets.

  • Dynamic graph anomaly detection matters for applications such as e-commerce, where anomalous edges can represent fake purchase orders.
  • Existing methods face two challenges: limited raw node attributes and difficulty learning discriminative knowledge from coupled spatial-temporal information.
  • Deep learning methods often use weak node features and separate spatial and temporal modules, which miss coupled spatial-temporal features.
  • TADDY constructs node encodings containing global spatial, local spatial, and temporal information for evolving nodes.
  • TADDY uses a dynamic graph transformer to aggregate spatial and temporal knowledge simultaneously, with edge-based substructure sampling supporting the learning model.
  • TADDY is evaluated on six benchmark datasets and delivers state-of-the-art performance.

2 RELATED WORK

Prior dynamic-graph anomaly detectors include shallow statistical or structural methods and deep models that learn evolving graph patterns. TADDY differs by using comprehensive spatial-temporal node encodings and a single transformer to model coupled information in dynamic graphs.

  • Shallow methods detect anomalous edges using structural connectivity, historical behavior, sketching, clustering, or similarity-based mechanisms.
  • Deep methods such as NetWalk, AddGraph, and H-VGRAE learn dynamic graph patterns with embeddings, graph convolutions, recurrent models, or reconstruction probabilities.
  • Most existing approaches separately extract spatial and temporal features, whereas TADDY models them simultaneously with a transformer network.
  • TADDY uses comprehensive node encodings containing spatial and temporal information instead of naive encodings from unattributed dynamic graphs.
  • Transformers have been applied to heterogeneous, web-scale, molecular, and other graph-learning tasks, while most existing methods focus on static graphs.

3 PROBLEM DEFINITION

The paper models a dynamic graph as a sequence of timestamped snapshots and formulates anomaly detection as assigning an anomaly score to each edge. Training is unsupervised, using normal training edges and abnormality labels only for testing.

  • A dynamic graph is represented as a graph stream of discrete snapshots G_t=(V_t,E_t), with node and edge sets defined at each timestamp.
  • Each snapshot uses a binary adjacency matrix A_t∈R^{n_t×n_t} to indicate whether node pairs are linked at timestamp t.
  • The task is to produce an anomaly score f(e^t_{i,j}) for every edge in each timestamp.
  • Training is unsupervised: all training edges are assumed normal, while binary abnormality labels are used during testing.
  • Normal and anomalous edges are often imbalanced, with normal edges substantially more numerous than anomalous edges.

4 METHODOLOGY

TADDY combines edge-based substructure sampling, spatial-temporal node encoding, a dynamic graph transformer, and a discriminative anomaly detector in an end-to-end framework.

  • TADDY has four components: edge-based substructure sampling, spatial-temporal node encoding, a dynamic graph transformer, and a discriminative anomaly detector.
  • The framework is trained end-to-end so anomaly scores are output and learned directly.

4.1 Edge-based Substructure Sampling

TADDY samples fixed-size, importance-aware local substructures around target edges across a temporal window. Graph diffusion ranks contextual nodes to reduce noisy, inefficient h-hop sampling while preserving structurally relevant context.

  • Each dynamic-graph edge is treated as a target edge and sampled as the center of a local substructure containing its target nodes and contextual nodes.
  • Naive h-hop sampling can be inefficient and noisy on imbalanced-degree graphs and treats shared and exclusive neighbors equally.On UCI Messages, average degree is 14.47 while maximum degree is 255.
  • Graph diffusion produces a fixed-size, importance-aware contextual node set by quantifying global structural connectivity.
  • The method ranks connectivity values, selects the top-k contextual nodes, excludes the target nodes during selection, and unions them with the target nodes.
  • A sliding window of length τ spans timestamps t−τ+1 through t, and sampled node sets from those snapshots are integrated to capture graph evolution.

4.2 Spatial-temporal Node Encoding

TADDY constructs node encodings for unattributed dynamic graphs from global structure, local connectivity, and relative time. These three terms are fused by summation for efficient input to the transformer.

  • Identity features cannot adequately represent structural roles, temporal status, large-scale graphs, or dynamically changing node sets.
  • The proposed encoding has diffusion-based spatial, distance-based spatial, and relative temporal components.The two spatial terms capture global and local structural roles, while the temporal term represents each node’s temporal information.
  • Diffusion-based spatial encoding ranks nodes by their diffusion values and applies a learnable linear mapping to represent global structural roles.
  • Distance-based spatial encoding uses each node’s distance to the target edge, decomposed through the minimum relative distance to its two target nodes.
  • Relative temporal encoding uses the difference between the target-edge time and each node’s timestamp, then applies a learnable linear mapping.
  • The three encoding terms are summed rather than concatenated to reduce the fused representation’s dimension and improve running efficiency.

4.3 Dynamic Graph Transformer

The dynamic graph transformer uses node encodings across multiple timestamps as input to a single encoder, capturing spatial and temporal information jointly before pooling node embeddings into a target edge embedding.

  • Hybrid spatial-temporal models may miss information crossing the two domains, producing sub-optimal representations.
  • A single transformer encoder processes multiple timestamps of node encodings to capture spatial and temporal features simultaneously.
  • Attention layers exchange information among nodes in a sampled substructure and adaptively aggregate their embeddings.
  • The transformer input is the target edge’s encoding matrix, and the final output is a node embedding matrix with one row per node.
  • Average pooling converts the substructure’s node embeddings into a target edge embedding vector.

4.4 Discriminative Anomaly Detector

TADDY learns edge anomaly scores end to end by contrasting observed edges with sampled negative edges using pseudo labels and binary cross-entropy.

  • Because training data lacks ground-truth anomalies, TADDY generates pseudo anomalies through negative edge sampling.
  • For each timestamp, the method samples as many candidate node pairs as existing edges and rejects pairs present in any training snapshot.
  • A fully connected layer with Sigmoid activation maps each edge embedding to an anomaly score.
  • Binary cross-entropy assigns pseudo label 0 to positive edges and 1 to negative edges, encouraging lower scores for positives.
  • The framework iteratively samples substructures, encodes nodes, computes transformer embeddings and scores, then updates parameters by backpropagation.

4.5 Complexity Analysis

The overall time complexity of TADDY is O(τkmI + T en^2), dominated by substructure processing and graph diffusion.

  • The overall time complexity is O(τkmI + T en^2), combining per-edge processing across iterations with graph diffusion across timestamps.
  • For one edge, spatial-temporal encoding and transformer processing require O(τk) time, yielding O(τkmI) across m edges and I iterations.
  • Edge-based substructure sampling requires O(T en^2) time for graph diffusion, while anomaly scoring costs O(mI) and is negligible comparatively.

5 EXPERIMENTS

TADDY is evaluated on six real-world dynamic-graph datasets using injected anomalies, AUC, and comparisons with graph-embedding and deep dynamic baselines. It consistently achieves the best reported performance, with larger gains under scarce anomalies and on Bitcoin datasets.

  • Experimental setup: Experiments use six real-world dynamic-graph datasets spanning social, communication, trust, and Internet connectivity networks.
  • Experimental setup: The first 50% of timestamps forms training data and the latter 50% forms test data; anomalous edges are injected into test snapshots.
  • Experimental setup: AUC is the primary metric, measuring the probability that a randomly selected anomalous edge ranks above a normal edge.
  • Performance comparison: TADDY consistently outperforms all baselines across six datasets and anomaly proportions, gaining 4.49% AUC over the best baseline on average.
  • Performance comparison: Deep dynamic methods outperform graph-embedding methods, which the authors attribute to incorporating interactions from previous timestamps.
  • Performance comparison: Under anomaly proportions of 1%, 5%, and 10%, TADDY’s average AUC gaps over the best baseline are 5.35%, 3.69%, and 4.43%, respectively.
  • Performance comparison: On Bitcoin-Alpha and Bitcoin-OTC, TADDY’s average AUC gain is 6.42%, compared with 3.53% on the remaining datasets.

5.3 Parameter Sensitivity

TADDY’s performance depends on the sampled context, temporal window, representation capacity, and training-data ratio. The sensitivity results support parameter choices that balance detection performance, stability, and efficiency across datasets.

  • Edge-based substructure sampling: When k > 5, AUC tends to stabilize, so TADDY fixes k = 5 to balance performance and efficiency.Larger contextual sets add little performance while increasing running cost linearly with k.
  • Edge-based substructure sampling: The appropriate time-window size τ differs by dataset: smaller windows benefit UCI Messages, whereas both Bitcoin datasets require longer horizons.The stated explanation is that temporal dependence varies across datasets.
  • Transformer parameters: AUC increases with d on Bitcoin-Alpha and Bitcoin-OTC until stabilizing, while d = 8 performs best on UCI Messages.The paper attributes overly large dimensions to possible noisy information capture by the transformer.
  • Transformer parameters: The number of transformer layers has limited impact overall, except that Bitcoin-Alpha AUC drops at L = 1; TADDY therefore fixes L = 2.This choice balances running speed and detection performance.
  • Training ratios: AUC increases smoothly with the training ratio, while variance decreases as the ratio grows.Even with 20% training data, TADDY remains competitive, especially on the two Bitcoin datasets.
  • Ablation study: Removing distance-based spatial encoding sharply reduces AUC to about 50%, whereas diffusion-based and relative temporal encodings generally have minor contributions.Combining all three encoding types usually yields the highest AUC, except on UCI Messages.

6 CONCLUSION

TADDY is an end-to-end framework for anomaly detection in dynamic graphs, combining substructure sampling, comprehensive spatial-temporal node encoding, a dynamic graph transformer, and anomaly detection. Experiments on real-world datasets report high effectiveness and significant improvements over existing methods.

  • 6 CONCLUSION: TADDY combines edge-based substructure sampling, spatial-temporal node encoding, a dynamic graph transformer, and a discriminative anomaly detector.Its node encoding represents evolving node roles, while one transformer captures coupled spatial-temporal information.
  • 6 CONCLUSION: Experiments on several real-world datasets show that TADDY detects dynamic-graph anomalies effectively and significantly outperforms existing methods.
Loading 2106.09876v2…