๐Ÿง  GNN Foundations

๐ŸŽฏ What are Graph Neural Networks?

Graph Neural Networks (GNNs) are deep learning models designed to operate on graph-structured data, leveraging the relational structure of nodes and edges for representation learning.

Core Concepts

Graph representation: Nodes (vertices) and edges (connections). Message passing: Nodes exchange information with neighbors. Node embeddings: Learn low-dimensional vector representations.

๐Ÿ“Œ Graph๐Ÿ“Œ Message Passing๐Ÿ“Œ Embeddings
import torch import torch.nn as nn import torch.nn.functional as F # Simple Graph Neural Network layer class GNNLayer(nn.Module): def __init__(self, in_features, out_features): super().__init__() self.linear = nn.Linear(in_features, out_features) def forward(self, x, adj): # x: node features (N, in_features) # adj: adjacency matrix (N, N) # Aggregate neighbor features aggr = torch.matmul(adj, x) # Apply linear transformation return self.linear(aggr)

๐Ÿ”— Graph Theory Basics

๐ŸŽฏ Graph Fundamentals

Graphs consist of nodes (vertices) connected by edges. They can be directed or undirected, weighted or unweighted, with or without self-loops.

Graph Concepts

Degree: Number of edges connected to a node. Adjacency matrix: Nร—N matrix representing connections. Laplacian: D - A for spectral graph theory.

๐Ÿ”— Degree๐Ÿ“Š Adjacency๐Ÿ“ Laplacian
import networkx as nx import numpy as np # Create a graph G = nx.erdos_renyi_graph(10, 0.3) # Get adjacency matrix A = nx.adjacency_matrix(G).todense() # Compute degree matrix degrees = np.diag(np.sum(A, axis=1)) # Compute Laplacian L = degrees - A print(f"Graph has {G.number_of_nodes()} nodes and {G.number_of_edges()} edges") print(f"Adjacency matrix shape: {A.shape}")

๐Ÿ“จ Message Passing

๐ŸŽฏ Information Propagation

Message passing is the core mechanism of GNNs โ€” nodes aggregate messages from neighbors and update their representations.

Message Passing Steps

Message: Transform node features. Aggregate: Sum, mean, max, or attention. Update: Combine old and aggregated features.

๐Ÿ“จ Message๐Ÿ“Š Aggregate๐Ÿ”„ Update
class MessagePassingLayer(nn.Module): def __init__(self, in_dim, out_dim, aggr='sum'): super().__init__() self.message_fn = nn.Linear(in_dim, out_dim) self.aggr = aggr self.update_fn = nn.Linear(in_dim + out_dim, out_dim) def forward(self, x, edge_index): # edge_index: (2, E) COO format # Send messages along edges messages = self.message_fn(x) # (N, out_dim) # Aggregate messages (scatter) if self.aggr == 'sum': aggr_msgs = torch.zeros_like(x) for i, (src, dst) in enumerate(edge_index.t()): aggr_msgs[dst] += messages[src] # Update node features return self.update_fn(torch.cat([x, aggr_msgs], dim=1))

๐Ÿ“Š Graph Convolutional Networks

๐ŸŽฏ Spectral Convolution

GCNs apply convolutional filters to graphs using spectral graph theory. They are the foundation of modern GNNs.

GCN Formulation

H^{l+1} = ฯƒ( \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2} H^l W^l ). Where \tilde{A} = A + I, \tilde{D} = degree(\tilde{A}).

๐Ÿ“Š Spectral๐Ÿ”„ Normalized๐Ÿ“ˆ Multi-layer
class GCNLayer(nn.Module): def __init__(self, in_features, out_features, dropout=0.1): super().__init__() self.linear = nn.Linear(in_features, out_features) self.dropout = nn.Dropout(dropout) def forward(self, x, adj): # Normalized adjacency: D^{-1/2} A D^{-1/2} degrees = torch.sum(adj, dim=1) D_inv_sqrt = torch.diag(1.0 / torch.sqrt(degrees + 1e-8)) adj_norm = D_inv_sqrt @ adj @ D_inv_sqrt # Convolution x = self.dropout(x) x = self.linear(x) x = adj_norm @ x return F.relu(x)

๐Ÿ‘€ Graph Attention Networks

๐ŸŽฏ Attention Mechanisms

GAT uses self-attention to weight neighbor contributions, allowing the model to focus on the most relevant neighbors.

Attention Benefits

Weighted aggregation: Learn importance of each neighbor. Multi-head: Multiple attention heads for stability. No adjacency normalization needed.

๐Ÿ‘€ Self-Attention๐Ÿ“Š Multi-Headโšก Learnable Weights
class GATLayer(nn.Module): def __init__(self, in_dim, out_dim, num_heads=8): super().__init__() self.num_heads = num_heads self.W = nn.Linear(in_dim, out_dim * num_heads) self.a = nn.Parameter(torch.zeros(out_dim * num_heads, 1)) def forward(self, x, edge_index): x = self.W(x) # (N, out_dim * num_heads) # Compute attention scores # For each edge, compute attention attention = [] for src, dst in edge_index.t(): src_feat = x[src] dst_feat = x[dst] # Compute attention score alpha = torch.sigmoid(torch.matmul(torch.cat([src_feat, dst_feat]), self.a)) attention.append(alpha) attention = torch.softmax(torch.stack(attention), dim=0) # Aggregate return attention

๐Ÿงช Graph Isomorphism Networks

๐ŸŽฏ Maximally Expressive GNNs

GIN is provably as powerful as the Weisfeiler-Lehman graph isomorphism test, making it the most expressive GNN architecture.

GIN Innovations

MLP instead of linear: Universal approximator. Learnable epsilon: ฮผ = (1+ฮต) x + aggregate. Sum aggregation: More expressive than mean/max.

๐Ÿงช MLP-Based๐Ÿ“Š Sum Aggregation๐Ÿ”ฌ WL-Test
class GINLayer(nn.Module): def __init__(self, in_dim, out_dim): super().__init__() self.mlp = nn.Sequential( nn.Linear(in_dim, out_dim), nn.ReLU(), nn.Linear(out_dim, out_dim) ) self.eps = nn.Parameter(torch.tensor(0.0)) def forward(self, x, adj): # Sum aggregation aggr = torch.matmul(adj, x) # Center node features with eps x = (1 + self.eps) * x + aggr return self.mlp(x)

๐Ÿ“ˆ Graph-Level Tasks

๐ŸŽฏ Whole Graph Prediction

Graph-level tasks involve predicting properties of entire graphs, such as molecular properties or graph classification.

Graph-Level Methods

Readout: Aggregate node embeddings (sum, mean, max, attention). Set pooling: Deep Sets, SortPool. Graph kernels: Traditional ML approach.

๐Ÿ“ˆ Readout๐Ÿ“Š Pooling๐Ÿ”ฌ Classification
class GraphLevelGNN(nn.Module): def __init__(self, node_dim, hidden_dim, output_dim): super().__init__() self.gcn1 = GCNLayer(node_dim, hidden_dim) self.gcn2 = GCNLayer(hidden_dim, hidden_dim) self.readout = nn.Linear(hidden_dim, output_dim) def forward(self, x, adj): x = self.gcn1(x, adj) x = self.gcn2(x, adj) # Readout: graph-level representation graph_rep = torch.mean(x, dim=0) # Simple mean return self.readout(graph_rep)

๐ŸŽฏ Node-Level Tasks

๐ŸŽฏ Node Classification & Regression

Node-level tasks predict properties of individual nodes, such as node classification, regression, or community detection.

Node Applications

Semi-supervised: Few labeled nodes, many unlabeled. Transductive: All nodes known during training. Inductive: New nodes can appear.

๐ŸŽฏ Classification๐Ÿ“Š Regression๐Ÿ” Community
class NodeLevelGNN(nn.Module): def __init__(self, node_dim, hidden_dim, num_classes): super().__init__() self.conv1 = GCNLayer(node_dim, hidden_dim) self.conv2 = GCNLayer(hidden_dim, hidden_dim) self.classifier = nn.Linear(hidden_dim, num_classes) def forward(self, x, adj): x = self.conv1(x, adj) x = self.conv2(x, adj) return self.classifier(x)

๐Ÿ”— Edge-Level Tasks

๐ŸŽฏ Link Prediction & Edge Classification

Edge-level tasks predict the existence or properties of edges between nodes, crucial for knowledge graphs and recommendation.

Edge Prediction Methods

Dot product: Score = h_u ยท h_v. MLP: Concatenate and classify. DistMult: Bilinear scoring.

๐Ÿ”— Link Prediction๐Ÿ“Š Scoring๐Ÿ” Recommendation
class EdgeLevelGNN(nn.Module): def __init__(self, node_dim, hidden_dim): super().__init__() self.gnn = NodeLevelGNN(node_dim, hidden_dim, hidden_dim) self.edge_classifier = nn.Linear(hidden_dim * 2, 1) def forward(self, x, adj, edge_index): node_embeddings = self.gnn(x, adj) # For each edge, combine node embeddings src_emb = node_embeddings[edge_index[0]] dst_emb = node_embeddings[edge_index[1]] edge_rep = torch.cat([src_emb, dst_emb], dim=1) return torch.sigmoid(self.edge_classifier(edge_rep))

๐Ÿ—บ๏ธ Spatial vs Spectral

๐ŸŽฏ Two GNN Paradigms

Spectral methods use graph Fourier transform. Spatial methods operate directly on the graph structure.

Comparison

Spectral: GCN, ChebNet โ€” global view. Spatial: GAT, GraphSAGE โ€” local aggregation. Trend: Spatial methods more popular.

๐Ÿ“Š Spectral๐Ÿ—บ๏ธ Spatial๐Ÿ”„ Hybrid
class GraphConv(nn.Module): def __init__(self, in_dim, out_dim, method='spatial'): super().__init__() if method == 'spectral': self.conv = GCNLayer(in_dim, out_dim) else: # spatial self.conv = GATLayer(in_dim, out_dim) def forward(self, x, adj, edge_index=None): if isinstance(self.conv, GCNLayer): return self.conv(x, adj) else: return self.conv(x, edge_index)

๐ŸŠ Graph Pooling

๐ŸŽฏ Reducing Graph Size

Pooling layers downsample graphs by clustering nodes, enabling hierarchical representation learning.

Pooling Methods

DiffPool: Differentiable pooling with assignment. Top-k: Keep most important nodes. SAGPool: Self-attention based.

๐ŸŠ DiffPool๐Ÿ“Š Top-k๐Ÿ‘€ SAGPool
class TopKPooling(nn.Module): def __init__(self, in_dim, ratio=0.5): super().__init__() self.ratio = ratio self.score = nn.Linear(in_dim, 1) def forward(self, x, adj): scores = torch.sigmoid(self.score(x)) k = max(1, int(len(x) * self.ratio)) _, idx = torch.topk(scores.flatten(), k) x_pool = x[idx] adj_pool = adj[idx, :][:, idx] return x_pool, adj_pool

๐Ÿš€ GNN Applications

๐ŸŽฏ Real-World GNN Use Cases

GNNs are used in drug discovery, social networks, recommendation systems, traffic prediction, and physical simulations.

Application Domains

Drug discovery: Molecular property prediction. Social networks: User classification, community detection. Recommender systems: User-item graph.

๐Ÿ’Š Drug Discovery๐Ÿ“ฑ Social Networks๐ŸŽฏ Recommendations
class MolecularGNN(nn.Module): def __init__(self, atom_features=78, hidden=64): super().__init__() self.gnn = GNN(atom_features, hidden) self.readout = nn.Linear(hidden, 1) # Property prediction def forward(self, atom_features, adj): x = self.gnn(atom_features, adj) return self.readout(torch.mean(x, dim=0))

๐Ÿ“š Libraries & Tools

๐ŸŽฏ GNN Frameworks

PyTorch Geometric, DGL, Spektral, NetworkX, and other libraries for building and training GNNs.

Popular Libraries

PyTorch Geometric: Most popular, extensive dataset. DGL: Deep Graph Library by AWS. Spektral: TensorFlow-based.

๐Ÿ“š PyG๐Ÿ“š DGL๐Ÿ“š Spektral
# PyTorch Geometric example from torch_geometric.datasets import Planetoid from torch_geometric.nn import GCNConv dataset = Planetoid(root='/tmp/Cora', name='Cora') class GCN(torch.nn.Module): def __init__(self): super().__init__() self.conv1 = GCNConv(dataset.num_features, 16) self.conv2 = GCNConv(16, dataset.num_classes) def forward(self, data): x, edge_index = data.x, data.edge_index x = self.conv1(x, edge_index) x = F.relu(x) x = self.conv2(x, edge_index) return F.log_softmax(x, dim=1)

๐Ÿ”ฎ Future Directions

๐ŸŽฏ Emerging GNN Research

Graph Transformers, dynamic graphs, heterogeneous graphs, temporal GNNs, and geometric GNNs.

Research Trends

Graph Transformers: Replace message passing with attention. Temporal GNNs: Handle evolving graphs. Geometric GNNs: 3D molecular structures.

๐Ÿ”ฎ Transformers๐Ÿ“Š Temporal๐Ÿ“ Geometric
class GraphTransformer(nn.Module): def __init__(self, in_dim, hidden_dim, num_heads): super().__init__() self.attention = nn.MultiheadAttention(hidden_dim, num_heads) self.ffn = nn.Sequential( nn.Linear(hidden_dim, hidden_dim * 4), nn.ReLU(), nn.Linear(hidden_dim * 4, hidden_dim) ) def forward(self, x, adj): # Graph Transformer with Laplacian positional encoding pos_enc = self.get_laplacian_pe(adj) x = x + pos_enc x = self.attention(x, x, x)[0] return self.ffn(x)