Adjacency matrix:
[[0 1 1 0]
[1 0 1 0]
[1 1 0 1]
[0 0 1 0]]
Leffingwell Odor Dataset
Leffingwell Odor Dataset: Composed of molecules with associated odor percepts (labels).
Data: Represent each molecule as a graph, atoms are nodes containing a one-hot encoding for atomic identity (Carbon, Nitrogen, Oxygen, Fluorine) and bonds are edges containing a bond type one-hot encoding (single, double, triple or aromatic).Build our model using sequential GNN layers, followed by a linear model with a sigmoid activation for classification.
The design space for our GNN has many hyper-parameters that can customize the model:
The number of GNN layers, also called the depth.
The dimensionality of each attribute when updated. The update function is a 1-layer MLP with a relu activation function and a layer norm for normalization of activations.
The aggregation function used in pooling: max, mean or sum.
The graph attributes that get updated, or styles of message passing: nodes, edges and global representation. We control these via boolean toggles (on or off).
A baseline model would be a graph-independent GNN (all message-passing off) which aggregates all data at the end into a single global attribute. Toggling on all message-passing functions yields a GraphNets architecture.
For this graph level prediction task, each graph is a molecule. The task is to predict whether or not a molecule will smell pungent. In the scatter plot, each point represents a graph.
You can edit the molecule to see how the prediction changes, or change the model params to load a different model.
Select a different molecule in the scatter plot.
Big picture overview
W is applied at every node’s neighborhood: the same weights everywhere.The full assembly line:
Here we use node level classification as an example, but below we will see how this pipeline can be used for different learning tasks.
A single layer is the composition of three familiar operations:
W (a linear re-expression).ReLU (so stacked layers aren’t just one big linear map).That’s the whole layer. Everything else is bookkeeping.
Textbook example
Adjacency matrix:
[[0 1 1 0]
[1 0 1 0]
[1 1 0 1]
[0 0 1 0]]
Node feature matrix:
[[0. 1. 0.]
[0. 0. 1.]
[0. 1. 0.]
[1. 0. 0.]]
\[ \boldsymbol{x}_i^{\prime}=\boldsymbol{x}_i \boldsymbol{W}_1+\sum_{j \in N(i)} x_j \boldsymbol{W}_2+b \]
np.dot() in NumPy performs the dot product of two arrays.
inner product;matrix multiplication.notice how the following are equivalent
dot:
[[6 4]
[6 4]]
matmul:
[[6 4]
[6 4]]
locality prior on graph holds.
Let make some random matrices to “act as” the weight matrices.
f_in: 3
f_out: 6
W_1: (3, 6)
W_2: (3, 6)
b: (1, 6)
W_1:
[[0.43599 0.02593 0.54966 0.43532 0.42037 0.33033]
[0.20465 0.61927 0.29965 0.26683 0.62113 0.52914]
[0.13458 0.51358 0.18444 0.78534 0.85398 0.49424]]
W_2:
[[0.84656 0.07965 0.50525 0.06529 0.42812 0.09653]
[0.12716 0.59675 0.22601 0.10695 0.22031 0.34983]
[0.46779 0.20174 0.64041 0.48307 0.50524 0.38689]]
b:
[[0.79364 0.58 0.1623 0.70075 0.96455 0.50001]]
\[x_i^{\prime}=x_i W_1+\sum_{j \in N(i)} x_j W_2+b\]
This is a batch implementation, if we multiply on the left by X, we apply the transformation the feature vectors of all nodes.
Lets first implement the sum of the weighted inputs for each node.
\[x_i^{\prime}=x_i W_1+\sum_{j \in N(i)} x_j W_2+b\]
NODE-0
node 0: [0. 1. 0.]
X[i].shape: (3,), W_1.shape: (3, 6)
self_update: [0.20465 0.61927 0.29965 0.26683 0.62113 0.52914], shape: (6,)
neighbor_update: [0.59495 0.79849 0.86642 0.59002 0.72555 0.73672], shape: (6,)
output:
[[1.59324 1.99776 1.32837 1.5576 2.31123 1.76587]
[1.18254 2.28708 0.79876 1.69999 2.25915 1.69391]
[2.4398 2.07741 1.83362 1.62289 2.73935 1.8624 ]
[1.35679 1.20268 0.93797 1.24302 1.60523 1.18017]]
(4, 6)
We can get the exact same result in a much more compact and efficient manner by using matrix multiplication.
A:
[[0 1 1 0]
[1 0 1 0]
[1 1 0 1]
[0 0 1 0]]
W_1: (3, 6)
W_2: (3, 6)
(4, 3) (3, 6) (4, 6)
[[1.59324 1.99776 1.32837 1.5576 2.31123 1.76587]
[1.18254 2.28708 0.79876 1.69999 2.25915 1.69391]
[2.4398 2.07741 1.83362 1.62289 2.73935 1.8624 ]
[1.35679 1.20268 0.93797 1.24302 1.60523 1.18017]]
Let’s see how these equations are generalized into matrix form.
\[ \mathbf{h}_i^{(k+1)}=\sigma\left(\sum_{j \in \mathcal{N}(i) \cup\{i\} } \frac{1}{c_{i j}} \mathbf{W}^{(k)} \mathbf{h}_j^{(k)}\right) \]
Explanation of Components:
Layer-Wise Propagation:
\[ \mathbf{H}^{(k+1)}=\sigma\left(\hat{\mathbf{D}}^{-\frac{1}{2}} \hat{\mathbf{A}} \hat{\mathbf{D}}^{-\frac{1}{2}} \mathbf{H}^{(k)} \mathbf{W}^{(k)}\right) \]
{1, 2, 3}. Right: the values get blended.W, a matrix learned by gradient descent.
W changes the feature dimension (e.g. F -> H) and lets the layer emphasize useful directions.W is used for every node (weight sharing: more soon).ReLU element-wise.
\[H^{(l+1)} = \sigma\!\left(\hat{A}\, H^{(l)}\, W^{(l)}\right)\]
where \(\hat A\) = normalized aggregation, \(W^{(l)}\) = shared weights, \(\sigma\) = ReLU, and \(H^{(0)} = X\).
Why raw aggregation breaks
A.A·x blows up at the hub; ·x stays tame.\[\hat{A} = \tilde{D}^{-1/2}\,(A+I)\,\tilde{D}^{-1/2}, \qquad \tilde{A}=A+I\]
Watch the four matrices for our 8-node graph:
X : N × F (nodes × input features)Z: N × C (C = number of classes)P: N × C, then argmax → one class per node.C logits of each node.W.The 2–3 layer rule & over-smoothing
H = 16–64) is plenty for small benchmarks.ReLU + dropout; a final softmax head for classification.PairNorm (Week 2).W (like a CNN kernel) is reused at every node → few params, generalizes.A GCN is just a module:
Â-blend,W-transform, repeat a couple times, then classify.
A Single Graph Convolution Layer
We will perform one forward pass of a Graph Convolutional Network (GCN) using the standard layer equation
\[ \mathbf{H}^{(k+1)} = \sigma\!\left( \hat{\mathbf{D}}^{-1/2} \hat{\mathbf{A}} \hat{\mathbf{D}}^{-1/2} \mathbf{H}^{(k)} \mathbf{W}^{(k)} \right) \]
where
Step 1: Define a Small Graph
Consider three nodes connected in a chain.
The adjacency matrix is
\[ \mathbf{A} = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}. \]
Adding self-loops gives
\[ \hat{\mathbf{A}} = \mathbf{A}+\mathbf{I} = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 1 \end{bmatrix}. \]
The node degrees are
\[ [2,\;3,\;2], \]
so
\[ \hat{\mathbf{D}} = \begin{bmatrix} 2 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 2 \end{bmatrix}. \]
Step 2: Initial Node Features
Suppose each node has two features.
\[ \mathbf{H}^{(0)} = \mathbf{X} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{bmatrix}. \]
Step 3: Choose a Simple Weight Matrix
For this toy example, let
\[ \mathbf{W} = \mathbf{I} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}. \]
This lets us focus only on the aggregation performed by the graph.
Step 4: Normalize the Adjacency Matrix
The normalized adjacency matrix is
\[ \hat{\mathbf{A}}_{\text{norm}} = \hat{\mathbf{D}}^{-1/2} \hat{\mathbf{A}} \hat{\mathbf{D}}^{-1/2}. \]
Using
\[ \frac{1}{\sqrt{2}} \approx 0.707, \qquad \frac{1}{\sqrt{3}} \approx 0.577, \]
we obtain
\[ \hat{\mathbf{A}}_{\text{norm}} \approx \begin{bmatrix} 0.500 & 0.408 & 0 \\ 0.408 & 0.333 & 0.408 \\ 0 & 0.408 & 0.500 \end{bmatrix}. \]
Notice that every row sums to approximately one, so each node computes a weighted average of itself and its neighbors.
Step 5: Aggregate Neighbor Information
Compute
\[ \hat{\mathbf{A}}_{\text{norm}} \mathbf{H}^{(0)}. \]
For Node 1
\[ 0.500 \begin{bmatrix}1\\0\end{bmatrix} + 0.408 \begin{bmatrix}0\\1\end{bmatrix} = \begin{bmatrix} 0.500\\ 0.408 \end{bmatrix}. \]
For Node 2
\[ 0.408 \begin{bmatrix}1\\0\end{bmatrix} + 0.333 \begin{bmatrix}0\\1\end{bmatrix} + 0.408 \begin{bmatrix}1\\1\end{bmatrix} = \begin{bmatrix} 0.816\\ 0.741 \end{bmatrix}. \]
For Node 3
\[ 0.408 \begin{bmatrix}0\\1\end{bmatrix} + 0.500 \begin{bmatrix}1\\1\end{bmatrix} = \begin{bmatrix} 0.500\\ 0.908 \end{bmatrix}. \]
Thus,
\[ \hat{\mathbf{A}}_{\text{norm}} \mathbf{H}^{(0)} = \begin{bmatrix} 0.500 & 0.408 \\ 0.816 & 0.741 \\ 0.500 & 0.908 \end{bmatrix}. \]
Step 6: Apply the Weight Matrix
Since
\[ \mathbf{W} = \mathbf{I}, \]
nothing changes:
\[ \hat{\mathbf{A}}_{\text{norm}} \mathbf{H}^{(0)} \mathbf{W} = \begin{bmatrix} 0.500 & 0.408 \\ 0.816 & 0.741 \\ 0.500 & 0.908 \end{bmatrix}. \]
Step 7: Apply the Activation Function
Using ReLU,
\[ \sigma(x) = \max(0, x), \]
all entries are already positive, so
\[ \mathbf{H}^{(1)} = \begin{bmatrix} 0.500 & 0.408 \\ 0.816 & 0.741 \\ 0.500 & 0.908 \end{bmatrix}. \]
Final Result
After one GCN layer, the node embeddings become
\[ \boxed{ \mathbf{H}^{(1)} = \begin{bmatrix} 0.500 & 0.408 \\ 0.816 & 0.741 \\ 0.500 & 0.908 \end{bmatrix} } \]
Interpretation
The graph convolution layers are usually identical across tasks. The primary difference between node, graph, and edge prediction is how the learned node embeddings are transformed by the final prediction head.
Graph
│
▼
Graph Convolution Layers
│
▼
Node Embeddings
(h₁, h₂, ..., hₙ)
│
▼
Task-Specific Prediction Head
│
▼
PredictionsThe graph convolution layers produce a learned embedding for every node. The way these embeddings are used depends on the prediction task.
| Task | Input to Prediction Head | Typical Prediction |
|---|---|---|
| Node Classification | Single node embedding | Class label for each node |
| Node Regression | Single node embedding | Continuous value for each node |
| Graph Classification | Pool all node embeddings into one graph embedding | One class for the entire graph |
| Graph Regression | Pool all node embeddings into one graph embedding | Continuous value for the entire graph |
| Edge Classification | Combine embeddings of the two endpoint nodes | Edge class (exists, type, relationship) |
| Edge Regression | Combine embeddings of the two endpoint nodes | Continuous edge value (weight, distance, score) |
Each node is processed independently after message passing.
For graph-level prediction, the GCN produces an embedding for every node. Since graphs contain different numbers of nodes, these embeddings must be pooled into a single fixed-length graph embedding before making a prediction.
Common pooling methods include:
Node Embeddings
(h₁, h₂, ..., hₙ)
│
▼
Global Pooling
(mean / sum / max / attention)
│
▼
Graph Embedding
│
▼
Prediction HeadThe pooling operation is often called the graph readout layer because it converts a variable-sized set of node embeddings into a single graph representation suitable for graph classification or regression.
All Node Embeddings
(h₁, h₂, ..., hₙ)
│
▼
Global Pooling
(mean / sum / max / attention)
│
▼
Graph Embedding
│
▼
Fully Connected Layer
│
▼
PredictionThe node embeddings are aggregated into a single graph representation before making a prediction.
Node Embedding hᵢ Node Embedding hⱼ
│ │
└──── Combine ─────────┘
(concat, dot product,
element-wise product)
│
▼
Fully Connected Layer
│
▼
PredictionPredictions are made using the embeddings of the two nodes that define the edge.
This content is drawn primarily from the following sources: