mlsanityData to 14 Oct 2026

Scalable Anomaly Ranking of Attributed Neighborhoods

arXiv 1601.06711 ↗First posted 25 Jan 2016cs.SI physics.soc-phcited by 33

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 6; 2022: 8; 2023: 7; 2024: 6; 2025: 4; 2026: 2.

33 papers.

Sort:

  1. 2021A Comprehensive Survey on Graph Anomaly Detection with Deep Learningcited by 230
  2. 2021Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learningcited by 177
  3. 2021Generative and Contrastive Self-Supervised Learning for Graph Anomaly Detectioncited by 67
  4. 2022Graph Anomaly Detection via Multi-Scale Contrastive Learning Networks with Augmented Viewcited by 55
  5. 2024ARC: A Generalist Graph Anomaly Detector with In-Context Learningcited by 48
  6. 2023Truncated Affinity Maximization: One-class Homophily Modeling for Graph Anomaly Detectioncited by 43
  7. 2021Hop-Count Based Self-Supervised Anomaly Detection on Attributed Networkscited by 31
  8. 2022Cross-Domain Graph Anomaly Detection via Anomaly-aware Contrastive Alignmentcited by 31
  9. 2022Reconstruction Enhanced Multi-View Contrastive Learning for Anomaly Detection on Attributed Networkscited by 28
  10. 2023PREM: A Simple Yet Effective Approach for Node-Level Graph Anomaly Detectioncited by 25
  11. 2024Generative Semi-supervised Graph Anomaly Detectioncited by 22
  12. 2022From Unsupervised to Few-shot Graph Anomaly Detection: A Multi-scale Contrastive Learning Approachcited by 13
21 more
  1. 2024Higher-order Structure Based Anomaly Detection on Attributed Networkscited by 12
  2. 2023Open-Set Graph Anomaly Detection via Normal Structure Regularisationcited by 11
  3. 2025FreeGAD: A Training-Free yet Effective Approach for Graph Anomaly Detectioncited by 10
  4. 2022Graph Anomaly Detection with Unsupervised GNNscited by 8
  5. 2022ARISE: Graph Anomaly Detection on Attributed Networks via Substructure Awarenesscited by 8
  6. 2024On the Detection of Reviewer-Author Collusion Rings From Paper Biddingcited by 7
  7. 2021Deep Dual Support Vector Data Description for Anomaly Detection on Attributed Networkscited by 3
  8. 2024Anomaly Detection in Graph Structured Data: A Surveycited by 3
  9. 2021GraphAnoGAN: Detecting Anomalous Snapshots from Attributed Graphscited by 2
  10. 2023Anomaly Detection in Networks via Score-Based Generative Modelscited by 2
  11. 2022Detecting Topology Attacks against Graph Neural Networkscited by 1
  12. 2022Hyperbolic Self-supervised Contrastive Learning Based Network Anomaly Detectioncited by 1
  13. 2023Decoupling anomaly discrimination and representation learning: self-supervised learning for anomaly detection on attributed graphcited by 1
  14. 2023Label-based Graph Augmentation with Metapath for Graph Anomaly Detectioncited by 1
  15. 2024SCALA: Sparsification-based Contrastive Learning for Anomaly Detection on Attributed Networkscited by 1
  16. 2025Rethinking Contrastive Learning in Graph Anomaly Detection: A Clean-View Perspectivecited by 1
  17. 2026AC2L-GAD: Active Counterfactual Contrastive Learning for Graph Anomaly Detectioncited by 1
  18. 2023A Graph Encoder-Decoder Network for Unsupervised Anomaly Detectioncited by 0
  19. 2025Towards Automated Self-Supervised Learning for Truly Unsupervised Graph Anomaly Detectioncited by 0
  20. 2025Reconciling Attribute and Structural Anomalies for Improved Graph Anomaly Detectioncited by 0
  21. 2026NeighborDiv: Training-free Zero-shot Generalist Graph Anomaly Detection via Neighbor Diversitycited by 0