Testing if two graphs are isomorphic

The usage of graphs as a data structure is not new, and in recent years, several advances in the area of Deep Learning for graphs happened, which created a new area of research that has been yielding very positive results.

These Deep Learning approaches usually take the form of Graph Neural Networks (GNNs). However, theoretical understanding of these GNNs is still incipient and largely unknown by practitioners that are not aware of the most recent research.

One interesting theoretical finding on GNNs states that Message-Passing networks (which is essentially how most architectures are implemented) have their expressive power upper-bounded by the Weisfeiler-Lehman Isomorphism Test (WL-Test) [1]. This has some very interesting implications.

Aiming to improve the understanding of this kind of limitation of the GNNs, this post will explore the WL-Test, how it relates to GNNs, how one can expand the test to be more expressive, and finally how these tests can be implemented in Python.

The notebooks with the code for this post are available on Kaggle and on my Github.

Graph Isomorphism

The first step is to understand what is a graph isomorphism, since the WL-Test, as the name suggests, is a test to identify if two graphs are isomorphic.

One way of viewing the isomorphism problem is to analyze it as follows: two graphs are isomorphic if there is a mapping between their nodes in which we can conclude that these graphs are in fact the same.

Or, in a more mathematical sense, we can say that two graphs H and G are isomorphic if and only if, for any pair of nodes u and v from H that are adjacent, there is a transformation f where f(u) is adjacent to f(v) in G.

These are examples of isomorphic graphs:

This problem is known to be very hard to solve. Until this day there is no polynomial-time solution and the problem may as well be considered NP-Complete.

The Weisfeiler-Lehman Test

The WL-Test is a test to quickly test if two graphs are isomorphic or not. Since the problem is NP-Complete, this test can fail in several cases. The interpretation of the test is as follows:

• If the test returns false, then the two graphs are surely not isomorphic
• If the test returns true, then the two graphs may be isomorphic

The test works in a node coloring scheme and works in the following fashion:

• We start by setting an initial value to every node on the graph. Let’s say ‘1’.
• For each node, we get the value of every neighbor and concatenate it together with the node value
• We take the hash of this value to set the new value of the node
• We repeat the process until there is no further change in the distribution of the values (not the values themselves)

We will return true for the test if the distribution of the values is the same for both graphs. Notice that one can run both coloring algorithms in parallel since the computations for both graphs are independent.

If the distribution of values is the same for both graphs, we are saying that for every node in H, there is an equivalent node in G in terms of its connections, so the graphs may be isomorphic.

Relationship to GNNs

But how does it relate to GNNs? Well, for one knowing the Message-Passing framework, it becomes clear that the strategy behind the WL-Test follows a similar pattern: neighbor information aggregation.

This way, it was proved by [1] that the GNNs are, at most (which means that they can be worse) as powerful as a WL-Test on its ability to tell if two graphs are isomorphic.

This means, for a GNN, that the ability to put two different graphs into two different embeddings points on the space, is limited by the WL-Test ability to tell these two graphs apart.

Some Examples of Failure for the WL-Test

The image below shows us an example of two non-isomorphic graphs that are indistinguishable by the WL-Test and therefore would receive the same embedding when applied on a GNN.

Notice also that this consideration takes into account only the topological structure of the graphs. When we use a feature matrix X on a GNN, it may be able to distinguish the graphs if their features are different. It would be the same as initializing the WL-Test with the hashing of the feature of the node instead of the same value for every node.

Python Implementation

For this implementation, we are going to create a base method that will receive different methods to construct the WL-Test and after that, the k-WL-Test.

You’ll see that the difference between the methods is basically:

• How we define the ‘set’ of nodes we are going to deal with
• How do we start coloring them
• How do we define the neighborhood of each element of the set

For this code we will need some libraries:

import copy
import pprint
import itertools
import hashlib
import networkx as nx

from collections import Counter

Now, let’s create a base_WL method that will do most of the heavy lifting for us:

def base_WL(G_, k, verbose, n_set, initial_colors_func, find_neighbors_func):    
    G, n = n_set(G_)
    colors = initial_colors_func(n)

old_colors = copy.deepcopy(colors)

for i in range(len(n)):
        for node in n:
            neigh_colors = "".join([colors[i][0] for i in find_neighbors_func(G, n, node)])

            colors[node].extend([neigh_colors])
            colors[node].sort()

