Efficient Hyper-truss Decomposition over Hypergraphs

vldb26-2936 · Regular Research · Haozhe Yin, Kai Wang, Wenjie Zhang, Xuemin Lin
Abstract

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 hyperedge 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.

Assigned reviewers

No reviewers assigned yet.

Candidates from the panel ranked by taxonomy affinity

#ReviewerMatchLoadWhy