graph isomorphism

[[concept]]

Graph Isomorphism

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

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

TABLE
FROM [[]]
 
FLATTEN choice(contains(artist, this.file.link), 1, "") + choice(contains(author, this.file.link), 1, "") + choice(contains(director, this.file.link), 1, "") + choice(contains(source, this.file.link), 1, "") as direct_source
 
WHERE !direct_source