Graph isomorphism

Weisfeiler Lehman graph isomorphism test

Roughly speaking, if we can match the vertices and edges of a graph to another, we say there is an isomorphism between these two graphs. A closely related problem is the Subgraph isomorphism problem where one should decide whether a graph contains a subgraph that is isomorphic to the other graph.

More relaxed isomorphism problems may be more interesting. One is deanonymization. Recently, a team won the link prediction challenge not by predicting links, but by matching the anonymized graph with real graph data and subsequently predicting the existing links. Although they didn’t have a complete graph of Flickr, it was enough to sample a portion (preferably hubs) to match many vertices and edges.

Another example is biological networks. Imagine two protein-protein interaction networks of two different species. If they are close relatives, they must have very similar vertices and similar edges. Making the problem easier, it is easy to identify many orthologues and homologs if they are close. But here is the catch: the current technology is well known to possess many false negatives and thus the edges are largely missing in both networks.

There are very nice papers tackling this problem. Sharan, Karp, and Ideker wrote a series of papers about aligning two networks.