Introduction to Graph Data

Traditional deep learning models, such as Convolutional Neural Networks (CNNs), excel at processing Euclidean data like images and sequences, where data points have a regular structure and fixed neighbor definitions. However, many real-world datasets—social networks, molecular structures, and citation networks—are Non-Euclidean. In these graphs, the number of neighbors varies, and the connections are irregular, making standard convolution operations inapplicable.

Graph Neural Networks (GNNs) bridge this gap by extending neural network architectures to graph-structured data. A graph is typical defined as $G=(V, E)$, where $V$ represents the set of nodes (entities) and $E$ represents the set of edges (relationships). Key matrix representations include:

• Adjacency Matrix ($A$): A square matrix where $A_{ij} = 1$ if a connection exists between node $i$ and node $j$, and $0$ otherwise.
• Degree Matrix ($D$): A diagonal matrix where $D_{ii}$ equals the number of edges connected to node $i$.

Using libraries like networkx, we can construct and analyze these structures programmatically.

import networkx as nx
import numpy as np

# Initialize a random graph
G = nx.Graph()
G.add_edges_from([('NodeA', 'NodeB'), ('NodeB', 'NodeC')])

# Convert to adjacency matrix
adj_matrix = nx.to_numpy_array(G)
print(adj_matrix)

Graph Convolutional Networks (GCN)

Graph Convolutional Networks form the backbone of modern GNN architectures. The core operation involves propagating information across the graph structure. A naive approach might define a layer as $f(X, A) = \sigma(AXW)$, where $X$ is the feature matrix and $W$ is the learnable weight matrix.

However, this formulation presents two issues:

1. Self-loops: Multiplying by $A$ aggregates neighbor features but ignores the node's own features.
2. Normalization: Nodes with high degrees will have large feature values, causing instability during training.

To resolve this, the GCN layer applies a renormalization trick. The modified propagation rule is:

$$f(X, A) = \sigma(\hat{D}^{-1/2}\hat{A}\hat{D}^{-1/2}XW)$$

Where $\hat{A} = A + I$ (adding self-loops) and $\hat{D}$ is the degree matrix of $\hat{A}$. This symmetric normalization ensures stable gradient flow.

GCN Implementation

Below is an implementation using torch_geometric, a popular geometric deep learning library. We define a two-layer GCN for a classification task.

import torch
import torch.nn.functional as F
from torch_geometric.nn import GCNConv

class GCNClassifier(torch.nn.Module):
    def __init__(self, input_dim, hidden_dim, output_dim):
        super(GCNClassifier, self).__init__()
        self.conv_layer1 = GCNConv(input_dim, hidden_dim)
        self.conv_layer2 = GCNConv(hidden_dim, output_dim)
        self.optimizer = torch.optim.Adam(self.parameters(), lr=0.01)

    def forward(self, node_features, edge_index):
        # First GCN layer with ReLU activation
        x = self.conv_layer1(node_features, edge_index)
        x = F.relu(x)
        
        # Second GCN layer for output
        x = self.conv_layer2(x, edge_index)
        return F.log_softmax(x, dim=1)

Graph Attention Networks (GAT)

While GCNs assign equal weight to all neighbor during aggregation, Graph Attention Networks leverage attnetion mechanisms to learn the relative importance of each neighbor. This allows the model to focus on the most relevant parts of the graph structure.

The GAT layer computes attention coefficients $e_{ij}$ indicating the importance of node $j$ to node $i$:

$$e_{ij} = a(W\vec{h_i}, W\vec{h_j})$$

These coefficients are normalized using softmax. The output feature for node $i$ is then computed as a weighted sum of its neighbors' features.

GAT Attention Mechanism (NumPy Implementation)

The following code demonstrates the attention calculation logic using NumPy to clarify the internal mathematics.

import numpy as np

def leaky_relu(x, alpha=0.2):
    return np.maximum(alpha * x, x)

def softmax_2d(x, axis):
    e_x = np.exp(x - np.max(x, axis=axis, keepdims=True))
    return e_x / np.sum(e_x, axis=axis, keepdims=True)

