Geometric Deep Learning  an overview
Tech Blog
June 10, 2020 • ☕️☕️ 8 min read
 NonEuclidean domains
 Spectral methods
 Spatial methods
 Why spatial is better than spectral
 Introduction by example: GCN implemented in PyTorch Geometric
I decided to write a series of articles to cover the things I’ve learned while working on my MEng thesis. My work is focused on applying Geometric Deep Learning methods for shape analysis in the medical setting. The first post is an overview of Geometric Deep Learning.
Geometric deep learning (GDL), a term first proposed by Bronstein et al. [1], has emerged aiming to generalize deep learning models to nonEuclidean domains. This novel field in the world of machine learning was successfully used for building recommender systems [2], protein function prediction [3], fake news detection [4], and detection of cancerbeating molecules in food [5]. GDL owes its success to the fact that it operates directly on the relational structure of a given problem. An example of such a structure is a graph. It can describe various concepts ranging from a social network to a chemical compound.
Most GNN architectures are based on message passing (spatial methods), where at each layer the nodes update their hidden representations by aggregating information they collect from their neighbours. A crucial difference from traditional neural networks operating on gridstructured data is the absence of canonical ordering of the nodes in a graph. To address this, usually the aggregation function is constructed to be invariant to neighbourhood permutations.
NonEuclidean domains
Graph. A graph $G$ is a pair $(V,E)$ with the finite set of vertices $V$ and edges $E$. It captures interactions (edges) between individual units (nodes).
Manifold. A manifold is a is a locally Euclidean space. In computer graphics, shapes are represented as discrete 2dimensional manifolds. A discrete manifold has vertices uniformly sampled from the surface of the manifold with edges expressing the local structure of the shape. It’s commonly called a triangular mesh.
Spectral methods
Spectral methods were the first approach to generalize convolution operation to nonEuclidean domains. In practice, they are rarely used because they are computationally inefficient and don’t generalize well to different domains.
Spectral graph convolution draws inspiration from the Euclidean convolution in a spectral domain. The Fourier basis is used to compute spectral convolution in the classical signal processing (Read this for an indepth explanation of Convolution theorem). Given a graph, one way to generalize a convolutional architecture is to look at linear operators that commute with the graph Laplacian. This property implies operating on the spectrum of the graph weights, given by the eigenvectors of the graph Laplacian. The concept of graph convolution is explained more indepth in here.
Spatial methods
Spatial methods are preferred over the spectral methods for a number of reasons. The spatial convolution is considered a more versatile method for learning on nonEuclidean structures.
Figure 1: 2D Convolution vs. Graph Convolution.
Spatial methods define graph convolutions based on a node’s spatial relations, which is analogous to the convolution operation on the classical CNN. Images can be considered a special form of a graph with each pixel representing a node, connected to each neighboring pixels. A filter would be applied on the patch of the image including the pixel and its neighboring nodes. Similarly, spatial methods convolve a given node’s features, using a patch operator, with its neighbors’ features. The intuition about the spatial graph convolutions is that this operation propagates and updates node features along edges.
Why spatial is better than spectral
Spatial models are preferred over spectral models due to efficiency, generality, and flexibility issues. Spectral models are less efficient than spatial models as they need to perform eigendecomposition or handle the whole graph at the same time (e.g. mesh completion scenario). Spatial models are more scalable to large graphs as they directly perform convolutions in the graph domain via information propagation (i.e. message passing). The computation can be performed in a batch of nodes instead of the whole graph. Moreover, spectral models assume a fixed graph and because they rely on a graph Fourier basis they generalize poorly to new graphs. This is because any perturbation to a graph results in a change of eigenbasis. Spatial models perform graph convolutions locally on each node, which allows for weight sharing across different structures and locations. Finally, spectral methods are limited to undirected graphs whereas spatial methods can handle a bigger variety of graphs such as edge inputs, directed graphs, signed graphs and heterogeneous graphs because of the flexibility of the aggregation function
Introduction by example: GCN implemented in PyTorch Geometric
PyTorch Geometric [6] is a geometric deep learning extension library for PyTorch. It is a library for deep learning on irregularly structured input data such as graphs, point clouds, and manifolds, also known as geometric deep learning, from a variety of published papers. It consists of an easytouse minibatch loader for many small and single big graphs, multi gpusupport and a large number of common benchmark datasets.
PyTorch Geometric makes use of Generic Message Passing Scheme to implement any convolutional operator. The message passing scheme consists of 2 steps:
 propagate step  messages from nodes are propagated to their local neighborhoods.
 update step  embedded node’s features are updated by the message vector.
