# What would make Graph Neural Networks better than 'normal' Neural Networks?

I am quite new to the area of artificial intelligence and deep learning, so I am exploring some of the available techniques and models. Throughout my readings, I noticed a growing trend towards using Graph Neural Networks (GNNs) in recent years, so I would appreciate having some feedback from experts:

1. What are the main differences between GNN and NN (apart from GNN has a graph as its input)?

2. Consequently, what is the potential in using GNN instead of NN, for example in knowledge graphs and bases?

• I don't know much about about GNN's, but it would seem to me that one GNN's would need a sparse matrix implementation to scale up, as the size of the dense graph is $O(N^2)$ ($N$ = number of nodes), yet we rarely see moderate sized graphs with even 1% density. – Cliff AB Dec 19 '19 at 20:53

what are the main differences between GNN and NN? Apart from GNN has its input as a graph data?

Well, that is the main difference. Of course some corollaries of this fact is that GNNs can deal with variable sized graph inputs and typical NNs cannot, GNNs are not fully connected and typical (non-convolutional) NNs are, GNNs are usually invariant to permutation of the vertices and NNs are not.

In a bit more detail: Let $$A$$ be the adjacency matrix of some graph $$G$$, and let $$X$$ be an $$n \times d$$ matrix of features for each vertex, and let $$W$$ be a $$d \times d'$$ weight matrix. Then a graph neural network layer might compute something like $$Y = \sigma(AXW)$$. Inspired by spectral analysis, more sophisticated versions compute $$Y = \sigma(\sum_i L^iXW_i)$$ where $$L^i$$ is the $$i$$th power of the laplacian.

Just as in a convolutional network, the size of the weight matrix is independent of the graph -- you might interpret it as some sort of convolutional filter which can be slid over each vertex of the graph. Graphs with different sizes and connectivity simply alters $$A$$ and $$L$$, but not $$W$$.

Consequently, what is the potential in using GNN instead of NN, saying for eg in knowledge graphs and bases?

Applications are very wide, and include...

Language models which operate on parse-trees rather than just a linear sequence of words. Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks

Solving reading comprehension by maintaining a graph of the relationships between all the different entities in a story. Learning Graphical State Transitions

Learning a model of physics by inferring the graph of physical interactions between objects. Neural Relational Inference for Interacting Systems and Interaction Networks for Learning about Objects, Relations and Physics

Improving segmentation boundaries Efficient Interactive Annotation of Segmentation Datasets with Polygon-RNN++ by modeling object boundaries as a graph.

A richer form of object detecion which not only detects objects in an image but reveals their relationship to each other. Graph R-CNN for Scene Graph Generation

Generating and predicting molecules with particular chemical properties. Junction Tree Variational Autoencoder for Molecular Graph Generation

Generating and learning patterns in real world road patterns. Neural Turtle Graphics for Modeling City Road Layouts

Since meshes are also graphs, you can generate / segment / reconstruct, etc. 3D shapes as well. Pixel2Mesh: Generating 3D Mesh Models from Single RGB Images Dynamic Graph CNN for Learning on Point Clouds

Neural networks are computation graphs, so you could use GNNs to learn to generate better network architectures. Graph HyperNetworks for Neural Architecture Search

• "Of course some corollaries of this fact is that GNNs can deal with variable sized graph inputs and typical NNs cannot": can you explain this? If I just think of a GNN as NN that takes a graph as an input, I don't see why this would be true. If you could explain how this works, it would certainly help differentiate a GNN and a vanilla NN for me. – Cliff AB Dec 19 '19 at 20:56
• @CliffAB sure, i've added some details. – shimao Dec 19 '19 at 21:12
• Ah, so in the context of using $AX$, we're basically just taking the sum of features of your friends (in a social graph) as your features plugging into the NN? – Cliff AB Dec 19 '19 at 21:43
• @CliffAB yes -- however this is just a very simple example, many (most?) GNN implementations use a more sophisticated "aggregation" function. – shimao Dec 20 '19 at 14:44
• Okay, thanks, cleared up my confusion. +1. – Cliff AB Dec 20 '19 at 17:23