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

• `[ ]` 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, since

where 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

1. Given GTF matrix , interpolation kernel , weights .
2. Forward Pass:
3. Fetch input batch and gradients w.r.t. outputs
4. Compute interpolated weights
5. Compute output:
6. Backward Pass:
7. Compute gradient w.r.t. input:
8. Compute gradient w.r.t. interpolated weights:
9. Compute gradient w.r.t. weights

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

Surely the "translation operator" is just .