DisCoMath Seminar: Fraud Detection for Random Walks

DisCoMath Seminar
Fraud Detection for Random Walks

Dr. Varsha Dani
Department of Computer Science
Rochester Institute of Technology

Abstract:
Traditional fraud detection is often based on finding statistical anomalies in data sets and transaction histories. A sophisticated fraudster, aware of the exact kinds of tests being deployed, might be difficult or impossible to catch. We are interested in paradigms for fraud detection that are provably robust against any adversary, no matter how sophisticated. In other words, the detection strategy should rely on signals in the data that are inherent in the goals the adversary is trying to achieve.
Specifically, we consider a fraud detection game centered on a random walk on a graph. We assume this random walk is implemented by having a player at each vertex, who can be honest or not. In particular, when the random walk reaches a vertex owned by an honest player, it proceeds to a uniformly random neighbor at the next timestep. However, when the random walk reaches a dishonest player, it instead proceeds to an arbitrary neighbor chosen by an omniscient Adversary.
The game is played between the Adversary and a Referee who sees the trajectory of the random walk. At any point during the random walk, if the Referee determines that a specific​ vertex is controlled by a dishonest player, the Referee accuses that player, and therefore wins the game. The Referee is allowed to make the occasional incorrect accusation, but must follow a policy that makes such mistakes very unlikely. The goal of the adversary is to delay the cover time, defined as the number of timesteps until all vertices of the graph have been visited at least once.
We consider the following basic question: how much can the omniscient Adversary delay the cover time without getting caught? Our main result is a tight upper bound on this delay factor.
Joint work with Tom Hayes, Seth Pettie, and Jared Saia.
Paper link: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.36

Keep up with DisCoMath Seminars on the DisCoMathS webpage.

Intended Audience:
All are welcome.

To request an interpreter, please visit myaccess.rit.edu