# GraphSAC: Detecting anomalies in large-scale graphs

**Authors:** Vassilis N. Ioannidis, Dimitris Berberidis, Georgios B. Giannakis  
**arXiv:** [1910.09589](https://arxiv.org/abs/1910.09589)  
**Date:** 2019-10-21  
**Summary page:** https://www.summarizepaper.com/en/paper/1910.09589v1/

## Key points

- GraphSAC is a novel graph-based sampling and consensus approach for detecting anomalous nodes in large-scale graphs.
- Traditional methods are vulnerable to manipulation by adversaries, but GraphSAC mitigates this vulnerability by randomly selecting subsets of nodes and applying graph-aware criteria to filter out contaminated sets.
- A semi-supervised learning (SSL) module is used to estimate nominal label distributions per node, which are minimally impacted by the presence of anomalous nodes.
- Rigorous performance analysis of GraphSAC provides guarantees by bounding the required number of draws, with complexity per draw growing linearly with the number of edges in the graph for efficient SSL implementation.
- GraphSAC can execute draws in parallel, ensuring scalability to large graphs.
- Experimental evaluations show that GraphSAC outperforms existing state-of-the-art alternatives under various anomaly generation models.

## Summary

GraphSAC is a novel graph-based sampling and consensus approach designed to effectively detect anomalous nodes within large-scale graphs. Traditional methods typically rely on the connectivity and attributes of all nodes to assign anomaly scores. However, these approaches are susceptible to compromise by adversaries who may manipulate nodal attributes and network links. In contrast, GraphSAC mitigates this vulnerability by randomly selecting subsets of nodes and applying graph-aware criteria to filter out sets contaminated by anomalous nodes. Subsequently, a semi-supervised learning (SSL) module is utilized to estimate nominal label distributions per node. Importantly, these learned nominal distributions are minimally impacted by the presence of anomalous nodes, making them suitable for direct adoption in anomaly detection tasks. A key feature of GraphSAC is its rigorous performance analysis, which provides guarantees by bounding the required number of draws. The complexity per draw grows linearly with the number of edges in the graph, indicating efficient SSL implementation. Moreover, draws can be executed in parallel, ensuring scalability to large graphs. Experimental evaluations under various anomaly generation models including random walks, clustered anomalies, and contemporary adversarial attacks demonstrate the superiority of GraphSAC over existing state-of-the-art alternatives. Authored by Vassilis N. Ioannidis, Dimitris Berberidis, and Georgios B. Giannakis,the study "GraphSAC: Detecting anomalies in large-scale graphs" presents a comprehensive framework that addresses the challenges associated with anomaly detection in complex network structures.By leveraging graph-based sampling and consensus techniques along with semi-supervised learning methodologies, GraphSAC offers a robust solution for identifying anomalous nodes in real-world graph data sets.