# Parallel Higher-order Truss Decomposition

arXiv: https://arxiv.org/abs/2411.06405 · HTML: https://mlsanity.com/paper/2411.06405/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Nov 2024.

## Built on by (most cited first, 1 of 1)

- [Cross-attentive Cohesive Subgraph Embedding to Mitigate Oversquashing in GNNs](https://mlsanity.com/paper/2603.27529/) (2026)

## Abstract (arXiv)

The k-truss model is one of the most important models in cohesive subgraph analysis. The k-truss decomposition problem is to compute the trussness of each edge in a given graph, and has been extensively studied. However, the conventional k-truss model is difficult to characterize the fine-grained hierarchical structures in networks due to the neglect of high order information. To overcome the limitation, the higher-order truss model is proposed in the literature. However, the previous solutions only consider non-parallel scenarios. To fill the gap, in this paper, we conduct the first research to study the problem of parallel higher-order truss decomposition. Specifically, a parallel framework is first proposed. Moreover, several optimizations are further developed to accelerate the processing. Finally, experiments over 6 real-world networks are conducted to verify the performance of proposed methods.