Color Refinement

A visual demo of the color refinement algorithm.

• Use it online
• For offline use, you will need to download the external resources loaded at the top of index.html, and change the paths correspondingly.

Screenshot

Description

The color refinement algorithm is a heuristic method to detect whether two graphs are isomorphic (see, e.g., [GKMS17+]). It is also known as the 1-dimensional Weisfeiler-Leman algorithm.

Development

For local development, install your favorite JavaScript toolkit, such as bun. Then install the dependencies and start the development server:

bun install --frozen-lockfile
bun dev

Run prettier to format the code:

bun format

Run eslint to check the code for errors:

bun lint

Built with

• D3.js
• CSS grid
• normalize.css

References

[GKMS17+] Martin Grohe, Kristian Kersting, Martin Mladenov, and Pascal Schweitzer. Color Refinement and its Applications. In An Introduction to Lifted Probabilistic Inference. Cambridge University Press. To appear. (preprint url)