CoreSource checked

Weisfeiler-Lehman Refinement

Refines graph vertex colors by repeatedly encoding each vertex's neighborhood color multiset.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Graph Traversal
Difficulty: Intermediate
Family: Graph Isomorphism
Tier: Core
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 0
Relationships: 4
Code example: Ready
Visualization: Ready

Overview

Weisfeiler-Lehman refinement assigns new colors from each vertex's current color and the multiset of neighbor colors, repeating until the coloring stabilizes or a fixed number of rounds is reached.

Core Concepts

color refinementneighbor multisetgraph signatureisomorphism screeningsimultaneous update

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(V + E)

Average

O((V + E) log V)

Worst

O(V^2 + E)

Space

O(V + E)

When to Use

Use when local neighborhood signatures are a useful discriminator.
Use as a fast filter or feature generator, not as the only proof for hard graph pairs.

When Not to Use

Avoid treating matching color histograms as a complete isomorphism proof.
Avoid when edge directions, labels, or attributes matter but are not encoded in the signatures.

What It Does

Produces increasingly detailed local structural signatures for graph vertices.
Separates many non-isomorphic graphs by comparing color histograms.
Provides graph features for kernels and learning pipelines.

Use Cases

Fast graph-isomorphism screening before exact search.
Feature extraction for graph kernels or graph classification.
Partition refinement where local neighborhood structure should be summarized compactly.

Inputs

Two graphs G_1, G_2 or a single graph G = (V, E) with vertex partitions

Outputs

Canonical graph certificate and automorphism group generators

Pseudocode

1.Assign initial colors from labels or a single default color
2.Repeat until stable or the round limit is reached
3.For each vertex, collect the multiset of old neighbor colors
4.Create a signature from old vertex color and neighbor multiset
5.Intern equal signatures to equal new color ids
6.Replace all vertex colors simultaneously
7.Return final colors or per-round color histograms

Canonical Example

Input: path A-B-C with all vertices initially color 0
Output: after one round, B has a different color from endpoints A and C
Explanation: B sees two neighbors of color 0, while each endpoint sees one neighbor of color 0.

Implementation Notes

Build signatures from old colors, then replace all colors simultaneously.
Represent neighbor color multisets deterministically, such as sorted counts.
Compare color histograms after each round if using refinement as an isomorphism filter.

Common Pitfalls

Some non-isomorphic graphs remain indistinguishable under 1-WL refinement.
New color ids must be assigned consistently from identical signatures within each round.
Updating colors in place before all signatures are computed changes the refinement rule.