What Is Graph Anomaly Detection (www.puppygraph.com)

This article is a compact primer on graph anomaly detection: the task of finding unusual nodes, edges, subgraphs or whole graphs by leveraging relational structure that tabular methods miss. It explains why graphs matter for anomaly hunting—relationships, neighborhood patterns and connectivity (sudden hub formation, star-like structures, dense cliques or bridging nodes) carry semantic signals useful in fraud, cybersecurity, social-network analysis and molecular screening. The piece walks through a practical pipeline (preprocessing, modeling, scoring, thresholding and explanation), includes reproducible code sketches, and compares three representative approaches: interpretable rule-based checks, statistical egonet methods (OddBall), and learning-based Graph Neural Network models (e.g., graph autoencoders using reconstruction error as an anomaly score). Key technical takeaways: rule-based systems compute node metrics (degree d(v), weighted degree W(v), egonet edges E_ego, ego-density, clustering C(v)=2E_ego/(d(d−1))) and aggregate rule violations S(v)=Σ w_i s_i(v) for explainable alerts—useful in regulated domains. OddBall fits power-law relationships (log y = a + b log x) on egonet feature pairs (e.g., (d, E_ego)), scores anomalies by residual r = |log y − (a + b log x)| and combines residuals to rank nodes; it’s fast, local and interpretable but needs robust fitting, binning or sampling for very-high-degree nodes (worst-case cost ~Σ d(v)^2). GNN approaches learn structural+attribute embeddings and use reconstruction/prediction error for flexible detection at the cost of training and tuning. Practical recommendations: use robust regression, degree-binning, sampling for hubs, and always include postmortem egonet inspection for explainability and action.