DecoMine: A Compilation-Based Graph Pattern Mining System with Pattern Decomposition

Counting how many times a small shape appears inside a large graph is astronomically expensive — a graph of 7,000 vertices contains 71 billion five-node chains — and an algorithm published years earlier could do it roughly fifty times faster than the best general-purpose system, by cutting the shape into pieces, counting each piece, and MULTIPLYING rather than enumerating; yet no general system had adopted it, and this paper (Purdue) diagnoses exactly why not, finding three separate obstacles — the standard programming interface demands whole matches that the fast algorithm never builds, choosing where to cut is a decision no user can make and a bad choice is sixty times worse than a good one, and the cost model everyone used to make such choices was wrong by nineteen orders of magnitude on real graphs.

The argument in one glance

Problem

The counts are astronomical, and grow explosively with shape size

Graph pattern mining finds every subgraph of a large graph matching a small shape you specify. The output sizes are hard to believe: a graph with only 7,000 vertices contains 71 BILLION five-node chains. Finding all frequent three-edge shapes in a medium-sized social graph takes one recent system over 12 hours. The cost is driven by enumeration, and it grows rapidly as the shape gets bigger, so the honest summary of the field is that the interesting questions are the ones you cannot afford to ask.
What people did

Cut the shape into pieces, count each, and multiply

An algorithm called PATTERN DECOMPOSITION avoids most of the enumeration. Choose a small set of the shape's vertices whose removal splits it into disconnected pieces. Enumerate only the matches of that small CUT. Then, for each one, count how many ways each piece extends from it — and MULTIPLY those counts together. Since enumeration cost grows rapidly with size and the pieces are small, this is dramatically cheaper. It works: counting all five-node shapes in a small graph took the best general-purpose system 617 seconds, against 12.7 seconds for hand-written decomposition code.
Why it fell short

Three separate obstacles kept it out of every general system

The 48-times-faster algorithm had been published and still nobody could use it without writing bespoke code per shape. First, the standard interface hands each whole match to a user function — but decomposition never BUILDS a whole match, so honouring that interface erases the entire advantage. Second, where to cut is a real decision, made in the original work by hand complexity analysis per shape, and it matters enormously: the worst cut is over 60 times slower than the best, and a bad cut makes decomposition slower than not decomposing at all. Third, the cost model such a decision would need was, on real graphs, wrong by roughly nineteen orders of magnitude.
This paper's idea

Change the interface, generate the candidates, and fix the cost model

This paper (Purdue — Chen and Qian) removes each obstacle in turn. A PARTIAL-EMBEDDING interface hands user code the pieces rather than whole matches, with two guarantees that keep applications like frequent subgraph mining correct without ever materialising anything. A compiler generates candidate algorithms for every cut and every vertex ordering, and picks among them. And a new cost model estimates how many times a loop runs by APPROXIMATELY MINING the smaller shape that reaches that loop, sampling edges from the real graph rather than assuming a uniform random one. The result runs 4-motif counting on billion-edge graphs in under two hours where prior systems need tens, and finishes tasks that previously timed out after a week.

Why this problem is worth solving

The workload is unusual in that the answer is enormously larger than the question.

GRAPH PATTERN MINING takes a large input graph and a small PATTERN — a triangle, a five-node chain, a near-clique — and finds every subgraph matching it, each match called an EMBEDDING. The counts explode: 71 billion five-node chains live inside a graph of 7,000 vertices. Modern systems enumerate matches by nested loops, one loop per pattern vertex, extending a partial match one vertex at a time, and the cost of that grows rapidly as the pattern gets larger. PATTERN DECOMPOSITION sidesteps most of it. Pick a VERTEX CUTTING SET, a few pattern vertices whose removal leaves the rest in disconnected pieces. Enumerate matches of that small cut only. For each one, count how many ways each piece can extend from it, and MULTIPLY those counts — one multiplication standing in for enumerating every combination. Then subtract the cases where two pieces happened to pick the same graph vertex, which are counted by enumerating separate SHRINKAGE patterns

