graph automorphism

[[concept]]

graph automorphism

Let $G=(V,E)$ be a graph. A graph automorphism is a graph homomorphism from $G$ to $G$. That is, a map $\gamma :G\to G$ such that $(i,j)\in E⟹(\gamma (i),\gamma (j))\in E$

If there exists an automorphism for $G$, then there exists a corresponding permutation matrix $P$ such that $V=PV$.

Note

In a learning task (in a GNN), this means that the shift operator $S=PS{P}^T$ and node features $x=Px$ for the permutation matrix $P$.

see also graph homomorphism and graph isomorphism

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