SNARE: a link analytic system for graph labeling and risk detection

ABSTRACT

Classifying nodes in networks is a task with a wide range of applications. It can be particularly useful in anomaly and fraud detection. Many resources are invested in the task of fraud detection due to the high cost of fraud, and being able to automatically detect potential fraud quickly and precisely allows human investigators to work more efficiently. Many data analytic schemes have been put into use; however, schemes that bolster link analysis prove promising. This work builds upon the belief propagation algorithm for use in detecting collusion and other fraud schemes. We propose an algorithm called SNARE (Social Network Analysis for Risk Evaluation). By allowing one to use domain knowledge as well as link knowledge, the method was very successful for pinpointing misstated accounts in our sample of general ledger data, with a significant improvement over the default heuristic in true positive rates, and a lift factor of up to 6.5 (more than twice that of the default heuristic). We also apply SNARE to the task of graph labeling in general on publicly-available datasets. We show that with only some information about the nodes themselves in a network, we get surprisingly high accuracy of labels. Not only is SNARE applicable in a wide variety of domains, but it is also robust to the choice of parameters and highly scalable-linearly with the number of edges in a graph.

REFERENCES

• 1: ]]L. Adamic and N. Glance. The political blogosphere and the 2004 U.S. election: Divided they blog, 2005.
• 2: Stephen Bay , Krishna Kumaraswamy , Markus G. Anderle , Rohit Kumar , David M. Steier, Large Scale Detection of Irregularities in Accounting Data, Proceedings of the Sixth International Conference on Data Mining, p.75-86, December 18-22, 2006 [doi>10.1109/ICDM.2006.93]
• 3: ]]R. Behrman and K. Carley. Modeling the structure and effectiveness of intelligence organizations: Dynamic information flow simulation. In Proceedings of the 8th International Command and Control Research and Technology Symposium., 2003.
• 4: ]]T. Bell and J. Carcello. A decision aid of assessing the likelihood of fraudulent financial reporting. Auditing: A journal of practice and theory, 19:169--184, 2000.
• 5: ]]M. Beneish. The detection of earnings manipulation. Financial Analysts Journal, 55(5):24--36, 1999.
• 6: ]]R. Bolton and D. Hand. Statistical fraud detection: A review, 2002.
• 7: ]]R. J. Bolton and D. J. Hand. Unsupervised profiling methods for fraud detection, 2001.
• 8: ]]T. Cohn. Scaling Conditional Random Fields for Natural Language Processing. PhD thesis, University of Melbourne, 2007.
• 9: ]]P. M. Dechow, W. Ge, C. R. Larson, and R. G. Sloan. Predicting material account manipulations. AAA 2008 Financial Accounting and Reporting Section (FARS), 2008.
• 10: ]]D. Dooley and G. Lamont. PwC 2005 securities litigation study. Technical report, PricewaterhouseCoopers LLP, 2006.
• 11: Andrew Fast , Lisa Friedland , Marc Maier , Brian Taylor , David Jensen , Henry G. Goldberg , John Komoroske, Relational data pre-processing techniques for improved securities fraud detection, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281293]
• 12: Tom Fawcett , Foster Provost, Adaptive Fraud Detection, Data Mining and Knowledge Discovery, v.1 n.3, p.291-316, 1997 [doi>10.1023/A:1009700419189]
• 13: Lisa Friedland , David Jensen, Finding tribes: identifying close-knit individuals from employment patterns, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281226]
• 14: ]]W. Golden, S. Skalak, and M. Clayton. A Guide to Forensic Accounting Investigation. John Wiley & Sons, Hoboken, N.J., 2006.
• 15: ]]H. Grove and T. Cook. A statistical analysis of financial ratio red flags. Oil, Gas and Energy Quarterly, 53(2):3212--3346, 2004.
• 16: R. Guha , Ravi Kumar , Prabhakar Raghavan , Andrew Tomkins, Propagation of trust and distrust, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988727]
• 17: Shawndra Hill , Foster Provost, The myth of the double-blind review?: author identification using only citations, ACM SIGKDD Explorations Newsletter, v.5 n.2, December 2003 [doi>10.1145/980972.981001]
• 18: ]]S. Hill, F. Provost, and C. Volinsky. Network-based marketing: Identifying likely adopters via consumer networks. Statistical Science, 22(2):256--275, 2006.
• 19: David Jensen , Jennifer Neville , Brian Gallagher, Why collective inference improves relational classification, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014125]
• 20: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 21: ]]S. A. Macskassy and F. Provost. Suspicion scoring based on guilt-by-association, collective inference, and focused data access. In Proceedings of the NAACSOS Conference, June 2005.
• 22: ]]C. W. Mulford and E. E. Comiskey. The Financial Numbers Game: Detecting Creative Accounting Practices. John Wiley & Sons, Hoboken, N.J., 2002.
• 23: Jennifer Neville , Özgür Şimşek , David Jensen , John Komoroske , Kelly Palmer , Henry Goldberg, Using relational knowledge discovery to prevent securities fraud, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081922]
• 24: ]]L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project, 1998.
• 25: Shashank Pandit , Duen Horng Chau , Samuel Wang , Christos Faloutsos, Netprobe: a fast and scalable system for fraud detection in online auction networks, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242600]
• 26: ]]H. Schilit. Financial Shenanigans: How to Detect Accounting Gimmicks and Fraud in Financial Reports. McGraw-Hill, 2002.
• 27: ]]S. Skalak and C. Nestler. Global economic crime survey 2005. Technical report, PricewaterhouseCooper LLP, 2005.
• 28: ]]J. Wells. Corporate Fraud Handbook: Prevention and Detection. John Wiley & Sons, Hoboken, N.J., 2004.
• 29: Jonathan S. Yedidia , William T. Freeman , Yair Weiss, Understanding belief propagation and its generalizations, Exploring artificial intelligence in the new millennium, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 30: Xiaojin Zhu , John Lafferty , Ronald Rosenfeld, Semi-supervised learning with graphs, Carnegie Mellon University, Pittsburgh, PA, 2005
• 31: Cai-Nicolas Ziegler , Georg Lausen, Propagation Models for Trust and Distrust in Social Networks, Information Systems Frontiers, v.7 n.4-5, p.337-358, December 2005 [doi>10.1007/s10796-005-4807-3]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Security

Keywords:
anomaly detection, belief propagation, social networks