Search papers, labs, and topics across Lattice.
This paper introduces NI-ORCA, a parallel algorithm designed to efficiently count the orbits of non-induced graphlets up to size four, addressing a critical gap in existing methods that only handle induced graphlets. By reformulating a system of linear equations and employing stage-specific parallelization strategies, NI-ORCA achieves significant performance improvements over traditional sequential algorithms. Experimental results indicate that NI-ORCA can deliver up to 30x speedups across various real-world and synthetic datasets, making it a powerful tool for graph analytics.
NI-ORCA achieves up to 30x speedups in counting non-induced graphlet orbits, revolutionizing the efficiency of graph analytics.
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.
