# Notes on: Henaff, M., Bruna, J., & LeCun, Y. (2015): Deep convolutional networks on graph-structured data

## Table of Contents

`[ ]`

Check out "Spectral networks and deep locally connected networks on graphs"`[ ]`

Check out "A wavelet tour of signal processing." for more info on the operators- Probably not necessary

## Notation

- denotes the number of nodes in the graph
- represents the
**similarity matrix** - is the diagonal matrix of the form
- denotes the
**graph Laplacian** - denotes the eigenvectors of
- denotes the spectral multipliers
- denotes input
- denotes the Fourier Transform of
- denotes a graph convolution layer with feature maps / channels
- denotes a fully connected layer with hidden units
- denotes the # of free parameters

## Prereqs

Let be a graph with vertices and edges . Let be a function of the vertices taking values in a ring .

Then, the **discrete Laplacian operator** acting on is defined by

where is the *graph distance* between vertices and , or for a *weighted* graph:

where is the weight value on th edge .

Thus, this is a *sum over the nearest neighbors* of the vertex .

For a graph of a *finite* number of edges and vertices, this definition is identical to the graph Laplacian.

## Spectral networks

- Generalizes a conv. net through Graph Fourier Transform, which is in turn defined via a generalization of the Laplacian operator on the grid to the graph Laplacian

Let be a similiarity matrix representing an undirected graph , and let

be it's *(normalized) graph Laplacian* with and eigenvectors .

Then a **graph convolution** of input signals with filters on is defined by

where represents a point-wise product, and the *convolution* operation, which is defined for a graph as above.

- Unitary matrix plays the role of the Fourier Transform in
- In the case where represents the lattice, from the definition of we recover the discrete Laplacian operator
- Laplacian commutes with the "translation operator", which is diagonalized in the Fourier basis
- Follows that eigenvectors of are given by the DFT matrix

Thus (apparently), learing filters on a graph thus amounts to learning spectral multipliers

### Multi-channel input

If is a signal with input channels and locations, we apply the transformation on each channel, and then use multipliers (which is a matrix, rather than a vector as for single-channel).

### Expressing spatial localization of filters

- Seek to express spatial localization of filters in terms of their spectral multipliers
In the

*grid*(NOT a graph), smoothness in the "frequency domain" corresponds to the*spatial decay*, sincewhere is the Fourier transform of .

Other paper suggests similiar approach; using a

*smoothing kernel*, such as splines, and searching for spectral multipliers of the form

### Algorithm

- Given GTF matrix , interpolation kernel , weights .
**Forward Pass:**- Fetch input batch and gradients w.r.t. outputs
- Compute interpolated weights
- Compute output:
**Backward Pass:**- Compute gradient w.r.t. input:
- Compute gradient w.r.t. interpolated weights:
- Compute gradient w.r.t. weights

### DONE What's the "translation operator" on a graph?

Surely the "translation operator" is just .