Graph Regular Expression#
Graph Regular expression is a powerful tool inspired by regular expressions. It is designed to express complex graph structures, much like regular expressions do for character strings.
This tutorial demonstrate the usage of the Graph Regular Expression to perform graph matching in Aidge.
It is organized as follows : - Section Requirements covers the requirements to run this tutorial - Section Graph Regex Flow explains the user pipeline to use Graph Regex - Section Query presents how to describe different graph patterns
Requirements#
Python packages : aidge_core, matplotlib, numpy
Define model visualization function
[1]:
!pip install --quiet matplotlib
!pip install --quiet numpy
[notice] A new release of pip is available: 24.1 -> 24.2
[notice] To update, run: pip install --upgrade pip
[notice] A new release of pip is available: 24.1 -> 24.2
[notice] To update, run: pip install --upgrade pip
[2]:
import base64
from IPython.display import Image, display
import matplotlib.pyplot as plt
def visualize_mmd(path_to_mmd):
with open(path_to_mmd, "r") as file_mmd:
graph_mmd = file_mmd.read()
graphbytes = graph_mmd.encode("ascii")
base64_bytes = base64.b64encode(graphbytes)
base64_string = base64_bytes.decode("ascii")
display(Image(url=f"https://mermaid.ink/img/{base64_string}"))
Graph Regex Flow#
The GraphRegex class enable to perform graph transformations. It takes as inputs : - A GraphView - Queries : express one or more graph pattern descriptions to find in the GraphView
To have more information on the query, i.e. graph descriptions, please refer to the following slides to open in your browser : - Basic concepts of Graph Regular Expression - Quantifier
For more information, please refer to the User Guide on graph transformation.
Query#
This section presents several examples to express different graph patterns : sequential, parallel, and advanced node testing.
Sequential graph#
Create a sequential graph
Describe a pattern with graph Regular Expression
Match the describe pattern
[3]:
import aidge_core
model = aidge_core.sequential([aidge_core.MatMul(name="MatMul0"),
aidge_core.Add(2, name="Add0"),
aidge_core.ReLU(name="ReLU0"),
aidge_core.MatMul(name="MatMul1"),
aidge_core.Add(2, name="Add1"),
aidge_core.ReLU(name="ReLU1")])
model.save("mySequentialModel")
visualize_mmd("mySequentialModel.mmd")
[4]:
graph_regex = aidge_core.GraphRegex()
graph_regex.set_node_key("A", "getType($) =='Add'")
graph_regex.set_node_key("B", "getType($) =='ReLU'")
graph_regex.add_query("A -> B")
all_match = graph_regex.match(model)
print('Number of match : ', len(all_match))
Number of match : 2
In this case, we have two matches. Each match contains : - The associated query. In this example : “A->B” - The list containing the start nodes. In this example : [Add0] - The set containing all the matched nodes. In this example : {Add0, ReLU0}
Let’s visualize the matches :
[5]:
for i, match in enumerate(all_match):
print('Match ', i ,' associated to query : ', match.get_query())
print('The start node :', match.get_start_node()[0].name())
print('All the matched nodes :')
for n in match.get_all():
print('\t', n.name())
Match 0 associated to query : A -> B
The start node : Add0
All the matched nodes :
Add0
ReLU0
Match 1 associated to query : A -> B
The start node : Add1
All the matched nodes :
ReLU1
Add1
Parallel graph#
Create a graph with parallel branches
Describe a pattern with graph Regular Expression
Match the describe pattern
[6]:
import aidge_core
model = aidge_core.sequential([aidge_core.MatMul(name="MatMul0"),
aidge_core.Add(2, name="Add0"),
aidge_core.ReLU(name="ReLU0"),
aidge_core.parallel([aidge_core.Conv2D(1, 1, [3, 3], name="Conv0"), aidge_core.Conv2D(1, 1, [3, 3], name="Conv1")]),
aidge_core.Add(2, name="Add1"),
aidge_core.ReLU(name="ReLU1")])
model.save("mySequentialModel")
visualize_mmd("mySequentialModel.mmd")
When applying regular expression concepts to graphs, we find ourselves dealing with parallel branches. To address this, we express the graph by decomposing it into sequences. This decomposition involves defining two types of nodes: - common nodes, which reference the same node across multiple sequences : token “#” - unique nodes, as the name suggests, that are exclusive to a particular sequence.
Let’s try to match the ReLU followed by the two parallel convolutions :
[7]:
graph_regex = aidge_core.GraphRegex()
graph_regex.set_node_key("A", "getType($) =='ReLU'")
graph_regex.set_node_key("B", "getType($) =='Conv'")
graph_regex.add_query("A# -> B; A# -> B")
all_match = graph_regex.match(model)
print('Number of match : ', len(all_match))
for i, match in enumerate(all_match):
print('Match ', i ,' associated to query : ', match.get_query())
print('The start node :', match.get_start_node()[0].name())
print('All the matched nodes :')
for n in match.get_all():
print('\t', n.name())
Number of match : 1
Match 0 associated to query : A# -> B; A# -> B
The start node : ReLU0
All the matched nodes :
Conv1
Conv0
ReLU0
Quantifiers#
Quantifiers are tokens that specify the number of occurrences of a preceding element in the pattern. The supported quantifiers in graph regular expressions are : - “+” : one or more - “*” : zero or more
Using the quantifiers, the graph regular expression can represent an ensemble of patterns. For example “Conv+” represents sequences of at least one convolution.
In this subsection : - Create a sequential graph - Describe a pattern with graph Regular Expression using quantifier ‘one or more’ : ‘+’ - Match the describe pattern
[8]:
import aidge_core
model = aidge_core.sequential([aidge_core.MatMul(name="MatMul0"),
aidge_core.Add(2, name="Add0"),
aidge_core.ReLU(name="ReLU0"),
aidge_core.Conv2D(1, 1, [3, 3], name="Conv0"),
aidge_core.Conv2D(1, 1, [3, 3], name="Conv1"),
aidge_core.Conv2D(1, 1, [3, 3], name="Conv2")])
model.save("mySequentialModel")
visualize_mmd("mySequentialModel.mmd")
Let’s try to match the ReLU0 followed by at least one convolution :
[9]:
graph_regex = aidge_core.GraphRegex()
graph_regex.set_node_key("A", "getType($) =='ReLU'")
graph_regex.set_node_key("B", "getType($) =='Conv'")
graph_regex.add_query("A -> B+")
all_match = graph_regex.match(model)
print('Number of match : ', len(all_match))
for i, match in enumerate(all_match):
print('Match ', i ,' associated to query : ', match.get_query())
print('The start node :', match.get_start_node()[0].name())
print('All the matched nodes :')
for n in match.get_all():
print('\t', n.name())
Number of match : 1
Match 0 associated to query : A -> B+
The start node : ReLU0
All the matched nodes :
Conv1
ReLU0
Conv2
Conv0
Advanced node testing#
So far, the described graph patterns were based on the topology of the graph and the type of nodes. Graph Regular expression allows to perform any test on the node by supporting the function calls of the given node.
Create a sequential graph
Describe a pattern with graph Regular Expression using advanced testing on the dimension of the convolution kernels.
Match the describe pattern
[10]:
import aidge_core
conv = aidge_core.Conv2D(1, 1, [7, 7], name="C")
print(conv.get_operator().attr.kernel_dims == [7,7])
print(conv.type())
model = aidge_core.sequential([aidge_core.Conv2D(1, 1, [7, 7], name="Conv0"),
aidge_core.Conv2D(1, 1, [5, 5], name="Conv1"),
aidge_core.Conv2D(1, 1, [3, 3], name="Conv2"),
aidge_core.Conv2D(1, 1, [5, 5], name="Conv3"),
aidge_core.Conv2D(1, 1, [7, 7], name="Conv4")])
model.save("mySequentialModel")
visualize_mmd("mySequentialModel.mmd")
True
Conv
Let’s try to find the convolutions with kernel size 3 or 5.
First define your own custom testing fonctions :
[11]:
def test_kernel_3(node):
b = False
if (node.type() == "Conv") :
b = node.get_operator().attr.kernel_dims == [3,3]
return b
def test_kernel_5(node):
b = False
if (node.type() == "Conv") :
b = node.get_operator().attr.kernel_dims == [5,5]
return b
Then register it in the graph regex and add the associated queries :
[12]:
graph_regex = aidge_core.GraphRegex()
# Register the custom testing functions
graph_regex.set_node_key("testk3", test_kernel_3)
graph_regex.set_node_key("testk5", test_kernel_5)
graph_regex.set_node_key("Convk3", "testk3($)==true")
graph_regex.set_node_key("Convk5", "testk5($)==true")
#Add the associated queries
graph_regex.add_query("Convk3")
graph_regex.add_query("Convk5")
all_match = graph_regex.match(model)
print('Number of match : ', len(all_match))
for i, match in enumerate(all_match):
print('Match ', i ,' associated to query : ', match.get_query())
print('The start node :', match.get_start_node()[0].name())
print('All the matched nodes :')
for n in match.get_all():
print('\t', n.name())
Number of match : 3
Match 0 associated to query : Convk3
The start node : Conv2
All the matched nodes :
Conv2
Match 1 associated to query : Convk5
The start node : Conv1
All the matched nodes :
Conv1
Match 2 associated to query : Convk5
The start node : Conv3
All the matched nodes :
Conv3