Graph Neural Networks Gnn Message Passing Node Classification
# Graph Neural Networks: GNN Message Passing & Node Classification
## Introduction & Motivation
GNNs learn on graph-structured data via message passing. Nodes aggregate neighbor features; edges propagate information. Graph Convolutional Networks (GCN) use spectral methods; GraphSAGE uses sampling; GAT uses attention. Foundation for social networks, molecules, knowledge graphs.
Motivation: CNNs assume grid structure; RNNs assume sequences. GNNs naturally model irregular, relational data via graph topology.
Applications: Social networks, molecular property prediction, knowledge graph completion, traffic forecasting.
---
## Core Concepts & Theory
### Message Passing
Each node aggregates messages from neighbors: h_v^(l+1) = UPDATE(h_v^(l), AGGREGATE({h_u^(l) : u ∈ N(v)})).
### Graph Convolutional Network (GCN)
Spectral convolution: multiply by normalized Laplacian. Efficient via Chebyshev approximation (1-hop localization).
### Graph Attention Network (GAT)
Attention weights on edges: α_uv ∝ exp(a^T[Wh_u || Wh_v]).
Learned edge importance; multi-head attention.
---
## Mathematical Formulation
Message passing (general):
$$\mathbf{h}_v^{(l+1)} = \gamma^{(l)}(\mathbf{h}_v^{(l)}, \square_{u \in \mathcal{N}(v)} \phi^{(l)}(\mathbf{h}_v^{(l)}, \mathbf{h}_u^{(l)}))$$
GCN update:
$$\mathbf{H}^{(l+1)} = \sigma( ilde{D}^{-1/2} ilde{A} ilde{D}^{-1/2} \mathbf{H}^{(l)} \mathbf{W}^{(l)})$$
Graph attention:
$$\alpha_{uv} = \frac{\exp(a^T ext{LeakyReLU}(\mathbf{W}[\mathbf{h}_u || \mathbf{h}_v]))}{\sum_{w \in \mathcal{N}(v)} \exp(a^T ext{LeakyReLU}(\mathbf{W}[\mathbf{h}_w || \mathbf{h}_v]))}$$
---
## Advanced Theory & Extensions
### GraphSAGE (Sampling & Aggregating)
Sample k-hop neighbors; aggregate via mean/LSTM/pooling. Enables inductive learning on unseen nodes.
### Graph Pooling
Global pooling: readout function (sum, mean, attention). Hierarchical pooling: DiffPool (learns soft cluster assignment).
---
## Computational Considerations
Memory: O(|E| × d) for edge features during aggregation.
Time: O(|V| × k × |N(v)| × d) per layer; k = aggregation complexity.
Scaling: Mini-batch sampling (GraphSAGE) reduces to O(batch_size × k × |N| × d).
---
## Practical Implementation Strategies
### Neighbor Sampling
Reduce neighbor set size; uniform or importance sampling. Balance accuracy-efficiency.
### Feature Normalization
Standardize node features; crucial for stable training.
### Batch Normalization on Edges
Normalize aggregated messages; improves convergence.
---
## Benchmark Datasets & Evaluation
Citation Networks (Cora, Citeseer): Node classification; few labels.
Social Networks (Zachary's, Karate Club): Community detection.
Molecular Graphs: Graph-level prediction; chemical properties.
Metrics: Accuracy, F1, AUC, link prediction recall@k.
---
## Key Challenges & Limitations
### Over-Smoothing
Deep GNNs make node embeddings similar; limits expressivity.
### Scalability
Neighbor aggregation becomes expensive on large graphs.
### Generalization
Performance sensitive to graph structure; limited to similar distributions.
---
## Hyperparameter Tuning
Number of layers: 2-3 (avoid over-smoothing).
Hidden dim: 64-256.
Learning rate: 0.01-0.1.
Dropout: 0.5 (on features, not aggregation).
---
## Real-World Applications & Case Studies
Pinterest: GraphSAGE for recommendation; billions of nodes.
DeepChem: GNN for molecular property prediction.
Knowledge Graphs: Link prediction, entity alignment.
---
## Integration with Other Methods
GNN + RL → graph-based planning, combinatorial optimization.
GNN + Transformer → Graphormer; attention over graph structure.
---
## Summary & Key Takeaways
GNNs learn representations via message passing on graphs, enabling node/edge/graph-level prediction on irregular data.
Principles:
1. Message passing aggregates neighbor information.
2. Spectral (GCN) vs. spatial (GraphSAGE, GAT) formulations.
3. Attention learns adaptive edge weights.
4. Sampling enables scalability to large graphs.
5. Over-smoothing limits depth; deep GNNs need careful design.
---
---
## Appendix: Practical Labs
### Lab 1: Basic GCN Node Classification
import torch
import torch.nn as nn
import numpy as np
from sklearn.datasets import make_blobs
class GCNLayer(nn.Module):
def __init__(self, in_dim, out_dim):
super().__init__()
self.linear = nn.Linear(in_dim, out_dim)
def forward(self, X, A):
# X: (N, in_dim), A: (N, N) adjacency
aggregated = torch.mm(A, X) # Neighbor aggregation
return torch.relu(self.linear(aggregated))
class GCN(nn.Module):
def __init__(self, in_dim, hidden_dim, out_dim):
super().__init__()
self.layer1 = GCNLayer(in_dim, hidden_dim)
self.layer2 = GCNLayer(hidden_dim, out_dim)
def forward(self, X, A):
h = self.layer1(X, A)
return self.layer2(h, A)
# Create synthetic graph
N, D = 20, 4
X = torch.randn(N, D)
A = torch.randn(N, N)
A = (A + A.T) / 2 # Symmetric
A = (A > A.mean()).float() # Binary adjacency
model = GCN(in_dim=D, hidden_dim=8, out_dim=3)
output = model(X, A)
print(f"Output shape: {output.shape}")
assert output.shape == (N, 3), "Should match (N, out_dim)"
assert torch.isfinite(output).all(), "Output should be finite"
print("✓ Basic GCN working")
if __name__ == "__main__":
print("Lab 1: GCN - PASSED")### Lab 2: Graph Attention
import torch
import torch.nn as nn
import numpy as np
class GraphAttentionLayer(nn.Module):
def __init__(self, in_dim, out_dim):
super().__init__()
self.W = nn.Linear(in_dim, out_dim)
self.a = nn.Parameter(torch.randn(2*out_dim, 1))
def forward(self, X, A):
# X: (N, in_dim), A: (N, N)
h = self.W(X) # (N, out_dim)
# Attention logits
concat = torch.cat([h.repeat_interleave(X.size(0), dim=0),
h.repeat(X.size(0), 1)], dim=1) # (N², 2*out_dim)
logits = (concat @ self.a).view(X.size(0), X.size(0))
# Masked softmax
mask = (A > 0).float()
logits = logits.masked_fill(mask == 0, -1e9)
alpha = torch.softmax(logits, dim=1)
return torch.mm(alpha, h)
N, D = 15, 4
X = torch.randn(N, D)
A = torch.randn(N, N)
A = (A > 0).float()
gat = GraphAttentionLayer(in_dim=D, out_dim=8)
output = gat(X, A)
print(f"GAT output shape: {output.shape}")
assert output.shape == (N, 8), "Should match (N, out_dim)"
assert torch.isfinite(output).all(), "Output should be finite"
print("✓ Graph attention working")
if __name__ == "__main__":
print("Lab 2: GAT - PASSED")### Lab 3: Node Embedding Visualization
import torch
import torch.nn as nn
import numpy as np
from sklearn.decomposition import PCA
class SimpleGNN(nn.Module):
def __init__(self, in_dim, emb_dim):
super().__init__()
self.embed = nn.Linear(in_dim, emb_dim)
def forward(self, X, A):
h = self.embed(X)
return torch.mm(A, h) # Simple aggregation
N, D = 30, 5
X = torch.randn(N, D)
A = torch.eye(N) + torch.randn(N, N) * 0.1
A = (A > 0).float() + torch.eye(N)
model = SimpleGNN(in_dim=D, emb_dim=8)
embeddings = model(X, A).detach().numpy()
# PCA to 2D
pca = PCA(n_components=2)
emb_2d = pca.fit_transform(embeddings)
print(f"Embedding 2D shape: {emb_2d.shape}")
assert emb_2d.shape == (N, 2), "Should have 2D embeddings"
assert np.isfinite(emb_2d).all(), "Should be finite"
print("✓ Node embedding visualization working")
if __name__ == "__main__":
print("Lab 3: Embedding - PASSED")### Lab 4: Neighborhood Sampling
import numpy as np
from collections import defaultdict
def build_adjacency(N=20, edge_prob=0.3):
adj = defaultdict(list)
for i in range(N):
for j in range(i+1, N):
if np.random.rand() < edge_prob:
adj[i].append(j)
adj[j].append(i)
return adj
def sample_neighbors(node, adj, k=5):
neighbors = adj[node]
if len(neighbors) <= k:
return neighbors
return np.random.choice(neighbors, k, replace=False).tolist()
adj = build_adjacency(N=20, edge_prob=0.3)
node = 5
sampled = sample_neighbors(node, adj, k=3)
print(f"Sampled neighbors of node {node}: {sampled}")
assert len(sampled) <= 3, "Should sample at most k neighbors"
assert all(n in adj[node] for n in sampled), "Should be actual neighbors"
print("✓ Neighborhood sampling working")
if __name__ == "__main__":
print("Lab 4: Sampling - PASSED")