From Basics to GNNs
An Overview of Graph Neural Networks
Presented by PÂRȚACHI Profir-Petru
profir@nii.ac.jp
Supervised by SUGIYAMA Mahito
mahito@nii.ac.jp

Single-layered PerceptronΣ θThe basic formulation of a single-layered perceptron is𝑓 𝒙 = 𝜃 𝒘𝒙 + 𝒃
Where 𝒙 is the input, 𝒘 is the learnt weights and 𝒃 is the bias.
𝜃 is a non-linearity.
In the original formulation of the perceptron, 𝜃 is a step-function.
Representational Power: can learn any linearly separable collection ofN binary labels provided that the size of the input 𝒙 is greater than N.

Slide 2 of 14

Multi-layered Perceptron (MLP)
Starting from the multi-classification perceptron, chain perceptrons
layer-wise.
Adjust the weights using backpropagation.
Historically MLP tackled the XOR learning problem which the singlelayered perceptron cannot handle.

It is often a building block in modern Graph Neural Networks.
Slide 3 of 14

Fixed Assumptions in MLP
There are no intra-layer connections,instead all connections are inter-layer.
The aggregation of the signal happens via summation.

Each neuron holds only a scalar value.
Each update only depends on the neurons in the following layer.
Slide 4 of 14

Relaxing the Assumptions
Allow arbitrary edges.
Allow signal aggregation to happen via other methods:
maximum, minimum, summation, median, average.

Allow each neuron/node to have a vector representation.
Consider the current state of a node when updating the representation.
Slide 5 of 14

𝒢Graph Prediction Tasksne• Node level• Community detection, Node classification, Node representation learning.

• Edge level• Relationship learning, operator learning:e.g. collaboration/co-author prediction, scene narrative graph• Graph level• Graph classification:e.g. drug prediction/discovery
Slide 6 of 14

𝒢A Simple Graph Neural Networkne

Consider a graph 𝒢(𝒩,ℰ), where at each node n ∈ 𝒩 and each edge e∈ ℰ, we have an associated vector vₙ, respectively vₑ, representing thenode (respectively edge).
A simple Graph Neural Network, takes the graph 𝒢 and associates witheach node/edge an MLP whose output is then used for
node/edge/graph classification tasks.
MLPₙ := vₙ → fₙ
MLPₑ := vₑ → fₑ
MLP𝒢 := (fₙ,fₑ) → f 𝒢Slide 7 of 14

End-to-End Example of a GNN
Input Graph

GNN Blocks

Transformed GraphClassifier

Prediction

YSlide 8 of 14

Message Passing
Let’s add graph structure into the learning algorithm.
We do so in the following steps:
1. For each node n ∈ 𝒢 where N(n) are the nodes neighbouring n,form the set U = {vₙ’ ∣ n’ ∈ N(n)};2. Apply an aggregation function that reduces the set U to a single
vector v’ₙ;
3. Apply an update function f: (vₙ,v’ₙ) → vₙ.
(For edges, consider the dual graph and apply the above)
Slide 9 of 14

Message Passing
Layer N+1

Layer N+

[1,0,2,3,1][0,1,1,2,1][0,0,1,1,1][1,1,4,6,3][1,0,1,2,2]

fSlide 10 of 14

Representational PowerTheorem 1 †(R. Sato, 2020): For any message passing GNN and for any
graphs 𝒢 and ℋ, if the 1-WL algorithm outputs that 𝒢 and ℋ are“possibly isomorphic”, the vector representations associated with eachnode and edge in 𝒢 and ℋ are the same.
Note: k-WL first “gathers” the labels of all nodes in a neighbourhood,and then hashes this set to obtain a new label, it outputs “possiblyisomorphic” if after k steps, if the set of all neighbourhood label sets
are the same.

†R. Sato, A survey on the expressive power of graph neural networks (2020). arXiv: 2003.04078. Uses random features for positional encoding.

Slide 11 of 14

Short-comings and Current Research
Focusing primarily on Message Passing GNNs, there are two main
short-comings associated:
Oversmoothing: As the number of GNN layers is increased, the vector
representation of nodes and edges tends to a uniform distribution.
Oversquashing: Under certain (often common) graph configurations,information loss occurs as a single node has to encode updates from an
exponentially large neighbourhood.
Slide 12 of 14

Common Methods to Alleviate
Oversmoothing and Oversquashing
For oversmoothing:
Regularise and add noise to node level features
Residual connections
Reduce model depth
For oversquashing:
Increase model depth
Master node/Fully connected graph
Graph rewiring
Hierarchical message passing/Overlay networks
Slide 13 of 14

FinQuestions?