Graph matching and manipulation with Aidge#

Aidge introduces a simple and efficient DSL for graph matching, sometimes referred to as ‘graph regex.’ It allows for the creation of complex textual queries to find a quantified or unquantified set of nodes with specific types, attributes, and/or relationships between them. This is particularly useful for implementing sophisticated pattern-matching heuristics with minimal effort!

[71]:

# First import some utility methods used in the tutorial:
import sys, os
sys.path.append(os.path.abspath(os.path.join('..')))
import tuto_utils

Graph matching#

Let’s first define a graph on which we will perform the graph matching:

[72]:

import aidge_core
import aidge_onnx
import aidge_backend_cpu

model = aidge_core.sequential([
    aidge_core.Producer([16, 3, 512, 512], name="dataProvider"),
    aidge_core.Conv2D(3, 4, [5, 5], name="conv1"),
    aidge_core.ReLU(name="relu1"),
    aidge_core.PaddedConv2D(4, 8, [5, 5], name="conv2", stride_dims=[1, 1], padding_dims=[2, 2, 2, 2]),
    aidge_core.ReLU(name="relu2"),
    aidge_core.PaddedConv2D(8, 16, [3, 3], name="conv3", stride_dims=[1, 1], padding_dims=[2, 2, 2, 2], no_bias=True),
    aidge_core.ReLU(name="relu3"),
    aidge_core.PaddedConv2D(16, 16, [5, 5], name="conv4", stride_dims=[1, 1], padding_dims=[2, 2, 2, 2]),
    aidge_core.Add(name="add"),
    aidge_core.PaddedConv2D(16, 16, [5, 5], name="conv5", stride_dims=[1, 1], padding_dims=[2, 2, 2, 2]),
    aidge_core.ReLU(name="relu5"),
    aidge_core.Add(name="add2")
])

model.get_node("relu3").add_child(model.get_node("add"), 0, 1)
model.get_node("conv5").add_child(model.get_node("add2"), 0, 1)
model.update_inputs_outputs()
aidge_core.expand_metaops(model)

# Display static scheduling
model.save("graph")
tuto_utils.visualize_mmd("graph.mmd")

Notice: the 0-th Parent of the child node relu2 (of type ReLU) already existed
Filling a Tensor already attributed.
You are replacing an existing parent for node relu2 (of type ReLU).
Notice: the 0-th Parent of the child node relu5 (of type ReLU) already existed
Filling a Tensor already attributed.
You are replacing an existing parent for node relu5 (of type ReLU).
Notice: the 1-th Parent of the child node add2 (of type Add) already existed
Filling a Tensor already attributed.
You are replacing an existing parent for node add2 (of type Add).
Notice: the 0-th Parent of the child node add (of type Add) already existed
Filling a Tensor already attributed.
You are replacing an existing parent for node add (of type Add).
Notice: the 0-th Parent of the child node relu3 (of type ReLU) already existed
Filling a Tensor already attributed.
You are replacing an existing parent for node relu3 (of type ReLU).

Base Matching Rules#

You can write regular expression-like search patterns to match elements in the graph. For example, you may want to find all Conv operators, including any preceding Pad operator and succeeding ReLU operator:

[73]:

matches = aidge_core.SinglePassGraphMatching(model).match("Conv2D#->ReLU?;Conv2D#<-Pad2D?")
print(f"Found {len(matches)} matches!\n")

for match in matches:
    print(f"root node = {match.graph.root_node()}")
    print(f" ↳ matched nodes = {match.graph.get_nodes()}\n")

Found 5 matches!

