VF2-PS: Parallel and Scalable Subgraph Monomorphism in Arachne

This paper introduces a novel, parallel, and scalable implementation of the VF2 algorithm for subgraph monomorphism developed in the high-productivity language Chapel. Efficient graph analysis in large and complex network datasets is crucial across numerous scientific domains. We address this need through our enhanced VF2-PS implementation, widely utilized in subgraph matching, and integrating it into Arachne-a Python-accessible, open-source, large-scale graph analysis framework. Leveraging the parallel computing capabilities of modern hardware architectures, our implementation achieves significant performance improvements. Benchmarks on synthetic and real-world datasets, including social, communication, and neuroscience networks, demonstrate speedups of up to 97.0 X on 128 cores, compared to existing Python-based tools like NetworkX and DotMotif, which do not exploit parallelization. On large graphs, our new parallel VF2-PS algorithm and implementation also outperforms the Carletti et al.'s parallel VF3P implementation. Our results on large-scale graphs demonstrate scalability and efficiency, establishing it as a viable tool for subgraph monomorphism, the backbone of numerous graph analytics such as motif counting and enumeration. Arachne, including our VF2-PS implementation, can be found on GitHub: https://github.com/Bears-R-Us/arkouda-njit.