Efficient Minimum k-Truss Search: A Decomposition-Based Approach

Cohesive subgraph mining has been extensively studied and finds numerous graph mining applications such as link farm identification, community detection, and product recommendation. Among various cohesive subgraph structures, the k-truss is particularly notable for its strong structural cohesiveness based on triangles. However, the classical k-truss problem aims to find the k-truss with the maximum number of vertices, which is often extremely large and complex in practice. To fully leverage the benefits of the k-truss, we consider a novel problem called the minimum k-truss problem, which seeks to identify a k-truss with the minimum number of vertices, where k ≥ 2 is a positive integer. We first formally prove the NP-hardness of the problem. We then design a baseline algorithm MTEnum that is based on the vertex enumeration and a heuristic method for computing an upper bound. Despite these efforts, MTEnum still faces practical efficiency issues which may be due to the fact that the k-truss lacks the hereditary property. To address this issue, we develop a novel decomposition-based framework DSA, which elegantly transforms the problem into a sequence of problems that are based on a new cohesive subgraph model called edge-based s-plex (s-eplex). With the hereditary property of s-eplex, we design a branch-and-bound algorithm with several customized techniques for the newly formulated problem. Extensive experiments demonstrate the effectiveness of our studied problem and the efficiency of our proposed algorithm DSA. In particular, DSA runs up to five orders of magnitude faster than the baseline MTEnum.