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

[[concept]]

Theorem

Consider two graphs $G$ and $G^{\prime }$ without node features, with laplacian $L=V\Lambda V^T$ and $L^{\prime }=V^{\prime }{\Lambda }^{\prime }{V}^{\prime T}$. Further suppose that there is some ${\lambda }_j$ such that ${\lambda }_j\ne {\lambda }_i^{\prime }$ for all $i$ - ie, $L$ has at least one eigenvalue that is different from $L^{\prime }$.

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

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(\ast )$ Define the graph feature $x$ to be white, ie such that $\mathbb{E}[{\hat{x}}_i]=1\forall i=1,\dots ,n$.

Set $h_k=\{\begin{array}{l}1\text{ if }k=1\\ 0\text{otherwise}\end{array}$

Then we have

\mathbb{E}(\hat{y}) &= \mathbb{E}(V^Ty) \ &= \mathbb{E}(V^Th_{k}Lx) \ &= \mathbb{E}(V^TV\Lambda V^Tx) \ &= \mathbb{E}(\Lambda x) \ \implies \mathbb{E}(\hat{y}) &= \begin{bmatrix} \lambda_{1} \ \lambda_{2} \ \vdots \ \lambda_{n} \end{bmatrix} \end{aligned}$$ And if there is some ${\lambda }_j$ such that ${\lambda }_j\ne {\lambda }_i^{\prime }$ for all $i$ - ie, $L$ has at least one eigenvalue that is different from $L^{\prime }$ as above, then it suffices to compare

$\mathbb{E}(1^T\hat{y})={\sum }_i{\lambda }_i=\mathrm{Tr}(L)\text{to }\mathbb{E}(1^T{\hat{y}}^{\prime })={\sum }_i{\lambda }_i^{\prime }=\mathrm{Tr}(L^{\prime })$ 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

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