Lune

VLDB2025Top-tier venue

Truss Decomposition in Hypergraphs

Hongchao Qin, Guang Zeng, Ronghua Li, Longlong Lin, Ye Yuan, Guoren Wang

Abstract

Truss decomposition is a fundamental approach in graph theory that focuses on uncovering cohesive subgraphs within networks. However, many networks involve groupwise rather than pairwise relationships and are often represented as hypergraphs. Modeling and capturing k-truss in hypergraphs is essential for uncovering tight-knit relationships in such multi-relational networks. In this paper, we tackle the problem of truss decomposition in hypergraph. A hyper k-truss is a subgraph in which each node is part of at least k hyper-triangles. We first introduce a framework for hyper-truss decomposition and determine that the most time-consuming component is counting hyper-triangles. To count all hyper-triangles efficiently, we propose an edge-iterator algorithm. To further reduce redundant computations, we present an improved algorithm that combines edge-iterator and node-iterator techniques to prune non-promising nodes. Next, to handle common nodes in hypergraphs, we develop a novel prefix forest technique to encode all hyperedges and count triangles within this prefix forest. We also propose several optimization strategies that reorder nodes and hyperedges to improve work balancing. Finally, we conduct extensive experiments on real-world hypergraph datasets, demonstrating the efficiency and effectiveness of our algorithms.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Distributed D-core Decomposition over Large Directed Graphs cites Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs
Builds onCited byLeft to right by year; the more cited, the higher.

Builds on9

  1. Efficient Bitruss Decomposition for Large-scale Bipartite GraphsKai Wang, Xuemin Lin, Lu Qin, Wenjie Zhang et al.ICDE 2020 · 107 citations
  2. Accelerating Triangle Counting on GPULin Hu, Lei Zou, Yu LiuSIGMOD 2021 · 38 citations
  3. Distributed D-core Decomposition over Large Directed GraphsXuankun Liao, Qing Liu, Jiaxin Jiang, Xin Huang et al.VLDB 2022 · 32 citations
  4. Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic GraphsQing Liu, Xuliang Zhu, Xin Huang, Jianliang XuVLDB 2021 · 27 citations
  5. Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate EdgesXiangyang Gou, Lei ZouSIGMOD 2021 · 26 citations

Related papers

  1. Efficient Hyper-truss Decomposition over HypergraphsHaozhe Yin, Kai Wang, Wenjie Zhang, Xuemin LinVLDB 2026
  2. Accelerating Truss Decomposition on Heterogeneous ProcessorsYulin Che, Zhuohang Lai, Shixuan Sun, Yue Wang et al.VLDB 2020 · 46 citations
  3. On Breaking Truss-Based CommunitiesHuiping Chen, Alessio Conte, Roberto Grossi, Grigorios Loukides et al.KDD 2021 · 11 citations
  4. TDT: Tensor Based Directed Truss DecompositionGuojing Li, Yuanyuan Zhu, Junchao Ma, Ming Zhong et al.ICDE 2025 · 1 citation
  5. Adaptive Truss Maximization on Large Graphs: A Minimum Cut ApproachZitan Sun, Xin Huang, Chengzhi Piao, Cheng Long et al.ICDE 2024 · 2 citations
Dusk over the sea between two cliffs drawn in fine vertical lines