Introduction

A molecule is not a list of atoms โ€” it is a graph. A social network is not a table of users โ€” it is a graph. A circuit is not a bag of components โ€” it is a graph. Yet for decades machine learning tools expected flat vectors: give each example a fixed-length array of numbers and let the network learn.

Graph Neural Networks (GNNs) break that constraint. They work directly on graphs: every node carries a feature vector, every edge represents a relationship, and the network learns by repeatedly asking each node to aggregate information from its neighbors. After a few rounds, each node's vector encodes not only its own properties but also the local structure surrounding it โ€” things a flat vector could never represent.

The core idea โ€” message passing โ€” is disarmingly simple, yet it underpins some of the most impressive recent results in computational chemistry, social-network analysis, and combinatorial optimization. Understanding it requires no exotic mathematics, only the willingness to think in connections rather than rows.

Try It: One Round of Message Passing

The graph below has six nodes, each initialized with a simple scalar feature (shown inside the circle). Click Run one round to execute one step of message passing: each node receives the features of its neighbors, averages them, and adds the result to its own value โ€” a classic mean-aggregation GNN layer.

<p class="hint">Each node starts with a feature value. Click <b>Run one round</b> to perform one message-passing step: every node averages its neighbors' values and adds that to its own. Depth = reach โ€” run multiple rounds to propagate information further across the graph.</p>
<div id="canvas-wrap"><canvas id="gc" width="460" height="280"></canvas></div>
<div class="status" id="status">Round 0 โ€” initial embeddings.</div>
<div class="btns">
  <button id="step" type="button">Run one round</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.5; }
