Deep Paper Pool really deep.

Graph Convolution Basic


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.