Contigra: Graph Mining with Containment Constraints

While graph mining systems employ efficient task-parallel strategies to quickly explore subgraphs of interest (or matches), they remain oblivious to containment constraints like maximality and minimality, resulting in expensive constraint checking on every explored match as well as redundant explorations that limit their scalability.

In this paper, we develop Contigra for efficient graph mining with containment constraints. We first model the impact of constraints in terms of dependencies across exploration tasks, and then exploit the dependencies to develop: (a) task fusion that merges correlated tasks to increase cache reuse; (b) task promotion that allows explorations to continue from available subgraphs and skip re-exploring subgraphs from scratch; (c) task cancelations that avoid unnecessary constraint checking and prioritizes faster constraint validations; and (d) task skipping that safely skips certain exploration and validation tasks. Experimental results show that Contigra scale to graph mining workloads with containment constraints, which could not be handled by existing state-of-the-art systems.