The Webs We Weave: Fighting Fraud in Real Time with Large Dynamic Graphs
This article is part of the Academic Alibaba series and is taken from the paper entitled “Real-time Constrained Cycle Detection in Large Dynamic Graphs” Xiafei Qiu, Wubin Cen, Zhengping Qian, You Peng, Ying Zhang, Xuemin Lin, and Jingren Zhou, accepted by VLDB 2018. The full paper can be read here.
While it may seem unlikely when one considers the massive scale of the Internet, one’s online activity can often be modeled as a graph. From social networks to e-commerce transactions to online payments, graph structures encode complex relationships among entities, with some graphs having hundreds of millions of edges and vertices. For example, on an e-commerce platform like Alibaba’s Taobao and TMall, vertices may represent users, and edges may represent payments and transactions.
The cyclical relationships between these vertices and edges can be used to understand trends and even to root out fraud. However, the structure of these graphs is constantly changing with the continuous stream of information produced by web users. This makes the tasks of effectively storing and managing the dynamic graph system and providing real-time analytics challenging.
In collaboration with the University of New South Wales and the University of Technology Sydney, Alibaba’s tech team has created GraphS, a new system designed to detect constrained cycles in a dynamic graph and to return satisfying cycles in real-time.
Monitoring Graph Patterns in Real Time
While previous graph frameworks have been successful in performing offline analytics to achieve a high throughput on a large scale, they also have a large degree of latency, which is not acceptable when dealing with data sets that can change by the second. To meet the real-time response time needed for a large dynamic graph, indexing solutions must have a small index size, must update quickly, and must efficiently enumerate all length-constrained simple paths for any two vertices.
Researchers formulated a hot point-based index that can be selectively applied to a specific portion of the graph. This index is built and maintained for each query to accelerate query time and achieve high system throughput. The GraphS system is developed to monitor various online fraudulent activities at Alibaba through cycle detection. As the graph evolves, the system adapts itself to capture new hot points and update the index accordingly. Through search evaluation, the index is efficiently maintained. With additional optimization techniques to evaluate constrained cycles concurrently and increase system throughput, this hot point-based index can handle a peak rate of tens of thousands of edge updates per second and find every cycle within predefined constraints in a few milliseconds.
Breaking the Cycles of Online Fraud
Researchers put the GraphS system to the test on Alibaba’s e-commerce platform, which serves millions of users each day. The system was tasked with monitoring fraudulent transactions involving particular types of user activity, using data from real-world users and transactions. To repeat this process under various conditions, researchers collected traces of 500,000 updates from real production to use in their evaluation.
For this massive dynamic graph, the system was able to handle a peak rate of tens of thousands of edge updates per second and find every cycle within predefined constraints with a 20-millisecond latency in 99.9% of cases. Going forward, researchers hope to develop GraphS further to support querying various structural patterns with complex constraints such as tree-like graph patterns and to share indexes among different queries to optimize index maintenance cost and individual query performance.
The full paper can be read here.
Alibaba Tech
First hand and in-depth information about Alibaba’s latest technology → Facebook: “Alibaba Tech”. Twitter: “AlibabaTech”.
