Dense Subgraph Extraction And Its Application

Graph is a natural tool to model the relationship between entities for many types of data.Mining information from complex graph data has important theoretical significance and practical value.Dense subgraph extraction is a fundamental graph mining task.The goal is to extract the subgraph with dense connection between vertices from the graph,which is widely used in social networks,bioinformatics,sociology,etc.In this paper,we introduce the weighted k-clique density,a novel formulation for dense subgraph extraction.We show that the problem of maximizing the weighted k-clique density can be solved optimally in polynomial time by solving a series of minimum cut problems.For scalability,we also propose a more efficient greedy algorithm with performance guarantee.The experimental results on real-world network datasets show that,compared with the state-of-the-art algorithms,the proposed algorithm can find much denser subgraph in terms of the edge density and the triangle density.Finally,the proposed dense subgraph extraction method is applied to the feature selection task of anomaly detection.The feature anomaly graph is constructed to capture the abnormality of the feature itself and the feature pair.The proposed dense subgraph extraction algorithm is used to extract the dense subgraph on the feature anomaly graph.The vertices of the extracted subgraph are the selected features related to anomaly detection.Experiments show that the algorithm can filter out features not related to anomaly detection and improve the performance of unsupervised anomaly detection models.