Introduction to Graph Neural Networks (GNN)

graph-nn
Author

gauneg

Published

November 28, 2025

Essential Components

The two essential components required for GNNs are:

  1. Node Features
  2. Adjacency Matrix (Relationships between Nodes)

Minimal Terminologies

  • Node Degree: No of edges on a node. (In-Degree, Out-Degree)

  • Centrality: Measure of node’s structural importance. It has multiple types:

    • Betweenness Centrality: How often does the node acts as a bridge along the shortest path between two other nodes.
    • Closeness Centrality: Average Distance from the node to all other reachable nodes in the graph.
    • Eigenvector Centrality: Measure of influence. A node connected to many high-degree nodes has high eigenvector centrality than a node connected to many low-degree nodes.

  • Graph Density: Undirected Graph \[\text{Density} = \frac{2 |E|}{|V|\times(|V|-1)}\] if Density is approx ~1.0 it is dense, ~0 spase.

import torch_geometric
from torch_geometric.datasets import Planetoid
from torch_geometric.nn import SAGEConv, GATConv
import torch.nn.functional as F
import torch
dataset = Planetoid(root="tutorial1", name="Cora")
print(f"Cora Graphs, {len(dataset)}")
print(f"Classes: {dataset.num_classes}")
print(f"Features: {dataset.num_features}")
Cora Graphs, 1
Classes: 7
Features: 1433

Graph Attention Network (GAT)

Implementing steps of GAT (simple)

STEPS:

  1. Linear Transformation
  2. Attention Calculation
  3. Weighing input with attention weight

STEP 1

\(W\) is initialized for linear projections

\(h\) here is \(h_i\) -> Linear projections obtained by \(h_i = W \times I\)

in_features = 5
out_features = 2
nb_nodes = 3

W = torch.nn.Parameter(torch.zeros(size=(in_features, out_features)))
torch.nn.init.xavier_uniform(W.data, gain=1.414)
inpx = torch.rand(nb_nodes, in_features)
h = torch.mm(inpx, W)

N = h.size()[0]
/var/folders/kr/021dhy4100546918_56lpp4m0000gn/T/ipykernel_14371/2968647810.py:6: UserWarning: nn.init.xavier_uniform is now deprecated in favor of nn.init.xavier_uniform_.
  torch.nn.init.xavier_uniform(W.data, gain=1.414)

STEP 2 : Attention Implementation

2.1 Initialising Parameters

\(a\): Parameters for attention calculation

\(a_{\text{input}}\): Cartesian of the graph nodes, i.e. The connection of every node to every other node. I think, how the attention will be used to express the relationships between the node is by modifying the weights of these connection matrix (sort of adjacency matrix) but with the properties of relationship learnt in these numbers.

a = torch.nn.Parameter(torch.zeros(size=(2*out_features, 1)))
torch.nn.init.xavier_normal(a.data, gain=1.414)

leaky_relu = torch.nn.LeakyReLU(0.2)
a_input = torch.cat([h.repeat(1, N).view(N * N, -1), h.repeat(N, 1)], dim=1).view(N, -1, 2 * out_features)

e = leaky_relu(torch.matmul(a_input, a).squeeze(2))
/var/folders/kr/021dhy4100546918_56lpp4m0000gn/T/ipykernel_14371/732829903.py:2: UserWarning: nn.init.xavier_normal is now deprecated in favor of nn.init.xavier_normal_.
  torch.nn.init.xavier_normal(a.data, gain=1.414)

2.2 Calculating attention values

  1. \(a_{\text{logit}} = a_{\text{input}}\times a\)

  2. Leaky Relu activation (E), \(E = ReLU_{\text{leaky}}(a_{\text{logit}})\)

e.shape, inpx.shape
(torch.Size([3, 3]), torch.Size([3, 5]))
print(a_input.shape, a.shape)
print("")
print(torch.matmul(a_input, a).shape)
print("")

torch.Size([3, 3, 4]) torch.Size([4, 1])

torch.Size([3, 3, 1])

2.3 Masked Attention

It is different than the mask in Bert, here masking is not continuous tokens, for mostly padding, but here it is used for marking connections using Adjacency Matrix.

\[\tilde{E} = E \odot A + (-\infty) \cdot (1-A)\]

The following snippet implements it:

  • Generates a matrix with size \(E\), with a very large negative (\(-\infty\)) value
  • Flip the mask and populate it with \(-\infty\) values i.e. replace (\(0 \rightarrow -\infty\))
adj = torch.randint(2, (3, 3))
zero_vec  = -9e15*torch.ones_like(e)
e
attention = torch.where(adj>0, e, zero_vec)

STEP 3. Applying attention

\(\alpha = \text{softmax}(\tilde{E})\)

