HiDDen: Hierarchical Dense Subgraph Detection with Application to Financial Fraud Detection

Authors:
  • SZSi Zhang
    Si Zhang
  • DZDawei Zhou
    Dawei Zhou
  • MYMehmet Yigit Yildirim
    Mehmet Yigit Yildirim
  • SAScott Alcorn
    Scott Alcorn
  • JHJingrui He
    Jingrui He
  • HDHasan Davulcu
    Hasan Davulcu
  • HTHanghang Tong
    Hanghang Tong

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).