Chapter 4

Pattern Matching in large Graph Transformation Systems

To our knowledge, the first practical proposal for a GTS-based quantum compiler was presented in Xu, 2022Mingkuan Xu, Zikun Li, Oded Padon, Sina Lin, Jessica Pointing, Auguste Hirth, Henry Ma, Jens Palsberg, Alex Aiken, Umut A. Acar and Zhihao Jia. 2022. Quartz: Superoptimization of Quantum Circuits. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation, June 2022. Association for Computing Machinery, 625--640. doi: 10.1145/3519939.3523433 and then refined in Xu, 2023Amanda Xu, Abtin Molavi, Lauren Pick, Swamit Tannu and Aws Albarghouthi. 2023. Synthesizing Quantum-Circuit Optimizers. Proceedings of the ACM on Programming Languages 7, PLDI (June 2023, 835--859). doi: 10.1145/3591254. In these, the set of possible graph transformations is obtained by exhaustive enumeration. Using SAT solvers and fingerprinting techniques, the set of all small programs up to a certain size can be generated ahead of time and clustered into disjoint partitions of equivalent programs. This concisely expresses every possible peephole optimisation up to the specified size: for every small enough subset of operations of an input program, its equivalence class can be determined. Any replacement of that set of operations with another program in the same equivalence class is a valid transformation and, thus, a potential peephole optimisation. Transformation systems on minIR graphs based on equivalence classes were formalised in section 3.4.

First results of this approach are promising. Xu, 2022Mingkuan Xu, Zikun Li, Oded Padon, Sina Lin, Jessica Pointing, Auguste Hirth, Henry Ma, Jens Palsberg, Alex Aiken, Umut A. Acar and Zhihao Jia. 2022. Quartz: Superoptimization of Quantum Circuits. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation, June 2022. Association for Computing Machinery, 625--640. doi: 10.1145/3519939.3523433 demonstrated that optimisation performance improves markedly with larger sets of transformation rules. Such workloads however rely heavily on pattern matching, the computational task that identifies subgraphs on which transformation rules apply. In Xu, 2022Mingkuan Xu, Zikun Li, Oded Padon, Sina Lin, Jessica Pointing, Auguste Hirth, Henry Ma, Jens Palsberg, Alex Aiken, Umut A. Acar and Zhihao Jia. 2022. Quartz: Superoptimization of Quantum Circuits. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation, June 2022. Association for Computing Machinery, 625--640. doi: 10.1145/3519939.3523433 and Xu, 2023Amanda Xu, Abtin Molavi, Lauren Pick, Swamit Tannu and Aws Albarghouthi. 2023. Synthesizing Quantum-Circuit Optimizers. Proceedings of the ACM on Programming Languages 7, PLDI (June 2023, 835--859). doi: 10.1145/3591254, pattern matching is carried out separately for each pattern. This becomes a significant bottleneck for large rule sets. In Xu, 2022Mingkuan Xu, Zikun Li, Oded Padon, Sina Lin, Jessica Pointing, Auguste Hirth, Henry Ma, Jens Palsberg, Alex Aiken, Umut A. Acar and Zhihao Jia. 2022. Quartz: Superoptimization of Quantum Circuits. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation, June 2022. Association for Computing Machinery, 625--640. doi: 10.1145/3519939.3523433, performance peaks at around 50,000 transformation rules, after which the additional overhead from pattern matching becomes dominant, deteriorating the compilation results.

In this chapter, we solve these scaling difficulties by presenting an algorithm for pattern matching on minIR graphs that uses a pre-computed data structure to return all pattern matches in a single query. The set of transformation rules is directly encoded in this data structure. After a one-time cost for construction, pattern-matching queries can be answered in running time independent of the number of rules in the transformation system.

The asymptotic complexity results presented in this chapter depend on some simplifying assumptions on the properties that the pattern graphs and embeddings must satisfy. This represents a restriction on the generality of minIR graphs, but we do not find that they restrict the usefulness of the result in practice. As discussed in section 4.7, none of these assumptions are required in practice for the implementation. We have not observed any impact on performance when the imposed constraints are lifted, so we conjecture that at least some of these assumptions can be relaxed and our results generalised.

After a discussion of related work in section 4.1, Section 4.2 presents the assumptions that we are making in detail, along with some relevant definitions for the rest of the chapter. Sections 4.3, 4.4, and 4.5 present the core ideas of our approach, respectively introducing: a reduction of minIR graphs to equivalent trees, a canonical construction for the tree reduction and an efficient way to enumerate all possible subtrees of a graph. We also prove bounds on the size and number of the resulting trees.

In section 4.6, we introduce a pre-computation step and show that the pattern-matching problem reduced to tree structures can be solved using a prefix tree-like automaton that is fixed and pre-computed for a given set of patterns. Combining the automaton construction with bounds from section 4.5 leads to the final result. We conclude in section 4.7 with benchmarks on a real-world dataset of 10000 quantum circuits, obtaining a 20x speedup over a leading C++ implementation of pattern matching for quantum circuits.

4.1. Related work

Our proposed solution can be seen as a specialisation of RETE networks Forgy, 1982Charles L. Forgy. 1982. Rete: A fast algorithm for the many pattern/many object pattern match problem. Artificial Intelligence 19, 1 (Septempter 1982, 17--37). doi: 10.1016/0004-3702(82)90020-0 Varró, 2013Gergely Varró and Frederik Deckwerth. 2013. A Rete Network Construction Algorithm for Incremental Pattern Matching and derivatives Ian, 2003Wright Ian and James A. R. Marshall. 2003. The execution kernel of RC++: RETE*, a faster RETE with TREAT as a special case. International Journal of Intelligent Games and Simulation 2, 1 (Feb 2003, 36-48) Armstr., 2014Dylan Armstrong. 2014. Memory Efficient Stream Reasoning onResource-Limited Devices Mirank., 1987D. P. Miranker. 1987. TREAT: a new and efficient match algorithm for AI production systems to the case of graph pattern matching. The additional structure obtained from restricting our considerations to graphs results in a simplified network design that allows us to derive worst-case asymptotic runtime and space bounds that are polynomial in the parameters relevant to our use case¹ – overcoming a key limitation of RETE.

Another well-studied application of large-scale pattern matching is in the context of stochastic biomolecular simulations Sneddon, 2010Michael W Sneddon, James R Faeder and Thierry Emonet. 2010. Efficient modeling, simulation and coarse-graining of biological complexity with NFsim. Nature Methods 8, 2 (December 2010, 177--183). doi: 10.1038/nmeth.1546 Bachman, 2011John A Bachman and Peter Sorger. 2011. New approaches to modeling complex biochemistry. Nature Methods 8, 2 (January 2011, 130--131). doi: 10.1038/nmeth0211-130, particularly the Kappa project Danos, 2004Vincent Danos and Cosimo Laneve. 2004. Formal molecular biology. Theoretical Computer Science 325, 1 (Septempter 2004, 69--110). doi: 10.1016/j.tcs.2004.03.065. Stochastic simulations depend on performing many rounds of fast pattern-matching for continuous Monte Carlo simulations Yang, 2008Jin Yang, Michael I. Monine, James R. Faeder and William S. Hlavacek. 2008. Kinetic Monte Carlo method for rule-based modeling of biochemical networks. Physical Review E 78, 3 (Septempter 2008, 031910). doi: 10.1103/physreve.78.031910. However, unlike our use case, the procedure typically does not need to scale well to a large number of patterns. In Danos, 2007Vincent Danos, Jérôme Feret, Walter Fontana and Jean Krivine. 2007. Scalable Simulation of Cellular Signaling Networks, Danos et al. introduced a pre-computation step to accelerate matching by establishing relations between patterns that activate or inhibit further patterns. This idea was later expanded upon and formalised in categorical language in Boutil., 2017Pierre Boutillier, Thomas Ehrhard and Jean Krivine. 2017. Incremental Update for Graph Rewriting. The ideas presented in Boutil., 2017Pierre Boutillier, Thomas Ehrhard and Jean Krivine. 2017. Incremental Update for Graph Rewriting are similar to ours; their formalism has the advantage of being more general but does not present any asymptotic complexity bounds and suffers from similar worst-case complexities as RETE.

A similar problem has also been studied in the context of multiple-query optimisation for database queries Sellis, 1988Timos K. Sellis. 1988. Multiple-query optimization. ACM Transactions on Database Systems 13, 1 (March 1988, 23–52). doi: 10.1145/42201.42203 Ren, 2016Xuguang Ren and Junhu Wang. 2016. Multi-Query Optimization for Subgraph Isomorphism Search. Proceedings of the VLDB Endowment 10, 3 (November 2016, 121–132). doi: 10.14778/3021924.3021929, but it has limited itself to developing caching strategies and search heuristics for specific use cases. Finally, using a pre-compiled data structure for pattern matching was already proposed in Messmer, 1999Bruno T. Messmer and Horst Bunke. 1999. A decision tree approach to graph and subgraph isomorphism detection. Pattern Recognition 32, 12 (December 1999, 1979--1998). doi: 10.1016/S0031-3203(98)90142-X. However, with a $n^{\Theta(m)}$ space complexity – $n$ is the input size and $m$ the pattern size – it does not scale to large input graphs, even for small patterns.

