@inproceedings{70b08b3f313046f493eb4e38c95f1d10,
title = "HiDDen: Hierarchical dense subgraph detection with application to financial fraud detection",
abstract = "Dense subgraphs are fundamental patterns in graphs, and dense subgraph detection is often the key step of numerous graph mining applications. Most of the existing methods aim to find a single subgraph with a high density. However, dense subgraphs at different granularities could reveal more intriguing patterns in the underlying graph. In this paper, we propose to hierarchically detect dense subgraphs. The key idea of our method (HiDDen) is to envision the density of subgraphs as a relative measure to its background (i.e., the subgraph at the coarse granularity). Given that the hierarchical dense subgraph detection problem is essentially a nonconvex quadratic programming problem, we propose effective and efficient alternative projected gradient based algorithms to solve it. The experimental evaluations on real graphs demonstrate that (1) our proposed algorithms find subgraphs with an up to 40% higher density in almost every hierarchy; (2) the densities of different hierarchies exhibit a desirable variety across different granularities; (3) our projected gradient descent based algorithm scales linearly w.r.t the number of edges of the input graph; and (4) our methods are able to reveal interesting patterns in the underlying graphs (e.g., synthetic ID in financial fraud detection).",
keywords = "Financial fraud detection, Graph mining, Hierarchical dense subgraph detection",
author = "Si Zhang and Dawei Zhou and Yildirim, {Mehmet Yigit} and Scott Alcorn and Jingrui He and Hasan Davulcu and Hanghang Tong",
note = "Funding Information: This work is supported by NSF grants IIP-1430144, IIS-1552654 and IIS-1651203, ONR grant N00014-15-1-2821, DTRA grant HDTRA1-16-0017, ARO grant W911NF-16-1-0168, NIH grant R01LM011986, an IBM Faculty Award and a Baidu gift. The views and conclusions are those of the authors and should not be interpreted as representing the official policies of the funding agencies or the government. References; 17th SIAM International Conference on Data Mining, SDM 2017 ; Conference date: 27-04-2017 Through 29-04-2017",
year = "2017",
doi = "10.1137/1.9781611974973.64",
language = "English (US)",
series = "Proceedings of the 17th SIAM International Conference on Data Mining, SDM 2017",
publisher = "Society for Industrial and Applied Mathematics Publications",
pages = "570--578",
editor = "Nitesh Chawla and Wei Wang",
booktitle = "Proceedings of the 17th SIAM International Conference on Data Mining, SDM 2017",
address = "United States",
}