convolutional graph filters are permutation equivariant

Data

subject:: Data Science Methods for Large Scale Graphs parent:: Graph Signals and Graph Signal Processing theme:: math notes

Theorem

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 $P1=1$, $P1=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$

Proof

y’ = H(S’)x’ &= \sum_{k=0}^{K-1}h_{k}(PSP^T)^k Px \ &= \sum_{k=0}^{K-1}h_{k} PS^k P^T Px \ &= P \sum_{k=0}^{K-1}h_{k}S^{k} x \ &= Py \end{aligned}$$

Thus $H$ is invariant to permutations. (if $S$ and $x$ are permuted/relabelled, $y$ is relabelled in the same way)

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