# Update with the hash
        colors = {i: [hashlib.sha224("".join(colors[i]).encode('utf-8')).hexdigest()] for i in colors}

        if list(Counter([item for sublist in colors.values() for item in sublist]).values()) == list(Counter([item for sublist in old_colors.values() for item in sublist]).values()) and i != 0:
            if verbose:
                print(f'Converged at iteration {i}!')
            break

        old_colors = copy.deepcopy(colors)

canonical_form = sorted(Counter([item for sublist in colors.values() for item in sublist]).items())
    if verbose:
        print(f'Canonical Form Found: n {canonical_form} n')

return canonical_form

This function receives a function that will compute the set of elements, a function that will start the colors, and a function that returns the neighbors of a given set element.

Then, it will iteratively update the colors for each one of the elements based on its neighbors until the histogram (or the distribution) of values stop changing, at which point we say that the canonical form was found.

Now, let’s implement the methods that will generate the WL-Test:

def WL(G, k=2, verbose=False):
    def n_set(G):
        G = nx.convert_node_labels_to_integers(G)
        return G, list(G.nodes())

    def set_initial_colors(n):
        return {i: [hashlib.sha224("1".encode('utf-8')).hexdigest()] for i in n}

    def find_neighbors(G, n, node):
        return G.neighbors(node)

    return base_WL(G, k, verbose, n_set, set_initial_colors, find_neighbors)

As we can see, for the WL-Test, the set of elements are the nodes of the graph. The initial color is the same for everybody and is only the ‘1’ string, and finally, its neighborhood is only the connected nodes to the node of interest.

Notice the k argument. It is there only to keep the consistency with the method for the k-WL we will implement next.

The k-Weisfeiler-Lehman Test

The k-WL-Test is a higher-order version of the WL-Test that aims to improve its expressiveness, in other words, it aims to make it more powerful than the original version. The cost for it is the growth in computational complexity during the task. This means that the algorithm is slower.

The idea behind the k-WL-Test is to avoid using the topological structure of the network and instead use the idea of k-tuples of nodes during the coloring algorithm.

This works as follows. Given a network K, let [K] be the nodes from K. Let now K² be the set of tuples of size 2 comprised of every permutation of nodes from [K].

The idea is that we will repeat the algorithm from the vanilla WL-Test, but with these 2-tuples instead of the nodes.

But how do we define the neighborhood in this case? We consider it as the set of every tuple that differs from the original tuple at only one position. In mathematical terms we have Equation 1:

Notice that this description is from a 2-WL-Test. There are variants of it for any value k and the idea is the same, just the size of the tuple changes.

This implementation is strictly more powerful than the WL-Test. Yet, it still is not able to solve completely the Graph Isomorphism problem.

Python Implementation

def kWL(G, k, verbose=False):
    def n_set(G):
        G = nx.convert_node_labels_to_integers(G)
        V = list(G.nodes())
        V_k = [comb for comb in itertools.combinations(V, k)]
        return G, V_k

def set_initial_colors(n):
        return {i: [hashlib.sha224(str(i).encode('utf-8')).hexdigest()] for i in n}

def find_neighbors(G, V_k, node):
        return [n for n in V_k if len(set(n) - set(V_k[V_k.index(node)])) == 1]

return base_WL(G, k, verbose, n_set, set_initial_colors, find_neighbors)

Here, as we can see, we have the following differences from the WL-Test:

• The set of elements is based on V^k and not on V anymore.
• The initial color is not the same for every node, now it depends on the nodes that compose the element
• The neighborhood of each element is defined according to Equation 1.

Conclusion

Knowing the limitations of current popular GNNs architectures may help practitioners to avoid common pitfalls during their developments and also help researchers look into new opportunities for improving this exciting new area of knowledge.

In this post, we explored the WL-Test and the k-WL-Test variant and the relationship between the test and the Message-Passing framework usually applied on GNNs.

[1]K. Xu et al. How powerful are graph neural networks? (2019). Proc. ICLR.

[2] N. T. Huang and S. Villar, "A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants," ICASSP 2021–2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2021, pp. 8533–8537, doi: 10.1109/ICASSP39728.2021.9413523.