4.2. Preliminaries and simplifying assumptions

For simplicity, we will throughout consider minIR graphs that admit a type system $\Sigma$, though most of the results can also be adapted to other graph domains. We will write $T$ for the types of $\Sigma$ (i.e. its values) and $\Gamma$ for the operation types (i.e. its edges).

Linear paths and operation splitting #

An operation type $\nu \in \Gamma$ in the type system $\Sigma$ is a hyperedge. Its endpoints

are strings of data types that define the input and output signature of the operation $\nu$. We can refer to the set of all hyperedge endpoints of $\nu$ using the string indices $\mathrm{Idx}(\cdot)$ ($\sqcup$ denotes the disjoint set union):

Fix a partition of $P_\nu$ into disjoint pairs

where the last set of the partition may be a singleton if $|P_\nu|$ is odd. For every $\nu \in \Gamma$, we then define $f = \lceil |P_o| / 2 \rceil$ new split operation types $\nu_1, \dots, \nu_f$, each with two endpoints: the $i$-th operation type $\nu_i$ has endpoints $p_i$ and $p_i'$ in $P_\nu$. For every operation $o \in E$ of type $\nu$, we can then split $o$ into $f$ operations $o_1, \dots, o_f,$ each of arity 1 or 2 and of types $\nu_1, \dots, \nu_f$ respectively. We will refer to the graph transformation that replaces an operation $o$ in a minIR graph with the operations $o_i$ for $1 \leqslant i \leqslant f$ as operation splitting.

It is important to note that the splitting of an operation $o$ is unique and given by the type of $o$, and thus invariant under (typed) morphisms: there is a morphism $P \to G$ of a pattern into a graph if and only if there is a morphism $P' \to G'$ from the split pattern $P'$ into the split graph $G'$.

The endpoint partitions $P_\nu$ also define linear paths. Two values $v, v'$ in a minIR graph are on the same linear path if there are values $u_1, \dots, u_k$ with $v = u_1$ and $v' = u_k$ such that $u_i$ is connected to $u_{i+1}$ through an operation $o$ and they correspond to the same pair of endpoints in the endpoints partition (i.e. the indices of $P_{type(o)}$ correspond to values $u_i$ and $u_{i+1}$ in $\textit{src}(o) \sqcup \textit{tgt}(o)$).

Linearity assumption and rigidity #

Recall that in Definition ., $V_\textit{src}$ and $V_\textit{tgt}$ refer to the subset of values that are within the domain of definition of $\textit{src}$ and $\textit{tgt}$ respectively. For this chapter, we will assume $V_\textit{src} = V_\textit{tgt} = V$; in other words, minIR graphs are IO-free (this is w.l.o.g., see discussion after Proposition .) and all values are linear¹ (this is definitely not w.l.o.g.!).

As a result of this assumption, the subcategory of minIR graphs that we consider forms a rigid category, as introduced by Danos et al. Danos, 2014Vincent Danos, Reiko Heckel and Pawel Sobocinski. 2014. Transformation and Refinement of Rigid Structures. The definition, which we reproduce here, is given in terms of morphisms that intersect all components of the codomain. We refer to Danos, 2014Vincent Danos, Reiko Heckel and Pawel Sobocinski. 2014. Transformation and Refinement of Rigid Structures for the precise definition of that notion: in the context of linear-valued minIR graphs, this is equivalent to requiring that the image of the graph homomorphism intersects every connected component of the codomain.

In other words, there is a unique way to extend a morphism $A \xrightarrow{g} C$ to a morphism $B \xrightarrow{f} C$, if it exists. If we interpret $A$ and $B$ as graph patterns that we are interested in matching with $A \subseteq B$, then rigidity guarantees that there is (at most) a unique way to extend a match morphism $A \to G$ into a match morphism on the larger pattern $B \to G$.

The linearity assumption also has other useful consequences. Every linear value has exactly one use and one definition. As a result, all linear paths are disjoint and form a partition of the values of the graph. They correspond to the paths that form the connected components of the fully split graph, i.e. the graph obtained by splitting every operation. We call the number of linear paths (and hence the number of connected components in the fully split graph) the circuit width, written $width(G)$. We also use the linear path decomposition to define circuit depth, written $depth(G)$, as the longest linear path in $G$.

As discussed in section 3.4, minIR rewrites are instantiated from transformation rules by minIR match morphisms $m: P \to G$. Restricting our considerations to linear-valued minIR graphs has the further implication that all such match morphsisms $m$ will be injective. We call $m$ an embedding and write it using greek letters and a hooked arrow

