Continuous Function

Machine Learning

Graph Expressivity and Weisfeiler-Lehman

Weisfeiler-Lehman color refinement shows a sharp limit of local message passing: some non-isomorphic graphs keep the same color histograms forever.

status: reviewimportance: importantdifficulty 4/5math: graduateread: 22mlive demo
Back to Machine Learning

Concept Structure

Graph Expressivity and Weisfeiler-Lehman

01Intuition

Start with the picture, metaphor, or geometric mechanism.

02Math

Make the objects explicit and connect them with notation.

03Code

Mirror the equations with runnable implementation details.

04Interactive Demo

Manipulate the mechanism and watch the idea respond.

1prerequisites
1next concepts
3related links

Learner Contract

What this page should let you do.

You are here becauseWeisfeiler-Lehman color refinement shows a sharp limit of local message passing: some non-isomorphic graphs keep the same color histograms forever.

This Machine Learning concept is the current idea: keep the same invariant visible across Intuition, Math, Code, Interactive Demo.

By the end4/4 sections ready | runnable code expected | live demo

Explain the mechanism, trace the main notation, and test one prediction in the live demo.

Do this firstIntuition

Read the intuition before the notation; the math should name a mechanism you already felt.

Then go nextGraph Transformers (planned)

Follow this edge after making one prediction here; the next page should reuse the result, not restart the route.

Test the linkManipulate one control and predict the visible change.

Claim/source review status

Substantive review recorded

1/1 claims have bounded review metadata; still check caveats and source scope.Metadata-derived; review may be AI-assisted. Not a human certification.
Claims1/1 reviewed
Sources5 cited
Codeattached
Demolive
Reviewed2026-07-02
Updatedpage 2026-07-02

Learning item flow

4/4 sections readyAsk about thisResearch room
ConceptGraph Expressivity and Weisfeiler-LehmanMachine LearningEquationGraph Expressivity and Weisfeiler-Lehman equation 1Exact equationCodeGraph Expressivity and Weisfeiler-Lehman runnable code 1Exact runnable codeDemoGraph Expressivity and Weisfeiler-Lehman interactive demoInteractive demoClaim1-WL updates each node from its current color and neighbor-color mult...Exact claim checkSourceHow Powerful are Graph Neural Networks?Exact source
ConceptGraph Expressivity and Weisfeiler-LehmanMachine Learning
5 sources attachedLocal snapshot ready
concept:machine-learning/graph-expressivity-weisfeiler-lehman
CodenearbyPredictbefore revealRoomitem handoff
01IntuitionStart with the picture, metaphor, or geometric mechanism.02MathMake the objects explicit and connect them with notation.03CodeMirror the equations with runnable implementation details.04Interactive DemoManipulate the mechanism and watch the idea respond.
01

01

Intuition

Build the mental picture first so the rest of the page has something to attach to.

Section prompt

Message passing feels powerful because every node listens to its neighbors. After several layers, information has moved through a larger and larger neighborhood.

But there is a precise question hiding underneath:

If two graphs make every node hear the same local stories, can message passing tell the graphs apart?

The one-dimensional Weisfeiler-Lehman test, often called 1-WL or color refinement, gives a clean way to feel this limit. Start every node with a color. At each round, a node forms a new color from:

  1. its current color, and
  2. the multiset of colors on its neighbors.

Then compare the color histogram of the whole graph. If the histograms differ, 1-WL has distinguished the graphs. If the histograms stay the same, this local color-refinement process has not found a difference.

The important failure witness is small:

  • Graph A is a 6-cycle.
  • Graph B is two disconnected triangles.

They are not isomorphic: one graph is connected, the other is not. Yet if every node starts with the same feature, each node in both graphs always sees exactly two neighbors with the same color. The color names may update each round, but the histograms remain:

6 nodes of one colorversus6 nodes of one color.6 \text{ nodes of one color} \quad\text{versus}\quad 6 \text{ nodes of one color}.

That is the core lesson. Local symmetry can hide global structure.

This does not mean GNNs are useless or that every message-passing model literally runs 1-WL. It means many neighborhood-aggregation GNNs inherit a similar information bottleneck: if their aggregators only see permutation-invariant multisets of neighbor states, then two locally indistinguishable graphs can remain hard to separate without extra features, identifiers, positional signals, subgraph structure, or higher-order mechanisms.

02

02

Math

