Graph Anomaly Detection with TGraphX
Anomaly detection on graphs — identifying nodes, edges, or subgraphs that deviate from normal behavior — underpins a wide range of high-stakes applications. Fraud detection in financial transaction networks, intrusion detection in network traffic graphs, and identification of bot accounts in social networks all require reliable methods for distinguishing normal from abnormal graph entities.
TGraphX implements graph anomaly detection utilities in tgraphx.mining.anomaly. The module supports node-level and edge-level anomaly detection using reconstruction-based and structural isolation approaches. This article explains the main approaches, their assumptions, and how to use the TGraphX anomaly detection tools.
Why Graph Anomaly Detection Is Harder Than Tabular Anomaly Detection
Standard anomaly detection methods (Isolation Forest, Local Outlier Factor, One-Class SVM) operate on i.i.d. feature vectors. Graph anomaly detection is harder for several reasons:
Structural correlations. Nodes are not independent — they are connected by edges. An anomalous node may be identifiable only through its neighborhood pattern, not its features alone.
Imbalanced and unlabeled data. In most real deployments, anomalies represent 0.1–1% of the data, and ground-truth anomaly labels are expensive to obtain. Many practical systems operate in a semi-supervised or fully unsupervised regime.
Graph heterogeneity. Different node types and edge types have different normal behavior distributions. Aggregating them naively produces poor anomaly scores.
Temporal dynamics. Anomalous behavior often emerges over time — a sudden change in connection patterns rather than an absolute structural deviation. Static graph anomaly detection misses this.
Two Main Approaches in TGraphX
Reconstruction-Based Detection
The reconstruction-based approach trains a GNN autoencoder on the normal graph and flags nodes (or edges) where the reconstruction error is high. The intuition is that a model trained to compress and reconstruct normal patterns will fail on anomalous patterns, producing higher error.
This is structurally similar to VGAE (see VGAE for link prediction), with the key difference that the objective is anomaly scoring rather than link prediction.
Structural Isolation
Isolation-based methods identify anomalies as nodes that are structurally isolated from the main graph — low-degree nodes, nodes with unusual local clustering coefficients, or nodes in unusually small connected components. These are fast and require no training but rely purely on structural features.
TGraphX's anomaly module combines both approaches through a scoring interface that returns per-node (or per-edge) anomaly scores between 0 and 1.
Prerequisites
This article assumes familiarity with:
- Basic GNN concepts (see GIN architecture guide for background)
- Autoencoder and reconstruction loss concepts
- Standard classification evaluation (precision, recall, AUROC)
Install TGraphX:
pip install tgraphx
Node-Level Anomaly Detection
The most common graph anomaly detection task is node-level: assign each node an anomaly score based on its features and structural position.
import torch
from tgraphx.mining.anomaly import NodeAnomalyDetector
# Graph with node features
num_nodes = 1000
x = torch.randn(num_nodes, 64)
edge_index = torch.randint(0, num_nodes, (2, 5000), dtype=torch.long)
# Inject a few synthetic anomalies (extreme features)
anomaly_idx = torch.tensor([10, 42, 137, 256, 589])
x[anomaly_idx] = torch.randn(5, 64) * 10.0 # much larger scale than normal
# Instantiate and fit anomaly detector
detector = NodeAnomalyDetector(
in_channels=64,
hidden_channels=128,
latent_channels=32,
num_layers=2,
method="reconstruction", # "reconstruction" or "structural"
epochs=100,
lr=1e-3,
)
detector.fit(x, edge_index)
# Score nodes — higher = more anomalous
scores = detector.score(x, edge_index)
print(scores.shape) # [1000] — one score per node
print(scores[anomaly_idx]) # should be higher than average
The method="structural" variant skips GNN training and scores nodes based on degree, local clustering coefficient, and component size:
structural_detector = NodeAnomalyDetector(
in_channels=64,
hidden_channels=128,
latent_channels=32,
method="structural",
)
structural_detector.fit(x, edge_index)
structural_scores = structural_detector.score(x, edge_index)
Structural scores are fast to compute and can serve as a first-pass filter before applying the more expensive reconstruction-based approach.
Edge-Level Anomaly Detection
For applications like fraud detection in transaction networks, the anomaly of interest is often an unusual edge (transaction) rather than an unusual node (account).
from tgraphx.mining.anomaly import EdgeAnomalyDetector
# Edge features
num_edges = 5000
edge_features = torch.randn(num_edges, 16)
# Inject anomalous edges
anomalous_edge_idx = torch.randint(0, num_edges, (50,))
edge_features[anomalous_edge_idx] *= 15.0
detector = EdgeAnomalyDetector(
node_in_channels=64,
edge_in_channels=16,
hidden_channels=128,
latent_channels=32,
epochs=100,
lr=1e-3,
)
detector.fit(x, edge_index, edge_features)
edge_scores = detector.score(x, edge_index, edge_features)
print(edge_scores.shape) # [5000] — one score per edge
The edge detector jointly encodes node representations via a GNN and edge features via a separate encoder, then scores each edge based on its reconstruction error in the joint latent space.
A Fraud Detection Use Case
Financial transaction networks are a canonical application. Each node is a user account; each edge is a transaction with features (amount, time of day, merchant category). Fraud manifests as:
- Abnormal transaction patterns: A user account suddenly making large transactions to many new recipients.
- Structural isolation: A fraudulent account with few connections except to known fraud accounts.
- Feature drift: Transaction amounts far outside the historical range for that account.
import torch
import torch.nn.functional as F
from tgraphx.mining.anomaly import NodeAnomalyDetector
from tgraphx.doctor import validate_graph
# Validate graph structure before training
validate_graph(x, edge_index)
# Node features: account-level statistics
# [num_accounts, features] — e.g., avg_transaction_amount, num_transactions, account_age, etc.
num_accounts = 50000
account_features = torch.randn(num_accounts, 32)
# Edge index from transaction graph
# (in practice, loaded from your transaction database)
transaction_edge_index = torch.randint(0, num_accounts, (2, 200000), dtype=torch.long)
detector = NodeAnomalyDetector(
in_channels=32,
hidden_channels=64,
latent_channels=16,
method="reconstruction",
epochs=50,
lr=5e-4,
)
# Train only on accounts not known to be fraudulent
# (semi-supervised: train on "normal" nodes only)
normal_mask = torch.ones(num_accounts, dtype=torch.bool)
# known_fraud_mask = ... # if available, exclude known fraud from training
detector.fit(account_features, transaction_edge_index)
fraud_scores = detector.score(account_features, transaction_edge_index)
# Threshold at top 1% of scores
threshold = torch.quantile(fraud_scores, 0.99)
flagged = (fraud_scores > threshold).sum()
print(f"Flagged {flagged.item()} accounts as potentially fraudulent (top 1%)")
Evaluating Anomaly Detectors
When ground-truth anomaly labels are available, use AUROC and average precision:
from sklearn.metrics import roc_auc_score, average_precision_score
import numpy as np
# Suppose we have ground truth labels for some nodes
# 1 = anomaly, 0 = normal
ground_truth = torch.zeros(num_nodes)
ground_truth[anomaly_idx] = 1.0
scores_np = scores.detach().cpu().numpy()
labels_np = ground_truth.numpy()
auroc = roc_auc_score(labels_np, scores_np)
ap = average_precision_score(labels_np, scores_np)
print(f"AUROC: {auroc:.4f} | Average Precision: {ap:.4f}")
For highly imbalanced datasets (0.1% anomaly rate), AUROC can be misleadingly high because random guessing already achieves 0.5. Average precision better reflects performance at the relevant operating point where precision matters.
Using TGraphX Doctor for Pre-Flight Validation
Before running anomaly detection, use TGraphX's doctor module to catch common graph data issues that can produce misleading anomaly scores:
from tgraphx.doctor import validate_graph, check_isolated_nodes
# Check for self-loops, duplicate edges, and disconnected components
validate_graph(x, edge_index, check_self_loops=True, check_duplicates=True)
# Report nodes with zero degree (potential trivial anomalies)
isolated = check_isolated_nodes(edge_index, num_nodes)
print(f"Isolated nodes: {isolated.sum().item()}")
Isolated nodes (degree zero) will always score highly under structural methods because they are structurally abnormal. If isolation is an artifact of graph construction rather than genuine anomaly, you should either remove those nodes or use feature-only reconstruction scoring. The shape-aware validation guide covers TGraphX validation tools in more depth.
Limitations and Honest Notes
Reconstruction-based methods assume anomalies are rare during training. If your training graph contains many anomalies, the model learns to reconstruct anomalous patterns normally, and anomaly scores become unreliable. In fraud detection, ensure training data is cleaned of known fraud accounts.
No method is universally best. Structural methods fail on camouflage attacks (fraudsters who mimic normal structural patterns). Reconstruction-based methods fail on in-distribution anomalies (anomalies with normal-looking features).
Anomaly score thresholds are application-specific. The "right" threshold depends on your tolerance for false positives vs. false negatives. There is no universally optimal threshold.
Temporal anomalies require temporal methods. If anomalous behavior only emerges over time (e.g., a gradual increase in transaction volume), static graph anomaly detection on a single snapshot will not detect it. Use temporal GNNs (see temporal GNN guide) combined with temporal anomaly scoring.
High AUROC does not guarantee operational utility. An AUROC of 0.95 on a research benchmark may not translate to useful fraud flagging rates at the operating point your business requires.
Frequently Asked Questions
Can I combine reconstruction and structural scores?
Yes. A simple linear combination — score = α * reconstruction_score + (1 - α) * structural_score — often outperforms either alone. Tune α on a labeled validation set.
How do I handle new nodes that were not present during training?
Inductive inference is supported for reconstruction-based detectors: pass the new node's features and its available edges to score(). The GNN encoder produces embeddings for unseen nodes via neighborhood aggregation. If the node is fully isolated (no edges), scoring relies on feature reconstruction only.
Does graph anomaly detection work on directed graphs?
Yes. The edge_index can represent directed edges. Structural scores (degree, clustering) compute in-degree and out-degree separately, which can be informative for directed anomalies.
Where is the TGraphX source?
GitHub, package: PyPI, technical preprint: arXiv:2504.03953.
Combining Anomaly Detection with GNN Embeddings
A powerful pattern for anomaly detection uses a GNN encoder to produce rich node embeddings, then applies a classical anomaly detection algorithm (Isolation Forest, One-Class SVM) on top of those embeddings:
import torch
import torch.nn.functional as F
from sklearn.ensemble import IsolationForest
from tgraphx.layers.sage import TensorGraphSAGELayer
import torch.nn as nn
# Train a GNN encoder on the normal training graph
class GNNEncoder(nn.Module):
def __init__(self, in_dim, hidden_dim, out_dim):
super().__init__()
self.sage1 = TensorGraphSAGELayer(in_dim, hidden_dim)
self.sage2 = TensorGraphSAGELayer(hidden_dim, out_dim)
def forward(self, x, edge_index):
x = F.relu(self.sage1(x, edge_index))
return self.sage2(x, edge_index)
num_nodes = 1000
x = torch.randn(num_nodes, 64)
edge_index = torch.randint(0, num_nodes, (2, 5000), dtype=torch.long)
encoder = GNNEncoder(64, 128, 32)
# Train encoder with a simple reconstruction objective
optimizer = torch.optim.Adam(encoder.parameters(), lr=1e-3)
for epoch in range(30):
encoder.train()
optimizer.zero_grad()
z = encoder(x, edge_index)
# Reconstruction: predict features from embeddings
recon = z @ z.mean(0, keepdim=True).t()
loss = F.mse_loss(recon.squeeze(), x.norm(dim=1))
loss.backward()
optimizer.step()
# Extract embeddings
encoder.eval()
with torch.no_grad():
embeddings = encoder(x, edge_index).cpu().numpy()
# Apply Isolation Forest on top of GNN embeddings
iso_forest = IsolationForest(contamination=0.05, random_state=42)
iso_forest.fit(embeddings)
anomaly_scores = -iso_forest.score_samples(embeddings) # higher = more anomalous
# Flag top 5% of nodes
threshold = torch.tensor(anomaly_scores).quantile(0.95)
flagged_nodes = (torch.tensor(anomaly_scores) > threshold).nonzero().squeeze()
print(f"Flagged {flagged_nodes.numel()} nodes as anomalous")
This hybrid approach combines the structural awareness of GNN embeddings with the calibrated anomaly scoring of established classical methods. It is particularly useful when labeled anomalies are not available for training the GNN detector directly.
Anomaly Detection at the Graph Level
Beyond node-level and edge-level anomalies, some tasks require detecting whether an entire graph is anomalous — for example, identifying an abnormal network traffic snapshot or a pathological molecule. This is graph-level anomaly detection.
from tgraphx import GraphBatch
from tgraphx.layers.pooling import GlobalMeanPool
from tgraphx.layers.sage import TensorGraphSAGELayer
import torch.nn as nn
import torch.nn.functional as F
class GraphAnomalyEncoder(nn.Module):
def __init__(self, in_dim, hidden_dim, graph_dim):
super().__init__()
self.sage1 = TensorGraphSAGELayer(in_dim, hidden_dim)
self.sage2 = TensorGraphSAGELayer(hidden_dim, graph_dim)
self.pool = GlobalMeanPool()
def forward(self, x, edge_index, batch):
x = F.relu(self.sage1(x, edge_index))
x = self.sage2(x, edge_index)
return self.pool(x, batch) # [num_graphs, graph_dim]
# After encoding a collection of graphs to graph-level vectors,
# apply Isolation Forest or One-Class SVM at the graph level
Graph-level anomaly detection follows the same pattern as node-level: encode each graph to a fixed-size vector, then apply classical anomaly scoring. The key challenge is that graph-level representations must be invariant to node permutation, which the pooling layer ensures.
Connecting to Reproducibility Best Practices
Anomaly detection evaluation is particularly sensitive to the choice of anomaly injection strategy, random seeds, and evaluation protocol. Before reporting AUROC or AP numbers:
- Fix the anomaly injection seed (to reproduce the same synthetic anomalies across runs)
- Run at least five seeds and report mean ± std
- Document whether anomalies were injected in training, validation, or only test data
- Report the contamination rate (fraction of anomalies) in your experimental setup
Use TGraphX's reproducibility context for deterministic anomaly injection:
from tgraphx.reproducibility import set_reproducible
with set_reproducible(seed=42):
# Inject anomalies consistently
anomaly_idx = torch.randperm(num_nodes)[:int(0.05 * num_nodes)]
x_with_anomalies = x.clone()
x_with_anomalies[anomaly_idx] *= 10.0
# ... train and evaluate detector ...
For a full treatment of reproducibility in GNN experiments, see the GNN research reproducibility guide.