graph isomorphism is not solvable in polynomial time

[[concept]]
Idea
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?

The graph isomorphism problem (ie, figuring out whether graphs are isomorphic) is not solvable in polynomial time as far as we know.

Mentions

File
graph isomorphism