Weisfeiler-Lehman Networkx function for different k-levels

Question

I am trying to use the Weisfeiler-Lehman (WL) algorithm implemented in networkx library to check if two graphs are isomorphic.

My graphs are the following:

import networkx as nx
g1 = nx.Graph()
g1.add_edges_from([(1, 2), (1, 4), (2, 4), (2, 5), (3, 5), (3, 6), (5, 6)])
g2 = nx.Graph()
g2.add_edges_from([(1, 2), (1, 4), (2, 3), (2, 5), (3, 6), (4, 5), (5, 6)])

g1_hash = nx.weisfeiler_lehman_graph_hash(g1)
g2_hash = nx.weisfeiler_lehman_graph_hash(g2)
# g1_hash and g2_hash are equal and they should not be since graphs are not isomorphic

# there is another implementation in networkx to check if two graphs 
# are isomorphic and there it produces the correct answer which is False
nx.is_isomorphic(g1, g2)

They are not isomorphic. However, if I try to go to higher levels of the WL algorithm it should produce different hashes for the given graphs. I don't know how to do that and I couldn't find something in the networkx documentation.

Answer 1

The Weisfeiler-Lehman algorithm produces for each graph a canonical form. If the canonical forms of two graphs are not equivalent, then the graphs are definitively not isomorphic. However, it is possible for two non-isomorphic graphs to share a canonical form, so this test alone cannot provide conclusive evidence that two graphs are isomorphic.

This is stated in the NetworkX documentation too:

Hashes are identical for isomorphic graphs and strong guarantees that non-isomorphic graphs will get different hashes

Therefore, it's still possible to have two identical hashes even if two graphs are not isomorphic.