# Graph Convolution Basic

### Graph

Edge $e=(i,j)$ connects vertices $v_i$ and $v_j$. It has weight of $\mathbf{W}_{ij}$

Laplacian is a real symmetric matrix.
It has orthonormal eigenvector as $\{\mathbf{u}_l\}_{l=0,1,...,N-1}$ and eigenvalue $\{\lambda_l\}_{l=0,1,...,N-1}$.

Assume $% $, we denote the entire spectrum by $\sigma(\mathcal{L}):=\{\lambda_0,\lambda_1,...,\lambda_{N-1}\}$

### Graph Fourier transform

Eigenfunction of a linear operator $D$ is any non-zero function $f$ that $Df=\lambda f$, where $\lambda$ is a scaling factor called eigenvalue.
In one dimensional space, laplacian or laplace operator is $\Delta$:

For classical Fourier transform:

where $e^{2\pi i\xi t}$ is eigenfunction of $\Delta$, since,

For graph, we can define graph Fourier transform $\hat f$ as,

and inverse graph Fourier transform as,

### Graph Spectral Filtering

In classical signal processing, filter is:

where $\hat h(\cdot)$ 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 $g_\theta = diag(\theta)$, parameterized by $\theta \in \mathbb R^N$

In order to calculate this, we need calculate $\mathbf{U}g_\theta\mathbf{U}^T. ~ (O(N^2))$
To avoid this, we can treat $g_\theta$ as a function of $\mathbf{\Lambda}$, and approximate it by truncated expansion in terms of Chebyshev polynomial $T_k(x)$ up to $K^{th}$ order:

with rescaled $\tilde{\mathbf\Lambda} = \frac{2}{\mathbf{\lambda}_{max}}\mathbf{\Lambda}-I_N$, $\theta'_k$ as vector of Chebyshev coefficients, and:

since $(\mathbf{U}\mathbf{\Lambda}\mathbf{U}^T)^k=\mathbf{U}\mathbf{\Lambda}^k\mathbf{U}^T$
Here we have:

Noted this expression is K-localized since it is a $K^{th}$ order polynomial of laplacian.