Graph Anomaly Detection

Identifies deviations in the topological structure of a graph rather than node attributes alone. This method flags subgraphs with unusual connectivity patterns, such as dense clusters in sparse networks or isolated nodes in highly connected regions.

• Egonet analysis: Compares a node's local neighborhood density against global averages
• Clique detection: Finds unexpectedly large or small fully-connected subgraphs
• Spectral methods: Uses eigenvalues of the Laplacian matrix to detect structural breaks

Example: Detecting a ring of colluding accounts in a financial transaction network that form an abnormally dense subgraph.

Flags nodes whose attribute vectors are statistically inconsistent with their neighbors, even if their structural position appears normal. This captures entities that look right structurally but behave wrong contextually.

• Residual analysis: Measures the difference between a node's actual features and those predicted by aggregating neighbor features via a GNN
• Contrastive scoring: Compares a node against its local context distribution using Mahalanobis distance
• Autoencoder reconstruction error: Uses graph autoencoders where high reconstruction loss signals contextual deviation

Example: A supplier node with normal connectivity but transaction amounts 5 standard deviations above its peer group.

Leverages community structure to identify nodes that bridge or lie between distinct clusters in unexpected ways. Anomalous nodes often serve as rare connectors between otherwise disconnected communities.

• Betweenness centrality outliers: Nodes with disproportionately high shortest-path traffic
• Community affiliation divergence: Nodes whose community membership probabilities are uniformly distributed rather than concentrated
• Bridge detection: Edges whose removal would disconnect the graph into isolated components

Example: A single logistics hub that inexplicably connects two entirely separate regional supply networks with no documented business relationship.

Monitors evolving graph snapshots over time to detect abrupt changes in edge formation rates, node attribute drift, or community restructuring. This is critical for real-time monitoring systems.

• Change point detection: Identifies time steps where the graph's statistical properties shift significantly
• Edge burst detection: Flags sudden spikes in edge creation between specific node pairs
• Temporal pattern deviation: Compares current graph state against learned seasonal or cyclical patterns using ST-GNNs

Example: A sudden surge in transaction edges between a supplier and buyer at 3 AM, far outside historical temporal norms.

Addresses the vulnerability of GNN-based anomaly detectors to adversarial attacks where malicious actors modify graph structure or features to evade detection. Robust detection requires adversarial training and certified defenses.

• Structural perturbation defense: Training on graphs with randomly dropped or added edges to improve generalization
• Certified robustness bounds: Mathematical guarantees that a prediction won't change within a defined perturbation radius
• Anomaly score smoothing: Aggregating scores across multiple perturbed versions of the input graph

Example: A fraud ring that strategically adds legitimate-looking edges to dilute their anomalous connectivity signature.

Provides human-interpretable explanations for why a specific node or subgraph was flagged as anomalous. This is essential for analyst trust and downstream investigation workflows.

• GNNExplainer adaptation: Identifies the minimal subgraph and feature subset responsible for the anomaly score
• Counterfactual reasoning: Shows what minimal changes would make the node appear normal
• Contrastive explanation: Highlights how the anomalous node differs from its k-nearest normal neighbors

Example: Explaining a flagged supplier by highlighting that two specific upstream connections and an unusual payment frequency drove the anomaly score.

Identifies deviations in the topological patterns of a graph, such as unexpected dense connections or isolated components.

• Detects fraud rings forming dense subgraphs in transaction networks.
• Identifies missing links in a Bill of Materials (BOM) graph indicating a supply disruption.
• Flags nodes with anomalous degree distributions or centrality metrics.
• Uses algorithms like OddBall and DOMINANT to score structural outliers.

Flags nodes whose feature vectors deviate significantly from their local neighborhood, even if their structure is normal.

• A supplier with a sudden drop in on-time delivery rate compared to peers.
• A warehouse showing abnormal temperature readings in a cold chain graph.
• Uses Graph Convolutional Networks (GCNs) to reconstruct features; high reconstruction error signals an anomaly.
• Often combined with structural analysis for holistic outlier scoring.

Leverages graph clustering to find nodes that do not fit well within any community or belong to a suspiciously small cluster.

• Applies algorithms like Louvain or Leiden to partition the supply chain graph.
• A logistics node that constantly switches community membership over time is a temporal anomaly.
• Micro-communities in a supplier network can indicate collusive bidding behavior.
• Contrasts an entity's behavior against the normative profile of its assigned group.

A self-supervised approach that learns to distinguish normal graph patterns from synthetically generated anomalies without labeled data.

• Generates negative samples via edge perturbation or node feature shuffling.
• Trains a Graph Neural Network (GNN) to maximize agreement between original and augmented normal views.
• Anomalies receive low agreement scores because they violate the learned invariances.
• Highly effective in supply chains where labeled fraud data is scarce or non-existent.

Monitors dynamic graphs to detect edges or nodes whose behavior over time breaks established evolutionary patterns.

• Uses Spatio-Temporal GNNs (ST-GNNs) to model how the supply chain graph evolves.
• A sudden surge in transaction volume between two previously dormant nodes.
• Detects drift in a supplier's reliability score that is anomalous relative to the network trend.
• Critical for identifying emerging disruptions before they cascade through the network.

Trains an encoder-decoder architecture to reconstruct the adjacency matrix and node features; high reconstruction error pinpoints anomalies.

• The encoder compresses the graph into latent embeddings.
• The decoder predicts the probability of edge existence.
• Anomalous edges (e.g., fraudulent transactions) are harder to reconstruct and receive low probability scores.
• Variants like GAE and VGAE provide probabilistic anomaly rankings for audit prioritization.