# Linear Programming Heuristics for the Graph Isomorphism Problem

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Nov 2016.

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

- [Breaking the Limits of Message Passing Graph Neural Networks](https://mlsanity.com/paper/2106.04319/) (2021)
- [Wasserstein Graph Distance Based on L1-Approximated Tree Edit Distance between Weisfeiler-Lehman Subtrees](https://mlsanity.com/paper/2207.04216/) (2022)
- [Matching and mixing: Matchability of graphs under Markovian error](https://mlsanity.com/paper/2601.20020/) (2026)

## Abstract (arXiv)

An isomorphism between two graphs is a bijection between their vertices that preserves the edges. We consider the problem of determining whether two finite undirected weighted graphs are isomorphic, and finding an isomorphism relating them if the answer is positive. In this paper we introduce effective probabilistic linear programming (LP) heuristics to solve the graph isomorphism problem. We motivate our heuristics by showing guarantees under some conditions, and present numerical experiments that show effectiveness of these heuristics in the general case.