convolutional graph filters are permutation equivariant

graph convolution are permutation equivariant.

Suppose we have a graph shift operator $S$, a graph signal $x$, and a permutation matrix $P$. (recall that $P\in \{0,1\}$ such that $P\mathbb{1}=1$, $P\mathbb{1}=1$, $P^{T}P=P{P}^T=I$). Suppose we relabel nodes $V=\{1,2,\dots ,n\}$ according to $P$, ie, define $S^{\prime }=PS{P}^T$ and $x^{\prime }=Px$. Consider filter $y=H(S)x$.

Then $y^{\prime }=H(S)x^{\prime }=Py$