\(h' = \alpha \times h\)

attention = F.softmax(attention, dim=1)
h_prime = torch.matmul(attention, h)
h
tensor([[ 0.7161, -0.3945],
        [ 0.5494, -0.4554],
        [-0.1075, -0.5380]], grad_fn=<MmBackward0>)
h_prime
tensor([[ 0.2763, -0.4898],
        [-0.1075, -0.5380],
        [ 0.7161, -0.3945]], grad_fn=<MmBackward0>)
test_arr = torch.tensor([1,2,3])

Exponential Linear Unit (ELU)

\[ELU(x) = \begin{cases} x &, if & x \gt 0 \\ \alpha(e^x -11) &, if & x \leq 0 \end{cases} \] By default, \(\alpha=1.0\)

Advantages over ReLU

  1. Mitigation of “dying ReLU” problem: \(ReLU(x) = 0 \text{ ,} \forall x\lt0\). It stops learning with negative pre-activation (“dies”). This preserves learning signal for negative inputs.
  2. Pushes mean activation closer to 0: ELU’s negative saturation counterbalances positive activations. Potentially reducing the need for batch normalization resulting in accelerated learning.
  3. Smoother Gradient Flow: It is continuously differentiable (when \(\alpha=0\)), avoiding abrupt changes in gradient at 0, which could lead to more stable training.

Q. Why not just use leakyReLU instead?

Leaky ReLU is simple, cheap, and often sufficient for many tasks (e.g., GANs, where it remains popular). ELU tends to perform better in deep feedforward or convolutional networks without batch normalization, as its saturation helps control activation statistics. However, when batch normalization is used, the advantage often diminishes.

GATLayer

Building GAT as a custorm pytorch Layer

There is no implementation of Multi-headed Attention (MHA) in this case. It is made for node classification problem.

Problem Statement

Given an undirected Graph, \(G=(\mathcal{V}, \mathcal{E})\), where \(\mathcal{V}\) is a set of \(N=2708\) nodes.

\(\mathcal{E} \subset \mathcal{V} \times \mathcal{V}\) is a set of \(|\mathcal{E}|=10556\) edges, represented by an edge index tensor \(E \in \mathbb{N}^{2 \times 10556}\)

Each node \(\mathcal{v}_i \in \mathcal{V}\) is associated with a feature vector \(x_i \in \mathbb{R}^{1433}\), collectively forming node feature matrix \(X \in \mathbb{R}^{2708 \times 1433}\).

Each node has a label with class assigned \(y_i \in \{1, 2, ..., 7\}\).

The task is to learn a function \(f_{\theta}: \mathbb{R}^{N \times D} \times \mathbb{N}^{2 \times |\mathcal{E}|} \rightarrow \{1, 2, ..., 7\}^{N}\)

In this eq:

\(\mathbb{R}^{N \times D}\): Node features (2708 \(\times\) 1433)

\(\mathbb{N}^{2 \times |\mathcal{E}|}\): Edge index

\(\theta\): learned parameters

class GATLayer(torch.nn.Module):
    def __init__(self, in_features, out_features, dropout, concat=True):
        super(GATLayer, self).__init__()
        self.n_in_features = in_features
        self.n_out_features = out_features
        
        self.W = torch.nn.Parameter(torch.zeros(size=(in_features, out_features)))
        torch.nn.init.xavier_uniform(self.W.data, gain=1.414)
        
        self.a = torch.nn.Parameter(torch.zeros(size=(2*out_features, 1)))
        torch.nn.init.xavier_normal(self.a.data, gain=1.414)
        self.leakyrelu = torch.nn.LeakyReLU(0.2)

    def forward(self, input_tensor, adj):
        assert input_tensor.shape[-1] == self.n_in_features, "number of features is different"
        h = torch.mm(input_tensor, self.W)
        N = h.size()[0]
        a_input = torch.cat([h.repeat(1, N).view(N * N, -1), h.repeat(N, 1)], dim=1).view(N, -1, 2 * out_features)
        e = self.leakyrelu(torch.matmul(a_input, a).squeeze(2))
        
        # adj = torch.randint(2, (3, 3))
        zero_vec  = -9e15*torch.ones_like(e)
        attention = torch.where(adj > 0, e, zero_vec)
        attention = F.softmax(attention, dim=1)
        attention = F.dropout(attention, self.dropout, training=self.training)
        h_prime   = torch.matmul(attention, h)
        if self.concat:
            return F.elu(h_prime)
        else:
            return h_prime

torch_geometric implementation of GAT

It has MHA, efficient implementation and ease of use.

class GAT(torch.nn.Module):
    def __init__(self):
        super(GAT, self).__init__()

        self.hid = 8
        self.in_head = 8
        self.out_head = 1

        self.conv1 = GATConv(dataset.num_features, self.hid, heads=self.in_head, dropout=0.6)
        self.conv2 = GATConv(self.hid*self.in_head, dataset.num_classes, concat=False, heads=self.out_head, dropout=0.6)

    def forward(self, data):
        x, edge_index = data.x, data.edge_index
        x = F.dropout(x, p=0.6, training=self.training)
        # print(f"Input shape Conv1: {x.shape}")
        x = self.conv1(x, edge_index)
        # print(f"Output shape Conv1, heads {self.in_head}: {x.shape}")
        x = F.elu(x)
        x = F.dropout(x, p=0.6, training=self.training)
        x = self.conv2(x, edge_index)
        # print(f"Output shape Conv2, heads {self.out_head}: {x.shape}")
        return F.log_softmax(x, dim=1)
data = dataset[0]
model = GAT()
optimizer = torch.optim.Adam(model.parameters(), lr=0.005, weight_decay=5e-4)

for epoch in range(1000):
    model.train()
    optimizer.zero_grad()
    out = model(data)
    loss = F.nll_loss(out[data.train_mask], data.y[data.train_mask])
    
    if epoch%200 == 0:
        print(loss)
    loss.backward()
    optimizer.step()
tensor(2.0154, grad_fn=<NllLossBackward0>)
tensor(0.4505, grad_fn=<NllLossBackward0>)
tensor(0.2827, grad_fn=<NllLossBackward0>)
tensor(0.3186, grad_fn=<NllLossBackward0>)
tensor(0.3924, grad_fn=<NllLossBackward0>)