PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph-based Anomaly Detection and Description: A Survey

Leman Akoglu, Hanghang Tong, Danai Koutra

arXiv:1404.4679v2cs.SIcs.CR

TL;DR

Graph anomaly detection addresses the challenge of finding rare objects in structured data whose interdependencies create long-range correlations. This survey organizes data mining and machine learning methods across graph settings, applications, and evaluation dimensions, while emphasizing anomaly attribution and open challenges. It concludes that detection should be complemented by techniques for explaining anomalies and supporting sense-making.

  • Problem

    Graph data contain interdependent objects with long-range correlations, making anomaly detection different from detecting outliers among independent multidimensional points.

  • Method

    The survey provides a structured overview of graph anomaly detection methods across unsupervised and (semi-)supervised, static and dynamic, and attributed and plain graph settings.

  • Results

    The survey synthesizes detection and attribution techniques and reviews applications in financial, auction, computer, telecommunication, and social networks.

  • Takeaways & Limitations

    Anomaly detection in graphs should support post-detection explanation of root causes and the “why” and “how” of anomalies for human sense-making.

  • Takeaways & Limitations

    Graph anomaly detection must address billion-scale, streaming, complex data, noisy or absent labels, adaptive adversaries, and the difficult explanation of detected anomalies.

Abstract

from arXiv · show