Finding such embeddings $P \hookrightarrow G$ is the pattern matching problem that we are solving. This problem is equivalent to finding minIR subgraphs $H \subseteq G$ of $G$ such that $H$ is isomorphic to the pattern $P \simeq H$.

Convexity #

According to Proposition ., a necessary condition for a subgraph $H$ to define a valid minIR rewrite is convexity. In this chapter we weaken this requirement and propose a condition based on circuit width:

In this chapter, whenever we define a subgraph $H \subseteq G$ of a graph $G$, we will assume that $H$ satisfies the above weakened convexity condition.

The converse of Proposition ., however, is not true. The pattern-matching technique presented below will find a strict superset of convex embeddings. To restrict considerations to convex embeddings, it suffices to filter out the non-convex ones in a post-processing step.

Ignoring minIR Hierarchy #

So far, we have omitted discussing one part of the minIR structure: the nested hierarchy of operations. Syntactically, the hierarchy formed by $parent$ relations between minIR operations can be viewed as just another value type that operations are incident to: parent operations define an additional output that children operations consume as additional input. Because of the bijectivity requirement of minIR morphisms on parent-child relations of Definition ., these parent-child relations behave, in fact, like linear values – and hence do not violate the linearity assumption we have imposed.

However, by treating them as such, we have further weakened the constraints on pattern embeddings. We do not enforce that boundary values must be in the same regions or that parent-child relations cannot be boundary values. Similarly to convexity, we defer checking these properties to a post-processing step.

Further assumptions (harmless) #

We will further simplify the problem by making presentation choices that do not imply any loss of generality. First of all, we assume that all patterns have the same width $w$ and depth $d$, are connected graphs and have at least 2 operations. These conditions can always be fulfilled by adding “dummy” operations if necessary. Embeddings of disconnected patterns can be computed one connected component at a time.

We will further assume that all operations are on at most two linear paths (and thus in particular, have at most 4 endpoints). Operations on $\Delta > 2$ linear paths can always be broken up into a composition of $\Delta-1$ operations, each on two linear paths as follows:

This transformation leaves circuit width unchanged but may multiply the graph depth by up to a factor $\Delta$.

We furthermore define the set of all port labels

so that we can associate every operation endpoint in a minIR graph $G$ with a port label from the set $P_{all}$. We further endow the labels $P_{all}$ with a total order (for instance, based on the string index values). The total order on $P_{all}$ then induces a total order on the paths $v_1\cdots v_k \in V^\ast$ in $G$ that start in the same value $v_1$: the paths are equivalently described by the sequence of port labels of the operations traversed. These form strings in $P_{all}^\ast$, which we order lexicographically. Given a root value $r$, for every value $v$ in $G$ there is thus a unique smallest path from $r$ to $v$ in $G$². This path is invariant under isomorphism of the underlying graph (i.e. relabelling of the values and operations but preserving the port labels). With this we conclude the discussions of the specificities of minIR graphs related to typing, linearity and hierarchy, and the related assumptions that we are making.

To summarise, minIR graphs as they are considered in this chapter are hypergraphs (Definition .) that satisfy the following properties

• every vertex (value) is incident to exactly two hyperedges (operations). It is the target of one hyperedge (its definition) and the source of another one (its use),
• every hyperedge is incident to at most four vertices,
• every hyperedge can be split in a unique way (and invariant under isomorphism) into at most two split operations, with each at most two endpoints.

When modelling subgraphs of IO-free minIR graphs (typically patterns for pattern matching), some hyperedge connections at the boundary of the subgraph will be missing. We say a value is open if a use or define operation is missing (i.e. it is a boundary value in a minIR subgraph).

We will simplify refer to hypergraphs that satisfy the above assumptions as graphs. In the unique instance of this chapter where a graph that does not satisfy this construction is referred to, we will specifically call it a simple graph.

We conclude with the following notable bound on circuit width.

4.3. Tree reduction

We reduce the problem of graph pattern matching to matching on rooted trees – as we will see in section 4.6, a much simpler problem to solve. The map between graphs and (rooted) trees is given by rooted dual trees. Call $G$ tree-like if $G$ is connected and the underlying undirected graph $G_U$ of $G$ is acyclic.

Unlike graphs, tree nodes are identified uniquely by their path from the root. Trees isomorphic as graphs with identical root are thus considered equal.

A tree reduction using path splitting #

To reduce a graph $G$ to a tree using the rooted dual tree construction, it suffices to reduce $G$ to a tree-like graph. The following result shows that this can always be achieved by repeatedly applying operation splitting transformations.

