HiPerMotif: Novel Parallel Subgraph Isomorphism in Large-Scale Property Graphs

Mohammad Dindoost, Oliver Alvarado Rodriguez, Bartosz Bryg, Ioannis Koutis, and David A. Bader · 2025

Read HiPerMotif: Novel Parallel Subgraph Isomorphism in Large-Scale Property Graphs by Mohammad Dindoost, Oliver Alvarado Rodriguez, Bartosz Bryg, Ioannis Koutis, and David A. Bader (2025) 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-2507-04130.txt.

Introduction

Dindoost and co-authors introduce in 2025 HiPerMotif, a parallel algorithm for finding pattern subgraphs inside huge property graphs. Such search matters in neuroscience, systems biology, and social network analysis. Classic methods grow matches vertex by vertex from empty, which wastes early search with little pruning.

Their method reorders the pattern to start from high degree vertices, then maps the first edge everywhere it could fit. Validated partial matches are injected at depth two, skipping the costly early tree. Vertex and edge checks exploit the rich attributes of property graphs. The build runs in an open source framework, with reordering alone worth up to five fold speed.

Catalog record

CREATORMohammad Dindoost, Oliver Alvarado Rodriguez, Bartosz Bryg, Ioannis Koutis, and David A. Bader
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-04130

Browse the full library · About the Tower of Babel

Full text

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