Choosing well requires predicting cost, and the standard way of doing that turns out to be badly broken.

Since enumeration is nested loops, predicting an implementation’s cost means predicting how many times each loop runs, which depends entirely on the input graph. The established model, from a prior compilation-based system, assumes a UNIFORM RANDOM graph: with a vertex count and a single connection probability, the loops run a predictable number of times. Applied to a real social graph of 4.8 million vertices, whose connection probability is about two in a million, this model estimates the total work of counting four-cliques at a number BELOW ONE. The graph actually contains 9.9 billion four-cliques, making the real work about 238 billion steps. The model is not merely imprecise — it predicts that an enormous computation is free, because real graphs are nothing like uniform random ones: connections cluster, and a few hub vertices carry disproportionate degree

What people did before, and where it broke

Enumerate everything and check. Early systems generate all subgraphs up to the pattern size and test each for a match. General and simple, but the isomorphism checks are expensive and the enumeration is total.
Use the pattern to guide the search. Recent systems build matches by construction with nested loops derived from the pattern, and add symmetry breaking so each match is found once. Far better, and the basis of every competitive system, including this one.
But the cost still grows explosively with pattern size. Measured here, one in-house implementation of the best compilation-based system fails to mine all six-node shapes in a graph of 7,000 vertices within a full week.
Hand-write the decomposition per shape. The algorithm exists and is much faster, but the published version supports only counting, only for patterns up to five vertices, and requires human complexity analysis to choose the cut.
Expose a low-level interface so experts can build it themselves. Some systems offer flexible primitives that can express decomposition. The authors’ objection is fair rather than dismissive: doing so by hand is almost the same work as writing the native algorithm for that specific shape, so the system adds little.
The gap. The algorithm was public, the speedup was known, and yet no general-purpose system had it. This paper’s contribution is diagnosing why — three obstacles that are not about the algorithm at all, but about the interface around it, the decision it demands of users, and the broken model any automatic decision would rest on.

How a known algorithm gets into a general system

Fix the interface, enumerate the choices, and predict cost by sampling the real graph

Enumerate matches with nested loops

Build matches one vertex at a time using loops derived from the pattern, intersecting neighbour sets at each level, with symmetry breaking so each match is produced once. This is what competitive systems do, and the cost grows rapidly with pattern size.
↓ →
Hand user code the pieces, not the whole match new

Replace the interface that delivers each complete match with one that delivers partial matches of the subpatterns, plus a count of how many whole matches each could expand into. Two guarantees make this sound: every partial match of a subpattern is delivered, and the subpatterns between them cover every pattern vertex.
↓ →
Generalise the algorithm beyond counting new

The published decomposition handles counting only, for patterns of at most five vertices. Extend it to arbitrary patterns and make it emit partial matches as it runs, so the new interface has something to deliver.
↓ →
Generate every candidate algorithm new

Enumerate all vertex subsets to find every cut that splits the pattern, and every ordering in which pattern vertices could be matched. Build a syntax tree of the algorithm each choice implies, then optimise each tree with standard compiler passes plus a rewriting step that recovers some of the symmetry breaking decomposition gives up.
↓ →
Predict each candidate cost by mining the graph approximately new

Estimate how many times a loop runs by the count of the smaller pattern that reaches that loop level. Get those counts by sampling a fixed number of edges from the real graph and running an approximate miner over the sample, storing the results in a table the compiler queries.
↓ →
Emit code for the winner, or decline new

Generate C++ for the lowest-cost candidate, parallelising the outermost loop with work stealing. If the model says no decomposition beats plain enumeration for this pattern and graph, fall back to plain enumeration.

About 10,000 lines of code, evaluated against seven prior systems on eight graphs from 4,500 to 1.8 billion edges, running motif counting, frequent subgraph mining and pseudo-clique counting on two 8-core Intel Xeon E5-2630 v3 processors.

The idea

