If you are using networkx.isomorphism.GraphMatcher to test whether a smaller pattern graph exists inside a larger target graph, you might occasionally run into a confusing scenario: you can clearly identify a valid mapping of nodes and edges by hand, yet NetworkX returns False.

The Root Cause: Induced vs. Non-Induced Subgraph Isomorphism

The primary reason NetworkX reports False in these cases comes down to the difference between induced subgraph isomorphism and non-induced (monomorphic) subgraph isomorphism.

By default, NetworkX's GraphMatcher uses the VF2 algorithm to test for induced subgraph isomorphism:

  • Induced Subgraph Isomorphism: A target node subset matches the pattern graph if and only if all edges between those nodes in the target graph also exist in the pattern graph. No extra edges are allowed between the matched target nodes.
  • Non-Induced Subgraph Isomorphism (Monomorphism): The pattern graph's edges must exist between the corresponding target nodes, but the target graph is allowed to have extra edges between those target nodes.

Analyzing the Example

Consider the proposed mapping between target nodes and pattern nodes:

  • Target 0 → Pattern h1
  • Target 1 → Pattern e1
  • Target 2 → Pattern c1
  • Target 4 → Pattern s1
  • Target 7 → Pattern u1

Looking at the pattern graph edges:

  • ('s1', 'e1') maps to target edge (4, 1) — Present
  • ('s1', 'u1') maps to target edge (4, 7) — Present
  • ('e1', 'h1') maps to target edge (1, 0) — Present
  • ('e1', 'c1') maps to target edge (1, 2) — Present

While all required edges exist in the target graph, look at the extra edges between the target subset {0, 1, 2, 4, 7} in the target graph:

  • The edge (4, 0) exists in the target graph, but there is no edge between s1 and h1 in the pattern graph.
  • The edge (4, 2) exists in the target graph, but there is no edge between s1 and c1 in the pattern graph.

Because of these extra edges ((4,0) and (4,2)), the target subset is not an induced subgraph of the pattern graph, causing subgraph_is_isomorphic() to return False.

How to Test for Non-Induced (Monomorphic) Subgraph Isomorphism

If you need to find subgraphs regardless of extra edges in the target graph, you are looking for graph monomorphism. NetworkX provides submodules and alternative approaches to handle this.

Solution 1: Using NetworkX ISMAGS Algorithm

NetworkX includes the ISMAGS algorithm implementation which supports non-induced subgraph matching natively: