Weisfeiler and Leman go Machine Learning: The Story so far

Christopher Morris; Yaron Lipman; Haggai Maron; Bastian Rieck; Nils M. Kriege; Martin Grohe; Matthias Fey; Karsten Borgwardt

Source-linked AI summary

Weisfeiler and Leman go Machine Learning: The Story so far

Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M. Kriege, Martin Grohe, Matthias Fey, Karsten Borgwardt

arXiv:2112.09992v4Dec 18, 2021cs.LGcs.DScs.NEstat.ML

TL;DR

Machine learning with graphs needs representations that handle irregular structure, attributes, permutation behavior, scale, and generalization. This survey organizes the Weisfeiler–Leman method, its graph-kernel and neural extensions, and its theoretical connections to equivariant architectures. It concludes by synthesizing applications and identifying limitations and future research directions.

Problem
Graph-learning methods must produce useful node and graph representations while handling irregular structure, attributes, permutation invariance or equivariance, scalability, and generalization.
Method
The paper surveys WL theory, WL-based graph kernels, supervised graph and node representation learning, GNN connections, equivariant architectures, applications, and open challenges.
Results
The survey connects 1-WL and k-WL expressive power with GNNs and higher-order equivariant architectures, and reviews architectures beyond 1-WL.
Takeaways & Limitations
The Weisfeiler–Leman paradigm provides a framework for understanding graph kernels, GNN expressivity, equivariant architectures, applications, and future research.
Takeaways & Limitations
The WL paradigm does not fully capture GNN expressivity for real-valued attributes, distance-based feature similarity, or spectral GNNs.

Abstract

from arXiv · show

In recent years, algorithms and neural architectures based on the Weisfeiler--Leman algorithm, a well-known heuristic for the graph isomorphism problem, have emerged as a powerful tool for machine learning with graphs and relational data. Here, we give a comprehensive overview of the algorithm's use in a machine-learning setting, focusing on the supervised regime. We discuss the theoretical background, show how to use it for supervised graph and node representation learning, discuss recent extensions, and outline the algorithm's connection to (permutation-)equivariant neural architectures. Moreover, we give an overview of current applications and future directions to stimulate further research.

1. Introduction

Graph-structured data appears across many domains, motivating embeddings that preserve graph structure and support supervised learning. The survey traces Weisfeiler–Leman-based kernels and neural architectures as approaches to these representation-learning challenges.

Graph data is used in cheminformatics, biology, computer vision, and social-network analysis, where models must exploit node and edge structure.
Graph and node embeddings convert irregular graph data into vectorial representations for standard machine-learning methods.
Successful embeddings should respect permutation invariance for graphs, permutation equivariance for nodes, scalability, attributes, and generalization to unseen instances.
The 1-WL algorithm iteratively refines node labels using neighbor-label counts but cannot distinguish all non-isomorphic graphs, including graphs differing in cyclic information.
The Weisfeiler–Lehman subtree kernel represents graphs with color-count vectors and compares them through inner products, while exact subgraph matching can miss partial similarities.
The survey covers WL-based graph kernels, their links to GNNs and equivariant neural architectures, applications, and future research directions.

2. Preliminaries

The preliminaries define graphs, labels, attributes, neighborhoods, isomorphism, permutation behavior, and kernels. These concepts establish the notation for discussing WL algorithms and graph-learning representations.

A graph consists of nodes and edges, while labeled and attributed graphs attach discrete labels or real-valued vectors to nodes and edges.
Two graphs are isomorphic when an edge-preserving bijection maps one graph to the other while preserving labels when present.
Permutation invariance requires graph outputs to remain unchanged under node reordering, whereas equivariance requires node outputs to reorder correspondingly.
A graph kernel is a positive semi-definite symmetric similarity function represented as an inner product in a feature space.

3. The Weisfeiler–Leman Method

The Weisfeiler–Leman method iteratively refines colors using neighborhood information, with higher-dimensional variants coloring tuples to increase distinguishing power. Its expressive strength is structured by graph classes, dimension, and computational limits.

1-WL: 1-WL initializes node colors from labels or a constant and repeatedly assigns colors based on neighboring colors until refinement stabilizes.
1-WL: After k iterations, a node’s color captures structural information from its k-hop neighborhood.
k-FWL: 1-WL can fail on non-isomorphic graphs, while k-FWL generalizes refinement by coloring k-tuples rather than individual nodes.
k-FWL: Increasing k strictly increases distinguishing power: for every k ≥1, some graphs are distinguished by (k + 1)-WL but not by k-WL.
Theoretical properties: The WL hierarchy has persistent limits: 2-FWL cannot distinguish strongly regular graphs with the same parameters, and every k has non-isomorphic graphs that k-FWL fails to distinguish.
Theoretical properties: WL dimension is bounded for several structurally restricted graph classes, including planar graphs, graphs of bounded genus, and graphs of bounded treewidth.
Theoretical properties: Stable coloring can require substantial computation, with k-FWL taking O(k2nk+1 log n) time and fixed-k distinction being PTIME-complete.

