Planted Anomalies in Networks

Objective

In today’s hyper-connected world, detecting malicious actors embedded in complex systems is a critical challenge with direct implications for cybersecurity, information integrity, and the safe deployment of AI technologies. This project will examine the problem from a mathematical perspective, focusing on random graphs with planted anomalies: small sets of nodes whose connectivity differs from that of the rest of the network. Many existing methods employ heuristics without formal guarantees of their performance, or they often overlook key aspects of real networks, such as inhomogeneity, spatial structure, or higher-order connections. The project will develop along four specific goals: (1) Build models of planted anomalies in networks that include realistic features; (2) Find the thresholds between recovery achievability and impossibility; (3) Design algorithms that guarantee planted anomalies recovery in polynomial time; (4) Test these methods on both synthetic data and real network datasets. My research will provide a clearer understanding of the limitations of anomaly detection and offer practical tools that others can utilize. All results will be shared, and the implementation will be collected in an open-source software. These outcomes are relevant for detecting cyber attacks, tracking disinformation, and protecting AI systems from hidden manipulation. The project supports European goals in cybersecurity, digital resilience, and trustworthy AI by developing reliable detection methods.