Project 57: Graph Message-Passing Playground

A self-contained deep-dive from the canonical Math from Foundations to Machine Learning curriculum.

  • Difficulty: Level 3: Advanced
  • Time: 1-2 weeks
  • Language: Python
  • Prerequisites: Projects 9, 20, 24, and 45
  • Source: ML-Math P29

What You Will Build

Build a sparse graph-learning playground for node signals and neighborhood aggregation. Parse edge lists and node features, compute degree/component statistics and simple centrality baselines, then implement normalized message-passing layers with configurable self-loops, aggregation, weights, activation, and depth. Train a small node classifier or perform fraud/risk signal propagation while exposing each node’s incoming messages. Compare raw, mean, symmetric-normalized, and learned transformations; measure hub bias, isolated-node behavior, receptive-field growth, and over-smoothing as layers increase.

Real World Outcome

On a citation, social, or payment graph, the program reports node/edge/component counts, task metrics, top-ranked nodes, and performance by degree bucket. An inspection view explains a selected node’s updated representation from its neighbors, while hop-wise plots warn when embeddings collapse toward indistinguishable values.

Core Question

How does relational structure change the evidence available for a prediction, and how should neighborhood information be aggregated safely?

Concepts You Must Understand First

  • Graphs, adjacency lists/matrices, connected components, degree, and sparse storage.
  • Permutation invariance/equivariance of node aggregation.
  • Message-passing neural networks and neighborhood aggregation.
  • Degree normalization, self-loops, and hub bias.
  • Node-level evaluation, leakage through graph splits, and over-smoothing.

Build Milestones

  1. Parse sparse graphs/features and validate duplicates, self-loops, components, and node IDs.
  2. Implement transparent one-hop aggregation and compare normalization choices on hand-built graphs.
  3. Add trainable message/update functions and a node-classification or ranking task.
  4. Evaluate by hop depth, degree bucket, connected component, and random seed.
  5. Visualize selected message flows and quantify embedding similarity/over-smoothing.

Hints in Layers

  1. Test permutation behavior by renumbering nodes; outputs should renumber correspondingly.
  2. Use sparse edge-index operations instead of materializing a dense adjacency matrix.
  3. Include isolated nodes and high-degree hubs in unit tests because normalization edge cases live there.

Common Pitfalls and Debugging

  • Memory explodes on a moderate graph: dense adjacency was constructed. Store edges/CSR data and aggregate only present edges.
  • High-degree nodes dominate predictions: raw summation introduces scale bias. Compare mean and symmetric normalization and report degree slices.
  • Validation is suspiciously high: graph edges or labels leak across the split. Define the inductive/transductive protocol and audit preprocessing visibility.

Definition of Done

  • Sparse representation handles a realistically sized graph without dense adjacency.
  • Hand-built graph tests verify normalization, self-loops, isolated nodes, and permutation behavior.
  • A node task beats feature-only and structure-only baselines where appropriate.
  • Evaluation includes degree/component slices and multiple seeds.
  • Message inspection explains one prediction through concrete neighbors.
  • Over-smoothing is measured and tied to a recommended depth.

Previous: Project 56 · Complete learning path · Next: Project 58