§4.6, p. 65 — a polynomial filter of degree r is localised in r-hop neighbourhood

Let $G$ be a simple graph on the nodes $\{1,\dots,n\}$, and let $W\in\mathbb R^{n\times n}$ be a weight matrix supported on the edges of $G$: $w_{uv}\neq 0$ with $u\neq v$ implies that $u$ and $v$ are adjacent in $G$. Let $\Delta=D-W$ be the Laplacian (24), $r\ge 0$, and $\alpha_0,\dots,\alpha_r\in\mathbb R$. Fix a node $u$ and two feature matrices $X,X'\in\mathbb R^{n\times d}$ whose rows agree at every node within $r$ hops of $u$ (every $v$ joined to $u$ by a walk of length at most $r$). Then

That is, the output of a degree-$r$ polynomial filter at $u$ depends only on the features in the $r$-hop neighbourhood of $u$. This is what makes polynomial spectral filters on graphs local, in contrast with general spectral filters and with rational filters, which have exponential decay but not local support.

Formalization Note The book's graph is the graph of the weights; here the weights may live on any graph $G$ containing their support (diagonal weights are allowed and cancel in $\Delta$), and $W$ need not be symmetric. The book's setting $W=W^\top$, $G$ the graph of $W$, is a special case.