Question on fuzzy path matching ---- matching arbitrary number and type of nodes in path

Dear community,

I encountered a problem when I trying with fuzzy path matching. I want to match arbitrary number of any type of node (i.e., node can be any type, and the path length is vary, using wildcard(None)) between a parent node and a post-dominate child node. One sample computation want to match is:

input1    input2 
     \      / 
      conv2d   input3
           \  /
           add    input4
              \    /
             multiply
                |
              relu

I am trying to match this pattern using a fuzzy path with only parent and child node specified. Match is successful when the parent node is add and child node is relu

# parent node is add, child node is nn.relu
fuzzy_pat = dominates(is_op('add')(wildcard(), wildcard()), wildcard()(None), is_op('nn.relu')(wildcard())) 
input1 = relay.var("input1")
input2 = relay.var("input2")
input3 = relay.var("input3")
input4 = relay.var("input4")

conv2d = relay.op.nn.conv2d(input1, input2)
buf1 = conv2d + input3
buf2 = relay.op.multiply(buf1, input4)
relu = relay.op.nn.relu(buf2)

assert fuzzy_pat.match(relu) # assert True

However, the matching is failed when the parent node is conv2d:

# parent node is conv2d, child node is nn.relu
fuzzy_pat = dominates(is_op('nn.conv2d')(wildcard(), wildcard()), wildcard()(None), is_op('nn.relu')(wildcard())) 
input1 = relay.var("input1")
input2 = relay.var("input2")
input3 = relay.var("input3")
input4 = relay.var("input4")

conv2d = relay.op.nn.conv2d(input1, input2)
buf1 = conv2d + input3
buf2 = relay.op.multiply(buf1, input4)
relu = relay.op.nn.relu(buf2)

assert fuzzy_pat.match(relu) # assert is False

I did not notice any fundamental differences between above two cases, why the second matching is failed and how could I match arbitrary number and type of nodes between a parent node and a post-dominate child node?

Many thanks in advance~!

cc @mbrookhart He may have some insights.

Ooh, I haven’t debugged a problem like this with the pattern matcher in like a year. :smiley: I thought it was stable. This looks like a bug.

I have some freetime today, I’ll try to reproduce and debug.

Okay, I’m remembering how this works. The issue here comes in the definition of the domination pattern. In your pattern, the nodes I’ve circled in green count as part of the domination, they’re in a direct line between conv2d and relu, but the second inputs to add and multiply are taking data from outside the domination relationship, so they don’t match, and that breaks the whole pattern.

You can see the kinds of patterns we tested this on here: Pattern Matching in Relay — tvm 0.8.dev0 documentation

@jroesch I don’t remember if we had a strong reason to dis-allow branching domination like this, do you?