As we consider typed graph, the splitting of an operation is unique; however the choice of spanning tree of $\mathcal I$ is not unique, and thus multiple PSGs exist for a given graph $G$.

If $G'$ is a PSG of some graph $G$, then call an operation $o$ of $G$ an anchor operation if it is on two linear paths and it is not split in $G'$. The set of all anchors operations $\pi \subseteq O$ fully determines the path-split graph. We write $G^\pi = G'$ for the PSG of $G$ obtained by anchors $\pi$.

We can make the path splitting transformation $G \to G^\pi$ reversible by separately storing the set of split operations in $G^\pi$ that correspond to a single operation in $G$. As every operation of $G$ can get split in at most two split operations, we can store the pairs of split operations in $G^\pi$ that correspond to an operation in $G$ in a partial map that defines weights for (a subset of) the operations $O^\pi$ of $G^\pi$:

This maps a split operation $o$ to the unique undirected path in $G^\pi$ from $o$ to the other half of the split operation.

This defines a map $\sigma_1: (G^\pi, split) \mapsto G$, the inverse of the path splitting transformation $G \to G^\pi$.

Contracted path-split graphs #

We can further simplify the structure of the data of a PSG by contracting all operations of $G^\pi$ that are on a single linear path. The result is the contracted path-split graph (cPSG) of $G$, written $c(G^\pi)$.

We employ a similar trick as above to make this transformation reversible, this time by introducing weights on the values of $c(G^\pi)$ that store the string of operations that were contracted²

where $V_C$ are the values of $c(G^\pi)$ and $\Gamma^\pi$ are the optypes of operations in $G^\pi$, i.e. the optypes of the minIR graph $G$ along with the optypes of the split operations. This defines a second map $\sigma_2: (c(G^\pi), contract) \mapsto G^\pi$ that is the inverse of the path-split graph contraction transformation $c(\cdot)$. In summary, we have the composition

Contracted PSGs are particularly useful for the study of the asymptotic complexity of the pattern matching algorithm we propose, as they have a very regular structure. This is expressed by the following proposition that further extends the statement of Proposition 4.3:

We conclude the construction presented in this section with the following result, expressing graph pattern matching in terms of tree equality:

The proof of this follows directly from our construction, the unicity of trees under isomorphism and the bijection between the graphs $P, H$ and their cPSGs.

We have thus successfully reduced the problem of pattern matching to the problem of matching on trees. Given that the ordering of children of a node in a tree is fixed, checking trees for equality is a simple matter of checking node and weight equality, one node (and edge) at a time.

We conclude this section with a figure summarising the constructions we have presented.

4.4. Canonicalising the tree reduction

The reduction of graph matching to ternary trees from the previous section is a big step towards an algorithm for graph matching. However, Proposition 4.5 is expressed in terms of existence of PSGs – it is as yet unclear how the trees can be constructed. This is the purpose of this section.

We introduce for this purpose a canonical, that is, invariant under isomorphism, choice of PSG $G^\pi$ of $G$. The result is a unique canonical transformation $G \mapsto G^\pi \mapsto c(G^\pi)$ from $G$ to a cPSG that we can use for pattern matching.

We proceed by using the total order that we have defined on port labels and can be extended lexicographically to paths outgoing from a shared root operation (see section 4.2 for more details). Whenever more than one path from $r$ to $o$ exist in $G$, it suffices to consider the smallest one. For a choice of root operation $r \in O,$ we thus obtain a total order of all operations $O$ in $G$.

We then restrict our attention to operations on two linear paths and consider them in order. We keep track of linear paths that have been visited and proceed as follows to determine whether $o \in O$ must be split:

• if $o$ is on a linear path that was not seen before, it is left unchanged and the set of visited linear paths is updated;
• otherwise, i.e. $o$ is on two linear paths that have already been visited, the operation is split, resulting in two operations on a single linear path.

The pseudocode CanonicalPathSplit implements this algorithm. We use Operations(G) to retrieve all the operations on the graph G and LinearPaths(G, op) to retrieve the linear paths of the operation op. The linear paths are identified using integer indices that can be pre-computed and stored in linear time in the graph size. SplitOperation(G, op) returns the graph resulting from splitting op into two operations on a single linear path. Finally, PathAsPortLabels(G, root, v) returns the string of the port labels that encode the path from root to v in the graph G. The strings are ordered lexicographically. The non-capitalized functions set, union, sort¹, len, and issubset have their standard meanings.

 1def CanonicalPathSplit(G: Graph, root: Operation) -> Graph:
 2  new_G := G
 3  all_operations := Operations(G)
 4  sorted_operations := sort(
 5      all_operations,
 6      sort_key= lambda v: PathAsPortLabels(G, root, v)
 7  )
 8
 9  # keep track of the visited linear paths
