부산대학교 도서관

The k-truss decomposition algorithm aims to find the cohesive subgraphs in a graph. It includes a two-step procedure of triangle counting and weak edge deletion. Due to the significant differences of graph typologies, the best performer appearing in the last year’s MIT/IEEE/Amazon GraphChallenge presents to manually explore a well-optimized combination from many k-truss techniques for each graph dataset, but this requires expertise from multiple disciplines. Linear algebra provides a unified framework to write parallel and scalable k-truss decomposition algorithm easily. However, the work imbalance and low memory efficiency remain. In this work, we propose a productive yet efficient k-truss decomposition implementation on GPU based on the fine-grained linear algebra. We propose a preprocessing method that renumbers the vertices to eliminate the longest adjacency list to balance the workloads and putting the adjacency list of the same source vertex into shared memory that exploits the shared memory effectively to improve memory access efficiency. Results show that our approach outperforms a linear algebra based implementation– eager (a champion in 2019) by up to 24.81× and a manual optimization KTRUSSEXPLORER by up to 2.69×.