Subgraph matching answers a deceptively simple question — where does this small pattern appear inside this huge graph? — and it is NP-hard, which is why the state of the art matters. DAF, from the SIGMOD 2019 paper Efficient Subgraph Matching: Harmonizing Dynamic Programming with Backtracking, was that state of the art — published as a sequential C++ program. My B.S. thesis asked what it takes to make it run on a cluster.
What I built
- The full three-phase DAF pipeline in Scala on Apache Spark GraphX, finding every embedding of a labeled query graph inside a labeled base graph
- Phase one, DAG construction — a degree-aware heuristic roots the query at its most constrained vertex, then BFS orients the graph
- Phase two, candidate space — the base graph is cut down to label-compatible vertices and edges, then refined with alternating forward and backward sweeps until nothing more can be pruned
- Phase three, backtracking — recursive enumeration over the refined space in BFS order, with a visited set guarding against double-mapping
Why it was hard
The original algorithm is sequential and pointer-heavy; GraphX wants immutable, partitioned graph transformations. Most of the thesis was reshaping one into the other — the same embeddings the reference implementation finds, produced by distributed operations instead of pointers.