[GraphRegex] Add ? quantifier and related issue

Right now, the "?" quantifier (meaning 0 or 1) is not supported, but it would be very useful in practice (much more than * actually).

Also, the following query does not seem to work:

Pad*->Conv->ReLU*

See unit test Test_example.cpp to reproduce the issue.

Same issue with fuseMulAdd, when changing the query from MatMul -> Add to MatMul -> Add*, the first set of nodes in the unit test is not matched!

assigned to @vincentlorrain

mentioned in issue #85 (closed)

changed the description

added IssueBug 🐛 AddFeature + 1 deleted label

There is indeed a problem because in reality, the first match should not be valid.

the paddedConv is not only a conv but

   graph TD;
   Pad--> Conv
   Producer_b--> Conv
   Producer_w--> Conv
   Conv --> ReLU

the query will be Pad->Conv#->ReLU;Producer->Conv#;Producer->Conv#

the error comme from FsmEdgeUnique ...But the correction shows that most uses of graph regex are incorrect, and there are numerous corrections to be made.

I don't think we should have to specify an exhaustive pattern of all the inputs: Pad->Conv#->ReLU should be enough to match your graph example. I think that would be more the expected behavior from users... unless there is a fundamental reason not to!

The fundamental reason is that you need to describe exactly what you want in order to search for it in a graph. There's no reason why:

Conv = Producer->Conv#;Producer->Conv#

it needs to be well defined somewhere, either it's defined in the conv operator during definition, or it must be defined in the query itself.

But there can be several cases that should be IMO handled transparently for the user:

• Several types of node could be connected to some inputs, the user does not necessarily care about the type (for example for the weights, it could be a Producer, but it could an other Operator type);
• Some inputs can be optional, like bias, in which care the user does not care if there is an input or not;
• User may only care about a specific input index, like 0 for Conv, which is the data input.

Typically, what would be the pattern to match Pad->Conv regardless of inputs 1 and 2 of Conv? Is there a way in this case also to enforce that Pad should match only input 0 of Conv?

There's no definitive answer; it's a matter of specifying how graph regexes work.

Indeed, we can limit the definition of the number of parent and child connections of a node to activation connections, although I can't see concretely how to do this in all cases (for example, with layers per element). By doing so, it's possible to reduce the size of the queries, which can be seen as simplifying the user interface. However, this is at the expense of the ability to match all parts of the computational graph, which could be limiting in some cases too.

We could also implement a hybrid mode in which the user could choose between these two modes, and it would be necessary to document this new possibility of use.

Personally, I have no opinion on the matter.

What I would suggest is to have a mode that allows matching a pattern even if additionnal input/output connections exists to the nodes in the pattern, regardless of the input connection type. This should probably be the default mode for the user, since this seems to be the expected behavior even in current tests and tutorials, as you said...

marked this issue as blocking #85 (closed)

added StatusWIP label

mentioned in merge request !106 (closed)

see !106 (closed)

closed

mentioned in merge request !138 (merged)