could_be_isomorphic returns False for an isomorphic graph on 3.2

[martinfleis]

Current Behavior

We have noticed a new failure on downstream testing using isomorphic checks when updating to networkx 3.2. We know that the graph we check is isomorphic, yet nx.could_be_isomorphic started returning False, which I believe is a regression in the latest release.

Expected Behavior

nx.could_be_isomorphic should return True for an isomorphic graph

Steps to Reproduce

import networkx as nx

left = nx.read_gexf("left.gexf")
right = nx.read_gexf("right.gexf")
assert nx.is_isomorphic(left, right)
nx.could_be_isomorphic(left, right) # should be True but is False

Environment

Python version: 3.9 - 3.12
NetworkX version: 3.2

Additional context

The gefx files:

Archive.zip

[dschult]

Thanks for reporting this!!
Is the nxleft and nxright in your example code (in the assert statement) supposed to be left and right?

Also, can you describe how you know these are isomorphic graphs?
Do you have the isomorphism? Or is that result based on previous networkx results?

[martinfleis]

Is the nxleft and nxright in your example code (in the assert statement) supposed to be left and right?

Yes, sorry!

Both left and right come from the same edge list, only ids are remapped. It is the same graph and it is isomorphic as proved by the assertion. Something has changed in the could_be_isomorphic function that it started returning False (which is wrong).

[dschult]

I can verify that could_be_isomorphic and fast_could_be_isomorphic return apparently false results for this case. And I've traced it to the computation of triangles. One node is only connected to itself by a self-loop (node "46" in right which is isomorphic to node "8" in left). Those nodes are getting a different number of triangles in the two graphs when using nx.triangles. The self-loop is the only edge involving those nodes in the graphs.

`nx.triangles was changed 3 months ago in #6258 so I think an error was introduced there -- something about self-loops but even worse, something that counts the triangles differently depending on relabeling the nodes.

[dschult]

Thanks soo much for reporting this bug. It would have been hard for me to find for sure.
The error in triangles comes down to using n is not node to rule out self-loops instead of the correct n != node.

I guess the result is: we should never use is to compare nodes. Always ==.

[martinfleis]

Wow, that is a tricky one. Thanks for debugging!