Density Decomposition of Multilayer Graphs

Multilayer graphs have emerged as a powerful model for representing complex systems with diverse types of interactions. Identifying cohesive subgraphs in such graphs is a fundamental task with broad applications in community detection, fraud analysis, and e-commerce recommendation. However, existing models either lack explicit density guarantees or fail to preserve across-layer structural cohesiveness. To address these limitations, in this paper, we propose a novel k-dense subgraph model, denoted as $D_{\mathrm{k}}$, which enforces layer-wise density constraints. Given a density vector $\mathbf{k}=\left[k_{\ell}\right]_{\ell \in L} \in \mathbb{Z}^{\vert L\vert}$, our model guarantees that the induced subgraph on each layer satisfies a minimum density threshold $k_{\ell}$. We further study the density decomposition problem: computing all non-empty $D_{\mathrm{k}} \mathrm{s}$ for feasible density vectors k. To this end, we design a suite of efficient algorithms. For computing a single $D_{\mathrm{k}}$, we first propose SLFBE, which uses network flow techniques to extract layer-wise subgraphs satisfying density thresholds. We then develop LCVSP, which combines k-core pruning and layerconstrained vertex set propagation to eliminate irrelevant vertices and accelerate convergence. For full density decomposition, we leverage the density lattice structure and propose HPDD, which incrementally constructs subgraphs by extending partial vectors layer by layer, enabling localized exploration and early pruning. To further improve scalability, we develop the HPDD+ algorithm, which adopts a recursive depth-first hierarchical strategy to lower memory cost. Additionally, HPDD+ employs an adaptive upperbounded divide-and-conquer approach that eliminates redundant computations. Extensive experiments on 9 real-world multilayer graphs demonstrate that our model discovers significantly higherquality subgraphs than existing methods, while our algorithms exhibit superior efficiency and scalability.