Graph Neural Networks

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.

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">{{hint}}</p>
<div id="canvas-wrap"><canvas id="gc" width="460" height="280"></canvas></div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="reset" type="button" class="ghost">{{btn_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; }

// Code not found

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.

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(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.

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.

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.