Efficient Minimum $k$-Truss Search: A Decomposition-Based Approach
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 <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="yu-ieq3-3701433.gif"/></alternatives></inline-formula>-truss is particularly notable for its strong structural cohesiveness based on triangles. However, the classical <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="yu-ieq4-3701433.gif"/></alternatives></inline-formula>-truss problem aims to find the <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="yu-ieq5-3701433.gif"/></alternatives></inline-formula>-truss with the maximum number of vertices, which is often extremely large and complex in practice. To fully leverage the benefits of the <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="yu-ieq6-3701433.gif"/></alternatives></inline-formula>-truss, we consider a novel problem called the <italic>minimum <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="yu-ieq7-3701433.gif"/></alternatives></inline-formula>-truss problem</italic>, which seeks to identify a <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="yu-ieq8-3701433.gif"/></alternatives></inline-formula>-truss with the minimum number of vertices, where <inline-formula><tex-math notation="LaTeX">$k\geq 2$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>k</mml:mi><mml:mo>≥</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math><inline-graphic xlink:href="yu-ieq9-3701433.gif"/></alternatives></inline-formula> is a positive integer. We first formally prove the NP-hardness of the problem. We then design a baseline algorithm <monospace>MTEnum</monospace> that is based on the vertex enumeration and a heuristic method for computing an upper bound. Despite these efforts, <monospace>MTEnum</monospace> still faces practical efficiency issues which may be due to the fact that the <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="yu-ieq10-3701433.gif"/></alternatives></inline-formula>-truss lacks the hereditary property. To address this issue, we develop a novel decomposition-based framework <monospace>DSA</monospace>, which elegantly transforms the problem into a sequence of problems that are based on a new cohesive subgraph model called <italic>edge-based <inline-formula><tex-math notation="LaTeX">$s$</tex-math><alternatives><mml:math><mml:mi>s</mml:mi></mml:math><inline-graphic xlink:href="yu-ieq11-3701433.gif"/></alternatives></inline-formula>-plex (<inline-formula><tex-math notation="LaTeX">$s$</tex-math><alternatives><mml:math><mml:mi>s</mml:mi></mml:math><inline-graphic xlink:href="yu-ieq12-3701433.gif"/></alternatives></inline-formula>-eplex)</italic>. With the hereditary property of <inline-formula><tex-math notation="LaTeX">$s$</tex-math><alternatives><mml:math><mml:mi>s</mml:mi></mml:math><inline-graphic xlink:href="yu-ieq13-3701433.gif"/></alternatives></inline-formula>-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 <monospace>DSA</monospace>. In particular, <monospace>DSA</monospace> runs up to five orders of magnitude faster than the baseline <monospace>MTEnum</monospace>.