root node = Node(name='conv5_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1, 1]])
 ↳ matched nodes = {Node(name='conv5_pad', optype='Pad2D', parents: [1], children: [[1]]), Node(name='conv5_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1, 1]])}

root node = Node(name='conv3_conv', optype='Conv2D', parents: [1, 1, 0], children: [[1]])
 ↳ matched nodes = {Node(name='conv3_conv', optype='Conv2D', parents: [1, 1, 0], children: [[1]]), Node(name='relu3', optype='ReLU', parents: [1], children: [[1, 1]]), Node(name='conv3_pad', optype='Pad2D', parents: [1], children: [[1]])}

root node = Node(name='conv4_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1]])
 ↳ matched nodes = {Node(name='conv4_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1]]), Node(name='conv4_pad', optype='Pad2D', parents: [1], children: [[1]])}

root node = Node(name='conv1', optype='Conv2D', parents: [1, 1, 1], children: [[1]])
 ↳ matched nodes = {Node(name='relu1', optype='ReLU', parents: [1], children: [[1]]), Node(name='conv1', optype='Conv2D', parents: [1, 1, 1], children: [[1]])}

root node = Node(name='conv2_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1]])
 ↳ matched nodes = {Node(name='conv2_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1]]), Node(name='conv2_pad', optype='Pad2D', parents: [1], children: [[1]]), Node(name='relu2', optype='ReLU', parents: [1], children: [[1]])}

This query is matched through a direct, single-pass parse. The returned matches are unordered, so they are stored in a std::set (if you rerun the same command, the order of results may change).

Here, the query is Conv2D#->ReLU?;Conv2D#<-Pad2D?. From this simple query, several rules for graph matching can already be identified:

The first node in the first sequence is the root node and cannot be optional:

WRONG:
- ReLU?->Conv (will throw an error)
GOOD:
- Conv<-ReLU?
The first node in any subsequent sequence must be an existing anchor (anchors cannot appear in the middle of a sequence). An anchor is defined by suffixing the node type with # and the anchor name (which can be empty):

WRONG:
- Conv->ReLU;Pad->Conv (will throw an error)
- Pad->Conv;Conv->ReLU (will throw an error)
GOOD:
- Conv#->ReLU;Conv#<-Pad
- Pad->Conv#;Conv#->ReLU
A node that has already been matched cannot be matched again (except for anchors).

Regarding the last point: when multiple nodes could match a given node query, the first one that hasn’t already been matched is selected, following the ordered list of child/parent nodes. Examples:

[74]:

print("Match the first Producer of the Conv:")
matches = aidge_core.SinglePassGraphMatching(model).match("Conv2D<*-Producer")
print(f"Found {len(matches)} matches!\n")

for match in matches:
    print(f"root node = {match.graph.root_node()}")
    print(f" ↳ matched nodes = {match.graph.get_nodes()}\n")

print("Match the first and second Producer of the Conv:")
matches = aidge_core.SinglePassGraphMatching(model).match("Conv2D#<*-Producer;Conv2D#<*-Producer")
print(f"Found {len(matches)} matches!\n")

for match in matches:
    print(f"root node = {match.graph.root_node()}")
    print(f" ↳ matched nodes = {match.graph.get_nodes()}\n")

Match the first Producer of the Conv:
Found 5 matches!

root node = Node(name='conv5_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1, 1]])
 ↳ matched nodes = {Node(name='conv5_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1, 1]]), Node(name='conv5_w', optype='Producer', children: [[1]])}

root node = Node(name='conv3_conv', optype='Conv2D', parents: [1, 1, 0], children: [[1]])
 ↳ matched nodes = {Node(name='conv3_w', optype='Producer', children: [[1]]), Node(name='conv3_conv', optype='Conv2D', parents: [1, 1, 0], children: [[1]])}

root node = Node(name='conv4_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1]])
 ↳ matched nodes = {Node(name='conv4_w', optype='Producer', children: [[1]]), Node(name='conv4_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1]])}

root node = Node(name='conv1', optype='Conv2D', parents: [1, 1, 1], children: [[1]])
 ↳ matched nodes = {Node(name='conv1', optype='Conv2D', parents: [1, 1, 1], children: [[1]]), Node(name='dataProvider', optype='Producer', children: [[1]])}

root node = Node(name='conv2_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1]])
 ↳ matched nodes = {Node(name='conv2_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1]]), Node(name='conv2_w', optype='Producer', children: [[1]])}

Match the first and second Producer of the Conv:
Found 4 matches!

root node = Node(name='conv5_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1, 1]])
 ↳ matched nodes = {Node(name='conv5_b', optype='Producer', children: [[1]]), Node(name='conv5_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1, 1]]), Node(name='conv5_w', optype='Producer', children: [[1]])}

root node = Node(name='conv4_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1]])
 ↳ matched nodes = {Node(name='conv4_b', optype='Producer', children: [[1]]), Node(name='conv4_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1]]), Node(name='conv4_w', optype='Producer', children: [[1]])}

root node = Node(name='conv1', optype='Conv2D', parents: [1, 1, 1], children: [[1]])
 ↳ matched nodes = {Node(name='conv1_w', optype='Producer', children: [[1]]), Node(name='conv1', optype='Conv2D', parents: [1, 1, 1], children: [[1]]), Node(name='dataProvider', optype='Producer', children: [[1]])}

root node = Node(name='conv2_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1]])
 ↳ matched nodes = {Node(name='conv2_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1]]), Node(name='conv2_b', optype='Producer', children: [[1]]), Node(name='conv2_w', optype='Producer', children: [[1]])}

Note that since all nodes matched in the query are always captured, it is not possible to capture only the second Producer in the second example. A selective capture mechanism may be implemented in the future if there is demand for it!

Specifiyng Edges#

Edges are specified using the child -> (ParentNodeType->ChildNodeType) or parent <- (ChildNodeType<-ParentNodeType) operators.

By default, an edge matches the first output to the first input:

ReLU->Conv is equivalent to ReLU-0-0>Conv;
To match the second input, use ReLU-0-1>Conv (or ReLU-1>Conv);
To match the second output, use ReLU-1-0>Conv;
To match any input and/or any output, use *, like ReLU-1-*>Conv or ReLU-*-0>Conv or ReLU-*-*>Conv.

The same syntax applies to the <- edge syntax.

In Aidge, a node output can be connected to multiple other nodes. In your query, you can allow it or not, with the ~ or - modifier in the edge operator. For example:

Conv->ReLU will match the Conv that are only connected to a ReLU node at their output #0.
Conv~>ReLU will match all the Conv connected to a ReLU even if they are also connected to other nodes at the same output #0.

[75]:

print("Match the ReLU that is *only* connected to (any input of) Add:")
matches = aidge_core.SinglePassGraphMatching(model).match("ReLU-*>Add")
print(f"Found {len(matches)} matches!\n")

for match in matches:
    print(f"root node = {match.graph.root_node()}")
    print(f" ↳ matched nodes = {match.graph.get_nodes()}\n")

print("Match all ReLU that are *at least* connected to (any input of) Add:")
matches = aidge_core.SinglePassGraphMatching(model).match("ReLU~*>Add")
print(f"Found {len(matches)} matches!\n")

for match in matches:
    print(f"root node = {match.graph.root_node()}")
    print(f" ↳ matched nodes = {match.graph.get_nodes()}\n")

print("Match the ReLU that is *at least* connected to input #0 of Add:")
matches = aidge_core.SinglePassGraphMatching(model).match("ReLU~>Add")
print(f"Found {len(matches)} matches!\n")

for match in matches:
    print(f"root node = {match.graph.root_node()}")
    print(f" ↳ matched nodes = {match.graph.get_nodes()}\n")

Match the ReLU that is *only* connected to (any input of) Add:
Found 1 matches!

root node = Node(name='relu5', optype='ReLU', parents: [1], children: [[1]])
 ↳ matched nodes = {Node(name='relu5', optype='ReLU', parents: [1], children: [[1]]), Node(name='add2', optype='Add', parents: [1, 1], children: [[]])}

Match all ReLU that are *at least* connected to (any input of) Add:
Found 2 matches!

root node = Node(name='relu5', optype='ReLU', parents: [1], children: [[1]])
 ↳ matched nodes = {Node(name='relu5', optype='ReLU', parents: [1], children: [[1]]), Node(name='add2', optype='Add', parents: [1, 1], children: [[]])}

root node = Node(name='relu3', optype='ReLU', parents: [1], children: [[1, 1]])
 ↳ matched nodes = {Node(name='relu3', optype='ReLU', parents: [1], children: [[1, 1]]), Node(name='add', optype='Add', parents: [1, 1], children: [[1]])}

Match the ReLU that is *at least* connected to input #0 of Add:
Found 1 matches!

root node = Node(name='relu5', optype='ReLU', parents: [1], children: [[1]])
 ↳ matched nodes = {Node(name='relu5', optype='ReLU', parents: [1], children: [[1]]), Node(name='add2', optype='Add', parents: [1, 1], children: [[]])}

When implementing a match & replace recipe, beware that you don’t break branches in the middle of your matching result if you use ~!

Quantifiers#

Graph matching supports the standard regular expression quantifiers:

? means zero or one;
* means zero or more;
+ means one or more.

Quantifier can be used on sub-expressions delimited with parentheses. Here is an example:

[76]:

matches = aidge_core.SinglePassGraphMatching(model).match("Conv2D->(ReLU~>Pad2D->Conv2D)+")
print(f"Found {len(matches)} matches!\n")

for match in matches:
    print(f"root node = {match.graph.root_node()}")
    print(f" ↳ matched nodes = {match.graph.get_nodes()}\n")

Found 3 matches!

root node = Node(name='conv3_conv', optype='Conv2D', parents: [1, 1, 0], children: [[1]])
 ↳ matched nodes = {Node(name='relu3', optype='ReLU', parents: [1], children: [[1, 1]]), Node(name='conv4_pad', optype='Pad2D', parents: [1], children: [[1]]), Node(name='conv4_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1]]), Node(name='conv3_conv', optype='Conv2D', parents: [1, 1, 0], children: [[1]])}

root node = Node(name='conv1', optype='Conv2D', parents: [1, 1, 1], children: [[1]])
 ↳ matched nodes = {Node(name='conv2_pad', optype='Pad2D', parents: [1], children: [[1]]), Node(name='conv3_conv', optype='Conv2D', parents: [1, 1, 0], children: [[1]]), Node(name='conv4_pad', optype='Pad2D', parents: [1], children: [[1]]), Node(name='conv3_pad', optype='Pad2D', parents: [1], children: [[1]]), Node(name='conv2_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1]]), Node(name='conv1', optype='Conv2D', parents: [1, 1, 1], children: [[1]]), Node(name='relu2', optype='ReLU', parents: [1], children: [[1]]), Node(name='conv4_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1]]), Node(name='relu3', optype='ReLU', parents: [1], children: [[1, 1]]), Node(name='relu1', optype='ReLU', parents: [1], children: [[1]])}

root node = Node(name='conv2_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1]])
 ↳ matched nodes = {Node(name='relu3', optype='ReLU', parents: [1], children: [[1, 1]]), Node(name='conv3_conv', optype='Conv2D', parents: [1, 1, 0], children: [[1]]), Node(name='relu2', optype='ReLU', parents: [1], children: [[1]]), Node(name='conv4_pad', optype='Pad2D', parents: [1], children: [[1]]), Node(name='conv3_pad', optype='Pad2D', parents: [1], children: [[1]]), Node(name='conv4_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1]]), Node(name='conv2_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1]])}

In this example, 3 matches are found, from 3 different root nodes. As one can see, the matching results are overlapping, meaning that some nodes are found in multiple results. Some results are in fact subsets of other results.

To avoid this behavior, you can set the disjoint argument to true. In this case, only the longest disjoint (non-overlapping) matches are kept:

[77]:

matches = aidge_core.SinglePassGraphMatching(model).match("Conv2D->(ReLU~>Pad2D->Conv2D)+", True)
print(f"Found {len(matches)} matches!\n")

for match in matches:
    print(f"root node = {match.graph.root_node()}")
    print(f" ↳ matched nodes = {match.graph.get_nodes()}\n")

Found 1 matches!

root node = Node(name='conv1', optype='Conv2D', parents: [1, 1, 1], children: [[1]])
 ↳ matched nodes = {Node(name='conv4_pad', optype='Pad2D', parents: [1], children: [[1]]), Node(name='conv3_pad', optype='Pad2D', parents: [1], children: [[1]]), Node(name='relu1', optype='ReLU', parents: [1], children: [[1]]), Node(name='conv2_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1]]), Node(name='conv3_conv', optype='Conv2D', parents: [1, 1, 0], children: [[1]]), Node(name='conv1', optype='Conv2D', parents: [1, 1, 1], children: [[1]]), Node(name='relu2', optype='ReLU', parents: [1], children: [[1]]), Node(name='conv2_pad', optype='Pad2D', parents: [1], children: [[1]]), Node(name='relu3', optype='ReLU', parents: [1], children: [[1, 1]]), Node(name='conv4_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1]])}

Advanced usage#

Match any node type#

To match any node type, use the . symbol:

[78]:

matches = aidge_core.SinglePassGraphMatching(model).match("Add<*-.")
print(f"Found {len(matches)} matches!\n")

for match in matches:
    print(f"root node = {match.graph.root_node()}")
    print(f" ↳ matched nodes = {match.graph.get_nodes()}\n")

Found 2 matches!

root node = Node(name='add2', optype='Add', parents: [1, 1], children: [[]])
 ↳ matched nodes = {Node(name='add2', optype='Add', parents: [1, 1], children: [[]]), Node(name='relu5', optype='ReLU', parents: [1], children: [[1]])}

root node = Node(name='add', optype='Add', parents: [1, 1], children: [[1]])
 ↳ matched nodes = {Node(name='conv4_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1]]), Node(name='add', optype='Add', parents: [1, 1], children: [[1]])}

Keep in mind that one always matches a sub-graph: additional connections can exist anywhere in the matched sub-graph.

Examples:

Add<*-. will match the Add operator and its first input, any additional inputs will not be included in the result;
(Add#<*-.)+ will match the Add operator and all of its inputs. Note that the anchor is required since we intend to match several inputs of the same node!

So, in order to match all inputs connected to Add, one must do:

[79]:

matches = aidge_core.SinglePassGraphMatching(model).match("(Add#<*-.)+")
print(f"Found {len(matches)} matches!\n")

for match in matches:
    print(f"root node = {match.graph.root_node()}")
    print(f" ↳ matched nodes = {match.graph.get_nodes()}\n")

Found 2 matches!

root node = Node(name='add2', optype='Add', parents: [1, 1], children: [[]])
 ↳ matched nodes = {Node(name='relu5', optype='ReLU', parents: [1], children: [[1]]), Node(name='add2', optype='Add', parents: [1, 1], children: [[]])}

root node = Node(name='add', optype='Add', parents: [1, 1], children: [[1]])
 ↳ matched nodes = {Node(name='conv4_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1]]), Node(name='add', optype='Add', parents: [1, 1], children: [[1]])}

Oups, what is going one here? We didn’t match the additionnal inputs!

Why? Because the other Add inputs (relu3 and conv5_conv) have multiple outputs. And remember, the <- operator assumes a unique edge from output to input!

So, in this example, to get the expected result, one must use the ~ edge modifier in place of the - one:

[80]:

matches = aidge_core.SinglePassGraphMatching(model).match("(Add#<*~.)+")
print(f"Found {len(matches)} matches!\n")

for match in matches:
    print(f"root node = {match.graph.root_node()}")
    print(f" ↳ matched nodes = {match.graph.get_nodes()}\n")

Found 2 matches!

root node = Node(name='add2', optype='Add', parents: [1, 1], children: [[]])
 ↳ matched nodes = {Node(name='relu5', optype='ReLU', parents: [1], children: [[1]]), Node(name='conv5_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1, 1]]), Node(name='add2', optype='Add', parents: [1, 1], children: [[]])}

root node = Node(name='add', optype='Add', parents: [1, 1], children: [[1]])
 ↳ matched nodes = {Node(name='conv4_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1]]), Node(name='add', optype='Add', parents: [1, 1], children: [[1]]), Node(name='relu3', optype='ReLU', parents: [1], children: [[1, 1]])}

Match “no edge”#

You can use the $ symbol for the node type to match the absence of node, or connection. For example, to match any Conv operator with no bias (meaning no connection at its input #2), you can do the following:

[81]:

matches = aidge_core.SinglePassGraphMatching(model).match("Conv2D<2-$")
print(f"Found {len(matches)} matches!\n")

for match in matches:
    print(f"root node = {match.graph.root_node()}")
    print(f" ↳ matched nodes = {match.graph.get_nodes()}\n")

Found 1 matches!

root node = Node(name='conv3_conv', optype='Conv2D', parents: [1, 1, 0], children: [[1]])
 ↳ matched nodes = {Node(name='conv3_conv', optype='Conv2D', parents: [1, 1, 0], children: [[1]])}

Match node attributes with a lambda function#

In order to match specific node attributes, one case use a lambda function:

[82]:

gm = aidge_core.SinglePassGraphMatching(model)
gm.add_node_lambda("3x3", lambda node: node.get_operator().attr.kernel_dims == [3, 3])

matches = gm.match("Pad2D->Conv2D[3x3]->ReLU")
print(f"Found {len(matches)} matches!\n")

for match in matches:
    print(f"root node = {match.graph.root_node()}")
    print(f" ↳ matched nodes = {match.graph.get_nodes()}\n")

Found 1 matches!

root node = Node(name='conv3_pad', optype='Pad2D', parents: [1], children: [[1]])
 ↳ matched nodes = {Node(name='relu3', optype='ReLU', parents: [1], children: [[1, 1]]), Node(name='conv3_pad', optype='Pad2D', parents: [1], children: [[1]]), Node(name='conv3_conv', optype='Conv2D', parents: [1, 1, 0], children: [[1]])}

Match the first / last node of some type#

Using lambda, it is relatively simple to match the first or last node of a given type in a graph:

[83]:

gm = aidge_core.SinglePassGraphMatching(model)
gm.add_node_lambda("exConv", lambda node: node.type() != "Conv2D")

print("Find first Conv2D:")
matches = gm.match("Conv2D#<-(.[exConv])*<-$")
print(f"Found {len(matches)} matches!\n")

for match in matches:
    print(f"root node = {match.graph.root_node()}")
    print(f" ↳ matched nodes = {match.graph.get_nodes()}\n")

print("Find last Conv2D:")
matches = gm.match("Conv2D#~>(.[exConv])*->$")
print(f"Found {len(matches)} matches!\n")

for match in matches:
    print(f"root node = {match.graph.root_node()}")
    print(f" ↳ matched nodes = {match.graph.get_nodes()}\n")

Find first Conv2D:
Found 1 matches!

root node = Node(name='conv1', optype='Conv2D', parents: [1, 1, 1], children: [[1]])
 ↳ matched nodes = {Node(name='conv1', optype='Conv2D', parents: [1, 1, 1], children: [[1]]), Node(name='dataProvider', optype='Producer', children: [[1]])}

Find last Conv2D:
Found 1 matches!

root node = Node(name='conv5_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1, 1]])
 ↳ matched nodes = {Node(name='relu5', optype='ReLU', parents: [1], children: [[1]]), Node(name='conv5_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1, 1]]), Node(name='add2', optype='Add', parents: [1, 1], children: [[]])}

Note that to find the last Conv operator, one must yet again use the ~ edge modifier, because conv5_conv has two nodes connected to its first output!

The intermediate nodes are captured as well, because they are part of the query (.[exConv]), but the expected result is simply the root node in this case.

Match alternative blocks#

Alternatives can be matched using the | separator. For example, to match either Conv2D or ReLU followed by Add, you can use the following query:

[84]:

matches = aidge_core.SinglePassGraphMatching(model).match("(Conv2D|ReLU)->Add")
print(f"Found {len(matches)} matches!\n")

for match in matches:
    print(f"root node = {match.graph.root_node()}")
    print(f" ↳ matched nodes = {match.graph.get_nodes()}\n")

Found 2 matches!

root node = Node(name='relu5', optype='ReLU', parents: [1], children: [[1]])
 ↳ matched nodes = {Node(name='add2', optype='Add', parents: [1, 1], children: [[]]), Node(name='relu5', optype='ReLU', parents: [1], children: [[1]])}

root node = Node(name='conv4_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1]])
 ↳ matched nodes = {Node(name='conv4_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1]]), Node(name='add', optype='Add', parents: [1, 1], children: [[1]])}

The | separator can be used for complex, full sequences, alternatives. In the following example, one matches the first and last Conv2D or FC operators with a weights Producer:

[85]:

gm = aidge_core.SinglePassGraphMatching(model)
gm.add_node_lambda("exParam", lambda node: node.type() != "FC" and node.type() != "Conv2D")

matches = gm.match("(((FC#|Conv2D#)<-(.[exParam])*<-$)|((FC#|Conv2D#)->(.[exParam])*->$));(FC#|Conv2D#)<1-Producer#")
print(f"Found {len(matches)} matches!\n")

for match in matches:
    print(f"root node = {match.graph.root_node()}")
    print(f" ↳ matched nodes = {match.graph.get_nodes()}\n")

Found 1 matches!

root node = Node(name='conv1', optype='Conv2D', parents: [1, 1, 1], children: [[1]])
 ↳ matched nodes = {Node(name='conv1', optype='Conv2D', parents: [1, 1, 1], children: [[1]]), Node(name='conv1_w', optype='Producer', children: [[1]]), Node(name='dataProvider', optype='Producer', children: [[1]])}

An alternative list of anchors (FC#|Conv2D#) is used in this example, which is allowed as long as it remains consistent accross the query.

Match parallel blocks#

It is possible to match branches with either multiple sequences and anchors, or using the & separator. Both example below are equivalent:

[86]:

matches = aidge_core.SinglePassGraphMatching(model).match("ReLU~*>((Pad2D->Conv2D-*>Add#)&Add#)")
print(f"Found {len(matches)} matches!\n")

for match in matches:
    print(f"root node = {match.graph.root_node()}")
    print(f" ↳ matched nodes = {match.graph.get_nodes()}\n")

matches = aidge_core.SinglePassGraphMatching(model).match("ReLU#~*>Pad2D->Conv2D-*>Add#;ReLU#~*>Add#")
print(f"Found {len(matches)} matches!\n")

for match in matches:
    print(f"root node = {match.graph.root_node()}")
    print(f" ↳ matched nodes = {match.graph.get_nodes()}\n")

Found 1 matches!

root node = Node(name='relu3', optype='ReLU', parents: [1], children: [[1, 1]])
 ↳ matched nodes = {Node(name='conv4_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1]]), Node(name='add', optype='Add', parents: [1, 1], children: [[1]]), Node(name='relu3', optype='ReLU', parents: [1], children: [[1, 1]]), Node(name='conv4_pad', optype='Pad2D', parents: [1], children: [[1]])}

Found 1 matches!

root node = Node(name='relu3', optype='ReLU', parents: [1], children: [[1, 1]])
 ↳ matched nodes = {Node(name='conv4_pad', optype='Pad2D', parents: [1], children: [[1]]), Node(name='relu3', optype='ReLU', parents: [1], children: [[1, 1]]), Node(name='conv4_conv', optype='Conv2D', parents: [1, 1, 1], children: [[1]]), Node(name='add', optype='Add', parents: [1, 1], children: [[1]])}

Graph manipulation#

Aidge provides some convenient facilities to manipulate the graph in one-liner methods.

Factorization#

Using graph matching, it is possible to match a sub-graph and replace it with a single meta-operator, containing the matched sub-graph, using the fuse_to_metaops recipe:

[87]:

aidge_core.fuse_to_metaops(model, "Conv2D#->ReLU?;Conv2D#<-Pad2D?", "PaddedConvReLU")

model.save("graph_fused")
tuto_utils.visualize_mmd("graph_fused.mmd")

Notice: the 0-th Parent of the child node relu5 (of type ReLU) already existed
Filling a Tensor already attributed.
You are replacing an existing parent for node relu5 (of type ReLU).
Notice: the 1-th Parent of the child node add2 (of type Add) already existed
Filling a Tensor already attributed.
You are replacing an existing parent for node add2 (of type Add).
Notice: the 1-th Parent of the child node add (of type Add) already existed
Filling a Tensor already attributed.
You are replacing an existing parent for node add (of type Add).
Notice: the 0-th Parent of the child node conv4_pad (of type Pad2D) already existed
Filling a Tensor already attributed.
You are replacing an existing parent for node conv4_pad (of type Pad2D).
Notice: the 0-th Parent of the child node add (of type Add) already existed
Filling a Tensor already attributed.
You are replacing an existing parent for node add (of type Add).
Notice: the 0-th Parent of the child node conv2_pad (of type Pad2D) already existed
Filling a Tensor already attributed.
You are replacing an existing parent for node conv2_pad (of type Pad2D).
Notice: the 0-th Parent of the child node  (of type PaddedConvReLU) already existed
Filling a Tensor already attributed.
You are replacing an existing parent for node  (of type PaddedConvReLU).
Replaced 5 (out of 5) matching sub-graph with meta operators

One can see that the last ReLu (relu5) was not factorized, because the preceding Conv’s output has multiple siblings. Using the ~ edge modifier would have led to an erroneous graph because the edge to add2 would have been lost.

Graph fusion can be recursive, with multiple hierarchical levels. For example, in the following code, we also move the weights and bias Producer in the PaddedConvReLU meta-operator, matching the just created meta-operator type PaddedConvReLU.

[88]:

aidge_core.fuse_to_metaops(model, "PaddedConvReLU#<1-Producer;PaddedConvReLU#<2-Producer?", "PaddedConvReLU_Prod")

model.save("graph_fused")
tuto_utils.visualize_mmd("graph_fused.mmd")

Notice: the 1-th Parent of the child node add (of type Add) already existed
Filling a Tensor already attributed.
You are replacing an existing parent for node add (of type Add).
Notice: the 0-th Parent of the child node  (of type PaddedConvReLU) already existed
Filling a Tensor already attributed.
You are replacing an existing parent for node  (of type PaddedConvReLU).
Notice: the 0-th Parent of the child node relu5 (of type ReLU) already existed
Filling a Tensor already attributed.
You are replacing an existing parent for node relu5 (of type ReLU).
Notice: the 1-th Parent of the child node add2 (of type Add) already existed
Filling a Tensor already attributed.
You are replacing an existing parent for node add2 (of type Add).
Notice: the 0-th Parent of the child node add (of type Add) already existed
Filling a Tensor already attributed.
You are replacing an existing parent for node add (of type Add).
Notice: the 0-th Parent of the child node  (of type PaddedConvReLU) already existed
Filling a Tensor already attributed.
You are replacing an existing parent for node  (of type PaddedConvReLU).
Notice: the 0-th Parent of the child node  (of type PaddedConvReLU_Prod) already existed
Filling a Tensor already attributed.
You are replacing an existing parent for node  (of type PaddedConvReLU_Prod).
Replaced 5 (out of 5) matching sub-graph with meta operators

Expansion#

The reserve operation is expand_metaops, which can be recursive or not (default):

[89]:

aidge_core.expand_metaops(model)

# Display static scheduling
model.save("graph")
tuto_utils.visualize_mmd("graph.mmd")

Notice: the 0-th Parent of the child node add (of type Add) already existed
Filling a Tensor already attributed.
You are replacing an existing parent for node add (of type Add).
Notice: the 1-th Parent of the child node add (of type Add) already existed
Filling a Tensor already attributed.
You are replacing an existing parent for node add (of type Add).
Notice: the 0-th Parent of the child node  (of type PaddedConvReLU) already existed
Filling a Tensor already attributed.
You are replacing an existing parent for node  (of type PaddedConvReLU).
Notice: the 0-th Parent of the child node  (of type PaddedConvReLU_Prod) already existed
Filling a Tensor already attributed.
You are replacing an existing parent for node  (of type PaddedConvReLU_Prod).
Notice: the 0-th Parent of the child node  (of type PaddedConvReLU) already existed
Filling a Tensor already attributed.
You are replacing an existing parent for node  (of type PaddedConvReLU).
Notice: the 0-th Parent of the child node relu5 (of type ReLU) already existed
Filling a Tensor already attributed.
You are replacing an existing parent for node relu5 (of type ReLU).
Notice: the 1-th Parent of the child node add2 (of type Add) already existed
Filling a Tensor already attributed.
You are replacing an existing parent for node add2 (of type Add).