Tester-Guided Graph Learning with End-to-End Detection Certificates for Triangle-Based Anomalies

We investigate anomaly detection in complex networks through a property-testing-guided graph neural model (PT-GNN) that provides an end-to-end miss-probability certificate (δ+α). The method combines (i) a wedge-sampling tester that estimates triangle-closure frequency and derives a concentration bound (δ) via Bernstein’s inequality, with (ii) a lightweight classifier over structural features whose validation error contributes (α). The overall certificate is given by the sum (δ+α), quantifying the probability of missed anomalies under bounded sampling. On synthetic communication graphs with n = 1000, edge probability p = 0.01, and anomalous subgraph size k = 120, PT-GNN achieves perfect detection performance (AUC = 1.0, F1 = 1.0) across all tested regimes. Moreover, the miss-probability certificate tightens systematically as the tester budget m increases (e.g., for ε = 0.06, enlarging m from 2000 to 8000 reduces (δ+α) from ≈0.87 to ≈0.49). These results demonstrate that PT-GNN effectively couples graph learning with property testing, offering both strong empirical detection and formally verifiable guarantees in anomaly detection tasks.