graph isomorphism

[[concept]]

Graph Isomorphism

Let $G$ and $G^{'}$ be two graphs. A graph isomorphism between $G$ and $G^{'}$ is a bijection $M : V (G) \to V (G^{'})$ such that for all $i, j \in V (G)$

(i, j) \in E (G) ⟺ (M (i), M (j)) \in E (G^{'})

We often ask,

Question

Is it possible to detect whether graphs are isomorphic? In particular, can we train a GNN to detect if graphs are isomorphic?

ie, to produce identical outputs for graphs in the same equivalence class/graphs which are isomorphic, and different outputs for graphs that are not isomorphic?

It turns out, graph isomorphism is not solvable in polynomial time.

We can verify whether graphs without node features and different laplacian eigenvalues are not isomorphic. However, there are many non-isomorphic graphs that do share a spectrum, so this is only a viable negative test. The Weisfeiler-Leman Graph Isomorphism Test is also a decent negative heuristic.

Mentions

File
A graph isomorphism exists exactly when two graphs are equivalent
We can verify whether graphs without node features and different laplacian eigenvalues are not isomorphic
Weisfeiler-Leman Graph Isomorphism Test
graph automorphism
graph homomorphism
graph isomorphism is not solvable in polynomial time
the WL test is at least as powerful as a GNN for detecting graph non-isomorphism
2025-02-19 graphs lecture 9
2025-02-24 graphs lecture 10
2025-03-03 graphs lecture 11
2025-02-25 equivariant lecture 4