Metraipolis › archive › dc_df2944699e9e
From Enumeration to Covering: Near-Optimal Densest P-Partite Subgraph Search over Large Heterogeneous Information Networks — arXiv:2608.06906
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.06906
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-23T15:11:01.277Z
- SHA-256 of the archived text
d91a7150f0b64218a20eb873d08a5075d6de80d5423b8014db599ead2f36f5fb- Stable URL of this page
https://metraipolis.com/documento/dc_df2944699e9e
How to cite
From Enumeration to Covering: Near-Optimal Densest P-Partite Subgraph Search over Large Heterogeneous Information Networks — arXiv:2608.06906 — arXiv (en), https://arxiv.org/abs/2608.06906 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_df2944699e9e (Metraipolis archive dc_df2944699e9e, sha256 d91a7150f0b64218a20eb873d08a5075d6de80d5423b8014db599ead2f36f5fb)
BibTeX
@misc{dcdf2944699e9e,
title = {From Enumeration to Covering: Near-Optimal Densest P-Partite Subgraph Search over Large Heterogeneous Information Networks — arXiv:2608.06906},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.06906},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_df2944699e9e; sha256 d91a7150f0b64218a20eb873d08a5075d6de80d5423b8014db599ead2f36f5fb},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.06906. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-10 in cs.DS). Categorie arXiv: Data Structures and Algorithms (cs.DS). Pagina del lavoro: https://arxiv.org/abs/2608.06906 — 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-23T15:08:55.953Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-10?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).