BoxDPpS performs box-level search with safe region pruning, eliminates redundant representations of the same iRM-set, improves early pruning through bounded warm-up, and compresses each fixed-M auxiliary network for exact parametric pseudoflow solving.
Abstract
Heterogeneous information networks (HINs) model typed entities and typed relations, where dense cross-type structures can reveal cohesive semantic patterns such as prolific author-paper-venue groups. Given a query meta-path, the densest P-partite subgraph search (DPpS) problem jointly selects a nonempty vertex set at each typed position and maximizes the number of induced meta-path instances normalized by the geometric mean of the selected set sizes. Existing exact methods solve DPpS by searching over iRM-sets and reducing each fixed-M problem to minimum-cut computations. However, their scalability is limited by the large number of candidate iRM-sets and the high cost of repeatedly solving large auxiliary networks. In this paper, we propose BoxDPpS, an efficient exact approach that reduces both sources of cost. It performs box-level search with safe region pruning, eliminates redundant representations of the same iRM-set, improves early pruning through bounded warm-up, and compresses each fixed-M auxiliary network for exact parametric pseudoflow solving. Experiments on seven real-world datasets show that BoxDPpS preserves the exact DPpS optimum while achieving an average speedup of 27.04x over the state-of-the-art method.
Given a heterogeneous information network (HIN) and a query meta-path P of length i, the densest P-partite subgraph problem finds the subgraph, spanning the i typed layers of P, that maximizes a parameter-free density: the number of meta-path instances over the geometric mean of the layer sizes. It has applications across bibliographic, e-commerce, and biomedical networks. The state-of-the-art approximation linearizes the geometric-mean objective by fixing per-layer weights, but solves one subproblem for every feasible weight set, of which there are $O((n/i)^i)$, and on each achieves only a $1/i$ approximation. We show that neither the exhaustive enumeration nor the loose guarantee is necessary. First, we replace enumeration by covering: polylogarithmically many representative weight sets, localized further by a data-dependent bound, cover all feasible ones while losing only a tunable factor $1+\eta$ in density. Second, we cast each fixed-weight subproblem as a weighted supermodular densest-subgraph instance and solve it near-optimally, lifting the overall guarantee to $(1-\delta)/(1+\eta)$. To our knowledge, this is the first near-optimal density approximation beyond the bipartite ($i=2$) case, and it yields a PTAS for every fixed i. Algorithmically, our solver is an adaptive peeling scheme that never materializes the meta-path instances, whose number can exceed the graph size by orders of magnitude. An incumbent-driven reduction further discards representative weight sets before their subproblems are solved. Experiments on five real HINs show that our algorithms achieve substantial speedups over enumeration-based baselines and can further certify the near-optimality of the returned subgraph.
Lu Chen, Chengfei Liu, Rui Zhou et al.· 0 citations
The Hierarchical Heterogeneous Information Network is proposed as a data model that organizes typed entity relations in a main structure layer and descriptive evidence in a strong attribute layer as well as developing controllable approximate reduction as one instantiation.
Qinggeng Jin, Wujie Hu, Yongjie Liang et al.· Journal of King Saud Univers...· 0 citations
CP-McSplitDAL is introduced, a cooperative parallel framework that extends McSplit-DAL with portfolio-style multi-heuristic search on shared-memory machines and achieves lower regret in time to optimality, improves solution quality under time limits, and better exploits multi-core hardware than non-cooperative or purely sequential variants.
Lorenzo Cardone, Stefano Quer· International Conference on...· 0 citations
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
