Amir Mehrafsa

Topic

Vectorising the Nucleus Hierarchy: Flat-Array Primitives for Data-Parallel Dense Subgraph Discovery

Department of Computer Science

Date & location

• Tuesday, August 18, 2026
• 9:00 A.M.
• Virtual Defence

Examining Committee

Supervisory Committee

• Dr. Alex Thomo, Department of Computer Science, University of Victoria (Co-Supervisor)
• Dr. Sean Chester, Department of Computer Science, UVic (Co-Supervisor)
• Dr. Amirali Baniasadi, Department of Electrical and Computer Engineering, UVic (Outside Member)

External Examiner

• Dr. Farzad Ghayoor, AMI Smart Grid Senior Firmware Engineer, Corinex Communications

Chair of Oral Examination

• Dr. Jon Noel, Department of Mathematics and Statistics, UVic

Abstract

Dense subgraph discovery is a cornerstone of graph analytics, underpinning com munity detection, anomaly and fraud detection, and network visualisation. Nucleus decomposition unifies the most widely used cohesive-subgraph models. It measures the density of one clique by the number of larger cliques that contain it, so that the 𝑘-core is the (1,2)-nucleus, the 𝑘-truss is the (2,3)-nucleus, and the (3,4)-nucleus gives a finer and more cohesive hierarchy. Computing these decompositions is expen sive, and the standard peeling algorithm that produces them is hard to accelerate. Its pointer-chasing, irregular memory access and tightly synchronised updates map poorly onto the wide, data-parallel hardware (multi-core SIMD units and GPUs) that now dominates computing.

This dissertation develops a single idea across the nucleus hierarchy. Peeling and the clique enumeration it depends on can be re-expressed as a small set of primitives over flat, one-dimensional arrays, after which highly optimised vector libraries and GPUs provide parallelism at low cost. We develop this thesis in three parts. First, we vectorise 𝑘-core decomposition, recasting peeling as a composition of array primitives. These include a reusable multi-arange operation for gathering neighbourhoods, and we obtain 4–8× speed-ups over state-of-the-art multi-core C++ on a single moderate GPU. Second, rather than re-enter the already-saturated field of GPU truss acceleration, we carry the approach to 𝑘-truss decomposition using only the ubiqui tous NumPy library together with Cantor pairing and Cuckoo hashing. This secures multi-core and SIMD parallelism without any low-level parallel programming, and shows that the same formulation needs neither a GPU nor C++. Third, we close a standing gap with the first GPU algorithm for (3,4)-nucleus decomposition. A clique reduction primitive removes the recursion in clique enumeration and linearises every intermediate structure into edge, degree, and offset arrays, with provable linearisability, composability, and partitionability. Against the parallel CPU state of the art, our CUDA implementation attains wall-time speed-ups of up to two orders of magnitude, while its flat-array layout lets the bandwidth-bound peeling phase stream four to six times fewer bytes per element. Together, the three results show that vectorization and clique reduction make scalable, higher-order dense-subgraph analytics both faster and more accessible.