Graph isomorphism

This notebook illustrates the Weisfeiler-Lehman test of isomorphism.

[1]:

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

Graph labeling

[2]:

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

[3]:

weisfeiler_lehman = WeisfeilerLehman()
labels = weisfeiler_lehman.fit_transform(adjacency)

[4]:

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

[4]:

../../_images/tutorials_topology_weisfeiler_lehman_6_0.svg

[5]:

# first iteration
weisfeiler_lehman = WeisfeilerLehman(max_iter=1)
labels = weisfeiler_lehman.fit_transform(adjacency)

[6]:

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

[6]:

../../_images/tutorials_topology_weisfeiler_lehman_8_0.svg

Weisfeiler-Lehman test

[7]:

adjacency_1 = house()

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

are_isomorphic(adjacency_1, adjacency_2)

[7]:

True