skip to main content
10.1145/2939672.2939747acmconferencesArticle/Chapter ViewAbstractPublication PageskddConference Proceedingsconference-collections
research-article
Public Access

FRAUDAR: Bounding Graph Fraud in the Face of Camouflage

Published: 13 August 2016 Publication History

Abstract

Given a bipartite graph of users and the products that they review, or followers and followees, how can we detect fake reviews or follows? Existing fraud detection methods (spectral, etc.) try to identify dense subgraphs of nodes that are sparsely connected to the remaining graph. Fraudsters can evade these methods using camouflage, by adding reviews or follows with honest targets so that they look "normal". Even worse, some fraudsters use hijacked accounts from honest users, and then the camouflage is indeed organic. Our focus is to spot fraudsters in the presence of camouflage or hijacked accounts. We propose FRAUDAR, an algorithm that (a) is camouflage-resistant, (b) provides upper bounds on the effectiveness of fraudsters, and (c) is effective in real-world data. Experimental results under various attacks show that FRAUDAR outperforms the top competitor in accuracy of detecting both camouflaged and non-camouflaged fraud. Additionally, in real-world experiments with a Twitter follower-followee graph of 1.47 billion edges, FRAUDAR successfully detected a subgraph of more than 4000 detected accounts, of which a majority had tweets showing that they used follower-buying services.

Supplementary Material

MP4 File (kdd2016_hooi_bounding_graph_01-acm.mp4)

References

[1]
L. Akoglu, R. Chandy, and C. Faloutsos. Opinion fraud detection in online reviews by network effects. In ICWSM, 2013.
[2]
A. Beutel, W. Xu, V. Guruswami, C. Palow, and C. Faloutsos. Copycatch: stopping group attacks by spotting lockstep behavior in social networks. In 22nd WWW, pages 119--130. International World Wide Web Conferences Steering Committee, 2013.
[3]
Q. Cao, M. Sirivianos, X. Yang, and T. Pregueiro. Aiding the detection of fake accounts in large scale social online services. In NSDI, 2012.
[4]
M. Charikar. Greedy approximation algorithms for finding dense components in a graph. In Approximation Algorithms for Combinatorial Optimization, pages 84--95. Springer, 2000.
[5]
C. Cortes, D. Pregibon, and C. Volinsky. Communities of interest. Springer, 2001.
[6]
S. Ghosh, B. Viswanath, F. Kooti, N. K. Sharma, G. Korlam, F. Benevenuto, N. Ganguly, and K. P. Gummadi. Understanding and combating link farming in the twitter social network. In 21st WWW, pages 61--70. ACM, 2012.
[7]
C. Giatsidis, D. M. Thilikos, and M. Vazirgiannis. Evaluating cooperation in communities with the k-core structure. In Advances in Social Networks Analysis and Mining (ASONAM), 2011 International Conference on, pages 87--93. IEEE, 2011.
[8]
Z. Gu, K. Pei, Q. Wang, L. Si, X. Zhang, and D. Xu. Leaps: Detecting camouflaged attacks with statistical learning guided by program analysis.
[9]
Z. Gyöngyi, H. Garcia-Molina, and J. Pedersen. Combating web spam with trustrank. In VLDB Endowment, pages 576--587, 2004.
[10]
M. Jiang, A. Beutel, P. Cui, B. Hooi, S. Yang, and C. Faloutsos. A general suspiciousness metric for dense blocks in multimodal data. In Data Mining (ICDM), 2015 IEEE International Conference on, pages 781--786. IEEE, 2015.
[11]
M. Jiang, P. Cui, A. Beutel, C. Faloutsos, and S. Yang. Catchsync: catching synchronized behavior in large directed graphs. In 20th KDD, pages 941--950. ACM, 2014.
[12]
M. Jiang, P. Cui, A. Beutel, C. Faloutsos, and S. Yang. Inferring strange behavior from connectivity pattern in social networks. In Advances in Knowledge Discovery and Data Mining, pages 126--138. Springer, 2014.
[13]
N. Jindal and B. Liu. Opinion spam and analysis. In ICDM 2008, pages 219--230. ACM, 2008.
[14]
G. Karypis and V. Kumar. METIS: Unstructured graph partitioning and sparse matrix ordering system. The University of Minnesota, 2, 1995.
[15]
J. Kleinberg. Authoritative sources in a hyperlinked environment. Journal of the ACM (JACM), 46(5):604--632, 1999.
[16]
H. Kwak, C. Lee, H. Park, and S. Moon. What is twitter, a social network or a news media? In 19th WWW, pages 591--600. ACM, 2010.
[17]
J. Leskovec, D. Huttenlocher, and J. Kleinberg. Signed networks in social media. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, pages 1361--1370. ACM, 2010.
[18]
J. McAuley and J. Leskovec. Hidden factors and hidden topics: understanding rating dimensions with review text. In Proceedings of the 7th ACM conference on Recommender systems, pages 165--172. ACM, 2013.
[19]
A. Molavi Kakhki, C. Kliman-Silver, and A. Mislove. Iolaus: Securing online content rating systems. In 22nd WWW, pages 919--930. International World Wide Web Conferences Steering Committee, 2013.
[20]
M. Ott, Y. Choi, C. Cardie, and J. T. Hancock. Finding deceptive opinion spam by any stretch of the imagination. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies-Volume 1, pages 309--319. Association for Computational Linguistics, 2011.
[21]
S. Pandit, D. H. Chau, S. Wang, and C. Faloutsos. Netprobe: a fast and scalable system for fraud detection in online auction networks. In 16th WWW, pages 201--210. ACM, 2007.
[22]
B. Perozzi, L. Akoglu, P. Iglesias Sánchez, and E. Müller. Focused clustering and outlier detection in large attributed graphs. In 20th KDD, pages 1346--1355. ACM, 2014.
[23]
B. Prakash, M. Seshadri, A. Sridharan, S. Machiraju, and C. Faloutsos. Eigenspokes: Surprising patterns and community structure in large graphs. PAKDD, 2010a, 84, 2010.
[24]
A. Rajaraman, J. D. Ullman, J. D. Ullman, and J. D. Ullman. Mining of massive datasets, volume 1. Cambridge University Press Cambridge, 2012.
[25]
N. Shah, A. Beutel, B. Gallagher, and C. Faloutsos. Spotting suspicious link behavior with fbox: An adversarial perspective. arXiv preprint arXiv:1410.3915, 2014.
[26]
D. N. Tran, B. Min, J. Li, and L. Subramanian. Sybil-resilient online content voting. In NSDI, volume 9, pages 15--28, 2009.
[27]
C. Tsourakakis. The k-clique densest subgraph problem. In 24th WWW, pages 1122--1132. International World Wide Web Conferences Steering Committee, 2015.
[28]
S. Virdhagriswaran and G. Dakin. Camouflaged fraud detection in domains with complex relationships. In 12th KDD, pages 941--947. ACM, 2006.
[29]
H. Wang, Y. Lu, and C. Zhai. Latent aspect rating analysis without aspect keyword supervision. In 17th KDD, pages 618--626. ACM, 2011.
[30]
B. Wu, V. Goel, and B. D. Davison. Propagating trust and distrust to demote web spam. MTW, 190, 2006.
[31]
H. Yu, P. B. Gibbons, M. Kaminsky, and F. Xiao. Sybillimit: A near-optimal social network defense against sybil attacks. In Security and Privacy, 2008. SP 2008. IEEE Symposium on, pages 3--17. IEEE, 2008.
[32]
H. Yu, M. Kaminsky, P. B. Gibbons, and A. Flaxman. Sybilguard: defending against sybil attacks via social networks. ACM SIGCOMM Computer Communication Review, 36(4):267--278, 2006.

