convolutional graph filters are local

Data

Theorem

Proof

We can write locally in terms of $k$ steps:

\begin{aligned} y & = \sum_{k = 0}^{K - 1} h_{k} S^{k} x \\ = \sum_{k = 0}^{K - 1} h_{k} S^{k - 1} S x, let z_{1} = S x \\ = \sum_{k = 0}^{K - 1} h_{k} S^{k - 1} z_{1} + h_{0} x \\ = \sum_{k = 1}^{K - 1} h_{k} S^{k - 2} S z_{1} + h_{0} x, let z_{2} = S z_{1} \\ = \sum_{k = 2}^{K - 1} h_{k} S^{k - 2} S z_{2} + h_{0} x + h_{1} z_{1} \\ = \dots \\ = \sum_{k = 0}^{K - 1} h_{k} z_{k} (letting z_{i} = S^{i} x) \end{aligned}

Example

Visual representation of the stepwise local expression