4. Non-neural Methods for Machine Learning Based on the Weisfeiler–Leman Algorithm

Non-neural Weisfeiler–Leman methods turn iterative color refinement into graph feature vectors and kernels, then extend this framework to edges, paths, matching, continuous attributes, topology, and higher-dimensional variants.

Weisfeiler–Lehman subtree kernels: The Weisfeiler–Lehman subtree kernel concatenates color histograms across refinement iterations and compares graphs through inner products.Each histogram counts occurrences of colors at one iteration; the resulting kernel sums matching-color node pairs over all refinement steps.
Weisfeiler–Lehman subtree kernels: O(hm) time computes one feature vector, while linear SVMs avoid the quadratic Gram-matrix overhead for large graph datasets.The Gram matrix costs O(Nhm + N2hn) under linear-time perfect hashing, with n and m denoting maximum nodes and edges.
Kernel variations: Edge and shortest-path variants incorporate incident-node colors, path lengths, and edge information beyond node-color counts.The shortest-path representation uses triples containing endpoint labels and path length, which may include edge weights.
Matching-based kernels: The optimal assignment kernel uses the 1-WL hierarchy to compare structurally similar node neighborhoods and achieves better accuracy in many classification experiments than the subtree kernel.Its hierarchy-based computation is linear time, and hierarchy weights can be optimized through multiple kernel learning.
Continuous attributes: Hash graph kernels extend 1-WL to continuous attributes with multiple hash functions, while retaining asymptotic complexity no higher than 1-WL under a fixed iteration count.Their evaluation complexity is O(J(hm + th)) when J is fixed and hashing is no more complex than computing 1-WL feature vectors.
Extensions: Topology-aware and higher-dimensional extensions add information beyond standard 1-WL, including cycles, faster k-OWL variants, and empirically improved benchmark performance.Topology-aware reweighting particularly improves molecular datasets; a k-OWL variant achieves state-of-the-art results while being several orders of magnitude faster than k-OWL.

5. Connections to Graph Neural Networks

The 1-WL algorithm characterizes the expressive ceiling of standard GNNs, while injective aggregation can match that ceiling. Several higher-order and symmetry-breaking architectures extend expressivity beyond 1-WL through tuple, identifier, permutation, random-feature, and subgraph information.

GNNs and the 1-WL algorithm: Any GNN is at most as powerful as 1-WL for distinguishing non-isomorphic graphs, regardless of its functions or parameters.
GNNs and the 1-WL algorithm: GNNs match 1-WL expressivity when their merge and aggregation functions are injective, including architectures using linearly independent encodings of initial labels.
GNNs and the 1-WL algorithm: GIN has the same expressive power as 1-WL for distinguishing non-isomorphic graphs.
Neural Architectures Beyond 1-WL’s Expressive Power: Higher-order GNNs learn features over k-node subgraphs, overcoming limitations of 1-WL by representing structural patterns beyond node-level aggregation.
Neural Architectures Beyond 1-WL’s Expressive Power: Unique identifiers, relational pooling, and random node features increase GNN expressivity through matrix contexts, permutation averaging, or randomized initialization.
Neural Architectures Beyond 1-WL’s Expressive Power: Subgraph-enhanced GNNs use node or edge roles, homomorphism counts, or extracted subgraphs to become more powerful than 1-WL under suitable structural choices.

6. Equivariant Graph Networks and the Weisfeiler–Leman Algorithm

This section connects permutation-equivariant graph neural networks to the Weisfeiler–Leman hierarchy, showing how tensor representations and equivariant layers reproduce WL update steps and separation power. It also characterizes these layers and notes the computational cost of universal constructions.

6.1 Equivariant Graph Networks: Graph data is encoded as tensors containing adjacency information, edge features, node features, or features attached to k-tuples of nodes.These representations support ordinary graphs, higher-order WL colorings, and hypergraphs.
6.1 Equivariant Graph Networks: Permutation symmetries arise because reordering nodes yields an equivalent graph representation, motivating invariant graph outputs and equivariant node or tensor outputs.The relevant symmetry group is the permutation group S_n acting on graph tensors.
6.1 Equivariant Graph Networks: The space of linear S_n-equivariant layers from R^n² to R^n² is 15-dimensional, with basis elements indexed by equality patterns of four indices.More generally, layers from R^nᵏ to R^nˡ have dimension bell(k + l).
6.1 Equivariant Graph Networks: The dimension of the equivariant-layer space is independent of graph size, allowing shared learned parameters across graphs of different sizes.This size-independent characterization also extends to higher-order tensor maps.
6.2 Expressive Power and Weisfeiler–Leman Hierarchy: Equivariant networks with tensors of order k can represent finite k-WL update steps, so k-order models separate graphs distinguished by k-WL.The corresponding separation power is stated to coincide with k-OWL for ordinary equivariant networks and k-FWL for polynomial variants.
6.2 Expressive Power and Weisfeiler–Leman Hierarchy: Universal equivariant constructions can be impractical because one construction uses O(n^4) order tensors.The section notes that more efficient universal constructions remain unfeasible in the cited results.