The interface was the bottleneck, not the algorithm. This is the diagnosis that makes the paper, and it is easy to miss because interfaces are usually discussed as ergonomics rather than performance. Systems let users supply a function to run on each match found, which is what makes them general rather than mere counters. But decomposition works precisely by NEVER constructing a whole match — it counts pieces and multiplies. Honouring the conventional interface therefore means reassembling exactly the thing the algorithm was designed to avoid, which erases the advantage completely. The replacement hands user code the partial matches instead, along with how many whole matches each represents, and the authors identify the two properties that make this sufficient: every partial match of a subpattern must be delivered, and the subpatterns must jointly cover every pattern vertex — the second of which decomposition guarantees for free, since the pieces all share the cut. Frequent subgraph mining, which needs only to know which graph vertices map to which pattern vertices, works unchanged. Recognising that an abstraction is silently dictating an implementation strategy, and that relaxing it is the whole unlock, is the same the-interface-is-the-constraint move covered elsewhere on this site where what a system promises its callers turns out to determine what it can possibly do underneath.

A model can be wrong in a way that is not a matter of degree. The cost model question looks like tuning and is not. Assuming a uniform random graph, the established model estimates the work of counting four-cliques in a real social network at a number below one, when the true figure is around 238 billion steps. Real graphs cluster and have hubs; a single global connection probability describes nothing about them. The paper’s replacement is pleasingly self-referential: to estimate how many times a loop runs, estimate the COUNT OF THE PATTERN that reaches that loop level — so predicting the cost of mining is done by approximately mining. A fixed number of edges is sampled and a fast approximate miner produces relative counts of all small patterns, which the compiler then queries. Two details make it work. Edges are sampled rather than vertices, because sampling vertices would drop hubs while a hub survives if any one of its many edges is drawn. And the known bias of approximate mining — good on frequent patterns, underestimating rare ones — happens to point the right way, since frequent patterns are exactly the loops that run many times and dominate the runtime. Discovering that a long-accepted model does not describe the inputs it is applied to is the same check-the-model-against-reality lesson covered elsewhere on this site where a heuristic validated at one scale silently stops predicting anything at another.

The cost model’s job is as much to decline as to choose. Decomposition is not uniformly better, and the paper is careful about this. Some subpatterns turn out to be extremely common, so counting them costs more than enumerating the original pattern would have. Decomposition also gives up symmetry breaking, because two symmetric matches of a PIECE can extend into different matches of the whole, so suppressing one would undercount — a loss the compiler partially recovers with a rewriting pass worth up to 6.5 times. The consequence is that the cost model is not merely an optimiser but a safety mechanism, and the paper’s cleanest experiment shows both sides: given a perfect cost model, the non-decomposing system is still far slower, confirming the algorithm is where the win comes from; given a bad cost model, the decomposing system is slower than not decomposing at all, because it picks a bad cut. Building a search that can conclude the new technique should not be used here is the same know-when-to-fall-back discipline covered elsewhere on this site where a compiler estimates whether its own transformation pays and emits the ordinary version when it does not.

Counting a five-node shape without ever building one

The paper's own example, following one cut through to a count

A five-vertex pattern with vertices A to E. Numbers throughout are from the paper's evaluation.

Step 1 of 5

Find a cut that splits the shape

Look for a set of pattern vertices whose removal leaves the rest disconnected. Here removing A, B and D separates C from E. Merging the cut back with each leftover piece gives two subpatterns: one on A, B, D and E, the other on A, B, C and D. Both are smaller than the original, and both contain the cut.

a clique has no such cut, since removing any vertices leaves the rest connected, so cliques get no benefit at all from this technique
counting cliques is comparatively cheap and rarely the bottleneck, which is why that exclusion costs little in practice

Why it works