10  seen_paths := set()
11  for op in sorted_operations:
12    # Get the (pre-computed) indices of the linear paths
13    op_linear_paths := LinearPaths(G, op)
14    if len(op_linear_paths) == 2:
15      if issubset(op_linear_paths, seen_paths):
16        # The two linear paths of `op` are already visited
17        new_G = SplitOperation(new_G, op)
18      else:
19        # Mark the new linear paths as visited
20        seen_paths = union(seen_paths, op_linear_paths)
21  return new_G

The following figure shows an example of splitting a graph into its canonical PSG using CanonicalPathSplit.

Using CanonicalPathSplit, we can now sketch what the pattern matching algorithm should look like. For each pattern, we first compute their canonical PSG for an arbirary choice of pattern root operation; then, given a graph $G$, we can find all embeddings of patterns into $G$ by iterating over all possible PSGs within $G$. Naively, this involves enumerating all posible subgraphs of $G$, and then for each of them, iterating over all possible root choices.

This can be significantly sped up by realising that many of the PSGs that are computed when iterating over all possible subgraphs and root choices are redundant². We will see in the next section that we can i) iterate once over all possible root choices $r$ in $G$ and ii) introduce a new procedure AllPathSplits that will efficiently enumerate all possible rooted ual trees of PSGs that are rooted in $r$ for subgraphs within $G$. In the process, we will also see that we can replace the tree equality check of line 12 with a subtree inclusion check, further reducing the number of PSGs that must be considered.

 1# Precompute all PSGs
 2allT = [CanonicalPathSplit(
 3    P, root_P
 4) for (P, root_P) in patterns]
 5
 6for S in Subgraphs(G):
 7  for root_S in Operations(S):
 8    TG = CanonicalPathSplit(
 9        S, root_S
10    )
11    for T in allT:
12      if T == TG:
13        yield T

 1# Precompute all PSGs
 2allT = [CanonicalPathSplit(
 3    P, root_P
 4) for (P, root_P) in patterns]
 5
 6for root_G in Operations(G):
 7  for TG in AllPathSplits(
 8      G, root_G
 9  ):
10    for T in allT
11      # Replace == with subtree
12      if IsSubTree(T, TG)
13        yield T

4.5. Enumerating all path-split graphs

The CanonicalPathSplit procedure in the previous section defines for all graphs $G$ and choice of root operation $r$ a canonical PSG $G^\pi$, and thus a canonical set of anchors $\pi$ that we write as $\pi_r(G) = \pi.$

Instead of CanonicalPathSplit, we can equivalently consider a CanonicalAnchors procedure, which computes $\pi_r(G)$ directly instead of the graph $G^{\pi_r(G)}$.

We formulate this computation below, using recursion instead of a for loop. This form generalises better to the AllAnchors procedure that we will introduce next.

The equivalence of the CanonicalAnchors procedure with CanonicalPathSplit follows from the observation made in section 4.2 that ordering operations in lexicographic order of the port labels is equivalent to a depth-first traversal of the graph.

CanonicalAnchors implements a recursive depth-first traversal (DFS), with the twist that the recursion is explicit only on the anchor nodes and otherwise relying on the lexicographic ordering just like in CanonicalPathSplit: lines 5–15 of CanonicalAnchors correspond to the iterations of the for loop (line 11–20) of CanonicalPathSplit until an anchor operation is found (i.e. the else branch on lines 18–20 is executed). From there, the graph traversal proceeds recursively.

We introduce the ConnectedComponent, Neighbours and RemoveOperation procedures; the first returns the connected component of the current operation, whereas the other two procedures are used to traverse, respectively modify, the graph $G$. Importantly, Neighbours(G, op) returns the neighbours of op ordered by port label order.

To ensure that the recursive DFS does not visit the same operation twice, we modify the graph with RemoveOperation on lines 11 and 15, ensuring that no visited operation remains in G. As a consequence, CanonicalAnchors may be called on disconnected graphs, which explains why an additional call to ConnectedComponent (line 4) is required.

The proof follows directly from the previous paragraphs.

 1def CanonicalAnchors(
 2    G: Graph, root: Operation, seen_paths: Set[int]
 3) -> (Set[Operation], Set[int], Graph):
 4  operations = Operations(ConnectedComponent(G, root))
 5  # sort by PathAsPortLabels, as previously
 6  sorted_operations := sort(operations)
 7  operations_queue := queue(sorted_operations)
 8
 9  # Skip all operations that are not anchors
