NI-ORCA: A Parallel Algorithm for Counting the Orbits of Non-Induced Graphlets up to K4
Provides a scalable solution for non-induced orbit counting, a previously unsupported task with applications in network analysis.
NI-ORCA is the first parallel algorithm for exact, scalable counting of non-induced graphlet orbits up to K4, achieving up to 30x speedup over sequential methods on real-world and synthetic graphs.
Counting the orbits of graphlets in a network is a vital tool for understanding the structural roles of vertices in various graph analytics tasks. While existing algorithms efficiently compute orbits of induced graphlets, many real-world applications require non-induced orbit counts. However, no current method offers exact, scalable, and parallel support for non-induced orbit counting. This paper presents NI-ORCA, a parallel algorithm to efficiently compute the orbits of non-induced graphlets up to size four (4-clique). NI-ORCA extends the ORCA framework for non-induced orbit counting by reformulating a system of linear equations. The algorithm consists of three stages: triangle counting, 4-clique enumeration, and orbit solving. We design and implement stage-specific parallelisation strategies using thread and vertex-local memory models and data structures, minimising contention and balancing workload. We further analyse the impact of scheduling policies, chunk sizes, and affinity strategies on performance. Experimental analysis on eight real-world datasets and a series of synthetic Erddos-Renyi graphs demonstrates that a mixed mode combining stage-specific data structure, with dynamic scheduling with small chunk sizes, delivers consistent speedup and effective load balancing. Our results show that NI-ORCA significantly outperforms state-of-the-art sequential algorithms, achieving up to 30x speedups.