Efficient Densest Flow Queries in Transaction Flow Networks (Complete Version)
2026-02-17 • Databases
Databases
AI summaryⓘ
The authors worked with Grab, a digital payments company, to find better ways to detect fraud in money transaction networks. They created a new method called the S-T densest flow query that finds groups of sources and sinks in the network where the flow between them is very dense, which can reveal suspicious activity. Because solving this problem exactly is very hard, the authors designed an efficient algorithm named CONAN and a faster approximate version to handle large datasets. Their approach was tested and used in Grab’s fraud detection system, showing much faster results and better identification of fraud patterns compared to existing methods.
transaction flow networkfraud detectiondense flowmaximum flowNP-harddivide-and-conquer algorithmapproximation algorithmCONANsource setsink set
Authors
Jiaxin Jiang, Yunxiang Zhao, Lyu Xu, Byron Choi, Bingsheng He, Shixuan Sun, Jia Chen
Abstract
Transaction flow networks are crucial in detecting illicit activities such as wash trading, credit card fraud, cashback arbitrage fraud, and money laundering. \revise{Our collaborator, Grab, a leader in digital payments in Southeast Asia, faces increasingly sophisticated fraud patterns in its transaction flow networks. In industry settings such as Grab's fraud detection pipeline, identifying fraudulent activities heavily relies on detecting dense flows within transaction networks. Motivated by this practical foundation,} we propose the \emph{\(S\)-\(T\) densest flow} (\SDMF{}) query. Given a transaction flow network \( G \), a source set \( \Src \), a sink set \( \Dst \), and a size threshold \( k \), the query outputs subsets \( \Src' \subseteq \Src \) and \( \Dst' \subseteq \Dst \) such that the maximum flow from \( \Src' \) to \( \Dst' \) is densest, with \(|\Src' \cup \Dst'| \geq k\). Recognizing the NP-hardness of the \SDMF{} query, we develop an efficient divide-and-conquer algorithm, CONAN. \revise{Driven by industry needs for scalable and efficient solutions}, we introduce an approximate flow-peeling algorithm to optimize the performance of CONAN, enhancing its efficiency in processing large transaction networks. \revise{Our approach has been integrated into Grab's fraud detection scenario, resulting in significant improvements in identifying fraudulent activities.} Experiments show that CONAN outperforms baseline methods by up to three orders of magnitude in runtime and more effectively identifies the densest flows. We showcase CONAN's applications in fraud detection on transaction flow networks from our industry partner, Grab, and on non-fungible tokens (NFTs).