Abstract
Traditional anomaly detection in network data often assumes that the features identifying a subgraph as anomalous are present within the primary dataset. However, in many real-world scenarios, these features are "implicit"—hidden or entirely absent from the target domain. This paper introduces the Implicit Anomaly Subgraph Detection (IASD) framework, which aligns target networks with auxiliary data from different domains to uncover and explain complex anomalous patterns. By utilizing multi-layer models and high-order contrastive learning, the proposed methods demonstrate superior performance in identifying hidden anomalies such as crime hotspots and epidemic outbreaks.
Introduction
In the study of attributed networks, an anomaly is rarely a single isolated node; it is more frequently a subgraph of connected entities behaving in a deviant manner. Identifying these subgraphs is critical for applications ranging from cybersecurity to public health. However, researchers face two primary hurdles: the "hidden feature" problem, where anomalous indicators are buried in high-dimensional data or missing from the target dataset, and the "explanation" problem, where identifying an anomaly is insufficient without understanding its root cause.
This research addresses these challenges through the lens of "Implicit" anomalies. These are cases where the target dataset appears devoid of anomaly features, but the anomalous nature of a subgraph becomes clear when linked with auxiliary data from other domains—such as correlating urban traffic networks with geographical infrastructure or social media activity.
Methodological Framework
The IASD framework employs three distinct algorithmic approaches to bridge the gap between data silos and enhance detection accuracy:
1. Multi-Layer and Multiple Network Alignment
To handle data spread across different contexts, the framework treats various data sources as layers within a multi-layer network or as separate network models that must be aligned. Two specific algorithms were developed for this purpose:
- Anomaly Subgraph Detection with Feature Transfer (ASDFT): A non-deep learning algorithm designed for multi-layer networks. It facilitates the transfer of features from a "source" layer (where the anomaly is visible) to the "target" layer.
- Anomaly Alignment in Attributed Networks (AAAN): This algorithm operates across multiple distinct network models, fusing auxiliary attributes and aligning them with the target network to provide better explainability for the detected subgraphs.
2. Deep Learning for High-Dimensional Data
For single-network scenarios involving high-dimensional attributes, the paper proposes Anomaly Subgraph Detection through High-order Sample Contrastive Learning (ASD-HC). This method utilizes a Graph Convolutional Network (GCN)-based contrastive learning model. By employing high-order neighbor sampling, the model captures complex, multi-hop relationships that standard first-order GCNs might overlook. It then uses "Non-Parameter Graph Scan" statistics to identify the most likely anomalous subgraphs within the learned feature space.
Experimental Evaluation
The effectiveness of the IASD framework was evaluated using both real-world case studies and standard benchmarks.
Real-World Applications
- Urban Crime and Traffic: By linking city block data with urban traffic networks and criminal event reports, the framework successfully identified crime hotspots that were not apparent from traffic data alone.
- Public Health: The methods were applied to explain the spread of COVID-19 by integrating geographical infrastructure datasets with traffic data. The model demonstrated how population mobility patterns drove epidemic breakouts, providing a clear "why" behind the detected anomalies.
Benchmark Performance
The deep learning component, ASD-HC, was tested against state-of-the-art baselines on five real-world benchmark datasets. The results indicated that ASD-HC consistently outperformed existing methods, particularly in its ability to handle high-dimensional attributes that typically trigger the "curse of dimensionality."
Key Insights and Conclusion
The core contribution of this work is the "Implicit" insight: the realization that anomalies invisible in one data silo can be projected and identified by aligning with auxiliary domains. By integrating multi-domain data, the IASD framework does more than flag suspicious subgraphs; it provides context by identifying which auxiliary features triggered the detection.
While the current deep learning approach (ASD-HC) is optimized for single network models, future work aims to expand this model to incorporate the multi-domain, multi-layer structures used in ASDFT and AAAN. This evolution will combine the powerful feature-extraction capabilities of GCNs with the cross-domain "unhiding" capabilities of the alignment framework, further advancing the field of complex anomaly detection.
Summary updated