We can verify whether graphs without node features and different laplacian eigenvalues are not isomorphic

[[concept]]

Theorem

Consider two graphs $G$ and $G^{'}$ without node features, with laplacian $L = V Λ V^{T}$ and $L^{'} = V^{'} Λ^{'} V^{' T}$ . Further suppose that there is some $λ_{j}$ such that $λ_{j} \neq λ_{i}^{'}$ for all $i$ - ie, $L$ has at least one eigenvalue that is different from $L^{'}$ .

Then there exists a graph convolution we can use to verify whether two graphs are NOT isomorphic, ie to test that $G \neq G^{'}$

For original proof, see the paper GNNs are more powerful than you think

Proof

Consider the following single-layer (linear) GNN

y = \sum_{k = 0}^{K - 1} h_{k} L^{k} x (*)

Define the graph feature $x$ to be white, ie such that $E [{\hat{x}}_{i}] = 1 \forall i = 1, \dots, n$ .

Set $h_{k} = {\begin{cases} 1 if k = 1 \\ 0 otherwise \end{cases}$

Then we have

\begin{aligned} E (\hat{y}) & = E (V^{T} y) \\ = E (V^{T} h_{k} L x) \\ = E (V^{T} V Λ V^{T} x) \\ = E (Λ x) \\ ⟹ E (\hat{y}) & = [\begin{array}{c} λ_{1} \\ λ_{2} \\ ⋮ \\ λ_{n} \end{array}] \end{aligned}

And if there is some $λ_{j}$ such that $λ_{j} \neq λ_{i}^{'}$ for all $i$ - ie, $L$ has at least one eigenvalue that is different from $L^{'}$ as above, then it suffices to compare

$E (1^{T} \hat{y}) = \sum_{i} λ_{i} = Tr (L) to E (1^{T} {\hat{y}}^{'}) = \sum_{i} λ_{i}^{'} = Tr (L^{'})$
Since the laplacian is positive semidefinite, the sums will be different if and only if we have at least eigenvalue that is different between them.

Mentions

File
Weisfeiler-Leman Graph Isomorphism Test
graph isomorphism
2025-02-19 graphs lecture 9
2025-03-03 graphs lecture 11