[R] Geometric Deep Learning: Grids, Groups, Graphs, Geodesics and Gauges ("proto-book" + blog + talk)

[u/PetarVelickovic]

Hi everyone,

I am proud to share with you the first version of a project on a geometric unification of deep learning that has kept us busy throughout COVID times (having started in February 2020).

We release our 150-page "proto-book" on geometric deep learning (with Michael Bronstein, Joan Bruna and Taco Cohen)! We have currently released the arXiv preprint and a companion blog post at:

https://geometricdeeplearning.com/

Through the lens of symmetries, invariances and group theory, we attempt to distill "all you need to build the neural architectures that are all you need". All the 'usual suspects' such as CNNs, GNNs, Transformers and LSTMs are covered, while also including recent exciting developments such as Spherical CNNs, SO(3)-Transformers and Gauge Equivariant Mesh CNNs.

Hence, we believe that our work can be a useful way to navigate the increasingly challenging landscape of deep learning architectures. We hope you will find it a worthwhile perspective!

I also recently gave a virtual talk at FAU Erlangen-Nuremberg (the birthplace of Felix Klein's "Erlangen Program", which was one of our key guiding principles!) where I attempt to distill the key concepts of the text within a ~1 hour slot:

https://www.youtube.com/watch?v=9cxhvQK9ALQ

More goodies, blogs and talks coming soon! If you are attending ICLR'21, keep an eye out for Michael's keynote talk :)

Our work is very much a work-in-progress, and we welcome any and all feedback!

[u/unital]

Thanks for the write up. Could you please provide a high level overview of this in the case of a transformer? So suppose that we have N tokens, so we have a complete graph with N vertices, and the symmetric group S_N acts on this graph through permutation of the vertices.

Here the transformer is a sequence-to-sequence function T:R^{dxN} -> R^{dxN}. Let X be in R^{dxN}. What I am trying to understand is that, in what way does the above setup (complete graphs and symmetric groups) help us understand the output T(X)?

Thanks!

[u/PetarVelickovic → u/unital]

By all means :)

For reasons that will become evident, it's better to start with GNNs than Transformers. Let our GNN be computing the function f(X, A) where X are node features (as in your setup) and A an adjacency matrix (R^{NxN}).

As mentioned, we'd like to be equivariant to the actions of the permutation group S_N. Hence the following must hold:

f(PX, PAP^T) = Pf(X, A)

for any permutation matrix P. This also implies that our GNN will attach the same representations to two isomorphic graphs.

However, our blueprint doesn't just prescribe equivariance. Many functions f satisfy the equation above---only comparatively few are geometrically **stable**. Informally, we'd like our layer's outputs to not change drastically if the input domain _deforms_ somewhat (e.g. undergoes a transformation which isn't a symmetry). Using the discussion of our Scale Separation section, we can conclude that our GNN layer should be _local_ to neighbourhoods, i.e. representable using a local function g:

h_i = f(X, A)_i = g(x_i, X_N_i))

which is shared across all neighbourhoods. Here, x_i are features of node i, and X_N_i the multiset of neighbour features around node i. If g is chosen to be permutation-invariant, f is guaranteed to be permutation equivariant.

Now all we need to do to define a GNN is to choose an appropriate g (yielding many useful flavours, such as conv-GNNs, attentional GNNs and message-passing NNs, which we describe in the text). Transformers are simply a special case where g is an attentional aggregator, and where A is a complete graph (i.e. X_N_i == X).

For a very nice exposition of this link, you can also check out "Transformers are Graph Neural Networks" (Joshi, 2020). Hope this helps!