Optimization of algebraic MST algorithm based on GraphBLAS

With the rapid development of Internet technology, the analysis of large-scale graph data is widely used in the fields of social networking, natural language processing, and bioinformatics. Among them, Minimum Spanning Tree algorithm plays an important role as a basic algorithm in the field of graph data analysis. However, common MST algorithms such as Prim and Kruskal are difficult to be effectively parallelized to fully utilize the potential of modern multi-core technologies. To address these challenges, we propose an algebraic scheme for Boruvka’s minimal spanning tree algorithm and successfully implement it based on GraphBLAS. The parallelism of the code is improved by transforming the relevant computations on graph data into matrix and vector operations. Through experiments on multiple datasets, we find that the Boruvka algebraization scheme has significant performance improvements and provides a powerful solution for efficiently processing large-scale graph data.