linear graph filter

Data

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

Graph Filter

A (linear) graph filter is defined as an operator $H:{\mathbb{R}}^n\to {\mathbb{R}}^n,x\to y=HS,H\in {\mathbb{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_{ij}\ne 0$, this is not consistent with the structure of the graph!
• Because of this, we cannot implement $H$ locally at each node.
• $(Sx{)}_i={\sum }_j{S}_{ij}{x}_i={\sum }_{j\in N_i}{S}_{ij}{x}_i$, but we cannot write $H$ analogously ie $(Hx{)}_i\ne {\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$.

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