Graph Neural Networks and Message Passing
A message-passing graph neural network updates each node from its current representation and messages from neighbors. Architecture names differ, but every layer must define a neighborhood, message function, aggregation, update, and direction of information flow.
Prerequisites
Complete node and graph embeddings. Keep the training objective and graph construction visible when moving from free node vectors to a feature-based encoder.
Learning goals
- Decompose a message-passing layer into messages, aggregation, and update.
- Calculate a small self-looped mean aggregation by hand and in NumPy.
- Relate layer depth to receptive field and neighbor dependence.
- Name homophily, direction, oversmoothing, and expressiveness limits.
Learning contract
- Graph: an undirected three-node path Ada–Ben–Cy with one added self-loop per node.
- Features: fixed two-dimensional input features; there are no labels and no fitted parameters.
- Update: row-normalized mean aggregation followed by a declared linear map and ReLU.
- Interpretation limit: this is a forward calculation, not training evidence or a claim that connected people should become similar.
One layer, explicit assumptions
For adjacency matrix , add self-loops and row-normalize it as . This lesson computes
The normalization is a mean over each node and its neighbors. The symmetric normalization in the original GCN paper is different; GraphSAGE offers learned aggregators for inductive use. Direction also matters: incoming, outgoing, and reciprocal messages answer different questions on the interaction graph.
After layers, a node can depend on nodes up to hops away. More layers can mix useful signal, noise, and sensitive attributes; repeated smoothing may make representations less distinguishable. Standard message passing also cannot distinguish every non-isomorphic graph. Homophily—neighbors tending to share task-relevant labels—is an empirical assumption, not a law.
Worked example
import numpy as np
nodes = ["ada", "ben", "cy"]
adjacency = np.array([[0, 1, 0], [1, 0, 1], [0, 1, 0]], dtype=float)
features = np.array([[1, 0], [0, 1], [1, 1]], dtype=float)
weights = np.array([[1.0, -1.0], [0.5, 0.5]])
with_self = adjacency + np.eye(len(nodes))
mean_operator = with_self / with_self.sum(axis=1, keepdims=True)
aggregated = mean_operator @ features
updated = np.maximum(aggregated @ weights, 0)
print(f"mean_ada={aggregated[0].round(3).tolist()} mean_ben={aggregated[1].round(3).tolist()}")
print(f"updated={dict(zip(nodes, updated.round(3).tolist()))}")
print("device=cpu parameters=fixed training=False")
Expected output:
mean_ada=[0.5, 0.5] mean_ben=[0.667, 0.667]
updated={'ada': [0.75, 0.0], 'ben': [1.0, 0.0], 'cy': [1.0, 0.0]}
device=cpu parameters=fixed training=False
This deterministic calculation is the boundary of the runnable example. PyTorch Geometric and similar libraries implement sparse message passing, automatic differentiation, samplers, and accelerators; real training also needs leakage-safe masks, losses, optimization, evaluation, and resource measurements.
Limitations
- The path is undirected and homogeneous; typed, directed, temporal, and heterogeneous edges require explicit operators.
- Mean aggregation discards multiplicity unless edge weights or event features are incorporated deliberately.
- Nodes with no usable features or neighbors need a declared fallback.
- A stronger benchmark score does not show that learned neighbor dependence is safe for affected people.
Practice
Remove self-loops and recompute Ben's aggregate. Explain which information a node loses and why adding self-loops is an architectural choice rather than a data fact.
Next steps
Continue to sampling and scaling large graphs to bound neighborhood expansion and understand the resulting estimator.
Primary sources
Checked 2026-10-18: T. N. Kipf and M. Welling, Semi-Supervised Classification with Graph Convolutional Networks; W. L. Hamilton, R. Ying, and J. Leskovec, GraphSAGE; PyTorch Geometric, MessagePassing.