#canvas-wrap { background: #f0f4f8; border-radius: 10px; overflow: hidden; margin-bottom: .5rem; }
canvas { display: block; max-width: 100%; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin: .3rem 0 .5rem; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Graph Neural Network โ€“ mean-aggregation message passing demo.
// Each node h_v โ† h_v + mean({ h_u : u โˆˆ neighbours(v) })
// This mirrors the "GraphSAGE mean" aggregation / basic GCN update rule.

// โ”€โ”€ Graph definition โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
// 6 nodes, 0-indexed. Positions are in canvas coordinates (460ร—280).
const NODES = [
  { x: 100, y:  60, init: 1.0 },   // 0
  { x: 260, y:  50, init: 3.0 },   // 1
  { x: 390, y: 110, init: 0.5 },   // 2
  { x: 320, y: 220, init: 2.0 },   // 3
  { x: 130, y: 230, init: 1.5 },   // 4
  { x: 230, y: 150, init: 0.0 },   // 5 (hub)
];
// Undirected edges stored as pairs [a,b] with a<b.
const EDGES = [[0,5],[1,5],[2,3],[2,5],[3,5],[4,5],[0,4],[1,2]];

// Build adjacency list
const adj = NODES.map(() => []);
EDGES.forEach(([a,b]) => { adj[a].push(b); adj[b].push(a); });

// โ”€โ”€ State โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
let h = NODES.map(n => n.init);   // current embeddings
let round = 0;

// Color ramp: map value in [0, MAX] to a blue gradient
const MAX_VAL = 8;
function valToColor(v) {
  const t = Math.min(1, Math.max(0, v / MAX_VAL));
  // interpolate from #c8d8e8 (light) to #1d3557 (dark)
  const r = Math.round(200 - t * 169);
  const g = Math.round(216 - t * 163);
  const b = Math.round(232 - t * 145);
  return `rgb(${r},${g},${b})`;
}
function textColor(v) {
  return (v / MAX_VAL) > 0.45 ? '#fff' : '#1d3557';
}

// โ”€โ”€ Canvas drawing โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
const canvas = document.getElementById('gc');
const ctx = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;
const R = 24; // node radius

function draw() {
  ctx.clearRect(0, 0, W, H);

  // Edges
  ctx.strokeStyle = '#9fb2c8';
  ctx.lineWidth = 2;
  EDGES.forEach(([a, b]) => {
    ctx.beginPath();
    ctx.moveTo(NODES[a].x, NODES[a].y);
    ctx.lineTo(NODES[b].x, NODES[b].y);
    ctx.stroke();
  });

  // Nodes
  NODES.forEach((n, i) => {
    const v = h[i];
    ctx.beginPath();
    ctx.arc(n.x, n.y, R, 0, Math.PI * 2);
    ctx.fillStyle = valToColor(v);
    ctx.fill();
    ctx.strokeStyle = '#1d3557';
    ctx.lineWidth = 2;
    ctx.stroke();

    // Value label
    ctx.fillStyle = textColor(v);
    ctx.font = 'bold 13px ui-monospace, monospace';
    ctx.textAlign = 'center';
    ctx.textBaseline = 'middle';
    ctx.fillText(v.toFixed(1), n.x, n.y);

    // Node index (small, outside)
    ctx.fillStyle = '#5a7088';
    ctx.font = '10px system-ui, sans-serif';
    ctx.fillText('v' + i, n.x, n.y - R - 7);
  });
}

// โ”€โ”€ Message passing step โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
// h_v โ† h_v + mean_neighbours(h_u)
function step() {
  const next = h.slice();
  let changed = 0;
  h.forEach((hv, v) => {
    const nbrs = adj[v];
    if (nbrs.length === 0) return;
    const meanNbr = nbrs.reduce((s, u) => s + h[u], 0) / nbrs.length;
    next[v] = hv + meanNbr;
    changed += Math.abs(next[v] - hv);
  });
  h = next;
  round++;
  const delta = changed.toFixed(2);
  document.getElementById('status').textContent =
    fmt('Round %round% complete โ€” total embedding shift: %delta%', { round: round, delta: delta });
  draw();

  // Log to console for verification
  console.log('Round', round, '| embeddings:', h.map(x => x.toFixed(3)));
}

function reset() {
  h = NODES.map(n => n.init);
  round = 0;
  document.getElementById('status').textContent =
    'Round 0 โ€” initial embeddings.';
  draw();
}

document.getElementById('step').addEventListener('click', step);
document.getElementById('reset').addEventListener('click', reset);

draw();
Result
Console

Notice how nodes with well-connected neighbors change more dramatically. After a single round every node has absorbed a snapshot of its immediate neighborhood. Click again to propagate information two hops out. This is how GNNs build context: depth equals reach.

The Real Complexity

Message-passing GNNs are powerful, but they have a provable ceiling.

In 2019, Xu et al. and Morris et al. independently showed that the entire class of message-passing GNNs is at most as expressive as the 1-dimensional Weisfeiler-Leman (1-WL) graph isomorphism test โ€” a classical algorithm that colors nodes by their neighborhood multisets until stable. Any two graphs that 1-WL cannot distinguish, no message-passing GNN can distinguish either, no matter how deep.

What does 1-WL miss? It cannot tell apart graphs that look locally identical but differ globally โ€” for instance, two 3-regular graphs on the same number of vertices. This means standard GNNs cannot count triangles, cannot detect cycles of fixed length, and cannot recognize certain structural motifs critical in chemistry.

  • Solved: expressiveness equivalence. Xu et al. (2019) proved this equivalence and proposed the Graph Isomorphism Network (GIN), shown to be maximally expressive within the 1-WL class.
  • Open: higher-order expressiveness. Lifting GNNs to k-WL (operating on k-tuples of nodes) increases power but costs O(nk)O(nแต) memory โ€” a combinatorial wall.
  • Open: generalization theory. When and why do GNNs generalize from training graphs to unseen ones? The theory is still developing.

This connects to fundamental questions about graph isomorphism โ€” a problem whose exact complexity (P, NP-complete, or something in between?) remains one of the most celebrated open questions in the field.

Where It Matters

Because so much of the world is relational, GNNs have spread rapidly:

  • Drug discovery and molecular property prediction: GNNs treat a molecule as a graph of atoms and bonds, predicting solubility, toxicity, and binding affinity orders of magnitude faster than quantum simulations. DeepMind's AlphaFold 2 uses graph-based attention over residue contact maps.
  • Social network analysis and recommendation: platforms represent users and content as nodes, edges as interactions. GNN-based recommenders learn to surface items liked by your "graph neighborhood" โ€” people with similar connection patterns.
  • Traffic and routing: Google Maps uses GNNs to predict travel times by modeling road segments as graph edges and updating speed estimates from neighboring segments.
  • Chip floor-planning: Google's 2021 Nature paper showed a GNN-guided reinforcement-learning agent places circuit components faster than human experts.
  • Fraud and anomaly detection: suspicious transaction chains appear as anomalous subgraphs; GNNs catch patterns that per-transaction classifiers miss.
  • Combinatorial optimization: GNNs learn heuristics for NP-hard problems such as graph coloring and vehicle routing, closing much of the gap with hand-crafted solvers on practical instances.

Wherever the data has an intrinsic shape โ€” bonds, friendships, roads, dependencies โ€” GNNs are becoming the default tool.

Conclusion

Graph Neural Networks rest on an idea so clean it can be stated in one sentence: let every node borrow knowledge from its neighbors, repeatedly. From that single rule emerges an architecture capable of predicting how a drug binds to a protein, where traffic will jam an hour from now, and which financial transactions belong to a fraud ring.

Their limits are just as instructive. The ceiling imposed by the Weisfeiler-Leman test is not a failure โ€” it is a precise characterization that guides researchers toward higher-order models, positional encodings, and hybrid architectures that push expressiveness further.

In a world where data increasingly lives in graphs โ€” social, biological, physical, computational โ€” the ability to learn from connections rather than just values is not a niche skill. It is becoming a fundamental one. To understand GNNs is to understand why structure is information.

Share this article

Pick a channel โ€” or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/graph-neural-networks/Content licensed under CC BY-NC 4.0.