Metraipolis › archive › dc_7dcbeb58d324

Scalable Exact Densest P-Partite Subgraph Search in Heterogeneous Information Networks — arXiv:2608.03061

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.03061
License (as archived): CC0-1.0
Archived: 2026-10-31T13:08:35.278Z
SHA-256 of the archived text: e4564f785b7a29b9b0631741ef298d275b9a516983b8b27ec81c2490c7983f9f
Stable URL of this page: https://metraipolis.com/documento/dc_7dcbeb58d324

How to cite

Scalable Exact Densest P-Partite Subgraph Search in Heterogeneous Information Networks — arXiv:2608.03061 — arXiv (en), https://arxiv.org/abs/2608.03061 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7dcbeb58d324 (Metraipolis archive dc_7dcbeb58d324, sha256 e4564f785b7a29b9b0631741ef298d275b9a516983b8b27ec81c2490c7983f9f)

BibTeX

@misc{dc7dcbeb58d324,
  title = {Scalable Exact Densest P-Partite Subgraph Search in Heterogeneous Information Networks — arXiv:2608.03061},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.03061},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7dcbeb58d324; sha256 e4564f785b7a29b9b0631741ef298d275b9a516983b8b27ec81c2490c7983f9f},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.03061. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: statistica e scienza dei dati (retro-catalogo arXiv: annunci del 2026-08-05 in cs.DB).
Categorie arXiv: Databases (cs.DB).
Pagina del lavoro: https://arxiv.org/abs/2608.03061 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-31T12:56:10.508Z dalla pagina https://arxiv.org/catchup/cs.DB/2026-08-05?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).