Enumeration cost grows rapidly with pattern size, and a cut is smaller than the whole → only the cut is enumerated, with the rest handled by counting and multiplication → so the advantage grows with pattern size, reaching 827 times over a strong baseline and finishing tasks that otherwise time out after a week.
The new interface delivers pieces rather than whole matches → applications never force the system to reassemble what it deliberately avoided building → so frequent subgraph mining, which only needs vertex mappings, keeps the full algorithmic advantage.
Every cut and every vertex ordering becomes a generated candidate → the choice that previously required hand complexity analysis becomes a search → removing the reason the algorithm was confined to bespoke implementations.
Loop iteration counts are estimated by approximately mining the smaller pattern that reaches each loop → the estimate reflects the real graph’s clustering and hubs → improving selected-implementation performance by up to 62 times over the uniform-random-graph model.
Sampling draws edges rather than vertices, and approximate mining is most accurate on frequent patterns → hubs survive sampling and the dominant loops are the well-estimated ones → so a 7-second profile suffices regardless of graph size.

What it costs (trade-offs and scope)

It can be slower, and needs the cost model to prevent that. Some subpatterns are more common than the original pattern, and decomposition also forfeits symmetry breaking. With a poor cost model the system is measurably slower than not decomposing at all.
Cliques get nothing. A clique has no cutting set, so the technique does not apply. The authors argue this matters little since clique counting is comparatively cheap, which is fair but is a real gap.
Applications needing whole matches fall back. Anything that fundamentally requires complete materialisation — writing every match to disk, say — gets no benefit and performs like existing systems.
The gains depend on the shape of the workload. On frequent subgraph mining the speedup peaks around 70 times at a middling threshold and collapses at both extremes: at high thresholds nearly everything is filtered out, and at low ones the cost is dominated by per-pattern overhead that decomposition cannot touch.
The headline win is not the paper’s own invention. The authors state plainly that the drastic improvements come primarily from the better algorithm, which was published earlier; their contribution is making it usable, which their own ablation confirms by showing a perfect cost model cannot rescue the alternative.

The evaluation

Comparison covers seven prior systems across eight graphs, from CiteSeer at 4,500 edges to Friendster at 1.8 billion, on motif counting, frequent subgraph mining and pseudo-clique counting. The baseline deserves note: since the strongest compilation-based competitor is not open source, the authors reimplemented it with all its optimisations and verified their version is faster than the published numbers in nearly every case, so the comparison is against a strengthened rather than a weakened opponent. Timeouts are set at 12 hours. Everything runs on a single node of two 8-core processors, except two distributed systems given an entire 8-node cluster.

Counting occurrences of a shape in a large graph

Property	Enumerate all subgraphs and check	Pattern-guided enumeration	Decompose, count pieces, multiply
What gets enumerated
Effect of a larger pattern
Choosing the implementation
What user code receives
Four-motif counting on 1.8 billion edges

Speedups reach 827 times over a strengthened reimplementation of the best compilation-based system, 575 times over Peregrine and far more over systems that materialise everything. Eight-node cycle counting on a small graph takes 5.7 hours against 5.6 days and 2.8 days for two competitors; seven-node cycles on another take 4.8 hours against more than a week. The better cost model alone is worth up to 62 times, the loop-rewriting pass up to 6.5 times, and compiling 112 six-node patterns takes under 300 milliseconds.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The authors are unusually direct that the headline speedups are not theirs: the drastic improvements come primarily from an algorithm published earlier, and their contribution is removing the three obstacles that kept it out of general systems. Their own ablation makes this precise in both directions — given a perfect cost model the non-decomposing system remains far slower, so the algorithm is genuinely the source of the win; but given a poor cost model the decomposing system is slower than not decomposing at all, because it selects a bad cut. That second half is the real caveat: this technique has no guaranteed benefit. Some subpatterns are more frequent than the original pattern, and decomposition forfeits symmetry breaking, since two symmetric matches of a piece can extend into different whole matches so suppressing one would undercount — a loss only partially recovered by a rewriting pass. Cliques are excluded outright, having no cutting set, which the authors reasonably note matters little because clique counting is cheap. Applications that fundamentally need whole matches materialised, such as writing every match to disk, fall back to ordinary performance. And the gains are workload-shaped: on frequent subgraph mining the speedup peaks near 70 times at a middling threshold and vanishes at both extremes, since high thresholds filter nearly everything away and low ones leave the cost dominated by per-pattern overhead this technique cannot touch. Worth crediting on the other side: the strongest baseline was reimplemented by the authors and verified faster than its published numbers, and a competing GPU system is acknowledged as performance-competitive before noting it costs six times more and cannot handle the large cases.

