Cohesive subgraph mining is a fundamental task in graph data analytics. We re-visit the problem of listing all minimal $k$-cores, where a $k$-core is a subgraph in which every vertex has degree at least $k$, and minimality requires that no proper subset remains a $k$-core. Existing methods are computationally prohibitive due to explosive branching and costly branch state update, leading to the trivial worst-case bound $O^{*}\left(2^{n}\right)$ for the basic branch-and-bound baseline wh, where $O^{*}$ suppresses polynomial factors and $n$ is the number of vertices. In this paper, we present an improved method IMinC based on three key ideas: (i) a principled branching state with lineartime update; (ii) a pivot strategy that guides branching toward promising vertices; and (iii) a divide-and-conquer framework that initializes each subproblem to enable our pivot strategy throughout and reduce recursion depth. We further introduce three reduction rules that aggressively prune infeasible branches. Together, these components yield the worst-case time complexity of $O^{*}\left(\alpha_{\ell}^{n}\right)$, where $\alpha_{\ell}$ is a positive number strictly smaller than 2. We also extend IMinC to list minimal $k$-cores under a size bound, addressing practical needs such as size-bounded community search. Extensive experiments on 12 real-world graphs demonstrate that IMinC outperforms the baselines by up to 2 order of magnitude, delivering substantial gains in efficiency.
Yukai Sun, Kaiqiang Yu, Shengxin Liu et al.· IEEE International Conferenc...· 0 citations
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>.
Qifan Zhang, Yang Liu, Kaiqiang Yu et al.· IEEE Transactions on Knowled...· 0 citations