NI-ORCA: A Parallel Algorithm for Counting the Orbits of Non-Induced Graphlets up to K 4 K_{4}

Syed Ibtisam Tauhidi, Arindam Karmakar, Thai Son Mai, Hans Vandierendonck · 2026

Read NI-ORCA: A Parallel Algorithm for Counting the Orbits of Non-Induced Graphlets up to K 4 K_{4} by Syed Ibtisam Tauhidi, Arindam Karmakar, Thai Son Mai, Hans Vandierendonck (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-29651.txt.

Introduction

Tauhidi, Karmakar, Mai, and Vandierendonck present NI-ORCA, a parallel algorithm that counts the orbits of non-induced graphlets in a network. Graphlets are small subgraph patterns, and a vertex's orbit records its structural role inside those patterns. Existing algorithms handle induced graphlets efficiently, but many applications need non-induced counts, where extra edges may be present.

NI-ORCA extends the ORCA framework by reformulating a system of linear equations for the non-induced case, covering graphlets up to size four. Three stages structure the computation: triangle counting, four-clique enumeration, and orbit solving. Stage-specific parallel strategies use thread and vertex-local memory to balance workload. Experiments on eight real-world datasets and on synthetic Erdős-Rényi graphs follow. A mixed mode with dynamic scheduling delivers consistent speedup, up to thirty times faster than sequential algorithms.

Catalog record

CREATORSyed Ibtisam Tauhidi, Arindam Karmakar, Thai Son Mai, Hans Vandierendonck
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE53 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.29651

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

NI-ORCA: A Parallel Algorithm for Counting the Orbits of Non-Induced Graphlets up to K 4 K_{4} Syed Ibtisam Tauhidi, Arindam Karmakar, Thai Son Mai, Hans Vandierendonck Abstract 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 Erdős–Rényi 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 30× speedups. K eywords graph algorithms, parallel algorithms, multicore processing, load balancing 1 Introduction Graphs, or networks, are ubiquitously used data structures in computer science, and are used to naturally represent data across a wide array of domains, including biology, astrophysics, cheminformatics, logistics, and social or computer networks [ 8 , 27 ] . A key task in graph analytics is understanding the structural role of individual vertices within the graph, characterising them using various descriptive parameters. To extract insights from such graph data, it is often necessary to describe the structure of a graph using various topological features. Prior studies have shown that analysing the global and local topology of graphs enables richer characterisation for tasks like classification, clustering, and similarity comparison [ 30 , 34 , 33 , 11 ] . One practical approach for this is counting the orbits of graphlets, which quantifies how frequently vertices participate in specific topological roles in the graph. Graphlets — also known as motifs — are small induced or non-induced subgraphs embedded within a larger graph [ 1 ] . However, motifs often denote the graphlets that occur more frequently (e.g., based on z-score or p-value) within a graph [ 17 , 13 ] . They capture recurring local patterns in graph topology and have been widely used in applications such as network comparison, node classification, clustering, anomaly detection, and biological function prediction. A closely related concept is that of the orbits of graphlets. Orbits are automorphic groups of vertices in a graphlet, i.e., vertices belonging to the same orbit can be mapped to one another in an isomorphism of a graphlet to itself [ 22 ] . Orbits capture the specific roles of vertices within these graphlets. Characterising a graph using orbit counts has several applications, such as role-based node analysis, machine learning, and network alignment and comparison [ 4 , 28 , 26 ] . Additionally, orbit-based features preserve fine-grained topological signatures while remaining computationally tractable for small graphlets. For these reasons, efficient and scalable algorithms for orbit counting have become a major area of interest. While several existing works focus on counting the orbits of induced graphlets, there is a gap in studying the algorithms for the scalable counting of orbits of non-induced graphlets. Algorithms like ORCA [ 6 ] , EVOKE [ 22 ] , and JESSE [ 18 ] are examples of the former. These methods use combinatorial techniques, graph decomposition, or equation systems to compute orbit counts, often avoiding full enumeration for efficiency. However, they are designed for counting the orbits of induced graphlets and are sequential. Many applications prefer the orbit count of non-induced graphlets instead. For example, non-induced graphlet orbits are crucial for analysing noisy or incomplete protein–protein interaction (PPI) networks, as they tolerate missing or spurious edges and still capture meaningful structural motifs. Unlike induced orbits, which require exact subgraph matches, non-induced orbits can reveal biologically relevant patterns even when some interactions are absent [ 14 ] . Furthermore, recent work has shown that using non-induced orbit counts can improve performance in algorithmic tasks such as subgraph isomorphism search by significantly pruning the search space [ 31 ] . Despite this, there has been a lack of exact, efficient and scalable algorithms for counting orbits of non-induced graphlets. To address these challenges, we propose NI-ORCA , an exact and parallel algorithm designed to count non-induced graphlet orbits up to size four ( K_{4} ). NI-ORCA builds on ORCA but introduces support for non-induced graphlets and leverages modern parallel architectures. At its core, the algorithm reuses the combinatorial equation framework from ORCA, but replaces the subtractive corrections required in the induced case. Both algorithms are structured into three stages. Stage I counts triangle participation for each edge. Stage II identifies 4-cliques ( K_{4} ) using efficient neighbourhood intersection techniques. Stage III computes the orbit counts for each vertex using a set of internal structural variables and a system of linear equations derived from local substructures. A major contribution of our work is the design of parallelisation strategies for each algorithm stage. While Stage I is trivially parallelisable, Stages II and III present significant challenges due to data dependencies and memory contention. We address these by introducing various thread-safe data structure designs, including per-thread and per-vertex arrays, unordered maps (UOM), and cache-friendly flat hash maps (FHM). We explore multiple configurations for these data structures to minimise contention and maximise memory locality. In particular, a hybrid MIXED mode — using thread-local FHM for Stage II and atomic arrays for Stage III — achieves the best performance in our evaluation. We also explore the impact of scheduling policies and chunk sizes in OpenMP-based execution. Our experiments show that dynamic scheduling with small chunk sizes provides the most consistent speedup and best load balancing across threads. We evaluate NI-ORCA on eight real-world networks ranging from small biological graphs like YEAST and HPRD to larger social and citation networks like YOUTUBE, EU2005, and PATENTS. Additionally, we generate synthetic Erdős–Rényi graphs with controlled density and size to study runtime characteristics in a more systematic manner. Our results demonstrate that the parallel NI-ORCA algorithm consistently outperforms state-of-the-art baselines in terms of speedup. Additionally, it demonstrates efficient scalability with increasing thread counts, on both AMD EPYC and Intel XEON multi-core, multi-socket shared-memory systems. The contributions of this paper are — 1. shows that induced orbit counting algorithms can be extended to non-induced orbits with low overhead, 2. introduces efficient, parallelisable strategies to accelerate computation, 3. demonstrates strong scalability and runtime performance across real-world and synthetic datasets. The rest of this paper is organised as follows. Section 2 reviews related work on graphlet and orbit counting algorithms. Section 3 defines graphlets and orbits. Section 4 details the original ORCA algorithm, followed by Section 5 , which presents the theoretical foundations and modifications required for NI-ORCA. Section 6 outlines the parallelisation techniques developed for each algorithm stage. Section

Read the complete text