A GPU-based method for network alignment

Network graph models are a powerful tool for handling objects, in terms of interactions and relationships. For instance, in bioinformatics networks are applied for analysing complex biological systems, topologically, as well as for investigating their own homology. In this context, the pairwise network alignment can be performed for producing a set of node-to-node mappings from a source network to a target one. For instance, network alignment can be applied for porting knowledge from a simpler to a more complex system (e.g., a simpler biological organism to a complex one). In this paper, we presented a GPU-based method for the pairwise Local Network Alignment, implemented by using a greedy strategy. It leverages GPU parallelism to accelerate the large-scale computation of a node similarity matrix of interest. Our experimentation showed a relevant improvement in terms of runtime when processing is executed on GPU, in comparison to the traditional CPU computing. Briefly, our method has proven to be an effective solution for the alignment of large networks, especially with dense similarity matrices, thus proving to be an ideal candidate for use in real-world study cases.