Skip to main content

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 AA, add self-loops A~=A+I\tilde{A}=A+I and row-normalize it as P=D−1A~P=D^{-1}\tilde{A}. This lesson computes

H(1)=ReLU⁡(PH(0)W).H^{(1)}=\operatorname{ReLU}(P H^{(0)} W).

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 LL layers, a node can depend on nodes up to LL 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.