Graph Convolution Basic13 Aug 2017
Edge connects vertices and . It has weight of
Laplacian is a real symmetric matrix.
It has orthonormal eigenvector as and eigenvalue .
Assume , we denote the entire spectrum by
Graph Fourier transform
Eigenfunction of a linear operator is any non-zero function that , where is a scaling factor called eigenvalue.
In one dimensional space, laplacian or laplace operator is :
For classical Fourier transform:
where is eigenfunction of , since,
For graph, we can define graph Fourier transform as,
and inverse graph Fourier transform as,
Graph Spectral Filtering
In classical signal processing, filter is:
where is transfer function of this filter. By inverse Fourier transform,
For graph, we define graph spectral (frequency) filtering as,
by inverse graph Fourier transform,
With some matrix manipulation and orthonormality, we can get:
Based on equation (20), we also define (22) or (23) as convolution on graph.
Chebyshev polynomial expansion
Note: we are using normalized graph laplacian now.
Assume we have a filter , parameterized by
In order to calculate this, we need calculate
To avoid this, we can treat as a function of , and approximate it by truncated expansion in terms of Chebyshev polynomial up to order:
with rescaled , as vector of Chebyshev coefficients, and:
Here we have:
Noted this expression is K-localized since it is a order polynomial of laplacian.