Geometric Deep Learning

Dealing with structured data.

Bronstein, Michael M., et al. "Geometric deep learning: going beyond euclidean data." IEEE Signal Processing Magazine 34.4

(2017): 18-42.

Speaker: Alberto Rossi

Outline

1. Main idea and related work
2. Deep Learning on Euclidean Domain
3. Convolutional Neural Network
4. Manifolds and Graphs
5. Fourier analysis on Non-Euclidean Domain
6. Spectral CNN
7. Spectrum-Free methods

​

Main idea and related work

Geometric Deep Learning try to generalize Deep Learning model to structured domain, such as graphs and manifolds

1. Scarselli, Franco, et al. "The graph neural network model." IEEE Transactions on Neural Networks 20.1 (2009): 61-80.
2. Li, Yujia, et al. "Gated graph sequence neural networks." arXiv preprint arXiv:1511.05493 (2015).
3. Bruna, Joan, et al. "Spectral networks and locally connected networks on graphs." arXiv preprint arXiv:1312.6203 (2013).
4. Defferrard, Michaël, Xavier Bresson, and Pierre Vandergheynst. "Convolutional neural networks on graphs with fast localized spectral filtering." Advances in Neural Information Processing Systems. 2016.
5. Masci, Jonathan, et al. "Geodesic convolutional neural networks on riemannian manifolds." Proceedings of the IEEE international conference on computer vision workshops. 2015.

Deep Learning on Euclidean Domains

Consider as an Euclidean Domain in which is defined e.g an image

In supervised learning an unknown function is observed on the training set

• Stationarity: translational operator

​

​

• Local deformation and scale operation:

Convolutional Neural Network

Convolutional layer acting on a p-dimensional input applying a set of filter and a pointwise non-linearity

​

​

Producing q-dimensional output called feature maps

• Often combined with pooling layers, a downsampler.
• The learning optimize a task-specific cost function.
• Geometric prior in which CNN are based avoid the curse of dimensionality

​

How to generalize CNN to Non-Euclidean domains?

Manifolds and Graphs

Graphs.

A pair where is the set of vertices, is the set of edges

Two function defined on graph:

• ​

Equivalent to scalar field and tangent vector field in discrete domain

Manifolds.

Roughly speaking manifolds is a space that is locally euclidean

Two function defined on manifolds to define calculus on manifold:

• Scalar field is a smooth real function on the manifold
• Tangent vector field

Fourier analysis on non-Euclidean domain

​

• Convolution theorem: allow to express the convolution of two function in the spectral domain as the element-wise product of their Fourier Transform.
• This could not be applicable directly to non-Euclidean domain, but we can use the convolution theorem as the definition.

where is an eigenfunction

In matrix form:

Where are the spectral representation of the filter and are the Laplacian eigenvectors

Laplacian: L=D-W, where D_ii is the sum of arcs weight on i and W_ij arcs weight matrix

​

​

​

Spectral CNN (SCNN)^[3]

Spectral convolutional layer.

​

• matrices and are the p- and q-dimensional input and output signal
• is a diagonal matrix of spectral multipliers (filters in frequency domain)
• is a non linearity applied on the vertex wise function values

Spectral methods are basis dependent so it is limited to a single domain.

Spectrum-Free methods

In order to not operate in frequency domain we prefer to approximate the laplacian with a polynomial expansion on its eigenvalues.

corresponding to

Vector of polynomial coefficient

Resulting in filter matrices

​

Graph CNN (ChebNet)^[4]

Characterize a filter by a Chebyshev expansion of order r-1

​

​

​

Are rescaling of the Laplacian mapping its eigenvalues

​

• GCN^[6] simplify the model assuming r=2.

[6] Kipf, Thomas N., and Max Welling. "Semi-supervised classification with graph convolutional networks." arXiv preprint arXiv:1609.02907 (2016).

Results

Evaluated on different task over MNIST and on 20NEWS text categorization

Result obtained by those methods are not the state-of-the-art.

They are able to save parameter resulting in faster learning.

Thanks!!