linear graph filter

Data

Graph Filter

A (linear) graph filter is defined as an operator

H : R^{n} \to R^{n}, x \to y = H S, H \in R^{n \times n}

ie, a graph filter is a linear map from graph signals to graph signals.

This is a basic building block for processing graph signals

Question

What are potential issues with such filters?

Answer

Since $H$ is not parameterized by the graph or the shift operator, it does not incorporate the graph sparsity pattern.
if nodes $i, j$ are in different connected components but $H_{i j} \neq 0$ , this is not consistent with the structure of the graph!
Because of this, we cannot implement $H$ locally at each node.
$(S x)_{i} = \sum_{j} S_{i j} x_{i} = \sum_{j \in N_{i}} S_{i j} x_{i}$ , but we cannot write $H$ analogously ie $(H x)_{i} \neq \sum_{j \in N_{i}} h_{j} x_{j}$
The number of parameters is $n^{2}$ - this is bad for large $G$ .
We cannot adapt $H$ for different sized graphs. Once we design $H$ , it only works for graphs of size $n$ .

File
2025-01-29 graphs lecture 3
2025-02-03 graphs lecture 4