graph neural networks message passing graph convolutions
# Graph Neural Networks: Message Passing & Graph Convolutions
## Introduction & Motivation
Graph neural networks: operate on graph-structured data. Message passing: aggregate neighbor information; update node representations. Graph convolutions: GCN; learnable filter via spectral approximation. GraphSAGE: inductive learning; sample and aggregate. Attention graphs: GAT; learnable neighbor weights. Applications: social networks, molecules, knowledge graphs, recommendations.
Motivation: Graphs ubiquitous: molecules, social networks, knowledge graphs. Specialized architectures leverage structure.
Applications: Node classification, link prediction, graph classification.
---
## Core Concepts & Theory
### Message Passing
Aggregate neighbor features; update via learned function.
### Graph Convolutions (GCN)
Spectral convolution via Chebyshev polynomial approximation.
### Attention (GAT)
Learnable attention over neighbors; compute edge weights.
---
## Mathematical Formulation
Message passing:
$$h_i^{(l+1)} = \phi(h_i^{(l)}, ext{Aggregate}(\{h_j^{(l)} : j \in N(i)\}))$$
GCN layer:
$$H^{(l+1)} = \sigma( ilde{D}^{-1/2} ilde{A} ilde{D}^{-1/2} H^{(l)} W^{(l)})$$
where à = A + I, D̃ diagonal degree matrix.
Graph Attention:
$$\alpha_{ij} = ext{softmax}( ext{LeakyReLU}(a^T[Wh_i || Wh_j]))$$
---
## Advanced Theory & Extensions
### GraphSAGE
Inductive: sample k neighbors, aggregate; train on subgraphs.
### Spectral Methods
Operate in spectral domain; leverage graph Laplacian.
### Heterogeneous Graphs
Multiple node/edge types; type-specific aggregation.
---
## Computational Considerations
Message passing: O(E·d) for E edges, d dimension.
GCN: O(N·d + E·d) per layer; sparse matrix ops.
Attention: O(N²) pairwise attention for dense graphs.
---
## Practical Implementation Strategies
### Neighbor Sampling
Sample k neighbors; reduce computation for large graphs.
### Mini-Batch Training
Subgraph sampling; allow mini-batch SGD.
### Aggregation Function
Sum, mean, max; learnable weight function.
---
## Benchmark Datasets & Evaluation
Cora/Citeseer: Citation networks; node classification.
OGB-ArXiv: Open Graph Benchmark; large-scale.
Ogbn-Products: Product graphs; billion-scale.
---
## Key Challenges & Limitations
### Oversmoothing
Deep GNNs → uniform node embeddings; diminishing returns.
### Graph Heterogeneity
Different subgraph structures; learning difficulty varies.
### Scalability
Large graphs: memory/compute bottleneck.
---
## Hyperparameter Tuning
Aggregation function: Mean common; sum for dense.
Number of layers: 2-3 typical; deeper → oversmooothing.
Neighbor sampling k: 10-25; balance computation-performance.
---
## Real-World Applications & Case Studies
Molecules: Quantum properties via MolGAN, GraphMolGen.
Knowledge Graphs: Link prediction; entity embeddings.
Recommendations: User-item graphs; implicit feedback.
---
## Integration with Other Methods
GNN + Attention → learnable neighbor focus.
GNN + Contrastive → self-supervised graph learning.
---
## Summary & Key Takeaways
Graph neural networks via message passing and graph convolutions enable learning on graph-structured data, capturing relational patterns through neighbor aggregation.
Principles:
1. Message passing: aggregate neighbor information.
2. GCN: spectral graph convolution.
3. GAT: learnable attention over neighbors.
4. GraphSAGE: inductive sampling and aggregation.
5. Scalability: neighborhood sampling essential.
---
---
## Appendix: Practical Labs
### Lab 1: Graph Representation
import numpy as np
class Graph:
def __init__(self, n_nodes, edges):
self.n_nodes = n_nodes
self.edges = edges
self.adjacency = self.build_adjacency()
def build_adjacency(self):
"""Build adjacency matrix"""
adj = np.zeros((self.n_nodes, self.n_nodes))
for u, v in self.edges:
adj[u, v] = 1
adj[v, u] = 1
return adj
def get_neighbors(self, node):
"""Get node neighbors"""
return np.where(self.adjacency[node] > 0)[0]
# Test
np.random.seed(42)
edges = [(0, 1), (1, 2), (2, 3), (3, 0)]
graph = Graph(4, edges)
neighbors_0 = graph.get_neighbors(0)
assert len(neighbors_0) == 2, "Node 0 should have 2 neighbors"
assert 1 in neighbors_0 and 3 in neighbors_0, "Neighbors correct"
print("✓ Graph representation working")
if __name__ == "__main__":
print("Lab 1: Graph - PASSED")### Lab 2: Message Passing
import numpy as np
def message_passing(features, adjacency, weight_matrix):
"""Single message passing step"""
# Aggregate neighbor features
aggregated = adjacency @ features
# Normalize by degree
degree = adjacency.sum(axis=1, keepdims=True)
aggregated = aggregated / (degree + 1e-8)
# Combine with self features
updated = np.tanh(aggregated @ weight_matrix)
return updated
# Test
np.random.seed(42)
n_nodes, n_features, hidden_dim = 10, 5, 8
features = np.random.randn(n_nodes, n_features)
adjacency = np.random.randint(0, 2, (n_nodes, n_nodes))
W = np.random.randn(n_features, hidden_dim)
updated = message_passing(features, adjacency, W)
assert updated.shape == (n_nodes, hidden_dim), "Output shape correct"
assert np.isfinite(updated).all(), "All finite"
print("✓ Message passing working")
if __name__ == "__main__":
print("Lab 2: MessagePassing - PASSED")### Lab 3: Graph Convolution Layer
import torch
import torch.nn as nn
import numpy as np
class GraphConvLayer(nn.Module):
def __init__(self, in_features, out_features):
super().__init__()
self.weight = nn.Parameter(torch.randn(in_features, out_features))
self.bias = nn.Parameter(torch.zeros(out_features))
def forward(self, features, adjacency):
"""GCN forward pass"""
# features: [n_nodes, in_features]
# adjacency: [n_nodes, n_nodes]
# Degree matrix
degree = adjacency.sum(dim=1, keepdim=True)
# Normalized adjacency: D^-1/2 A D^-1/2
D_inv_sqrt = torch.pow(degree, -0.5)
D_inv_sqrt[torch.isinf(D_inv_sqrt)] = 0
norm_adj = D_inv_sqrt * adjacency * D_inv_sqrt.T
# GCN update
output = torch.relu(norm_adj @ features @ self.weight + self.bias)
return output
# Test
np.random.seed(42)
n_nodes, n_features, out_features = 5, 3, 4
gcn = GraphConvLayer(n_features, out_features)
features = torch.randn(n_nodes, n_features)
adjacency = torch.randint(0, 2, (n_nodes, n_nodes)).float()
output = gcn(features, adjacency)
assert output.shape == (n_nodes, out_features), "Output shape correct"
print("✓ Graph convolution working")
if __name__ == "__main__":
print("Lab 3: GCN - PASSED")### Lab 4: Node Classification
import torch
import torch.nn as nn
import numpy as np
class GraphNodeClassifier(nn.Module):
def __init__(self, n_features, n_hidden, n_classes):
super().__init__()
self.gcn1 = nn.Linear(n_features, n_hidden)
self.gcn2 = nn.Linear(n_hidden, n_classes)
def forward(self, features, adjacency):
# First layer
h = torch.relu(self.gcn1(features))
# Aggregate via adjacency
h = adjacency @ h
# Second layer
output = self.gcn2(h)
return output
# Test
np.random.seed(42)
n_nodes, n_features, n_hidden, n_classes = 10, 5, 8, 3
model = GraphNodeClassifier(n_features, n_hidden, n_classes)
features = torch.randn(n_nodes, n_features)
adjacency = torch.randint(0, 2, (n_nodes, n_nodes)).float()
output = model(features, adjacency)
assert output.shape == (n_nodes, n_classes), "Output shape correct"
print("✓ Node classification working")
if __name__ == "__main__":
print("Lab 4: Classification - PASSED")