Fraudar: Graph-Based Fraud Detection in Bipartite Transaction Networks

During major shopping festivals, merchants often resort to "brushing"—paying a crowd to place fake orders and reviews—to boost sales and rankings, creating a large ecosystem of buyers, sellers, intermediaries, and logistics that harms market fairness and misleads consumers.

Traditional fraud detection examines orders, products, users, devices, and logistics separately, but evolving cheating tactics render static features ineffective. By viewing the entire ecosystem as a transaction network, the problem becomes identifying a suspicious sub‑network within a larger bipartite graph composed of two node types: consumers (or fraud workers) and merchants.

The article introduces the Fraudar algorithm (KDD 2016 Best Paper) which defines a global suspiciousness score G(S) = (F(A)+F(B))/(|A|+|B|), where F(·) is the sum of edge‑based suspiciousness. Fraudar greedily removes the node with the lowest contribution, updating G after each removal, and uses priority trees to locate the minimum efficiently.

To improve scalability, the algorithm first discards nodes whose individual suspiciousness falls below twice the initial global score, then removes nodes in batches proportional to the remaining population, balancing speed and accuracy for graphs containing millions of nodes.

Fraudar’s unsupervised dense sub‑graph detection is combined with supervised models that score individual nodes based on features such as registration age, activity level, and device stability. The supervised scores re‑weight node suspiciousness, while the unsupervised clusters provide additional labeled data, forming a collaborative training loop that enhances both detection precision and coverage.

Although Fraudar shares common limitations of unsupervised methods—low interpretability and stability—it serves as a powerful tool for pinpointing high‑risk fraud clusters in e‑commerce, payment, and related industries when integrated with domain knowledge and supervised refinement.