7. Expressivity and Generalization Abilities of GNNs

This section frames GNN generalization as an open issue beyond expressive power. Existing bounds use classical graph parameters, but those parameters do not fully capture the structure of real-world graphs.

7. Expressivity and Generalization Abilities of GNNs: Existing GNN generalization-error bounds express ability using parameters such as maximum degree, vertex count, or edge count.The section states that these classical parameters cannot fully capture complex real-world graph structure.

8. Applications

This section surveys Weisfeiler–Leman-related methods across graph-learning applications, including code, knowledge graphs, molecules, vision, and graph matching. It emphasizes adapting graph representations and refinement procedures to domain-specific structure and constraints.

8. Applications: Graph-based machine learning is applied across cheminformatics, bioinformatics, neuroscience, natural-language processing, social-network analysis, and computer vision.The paper notes that general-purpose Weisfeiler–Leman-related methods have proven highly effective across these domains.
8. Applications: The Weisfeiler–Leman graph kernel represents programs through API-call or data-flow graphs to measure source-code similarity.The resulting similarities can help identify related code in online repositories.
8. Applications: For malware detection, Weisfeiler–Leman refinement incorporates context labels such as whether a user is aware of code execution.The graph model is extended because structural information alone is insufficient for the described setting.
8. Applications: Weisfeiler–Leman kernels can be adapted to heterogeneous knowledge graphs containing typed nodes, attributes, and typed relationships.The cited RDF adaptation targets Resource Description Framework data.
8. Applications: Molecular graph learning must often account for three-dimensional conformations because molecular properties can depend on geometric atom arrangements.Different conformations can make identifying the relevant geometry part of the learning problem.
8. Applications: Domain-specific molecular GNNs use recurrent hierarchical message passing or multiple graph abstractions to capture long-range and multiscale molecular effects.The cited fuel-ignition model combines standard and higher-order GNNs, while another architecture exchanges messages between atom-level and group-level graphs.
8. Applications: Graph representations support vision tasks involving scene graphs, keypoints, superpixels, point clouds, and manifolds by introducing relational inductive biases.The section also connects these models to permutation-invariant architectures for sets and scene-graph prediction.
8. Applications: Weisfeiler–Leman refinement provides a simple graph-matching heuristic by organizing nodes into a hierarchy and matching available nodes from leaves toward the root.Graph matching variants include maximum common subgraph isomorphism, network alignment, graph matching, and graph edit distance.

9. Open Challenges, Limitations, Future Research Directions

The survey identifies limitations in WL-based equivariant architectures involving scalability, optimization, generalization, depth, expert knowledge, attributed graphs, similarity, and spectral information, and formulates open research challenges around them.

Scalability and Expressivity: Universal WL-based equivariant architectures can be exponentially expensive in k, motivating designs that better balance expressive power and scalability.The cost arises, for example, from operating on k-order tensors.
Optimization and Expressivity: Existential expressivity results do not guarantee convergence under standard first-order optimization methods.The survey therefore calls for studying how optimization affects the expressive power of WL-based architectures.
Optimization and Generalization: The relationship between optimization and generalization in WL-based equivariant architectures remains insufficiently understood.Existing work is limited, including analysis based on a linearized GNN and factors such as skip connections, depth, and label distribution.
Locality and Depth: Using more than a small number of WL iterations or GNN layers can cause overfitting or over-smoothing, while large neighborhoods remain difficult to represent accurately.These locality-related problems limit the capture of global or long-range information and motivate depth studies.
Expert Knowledge: WL-based methods often use expert knowledge only ad hoc, motivating architectures that provably capture task-relevant graph structure specified by domain expertise.The survey highlights functional-group and pharmacophore information in cheminformatics as an example.
Limitations and Future Directions: Because WL is discrete, its expressivity implications for real-valued node attributes and its usefulness as a fine-grained similarity measure remain limited.The survey also notes that the framework primarily characterizes message-passing GNNs, leaving the role of spectral information open.

10. Conclusion

The paper surveys WL-based machine learning for graphs, covering its theory, kernels, GNN connections, equivariant architectures, applications, and open challenges. It presents the survey as a handbook intended to support future research at the intersection of graph theory and machine learning.

Conclusion: The survey introduces 1-WL and k-WL, reviews their theory and graph kernels, and connects them to GNNs and more powerful equivariant architectures.It also surveys applications and identifies open challenges and future research directions.
Conclusion: The authors position the survey as a handbook of graph representation-learning methods, perspectives, and limitations intended to spur research connecting graph theory and machine learning.The stated aim is to support novel research at this intersection.