Doctoral Showcase Archive

Subgraph Counting: Methods, Frameworks, and Applications


Author: Ali Khan (University of North Texas)

Advisor: Sanjukta Bhowmick (University of North Texas)

Abstract: Subgraph counting and matching are core primitives in network analysis, underpinning applications from computational biology to fraud detection to performance analysis in HPC. Existing methods assume static, small networks, rely on hardware-specific kernels that do not scale across the accelerator ecosystem, and emphasize counting over the harder problem of locating pattern instances. This dissertation addresses all three.

We develop ParaDyMS, a parallel method for counting all motifs of size k ≤ 5 on fully dynamic networks under batched edge insertions and deletions. Rather than recomputing from scratch, ParaDyMS updates motif counts incrementally using only the delta induced by a batch of changes. Implemented in the Kokkos C++ Performance Portability ecosystem, ParaDyMS targets both OpenMP and CUDA from one source, achieving up to 124× speedup over the state-of-the-art static method and outperforming 112 CPU cores with a single GPU.

To address hardware portability, we present PyGB-LAPIS, a compilation pipeline lowering graph algorithms written in Python-GraphBLAS through MLIR and the LAPIS backend into Kokkos-flavored C++. PyGB-LAPIS generates kernels across five sparse storage formats and multiple hardware backends from one source, matching hand-written Kokkos performance while eliminating per-backend engineering effort.

Finally, we develop an exact subgraph matching method that decomposes query and host graphs into size-4 graphlets and searches a compressed graphlet-overlap representation. This supports arbitrary-size queries and, uniquely, resolves multiple simultaneous queries in one pass through a shared search tree rather than restarting per query, with the union graph traversed on the fly and pruned by graphlet frequency to control its size.


Thesis Canvas: pdf



Back to Doctoral Showcase Archive Listing