Efficiently Answering k-hop Reachability Queries in Large Dynamic Graphs for Fraud Feature Extraction

Zequan Xu, Siqiang Luo, Jieming Shi, Hui Li, Chen Lin, Qihang Sun, Shaofeng Hu

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

2 Citations (Scopus)

Abstract

Instant messaging client (IMC) is now an essential tool for mobile users. In the representative IMC We Chat, cybercriminals deceive frauds, causing financial loss to normal users. Through statistical analysis, we find that certain fraud interactions commonly occur among WeChat users who are not k-hop neighbors. Therefore, efficiently answering whether the distance between two vertices is not longer than k at a certain time point (i.e., k-hop reachability queries) over the dynamic social graph of WeChat becomes a crucial task for fraud feature extraction in the detection system: it can help human experts quickly identify suspicious user interactions and the query results can be further used as the input feature to the downstream machine learning based detection methods. In this paper, we illustrate Bidirectional k-hop Reachability Query Processing over a Dynamic Graph (BREAD) that is used in WeChat for extracting the k-hop reachability feature for fraud detection. BREAD adopts the idea of estimating Personalized PageRank value. It first conducts the backward search from the destination vertex to construct an intermediate vertex set. Then, it performs a certain amount of random walks from the start vertex to see whether they can hit the intermediate vertex set, and the results are returned to answer k-hop reachability queries. We further propose text{BREAD}++ that leverages the massive parallel processing power of GPU to achieve a considerable performance gain. Experiments on several large-scale dynamic graph benchmarks and the social graph of WeChat have demonstrated that text{BREAD}/text{BREAD}++ is superior than existing index-free competitors: our methods provide not only fast but also accurate responses and they are of practical value to k-hop reachability feature extraction in the fraud detection system of WeChat. Our implementation is available at https://github.com/XMUDM/BREAD.

Original languageEnglish
Title of host publicationProceedings - 2022 23rd IEEE International Conference on Mobile Data Management, MDM 2022
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages238-245
Number of pages8
ISBN (Electronic)9781665451765
DOIs
Publication statusPublished - Aug 2022
Event23rd IEEE International Conference on Mobile Data Management, MDM 2022 - Virtual, Paphos, Cyprus
Duration: 6 Jun 20229 Jun 2022

Publication series

NameProceedings - IEEE International Conference on Mobile Data Management
Volume2022-June
ISSN (Print)1551-6245

Conference

Conference23rd IEEE International Conference on Mobile Data Management, MDM 2022
Country/TerritoryCyprus
CityVirtual, Paphos
Period6/06/229/06/22

Keywords

  • fraud detection
  • k-hop reachability
  • personalized pagerank

ASJC Scopus subject areas

  • General Engineering

Fingerprint

Dive into the research topics of 'Efficiently Answering k-hop Reachability Queries in Large Dynamic Graphs for Fraud Feature Extraction'. Together they form a unique fingerprint.

Cite this