# Graph Convolution Basic

13 Aug 2017### Graph

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:

since

Here we have:

Noted this expression is K-localized since it is a order polynomial of laplacian.