Cited By

View all
  • (2025) Nowhere to H 2 IDE: Fraud Detection From Multi-Relation Graphs via Disentangled Homophily and Heterophily Identification IEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.352310737:3(1380-1393)Online publication date: Mar-2025
  • (2025)Temporal Insights for Group-Based Fraud Detection on e-Commerce PlatformsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.348512737:2(951-965)Online publication date: Feb-2025
  • (2025)Multiplex graph fusion network with reinforcement structure learning for fraud detection in online e-commerce platformsExpert Systems with Applications10.1016/j.eswa.2024.125598262(125598)Online publication date: Mar-2025
  • Show More Cited By

Index Terms

  1. FRAUDAR: Bounding Graph Fraud in the Face of Camouflage

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    KDD '16: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
    August 2016
    2176 pages
    ISBN:9781450342322
    DOI:10.1145/2939672
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 13 August 2016

    Permissions

    Request permissions for this article.

    Check for updates

    Badges

    • Best Paper

    Author Tags

    1. content ranking
    2. fraud detection

    Qualifiers

    • Research-article

    Funding Sources

    Conference

    KDD '16
    Sponsor:

    Acceptance Rates

    KDD '16 Paper Acceptance Rate 66 of 1,115 submissions, 6%;
    Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

    Upcoming Conference

    KDD '25

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)790
    • Downloads (Last 6 weeks)68
    Reflects downloads up to 19 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2025) Nowhere to H 2 IDE: Fraud Detection From Multi-Relation Graphs via Disentangled Homophily and Heterophily Identification IEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.352310737:3(1380-1393)Online publication date: Mar-2025
    • (2025)Temporal Insights for Group-Based Fraud Detection on e-Commerce PlatformsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.348512737:2(951-965)Online publication date: Feb-2025
    • (2025)Multiplex graph fusion network with reinforcement structure learning for fraud detection in online e-commerce platformsExpert Systems with Applications10.1016/j.eswa.2024.125598262(125598)Online publication date: Mar-2025
    • (2024)AHD-SLE: Anomalous Hyperedge Detection on Hypergraph Symmetric Line ExpansionAxioms10.3390/axioms1306038713:6(387)Online publication date: 7-Jun-2024
    • (2024)Spade: A Real-Time Fraud Detection FrameworkProceedings of the VLDB Endowment10.14778/3685800.368584817:12(4253-4256)Online publication date: 8-Nov-2024
    • (2024)RUSH: Real-Time Burst Subgraph Detection in Dynamic GraphsProceedings of the VLDB Endowment10.14778/3681954.368202817:11(3657-3665)Online publication date: 1-Jul-2024
    • (2024)FraudGT: A Simple, Effective, and Efficient Graph Transformer for Financial Fraud DetectionProceedings of the 5th ACM International Conference on AI in Finance10.1145/3677052.3698648(292-300)Online publication date: 14-Nov-2024
    • (2024)FiFrauD: Unsupervised Financial Fraud Detection in Dynamic Graph StreamsACM Transactions on Knowledge Discovery from Data10.1145/364185718:5(1-29)Online publication date: 27-Feb-2024
    • (2024)A Learned Generalized Geodesic Distance Function-Based Approach for Node Feature Augmentation on GraphsProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671858(49-58)Online publication date: 25-Aug-2024
    • (2024)Collaborative Fraud Detection on Large Scale Graph Using Secure Multi-Party ComputationProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679863(1473-1482)Online publication date: 21-Oct-2024
    • Show More Cited By

    View Options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Login options

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media