10  op := operations_queue.pop() # never emtpy, contains root
11  G = RemoveOperation(G, op)
12  while len(LinearPaths(G, op)) == 1 or
13        issubset(LinearPaths(G, op), seen_paths):
14    op = operations_queue.pop() or return ({}, {}, G)
15    G = RemoveOperation(G, op)
16
17  # op is anchor, update seen_paths and recurse
18  seen_paths = union(seen_paths, LinearPaths(G, op))
19  anchors := [op]
20  # sort by port labels
21  for child in Neighbours(G, op):
22    (new_anchors, seen_paths, G) = CanonicalAnchors(
23        G, child, seen_paths
24    )
25    anchors += new_anchors
26
27  return (anchors, seen_paths, G)

Maximal PSGs #

In addition to “simplifying” the data required to define path splitting, the definition of PSGs using anchor operations has another advantage that is fundamental to the pattern matching algorithm.

Consider the rooted dual tree $\tau_r(G^\pi)$ of a PSG with root operation $r$ in $G^\pi$. Recall that tree nodes are uniquely identified by their path from the root and thus are considered equal if they are isomorphic as graphs. We can in the same way define a tree inclusion relation $\subseteq$ on rooted dual trees that corresponds to checking that the trees have the same root and that the left-hand side is isomorphic to a subtree of the right-hand side. We also require that the operation weights given by the $split$ map $split$ map coincide on the common subtree.

The proof gives an explicit construction for $M$.

This result means that instead of listing all PSGs for every possible subgraph of $G$, it is sufficient to proceed as follows:

1. for every pattern $P$, fix a root operation $r_P$ and construct the rooted tree dual of the canonical PSG
   $$\tau_P := \tau_{r_P}(P^{\pi_{r_P}(P)}).$$
2. enumerate every possible root operation $r$ in $G$,
3. enumerate every possible sets of anchors $\pi$ in $G$ with root $r$,
4. for each set $\pi$, find the maximal PSG $M$ with anchors $\pi$ in $G$, and take its rooted tree dual $\tau_M := \tau_r(M^\pi)$,
5. find all patterns $P$ such that $\tau_P \subseteq \tau_M$.

In other words, if AllAnchors is a procedure that enumerates all possible sets of anchors $\pi$ in $G$ and MaximalPathSplit computes the maximal PSG $M$ as presented in the proof of Proposition 4.9, then AllPathSplits(G) can simply be obtained by calling AllAnchors and then returning their respective maximal PSGs in $G$:

def AllPathSplits(G: Graph, root: Operation) -> Set[Graph]:
  all_anchors = AllAnchors(G, root)
  return {MaximalPathSplit(G, pi) for pi in all_anchors}

The missing piece: AllAnchors #

We can now complete the definition of AllPathSplits by defining the AllAnchors procedure, which enumerates all possible sets of anchors in $G$ given a root operation $r$.

The procedure is similar to CanonicalAnchors, described in detail in the previous paragraphs. In addition to the arguments of CanonicalAnchors, AllAnchors requires a width $w \geq 1$ argument. It then returns all sets of at most $w$ operations¹ that form the canonical anchors of some width-$w$ subgraph of $G$ with root $r$. The main difference between CanonicalAnchors and AllAnchors is that the successive recursive calls (line 22 in CanonicalAnchors) are replaced by a series of nested loops (lines 42–48 in AllAnchors) that exhaustively iterate over the possible outcomes for different subgraphs of $G$. The results of every possible combination of recursive calls are then collected into a list of anchor sets, which is returned.

The part of the pseudocode that is without comments is unchanged from CanonicalAnchors. Using Proposition 4.3, we know that we can assume that every operation has at most 3 children, and thus 3 neighbours in G, given that the operations equivalent to parent nodes were removed.

 1def AllAnchors(
 2    G: Graph, root: Operation, w: int,
 3    seen_paths: Set[int] = {}
 4) -> List[(Set[Operation], Set[int], Graph)]:
 5  # Base case: return one empty anchor list
 6  if w == 0:
 7    return [({}, {}, G)]
 8
 9  operations = Operations(ConnectedComponent(G, root))
