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

Authors:
Publisher website
Google Scholar
Abstract
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\geq 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.
Funding Information
  • Basic and Applied Basic Research Foundation of Guangdong Province (2025A1515060015)
  • Shenzhen Science and Technology Program (GXWD20231129111306002)
  • Overseas Expertise Introduction Center for Discipline Innovation of Food Nutrition and Human Health (B26023)
  • Fundamental and Interdisciplinary Disciplines Breakthrough Plan of the Ministry of Education of China (JYB2025XDXM118)
  • National Natural Science Foundation of China (62472125)
  • Basic and Applied Basic Research Foundation of Guangdong Province (2025A1515011258)
  • Key Technologies R&D Program of Guangdong Province (2026B0909060001)
  • Shenzhen Science and Technology Programs (GXWD20231128102922001)
  • Ministry of Education - Singapore (MOE-T2EP20224-0011)
  • Tier 1 Award (RG20/24)

This publication has 67 references indexed in Scilit: