Speaker
Prof.
Elitza Maneva
(University of Barcelona)
Description
The Weisfeiler-Lehman (WL) algorithm is an iterative
algorithm for certifying that two graphs are not isomorphic.
At every iteration a label is generated for each vertex based
on the mutliset of labels of its neighbors at the previous
iteration. The starting label is the degree of the vertex.
When a fixed point is reached the multisets of labels of the
vertices of the two graphs are compared. These are different
only if the graphs are not isomorphic. In the k level version
of the WL algorithm a label is instead generated for every k-
tuple of vertices.
We compare the WL algorithm to a hierarchy of linear
programming relaxations of graph isomorphism generated
by the Sherali Adams lift-and-project method. It was
already known that two graphs are fractionally isomorphic
(i.e. there is a doubly stochastic matrix that converts one
graph into the other) if and only if they are not
distinguished by the first level of the WL algorithm. We
show that, furthermore, the levels of the Sherali-Adams
hierarchy interleave in power with the higher levels of the
WL algorithm.
Primary author
Prof.
Elitza Maneva
(University of Barcelona)