Translate the story into symbols, assumptions, and a derivation you can inspect.

Section prompt
Equation 1ct(v).c_t(v).Equation 2st(v)=(ct(v),  multiset⁡{ct(u):u∈N(v)}).s_t(v) = \left(c_t(v),\; \operatorname{multiset}\{c_t(u):u\in\mathcal N(v)\}\right).

Let G=(V,E)G=(V,E) be an undirected graph. At round tt, each node v∈Vv\in V has a color

ct(v).c_t(v).

The 1-WL update forms a signature from the current color and the multiset of neighbor colors:

st(v)=(ct(v),  multiset⁡{ct(u):u∈N(v)}).s_t(v) = \left(c_t(v),\; \operatorname{multiset}\{c_t(u):u\in\mathcal N(v)\}\right).

Then an injective relabeling map assigns the next color:

ct+1(v)=hash⁡(st(v)).c_{t+1}(v)=\operatorname{hash}(s_t(v)).

The graph-level observation after round tt is the histogram

Ht(G)=multiset⁡{ct(v):v∈V}.H_t(G)=\operatorname{multiset}\{c_t(v):v\in V\}.

Two graphs are distinguished at round tt if

Ht(G1)≠Ht(G2).H_t(G_1)\ne H_t(G_2).

Why the 6-cycle and two triangles fool 1-WL

Assume every node begins with the same color aa.

In the 6-cycle, every node has two neighbors, both color aa at round 0. In the two-triangles graph, every node also has two neighbors, both color aa at round 0. So every node in both graphs has the same signature:

(a,{a,a}).(a,\{a,a\}).

After relabeling, all nodes in both graphs receive the same new color, call it bb. The same reasoning repeats:

(b,{b,b})↦c,(c,{c,c})↦d,(b,\{b,b\}) \mapsto c,\qquad (c,\{c,c\}) \mapsto d,

and so on. Therefore

Ht(C6)=Ht(2C3)H_t(C_6)=H_t(2C_3)

for every refinement round tt in this unlabeled setting, even though C6C_6 and 2C32C_3 are different graphs.

Connection to message-passing GNNs

A generic message-passing layer has the shape

hv(t+1)=ϕt(hv(t),AGG⁡t{hu(t):u∈N(v)}),h_v^{(t+1)} = \phi_t\left( h_v^{(t)}, \operatorname{AGG}_t\{h_u^{(t)}:u\in\mathcal N(v)\} \right),

where AGG⁡t\operatorname{AGG}_t must be permutation-invariant because graph neighbors do not have a canonical order.

That is why 1-WL is the right mental model. It asks what can be learned from repeated local multisets. If two nodes always receive the same kind of multiset information, a local invariant aggregator has no obvious handle for separating them.

The caveat matters: node features, edge labels, random identifiers, Laplacian or positional encodings, subgraph methods, higher-order WL variants, and graph transformers can add information that the bare unlabeled 1-WL test does not have. The demo below teaches the bottleneck, not the end of graph learning.

03

03

Code

Keep the implementation aligned with the notation so the algorithm is legible.

