Incorrect/Inconsistent subgraph identification when using get_subisomorphisms_vf2?

Usage
1 
from igraph import Graph

G1 = Graph()
G2 = Graph()

G1.add_vertices(5)
G2.add_vertices(4)

G1.add_edge(0, 1)
G1.add_edge(1, 2)
G1.add_edge(2, 3)
G1.add_edge(3, 0)
G1.add_edge(3, 4)

G2.add_edge(0, 1)
G2.add_edge(1, 2)
G2.add_edge(2, 3)

isomorphisms = set()
for i in G1.get_subisomorphisms_vf2(G2):
    isomorphisms.add(tuple(sorted(i)))
print(isomorphisms)

If you run the above code you end up with 3 unique subisomorphisms of G2 on G1. However, there should only be two (you will get this result if you use the VF2 implementation found in networkx). What appears to be happening is that it is finding that G2 a line of 4 vertices is isomorphic to the subgraph on G1 given by vertices (0, 1, 2, 3), but this is a square. I find this behavior very confusing as igraph correctly says a square and G2 are not isomorphic yet they somehow are subgraph ismorphisms? Does anyone have any insight into why this is happening and if there is a workaround/fix? I’d like to figure this out so I can keep using igraph and don’t have to go with the slower option of networkx.

2

The result is correct, and consistent with the customary use of the term “subgraph” in graph theory. 0-1-2-3 is a subgraph of G1, but it is not an induced subgraph. If you need only induced subgraphs, use get_subisomorphisms_lad() with induced=True.

Here’s a visual check of the result with Mathematica:

image
image1412×1188 54.9 KB

3

Ah ok, my bad. I was thinking strictly in terms of induced subgraphs.

Unfortunately, in my use case I can have weighted edges that effect the isomorphisms which only the VF2 algorithm can handle (unless I am missing something in the docs).

Thanks for your quick response.

4

You mean coloured edges? You can construct an appropriate domain parameter for LAD to handle those.

I would like to have an alternative interface for LAD that takes vertex and edge colours directly, as I did in igraph’s Mathematica interface, but we’re not there yet. So you’ll have to construct the domain manually for now.

5

I’m sorry, I responded in too much of a hurry. It may not be possible to handle edge colours with LAD, only vertex colours.

However, you can filter the matches returns by VF2 and keep only induced subgraphs.

I don’t have the time to write an example now, or even to check if the most convenient functions are exposed in Python … in C I’d use igraph_induced_subgraph_edges() to count if the induced subgraph has as many edges as the pattern. I’m sure Python should have function to get an induced subgraph at least as a graph, if not a list of edges (which is more performant).

6

Thanks for the idea! That should totally work.

7

Feel free to open an issue for adding support for finding induced-only subgraphs with VF2 here:

Doing the filtering in C would be more performant than relying on Python for this. It won’t be as performant as modifying VF2 for this purpose, but better than nothing.