def compute_gat_features(features, adj_matrix, weight_matrix, attention_vector):
    # Linear transformation
    h_transformed = features @ weight_matrix
    
    # Get connected nodes
    rows, cols = np.where(adj_matrix > 0)
    
    # Calculate attention scores (concatenating source and target features)
    # In practice, this is often done via efficient matrix operations
    concat_features = np.concatenate([h_transformed[rows], h_transformed[cols]], axis=1)
    attention_scores = leaky_relu(concat_features @ attention_vector)
    
    # Normalize attention scores using softmax
    # Note: This is a simplified conceptual implementation
    # A real implementation would group scores by source node before softmax
    alpha = softmax_2d(attention_scores, axis=0)
    
    # Aggregate features (conceptual)
    # output = aggregate(alpha, h_transformed)
    return alpha

Inductive Learning with GraphSAGE

GraphSAGE (Sample and Aggregate) addresses the challenge of generalizing to unseen nodes. Instead of training an embedding for every node, it learns an aggregator function that generates embeddings by sampling and aggregating features from a node's local neighborhood.

The algorithm follows three steps:

1. Sample: Randomly sample a fixed number of neighbors.
2. Aggregate: Aggregate neighbor features (using Mean, LSTM, or Pooling aggregators).
3. Predict: Concatenate the aggregated vector with the node's current representation and pass it through a dense layer.

Node Classification Task

A common practical application is node classification, where we predict missing labels for nodes in a graph. Using the Facebook Page-Page dataset, we can compare a simple MLP (which ignores graph structure) against a GNN model.

The GNN model leverages the adjacency matrix to propagate label information across connected nodes, typically resulting in superior performance compared to models that treat nodes independently.

import torch
from torch_geometric.datasets import FacebookPagePage
from torch_geometric.utils import to_dense_adj

# Load dataset
dataset = FacebookPagePage(root='./data/facebook')
data = dataset[0]
data.train_mask = range(18000)
data.test_mask = range(18000, 22000)

# Prepare adjacency matrix with self-loops
adj = to_dense_adj(data.edge_index)[0]
adj = adj + torch.eye(adj.size(0))

class VanillaGNNLayer(torch.nn.Module):
    def __init__(self, in_channels, out_channels):
        super().__init__()
        self.linear = torch.nn.Linear(in_channels, out_channels)

    def forward(self, x, adjacency):
        return torch.sparse.mm(adjacency, self.linear(x))

class GNNNodeClassifier(torch.nn.Module):
    def __init__(self, in_dim, hidden_dim, out_dim):
        super().__init__()
        self.layer1 = VanillaGNNLayer(in_dim, hidden_dim)
        self.layer2 = VanillaGNNLayer(hidden_dim, out_dim)

    def forward(self, x, adj):
        h = self.layer1(x, adj).relu()
        h = self.layer2(h, adj)
        return F.log_softmax(h, dim=1)

# Initialize and train
model = GNNNodeClassifier(dataset.num_features, 16, dataset.num_classes)
optimizer = torch.optim.Adam(model.parameters(), lr=0.01)
criterion = torch.nn.CrossEntropyLoss()

def train():
    model.train()
    optimizer.zero_grad()
    out = model(data.x, adj)
    loss = criterion(out[data.train_mask], data.y[data.train_mask])
    loss.backward()
    optimizer.step()
    return loss.item()

for epoch in range(100):
    loss = train()
    if epoch % 20 == 0:
        print(f'Epoch {epoch}, Loss: {loss:.4f}')

Spatio-Temporal Graph Neural Networks (STGNN)

Beyond static graphs, many tasks involve spatial-temporal data, such as traffic flow prediction. STGNNs combine Graph Convolutional Networks (GCN) to capture spatial dependencies with Convolutional Neural Networks (CNN) or RNNs to capture temporal dynamics. This architecture typically employs a "sandwich" structure: Temporal Convolution -> Spatial Graph Convolution -> Temporal Convolution, allowing the model to effectively learn patterns across both time and space.