Section prompt
Runnable code 1from collections import Counter def wl_histories(edges, n, rounds=3): nbrs = {i: [] for i in...python
from collections import Counter

def wl_histories(edges, n, rounds=3):
    nbrs = {i: [] for i in range(n)}
    for a, b in edges:
        nbrs[a].append(b); nbrs[b].append(a)

    colors = ["x"] * n
    histories = [Counter(colors)]
    for _ in range(rounds):
        signatures = [
            (colors[v], tuple(sorted(colors[u] for u in nbrs[v])))
            for v in range(n)
        ]
        ids = {sig: f"c{i}" for i, sig in enumerate(sorted(set(signatures)))}
        colors = [ids[sig] for sig in signatures]
        histories.append(Counter(colors))
    return histories

cycle6 = [(0,1), (1,2), (2,3), (3,4), (4,5), (5,0)]
triangles = [(0,1), (1,2), (2,0), (3,4), (4,5), (5,3)]

for t, (a, b) in enumerate(zip(wl_histories(cycle6, 6), wl_histories(triangles, 6))):
    print(t, dict(a), dict(b), "same histogram?", a == b)

This code uses identical starting node features. Some library implementations use degree as an initial fallback when no node label is provided. That is useful for hashing, but the teaching witness here is the standard unlabeled color-refinement thought experiment with all nodes initially identical.

04

04

Interactive Demo

Use direct manipulation to connect the explanation to a moving system.

Section prompt

Use the Color Refinement Lab to predict whether 1-WL will distinguish the selected pair.

The failure pair is the one to remember: C6C_6 versus two disconnected triangles. The graphs differ globally, but every node keeps hearing the same local multiset story.

The contrast pair, path versus star, shows what success looks like. When degree patterns differ, the first refinement round splits the histograms immediately.

Live Concept Demo

Explore Graph Expressivity and Weisfeiler-Lehman

The stage is code-native and interactive. Use it to test the explanation against the mechanism.

difficulty 4/5graduatecode-aligned
Demo Prediction Checkpoint

Manipulate one control and predict the visible change.

Commit to what Graph Expressivity and Weisfeiler-Lehman should make visible before reading the result.

After The First Pass

Turn the concept into an inspected object.

Once the invariant is visible in the intuition, math, code, and demo, use these panels to inspect the mechanism visually, check source support, practice the idea, and attach a grounded research question.

Mechanism Storyboard

See the idea move before the page explains it

Weisfeiler-Lehman color refinement shows a sharp limit of local message passing: some non-isomorphic graphs keep the same color histograms forever.

Prediction open01 / Intuition
Prediction lens

Start with the picture, metaphor, or geometric mechanism.

Commit first

Before reading further, choose the kind of change Graph Expressivity and Weisfeiler-Lehman should make visible.

Visual Inquiry

Make the image answer a mathematical question

Weisfeiler-Lehman color refinement shows a sharp limit of local message passing: some non-isomorphic graphs keep the same color histograms forever.

4/4 stages readyLive demo connected
Prediction

Which visible object should carry the first intuition?

Commit first

Pick the cue that should make Graph Expressivity and Weisfeiler-Lehman easier to reason about before the page gives the answer.

Source Grounding

Canonical references for the mechanism on this page.

paper · 2019How Powerful are Graph Neural Networks?Xu, Hu, Leskovec, and Jegelka

Primary GIN source connecting message-passing GNN discriminative power to the Weisfeiler-Lehman graph isomorphism test.

Open source
paper · 2019Weisfeiler and Leman Go Neural: Higher-order Graph Neural NetworksMorris et al.

Primary source for relating neighborhood aggregation GNNs to 1-WL and motivating higher-order variants.

Open source
paper · 2011Weisfeiler-Lehman Graph KernelsShervashidze et al.

Graph-kernel source for iterative relabeling through sorted neighbor-label multisets.

Open source
course-notes · 2026Stanford CS224W: GNN ExpressivenessStanford CS224W

Course source for WL color refinement and graph neural network expressiveness framing.

Open source
documentation · 2026NetworkX: weisfeiler_lehman_graph_hashNetworkX

Implementation reference for iterative node-label aggregation and graph-level histogram hashes.

Open source

Claim Review

Weisfeiler-Lehman color refinement shows a sharp limit of local message passing: some non-isomorphic graphs keep the same color histograms forever.

Status1 substantive review recorded

Claims without a substantive review badge still need exact source-support review.

Sources5 references

xu-2019-gin, morris-2019-wl-go-neural, shervashidze-2011-wl-kernels, cs224w-gnn-theory, networkx-wl-hash-2026

Local checks4 local checks

Use equations, runnable code, and demos to check whether the source support is operational.

Substantively reviewed1-WL updates each node from its current color and neighbor-color multiset, giving a useful expressivity lens for permutation-invariant message passing.Claim metadata: source checked

The sources support the page's local color-refinement update, graph-level color-histogram comparison, the 1-WL expressivity lens for neighborhood-aggregation GNNs, and the need to distinguish this finite witness from stronger graph models.

Sources: How Powerful are Graph Neural Networks?, Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks, Weisfeiler-Lehman Graph Kernels, Stanford CS224W: GNN Expressiveness, NetworkX: weisfeiler_lehman_graph_hashTiny unlabeled-graph witness only; it does not train a GNN, prove the full 1-WL theorem, cover node/edge labels, random IDs, positional or structural encodings, subgraph GNNs, higher-order WL tests, graph transformers, or real benchmark performance.A bounded review summary is present; still check caveats and exact reference scope.

Checked Xu et al. for the GNN/1-WL expressivity connection and GIN motivation; Morris et al. for the 1-WL and higher-order GNN relationship; Shervashidze et al. for sorted-neighbor-label relabeling; CS224W theory slides for course-level expressiveness framing; and NetworkX docs for the practical iterative hash procedure. GPT Pro publication critique remains pending because 127.0.0.1:51672 is unavailable.

Reviewer: codex-local-source-review; reviewed 2026-07-02
Equation 1Runnable code 1Interactive demo

Source support candidates

paper 2019How Powerful are Graph Neural Networks?

Primary GIN source connecting message-passing GNN discriminative power to the Weisfeiler-Lehman graph isomorphism test.

paper 2019Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks

Primary source for relating neighborhood aggregation GNNs to 1-WL and motivating higher-order variants.

paper 2011Weisfeiler-Lehman Graph Kernels

Graph-kernel source for iterative relabeling through sorted neighbor-label multisets.

course-notes 2026Stanford CS224W: GNN Expressiveness

Course source for WL color refinement and graph neural network expressiveness framing.

Mechanism checks

Equation 1
ct(v).c_t(v).
Equation 2
st(v)=(ct(v),  multiset⁡{ct(u):u∈N(v)}).s_t(v) = \left(c_t(v),\; \operatorname{multiset}\{c_t(u):u\in\mathcal N(v)\}\right).
Runnable code 1from collections import Counter def wl_histories(edges, n, rounds=3): nbrs = {i: [] for i in...Demo stateLive mechanism probe

Practice Loop

Try the idea before it explains itself

Weisfeiler-Lehman color refinement shows a sharp limit of local message passing: some non-isomorphic graphs keep the same color histograms forever.

Readiness0/3 checks ready
Predict

Before touching the demo, predict one visible change that should happen in Graph Expressivity and Weisfeiler-Lehman.

Hint 1

Reveal when your model needs a nudge.

Hint 2

Reveal when your model needs a nudge.

Hint 3

Reveal when your model needs a nudge.

Grounded research drawerClose
ConceptGraph Expressivity and Weisfeiler-LehmanMachine Learning
Runnable code comparisonGraph Expressivity and Weisfeiler-Lehman runnable code 1nbrs = {i: [] for i in range(n)}Prediction before revealGraph Expressivity and Weisfeiler-Lehman interactive demoManipulate one control and predict the visible change.
Grounded room questionWhat is the smallest example that makes Graph Expressivity and Weisfeiler-Lehman click without losing the math?Local snapshot ready

Research Room

Attach the question to a claim, equation, code, or demo

Pick the concept, equation, source, runnable code, claim, misconception, or demo state before asking for help. The handoff keeps that page item in context.
Next local actionNo local draft saved yet

Open the draft below to save one note and next action in this browser.

conceptMachine Learning

Graph Expressivity and Weisfeiler-Lehman

Attached question

What is the smallest example that makes Graph Expressivity and Weisfeiler-Lehman click without losing the math?

Local action draftNo local draft saved yetExpand only when ready to capture one local next action
Local action draft

This draft stays in this browser, attached to the selected learning item.

No local draft saved.
Evidence to inspect
  • References to inspect: attached references on this page.
  • Definition, prerequisite, and contrast concept links
  • The equation or runnable code that makes the concept operational
  • One demo state that shows the invariant instead of a slogan
What would resolve this
  • The learner can state the mechanism in their own words
  • The learner can name the prerequisite that would repair confusion
  • The learner can predict how the mechanism changes under one perturbation
Grounded AI handoff

I am working in Continuous Function's research reading room. Object: concept - Graph Expressivity and Weisfeiler-Lehman Selected item key: recorded for copy. Context: Machine Learning Page anchor: recorded for copy. Open question: What is the smallest example that makes Graph Expressivity and Weisfeiler-Lehman click without losing the math? Evidence to inspect: - References to inspect: attached references on this page. - Definition, prerequisite, and contrast concept links - The equation or runnable code that makes the concept operational - One demo state that shows the invariant instead of a slogan What would resolve this: - The learner can state the mechanism in their own words - The learner can name the prerequisite that would repair confusion - The learner can predict how the mechanism changes under one perturbation Answer as a careful research tutor: stay source-grounded, separate verified evidence from assumptions, name the relevant math objects, and end with one next action.

View it in context
concept/concept-notebook/machine-learning/graph-expressivity-weisfeiler-lehman concept:machine-learning/graph-expressivity-weisfeiler-lehman