# Scalable Anomaly Ranking of Attributed Neighborhoods

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jan 2016.

## Built on by (most cited first, 30 of 33)

- [A Comprehensive Survey on Graph Anomaly Detection with Deep Learning](https://mlsanity.com/paper/2106.07178/) (2021)
- [Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning](https://mlsanity.com/paper/2103.00113/) (2021)
- [Generative and Contrastive Self-Supervised Learning for Graph Anomaly Detection](https://mlsanity.com/paper/2108.09896/) (2021)
- [Graph Anomaly Detection via Multi-Scale Contrastive Learning Networks with Augmented View](https://mlsanity.com/paper/2212.00535/) (2022)
- [ARC: A Generalist Graph Anomaly Detector with In-Context Learning](https://mlsanity.com/paper/2405.16771/) (2024)
- [Truncated Affinity Maximization: One-class Homophily Modeling for Graph Anomaly Detection](https://mlsanity.com/paper/2306.00006/) (2023)
- [Hop-Count Based Self-Supervised Anomaly Detection on Attributed Networks](https://mlsanity.com/paper/2104.07917/) (2021)
- [Cross-Domain Graph Anomaly Detection via Anomaly-aware Contrastive Alignment](https://mlsanity.com/paper/2212.01096/) (2022)
- [Reconstruction Enhanced Multi-View Contrastive Learning for Anomaly Detection on Attributed Networks](https://mlsanity.com/paper/2205.04816/) (2022)
- [PREM: A Simple Yet Effective Approach for Node-Level Graph Anomaly Detection](https://mlsanity.com/paper/2310.11676/) (2023)
- [Generative Semi-supervised Graph Anomaly Detection](https://mlsanity.com/paper/2402.11887/) (2024)
- [From Unsupervised to Few-shot Graph Anomaly Detection: A Multi-scale Contrastive Learning Approach](https://mlsanity.com/paper/2202.05525/) (2022)
- [Higher-order Structure Based Anomaly Detection on Attributed Networks](https://mlsanity.com/paper/2406.04690/) (2024)
- [Open-Set Graph Anomaly Detection via Normal Structure Regularisation](https://mlsanity.com/paper/2311.06835/) (2023)
- [FreeGAD: A Training-Free yet Effective Approach for Graph Anomaly Detection](https://mlsanity.com/paper/2508.10594/) (2025)
- [Graph Anomaly Detection with Unsupervised GNNs](https://mlsanity.com/paper/2210.09535/) (2022)
- [ARISE: Graph Anomaly Detection on Attributed Networks via Substructure Awareness](https://mlsanity.com/paper/2211.15255/) (2022)
- [On the Detection of Reviewer-Author Collusion Rings From Paper Bidding](https://mlsanity.com/paper/2402.07860/) (2024)
- [Deep Dual Support Vector Data Description for Anomaly Detection on Attributed Networks](https://mlsanity.com/paper/2109.00138/) (2021)
- [Anomaly Detection in Graph Structured Data: A Survey](https://mlsanity.com/paper/2405.06172/) (2024)
- [GraphAnoGAN: Detecting Anomalous Snapshots from Attributed Graphs](https://mlsanity.com/paper/2106.15504/) (2021)
- [Anomaly Detection in Networks via Score-Based Generative Models](https://mlsanity.com/paper/2306.15324/) (2023)
- [Detecting Topology Attacks against Graph Neural Networks](https://mlsanity.com/paper/2204.10072/) (2022)
- [Hyperbolic Self-supervised Contrastive Learning Based Network Anomaly Detection](https://mlsanity.com/paper/2209.05049/) (2022)
- [Decoupling anomaly discrimination and representation learning: self-supervised learning for anomaly detection on attributed graph](https://mlsanity.com/paper/2304.05176/) (2023)
- [Label-based Graph Augmentation with Metapath for Graph Anomaly Detection](https://mlsanity.com/paper/2308.10918/) (2023)
- [SCALA: Sparsification-based Contrastive Learning for Anomaly Detection on Attributed Networks](https://mlsanity.com/paper/2401.01625/) (2024)
- [Rethinking Contrastive Learning in Graph Anomaly Detection: A Clean-View Perspective](https://mlsanity.com/paper/2505.18002/) (2025)
- [AC2L-GAD: Active Counterfactual Contrastive Learning for Graph Anomaly Detection](https://mlsanity.com/paper/2601.21171/) (2026)
- [A Graph Encoder-Decoder Network for Unsupervised Anomaly Detection](https://mlsanity.com/paper/2308.07774/) (2023)

## Abstract (arXiv)

Given a graph with node attributes, what neighborhoods are anomalous? To answer this question, one needs a quality score that utilizes both structure and attributes. Popular existing measures either quantify the structure only and ignore the attributes (e.g., conductance), or only consider the connectedness of the nodes inside the neighborhood and ignore the cross-edges at the boundary (e.g., density). In this work we propose normality, a new quality measure for attributed neighborhoods. Normality utilizes structure and attributes together to quantify both internal consistency and external separability. It exhibits two key advantages over other measures: (1) It allows many boundary-edges as long as they can be "exonerated"; i.e., either (i) are expected under a null model, and/or (ii) the boundary nodes do not exhibit the subset of attributes shared by the neighborhood members. Existing measures, in contrast, penalize boundary edges irrespectively. (2) Normality can be efficiently maximized to automatically infer the shared attribute subspace (and respective weights) that characterize a neighborhood. This efficient optimization allows us to process graphs with millions of attributes. We capitalize on our measure to present a novel approach for Anomaly Mining of Entity Neighborhoods (AMEN). Experiments on real-world attributed graphs illustrate the effectiveness of our measure at anomaly detection, outperforming popular approaches including conductance, density, OddBall, and SODA. In addition to anomaly detection, our qualitative analysis demonstrates the utility of normality as a powerful tool to contrast the correlation between structure and attributes across different graphs.