Detecting anomalies in data is a vital task, with numerous high-impact applications in areas such as security, finance, health care, and law enforcement. While numerous techniques have been developed in past years for spotting outliers and anomalies in unstructured collections of multi-dimensional points, with graph data becoming ubiquitous, techniques for structured {\em graph} data have been of focus recently. As objects in graphs have long-range correlations, a suite of novel technology has been developed for anomaly detection in graph data. This survey aims to provide a general, comprehensive, and structured overview of the state-of-the-art methods for anomaly detection in data represented as graphs. As a key contribution, we provide a comprehensive exploration of both data mining and machine learning algorithms for these {\em detection} tasks. we give a general framework for the algorithms categorized under various settings: unsupervised vs. (semi-)supervised approaches, for static vs. dynamic graphs, for attributed vs. plain graphs. We highlight the effectiveness, scalability, generality, and robustness aspects of the methods. What is more, we stress the importance of anomaly {\em attribution} and highlight the major techniques that facilitate digging out the root cause, or the `why', of the detected anomalies for further analysis and sense-making. Finally, we present several real-world applications of graph-based anomaly detection in diverse domains, including financial, auction, computer traffic, and social networks. We conclude our survey with a discussion on open theoretical and practical challenges in the field.

1 Introduction

Graph anomaly detection extends conventional outlier detection by modeling inter-dependent objects and their long-range correlations. This survey organizes graph-based detection methods, applications, and challenges while emphasizing post-detection explanation.

  • Motivation: Anomaly detection identifies rare occurrences with applications in security, finance, health care, law enforcement, medical diagnosis, and data cleaning.It can reveal suspicious behavior, rare events, and erroneous or noisy values.
  • Outliers vs. Graph Anomalies: Graph anomaly detection is needed because inter-dependent objects cannot always be treated as independent points in a multidimensional space.A reviewer’s fraudulence, for example, depends on linked ratings, products, and other reviewers’ trustworthiness.
  • Why Graphs?: Graphs represent long-range correlations through links and can incorporate node and edge attributes and types.These properties support relational analysis across biological, communication, retail, social, and other networks.
  • Challenges: Anomaly detection has application-specific definitions and names because the general concept of an anomaly is vague and open-ended.Contexts may refer to outliers, anomalies, outbreaks, events, changes, fraud, or noise.
  • Challenges: Graph data introduce scale, velocity, variety, and complexity challenges, including billion-scale and streaming graphs with typed nodes, edges, and attributes.The search space for anomalous substructures is combinatorial and expands further when graph attributes are included.
  • Survey Contributions: The survey unifies unsupervised and (semi-)supervised graph methods, compares their properties and applications, and highlights anomaly attribution for root-cause analysis and sense-making.It considers effectiveness, scalability, robustness, and generality alongside post-detection exploration.

I. Anomaly detection in static graphs (Section 2)

The survey organizes graph-based anomaly detection around static and dynamic graph methods, qualitative explanation, and applications across diverse network domains.

  • Static graph methods cover anomalies in plain and attributed graphs, while dynamic graph methods address feature-, decomposition-, community-, and window-based events.
  • The survey includes graph anomaly description through interpretation-friendly detection, interactive querying, and sense-making.
  • Applications span telecom, auction, account, security, opinion, Web, social, computer, and financial networks.
  • The taxonomy distinguishes unsupervised techniques from (semi-) supervised relational-classification approaches for static and dynamic graph anomalies.

2 Anomaly Detection in Static Graphs

This section introduces static graph anomaly detection as the task of identifying anomalous network entities from the complete graph structure.

  • Static graph anomaly detection identifies anomalous nodes, edges, or subgraphs using the entire graph structure.
  • The section surveys methods for static graphs after briefly reviewing outlier detection techniques for conventional data points.

Overview: Outliers in Clouds of Data Points

The section reviews conventional outlier detection as background for graph anomaly methods, including scoring, ranking, and multiple feature-space paradigms.

  • Graph anomaly systems can apply conventional outlier methods after extracting graph features.
  • Outlier detection methods may classify points as binary outliers or assign outlierness scores for ranking.
  • Multi-dimensional outlier detection includes density-, distance-, depth-, distribution-, and clustering-based techniques.
  • Additional methods handle categorical or mixed features and include one-class classification approaches.
  • The section directs readers to comprehensive surveys and a book for further discussion of outlier detection methods.

Anomalies in Static Graph Data

Static graph anomaly detection is studied for plain graphs and attributed graphs, with anomalies defined relative to the graph setting.

  • The survey distinguishes plain graphs containing nodes and edges from attributed graphs whose nodes or edges have associated features.
  • The section introduces a general definition of anomaly detection for static graphs while noting that specific anomaly definitions may vary.

Definition 3 (Static-Graph Anomaly Detection Problem)

Static-graph anomaly detection seeks nodes, edges, or substructures that are few, different, or significantly deviate from observed graph patterns.

  • The task identifies anomalous nodes, edges, or substructures in a snapshot of a plain or attributed graph.

2.1 Anomalies in static plain graphs

Static plain-graph methods use structure alone to detect anomalies through structural patterns, communities, graph-centric features, or proximity. Techniques such as ODDBALL, recursive features, random walks, and residual factorization support detection, interpretation, and ranking.

  • Structure-based methods: Plain-graph methods exploit structure alone, using structure-based or community-based patterns to detect anomalies.
  • Feature-based approaches: Feature-based approaches transform graph anomaly detection into outlier detection over graph-centric features from nodes, dyads, triads, egonets, communities, or global structure.
  • Feature-based approaches: ODDBALL extracts egonet features and identifies anomalous egonets whose feature relationships depart from patterns followed by most egonets.An egonet is the induced one-step neighborhood around a node, including the node, its direct neighbors, and their internal connections.
  • Combining multiple anomaly scores into final scores or rankings is addressed by outlier-ensemble methods.
  • Feature-based approaches: Paired egonet features support two-dimensional visualization and interpretability by linking anomaly types to deviations from particular patterns or laws.Low-dimensional feature spaces help users inspect patterns and identify what type of anomaly a node represents.
  • Feature-based approaches: Recursive features aggregate existing node or neighborhood features across neighbors, extending local and egonet information toward regional behavior.Aggregates can include the mean, minimum, or maximum of existing feature values among a node’s neighbors.
  • Proximity-based approaches: Proximity-based approaches measure graph closeness, including random-walk measures such as PageRank and Personalized PageRank and structural-context similarity such as SimRank.These methods use graph proximity to capture autocorrelation, treating close-by objects as likely to share a class.
  • Community-based methods: NRMF detects community-based node and edge anomalies by enforcing non-negativity on matrix-factorization residuals, revealing strange connections and structures.Reported examples include port-scanning-like or DDoS-like activity, bridging connections, and bipartite-core structures.

2.2 Anomalies in static attributed graphs

Static attributed-graph methods jointly use graph structure and attribute coherence, detecting rare attributed substructures or nodes whose attributes deviate within communities. They include pattern-based, community-based, and relational approaches, with interpretability and generality balanced against false positives, thresholds, and inference limitations.

  • Attributed-graph methods exploit both graph structure and attribute coherence through structure-based and community-based approaches.
  • Structure-based methods: Structure-based methods seek rare substructures by identifying deviations from frequent patterns in connectivity and attributes.
  • Structure-based methods: MDL-based scoring ranks unusual substructures and penalizes subgraphs containing few common substructures.
  • Structure-based methods: Numerical and categorical attributes require care because treating every numerical value as distinct loses ordering and closeness information.
  • Structure-based methods: Pattern-based techniques are interpretable, support post-analysis and root-cause investigation, and apply across attributed graph scenarios.
  • Structure-based methods: Their generality can produce high false-positive rates, while user-specified alteration or frequency thresholds complicate false-positive and false-negative trade-offs.
  • Community-based methods: Community outliers are nodes whose attributes deviate significantly from other members of their communities, with detection integrated into clustering or performed afterward.
  • Community-based methods: CODA jointly infers communities and community outliers using an alternating unsupervised probabilistic procedure.Its quality depends on initialization, and convergence is not guaranteed.

3 Anomaly Detection in Dynamic Graphs

Dynamic-graph anomaly detection builds on event and change detection methods for data series, including statistical, predictive, drift, chart-based, categorical-change, and MDL-based approaches.

  • Related dynamic-data methods include statistical quality control, autoregressive moving average prediction, drift detection, chart-based monitoring, categorical change detection, and StreamKrimp.

3.2 Event detection in time series of graph data

This section surveys anomaly detection algorithms for dynamic graphs, treating them as sequences of static graphs and focusing on graph and community evolution.

  • Dynamic graphs are modeled as sequences of static or attributed graphs whose evolution can reveal anomalies.The section places dynamic-graph anomaly detection within the broader study of evolving graphs and communities.

Definition 4 (Dynamic-Graph Anomaly Detection Problem)

Dynamic-graph anomaly detection identifies unusual timestamps and the graph components contributing most to those events. Methods summarize snapshots or node behavior, compare temporal patterns, and flag deviations using thresholds, residuals, Bayesian scores, or structural partitions.

  • The problem is to find timestamps of changes or events and the top-k nodes, edges, or graph parts contributing most to them.
  • Feature-based events: Feature-based methods summarize each graph, compare snapshots with distance or similarity functions, and flag sufficiently dissimilar instances.Common summaries include degree distributions, diameters, eigenvalues, and other graph features.
  • Decomposition-based events: Decomposition-based approaches use matrix decompositions such as SVD, CUR, CMD, or Colibri to represent graph structure and compare changes.Example-based approximations can use sampled rows and columns, while spectral methods compare eigenvalues.
  • Feature-based events: Temporal feature distances can be modeled with ARMA, with instances whose residuals exceed a threshold treated as anomalous.For one IP-traffic dataset, MCS edge, MCS vertex, edit, median, and entropy metrics detected introduced anomalies.
  • Feature-based events: Node-behavior methods extract egonet features over time and detect anomalous windows when current behavior has low similarity to its historical behavior.Features include weighted and unweighted degrees, neighbor counts, and triangle counts.
  • Community- or clustering-based events: Community-based methods can partition streaming graphs using MDL or identify anomalous regions by clustering edges and nodes with anomalous Bayesian scores.GRAPHSCOPE monitors evolving node partitions, whereas the Bayesian approach first scores edges and then clusters the anomalous subgraph.

3.3 Discussion

The discussion compares graph-similarity approaches and emphasizes that algorithm choice depends on data, correspondence assumptions, computational requirements, and the desired anomaly output.

  • Graph anomaly detection commonly relies on graph, subgraph, community, or cluster similarity at some stage.
  • Exact graph-isomorphism methods can be exponential and therefore are not readily applicable to continuously increasing graph data.
  • Graph kernels compute similarity between graphs but cannot attribute a change to the nodes contributing most to it.
  • Algorithm selection depends on application, graph attributes, node correspondence, time and parameter requirements, and whether the target is a graph, subgraph, or node anomaly.
  • Table 4 compares dynamic-graph methods by input type, linearity, parameter requirements, output format, node correspondence, attribution, and visualization.

Concluding Remarks: Static & Dynamic Graph Anomaly Detection

The survey reviews evaluation strategies for graph anomaly detection and identifies open problems, especially evaluation validity and methods for dynamic attributed graphs.

  • Evaluation: Evaluation is difficult because ground-truth anomaly labels are often unavailable.The survey therefore reviews internal, qualitative, synthetic, injected, and external-source validation approaches.
  • Evaluation: Internal evaluation quantifies score extremity, but scores depend on the specific method and may not directly match the external purpose of detection.
  • Evaluation: External-source validation detects anomalies from one information source and checks them against other consistent sources.For opinion spam, graph structure can identify reviewers and temporal behavior can provide additional validation.
  • Open problems: The survey found few methods for anomalies in dynamically changing attributed graphs and identifies this setting as an open research problem.It also calls for definitions and real-world applications for abnormalities in this setting.
  • Summary: The survey presents a unified categorization spanning static and dynamic, plain and attributed graph-based techniques.

4 Graph-based Anomaly Description: Interpretation and Sense-making

Graph anomaly description extends detection by making individual anomalies interpretable and by exposing relationships among detected anomalies. The survey presents matrix- and feature-based interpretation methods alongside interactive graph querying for concise, root-cause-oriented sense-making.

  • Overview: Graph anomaly attribution addresses both interpreting individual detections and characterizing associations among detected anomalies.The survey distinguishes interpretation-friendly detection from interactive querying and sense-making.
  • Interpretation-friendly Graph Anomaly Detection: Matrix-based methods factorize an adjacency matrix as A = XY′ + R, with low-rank factors capturing normality and the residual capturing anomalous structure.The example uses a bipartite author-conference graph represented by adjacency matrix A.
  • Interpretation-friendly Graph Anomaly Detection: SVD/PCA minimizes reconstruction error but may hinder interpretation because its singular vectors are linear combinations of the original rows and columns.Example-based low-rank approximations instead use actual rows and columns of the adjacency matrix.
  • Interpretation-friendly Graph Anomaly Detection: Nonnegative matrix factorization improves interpretability by restricting factorized matrices to nonnegative entries.The survey identifies non-negativity as an interpretation-friendly property for graph anomaly analysis.
  • Interpretation-friendly Graph Anomaly Detection: Feature-based visualization helps users identify which low-dimensional graph features make abnormal nodes differ from normal nodes.Pairwise egonet features support two-dimensional visualization and improve interpretability of anomaly types.
  • Finding the root cause of anomalies: Interactive Graph Querying: Interactive graph querying finds concise contexts linking detected anomalies, while DOT2DOT groups query nodes and finds within-group connections without requiring a connectivity parameter.Connection subgraphs use paths or subgraphs to characterize relationships, and discovered paths can explain links among suspects.

5 Graph-based Anomaly Detection in Real-world Applications

Graph-based detection methods address fraud, spam, accounting, security, auction, telecommunications, and opinion-network anomalies by modeling relationships among entities and interactions. Applications use graph structure, relational features, propagation, and community behavior to identify suspicious accounts, activities, or communications.

  • Fraud detection: Graph-based fraud detection exploits relationships among participants because fraud can spread through acquaintances or arise from collaboration between closely related parties.These relational patterns motivate graph methods beyond individual behavioral features.
  • Telecommunications fraud: Telecommunications methods build dynamic communities of interest around phone accounts to link fraudulent accounts and identify new accounts resembling previously flagged fraud networks.The communities incorporate call quantities and durations and are updated daily.
  • Auction fraud: Auction-fraud methods address the weakness of easily faked individual features by analyzing interaction patterns in large eBay graphs.Fraudsters’ limited view of the overall auction graph makes it harder to fit altered behavior into the network’s interaction patterns.
  • Accounting fraud: Accounting-fraud detection uses relational models that propagate prior risk beliefs through networks, improving true-positive detection over rule-based methods at the same small false-positive rate.The propagated beliefs can corroborate or discard noisy domain-knowledge flags.
  • Opinion spam: Opinion-spam detection jointly propagates reviewer trustiness, store reliability, and review honesty through their relationships until a convergence criterion is reached.Each score is defined as a function of the other connected scores.
  • Network intrusion: Network-intrusion methods combine graph structure with node, edge, and communication behavior, including community boundaries, to detect attacks in large dynamic communication networks.Community-based detection exceeded 90% accuracy but had an approximately 50% false-alarm rate on malicious-attack ground-truth data.

6 Conclusions and Open Challenges

The survey concludes that graph representations capture relational structure useful for anomaly detection and attribution, while emphasizing that substantial theoretical, practical, and systems challenges remain.

  • Conclusions: The survey organizes graph-based work into detection for static graphs, event detection for dynamic graphs, fraud detection, and anomaly attribution.Attribution includes analysis, visualization, monitoring, exploration, and sense-making tools.
  • Conclusions: Graphs are effective for anomalies involving interdependence, long-range correlations, relational fraud, and adversarial behavior.The authors present graph methods as complementary to other detection techniques rather than universally superior.
  • Theoretical research challenges: Dynamic attributed graphs, update histories, and appropriate time-window selection remain underdeveloped research areas.Existing work rarely exploits the history of graph updates, and few studies address dynamic graphs with attributes.
  • Systems and practical challenges: Future systems should address adversarial robustness, measurement and monitoring costs, and scalable real-time discontinuity detection.The survey specifically calls for linear or sub-linear approaches for streaming graphs.
  • Practical research challenges: Evaluation lacks a standard because graph anomaly ground truth is often unavailable and may require anomaly injection or qualitative analysis.Practitioners also face unresolved issues in graph construction and combining multiple networks.
  • Practical research challenges: Anomaly attribution must be balanced against novelty detection because explanations based on known evidence can conflict with discovering previously unrecognized patterns.The survey also identifies latent-edge augmentation as a possible direction when explicit network representations are incomplete.
Loading 1404.4679v2…