# Multi-scale Anomaly Detection on Attributed Networks

arXiv: https://arxiv.org/abs/1912.04144 · HTML: https://mlsanity.com/paper/1912.04144/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Nov 2019.

## Built on by (most cited first, 13 of 13)

- [A Comprehensive Survey on Graph Anomaly Detection with Deep Learning](https://mlsanity.com/paper/2106.07178/) (2021)
- [GAD-NR: Graph Anomaly Detection via Neighborhood Reconstruction](https://mlsanity.com/paper/2306.01951/) (2023)
- [Hop-Count Based Self-Supervised Anomaly Detection on Attributed Networks](https://mlsanity.com/paper/2104.07917/) (2021)
- [Unsupervised Graph Outlier Detection: Problem Revisit, New Insight, and Superior Method](https://mlsanity.com/paper/2210.12941/) (2022)
- [A Survey of Imbalanced Learning on Graphs: Problems, Techniques, and Future Directions](https://mlsanity.com/paper/2308.13821/) (2023)
- [Spatiotemporal Data Mining: A Survey on Challenges and Open Problems](https://mlsanity.com/paper/2103.17128/) (2021)
- [Higher-order Structure Based Anomaly Detection on Attributed Networks](https://mlsanity.com/paper/2406.04690/) (2024)
- [Improving Generalizability of Graph Anomaly Detection Models via Data Augmentation](https://mlsanity.com/paper/2306.10534/) (2023)
- [BSDM: Background Suppression Diffusion Model for Hyperspectral Anomaly Detection](https://mlsanity.com/paper/2307.09861/) (2023)
- [HIRE: Distilling High-order Relational Knowledge From Heterogeneous Graph Neural Networks](https://mlsanity.com/paper/2207.11887/) (2022)
- [AHEAD: A Triple Attention Based Heterogeneous Graph Anomaly Detection Approach](https://mlsanity.com/paper/2208.08200/) (2022)
- [Co-Membership-based Generic Anomalous Communities Detection](https://mlsanity.com/paper/2203.16246/) (2022)
- [Improving Generalizability of Graph Anomaly Detection Models via Data Augmentation](https://mlsanity.com/paper/2209.10168/) (2022)

## Abstract (arXiv)

Many social and economic systems can be represented as attributed networks encoding the relations between entities who are themselves described by different node attributes. Finding anomalies in these systems is crucial for detecting abuses such as credit card frauds, web spams or network intrusions. Intuitively, anomalous nodes are defined as nodes whose attributes differ starkly from the attributes of a certain set of nodes of reference, called the context of the anomaly. While some methods have proposed to spot anomalies locally, globally or within a community context, the problem remain challenging due to the multi-scale composition of real networks and the heterogeneity of node metadata. Here, we propose a principled way to uncover outlier nodes simultaneously with the context with respect to which they are anomalous, at all relevant scales of the network. We characterize anomalous nodes in terms of the concentration retained for each node after smoothing specific signals localized on the vertices of the graph. Besides, we introduce a graph signal processing formulation of the Markov stability framework used in community detection, in order to find the context of anomalies. The performance of our method is assessed on synthetic and real-world attributed networks and shows superior results concerning state of the art algorithms. Finally, we show the scalability of our approach in large networks employing Chebychev polynomial approximations.