HiPerMotif: Novel Parallel Subgraph Isomorphism in Large-Scale Property Graphs Mohammad Dindoost, Oliver Alvarado Rodriguez, Bartosz Bryg, Ioannis Koutis, and David A. Bader Abstract Subgraph isomorphism, essential for pattern detection in large-scale graphs, faces scalability challenges in attribute-rich property graphs used in neuroscience, systems biology, and social network analysis. Traditional algorithms explore search spaces vertex-by-vertex from empty mappings, leading to extensive early-stage exploration with limited pruning opportunities. We introduce HiPerMotif, a novel hybrid parallel algorithm that fundamentally shifts the search initialization strategy. After structurally reordering the pattern graph to prioritize high-degree vertices, HiPerMotif systematically identifies all possible mappings for the first edge (vertices 0,1) in the target graph, validates these edge candidates using efficient vertex and edge validators, and injects the validated partial mappings as states at depth 2. The algorithm then continues with traditional vertex-by-vertex exploration from these pre-validated starting points, effectively pruning the expensive early search tree branches while enabling natural parallelization over edge candidates. Our contributions include the edge-centric initialization paradigm with state injection, a structural reordering strategy achieving up to 5× speedup, rapid edge and vertex validators for attribute-rich graphs, and efficient parallel enumeration over target graph edges. Implemented in the open-source Arachne framework, HiPerMotif achieves up to 66× speedup over state-of-the-art baselines (VF2-PS, VF3P, Glasgow) on diverse datasets where baselines successfully complete execution. Additionally, HiPerMotif successfully processes massive datasets such as the H01 connectome with 147 million edges, which existing methods cannot handle due to memory constraints. Comprehensive evaluation across synthetic and real-world graphs demonstrates HiPerMotif’s scalability, enabling advanced analysis in computational neuroscience and beyond. I Introduction Subgraph isomorphism and monomorphism, critical for detecting patterns in large-scale graphs, underpin discoveries in neuroscience [ 1 , 2 ] , systems biology [ 3 , 4 ] , social network analysis [ 5 , 6 ] , and cybersecurity [ 7 , 8 ] . Recurring substructures, or motifs, reveal network organization and function through tasks like motif detection and network similarity analysis [ 9 , 10 ] . Analyzing massive graphs with millions of edges demands scalable, expressive tools. Traditional adjacency-based representations fail to capture domain-specific semantics (e.g., neuron types, protein interactions), necessitating property graphs [ 11 , 12 ] that support multiple vertex and edge properties, significantly increasing computational complexity. Traditional subgraph matching algorithms follow a vertex-centric approach, starting from empty mappings and incrementally building partial solutions vertex-by-vertex through recursive backtracking. This strategy requires extensive exploration of early search tree levels, where pruning opportunities are limited and parallel efficiency is constrained by sequential vertex ordering decisions. Existing algorithms struggle with five fundamental challenges: (1) inefficient candidate generation producing large search spaces; (2) rigid vertex-ordering heuristics that overlook graph structure; (3) high memory overhead in tracking candidate sets; (4) limited parallelization opportunities in early tree-search stages; and (5) unnecessary exhaustive enumeration despite applications often needing partial results. These limitations become critical in applications like connectome motif detection, where graphs exceed 100 million edges. We propose HiPerMotif, a hybrid algorithm that fundamentally changes the search initialization strategy while preserving the benefits of established tree-search methods. After structurally reordering the pattern graph to prioritize high-degree vertices, HiPerMotif systematically identifies all possible mappings for the first edge (vertices 0,1) in the target graph. Instead of exploring vertex assignments sequentially from empty states, the algorithm validates these edge candidates using efficient vertex and edge validators, then injects the validated partial mappings as states at depth 2 into traditional vertex-by-vertex search. This approach eliminates the expensive early search tree exploration (depths 0-1) while enabling natural parallelization over edge candidates rather than search tree branches. Implemented in the open-source Arachne framework, HiPerMotif achieves up to 66 \times speedup over state-of-the-art baselines (VF2-PS, VF3P, Glasgow) and successfully processes massive datasets, such as the H01 connectome [ 13 ] , that cause existing methods to fail due to memory constraints. The main contributions of this paper are: 1. A hybrid algorithmic paradigm that systematically validates all edge mappings for the first edge and injects partial states at depth 2, eliminating costly early search tree exploration while preserving traditional vertex-by-vertex efficiency. 2. A structural reordering strategy that prioritizes high-degree vertices to identify the optimal starting edge, achieving up to 5 \times speedup in search initiation. 3. Efficient vertex and edge validators that rapidly prune infeasible edge candidates before state injection, reducing computational overhead in attribute-rich property graphs. 4. A parallel edge enumeration framework within the open-source Arachne framework, enabling scalable analysis of previously intractable large-scale property graphs. Comprehensive evaluation on synthetic and real-world graphs demonstrates HiPerMotif’s scalability across diverse domains, from computational neuroscience to social network analysis. The rest of this paper is organized as follows: Section II reviews related work, Section III presents HiPerMotif algorithms and Arachne implementation, Section IV evaluates performance on synthetic and real-world graphs, and Section V concludes with future directions. II Background and Preliminaries II-A Subgraph Isomorphism and Monomorphism Subgraph isomorphism and monomorphism are fundamental problems in graph theory, with applications in neuroscience, systems biology, social network analysis, and cybersecurity [ 14 , 15 , 7 ] . Given graphs G_{1}=(V_{1},E_{1}) and G_{2}=(V_{2},E_{2}) with vertex labels \alpha_{i}:V_{i}\rightarrow L_{V} and edge labels \beta_{i}:E_{i}\rightarrow L_{E} , subgraph isomorphism seeks an injective function f:V_{1}\rightarrow V_{2} such that: \displaystyle\forall u,v\in V_{1} \displaystyle:\ (u,v)\in E_{1} \displaystyle\Leftrightarrow(f(u),f(v))\in E_{2}, (1) \displaystyle\forall v\in V_{1} \displaystyle:\ \alpha_{1}(v) \displaystyle=\alpha_{2}(f(v)), (2) \displaystyle\forall(u,v)\in E_{1} \displaystyle:\ \beta_{1}(u,v) \displaystyle=\beta_{2}(f(u),f(v)). (3) Subgraph monomorphism relaxes the edge constraint to (u,v)\in E_{1}\Rightarrow(f(u),f(v))\in E_{2} . Both problems are NP-complete, with worst-case complexity O(|V_{2}|^{|V_{1}|}) [ 16 ] . Property graphs [ 11 ] , supporting vertex and edge attributes, increase computational demands. II-B Tree-Search and Parallel Algorithms Tree-search algorithms dominate exact subgraph matching, using recursive backtracking to explore partial vertex mappings [ 17 ] . VF2 introduced frontier sets for pruning infeasible branches [ 18 ] , while VF3 improved data structures for dense graphs [ 19 ] . The Glasgow Subgraph Solver employs constraint programming and conflict-directed backjumping [ 20 ] , and LAD uses arc consistency preprocessing [ 21 ] . Recent methods like DP-iso [ 22 ] and VEQ [ 23 ] optimize backtracking with failing sets and dynamic equivalence classes, respectively. Variable ordering significantly impacts tree-search efficiency [ 24 ] . Static strategies, like RI’s high-degree vertex selection [ 25 ] , precompute sequences, while dynamic methods, like DP-iso, adapt during search [ 22 ] . Techniques such as CFL’s core-forest-leaf decomposition enhance pruning by delaying leaf matching [ 26 ] . Parallel implementations address scalability on multi-core architectures. VF3P uses state cloning for near-linear scaling up to 16 cores [ 27 ] , while SLF’s “Ask for Sharing” and “Low-depth Priority Sharing” reduce synchronization overhead [ 28 ] . Glasgow integrates parallel backjumping with low-overhead synchronization [ 20 ] . Dense graphs benefit more from parallelization due to larger search trees, but synchronization limits scalability beyond moderate core counts [ 27 ] . Index-based methods (e.g., FG-index [ 29 ] ) preprocess graphs for rapid filtering but incur high memory overhead, limiting scalability for large, attribute-rich graphs [ 30 ] . GPU-accelerated approaches like GSI [ 31 ] leverage parallelism but struggle with irregular memory access [ 32 ] . II-C VF2-PS: Our Enhanced Baseline Building upon VF2’s foundation, our previous VF2-PS algorithm [ 33

Read the complete text