Efficient trimming for strongly connected components calculation

Abstract

Strongly Connected Components (SCCs) are useful for many applications, such as community detection and personalized recommendation. Determining the SCCs of a graph, however, can be very expensive, and parallelization is not an easy way out: the paral-lelization itself is challenging, and its performance impact varies non-trivially with the input graph structure. This variability is due to trivial components, i.e., SCCs consisting of a single vertex, which lead to significant workload imbalance. Trimming is an effective method to remove trivial components, but is inefficient when used on graphs with few trivial components. In this work, we propose FB-AI-Trim, a parallel SCC algorithm with selective trimming. Our algorithm decides dynamically, at runtime, based on the input graph how to trim the graph. To this end, we train a neural network to predict, using topological graph information, whether trimming is beneficial for performance. We evaluate FB-AI-Trim using 173 unseen graphs, and compare it against four different static trimming models. Our results demonstrate that, over the set of graphs, FB-AI-Trim is the fastest algorithm. Furthermore, FB-AI-Trim is, in 80% of the cases, less than 10% slower than the best performing model on a single graph. Finally, FB-AI-Trim shows significant performance degradation in less than 3% of the graphs.