Graph Neural Networks — Deep Dive

GNNs learn on graph-structured data by aggregating information from node neighborhoods. They generalize neural networks to irregular, non-Euclidean data structures.

Graph Data

DfGraph

A graph $G = (V, E)$ consists of:

Nodes $V$ : $\{v_1, \ldots, v_N\}$ — entities (people, molecules, papers)
Edges $E$ : $\{(v_i, v_j)\}$ — relationships (friendships, bonds, citations)
Node features $X \in \mathbb{R}^{N \times d}$ : Feature matrix
Adjacency matrix $A \in \{0, 1\}^{N \times N}$ : Connectivity

Common graph types: citation networks, molecular graphs, social networks, knowledge graphs, point clouds.

Message Passing Framework

h_v^{(k+1)} = \text{UPDATE}\left(h_v^{(k)}, \text{AGGREGATE}\left(\{m_{u \to v} : u \in \mathcal{N}(v)\}\right)\right)

Message Function

m_{u \to v}^{(k)} = \text{MSG}^{(k)}(h_u^{(k)}, h_v^{(k)}, e_{uv})

Here,

$h_u^{(k)}$ =Node u's representation at layer k
$h_v^{(k)}$ =Node v's representation at layer k
$e_{uv}$ =Edge features (if any)
$\mathcal{N}(v)$ =Neighbors of node v

Aggregation Function

\bar{h}_v^{(k)} = \text{AGG}^{(k)}(\{m_{u \to v}^{(k)} : u \in \mathcal{N}(v)\})

Here,

$\text{AGG}$ =Aggregation function (mean, max, sum, attention)
$\bar{h}_v^{(k)}$ =Aggregated neighborhood message

Update Function

h_v^{(k+1)} = \text{UPDATE}^{(k)}(h_v^{(k)}, \bar{h}_v^{(k)})

Here,

$\text{UPDATE}$ =Update function (e.g., GRU, MLP, residual connection)

Graph Convolutional Network (GCN)

DfGCN Layer

GCN (Kipf & Welling, 2017) performs spectral-inspired convolution on graphs:

h_v^{(k+1)} = \sigma\left(\sum_{u \in \mathcal{N}(v) \cup \{v\}} \frac{1}{\sqrt{\hat{d}_u \hat{d}_v}} W^{(k)} h_u^{(k)}\right)

where $\hat{d}_v = |\mathcal{N}(v)| + 1$ is the degree plus self-loop.

GCN Layer (Matrix Form)

H^{(k+1)} = \sigma\left(\tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2} H^{(k)} W^{(k)}\right)

Here,

$\tilde{A}$ =A + I (adjacency with self-loops)
$\tilde{D}$ =Degree matrix of \tilde{A}
$W^{(k)}$ =Learnable weight matrix at layer k
$H^{(k)}$ =Node representations at layer k

GraphSAGE

DfGraphSAGE

GraphSAGE (Hamilton et al., 2017) enables inductive learning by sampling and aggregating from neighborhoods:

Sample $K$ neighbors from $\mathcal{N}(v)$
Aggregate using mean, LSTM, or pooling
Concatenate with node's own features
Transform with MLP

Key advantage: Can generate embeddings for unseen nodes (inductive).

GraphSAGE Update

h_v^{(k+1)} = \sigma\left(W^{(k)} \cdot \text{CONCAT}(h_v^{(k)}, \text{AGG}(\{h_u^{(k)} : u \in S_{\mathcal{N}(v)}\}))\right)

Here,

$S_{\mathcal{N}(v)}$ =Sampled subset of neighbors
$\text{AGG}$ =Aggregator (mean, LSTM, pooling)
$\text{CONCAT}$ =Concatenation of self and neighborhood features

Graph Attention Network (GAT)

DfGAT

GAT (Veličković et al., 2018) uses attention to weight neighbor contributions:

\alpha_{uv} = \frac{\exp(\text{LeakyReLU}(a^T [W h_u \| W h_v]))}{\sum_{k \in \mathcal{N}(v)} \exp(\text{LeakyReLU}(a^T [W h_k \| W h_v]))}

h_v^{(k+1)} = \sigma\left(\sum_{u \in \mathcal{N}(v)} \alpha_{uv} W h_u^{(k)}\right)

GAT Attention Coefficients

\alpha_{uv} = \frac{\exp(\text{LeakyReLU}(a^T [W h_u \| W h_v]))}{\sum_{k \in \mathcal{N}(v)} \exp(\text{LeakyReLU}(a^T [W h_k \| W h_v]))}

Here,

$\alpha_{uv}$ =Attention weight from u to v
$a$ =Attention parameter vector
$W$ =Shared linear transformation
$\|$ =Concatenation

Over-Smoothing

ThOver-Smoothing in GNNs

As the number of GNN layers increases, node representations converge to the same vector regardless of initial features:

\lim_{k \\to \\infty} H^{(k)} = \mathbf{1} v^T

for some vector $v$ . This means deep GNNs lose the ability to distinguish nodes, limiting practical depth to 2-3 layers.

Graph Neural Networks — Deep Dive

Graph Neural Networks — Deep Dive

Graph Data

DfGraph

Message Passing Framework

Message Function

Aggregation Function

Update Function

Graph Convolutional Network (GCN)

DfGCN Layer

GCN Layer (Matrix Form)

GraphSAGE

DfGraphSAGE

GraphSAGE Update

Graph Attention Network (GAT)

DfGAT

GAT Attention Coefficients

Over-Smoothing

ThOver-Smoothing in GNNs

Need Expert Deep Learning Help?