Monomorphism and Isomorphism

There is an important distinction between subgraph isomorphism and subgraph monomorphism. In this page we will discuss both, but you should not treat this as a formal mathematical guide/proof/definition. For that, I recommend the Wikipedia pages on Monomorphism and Isomorphism.

If you've been using another search algorithm and you can't figure out why you're getting the wrong number of search results (or maybe no query results at all!), you may have found the culprit.

Interactive examples in Binder:

High-Level Differences

Subgraph isomorphisms and subgraph monomorphisms are similar in that they are both mappings of a subgraph structure to subsets of vertices in a host graph. But whereas monomorphism mappings occur ANY time the subgraph appears, isomorphisms relate ONLY to when the induced subgraph of the match in the host is a perfect match to the motif.

Let's look at an example. Suppose we have the following host graph:

And the following motif:

If we are searching for monomorphisms, then both of these mappings are valid (this is not an exhaustive list of matches!):

But if we are searching for isomorphisms, this is NOT a valid mapping, because there is an edge between motif nodes that we didn't ask for explicitly:

Implementation Differences

Depending on the underlying implementation, it can be much faster to search for isomorphisms than monomorphisms because the type of edge illustrated above can help disqualify a potential match earlier in the process. But this is highly dependent upon the subgraph search implementation, and you may find very little practical difference in time-cost in most graphs.

When performing searches using DotMotif, the default behavior is to search for monomorphisms. You can explicitly request isomorphism mappings from certain Executors: For more details, check the documentation on the Executor.

Considerations for Motif Search

When looking for motifs in certain application areas such as connectomics, the distinction between isomorphisms and monomorphisms can become very important. For example, there is a big difference between saying "these two neurons may share a synapse" (monomorphism) and "I know for certain that these neurons do NOT share a synapse" (isomorphism). When the case is mixed, i.e., you might know about some edges but not others, DotMotif's syntax has a "no-edge" operator that lets you stay agnostic about most edges, but fix the behavior of others:

A -> B # There MUST BE an edge between A and B
B -> C # There MUST BE an edge between B and C
A !> C # There CANNOT be an edge from A to C
# There CAN be an edge from C to A

This is recommended in most cases, as it enables you to be as specific as you can be, but not more. In other words, DotMotif will optimize your motif query based upon all available information, and if you specify "no-edge" lines like this, you will get a more performant query, regardless of whether you've requested isomorphisms or monomorphisms.

Further Reading

• Stack Overflow: Subgraph monomorphism in NetworkX
• Stack Overflow: What's the Difference Between ...