Isomorphism of labeled uniqueness trees

The paper Deep Weisfeiler Leman by Martin Grohe, Pascal Schweitzer, Daniel Wiebking introduces a framework that allows the design of purely combinatorial graph isomorphism tests that are more powerful than the well-known Weisfeiler-Leman algorithm. This is a major achievement, see for example the beginning of an email I wrote to Jonathan Gorard (author of the paper Uniqueness Trees: A Possible Polynomial Approach to the Graph Isomorphism Problem) on June 25, 2016:

Dear author,

you recently proposed a purely combinatorial method towards determining isomorphism of graphs, which you called uniqueness trees. For purely combinatorial methods, the most interesting question is how they compare to Weisfeiler-Lehman, and “not being subsumed” by Weisfeiler-Lehman would be considered to be a major achievement, even if the method would not yield a polynomial time algorithm for checking graph isomorphism.

I never received an answer. This is not uncommon, as I wrote in another place:

I sometimes write the authors of such papers my thoughts, but the typical reaction is to totally ignore my email such that I don’t even know whether a spam filter eliminated it before reaching the author, the best reaction is an “thanks for your kind words, I’m used to much more insulting feedback”. Being totally ignored feels bad, but maybe it is an appropriate reaction to “proof refutation”?

But in this post, I want to elaborate another point which I mentioned in that email:

Rooted (colored) trees can be canonically labeled, which allows to use your method for iterative color refinement just like Weisfeiler Lehman. Your uniqueness trees on the other hand are also labeled with the original vertices, but isomorphism of rooted labeled trees is GI-complete, so the labels probably can’t be exploited/included for canonical labeling.

(For completeness, I will also give a small counterexample to the algorithm proposed in that paper.)

Definitions and known results for labeled tree isomorphism

For unlabeled rooted trees, the AHU algorithm (by Aho, Hopcroft and Ullman, Example 3.2 on page 84 in their book “The Design and Analysis of Computer Algorithms”) allows to efficiently decide whether two rooted trees are isomorphic. We may regard the AHU algorithm as an efficient implementation of color refinement (also known as naive vertex classification) for rooted trees. Therefore, color refinement decides (rooted) tree isomorphism. Does it also decide labeled tree isomorphism? That depends on what we mean by isomorphism of labeled graphs:

For labeled graphs, two definitions of isomorphism are in use.

Under one definition, an isomorphism is a vertex bijection which is both edge-preserving and label-preserving.[1][2]

Under another definition, an isomorphism is an edge-preserving vertex bijection which preserves equivalence classes of labels, i.e., vertices with equivalent (e.g., the same) labels are mapped onto the vertices with equivalent labels and vice versa; same with edge labels.[3]

For the first definition, where the isomorphism is required to be label-preserving, color refinement decides isomorphism. It won’t for the second definition, since we know

Theorem: Marked tree isomorphism is isomorphism complete

from section 6.4 Marked Graphs and Marked Trees in Booth, Kellogg S.; Colbourn, C. J. (1977), Problems polynomially equivalent to graph isomorphism, Technical Report CS-77-04, Computer Science Department, University of Waterloo. They used the definition that “A marked graph is a graph together with a partition of its vertices. An isomorphism of marked graphs is an isomorphism of the underlying graphs which preserves the partitioning.”

Isomorphism of labeled uniqueness trees is GI complete

I don’t remember how I figured out that isomorphism of rooted labeled trees is GI-complete when I wrote that email back in 2016. I guess I just looked it up in section 6.4 Marked Graphs and Marked Trees cited above. This time I didn’t look it up, and just came up with a rather obvious construction on the fly:

From a graph G, construct a rooted labeled tree T by putting a node below the root of the tree for every vertex of G. For every edge of G, put two nodes with the same label on the next lower level. An edge has two endpoints, connect the corresponding vertices (or rather the tree nodes corresponding to them) each with one of the tree nodes corresponding to the edge.
graph2labtree.png

This construction does not yet rule out that the rooted labeled trees arising in the uniqueness trees algorithm could be efficiently tested for isomorphism. In those trees, no label is repeated on a given level of the tree. I initially believed that I had an efficient algorithm for this task. Then I realized that my algorithm was just an efficient implementation of color refinement for rooted labeled trees. So the question whether the algorithm worked boiled to whether color refinement decides isomorphism in this case. In the end it wasn’t that difficult to modify the above construction such that it also worked for this case:
graph2labuniquetree.png

A counterexample to the uniqueness trees algorithm

An easy way to break the uniqueness trees algorithm is to ensure that the trees don’t grow beyond depth 3 by replacing each edge by two nodes connected to the original end points of the edge, but not to each other. This ensures that only duplicate nodes are present at depth 2 or 3 of the uniqueness trees. Below we apply this construction to two non-isomorphis trees to construct two non-isomorphic graphs which cannot be distringuished by the uniqueness trees algorithm:
tree-noniso.png
However, this counterexample does not answer the question whether the uniqueness trees algorithm is subsumed by Weisfeiler-Leman. Somebody told me that he remembers that the uniqueness trees algorithm was indeed subsumed by Weisfeiler-Leman. I still don’t see it, but I admit that it is quite plausible. It is probably subsumed by the algorithm where each vertex is individualized separately followed by color refinement to generate a label for that individualized vertex. And that algorithm in turn is probably subsumed by 2-WL. Or more generally, if each k-tuple is individualized separately followed by k-WL to generate a label for that k-tuple, then that algorithm is probably subsumed by 2k-WL.

Conclusions?

This was not the post I had planed to write next. It is reasonably short, which is definitively a good thing. It may also be a good thing that it reminds us that marked tree isomorphism is known to be GI complete. In fact, this cs.stackexchange question about a polynomial time algorithm for marked tree isomorphism motivated me to reformulate my supposedly efficient algorithm for labeled uniqueness trees in simple terms (i.e. as an instance of color refinement). This in turn allowed me to step back and find a reduction to show that it cannot work.

Maybe this post would have been more interesting, if I had talked more about details of the new Deep Weisfeiler Leman paper. At least I explained why I consider it to be a major achievement.

About gentzen

Logic, Logic, and Logic
This entry was posted in isomorphism and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s