ScaWL: Scaling k-WL (Weisfeiler-Leman) Algorithms

What is it about?

Graph Isomorphism, or finding out whether two graphs are equivalent in structure, is an important problem to solve in many domains. The k-WL (Weisfeiler-Leman) algorithm is a well-known graph isomorphism test. The algorithm works by iteratively learning the structure of two input graphs, comparing what it has learned about both graphs at each iteration. If the structural information doesn’t match at any iteration, the two graphs are declared not isomorphic. If the structural information learned ever stops changing and the structure between the two graphs still match, the algorithm terminates and the two graphs are considered possibly isomorphic. ScaWL is the first distributed implementation of the k-WL algorithm, overcoming critical communication and memory bottlenecks. The innovations in ScaWL allow, for the first time, graphs of massive size to be feasibly subjected to the graph isomorphism test. The optimizations result in drastically reduced runtime and memory footprint.

Featured Image

Photo by Conny Schneider on Unsplash

Photo by Conny Schneider on Unsplash

Why is it important?

The k-WL algorithm has applications wherever problems can be formulated as graph comparison. Examples include chemoinformatics, computer vision, security, and social network analysis to name a few. The techniques of the WL-hierarchy of algorithms have inspired many other methods, including Graph Neural Networks. The insights provided by the ScaWL framework will inform design of algorithms for applications that employ or are inspired by the WL-hierarchy.