Source-linked AI summary
Structural Temporal Graph Neural Networks for Anomaly Detection in Dynamic Graphs
Lei Cai, Zhengzhang Chen, Chen Luo, Jiaping Gui, Jingchao Ni, Ding Li, Haifeng Chen
TL;DR
Dynamic-graph anomaly detection must account for changing structures and temporal dependencies, while prior embedding methods often focus on node representations. StrGNN extracts labeled enclosing subgraphs, structural features, and temporal representations to detect anomalous edges, outperforming baselines and achieving zero false negatives in an enterprise security application.
Problem
Dynamic-graph anomaly detection requires modeling evolving structural changes around target edges, which prior network-embedding methods largely overlook.
Method
StrGNN extracts h-hop enclosing subgraphs, labels node roles, obtains fixed-size structural features, and uses GRUs to capture temporal information for edge anomaly detection.
Results
StrGNN outperformed four baselines across six benchmark datasets and achieved superior enterprise intrusion detection performance with zero false negatives.
Takeaways & Limitations
The experiments support StrGNN as an effective end-to-end approach for anomalous-edge detection in benchmark dynamic graphs and a real enterprise security system.
Takeaways & Limitations
The graph structural feature extraction module does not itself model temporal information, so temporal processing is needed for dynamic-edge classification.
Abstract
from arXiv · showhide
Detecting anomalies in dynamic graphs is a vital task, with numerous practical applications in areas such as security, finance, and social media. Previous network embedding based methods have been mostly focusing on learning good node representations, whereas largely ignoring the subgraph structural changes related to the target nodes in dynamic graphs. In this paper, we propose StrGNN, an end-to-end structural temporal Graph Neural Network model for detecting anomalous edges in dynamic graphs. In particular, we first extract the $h$-hop enclosing subgraph centered on the target edge and propose the node labeling function to identify the role of each node in the subgraph. Then, we leverage graph convolution operation and Sortpooling layer to extract the fixed-size feature from each snapshot/timestamp. Based on the extracted features, we utilize Gated recurrent units (GRUs) to capture the temporal information for anomaly detection. Extensive experiments on six benchmark datasets and a real enterprise security system demonstrate the effectiveness of StrGNN.
1 Introduction
Dynamic-graph anomaly detection matters because anomalous edges can reveal system faults and cyber-attacks, while many existing embedding methods inadequately model evolving structural changes. StrGNN addresses this by detecting unusual temporal subgraph structures around target edges.
- Anomalous edge detection identifies relationships whose behavior deviates from the network’s majority and can help diagnose system faults.
- In enterprise networks, unexpected interactions between system entities can indicate serious cyber-attacks and damage the enterprise system.
- Most graph embedding approaches target static graphs, while dynamic methods must continually update representations as networks evolve.
- StrGNN detects unusual subgraph structures centered on target edges within time windows while considering temporal dependencies.
- Its pipeline extracts enclosing subgraphs, labels node roles, applies graph convolution and pooling, and processes the resulting features temporally.
2 Related Work
Prior graph anomaly-detection work largely builds node embeddings, whereas dynamic graphs require methods that account for changing vertices, edges, and dependencies across time.
- DeepWalk, LINE, and Node2Vec learn node embeddings through skip-gram-based random-walk or neighborhood-preserving strategies.
- Network embeddings can support anomalous node and edge detection with traditional anomaly detection methods.
- Dynamic graphs vary in both structure and graph membership along the time dimension, making temporal dependency modeling necessary.
- Dyngem learns embeddings for each graph with an auto-encoder and uses a constraint loss to minimize differences across graphs.
3 Method
StrGNN is a structural-temporal framework organized into enclosing-subgraph generation, graph structural feature extraction, and temporal detection components. It is designed to capture structural information across evolving graph snapshots.
- StrGNN addresses dynamic-graph challenges by modeling structural information across graph snapshots for anomaly detection.
- ESG: Enclosing Subgraph Generation: Enclosing Subgraph Generation produces subgraph structures related to the target edge.
- The method comprises Enclosing Subgraph Generation, Graph Structural Feature Extraction, and Temporal Detection Network modules.
- GSFE: Graph Structural Feature Extraction: Graph Structural Feature Extraction converts enclosing-subgraph information into graph structural features.
- TDN: Temporal Detection Network: Temporal Detection Network uses temporal information to distinguish normal from anomalous edges.
GRU GRU GRU GRU
StrGNN analyzes target-edge-centered enclosing subgraphs across time, combining structural feature extraction with temporal modeling for anomaly detection. It addresses varying subgraph sizes and the need to incorporate temporal context.
- ESG: StrGNN extracts h-hop enclosing subgraphs centered on each target edge across a temporal window.The dynamic enclosing subgraph collects the corresponding edge-centered subgraphs from multiple graph snapshots.
- ESG: The node labeling function distinguishes target-edge endpoints and encodes each node’s role in identifying the edge category.It helps distinguish subgraphs that share the same topology but arise around different target edges.
- GSFE: GCN layers learn node embeddings by aggregating information from neighboring nodes and progressively larger neighborhoods.Adding self-loops and stacking layers allows nodes to incorporate information from progressively more distant neighbors.
- GSFE: Sortpooling converts variable-sized enclosing subgraphs into fixed-size features by ranking nodes and selecting the top K embeddings.Subgraphs with fewer than K nodes use zero-padding to preserve a common feature size.
- TDN: GRUs process structural features from successive timestamps to model temporal information and classify the target edge using the final hidden state.The current timestamp’s output is fed into the next timestamp, and the final state is used for edge-category analysis.
- Training: Context-dependent negative sampling generates anomalous training examples by modifying observed normal edges rather than sampling independently from a broad noise distribution.The strategy is motivated by the mismatch between context-independent noise and the observed data distribution.
4 Experiments
StrGNN is evaluated on six benchmark datasets and a real enterprise network against four network-embedding baselines. It outperforms the baselines on benchmark datasets, remains effective with injected anomalies, and shows strong enterprise intrusion-detection results.
- Datasets: Six public datasets from different domains and a real enterprise network are used to evaluate StrGNN.The public datasets cover online messages, news replies, email communication, Internet topology, and Bitcoin ratings; the enterprise network contains 109 hosts and 82 attack records.
- Baselines: StrGNN is compared with four network embedding based baselines, with K-means used for anomaly detection after representation learning for the first three.The baselines are DeepWalk, Node2Vec, Spectral Clustering, and NetWalk.
- Benchmark Results: StrGNN outperforms all four baseline methods on all benchmark datasets and remains acceptable when 10% anomalies are injected.The authors attribute the result to exploiting structural and temporal features for dynamic-graph anomaly detection.
- Embedding Visualization: The GRU-generated embeddings are projected into two dimensions with PCA, and the reported visualization shows anomalies can be easily detected.Figure 3 marks anomalies with red dots and normal samples with blue dots.
- Stability Analysis: AUC increases as the training-data percentage rises from 50% to 75% on UCI Messages, then remains relatively stable.This stability evaluation uses UCI Messages with 10% anomalies.
- Intrusion Detection: StrGNN achieves a 9%-28% AUC increase over four baselines in enterprise intrusion detection, captures all 82 true alerts, and generates 164 false positives.The baselines capture at most 72 true alerts and generate at least 335 false positives.
5 Conclusion
StrGNN detects anomalous edges by mining unusual temporal subgraph structures and is trained end-to-end. Experiments across six benchmark datasets and an enterprise security system support its effectiveness, including zero false negatives in intrusion detection.
- StrGNN detects anomalous edges by mining unusual temporal subgraph structures rather than focusing only on node representations.
- The framework can be trained end-to-end and is not sensitive to the percentage of anomalies.
- Experiments evaluated StrGNN on six benchmark datasets and a real enterprise security system.
- Zero false negatives were achieved when StrGNN was applied to intrusion detection in the enterprise security system.