Graph Convolutional Network (GCN) was defined by Kipf et al. [7]. The intuition of this method is that it can alleviate the problem of overfitting on local neighborhood structures for graphs with very wide node degree distributions, such as social networks, citation networks, and many other realworld graph datasets. The computational complexity of this approach is $O(n)$. It applies simple filters acting on the 1hop neighborhood of the graph in the spatial domain. It can be expressed in the generic messagepassing scheme as:
$\text{msg}(x_i, x_j) = \frac{1}{\sqrt{\deg(x_i)} \sqrt{deg(x_j)}} \left( \mathbf{x}_j \mathbf{\Theta} \right)$ $\mathbf{x'}_i = \sum_{j \in \mathcal{N}(i) \cup \{ i \}} \text{msg}(x_i, x_j)$where neighboring node features are first transformed by a weight matrix $\mathbf{\Theta}$, normalized by their degree, and finally summed up. This formula can be divided into the following steps:
 Add selfloops to the adjacency matrix.
 Linearly transform node feature matrix.
 Normalize node features.
 Sum up neighboring node features.
 Return new node embeddings.
Pytorch Geometric provides the MessagePassing
class, all we need to do to implement GCN is write our update()
and message()
functions.
class GCNConv(MessagePassing):
def __init__(self, in_channels, out_channels):
super(GCNConv, self).__init__(aggr='add') # "Add" aggregation.
self.lin = torch.nn.Linear(in_channels, out_channels)
def forward(self, x, edge_index):
# x has shape [N, in_channels]
# edge_index has shape [2, E]
# Step 1: Add selfloops to the adjacency matrix.
edge_index = add_self_loops(edge_index, num_nodes=x.size(0))
# Step 2: Linearly transform node feature matrix.
x = self.lin(x)
# Step 35: Start propagating messages.
return self.propagate(edge_index, x=x)
def message(self, x_j, edge_index, size):
# x_j has shape [E, out_channels]
# Step 3: Normalize node features.
row, col = edge_index
deg = degree(row, size[0], dtype=x_j.dtype)
deg_inv_sqrt = deg.pow(0.5)
deg_inv_sqrt[deg_inv_sqrt == float('inf')] = 0
norm = deg_inv_sqrt[row] * deg_inv_sqrt[col]
return norm.view(1, 1) * x_j
def update(self, aggr_out):
# aggr_out has shape [N, out_channels]
# Step 5: Return new node embeddings.
return aggr_out
Note: Step 4 is done by setting aggr='add'
when initialising GCNConv
.
Wasn’t too bad, right? PyTorch Geometric offers implementations of most popular convolutional layers and provides lots of examples. Check it out on github.
Now we can get our hands dirty with a realworld problem. The Cora dataset consists of 2708 scientific publications classified into one of seven classes. The citation network consists of 5429 links. Each publication in the dataset is described by a 0/1valued word vector indicating the absence/presence of the corresponding word from the dictionary. We can create a simple model for the semisupervised classication of each publication in the graph. Our model is constructed as follows:
class Net(torch.nn.Module):
def __init__(self):
super(Net, self).__init__()
self.conv1 = GCNConv(dataset.num_features, 16)
self.conv2 = GCNConv(16, dataset.num_classes)
def forward(self):
x, edge_index, edge_weight = data.x, data.edge_index, data.edge_attr
x = F.relu(self.conv1(x, edge_index, edge_weight))
x = F.dropout(x, training=self.training)
x = self.conv2(x, edge_index, edge_weight)
return F.log_softmax(x, dim=1)
With just 140 nodes in the training set we are able to achieve >80% classification accuracy for the rest of the nodes, the resulting classified Cora dataset looks as follows:
Figure 2: Semisupervised node classification result on Cora dataset.
It shows that Geometric Deep Learning is an elegant and performant approach when dealing with nonEuclidean structures.
References

[1] Bronstein, Michael M., et al. “Geometric deep learning: going beyond euclidean data.” IEEE Signal Processing Magazine 34.4 (2017): 1842.

[2] Monti, Federico, Michael Bronstein, and Xavier Bresson. “Geometric matrix completion with recurrent multigraph neural networks.” Advances in Neural Information Processing Systems. 2017.

[3] Gainza, Pablo, et al. “Deciphering interaction fingerprints from protein molecular surfaces using geometric deep learning.” Nature Methods 17.2 (2020): 184192.

[4] Twitter: fabula_ai

[5] Veselkov, Kirill, et al. “HyperFoods: Machine intelligent mapping of cancerbeating molecules in foods.” Scientific reports 9.1 (2019): 112.

[6] Kipf, Thomas N., and Max Welling. “Semisupervised classification with graph convolutional networks.” arXiv preprint arXiv:1609.02907 (2016).

[7] Fey, Matthias, and Jan Eric Lenssen. “Fast graph representation learning with PyTorch Geometric.” arXiv preprint arXiv:1903.02428 (2019).