{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T07:11:10Z","timestamp":1760425870208,"version":"build-2065373602"},"reference-count":26,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T00:00:00Z","timestamp":1760227200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["BDCC"],"abstract":"<jats:p>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 (\u03b4+\u03b1). The method combines (i) a wedge-sampling tester that estimates triangle-closure frequency and derives a concentration bound (\u03b4) via Bernstein\u2019s inequality, with (ii) a lightweight classifier over structural features whose validation error contributes (\u03b1). The overall certificate is given by the sum (\u03b4+\u03b1), 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 \u03b5 = 0.06, enlarging m from 2000 to 8000 reduces (\u03b4+\u03b1) from \u22480.87 to \u22480.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.<\/jats:p>","DOI":"10.3390\/bdcc9100257","type":"journal-article","created":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T05:48:21Z","timestamp":1760420901000},"page":"257","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Tester-Guided Graph Learning with End-to-End Detection Certificates for Triangle-Based Anomalies"],"prefix":"10.3390","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8872-5721","authenticated-orcid":false,"given":"Manuel J. C. S.","family":"Reis","sequence":"first","affiliation":[{"name":"Engineering Department and Institute of Electronics and Informatics Engineering of Aveiro (IEETA), University of Tr\u00e1s-os-Montes e Alto Douro, Quinta de Prados, 5000-801 Vila Real, Portugal"}]}],"member":"1968","published-online":{"date-parts":[[2025,10,12]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"626","DOI":"10.1007\/s10618-014-0365-y","article-title":"Graph based anomaly detection and description: A survey","volume":"29","author":"Akoglu","year":"2015","journal-title":"Data Min. Knowl. Discov."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"12012","DOI":"10.1109\/TKDE.2021.3118815","article-title":"A Comprehensive Survey on Graph Anomaly Detection with Deep Learning","volume":"35","author":"Ma","year":"2023","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"153244","DOI":"10.1109\/ACCESS.2025.3603937","article-title":"Scalable Intrusion Detection in IoT Networks via Property Testing and Federated Edge AI","volume":"13","author":"Reis","year":"2025","journal-title":"IEEE Access"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Reis, M.J.C.S. (2025). Property-Based Testing for Cybersecurity: Towards Automated Validation of Security Protocols. Computers, 14.","DOI":"10.3390\/computers14050179"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1561\/0400000029","article-title":"Algorithmic and Analysis Techniques in Property Testing","volume":"5","author":"Ron","year":"2010","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Goldreich, O. (2010). Algorithmic Aspects of Property Testing in the Dense Graphs Model. Property Testing: Current Research and Surveys, Springer.","DOI":"10.1007\/978-3-642-16367-8"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Seshadhri, C., Pinar, A., and Kolda, T.G. (2013, January 2\u20134). Triadic Measures on Graphs: The Power of Wedge Sampling. Proceedings of the 2013 SIAM International Conference on Data Mining (SDM), Austin, TX, USA.","DOI":"10.1137\/1.9781611972832.2"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1002\/sam.11224","article-title":"Wedge Sampling for Computing Clustering Coefficients and Triangle Counts on Large Graphs","volume":"7","author":"Seshadhri","year":"2014","journal-title":"Stat. Anal. Data Mining ASA Data Sci. J."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Boucheron, S., Lugosi, G., and Massart, P. (2013). Concentration Inequalities: A Nonasymptotic Theory of Independence, Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780199535255.001.0001"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1263","DOI":"10.1016\/j.procs.2024.08.145","article-title":"A Brief Survey on Graph Anomaly Detection","volume":"242","author":"Song","year":"2024","journal-title":"Procedia Comput. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TKDE.2023.3282898","article-title":"A Survey of Graph-Based Deep Learning for Anomaly Detection in Distributed Systems","volume":"36","author":"Pazho","year":"2024","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1145\/3669906","article-title":"Anomaly Detection in Dynamic Graphs: A Comprehensive Survey","volume":"18","author":"Ekle","year":"2024","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"824","DOI":"10.1126\/science.298.5594.824","article-title":"Network Motifs: Simple Building Blocks of Complex Networks","volume":"298","author":"Milo","year":"2002","journal-title":"Science"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"ID\u00c9, T., and KASHIMA, H. (2004, January 22\u201325). Eigenspace-based anomaly detection in computer systems. Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD \u201804, New York, NY, USA.","DOI":"10.1145\/1014052.1014102"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Ai, X., Zhou, J., Zhu, Y., Li, G., Michalak, T.P., Luo, X., and Zhou, K. (2024, January 13\u201316). Graph Anomaly Detection at Group Level: A Topology Pattern Enhanced Unsupervised Approach. Proceedings of the 2024 IEEE 40th International Conference on Data Engineering (ICDE), Utrecht, The Netherlands.","DOI":"10.1109\/ICDE60146.2024.00098"},{"key":"ref_16","unstructured":"Kipf, T., and Welling, M. (2016). Variational Graph Auto-Encoders. arXiv."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Roy, A., Shu, J., Li, J., Yang, C., Elshocht, O., Smeets, J., and Li, P. (2024, January 4\u20138). GAD-NR: Graph Anomaly Detection via Neighborhood Reconstruction. Proceedings of the 17th ACM International Conference on Web Search and Data Mining, WSDM \u201824, New York, NY, USA.","DOI":"10.1145\/3616855.3635767"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Tian, S., Dong, J., Li, J., Zhao, W., Xu, X., Wang, B., Song, B., Meng, C., Zhang, T., and Chen, L. (2023, January 19\u201325). SAD: Semi-supervised anomaly detection on dynamic graphs. Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI \u201923, Macao.","DOI":"10.24963\/ijcai.2023\/256"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"106463","DOI":"10.1016\/j.neunet.2024.106463","article-title":"GRAM: An interpretable approach for graph anomaly detection using gradient attention maps","volume":"178","author":"Yang","year":"2024","journal-title":"Neural Netw."},{"key":"ref_20","unstructured":"Cohen, J., Rosenfeld, E., and Kolter, J.Z. (2019, January 10\u201315). Certified Adversarial Robustness via Randomized Smoothing. Proceedings of the 36th International Conference on Machine Learning (ICML), Long Beach, CA, USA."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Vovk, V., Gammerman, A., and Shafer, G. (2022). Algorithmic Learning in a Random World: Conformal Prediction and Its Applications, Springer. [2nd ed.].","DOI":"10.1007\/978-3-031-06649-8"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Zhou, A., Xu, X., Raghunathan, R., Lal, A., Guan, X., Yu, B., and Li, B. (2024, January 14\u201318). KnowGraph: Knowledge-Enabled Anomaly Detection via Logical Reasoning on Graph Data. Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, CCS \u201824, New York, NY, USA.","DOI":"10.1145\/3658644.3690354"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1080\/01621459.1962.10482149","article-title":"Probability Inequalities for the Sum of Independent Random Variables","volume":"57","author":"Bennett","year":"1962","journal-title":"J. Am. Stat. Assoc."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","article-title":"Probability Inequalities for Sums of Bounded Random Variables","volume":"58","author":"Hoeffding","year":"1963","journal-title":"J. Am. Stat. Assoc."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1141","DOI":"10.1214\/aoms\/1177706098","article-title":"Random Graphs","volume":"30","author":"Gilbert","year":"1959","journal-title":"Ann. Math. Stat."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Vershynin, R. (2018). High-Dimensional Probability: An Introduction with Applications in Data Science, Cambridge University Press.","DOI":"10.1017\/9781108231596"}],"container-title":["Big Data and Cognitive Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2504-2289\/9\/10\/257\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T06:33:28Z","timestamp":1760423608000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2504-2289\/9\/10\/257"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,12]]},"references-count":26,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2025,10]]}},"alternative-id":["bdcc9100257"],"URL":"https:\/\/doi.org\/10.3390\/bdcc9100257","relation":{},"ISSN":["2504-2289"],"issn-type":[{"value":"2504-2289","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,12]]}}}