Abstract
Graph Anomaly Detection (GAD) on attributed networks is critical for identifying irregular patterns in complex data structures. While existing methods effectively identify individual attribute outliers, they often fail to capture collective topological anomalies—densely connected groups of nodes with dissimilar attributes. We present GADMSL, a framework that integrates a density-based region proposal module for topology and graph contrastive learning for attribute-level analysis. By focusing on multi-scale substructures rather than isolated nodes, GADMSL achieves state-of-the-art performance, outperforming existing baselines by up to 7.3% in AUC across benchmark datasets.
Introduction
In attributed networks, where nodes possess both connectivity information (topology) and feature vectors (attributes), anomalies typically manifest in two forms: attribute anomalies and topology anomalies. Attribute anomalies occur when a node's data significantly deviates from its neighborhood. Conversely, topology anomalies represent collective behaviors where uncorrelated nodes form unusually dense substructures, such as "link farms" in social networks.
Traditional GAD algorithms often overlook these collective patterns, focusing instead on point-wise deviations. This "missing the forest for the trees" approach limits the detection of sophisticated topological structures. GADMSL addresses this by shifting the focus to substructure awareness, treating anomalies as collective phenomena.
The GADMSL Framework
The GADMSL architecture employs a dual-pronged strategy to capture both local and structural irregularities simultaneously.
Topology Anomaly Detection
The framework introduces a "Region Proposal" module inspired by computer vision. It utilizes density-based algorithms (specifically the k-core method) to identify high-density regions within the graph. Within these regions, the model calculates the average similarity between node pairs. Clusters exhibiting high topological density but low attribute similarity are flagged as collective topological anomalies.
Attribute Anomaly Detection
To model "normal" attribute patterns, GADMSL leverages self-supervised graph contrastive learning. The model compares a node's attributes to its local subgraph (positive pair) and a distant, random subgraph (negative pair). This process generates high-quality node embeddings that encapsulate local context, which are then used to refine the similarity metrics in the topology module.
Multi-Scale Fusion
Because anomalies can exist at different sizes, GADMSL executes detection across multiple substructure scales and aggregates the resulting scores. A final fusion step combines topology and attribute scores into a unified anomaly ranking for each node.
Experimental Results
The framework was evaluated on six benchmark datasets: Cora, CiteSeer, PubMed, Citation, ACM, and DBLP. To simulate real-world conditions, artificial topological clusters and attribute outliers were injected into these datasets following standard practices.
GADMSL consistently outperformed eight state-of-the-art baselines, including DOMINANT, CoLA, and SL-GAD. Key results include:
- AUC Improvements: Gains of up to 7.30% over the next best performing method.
- AUPRC Gains: Improvements of up to 17.46% in Area Under the Precision-Recall Curve, demonstrating high precision in anomaly identification.
As shown in the ROC curves, GADMSL maintains a superior true-positive rate even at low false-positive thresholds, indicating robust discriminative power across diverse network types.
Conclusion
GADMSL represents a significant advancement in graph anomaly detection by prioritizing substructure awareness. By treating topological anomalies as collective behaviors and utilizing contrastive learning for attribute context, the framework provides a comprehensive solution for complex attributed networks. Future research will focus on adaptive fusion strategies to automatically balance topology and attribute signals without manual parameter tuning.
Summary updated