Communications of the ACM
Home/Magazine Archive/May 2021 (Vol. 64, No. 5)/Technical Perspective: A Logical Step Toward the Graph.../Full Text
Research highlights
Technical Perspective: A Logical Step Toward the Graph Isomorphism Problem
The graph isomorphism problem remains one of those mysteries in theoretical computer science that fascinates laypersons and experts alike. In 1979, Garey and Johnson mentioned the problem in their renowned book on computers and intractability but, in fact, it dates back even earlier and has been unresolved for over half a century. In 2015, a major advance hit the media: Babai's quasipolynomial algorithm. This was the first improvement for the general problem in over 30 years. And yet it remains an open problem. At its core, the problem captures the algorithmic detection of symmetries of combinatorial objects.
Maybe surprisingly, there are various and quite distinct areas in which the problem finds applications. We can find one such application domain in the context of logics. Indeed, the isomorphism problem appears to be closely linked to what logicians call the quest for a logic that captures PTIME, a major open problem in finite model theory. In a nutshell we want a logic that is powerful enough to precisely allow everything that is efficiently solvable to be captured in a formula but is not more powerful than that. In terms of databases, we want a query language expressive enough to allow all queries that can be efficiently answered but again not more than that.
For a logician on the quest, designing an efficient isomorphism algorithm for some class of structures is not particularly helpful. What is needed is to be able to "solve" the problem within a logic. In fact, while this is a necessary step, it might not be enough. What does suffice, however, is to be able to "solve" the canonization problem for the class within a logic. Intuitively, the canonization problem asks for an efficient normal form, some way of unambiguously (that is, canonically) representing a given input. The canonization problem is closely linked to the isomorphism problem, and considering practical applications of isomorphism, it turns out that a solution to the canonization problem is what users often actually want and need.
In the following paper, Grohe and Neuen consider the class of graphs of bounded rank width. The class is equivalent to graphs of bounded clique width, a term sometimes more familiar to graph theorists who do not have a focus on algorithmic aspects. The class is not readily defined, but it does play a central role in graph structure theory. Quintessentially, graphs in this class are recursively decomposable into small parts so that the interplay between the different parts is not too complicated. Several years ago, the class was essentially the only class of naturally decomposable graphs for which we had no efficient isomorphism test.
In 2015, Grohe and Schweitzer found an efficient test, but for the questing logician the answer was unsatisfactory. The algorithm involves a barrage of techniques from computational group theory, making the solution not only complicated but also not providing a sufficient answer to logical definability and canonization. In their new paper, Grohe and Neuen instead use a purely combinatorial approach: the Weisfeiler-Leman algorithm. This algorithm has its roots in algebraic graph theory, it is used in Babai's algorithm, and it recently found applications in machine learning in the form of graph kernels.
The authors now show, remarkably, that the well-established Weisfeiler-Leman algorithm in its plain form solves the isomorphism problem for bounded-rank width graphs. In fact, the paper even goes the crucial step further to show that canonization can be solved in the logic corresponding to the algorithm (fixed-point logic with counting). Overall, they obtain a logic that captures PTIME on graphs of bounded rank width. This means, essentially, that everything that can be algorithmically solved efficiently on these graphs can alternatively be expressed by a logical formula of fairly simple composition.
Grohe and Neuen use a purely combinatorial approach: the Weisfeiler-Leman algorithm.
Grohe had previously demonstrated this type of approach can be very fruitful. In fact, his 2017 book on the matter, spanning more than 500 pages, executes the approach for graph classes closed under taking minors. Yet, the class of graphs of bounded rank width is one of the most general classes for which the approach has been put to work successfully.
Overall, in comparison to the previously best result, the paper provides us with a stronger result based on a simpler algorithm. On top of that, the overall proof is—at least from my perspective—simpler and, for many, easier to understand. Finally, the constants in the running time of the algorithm, which translate in logic terms to the number of variables needed, are small (specifically, linear in the rank width) and in some sense as small as they can be. Central to the analysis is the introduction of the novel concepts of split pairs and flip functions, which cleanly facilitate many of the arguments. It is common to find that when it comes to matters of theory, hitting the right approach, careful choice of definitions, and a hunch can make all the difference. Overall, Grohe and Neuen have found a clean and neat way to complete the logicians' quest for graphs of bounded rank width.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2021 ACM, Inc.
No entries found