Graph isomorphism

This notebook illustrates the Weisfeiler-Lehman test of isomorphism.

from IPython.display import SVG
import numpy as np
from sknetwork.data import house
from sknetwork.topology import color_weisfeiler_lehman, are_isomorphic
from sknetwork.visualization import visualize_graph

Graph labeling

graph = house(metadata=True)
adjacency = graph.adjacency
position = graph.position

labels = color_weisfeiler_lehman(adjacency)

image = visualize_graph(adjacency, position, labels=labels)
SVG(image)

# first iteration
labels = color_weisfeiler_lehman(adjacency, max_iter=1)

image = visualize_graph(adjacency, position, labels=labels)
SVG(image)

Weisfeiler-Lehman test

adjacency1 = house()

n = adjacency1.indptr.shape[0] - 1
reorder = list(range(n))
np.random.shuffle(reorder)
adjacency2 = adjacency1[reorder][:, reorder]

are_isomorphic(adjacency1, adjacency2)

True