# A Message-Passing Algorithm for Graph Isomorphism

arXiv: https://arxiv.org/abs/1704.00395 · HTML: https://mlsanity.com/paper/1704.00395/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Apr 2017.

## Built on by (most cited first, 1 of 1)

- [Neuromorphic Camera Denoising using Graph Neural Network-driven Transformers](https://mlsanity.com/paper/2112.09685/) (2021)

## Abstract (arXiv)

A message-passing procedure for solving the graph isomorphism problem is proposed. The procedure resembles the belief-propagation algorithm in the context of graphical models inference and LDPC decoding. To enable the algorithm, the input graphs are transformed into intermediate canonical representations of bipartite graphs. The matching procedure injects specially designed input patterns to the canonical graphs and runs a message-passing algorithm to generate two output fingerprints that are matched if and only if the input graphs are isomorphic.