10  sorted_operations := sort(operations)
11  operations_queue := queue(sorted_operations)
12
13  op := operations_queue.pop()
14  G = RemoveOperation(G, op)
15  while len(LinearPaths(G, op)) == 1 or
16        issubset(LinearPaths(G, op), seen_paths):
17    op = operations_queue.pop() or return [({}, {}, G)]
18    G = RemoveOperation(G, op)
19
20  seen0 = union(seen_paths, LinearPaths(G, op))
21  # There are always at most three neighbours: we
22  # unroll the for loop of CanonicalAnchors.
23  [child1, child2, child3] = Neighbours(G, op)
24  # Iterate over all ways to split w-1 anchors over
25  # the three children and solve recursively
26  all_anchors = []
27  for 0 <= w1, w2, w3 < w with w1 + w2 + w3 == w - 1:
28    for (anchors1, seen1, G1) in
29        AllAnchors(G, child1, w1, seen0):
30      for (anchors2, seen2, G2) in
31          AllAnchors(G1, child2, w2, seen1):
32        for (anchors3, seen3, G3) in
33            AllAnchors(G2, child3, w3, seen2):
34          # Concatenate new anchor with anchors from all paths
35          anchors = union([op], anchors1, anchors2, anchors3)
36          all_anchors.push((anchors, seen3, G3))
37  return all_anchors

We can represent the sequence of recursive calls to AllAnchors as a tree. The call tree for the graph used as example to illustrate CanonicalAnchors earlier is given on the next page.

We now show correctness of the procedure. Let us write $\Pi_r^w(G)$ for the set of sets of anchors returned by AllAnchors(G, r, w, {}).

The proof is by induction over the width $w$ of the subgraph $H$. The idea is to map every recursive call in CanonicalAnchors to one of the calls to AllAnchors on lines 29, 31 or 33. All recursive results are concatenated on line 36, and thus, the value returned by CanonicalAnchors will be one of the anchor sets in the list returned by AllAnchors.

We will see that the overall runtime complexity of AllAnchors can be easily derived from a bound on the size of the returned list. For this, we use the following result:

To obtain a runtime bound for AllAnchors, it is useful to identify how much of $G$ needs to be traversed. If we suppose all patterns have at most depth $d$, then it immediately follows that any operation in $G$ that is in the image of a pattern embedding must be at most a distance $d$ away from an anchor operation. We can thus equivalently call AllAnchors on a subgraph of $G$ such that no linear path is longer than $2d$. We thus obtain the following runtime.

4.6. An automaton for multi-pattern matching

We have shown in the previous sections that graph pattern-matching can be reduced to a problem of tree inclusions, with trees of fixed width $w$. To complete the pattern-matching algorithm, we must provide a fast way to evaluate the subtree relation for many trees representing the set of all patterns we wish to match.

More precisely, for patterns $P_1, \dots, P_\ell$ with width $w$, fix a root operation $r_i$ in $P_i$ for each $1 \leqslant i \leqslant \ell$ and consider the rooted tree duals of the canonical PSGs $\tau_{r_i}(P_i^{\pi_i})$, with $\pi_i = \pi_{r_i}(P_i)$ the canonical anchors. Then given a subject graph $G$, we wish to compute the set

for all anchor sets $\pi \in \Pi_r^w(G)$ and root operation $r$ in $G$. This corresponds to the IsSubTree predicate introduced in the sketch of the algorith in section 4.4.

Instead of considering the trees of PSGs, it will prove easier to consider the contracted PSGs (cPSGs)

Such tree inclusions are equivalent to finding embeddings in the subject graph itself, provided that we keep track of the $split$ and $contract$ weight maps (see section 4.3).

It will be useful to remind ourselves the following properties of contracted PSGs. Every operation of a cPSG (and thus every node in its rooted dual tree) is an anchor operation of the PSG. Per Proposition 4.4, the rooted dual tree of a cPSG is a ternary tree and has exactly $width(G) - 1$ nodes. Finally, recall the concept of an open value of a graph, i.e. a value that is missing either a use or define operation (see section 4.2).

Reduction of tree inclusion to string prefix matching #

Now consider two contracted spanning tree reductions $c(G_1^{\pi_1})$ and $c(G_2^{\pi_2})$ with values $V_1$ and $V_2$. To simplify notation, define

for some choice of root operations $r_1$ and $r_2$ in $G_1$ and $G_2$, respectively. We lift the $\subseteq$ relation on rooted dual trees of PSGs introduced in section 4.5 to rooted dual trees of cPSGs in Such a way that there is an inclusion relation between two rooted dual trees of PSGs if and only if the same relation holds on the rooted duals of cPSGs.

We say that $\tau_1 \subseteq \tau_2$ if and only if

• the trees share the same root operation,
• $\tau_1$ is a subtree of $\tau_2$,
• the $spilt$ map coincides on the common subtree, and
• the $contract$ map satisfies for all $v \in V_1$:
  $$\begin{cases}contract(v) \subseteq contract(f(v))\quad&\textrm{if }v\textrm{ is an open value},\\contract(v) = contract(f(v))\quad&\textrm{otherwise},\\\end{cases}$$