UC Riverside

Graph search algorithms have become an important area of research in recent years to handle increasingly larger real-world networks using state-of-the-art platforms and techniques. Subgraph isomorphism (SI) search is one such algorithm that is actively being studied: given both query and data graphs, return all subgraphs of the data graph that are isomorphic to the query. Multi-query optimization (MQO) is an extension of SI to support multiple queries efficiently and concurrently, which utilizes commonalities between queries for faster results vs. one-query-at-a-time. In the past decade, the graphics processing unit (GPU) has become an attractive platform to run general-purpose parallel algorithms in single-instruction multiple data (SIMD) fashion. However, problems with current GPU-based solutions that inhibit high-throughput performance include (1) potential extraneous computations, (2) large amounts of intermediate data generated on the device, and (3) lack of support for multi-query optimization.

First, we present G-Morph, a GPU-based subgraph isomorphism search system that introduces a vertex filtering technique using a vertex signature (LOC and TRI) to address the problem of potential extraneous computations by pruning a vast amount of solution paths upfront. In addition to our vertex signature, we support induced matches and introduce the slide-join algorithm to build candidate edges in parts on the GPU through use of a threshold to further limit extraneous computations; split-scan is used to perform exclusive prefix sum operations. G-Morph outperforms the state-of-the-art GPU-based GSI and CPU-based VF3 systems on labeled real-world graphs achieving speedups of up to 15.78x and 43.56x respectively.

Second, we present SymLimit, a GPU-based symmetry-breaking technique that calculates automorphisms and orbits of the input query graph to calculate a sufficient join order and calculate symmetry-breaking conditions to address the problem of large amounts of intermediate data generated by the SI algorithm. We implement our technique as an update to G-Morph using a symmetry-breaking conditions shared memory lookup table for efficient application of conditions; we also propose an algorithm for finding structural equivalence classes (SEC) on the GPU to logically combine equivalent query vertices that outperforms another algorithm (up to 65x). Our experiments show large intermediate data reduction (75.5% on average) and speedups (up to 5x).

Last, we present OneMoreQuery, a GPU-based multi-query optimization technique that efficiently processes multiple input query graphs by computing the maximum common induced subgraph (MCIS) among query graph pairs, grouping each MCIS by its minimum DFS code, and computing the optimal query plan using GPU-accelerated cost-estimation. Our technique assigns workloads to multiple GPUs while caching MCIS results. To support multi-query symmetry-breaking, we propose a technique that enumerates MCIS results then filters (via parallel scan) per query by applying conditions. Our experiments show SI speedups (up to 10.3x) against state-of-the-art GPU-based EGSM in multi-GPU mode and core functionality acceleration with speedups (up to 7.2x).