Accelerating Triangle-Connected Truss Community Search Across Heterogeneous Hardware
Open Access
- 2 April 2026
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 4 (1) , 1-26
Abstract
k -truss is one of the most widely used community models where each edge is contained in at least k -2 triangles, and Triangle-connected k -Truss Community ( k -TTC) is a strengthened variant of k -truss that further requires edges to reach each other via a series of adjacent triangles. EquiTree is the state-of-the-art tree-structured index, which is space efficient and can support time-optimal k -TTC search for query vertices. However, for large graphs with billions of edges, the sequential algorithm still needs seconds to conduct k -TTC search and hours to construct the index due to the costly triangle connectivity examination. In this paper, we study how to accelerate k -TTC search by hardware accelerators. Specifically, we propose a tensor-based framework, including index construction, online search, and index maintenance, which can be efficiently deployed and run on heterogeneous hardware. To accelerate index construction, we first propose an iterative basic algorithm which creates and refines supernodes and superedges based on each k -class layer by layer. To further boost the parallelism, we propose a triangle-based supernode and superedge creation strategy, which categorizes triangles into three types ( internal, marginal, external ), and applies tailored operations for each type to enable batch processing instead of iterative steps. Meanwhile, we propose the batch-based merging strategy to refine the index into a tree structure. We also propose tensor-based algorithms for online k -TTC search and index maintenance. Extensive experiments show that our tensor-based algorithms achieve an average speedup of two orders of magnitude over state-of-the-art methods in both index construction and community search, while efficiently maintaining indices for dynamic graphs. Moreover, we validated that our tensor-based algorithms can be smoothly deployed and run on heterogeneous hardware accelerators (NVIDIA GPUs and AMD GPUs) for acceleration.Keywords
Funding Information
- National Natural Science Foundation of China (6227235)
- National Natural Science Foundation of China (6227619)
This publication has 21 references indexed in Scilit:
- Identifying Concepts in Software ProjectsIEEE Transactions on Software Engineering, 2023
- K-truss community most favorites query based on top-tWorld Wide Web, 2021
- I/O efficient k-truss community search in massive graphsThe VLDB Journal, 2021
- -core: Theories and applicationsPhysics Reports, 2019
- A survey of community search over big graphsThe VLDB Journal, 2019
- Incremental k-core decomposition: algorithms and evaluationThe VLDB Journal, 2016
- Online search of overlapping communities2013
- Uncovering the overlapping community structure of complex networks in nature and societyNature, 2005
- Arboricity and Subgraph Listing AlgorithmsSIAM Journal on Computing, 1985
- Network structure and minimum degreeSocial Networks, 1983