Background

When the interface, not the algorithm, is what stands in the way

This paper sits in the site’s graph processing and compilers clusters and rhymes with several ideas covered elsewhere on this site. It is a direct sibling of the distributed graph-mining page, from the same authors on the same workload, attacking a complementary layer — that paper rebuilt the execution engine while this one rebuilds the algorithm and the compiler around it, and both reach their result by identifying that the accepted framing rather than the raw machinery was the obstacle. Its central diagnosis, that an interface promising whole matches silently forbids the fast algorithm, is the same the-abstraction-is-the-constraint observation the accelerator and dynamic-shape pages make when what a system commits to its callers determines what it can do underneath. Its cost model story belongs firmly with the microservice-debugging and instruction-prefetching pages: a model everyone accepted stopped describing the inputs it was applied to, here by nineteen orders of magnitude, because real graphs cluster and have hubs while the model assumed uniform randomness — and the same power-law concentration is why the fix samples edges rather than vertices, so hubs survive. Its compiler structure, generating candidates and scoring them with an analytic model cheap enough to run at build time while retaining the option to decline and emit the ordinary version, is precisely the shape of the dynamic-shape compilation page.

If you remember only three things

1. Graph pattern mining produces astronomical output — 71 billion five-node chains inside a graph of 7,000 vertices — and cost grows rapidly with pattern size. An algorithm called pattern decomposition largely avoids this: cut the pattern at a few vertices so the rest falls into disconnected pieces, enumerate only matches of that small cut, then for each one count how many ways each piece extends and MULTIPLY. One multiplication replaces enumerating every combination, with over-counts corrected by separately counting the cases where two pieces landed on the same vertex. It was roughly 48 times faster than the best general system, and had been published years earlier.
2. The paper is a diagnosis of why nobody could use it. The standard interface hands each whole match to user code, but decomposition never builds a whole match — honouring the interface means reassembling exactly what the algorithm exists to avoid. Choosing where to cut required hand complexity analysis and matters enormously, the worst choice being over 60 times slower than the best. And the cost model any automatic choice would rest on assumed a uniform random graph, estimating the work of counting four-cliques in a real social network at a number below one when the truth is around 238 billion steps.
3. Each obstacle gets a targeted fix: an interface delivering partial matches plus an expansion count, sound under two stated properties; a compiler generating a candidate for every cut and vertex ordering; and a cost model that estimates a loop iteration count by approximately mining the smaller pattern reaching that loop, sampling edges so hubs survive. Four-motif counting on 1.8 billion edges drops from tens of hours to 1.4; eight-node cycles take 5.7 hours against 5.6 days. Reported honestly: the algorithm is not the authors' invention, and with a poor cost model their system is slower than not decomposing at all.

Check yourself

Check your understanding

1. The programming interface a mining system offers is normally an ergonomics question. Here it is described as the first obstacle to a 48-times speedup. Predict why.
2. The established cost model estimates the work of counting four-cliques in a real social graph at a number below one, when the actual work is around 238 billion steps. Predict what assumption fails.
3. The replacement cost model estimates how many times a loop runs by approximately mining the input graph. Predict why sampling EDGES rather than vertices matters, and why the sampler known inaccuracy is tolerable.
4. The technique gives no benefit at all on cliques, while its advantage grows as patterns get larger. Predict what single property explains both.

Sources

DecoMine: A Compilation-Based Graph Pattern Mining System with Pattern Decomposition (ACM Digital Library, DOI 10.1145/3567955.3567956) — ASPLOS 2023; the full 15-page paper, read in full for this explainer. Published open access under a Creative Commons licence.