Efficient Hyper-Truss Decomposition over Hypergraphs
Proceedings of the VLDB Endowment · 01.06.2026 · 19 (10) · 2549-2562
DOI: 10.14778/3828612.3828614 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 03.09.2026. Verfasst von Haozhe Yin und 3 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 60 Literaturangaben.
Abstract (Originalsprache)
Cohesive subgraph mining in hypergraphs has recently attracted increasing research attention due to its broad applicability in domains such as social networks, co-authorship networks, and recommendation systems. An important model, the hyper k -truss, is defined as a maximal cohesive subgraph in which each hyper-edge is contained in at least ( k – 2) hyper-triangles (i.e., structures formed by three pairwise connected hyperedges). In this paper, we study the problem of hyper-truss decomposition, which aims to identify all hyper k -trusses for k ≥ 0. Due to the complex structure of hyper-triangles, the existing hyperedge-aware framework for hyper-truss decomposition incurs extra computational cost by traversing open hyper-triangles (i.e., hyper-triangles in which two hyperedges are not connected). Moreover, existing strategies enumerate all supporting hyper-triangles for each peeled hyperedge, which substantially limits overall efficiency. To address these issues, we propose a vertex-aware framework that leverages vertex-level connectivity among hyperedges. Under this framework, we design a vertex-oriented counting strategy to completely eliminate the traversal of open hyper-triangles during the counting phase and a vertex-based state propagation method to minimize the number of hyper-triangles enumerated in the peeling phase. Extensive experiments on eleven real-world datasets demonstrate the effectiveness and efficiency of our approach.
Zitieren
APA
Yin, H., Wang, K., Zhang, W., & Lin, X. (2026). Efficient Hyper-Truss Decomposition over Hypergraphs. Proceedings of the VLDB Endowment, 19(10), 2549-2562. https://doi.org/10.14778/3828612.3828614
Vancouver
Yin H, Wang K, Zhang W, Lin X. Efficient Hyper-Truss Decomposition over Hypergraphs. Proceedings of the VLDB Endowment. 2026;19(10):2549-2562. doi:10.14778/3828612.3828614
BibTeX
@article{Yin2026,
author = {Yin, Haozhe and Wang, Kai and Zhang, Wenjie and Lin, Xuemin},
title = {Efficient Hyper-Truss Decomposition over Hypergraphs},
journal = {Proceedings of the VLDB Endowment},
year = {2026},
volume = {19},
number = {10},
pages = {2549--2562},
doi = {10.14778/3828612.3828614}
}
EUVIMED